Abstract

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

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  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 .

2009

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]

2007

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]

2006

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]

2003

D. Umbach and K. N. Jones, “A few methods for fitting circles to data,” IEEE Trans. Instrum. Meas. 52, 1881–1885 (2003).
[CrossRef]

2001

T. C. Chen and K. Chung, “An efficient randomized algorithm for detecting circles,” Comput. Vis. Image Underst. 83, 172–191 (2001).
[CrossRef]

1999

T. Atherton and D. Kerbyson, “Size invariant circle detection,” Image Vis. Comput. 17, 196–803 (1999).
[CrossRef]

A. Fitzgibbon, M. Pilu, and R. Fisher, “Direct least square fitting of ellipses,” IEEE Trans. Pattern Anal. Mach. Intell. 21, 476–480 (1999).
[CrossRef]

1997

W. Y. Liu and D. Dori, “A protocol for performance evaluation of line detection algorithms,” Machine Vis. Appl 9, 240–250 (1997).
[CrossRef]

1994

W. Gander, G. Golub, and R. Strebel, “Least-squares fitting of circles and ellipses,” BIT 34, 558–578 (1994).
[CrossRef]

1992

R. Dave, “Generalized fuzzy c-shells clustering and detection of circular and elliptical boundaries,” Pattern Recogn. 25, 713–721 (1992).
[CrossRef]

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]

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]

P. Kierkegaard, “A method for detection of circular arcs based on the Hough transform,” Machine Vis. Appl. 5, 249–263 (1992).
[CrossRef]

1990

R. Dave, “Fuzzy shell-clustering and applications to circle detection in digital images,” Int. J. Gen. Syst. 16, 343–355 (1990).
[CrossRef]

L. Xu, E. Oja, and P. Kultanen, “A new curve detection method: randomized Hough transform,” Pattern Recogn. Lett. 11, 331–338 (1990).
[CrossRef]

1988

E. Davies, “A modified Hough scheme for general circle location,” Pattern Recogn. Lett. 7, 37–43 (1988).
[CrossRef]

1986

J. Canny, “A computational approach to edge detection,” IEEE Trans. Pattern Anal. Mach. Intell. 8, 679–698 (1986).
[CrossRef]

1981

L. Minor and J. Sklansky, “Detection and segmentation of blobs in infrared images,” IEEE Trans. Syst. Man Cybern 11, 194–201 (1981).
[CrossRef]

1976

I. Kasa, “A circle fitting procedure and its error analysis,” IEEE Trans. Instrum. Meas. IM-25, 8–14 (1976).
[CrossRef]

1975

C. Kimme, D. Ballard, and J. Sklansky, “Finding circles by an array of accumulators,” Proc. ACM 18, 120–122 (1975).
[CrossRef]

1972

R. Duda and P. Hart, “Use of the Hough transform to detect lines and curves in pictures,” Commun. ACM 15, 11–15 (1972).
[CrossRef]

Abraham, A.

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]

Al-Khaffaf, H.

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]

Atherton, T.

T. Atherton and D. Kerbyson, “Size invariant circle detection,” Image Vis. Comput. 17, 196–803 (1999).
[CrossRef]

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.

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.

Ayala-Ramirez, V.

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]

Bafgeton, A.

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).

Ballard, D.

C. Kimme, D. Ballard, and J. Sklansky, “Finding circles by an array of accumulators,” Proc. ACM 18, 120–122 (1975).
[CrossRef]

Bezdek, J.

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]

Biswas, A.

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]

Bradai, B.

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).

Canny, J.

J. Canny, “A computational approach to edge detection,” IEEE Trans. Pattern Anal. Mach. Intell. 8, 679–698 (1986).
[CrossRef]

Ceccarelli, M.

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.

Chen, T. C.

T. C. Chen and K. Chung, “An efficient randomized algorithm for detecting circles,” Comput. Vis. Image Underst. 83, 172–191 (2001).
[CrossRef]

Chung, K.

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]

T. C. Chen and K. Chung, “An efficient randomized algorithm for detecting circles,” Comput. Vis. Image Underst. 83, 172–191 (2001).
[CrossRef]

Das, S.

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]

Dasgupta, S.

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]

Dave, R.

