OSA's Digital Library

Journal of the Optical Society of America A

Journal of the Optical Society of America A


  • Editor: Franco Gori
  • Vol. 30, Iss. 6 — Jun. 1, 2013
  • pp: 1184–1192

Fast and accurate circle detection using gradient-direction-based segmentation

Jianping Wu, Ke Chen, and Xiaohui Gao  »View Author Affiliations

JOSA A, Vol. 30, Issue 6, pp. 1184-1192 (2013)

View Full Text Article

Enhanced HTML    Acrobat PDF (701 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



We present what is to our knowledge the first-ever fitting-based circle detection algorithm, namely, the fast and accurate circle (FACILE) detection algorithm, based on gradient-direction-based edge clustering and direct least square fitting. Edges are segmented into sections based on gradient directions, and each section is validated separately; valid arcs are then fitted and further merged to extract more accurate circle information. We implemented the algorithm with the C++ language and compared it with four other algorithms. Testing on simulated data showed FACILE was far superior to the randomized Hough transform, standard Hough transform, and fast circle detection using gradient pair vectors with regard to processing speed and detection reliability. Testing on publicly available standard datasets showed FACILE outperformed robust and precise circular detection, a state-of-art arc detection method, by 35% with regard to recognition rate and is also a significant improvement over the latter in processing speed.

© 2013 Optical Society of America

OCIS Codes
(040.1880) Detectors : Detection
(150.1135) Machine vision : Algorithms

ToC Category:

Original Manuscript: January 10, 2013
Revised Manuscript: March 23, 2013
Manuscript Accepted: April 24, 2013
Published: May 20, 2013

Jianping Wu, Ke Chen, and Xiaohui Gao, "Fast and accurate circle detection using gradient-direction-based segmentation," J. Opt. Soc. Am. A 30, 1184-1192 (2013)

Sort:  Author  |  Year  |  Journal  |  Reset  


  1. P. V. C. Hough, “Method and means for recognizing complex patterns,” U.S. patent 3,069,654 (18December1962).
  2. R. Duda and P. Hart, “Use of the Hough transform to detect lines and curves in pictures,” Commun. ACM 15, 11–15 (1972). [CrossRef]
  3. E. Davies, “A modified Hough scheme for general circle location,” Pattern Recogn. Lett. 7, 37–43 (1988). [CrossRef]
  4. P. Kierkegaard, “A method for detection of circular arcs based on the Hough transform,” Machine Vis. Appl. 5, 249–263 (1992). [CrossRef]
  5. T. Atherton and D. Kerbyson, “Using phase to represent radius in the coherent circle Hough transform,” in Proceedings of IEE Colloquium on the Hough Transform (IEE, 1993), paper 5.
  6. C. Kimme, D. Ballard, and J. Sklansky, “Finding circles by an array of accumulators,” Proc. ACM 18, 120–122 (1975). [CrossRef]
  7. L. Minor and J. Sklansky, “Detection and segmentation of blobs in infrared images,” IEEE Trans. Syst. Man Cybern 11, 194–201 (1981). [CrossRef]
  8. T. Atherton and D. Kerbyson, “Size invariant circle detection,” Image Vis. Comput. 17, 196–803 (1999). [CrossRef]
  9. D. Kerbyson and T. Atherton, “Circle detection using Hough transform filters,” in IEE Conference on Image Processing and Its Applications (IEE, 1995), pp. 370–374.
  10. F. Nashashibi, A. Bafgeton, F. Moutarde, and B. Bradai, “Method of circle detection in images for round traffic sign identification and vehicle driving assistance device,” World Intellectual Property Organization patent WO2012076036 (14June2012).
  11. R. Dave, “Fuzzy shell-clustering and applications to circle detection in digital images,” Int. J. Gen. Syst. 16, 343–355 (1990). [CrossRef]
  12. R. Dave, “Generalized fuzzy c-shells clustering and detection of circular and elliptical boundaries,” Pattern Recogn. 25, 713–721 (1992). [CrossRef]
  13. J. Bezdek and R. Hathaway, “Numerical convergence and interpretation of the fuzzy c-shell clustering algorithm,” IEEE Trans. Neural Netw. 3, 787–793 (1992). [CrossRef]
  14. R. Krishnapuram, O. Nasraoui, and H. Frigui, “The fuzzy C spherical shells algorithm: a new approach,” IEEE Trans. Neural Netw. 3, 663–671 (1992). [CrossRef]
  15. G. Schuster and A. Katsaggelos, “Robust circle detection using a weighted MSE estimator,” in International Conference on Image Processing (ICIP) (IEEE, 2004), pp. 2111–2114.
  16. M. Ceccarelli, A. Petrosino, and G. Laccetti, “Circle detection based on orientation matching,” in 11th International Conference on Image Analysis and Processing Proceedings (IEEE, 2001), pp. 119–124.
  17. A. Rad, K. Faez, and N. Qaragozlou, “Fast circle detection using gradient pair vectors,” in Proceedings of 7th Digital Image Computing: Techniques and Applications (CSIRO, 2003), pp. 10–12.
  18. J. Yao, “Fast robust genetic algorithm based ellipse detection,” in 17th International Conference on Pattern Recognition (IEEE, 2004), Vol. 2, pp. 859–862.
  19. V. Ayala-Ramirez, C. H. Garcia-Capulin, A. Perez-Garcia, and R. E. Sanchez-Yanez, “Circle detection on images using genetic algorithm,” Pattern Recogn. Lett. 27, 652–657 (2006). [CrossRef]
  20. S. Dasgupta, S. Das, A. Biswas, and A. Abraham, “Automatic circle detection on digital images using an adaptive bacterial foraging algorithm,” Soft Comput. A 14, 1151–1164 (2009). [CrossRef]
  21. L. Xu, E. Oja, and P. Kultanen, “A new curve detection method: randomized Hough transform,” Pattern Recogn. Lett. 11, 331–338 (1990). [CrossRef]
  22. T. C. Chen and K. Chung, “An efficient randomized algorithm for detecting circles,” Comput. Vis. Image Underst. 83, 172–191 (2001). [CrossRef]
  23. K. Chung and Y. Huang, “Speed up the computation of randomized algorithms for detecting lines, circles, and ellipses using novel tuning-and-LUT-based voting platform,” Appl. Math. Comput. 190, 132–149 (2007). [CrossRef]
  24. B. Lamiroy and Y. Guebbas, “Robust and precise circular arc detection,” in Graphics Recognition, Achievements, Challenges, and Evolution, Vol. 6020 of Lecture Notes in Computer Science (Springer, 2010), pp. 49–60. [CrossRef]
  25. H. Al-Khaffaf, A. Talib, and M. Osman, “Final report of GREC’11 arc segmentation contest: performance evaluation on multi-resolution scanned documents,” in Graphics Recognition: New Trends and Challenges, Vol. 7423 of Lecture Notes in Computer Science (Springer, 2013), pp. 187–197. [CrossRef]
  26. J. Canny, “A computational approach to edge detection,” IEEE Trans. Pattern Anal. Mach. Intell. 8, 679–698 (1986). [CrossRef]
  27. W. Gander, G. Golub, and R. Strebel, “Least-squares fitting of circles and ellipses,” BIT 34, 558–578 (1994). [CrossRef]
  28. A. Fitzgibbon, M. Pilu, and R. Fisher, “Direct least square fitting of ellipses,” IEEE Trans. Pattern Anal. Mach. Intell. 21, 476–480 (1999). [CrossRef]
  29. I. Kasa, “A circle fitting procedure and its error analysis,” IEEE Trans. Instrum. Meas. IM-25, 8–14 (1976). [CrossRef]
  30. D. Umbach and K. N. Jones, “A few methods for fitting circles to data,” IEEE Trans. Instrum. Meas. 52, 1881–1885 (2003). [CrossRef]
  31. Qgar Software, http://www.qgar.org .
  32. “Inria Forge,” http://gforge.inria.fr/projects/visuvocab/ .
  33. W. Y. Liu and D. Dori, “A protocol for performance evaluation of line detection algorithms,” Machine Vis. Appl 9, 240–250 (1997). [CrossRef]
  34. “GREC’11 Arc Segmentation Contest,” http://www.cs.usm.my/arcseg2011 .
  35. http://www.cs.cityu.edu.hk/~liuwy/ArcContest/ArcContest2005.zip .

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited