Abstract

In this research we propose a fast and robust ellipse detection algorithm based on a multipass Hough transform and an image pyramid data structure. The algorithm starts with an exhaustive search on a low-resolution image in the image pyramid using elliptical Hough transform. Then the image resolution is iteratively increased while the candidate ellipses with higher resolution are updated at each step until the original image resolution is reached. After removing the detected ellipses, the Hough transform is repeatedly applied in multiple passes to search for remaining ellipses, and terminates when no more ellipses are found. This approach significantly reduces the false positive error of ellipse detection as compared with the conventional randomized Hough transform method. The analysis shows that the computing complexity of this algorithm is Θ(n5/2), and thus the computation time and memory requirement are significantly reduced. The developed algorithm was tested with images containing various numbers of ellipses. The effects of noise-to-signal ratio combined with various ellipse sizes on the detection accuracy were analyzed and discussed. Experimental results revealed that the algorithm is robust to noise. The average detection accuracies were all above 90% for images with less than seven ellipses, and slightly decreased to about 80% for images with more ellipses. The average false positive error was less than 2%.

© 2011 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 (18 December 1962).
  2. R. O. Duda and P. E. Hart, “Use of the Hough transformation to detect lines and curves in pictures,” Commun. ACM 15, 11–15 (1972).
    [CrossRef]
  3. D. H. Ballard, “Generalizing the Hough transform to detect arbitrary shapes,” Pattern Recogn. 13, 111–122 (1981).
    [CrossRef]
  4. S. Tsuji and F. Matsumoto, “Detection of ellipses by a modified Hough transformation,” IEEE Trans. Comput. C-27, 777–781(1978).
    [CrossRef]
  5. C. Kimme, D. Ballard, and J. Sklansky, “Finding circles by an array of accumulators,” Commun. ACM 18, 120–122 (1975).
    [CrossRef]
  6. H. Li, M. A. Lavin, and R. J. Le Master, “Fast Hough transform: a hierarchical approach,” Comput. Vision Graphics Image Process. 36, 139–161 (1986).
    [CrossRef]
  7. H. K. Muammar and M. Nixon, “Tristage Hough transform for multiple ellipse extraction,” IEE Proc. E 138, 27–35 (1991).
    [CrossRef]
  8. N. Guil and L. Zapata, “Lower order circle and ellipse Hough transform,” Pattern Recogn. 30, 1729–1744 (1997).
    [CrossRef]
  9. J. Illingworth and J. Kittler, “A survey of the Hough transform,” Comput. Vision Graphics Image Process. 44, 87–116 (1988).
    [CrossRef]
  10. R. A. McLaughlin, “Randomized Hough transform: improved ellipse detection with comparison,” Pattern Recogn. Lett. 19, 299–305 (1998).
    [CrossRef]
  11. Y. Lei and K. C. Wong, “Ellipse detection based on symmetry,” Pattern Recogn. Lett. 20, 41–47 (1999).
    [CrossRef]
  12. A. A. Sewisy and F. Leberl, “Detection ellipses by finding lines of symmetry in the images via a Hough transform applied to straight lines,” Image Vision Comput. 19, 857–866 (2001).
    [CrossRef]
  13. S. C. Zhang and Z. Q. Liu, “A robust, real-time ellipse detector,” Pattern Recogn. 38, 273–287 (2005).
    [CrossRef]
  14. J. Yao, N. Kharma, and P. Grogono, “A multi-population genetic algorithm for robust and fast ellipse detection,” Pattern Anal. Appl. 8, 149–162 (2005).
    [CrossRef]
  15. G. Song and H. Wang, “A fast and robust ellipse detection algorithm based on pseudo-random sample consensus,” in Computer Analysis of Images and Patterns, Vol.  4673 of Lecture Notes in Computer Science (Springer, 2007), pp. 669–676.
  16. W. Kaewapichai and P. Kaewtrakulpong, “Robust ellipse detection by fitting randomly selected edge patches,” World Acad. Sci. Eng. Technol. 48, 30–33 (2008).
  17. F. Mai, Y. S. Hung, H. Zhong, and W. F. Sze, “A hierarchical approach for fast and robust ellipse extraction,” Pattern Recogn. 41, 2512–2524 (2008).
    [CrossRef]
  18. M. A. Rashwan, M. S. Elsherif, and A. M. Elsayad, “Pyramid data structures for on-line image progressive transmission,” in 36th Mid-West Symposium on Circuits and Systems (IEEE, 1993), pp. 103–106.
  19. L.Uhr, ed., Parallel Computer Vision, (Academic, 1987).
  20. M. Wu, J. Sun, J. Zhou, and G. Xue, “Color constancy based on texture pyramid matching and regularized local regression,” J. Opt. Soc. Am. A 27, 2097–2015 (2010).
    [CrossRef]
  21. M. Goldberg and L. Wang, “Comparative performance of pyramid data structures for progressive image transmission,” IEEE Trans. Commun. 39, 540–548 (1991).
    [CrossRef]
  22. W. D. Hofmann and D. E. Troxel, “Making progressive transmission adaptive,” IEEE Trans. Commun. 34, 806–813 (1986).
    [CrossRef]
  23. P. Meer, “Stochastic image pyramids,” Comput. Vision Graphics Image Process. 45, 269–294 (1989).
    [CrossRef]
  24. K. R. Sloan and S. L. Tanimoto, “Progressive refinement of raster images,” IEEE Trans. Comput. C-28, 871–875 (1979).
    [CrossRef]
  25. L. Wang and M. Goldberg, “Progressive image transmission using vector quantization on images in pyramid form,” IEEE Trans. Commun. 37, 1339–1349 (1989).
    [CrossRef]
  26. G. Bongiovanni, C. Guerra, and S. Levialdi, “Computing the Hough transform on a pyramid architecture,” Machine Vision Appl. 3, 117–123 (1990).
    [CrossRef]
  27. C. Espinosa and M. A. Perkowski, “Hierarchical Hough transform based on pyramidal architecture,” in Eleventh Annual International Phoenix Conference on Computer and Communications 1992 (IEEE, 1992), pp. 0743–0750.
  28. J. M. Jolion and A. Rosenfeld, “An O(log⁡n) pyramid Hough transform,” Pattern Recogn. Lett. 9, 343–349 (1989).
    [CrossRef]
  29. D. Schreiber and Y. Luo, “Seat detection in a car for a smart airbag application,” Pattern Recogn. Lett. 28, 534–544(2007).
    [CrossRef]
  30. S. R. Deans, “Hough transform from the Radon transform,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-3, 185–188 (1981).
    [CrossRef]
  31. V. F. Leavers, “Which Hough transform?” Comput. Vision Graphics Image Process. Image Underst. 58, 250–264 (1993).
    [CrossRef]
  32. G. B. Thomas and R. L. Finney, Calculus and Analytic Geometry (Addison-Wesley, 1996).
  33. C. F. Chien and T. T. Lin, “Leaf area measurement of selected vegetable seedlings using elliptical Hough transform,” Trans. Am. Soc. Agric. Eng. 45, 1669–1677 (2002).
  34. C. F. Chien, “Non-destructive measurement of selected vegetable seedlings using 3D machine vision,” Ph.D. dissertation (Bio-Industrial Mechatronics Engineering Department, National Taiwan University, 2003).
  35. R. M. Haralick and L. G. Shapiro, Computer and Robot Vision (Addison-Wesley, 1992), Vol.  I.
  36. C. T. Ho and L. H. Chen, “A fast ellipse/circle detector using geometric symmetry,” Pattern Recogn. 28, 117–124 (1995).
    [CrossRef]

2010 (1)

2008 (2)

W. Kaewapichai and P. Kaewtrakulpong, “Robust ellipse detection by fitting randomly selected edge patches,” World Acad. Sci. Eng. Technol. 48, 30–33 (2008).

F. Mai, Y. S. Hung, H. Zhong, and W. F. Sze, “A hierarchical approach for fast and robust ellipse extraction,” Pattern Recogn. 41, 2512–2524 (2008).
[CrossRef]

2007 (1)

D. Schreiber and Y. Luo, “Seat detection in a car for a smart airbag application,” Pattern Recogn. Lett. 28, 534–544(2007).
[CrossRef]

2005 (2)

S. C. Zhang and Z. Q. Liu, “A robust, real-time ellipse detector,” Pattern Recogn. 38, 273–287 (2005).
[CrossRef]

J. Yao, N. Kharma, and P. Grogono, “A multi-population genetic algorithm for robust and fast ellipse detection,” Pattern Anal. Appl. 8, 149–162 (2005).
[CrossRef]

2002 (1)

C. F. Chien and T. T. Lin, “Leaf area measurement of selected vegetable seedlings using elliptical Hough transform,” Trans. Am. Soc. Agric. Eng. 45, 1669–1677 (2002).

2001 (1)

A. A. Sewisy and F. Leberl, “Detection ellipses by finding lines of symmetry in the images via a Hough transform applied to straight lines,” Image Vision Comput. 19, 857–866 (2001).
[CrossRef]

1999 (1)