R. Dave, “Generalized fuzzy c-shells clustering and detection of circular and elliptical boundaries,” Pattern Recogn. 25, 713–721 (1992).
[CrossRef]

R. Dave, “Fuzzy shell-clustering and applications to circle detection in digital images,” Int. J. Gen. Syst. 16, 343–355 (1990).
[CrossRef]

Davies, E.

E. Davies, “A modified Hough scheme for general circle location,” Pattern Recogn. Lett. 7, 37–43 (1988).
[CrossRef]

Dori, D.

W. Y. Liu and D. Dori, “A protocol for performance evaluation of line detection algorithms,” Machine Vis. Appl 9, 240–250 (1997).
[CrossRef]

Duda, R.

R. Duda and P. Hart, “Use of the Hough transform to detect lines and curves in pictures,” Commun. ACM 15, 11–15 (1972).
[CrossRef]

Faez, K.

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.

Fisher, R.

A. Fitzgibbon, M. Pilu, and R. Fisher, “Direct least square fitting of ellipses,” IEEE Trans. Pattern Anal. Mach. Intell. 21, 476–480 (1999).
[CrossRef]

Fitzgibbon, A.

A. Fitzgibbon, M. Pilu, and R. Fisher, “Direct least square fitting of ellipses,” IEEE Trans. Pattern Anal. Mach. Intell. 21, 476–480 (1999).
[CrossRef]

Frigui, H.

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]

Gander, W.

W. Gander, G. Golub, and R. Strebel, “Least-squares fitting of circles and ellipses,” BIT 34, 558–578 (1994).
[CrossRef]

Garcia-Capulin, C. H.

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]

Golub, G.

W. Gander, G. Golub, and R. Strebel, “Least-squares fitting of circles and ellipses,” BIT 34, 558–578 (1994).
[CrossRef]

Guebbas, Y.

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]

Hart, P.

R. Duda and P. Hart, “Use of the Hough transform to detect lines and curves in pictures,” Commun. ACM 15, 11–15 (1972).
[CrossRef]

Hathaway, R.

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]

Hough, P. V. C.

P. V. C. Hough, “Method and means for recognizing complex patterns,” U.S. patent 3,069,654 (18December1962).

Huang, Y.

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]

Jones, K. N.

D. Umbach and K. N. Jones, “A few methods for fitting circles to data,” IEEE Trans. Instrum. Meas. 52, 1881–1885 (2003).
[CrossRef]

Kasa, I.

I. Kasa, “A circle fitting procedure and its error analysis,” IEEE Trans. Instrum. Meas. IM-25, 8–14 (1976).
[CrossRef]

Katsaggelos, A.

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.

Kerbyson, D.

T. Atherton and D. Kerbyson, “Size invariant circle detection,” Image Vis. Comput. 17, 196–803 (1999).
[CrossRef]

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.

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.

Kierkegaard, P.

P. Kierkegaard, “A method for detection of circular arcs based on the Hough transform,” Machine Vis. Appl. 5, 249–263 (1992).
[CrossRef]

Kimme, C.

C. Kimme, D. Ballard, and J. Sklansky, “Finding circles by an array of accumulators,” Proc. ACM 18, 120–122 (1975).
[CrossRef]

Krishnapuram, R.

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]

Kultanen, P.

L. Xu, E. Oja, and P. Kultanen, “A new curve detection method: randomized Hough transform,” Pattern Recogn. Lett. 11, 331–338 (1990).
[CrossRef]

Laccetti, G.

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.

Lamiroy, B.

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]

Liu, W. Y.

W. Y. Liu and D. Dori, “A protocol for performance evaluation of line detection algorithms,” Machine Vis. Appl 9, 240–250 (1997).
[CrossRef]

Minor, L.

L. Minor and J. Sklansky, “Detection and segmentation of blobs in infrared images,” IEEE Trans. Syst. Man Cybern 11, 194–201 (1981).
[CrossRef]

Moutarde, F.

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).

Nashashibi, F.

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).

Nasraoui, O.

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]

Oja, E.

L. Xu, E. Oja, and P. Kultanen, “A new curve detection method: randomized Hough transform,” Pattern Recogn. Lett. 11, 331–338 (1990).
[CrossRef]

Osman, M.

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]

