Robust Ellipse Detection by Fitting Randomly Selected Edge Patches
In this paper, a method to detect multiple ellipses is presented. The technique is efficient and robust against incomplete ellipses due to partial occlusion, noise or missing edges and outliers. It is an iterative technique that finds and removes the best ellipse until no reasonable ellipse is found. At each run, the best ellipse is extracted from randomly selected edge patches, its fitness calculated and compared to a fitness threshold. RANSAC algorithm is applied as a sampling process together with the Direct Least Square fitting of ellipses (DLS) as the fitting algorithm. In our experiment, the method performs very well and is robust against noise and spurious edges on both synthetic and real-world image data.
[1] L. Xu and E. Oja, "Randomized Hough Transform (RHT): Basic
Mechanisms, Algorithms, and Computational Complexities," Graphical
Models and mage rocessing mage Understanding, vol. 57, pp
111-122, 1993.
[2] R.A. McLaughlin, "Randomized Hough Transform: Better Ellipse
Detection," EEE TENC N igital ignal rocessing Applications
1996, pp. 409-414.
[3] D. Ben-Tzvi and M.B. Sandler, "A Combinatorial Hough Transform,"
attern Recognition Letter, vol. 11, pp 167-174, 1990.
[4] N. Kiryati, Y. Eldar, and A.M. Bruckstein, "Probabilistic Hough
transform," attern Recognition Letter, vol. 24, pp 303-316, 1991.
[5] V.F. Leavers, "The Dynamic Generalized Hough Transform: Its
Relationship to The Probabilistic Hough Transforms and An Application
to The Concurrent Detection of Circles and Ellipse," Graphical Models
and mage rocessing mage Understanding, vol. 56, pp. 381-398,
1992.
[6] E. Lutton and P. Martinez, "A Genetic Algorithm for the Detection of 2D
Geometric Primitives in Images," roceedings of the 12th A R
nternational Conference on attern Recognition, vol. 1, pp. 526-528,
1994.
[7] . Yao, N. Kharma, and P. Grogono, "A Multi-Population Genetic
Algorithm for Robust and Fast Ellipse Detection," attern Analysis and
Application, vol. 8, pp.169-162, 2005.
[8] A. Soetedjo and K. Yamada, "Fast and Robust Traffic Sign Detection,"
EEE nternal Conference on ystems Man and Cybernetics vol. 2, pp.
1341-1346, 2005.
[9] T. Kawaquchi and R.-I. Nagata, "Ellipse Detection Using a Genetic
Algorithm," roceedings ourteenth nternational Conference on
attern Recognition, vol. 1, pp. 141-145, 1998.
[10] G. Song and H. Wang, "A Fast and Robust Ellipse Detection Algorithm
Based on Pseudo-random Sample Consensus," Center for Advanced
nformation rocessing, pp. 669-676, 2007.
[11] M.A. Fischler, and R.C. Bolles, "Random Sample Consensus: A
Paradigm for Modle Fitting with Applications to Image Analysis and
Automated Cartography," Communication of the Association for
Computing Machinery, vol. 24, pp. 381-395, 1981.
[12] A. Fitzgibbon, M. Pilu, and R.B. Fisher, "Direct Least Square Fitting of
Ellipse," EEE Transactions on attern Analysis and Machine
ntelligence, vol. 21, pp. 446-480, 1999.
[13] Halif and . Flusser, "Numerically Stable Direct Least Squares Fitting
of Ellipses," nternational Conference in Central Europe on Computer
Graphics isualization and nteractive igital Media, pp.125-132,
1998.
[14] Nicholas Higham, "Handbook of writing for the mathematical
sciences," SIAM. ISBN 0898714206, pp. 25.
[1] L. Xu and E. Oja, "Randomized Hough Transform (RHT): Basic
Mechanisms, Algorithms, and Computational Complexities," Graphical
Models and mage rocessing mage Understanding, vol. 57, pp
111-122, 1993.
[2] R.A. McLaughlin, "Randomized Hough Transform: Better Ellipse
Detection," EEE TENC N igital ignal rocessing Applications
1996, pp. 409-414.
[3] D. Ben-Tzvi and M.B. Sandler, "A Combinatorial Hough Transform,"
attern Recognition Letter, vol. 11, pp 167-174, 1990.
[4] N. Kiryati, Y. Eldar, and A.M. Bruckstein, "Probabilistic Hough
transform," attern Recognition Letter, vol. 24, pp 303-316, 1991.
[5] V.F. Leavers, "The Dynamic Generalized Hough Transform: Its
Relationship to The Probabilistic Hough Transforms and An Application
to The Concurrent Detection of Circles and Ellipse," Graphical Models
and mage rocessing mage Understanding, vol. 56, pp. 381-398,
1992.
[6] E. Lutton and P. Martinez, "A Genetic Algorithm for the Detection of 2D
Geometric Primitives in Images," roceedings of the 12th A R
nternational Conference on attern Recognition, vol. 1, pp. 526-528,
1994.
[7] . Yao, N. Kharma, and P. Grogono, "A Multi-Population Genetic
Algorithm for Robust and Fast Ellipse Detection," attern Analysis and
Application, vol. 8, pp.169-162, 2005.
[8] A. Soetedjo and K. Yamada, "Fast and Robust Traffic Sign Detection,"
EEE nternal Conference on ystems Man and Cybernetics vol. 2, pp.
1341-1346, 2005.
[9] T. Kawaquchi and R.-I. Nagata, "Ellipse Detection Using a Genetic
Algorithm," roceedings ourteenth nternational Conference on
attern Recognition, vol. 1, pp. 141-145, 1998.
[10] G. Song and H. Wang, "A Fast and Robust Ellipse Detection Algorithm
Based on Pseudo-random Sample Consensus," Center for Advanced
nformation rocessing, pp. 669-676, 2007.
[11] M.A. Fischler, and R.C. Bolles, "Random Sample Consensus: A
Paradigm for Modle Fitting with Applications to Image Analysis and
Automated Cartography," Communication of the Association for
Computing Machinery, vol. 24, pp. 381-395, 1981.
[12] A. Fitzgibbon, M. Pilu, and R.B. Fisher, "Direct Least Square Fitting of
Ellipse," EEE Transactions on attern Analysis and Machine
ntelligence, vol. 21, pp. 446-480, 1999.
[13] Halif and . Flusser, "Numerically Stable Direct Least Squares Fitting
of Ellipses," nternational Conference in Central Europe on Computer
Graphics isualization and nteractive igital Media, pp.125-132,
1998.
[14] Nicholas Higham, "Handbook of writing for the mathematical
sciences," SIAM. ISBN 0898714206, pp. 25.
@article{"International Journal of Information, Control and Computer Sciences:63384", author = "Watcharin Kaewapichai and Pakorn Kaewtrakulpong", title = "Robust Ellipse Detection by Fitting Randomly Selected Edge Patches", abstract = "In this paper, a method to detect multiple ellipses is presented. The technique is efficient and robust against incomplete ellipses due to partial occlusion, noise or missing edges and outliers. It is an iterative technique that finds and removes the best ellipse until no reasonable ellipse is found. At each run, the best ellipse is extracted from randomly selected edge patches, its fitness calculated and compared to a fitness threshold. RANSAC algorithm is applied as a sampling process together with the Direct Least Square fitting of ellipses (DLS) as the fitting algorithm. In our experiment, the method performs very well and is robust against noise and spurious edges on both synthetic and real-world image data.
", keywords = "Direct Least Square Fitting, Ellipse Detection,RANSAC", volume = "2", number = "12", pages = "4248-4", }