Y. Lei and K. C. Wong, “Ellipse detection based on symmetry,” Pattern Recogn. Lett. 20, 41–47 (1999).
[CrossRef]

1998 (1)

R. A. McLaughlin, “Randomized Hough transform: improved ellipse detection with comparison,” Pattern Recogn. Lett. 19, 299–305 (1998).
[CrossRef]

1997 (1)

N. Guil and L. Zapata, “Lower order circle and ellipse Hough transform,” Pattern Recogn. 30, 1729–1744 (1997).
[CrossRef]

1995 (1)

C. T. Ho and L. H. Chen, “A fast ellipse/circle detector using geometric symmetry,” Pattern Recogn. 28, 117–124 (1995).
[CrossRef]

1993 (1)

V. F. Leavers, “Which Hough transform?” Comput. Vision Graphics Image Process. Image Underst. 58, 250–264 (1993).
[CrossRef]

1991 (2)

H. K. Muammar and M. Nixon, “Tristage Hough transform for multiple ellipse extraction,” IEE Proc. E 138, 27–35 (1991).
[CrossRef]

M. Goldberg and L. Wang, “Comparative performance of pyramid data structures for progressive image transmission,” IEEE Trans. Commun. 39, 540–548 (1991).
[CrossRef]

1990 (1)

G. Bongiovanni, C. Guerra, and S. Levialdi, “Computing the Hough transform on a pyramid architecture,” Machine Vision Appl. 3, 117–123 (1990).
[CrossRef]

1989 (3)

J. M. Jolion and A. Rosenfeld, “An O(log⁡n) pyramid Hough transform,” Pattern Recogn. Lett. 9, 343–349 (1989).
[CrossRef]

P. Meer, “Stochastic image pyramids,” Comput. Vision Graphics Image Process. 45, 269–294 (1989).
[CrossRef]

L. Wang and M. Goldberg, “Progressive image transmission using vector quantization on images in pyramid form,” IEEE Trans. Commun. 37, 1339–1349 (1989).
[CrossRef]

1988 (1)

J. Illingworth and J. Kittler, “A survey of the Hough transform,” Comput. Vision Graphics Image Process. 44, 87–116 (1988).
[CrossRef]

1986 (2)

H. Li, M. A. Lavin, and R. J. Le Master, “Fast Hough transform: a hierarchical approach,” Comput. Vision Graphics Image Process. 36, 139–161 (1986).
[CrossRef]

W. D. Hofmann and D. E. Troxel, “Making progressive transmission adaptive,” IEEE Trans. Commun. 34, 806–813 (1986).
[CrossRef]

1981 (2)

D. H. Ballard, “Generalizing the Hough transform to detect arbitrary shapes,” Pattern Recogn. 13, 111–122 (1981).
[CrossRef]

S. R. Deans, “Hough transform from the Radon transform,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-3, 185–188 (1981).
[CrossRef]

1979 (1)

K. R. Sloan and S. L. Tanimoto, “Progressive refinement of raster images,” IEEE Trans. Comput. C-28, 871–875 (1979).
[CrossRef]

1978 (1)

S. Tsuji and F. Matsumoto, “Detection of ellipses by a modified Hough transformation,” IEEE Trans. Comput. C-27, 777–781(1978).
[CrossRef]

1975 (1)

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

1972 (1)

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

Ballard, D.

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

Ballard, D. H.

D. H. Ballard, “Generalizing the Hough transform to detect arbitrary shapes,” Pattern Recogn. 13, 111–122 (1981).
[CrossRef]

Bongiovanni, G.

G. Bongiovanni, C. Guerra, and S. Levialdi, “Computing the Hough transform on a pyramid architecture,” Machine Vision Appl. 3, 117–123 (1990).
[CrossRef]

Chen, L. H.

C. T. Ho and L. H. Chen, “A fast ellipse/circle detector using geometric symmetry,” Pattern Recogn. 28, 117–124 (1995).
[CrossRef]

Chien, C. F.

C. F. Chien and T. T. Lin, “Leaf area measurement of selected vegetable seedlings using elliptical Hough transform,” Trans. Am. Soc. Agric. Eng. 45, 1669–1677 (2002).

C. F. Chien, “Non-destructive measurement of selected vegetable seedlings using 3D machine vision,” Ph.D. dissertation (Bio-Industrial Mechatronics Engineering Department, National Taiwan University, 2003).

Deans, S. R.

S. R. Deans, “Hough transform from the Radon transform,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-3, 185–188 (1981).
[CrossRef]

Duda, R. O.

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

Elsayad, A. M.

M. A. Rashwan, M. S. Elsherif, and A. M. Elsayad, “Pyramid data structures for on-line image progressive transmission,” in 36th Mid-West Symposium on Circuits and Systems (IEEE, 1993), pp. 103–106.

Elsherif, M. S.

M. A. Rashwan, M. S. Elsherif, and A. M. Elsayad, “Pyramid data structures for on-line image progressive transmission,” in 36th Mid-West Symposium on Circuits and Systems (IEEE, 1993), pp. 103–106.

Espinosa, C.

C. Espinosa and M. A. Perkowski, “Hierarchical Hough transform based on pyramidal architecture,” in Eleventh Annual International Phoenix Conference on Computer and Communications 1992 (IEEE, 1992), pp. 0743–0750.

Finney, R. L.

G. B. Thomas and R. L. Finney, Calculus and Analytic Geometry (Addison-Wesley, 1996).

Goldberg, M.

M. Goldberg and L. Wang, “Comparative performance of pyramid data structures for progressive image transmission,” IEEE Trans. Commun. 39, 540–548 (1991).
[CrossRef]

L. Wang and M. Goldberg, “Progressive image transmission using vector quantization on images in pyramid form,” IEEE Trans. Commun. 37, 1339–1349 (1989).
[CrossRef]

Grogono, P.

J. Yao, N. Kharma, and P. Grogono, “A multi-population genetic algorithm for robust and fast ellipse detection,” Pattern Anal. Appl. 8, 149–162 (2005).
[CrossRef]

Guerra, C.

G. Bongiovanni, C. Guerra, and S. Levialdi, “Computing the Hough transform on a pyramid architecture,” Machine Vision Appl. 3, 117–123 (1990).
[CrossRef]

Guil, N.

N. Guil and L. Zapata, “Lower order circle and ellipse Hough transform,” Pattern Recogn. 30, 1729–1744 (1997).
[CrossRef]

Haralick, R. M.

R. M. Haralick and L. G. Shapiro, Computer and Robot Vision (Addison-Wesley, 1992), Vol.  I.

Hart, P. E.

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

Ho, C. T.

C. T. Ho and L. H. Chen, “A fast ellipse/circle detector using geometric symmetry,” Pattern Recogn. 28, 117–124 (1995).
[CrossRef]

Hofmann, W. D.

W. D. Hofmann and D. E. Troxel, “Making progressive transmission adaptive,” IEEE Trans. Commun. 34, 806–813 (1986).
[CrossRef]

Hough, P. V. C.

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

Hung, Y. S.

F. Mai, Y. S. Hung, H. Zhong, and W. F. Sze, “A hierarchical approach for fast and robust ellipse extraction,” Pattern Recogn. 41, 2512–2524 (2008).
[CrossRef]

Illingworth, J.

J. Illingworth and J. Kittler, “A survey of the Hough transform,” Comput. Vision Graphics Image Process. 44, 87–116 (1988).
[CrossRef]

Jolion, J. M.

J. M. Jolion and A. Rosenfeld, “An O(log⁡n) pyramid Hough transform,” Pattern Recogn. Lett. 9, 343–349 (1989).
[CrossRef]

Kaewapichai, W.

W. Kaewapichai and P. Kaewtrakulpong, “Robust ellipse detection by fitting randomly selected edge patches,” World Acad. Sci. Eng. Technol. 48, 30–33 (2008).

Kaewtrakulpong, P.

W. Kaewapichai and P. Kaewtrakulpong, “Robust ellipse detection by fitting randomly selected edge patches,” World Acad. Sci. Eng. Technol. 48, 30–33 (2008).

Kharma, N.

J. Yao, N. Kharma, and P. Grogono, “A multi-population genetic algorithm for robust and fast ellipse detection,” Pattern Anal. Appl. 8, 149–162 (2005).
[CrossRef]

Kimme, C.

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

Kittler, J.

J. Illingworth and J. Kittler, “A survey of the Hough transform,” Comput. Vision Graphics Image Process. 44, 87–116 (1988).
[CrossRef]

Lavin, M. A.

H. Li, M. A. Lavin, and R. J. Le Master, “Fast Hough transform: a hierarchical approach,” Comput. Vision Graphics Image Process. 36, 139–161 (1986).
[CrossRef]

Le Master, R. J.

H. Li, M. A. Lavin, and R. J. Le Master, “Fast Hough transform: a hierarchical approach,” Comput. Vision Graphics Image Process. 36, 139–161 (1986).
[CrossRef]

Leavers, V. F.

V. F. Leavers, “Which Hough transform?” Comput. Vision Graphics Image Process. Image Underst. 58, 250–264 (1993).
[CrossRef]