Perez-Garcia, A.

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]

Petrosino, A.

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.

Pilu, M.

A. Fitzgibbon, M. Pilu, and R. Fisher, “Direct least square fitting of ellipses,” IEEE Trans. Pattern Anal. Mach. Intell. 21, 476–480 (1999).
[CrossRef]

Qaragozlou, N.

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.

Rad, A.

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.

Sanchez-Yanez, R. E.

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]

Schuster, G.

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.

Sklansky, J.

L. Minor and J. Sklansky, “Detection and segmentation of blobs in infrared images,” IEEE Trans. Syst. Man Cybern 11, 194–201 (1981).
[CrossRef]

C. Kimme, D. Ballard, and J. Sklansky, “Finding circles by an array of accumulators,” Proc. ACM 18, 120–122 (1975).
[CrossRef]

Strebel, R.

W. Gander, G. Golub, and R. Strebel, “Least-squares fitting of circles and ellipses,” BIT 34, 558–578 (1994).
[CrossRef]

Talib, A.

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]

Umbach, D.

D. Umbach and K. N. Jones, “A few methods for fitting circles to data,” IEEE Trans. Instrum. Meas. 52, 1881–1885 (2003).
[CrossRef]

Xu, L.

L. Xu, E. Oja, and P. Kultanen, “A new curve detection method: randomized Hough transform,” Pattern Recogn. Lett. 11, 331–338 (1990).
[CrossRef]

Yao, J.

J. Yao, “Fast robust genetic algorithm based ellipse detection,” in 17th International Conference on Pattern Recognition (IEEE, 2004), Vol. 2, pp. 859–862.

Appl. Math. Comput.

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]

BIT

W. Gander, G. Golub, and R. Strebel, “Least-squares fitting of circles and ellipses,” BIT 34, 558–578 (1994).
[CrossRef]

Commun. ACM

R. Duda and P. Hart, “Use of the Hough transform to detect lines and curves in pictures,” Commun. ACM 15, 11–15 (1972).
[CrossRef]

Comput. Vis. Image Underst.

T. C. Chen and K. Chung, “An efficient randomized algorithm for detecting circles,” Comput. Vis. Image Underst. 83, 172–191 (2001).
[CrossRef]

IEEE Trans. Instrum. Meas.

I. Kasa, “A circle fitting procedure and its error analysis,” IEEE Trans. Instrum. Meas. IM-25, 8–14 (1976).
[CrossRef]

D. Umbach and K. N. Jones, “A few methods for fitting circles to data,” IEEE Trans. Instrum. Meas. 52, 1881–1885 (2003).
[CrossRef]

IEEE Trans. Neural Netw.

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]

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]

IEEE Trans. Pattern Anal. Mach. Intell.

J. Canny, “A computational approach to edge detection,” IEEE Trans. Pattern Anal. Mach. Intell. 8, 679–698 (1986).
[CrossRef]

A. Fitzgibbon, M. Pilu, and R. Fisher, “Direct least square fitting of ellipses,” IEEE Trans. Pattern Anal. Mach. Intell. 21, 476–480 (1999).
[CrossRef]

IEEE Trans. Syst. Man Cybern

L. Minor and J. Sklansky, “Detection and segmentation of blobs in infrared images,” IEEE Trans. Syst. Man Cybern 11, 194–201 (1981).
[CrossRef]

Image Vis. Comput.

T. Atherton and D. Kerbyson, “Size invariant circle detection,” Image Vis. Comput. 17, 196–803 (1999).
[CrossRef]

Int. J. Gen. Syst.

R. Dave, “Fuzzy shell-clustering and applications to circle detection in digital images,” Int. J. Gen. Syst. 16, 343–355 (1990).
[CrossRef]

Machine Vis. Appl

W. Y. Liu and D. Dori, “A protocol for performance evaluation of line detection algorithms,” Machine Vis. Appl 9, 240–250 (1997).
[CrossRef]

Machine Vis. Appl.

P. Kierkegaard, “A method for detection of circular arcs based on the Hough transform,” Machine Vis. Appl. 5, 249–263 (1992).
[CrossRef]

Pattern Recogn.

R. Dave, “Generalized fuzzy c-shells clustering and detection of circular and elliptical boundaries,” Pattern Recogn. 25, 713–721 (1992).
[CrossRef]

