Robust Ellipse Detection by Fitting Randomly Selected Edge Patches

Authors: Watcharin Kaewapichai, Pakorn Kaewtrakulpong

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

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1082877

References:

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