Leberl, F.

A. A. Sewisy and F. Leberl, “Detection ellipses by finding lines of symmetry in the images via a Hough transform applied to straight lines,” Image Vision Comput. 19, 857–866 (2001).
[CrossRef]

Lei, Y.

Y. Lei and K. C. Wong, “Ellipse detection based on symmetry,” Pattern Recogn. Lett. 20, 41–47 (1999).
[CrossRef]

Levialdi, S.

G. Bongiovanni, C. Guerra, and S. Levialdi, “Computing the Hough transform on a pyramid architecture,” Machine Vision Appl. 3, 117–123 (1990).
[CrossRef]

Li, H.

H. Li, M. A. Lavin, and R. J. Le Master, “Fast Hough transform: a hierarchical approach,” Comput. Vision Graphics Image Process. 36, 139–161 (1986).
[CrossRef]

Lin, T. T.

C. F. Chien and T. T. Lin, “Leaf area measurement of selected vegetable seedlings using elliptical Hough transform,” Trans. Am. Soc. Agric. Eng. 45, 1669–1677 (2002).

Liu, Z. Q.

S. C. Zhang and Z. Q. Liu, “A robust, real-time ellipse detector,” Pattern Recogn. 38, 273–287 (2005).
[CrossRef]

Luo, Y.

D. Schreiber and Y. Luo, “Seat detection in a car for a smart airbag application,” Pattern Recogn. Lett. 28, 534–544(2007).
[CrossRef]

Mai, F.

F. Mai, Y. S. Hung, H. Zhong, and W. F. Sze, “A hierarchical approach for fast and robust ellipse extraction,” Pattern Recogn. 41, 2512–2524 (2008).
[CrossRef]

Matsumoto, F.

S. Tsuji and F. Matsumoto, “Detection of ellipses by a modified Hough transformation,” IEEE Trans. Comput. C-27, 777–781(1978).
[CrossRef]

McLaughlin, R. A.

R. A. McLaughlin, “Randomized Hough transform: improved ellipse detection with comparison,” Pattern Recogn. Lett. 19, 299–305 (1998).
[CrossRef]

Meer, P.

P. Meer, “Stochastic image pyramids,” Comput. Vision Graphics Image Process. 45, 269–294 (1989).
[CrossRef]

Muammar, H. K.

H. K. Muammar and M. Nixon, “Tristage Hough transform for multiple ellipse extraction,” IEE Proc. E 138, 27–35 (1991).
[CrossRef]

Nixon, M.

H. K. Muammar and M. Nixon, “Tristage Hough transform for multiple ellipse extraction,” IEE Proc. E 138, 27–35 (1991).
[CrossRef]

Perkowski, M. A.

C. Espinosa and M. A. Perkowski, “Hierarchical Hough transform based on pyramidal architecture,” in Eleventh Annual International Phoenix Conference on Computer and Communications 1992 (IEEE, 1992), pp. 0743–0750.

Rashwan, M. A.

M. A. Rashwan, M. S. Elsherif, and A. M. Elsayad, “Pyramid data structures for on-line image progressive transmission,” in 36th Mid-West Symposium on Circuits and Systems (IEEE, 1993), pp. 103–106.

Rosenfeld, A.

J. M. Jolion and A. Rosenfeld, “An O(log⁡n) pyramid Hough transform,” Pattern Recogn. Lett. 9, 343–349 (1989).
[CrossRef]

Schreiber, D.

D. Schreiber and Y. Luo, “Seat detection in a car for a smart airbag application,” Pattern Recogn. Lett. 28, 534–544(2007).
[CrossRef]

Sewisy, A. A.

A. A. Sewisy and F. Leberl, “Detection ellipses by finding lines of symmetry in the images via a Hough transform applied to straight lines,” Image Vision Comput. 19, 857–866 (2001).
[CrossRef]

Shapiro, L. G.

R. M. Haralick and L. G. Shapiro, Computer and Robot Vision (Addison-Wesley, 1992), Vol.  I.

Sklansky, J.

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

Sloan, K. R.

K. R. Sloan and S. L. Tanimoto, “Progressive refinement of raster images,” IEEE Trans. Comput. C-28, 871–875 (1979).
[CrossRef]

Song, G.

G. Song and H. Wang, “A fast and robust ellipse detection algorithm based on pseudo-random sample consensus,” in Computer Analysis of Images and Patterns, Vol.  4673 of Lecture Notes in Computer Science (Springer, 2007), pp. 669–676.

Sun, J.

Sze, W. F.

F. Mai, Y. S. Hung, H. Zhong, and W. F. Sze, “A hierarchical approach for fast and robust ellipse extraction,” Pattern Recogn. 41, 2512–2524 (2008).
[CrossRef]

Tanimoto, S. L.

K. R. Sloan and S. L. Tanimoto, “Progressive refinement of raster images,” IEEE Trans. Comput. C-28, 871–875 (1979).
[CrossRef]

Thomas, G. B.

G. B. Thomas and R. L. Finney, Calculus and Analytic Geometry (Addison-Wesley, 1996).

Troxel, D. E.

W. D. Hofmann and D. E. Troxel, “Making progressive transmission adaptive,” IEEE Trans. Commun. 34, 806–813 (1986).
[CrossRef]

Tsuji, S.

S. Tsuji and F. Matsumoto, “Detection of ellipses by a modified Hough transformation,” IEEE Trans. Comput. C-27, 777–781(1978).
[CrossRef]

Wang, H.

G. Song and H. Wang, “A fast and robust ellipse detection algorithm based on pseudo-random sample consensus,” in Computer Analysis of Images and Patterns, Vol.  4673 of Lecture Notes in Computer Science (Springer, 2007), pp. 669–676.

Wang, L.

M. Goldberg and L. Wang, “Comparative performance of pyramid data structures for progressive image transmission,” IEEE Trans. Commun. 39, 540–548 (1991).
[CrossRef]

L. Wang and M. Goldberg, “Progressive image transmission using vector quantization on images in pyramid form,” IEEE Trans. Commun. 37, 1339–1349 (1989).
[CrossRef]

Wong, K. C.

Y. Lei and K. C. Wong, “Ellipse detection based on symmetry,” Pattern Recogn. Lett. 20, 41–47 (1999).
[CrossRef]

Wu, M.

Xue, G.

Yao, J.

J. Yao, N. Kharma, and P. Grogono, “A multi-population genetic algorithm for robust and fast ellipse detection,” Pattern Anal. Appl. 8, 149–162 (2005).
[CrossRef]

Zapata, L.

N. Guil and L. Zapata, “Lower order circle and ellipse Hough transform,” Pattern Recogn. 30, 1729–1744 (1997).
[CrossRef]

Zhang, S. C.

S. C. Zhang and Z. Q. Liu, “A robust, real-time ellipse detector,” Pattern Recogn. 38, 273–287 (2005).
[CrossRef]

Zhong, H.

F. Mai, Y. S. Hung, H. Zhong, and W. F. Sze, “A hierarchical approach for fast and robust ellipse extraction,” Pattern Recogn. 41, 2512–2524 (2008).
[CrossRef]

Zhou, J.

Commun. ACM (2)

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

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

Comput. Vision Graphics Image Process. (3)

H. Li, M. A. Lavin, and R. J. Le Master, “Fast Hough transform: a hierarchical approach,” Comput. Vision Graphics Image Process. 36, 139–161 (1986).
[CrossRef]

J. Illingworth and J. Kittler, “A survey of the Hough transform,” Comput. Vision Graphics Image Process. 44, 87–116 (1988).
[CrossRef]

P. Meer, “Stochastic image pyramids,” Comput. Vision Graphics Image Process. 45, 269–294 (1989).
[CrossRef]

Comput. Vision Graphics Image Process. Image Underst. (1)

V. F. Leavers, “Which Hough transform?” Comput. Vision Graphics Image Process. Image Underst. 58, 250–264 (1993).
[CrossRef]

IEE Proc. E (1)

H. K. Muammar and M. Nixon, “Tristage Hough transform for multiple ellipse extraction,” IEE Proc. E 138, 27–35 (1991).
[CrossRef]

IEEE Trans. Commun. (3)

M. Goldberg and L. Wang, “Comparative performance of pyramid data structures for progressive image transmission,” IEEE Trans. Commun. 39, 540–548 (1991).
[CrossRef]

W. D. Hofmann and D. E. Troxel, “Making progressive transmission adaptive,” IEEE Trans. Commun. 34, 806–813 (1986).
[CrossRef]

L. Wang and M. Goldberg, “Progressive image transmission using vector quantization on images in pyramid form,” IEEE Trans. Commun. 37, 1339–1349 (1989).
[CrossRef]

IEEE Trans. Comput. (2)

K. R. Sloan and S. L. Tanimoto, “Progressive refinement of raster images,” IEEE Trans. Comput. C-28, 871–875 (1979).
[CrossRef]

S. Tsuji and F. Matsumoto, “Detection of ellipses by a modified Hough transformation,” IEEE Trans. Comput. C-27, 777–781(1978).
[CrossRef]

IEEE Trans. Pattern Anal. Machine Intell. (1)

S. R. Deans, “Hough transform from the Radon transform,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-3, 185–188 (1981).
[CrossRef]

Image Vision Comput. (1)

A. A. Sewisy and F. Leberl, “Detection ellipses by finding lines of symmetry in the images via a Hough transform applied to straight lines,” Image Vision Comput. 19, 857–866 (2001).
[CrossRef]

J. Opt. Soc. Am. A (1)

Machine Vision Appl. (1)

G. Bongiovanni, C. Guerra, and S. Levialdi, “Computing the Hough transform on a pyramid architecture,” Machine Vision Appl. 3, 117–123 (1990).
[CrossRef]

Pattern Anal. Appl. (1)

J. Yao, N. Kharma, and P. Grogono, “A multi-population genetic algorithm for robust and fast ellipse detection,” Pattern Anal. Appl. 8, 149–162 (2005).
[CrossRef]

Pattern Recogn. (5)

F. Mai, Y. S. Hung, H. Zhong, and W. F. Sze, “A hierarchical approach for fast and robust ellipse extraction,” Pattern Recogn. 41, 2512–2524 (2008).
[CrossRef]

S. C. Zhang and Z. Q. Liu, “A robust, real-time ellipse detector,” Pattern Recogn. 38, 273–287 (2005).
[CrossRef]

D. H. Ballard, “Generalizing the Hough transform to detect arbitrary shapes,” Pattern Recogn. 13, 111–122 (1981).
[CrossRef]

N. Guil and L. Zapata, “Lower order circle and ellipse Hough transform,” Pattern Recogn. 30, 1729–1744 (1997).
[CrossRef]

C. T. Ho and L. H. Chen, “A fast ellipse/circle detector using geometric symmetry,” Pattern Recogn. 28, 117–124 (1995).
[CrossRef]

Pattern Recogn. Lett. (4)

J. M. Jolion and A. Rosenfeld, “An O(log⁡n) pyramid Hough transform,” Pattern Recogn. Lett. 9, 343–349 (1989).
[CrossRef]

D. Schreiber and Y. Luo, “Seat detection in a car for a smart airbag application,” Pattern Recogn. Lett. 28, 534–544(2007).
[CrossRef]

R. A. McLaughlin, “Randomized Hough transform: improved ellipse detection with comparison,” Pattern Recogn. Lett. 19, 299–305 (1998).
[CrossRef]

Y. Lei and K. C. Wong, “Ellipse detection based on symmetry,” Pattern Recogn. Lett. 20, 41–47 (1999).
[CrossRef]

Trans. Am. Soc. Agric. Eng. (1)

C. F. Chien and T. T. Lin, “Leaf area measurement of selected vegetable seedlings using elliptical Hough transform,” Trans. Am. Soc. Agric. Eng. 45, 1669–1677 (2002).

World Acad. Sci. Eng. Technol. (1)

W. Kaewapichai and P. Kaewtrakulpong, “Robust ellipse detection by fitting randomly selected edge patches,” World Acad. Sci. Eng. Technol. 48, 30–33 (2008).

Other (8)

G. B. Thomas and R. L. Finney, Calculus and Analytic Geometry (Addison-Wesley, 1996).

C. F. Chien, “Non-destructive measurement of selected vegetable seedlings using 3D machine vision,” Ph.D. dissertation (Bio-Industrial Mechatronics Engineering Department, National Taiwan University, 2003).

R. M. Haralick and L. G. Shapiro, Computer and Robot Vision (Addison-Wesley, 1992), Vol.  I.

C. Espinosa and M. A. Perkowski, “Hierarchical Hough transform based on pyramidal architecture,” in Eleventh Annual International Phoenix Conference on Computer and Communications 1992 (IEEE, 1992), pp. 0743–0750.

M. A. Rashwan, M. S. Elsherif, and A. M. Elsayad, “Pyramid data structures for on-line image progressive transmission,” in 36th Mid-West Symposium on Circuits and Systems (IEEE, 1993), pp. 103–106.

L.Uhr, ed., Parallel Computer Vision, (Academic, 1987).

G. Song and H. Wang, “A fast and robust ellipse detection algorithm based on pseudo-random sample consensus,” in Computer Analysis of Images and Patterns, Vol.  4673 of Lecture Notes in Computer Science (Springer, 2007), pp. 669–676.

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

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 (11)

Fig. 1
Fig. 1

Flowchart of the Hough transform algorithm for ellipse detection based on hierarchical image pyramid.

Fig. 2
Fig. 2

Image down-sampling from fine to coarse resolutions: (a) image layer i + 1 (original 8 × 8 image); (b) image layer i ( 4 × 4 image); (c) image pyramid data structure.

Fig. 3
Fig. 3

(a) Point P in a digitized image of 2 × 2 resolution; (b) point P’s possible position range in a continuous space; (c) point P’s possible positions in a digitized image of 4 × 4 resolution.

Fig. 4
Fig. 4

Flowchart of the multipass elliptical Hough transform algorithm for ellipse detection.

Fig. 5
Fig. 5

Typical synthetic images containing various numbers of ellipses: (a) image with five ellipses; (b) image with 10 ellipses.

Fig. 6
Fig. 6

Demonstration of ellipse detection in real images. The images in the left column are the original images. The binary images in the central column are images after segmentation, edge detection, and thinning. The images in the right column show the detected ellipses corresponding to the original images.

Fig. 7
Fig. 7

Comparison of computation time for ellipse detection using the single-pass and multipass approaches.

Fig. 8
Fig. 8

Comparison of average detection accuracies among the single-pass and multipass approaches of the proposed algorithm and other Hough transform methods, as affected by the number of ellipses in images.

Fig. 9
Fig. 9

Average false positive errors of ellipse detection as affected by the number of ellipses in an image.

Fig. 10
Fig. 10

Effect of NSR on average computation time per ellipse for images containing ellipses of different sizes.

Fig. 11
Fig. 11

Effect of NSR on average detection accuracy for images containing ellipses of different sizes.

Equations (18)

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

ρ = y sin θ + x cos θ ,
d r = ( x x 1 ) 2 + ( y y 1 ) 2 + ( x x 2 ) 2 + ( y y 2 ) 2 ,
f ( ( x 1 , y 1 , x 2 , y 2 , d r ) , ( x , y ) ) = ( x x 1 ) 2 + ( y y 1 ) 2 + ( x x 2 ) 2 + ( y y 2 ) 2 d r = 0.
x 2 a 2 + y 2 b 2 = 1 ,
r = ± a 2 b 2 b 2 cos 2 θ + a 2 sin 2 θ ,
c = ( x 1 x 2 ) 2 + ( y 1 y 2 ) 2 2 ,
a = d r 2 ,
b = a 2 c 2 = ( d r 2 ) 2 c 2 ,
x = r cos θ = d r 2 d r 2 4 c 2 d r 2 4 c 2 cos 2 θ ,
y = r sin θ = d r sin θ 2 d r 2 4 c 2 d r 2 4 c 2 cos 2 θ + d r 2 sin 2 θ .
α = tan 1 ( y 2 y 1 x 2 x 1 ) .
[ x y ] = [ cos α sin α sin α cos α ] [ r * cos θ r * sin θ ] + [ x 0 y 0 ] ,
{ X 1 0.5 x 1 < X 1 + 0.5 Y 1 0.5 y 1 < Y 1 + 0.5 X 2 0.5 x 2 < X 2 + 0.5 Y 2 0.5 y 2 < Y 2 + 0.5 D r 0.5 d r < D r + 0.5 ,
{ 2 X 1 1 x 1 < 2 X 1 + 1 2 Y 1 1 y 1 < 2 Y 1 + 1 2 X 2 1 x 2 < 2 X 2 + 1 2 Y 2 1 y 2 < 2 Y 2 + 1 2 D r 1 d r < 2 D r + 1 ,
{ X 1 { 2 X 1 , 2 X 1 ± 1 } Y 1 { 2 Y 1 , 2 Y 1 ± 1 } X 2 { 2 X 2 , 2 X 2 ± 1 } Y 2 { 2 Y 2 , 2 Y 2 ± 1 } D r { 2 D r , 2 D r ± 1 } .
C total = N × p e × C s + N × ( 2 p e ) × 3 5 × C s + N × ( 4 p e ) × 3 5 × C s + + N × ( 2 m p e ) × 3 5 × C s = N × p e × C s + N × p e × C s × 3 5 ( 2 1 + 2 2 + + 2 m ) = N × p e × C s + N × p e × C s × 3 5 × 2 × ( 2 m 1 ) = N × p e × C s ( 1 + 3 5 × 2 m + 1 2 × 3 5 ) = Θ ( n ) × Θ ( 2 m + 1 ) = Θ ( n ) × Θ ( 2 n ) = Θ ( n 2 ) .
T ( n ) = Θ ( n 2 ) + Θ ( n 5 / 2 ) + Θ ( n 2 ) = Θ ( n 5 / 2 ) .
NSR = ( Number of noise pixels ) / ( Number of boundary pixels of ellipses ) .

Metrics