在數位影像中偵測直線、圓、橢圓長久以來在圖形辨識與影像處理領域都是相當重要的研究議題。本論文提出一個新的快速整合偵測方法，可以同時偵測直線、圓、橢圓。在整合的方法上，我們提出有效的連結機制得到線段，再透過分類將線段分成線(Line Bucket)以及曲線(Arc Bucket)，並且根據線段長度做排序以利於偵測與降低計算時間。最後再根據不同的Bucket種類去做偵測，Line Bucket內的線偵測直線，Arc Bucket內的曲線偵測圓、橢圓。在偵測圓、橢圓我們提出基於隨機式測橢圓改良版，可以快速辨識曲線為圓或者橢圓。此外在形狀偵測中，陣列用來表示投票的資料結構。實驗結果顯示，在合成影像與真實影像在相同的偵測結果下，平均可以省22%的偵測時間。

Detecting straight lines, circles, and ellipses from digital images is important and has a long history in pattern recognition and image processing community. In this paper, a novel fast unified method is proposed to efficiently detect the three shapes simultaneously from the images. In the proposed unified method, we first propose the arc segment-lookahead approach to filter the useful segments from the input image, then these filtered arc segments are allocated into the line bucket or curve bucket. The arc segments of each bucket are sorted based on their lengths. The proposed method selects the arc segment with the longest length as the seed to determine the resultant shape, leading to clear computation-saving and robustness merits. In order to speed up the circle/ellipse detection time, an efficient discrimination strategy is proposed to decide the detection order: detecting circle first or ellipse first. In addition, an array data structure is presented to be as the voting platform in the shape detection. Based on some synthesized and real images, experimental results demonstrated the computation-saving merit of the proposed method for detecting the above three shapes, while preserving the similar detection accuracy when compared with some related state-of-the-art methods.

[1] D. Ben-Tzvi, and M. B. Sandler, “A combinatorial Hough transform,” Pattern Recognition Letters, Vol. 11, No. 3, pp. 167-174, 1990.
[2] 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.
[3] J. E. Bresenham, "An algorithm for computer control of a digital plotter," IBM Syst. J., vol. 4, no. 1, pp.25 -30, 1965
[4] K. L. Chung, Z. W. Lin, S. T. Huang, Y. H. Huang, and H.Y. M. Liao, “New orientation-based elimination approach for accurate line-detection,” Pattern Recognition Letters, Vol. 31, No. 1, pp. 11-19, 2010.
[5] K. L. Chung and Y. H. Huang, “Speed up the computation of randomized algorithms for detecting lines, circles, and ellipses using novel tuningand LUT-based voting platform,” Applied Mathematics and Computation 190(1), pp. 132-149, 2007
[6] T. C. Chen and K. L. Chung, “An efficient randomized algorithm for detecting circles,” Computer Vision and Image Understanding, 83, pp.172-191, 2001.
[7] H. D. Cheng, Y. Guo, and Y. Zhang, “A novel Hough transform based on eliminating particle swarm optimization and its applications,” Pattern Recognition, 42(9), pp.1956-1969, 2009
[8] E. R. Davies, “Finding ellipses using the generalized Hough transform,” Pattern Recognition Letters, 9(2), pp. 87–96, 1989.
[9] M. Fornaciari, A.Prati, R.Cucchiara, “A fast and effective ellipse detector for embedded vision applications,” Pattern Recognition , Vol. 47, No .11, pp. 3693-3708, 2014.
[10] 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.
[11] S. Guoa, T. Pridmoreb, Y. Kongc, and X. Zhangd, “An improved Hough transform voting scheme utilizing surround suppression,” Pattern Recognition Letters, Vol. 30, No. 13, pp. 1241-1252, 2009.
[12] C. T. Ho and L. H. Chen, “A fast ellipse/circle detector using geometric symmetry, ” Pattern Recognition, 28, pp. 117-124, 1995.
[13] 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.
[14] D. Ioannou, W. Huda, and A. F. Laine, “Circle recognition through a 2D Hough transform and radius histogramming,” Image and Vision Computing, 17(1), pp.15-26, 1999.
[15] J. Illingworth, and J. Kittler, “Survey: A Survey of the Hough Transform,” Computer Vision, Graphics, and Image Processing, 44(1), pp. 87–116, 1988.
[16] J. Illingworth, and J. Kittler, “The adaptive Hough transform”, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 9, No.5, pp. 690-698, 1987.
[17] H. S. Kim and J. H. Kim, “A two-step circle detection from the intersecting chords, ” Pattern Recognition Letters, 22(6-7), pp.787- 798 , 2001.
[18] M. R. Kappel, “An ellipse-drawing algorithms for faster displays,” Fundamental Algorithms for Computer Graphics, pp. 257–280, 1985.
[19] J. Kennedy, “A fast Bresenham type algorithm for drawing circles, ” Internal Report, Santa Monic College, CA.
[20] R. A. McLaughlin, “Randomized Hough Transform: Improved ellipse detection with comparison,” Pattern Recognition Letters, 19, pp. 299–305, 1998.
[21] P. Mukhopadhyay and B. B. Chaudhuri, “A survey of Hough transform,” Pattern Recognition, vol. 48, no. 3, pp. 993–1010, 2015.
[22] 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.
[23]T. S. Ren, “Efficient Line Detection for Images with Complex Background Using Line-Segment-Priority Approach, ” masters dissertation, 2013
[24] X. Shen, J. Zhang, S. Yu, L. Meng, and K. L. Du, “An improved sampling strategy for randomized Hough transform based line detection”, International Conference on Systems and Informatics (IC-SAI), pp. 1874-1877, 2012.
[25] S. Tsuji and F. Matsumoto, “Detection of ellipses by a modified Hough transformation,” IEEE Trans. Computers, 27(8), pp. 777–781, 1978.
[26] C. Topal, C. Akinlar, “Edge Drawing: A Combined Real-Time Edge and Segment Detector,” Journal of Visual Communication and Image Representation, 23(6), 862-872, 2012.
[27] 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.
[28] L. Xu and E. Oja, “Randomized Hough Transform (RHT): Basic mechanisms, algorithms, and computational complexities,” CVGIP: Image Understanding, 57(2), pp. 131–154, 1993.
[29] 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.
[30] 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.
[31] B. Yuan, M. Liu, “Power histogram for circle detection on images,” Pattern Recognition , acceptance for publication, 2015.