Pattern Recogn. Lett.

E. Davies, “A modified Hough scheme for general circle location,” Pattern Recogn. Lett. 7, 37–43 (1988).
[CrossRef]

L. Xu, E. Oja, and P. Kultanen, “A new curve detection method: randomized Hough transform,” Pattern Recogn. Lett. 11, 331–338 (1990).
[CrossRef]

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]

Proc. ACM

C. Kimme, D. Ballard, and J. Sklansky, “Finding circles by an array of accumulators,” Proc. ACM 18, 120–122 (1975).
[CrossRef]

Soft Comput. A

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]

Other

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]

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]

“GREC’11 Arc Segmentation Contest,” http://www.cs.usm.my/arcseg2011 .

http://www.cs.cityu.edu.hk/~liuwy/ArcContest/ArcContest2005.zip .

Qgar Software, http://www.qgar.org .

“Inria Forge,” http://gforge.inria.fr/projects/visuvocab/ .

P. V. C. Hough, “Method and means for recognizing complex patterns,” U.S. patent 3,069,654 (18December1962).

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.

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.

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.

J. Yao, “Fast robust genetic algorithm based ellipse detection,” in 17th International Conference on Pattern Recognition (IEEE, 2004), Vol. 2, pp. 859–862.

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.

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.

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).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (9)

Fig. 1.
Fig. 1.

Step-by-step implementation of FACILE.

Fig. 2.
Fig. 2.

Edge segmentation.

Fig. 3.
Fig. 3.

ROI sift via ACB. A and B are the end points of the ROI and C is the midpoint of the ROI.

Fig. 4.
Fig. 4.

Fitting results from the pink and red pixels based on three curve-fitting algorithms.

Fig. 5.
Fig. 5.

Validation of an arc by splitting the arc into two subarcs across the straight line passing through both arcs’ gravity center (xm,ym) and circular center (xc,yc).

Fig. 6.
Fig. 6.

Gradient-based arc merging and duplicate elimination.

Fig. 7.
Fig. 7.

Simulated dataset used to compare the performance of FACILE with other circle-detection algorithms.

Fig. 8.
Fig. 8.

Processing time on simulated data for the four circle-detection algorithms. Here the radius lower bound is fixed at 10 pixels.

Fig. 9.
Fig. 9.

Comparison of false-positive error and false-negative error counts on simulated data for four algorithms.

Tables (2)

Tables Icon

Table 1. Radius and Center-Position Accuracy Comparison for Different Circle-Detection Algorithms on the Simulated Dataset Shown in Fig. 7

Tables Icon

Table 2. Performance Score [Dv,Fv, VRI] Comparison between Qgar–Lamiroy and FACILE

Equations (11)

Equations on this page are rendered with MathJax. Learn more.

ACB=arccos(xAxC)(xBxC)+(yAyC)(yByC)((xAxC)2+(yAyC)2)((xBxC)2+(yByC)2).
((xAxC)(xBxC)+(yAyC)(yByC))2((xAxC)2+(yAyC)2)((xBxC)2+(yByC)2)<cos2T.
(xxc)2+(yyc)2=R2,
(xxc)2+(yyc)2=R2
(x2+y2)+ax+by+c=0,
f(a,b,c)=i=1n(xi2+yi2+axi+byi+c)2,
{fa=2(axi2+bxiyi+cxi+(xi3+xiyi2))=0fb=2(axiyi+byi2+cyi+(xi2yi+yi3))=0fc=2(axi+byi+c+(xi2+yi2))=0.
{xc=det(xi3+xiyi2xiyixixi2yi+yi3yi2yixi2+yi2yin)/det(2xi22xiyi2xixiyiyi2yixiyin)yc=det(xi2(xi3+xiyi2)xixiyi(xi2yi+yi3)yixi(xi2+yi2)n)/det(2xi22xiyi2xixiyiyi2yixiyin)R=((xixc)2+(yiyc)2)/n,
std=|(xixc)2+(yiyc)2R2|2/n2R.
Conf=(12|R1R2|R1+R2)(12|C⃗1C⃗2|R1+R2)Tconfidence,
VRI=Dv*(1Fv),

Metrics