Skip to main content
SpringerLink
Log in

Multi-circle detection on images using artificial bee colony (ABC) optimization

  • Original Paper
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

Hough transform has been the most common method for circle detection, exhibiting robustness, but adversely demanding considerable computational effort and large memory requirements. Alternative approaches include heuristic methods that employ iterative optimization procedures for detecting multiple circles. Since only one circle can be marked at each optimization cycle, multiple executions ought to be enforced in order to achieve multi-detection. This paper presents an algorithm for automatic detection of multiple circular shapes that considers the overall process as a multi-modal optimization problem. The approach is based on the artificial bee colony (ABC) algorithm, a swarm optimization algorithm inspired by the intelligent foraging behavior of honeybees. Unlike the original ABC algorithm, the proposed approach presents the addition of a memory for discarded solutions. Such memory allows holding important information regarding other local optima, which might have emerged during the optimization process. The detector uses a combination of three non-collinear edge points as parameters to determine circle candidates. A matching function (nectar-amount) determines if such circle candidates (bee-food sources) are actually present in the image. Guided by the values of such matching functions, the set of encoded candidate circles are evolved through the ABC algorithm so that the best candidate (global optimum) can be fitted into an actual circle within the edge-only image. Then, an analysis of the incorporated memory is executed in order to identify potential local optima, i.e., other circles. The proposed method is able to detect single or multiple circles from a digital image through only one optimization pass. Simulation results over several synthetic and natural images, with a varying range of complexity, validate the efficiency of the proposed technique regarding its accuracy, speed, and robustness.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  • Atherton TJ, Kerbyson DJ (1993) Using phase to represent radius in the coherent circle Hough transform. In: Proceedings of the IEE colloquium on the Hough transform. IEE, London

  • Ayala-Ramirez V, Garcia-Capulin CH, Perez-Garcia A, Sanchez-Yanez RE (2006) Circle detection on images using genetic algorithms. Pattern Recogn Lett 27:652–657

    Article  Google Scholar 

  • Aytug H, Koehler GJ (2000) New stopping criterion for genetic algorithms. Eur J Oper Res 126:662–674

    Article  MATH  MathSciNet  Google Scholar 

  • Becker J, Grousson S, Coltuc D (2002) From Hough transforms to integral transforms. In: Proceedings of the international geoscience and remote sensing symposium 2002 IGARSS_02, vol 3, pp 1444–1446

  • Bhowmick P, Bhattacharya BB (2008) Number-theoretic interpretation and construction of a digital circle. Discrete Appl Math 156:2381–2399

    Article  MATH  MathSciNet  Google Scholar 

  • Biswas A, Das S, Abraham A, Dasgupta S (2010) Stability analysis of the reproduction operator in bacterial foraging optimization. Theoret Comput Sci 411:2127–2139

    Article  MATH  MathSciNet  Google Scholar 

  • Bongiovanni G, Crescenzi P (1995) Parallel simulated annealing for shape detection. Comput Vis Image Underst 61(1):60–69

    Article  Google Scholar 

  • Bresenham JE (1987) A linear algorithm for incremental digital display of circular arcs. Commun ACM 20:100–106

    Article  Google Scholar 

  • Chen T-C, Chung K-L (2001) An efficient randomized algorithm for detecting circles. Comput Vis Image Underst 83:172–191

    Article  MATH  Google Scholar 

  • Chen Y, Jiang P (2010) Analysis of particle interaction in particle swarm optimization. Theoret Comput Sci 411(21):2101–2115

    Article  MATH  MathSciNet  Google Scholar 

  • da Fontoura Costa L, Marcondes Cesar R Jr (2001) Shape análisis and classification. CRC Press, Boca Raton

    Google Scholar 

  • Dasgupta S, Das S, Biswas A, Abraham A (2009) Automatic circle detection on digital images whit an adaptive bacterial foraging algorithm. Soft Comput. doi:10.1007/s00500-009-0508-z

  • Dorigo M, Maniezzo V, Colorni (1991) A positive feedback as a search strategy. Technical report 91-016, Politecnico di Milano, Italy

  • Fischer M, Bolles R (1981) Random sample consensus: a paradigm to model fitting with applications to image analysis and automated cartography. CACM 24(6):381–395

    Google Scholar 

  • Garcia S, Molina D, Lozano M, Herrera F (2008) A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization. J Heurist. doi:10.1007/s10732-008-9080-4

  • Greenhalgh D, Marshall S (2000) Convergence criteria for genetic algorithms. SIAM J Comput 20:269–282

    Article  MathSciNet  Google Scholar 

  • Han JH, Koczy LT, Poston T (1993) Fuzzy Hough transform. In: Proceedings of the 2nd international conference on fuzzy systems, vol 2, pp 803–808

  • Ho SL, Yang S (2009) An artificial bee colony algorithm for inverse problems. Int J Appl Electromagn Mech 31:181–192

    Google Scholar 

  • Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor

    Google Scholar 

  • Iivarinen J, Peura M, Sarela J, Visa A (1997) Comparison of combined shape descriptors for irregular objects. In: Proceedings of the 8th British machine vision conference, Cochester, UK, pp 430–439

  • Jones G, Princen J, Illingworth J, Kittler J (1990) Robust estimation of shape parameters. In: Proceedings of the British machine vision conference, pp 43–48

  • Kang F, Li J, Xu Q (2009) Structural inverse analysis by hybrid simplex artificial bee colony algorithms. Comput Struct 87:861–870

    Article  Google Scholar 

  • Karaboga D (2005) An idea based on honey bee swarm for numerical optimization, technical report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department

  • Karaboga N (2009) A new design method based on artificial bee colony algorithm for digital IIR filters. J Frankl Inst 346:328–348

    Article  MATH  MathSciNet  Google Scholar 

  • Karaboga D, Akay B (2009) A comparative study of Artificial Bee Colony algorithm. Appl Math Comput 214:108–132

    Article  MATH  MathSciNet  Google Scholar 

  • Karaboga D, Basturk B (2008) On the performance of artificial bee colony (ABC) algorithm. Appl Soft Comput 8(1):687–697

    Article  Google Scholar 

  • Karaboga D, Ozturk C (2011) A novel clustering approach: Artificial Bee Colony (ABC) algorithm. Appl Soft Comput 11:652–657

    Article  Google Scholar 

  • Kennedy J, Eberhart R (1995) Particle swarm optimization. In: IEEE international conference on neural networks, Piscataway, NJ, pp 1942–1948

  • Liu Y, Passino K (2002) Biomimicry of social foraging bacteria for distributed optimization: models, principles, and emergent behaviors. J Optim Theory Appl 115(3):603–628

    Article  MATH  MathSciNet  Google Scholar 

  • Mairessea F, Sliwa T, Binczak S, Voisina Y (2007) Subpixel determination of imperfect circles characteristics. Pattern Recogn 41:250–271

    Article  Google Scholar 

  • Muammar H, Nixon M (1989) Approaches to extending the Hough transform. In: Proceedings of the international conference on acoustics, speech and signal processing ICASSP_89, vol 3, pp 1556–1559

  • Pan Q-K, Fatih Tasgetiren M, Suganthan PN, Chua TJ (2010) A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Inf Sci. doi:10.1016/j.ins.2009.12.025

  • Peura M, Iivarinen J (1997) Efficiency of simple shape descriptors. In: Arcelli C, Cordella LP, di Baja GS (eds) Advances in visual form analysis. World Scientific, Singapore, pp 443–451

    Google Scholar 

  • Price K, Storn R, Lampinen A (2005) Differential evolution a practical approach to global optimization. In: Springer Natural Computing Series

  • Roth G, Levine MD (1994) Geometric primitive extraction using a genetic algorithm. IEEE Trans Pattern Anal Machine Intell 16(9):901–905

    Article  Google Scholar 

  • Sabat SL, Udgata SK, Abraham A (2010) Artificial bee colony algorithm for small signal model parameter extraction of MESFET. Eng Appl Artif Intell 23:689–694

    Article  Google Scholar 

  • Santamaría J, Cordón O, Damas S, García-Torres JM, Quirin A (2008) Performance evaluation of memetic approaches in 3D reconstruction of forensic objects. Soft Comput. doi:10.1007/s00500-008-0351-7

  • Shaked D, Yaron O, Kiryati N (1996) Deriving stopping rules for the probabilistic Hough transform by sequential analysis. Comput Vis Image Underst 63:512–526

    Article  Google Scholar 

  • Tvrdík J (2009) Adaptation in differential evolution: a numerical comparison. Appl Soft Comput 9(3):1149–1155

    Article  Google Scholar 

  • Van Aken JR (2005) Efficient ellipse-drawing algorithm. IEEE Comput Graph Appl 4(9):24–35

    Article  Google Scholar 

  • Weisstein EW (1999) Circle. From Mathworld—a wolfram web resource. http://mathworld.wolfram.com/Circle.html

  • Wilcoxon F (1945) Individual comparisons by ranking methods. Biometrics 1:80–83

    Article  Google Scholar 

  • Xu L, Oja E, Kultanen P (1990) A new curve detection method: randomized Hough transform (RHT). Pattern Recogn Lett 11(5):331–338

    Article  MATH  Google Scholar 

  • Xu C, Duan H, Liu F (2010) Chaotic artificial bee colony approach to Uninhabited Combat Air Vehicle (UCAV) path planning. Aerosp Sci Technol 14:535–541

    Article  Google Scholar 

  • Yuen H, Princen J, Illingworth J, Kittler J (1990) Comparative study of Hough transform methods for circle finding. Image Vis Comput 8(1):71–77

    Article  Google Scholar 

  • Zang H, Zhang S, Hapeshia K (2010) A review of nature-inspired algorithms. J Bionic Eng 7(1):S232–S237

    Article  Google Scholar 

  • Zhang C, Ouyang D, Ning J (2010) An artificial bee colony approach for clustering. Expert Syst Appl 37:4761–4767

    Article  Google Scholar 

Download references

Acknowledgments

Erik Cuevas would like to thank DAAD and SEP-PROMEP for their economical support. Authors thank to the European Union, the European Commission and the CONACYT for their support. This paper has been prepared by an economical support of the European Commission under grant FONCICYT 93829. The content of this paper is an exclusive responsibility of the UDEG and the CIC-IPN and it cannot be considered a reflection of the European Union position. The proposed algorithm belongs to the visual system operating on the biped robot which has been supported under the grant CONACYT CB 82877.

Author information

Authors and Affiliations

  1. Departamento de Ciencias Computacionales, Universidad de Guadalajara, CUCEI, Av. Revolución 1500, Guadalajara, Jal, Mexico

    Erik Cuevas, Felipe Sención-Echauri, Daniel Zaldivar & Marco Pérez-Cisneros

Authors
  1. Erik Cuevas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Felipe Sención-Echauri
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniel Zaldivar
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Marco Pérez-Cisneros
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniel Zaldivar.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cuevas, E., Sención-Echauri, F., Zaldivar, D. et al. Multi-circle detection on images using artificial bee colony (ABC) optimization. Soft Comput 16, 281–296 (2012). https://doi.org/10.1007/s00500-011-0741-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-011-0741-0

Keywords

Search

Navigation