在複雜背景影像中偵測橢圓是圖形辨識與機器視覺領域中相當具有挑戰性的研究議題。本論文提出一個有效且強健的橢圓偵測法來快速的偵測複雜背景影像中的橢圓物件。我們的演算法主要由以下四個階段構成：(1) 利用基於優先權的橢圓弧選取策略來決定可能的橢圓，(2) 利用橢圓對稱性質從可能的橢圓中篩選出候選橢圓，(3) 以繪圖式投票機制決定候選橢圓是否為真正的橢圓，(4) 以最小平方法修正橢圓參數。根據一些真實的測試影像，實驗結果顯示我們提出的方法與Prasad等人的方法相比，能夠準確且更快速的偵測出複雜背景影像中的橢圓物件。

Detecting ellipses from complex background is a challenging problem in pattern recognition and machine vision community. In this paper, a novel efficient and robust elliptical-arc-priority based algorithm is presented for detecting ellipses from the input image with complex background. In the proposed algorithm, we first sort all elliptical arcs according to their importance levels in ellipse detection and then assign a proper priority to each elliptical arc. After selecting the elliptical arc with the highest priority in the current elliptical arc pool as a seed of the possible ellipse, a symmetry-based screening strategy is proposed to confirm whether the possible ellipse can be promoted to the candidate ellipse or not. Further, a drawing-based voting process is presented for determining the true ellipse. Finally, a refinement method is presented to improve the accuracy of detected ellipses. Based on some real test images, experimental results demonstrated the computation-saving and robust advantages of our proposed ellipse detection algorithm when compared to the current algorithm by Prasad et al.

[1] D. H. Ballard and C. M. Brown, Computer Vision, Prentice–Hall, Englewood Cliffs, New Jersey, 1982.
[2] E. R. Davies, Machine Vision: Theory, Algorithms, Practicalities, Academic Press, London, 1990.
[3] J. Illingworth and J. Kittler, “Survey: A Survey of the Hough Transform,” Computer Vision, Graphics, and Image Processing, 44(1), pp. 87–116, 1988.
[4] V. F. Leavers, “Survey: Which Hough Transform,” CVGIP: Image Understanding, 58(2), pp. 250–264, 1993.
[5] I. Pitas, Digital Image Processing Algorithms, Prentice-Hall, Englewood Cliffs, New York, 1993.
[6] N. Bennett, R. Burridge, and N. Saito, “A method to detect and characterize ellipses using the Hough Transform,” IEEE Trans. Pattern Analysis and Machine Intelligence, 21(7), pp. 652–657, 1999.
[7] E. R. Davies, “Finding ellipses using the generalized Hough transform,” Pattern Recognition Letters, 9(2), pp. 87–96, 1989.
[8] C. T. Ho and L. H. Chen, “A fast ellipse/circle detector using geometric symmetry,” Pattern Recognition, 28(1), pp. 117–124, 1995.
[9] C. T. Ho and L. H. Chen, “A high–speed algorithm for elliptical object detection,” IEEE Trans. Image Processing, 5(3), pp. 547–550, 1996.
[10] S. Tsuji and F. Matsumoto, “Detection of ellipses by a modified Hough transformation,” IEEE Trans. Computers, 27(8), pp. 777–781, 1978.
[11] R. K. K. Yip, P. K. S. Tam, and D. N. K. Leung, “Modification of Hough transform for circles and ellipses detection using a 2-dimensional array,” Pattern Recognition, 25(9), pp. 1007–1022, 1992.
[12] H. K. Yuen, J. Illingworth, and J. Kittler, “Detection partially occluded ellipses using the Hough transform,” Image and Vision Computing, 7(1), pp. 31–37, 1989.
[13] L. Xu, E. Oja, and P. Kultanan, “A new curve detection method: randomized Hough transform (RHT),” Pattern Recognition Letters, 11(5), pp.331–338, 1990.
[14] L. Xu and E. Oja, “Randomized Hough Transform (RHT): Basic mechanisms, algorithms, and computational complexities,” CVGIP: Image Understanding, 57(2), pp. 131–154, 1993.
[15] R. A. McLaughlin, “Randomized Hough Transform: Improved ellipse detection with comparison,” Pattern Recognition Letters, 19, pp. 299–305, 1998.
[16] K. L. Chung and Y. H. Huang, “Speed up the computation of randomized algorithms for detecting lines, circles, and ellipses using novel tuning and LUT-based voting platform,” Applied Mathematics and Computation, 190(1), pp. 132-149, 2007.
[17] E. Kim, M. Haseyama, and H. Kitajima, “Fast and robust ellipse extraction from complicated images,” in Proc. Int. Conf. Information Technology and Applications, 2002, pp. 357-362.
[18] F. Mai, Y. S. Hung, H. Zhong, and W. F. Sze, “A hierarchical approach for fast and robust ellipse extraction,” Pattern Recognition, 41(8), pp. 2512-2524, 2008.
[19] Z. Y. Liu and H. Qiao, “Multiple ellipses detection in noisy environments: a hierarchical approach,” Pattern Recognition, 42(11), pp. 2421-2433, 2009.
[20] X. Bai, C. Sun, and F. Zhou, “Splitting touching cells based on concave points and ellipse fitting,” Pattern Recognition, 42(11), pp. 2434-2446, 2009.
[21] D. K. Prasad, M. K. H. Leung, and S. Y. Cho, “Edge curvature and convexity based ellipse detection method,” Pattern Recognition, 45(9) pp. 3204-3221, 2012.
[22] C. Akinlar and C. Topal, “EDCircles: Areal-time circle detector with a false detection control,” Pattern Recognition, 46(3), pp. 725-740, 2013.
[23] C. Akinlar and C. Topal, “EDPF: a parameter-free edge segment detector with a false detection control,” Int. J. Pattern Recognition and Articial Intelligence, 23(6), pp. 862-872, 2012.
[24] A.Y.-S. Chia, S. Rahardja, D. Rajan, and M.K. Leung, “A split and merge based ellipse detector with self-correcting capability,” IEEE Trans. Image Processing, 20(7), pp. 1991-2006, 2011.
[25] C. Grigorescu, N. Petkov, and M. A. Westenberg, “Contour and boundary detection improved by surround suppression of texture edges,” Image and Vision Computing, 22(8), pp. 609-622, 2004.
[26] C. Guo, T. Pridmore, Y. Kong, and X. Zhang, “An improved Hough transform voting scheme utilizing surround suppression,” Pattern Recognition Letters, 30(13), pp. 1241-1252, 2009.
[27] Y. H. Huang, K. L. Chung, W. N. Yang, and S. H. Chiu, “Efficient symmetry-based screening strategy to speed up randomized circle-detection,” Pattern Recognition Letters, 33(16), pp. 2071-2076, 2012.
[28] M. A. Fischler and R. C. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography,” Commun. ACM 24 (6), 381-395, 1981.
[29] A. W. Fitzgibbon, M. Pilu, and R. B. Fisher, “Direct least-squares fitting of ellipses,” IEEE Trans. Pattern Analysis and Machine Intelligence, 21 (5), pp. 476-480, 1994.
[30] K. L. Chung and Y. H. Huang, “A pruning-and-voting strategy to speed up the detection for lines, circles, and ellipses,” J. Information Science and Engineering, 24(2), pp. 503-520, 2008.
[31] M. R. Kappel, “An ellipse-drawing algorithms for faster displays,” Fundamental Algorithms for Computer Graphics, pp. 257–280, 1985.