圓的偵測是影像處理領域中的一個基礎問題。一般來說，哈克轉
換是一種最常見的圓偵測演算法。然而，針對輸入影像，哈克轉換需
花費許多的執行時間在三維的累積陣列上完成投票程的程序。為了提
高哈克轉換的時間效率，本篇論文首先提出一個植基於曲率的淘汰策
略來減少參與投票程序的邊點數量。根據每個邊點的曲率，我們將較
不可能位於圓周上的邊點濾除，只留下少量邊點參與投票程序。除此
之外，利用邊點的曲率，本篇論文也提出了一個半徑估計的機制。根
據估計的半徑及邊點的梯度方向，每個邊點只需要在一個變動的半徑
範圍內進行投票，因此可降低哈克轉換的執行時間。實驗結果顯示，
與其他四種已知的圓偵測演算法相比之下，本篇論文所提出的快速演
算法可達到較佳的時間效率，其執行時間的平均改善率能達到
87.67%。

Circle-detection is an important issue in the image processing. In
general, the Hough transform is most common method for detecting
circles from digital images. However, given an input image, the Hough
transform consumes a lot of time to perform the voting process on a 3-D
accumulator array. To improve the execution-time performance of the
Hough transform, we first present curvature-based elimination strategy to
reduce the number of edge pixels considered in the voting process. Based
on the curvatures of edge pixels, we discard those edge pixels which have
lower probability of lying on circles and only a small amount of edge
pixels will be considered in the voting process. Further, the curvature of
each edge pixel is also considered in our proposed radius estimation
scheme to estimate the radius of the circle. Based on the estimated radius
and the gradient direction, each edge pixel only considers a range of
radius rather than considers all possible centers and radiuses to perform
the voting process. Combining the proposed curvature-based
elimination strategy and radius estimation scheme, the proposed fast
circle detection algorithm is presented. Experimental results demonstrate
that the proposed algorithm has 87.67% average execution-time
improvement ratio when compared to four currently published
algorithms.

[1] E. R. Davies, Machine Vision: Theory, Algorithms, Practicalities, Academic
Press, London, 1990.
[2] J. Illingworth and J. Kittler, “A survery of the hough transform,” Computer
Vision, Graphics, and Image Processing, vol. 44, no. 1, pp. 87-116, Oct.1988.
[3] V. F. Leavers, “Survey: Which hugh transform,” CVGIP: Image Understanding,
vol. 58, no. 2, pp. 250-264, Sep. 1993.
[4] 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, vol. 25, no. 9, pp. 1007–1022, Sep. 1992.
[5] D. H. Ballard, “ Generalizing the Hough Transform to detect arbitrary
shapes,＂ Pattern Recognition, vol. 13, no. 2, pp. 111–122, 1981.
[6] E. R. Davies, “A modified Hough scheme for general circle location,＂
Pattern Recognition, vol. 7, no. 1, pp. 37–43, Jan. 1981.
[7] C. Kimme, D. Ballard, and J. Sklansky, “Finding circles by an array of
accumulators,＂ Communication of the ACM, vol. 18, no. 2, pp. 120–122, Feb.
1975.
[8] N. Kiryati, Y. Eldar, and A. M. Bruckstein, “ A probabilistic Hough
transform.＂ Pattern Recognition, vol. 24, no. 4, pp. 303–316, 1981.
[9] L. Xu, E. Oja, and P. Kultanan, “A new curve detection method: Randomized
Hough transform (RHT),＂ Pattern Recognition, vol. 11, no. 5, pp. 331–338,
May. 1990.
45
[10] L. Xu and E. Oja, “Randomized Hough transform (RHT): Basic mechanisms,
algorithms, and computational complexities,＂ CVGIP: Image Understanding,
vol. 57, no. 2, pp. 131-154, Mar. 1993.
[11] S. H. Chiu and J. J. Liaw, “An effective voting method for circle detection,”
Pattern Recognition Letters, vol. 26, no. 2, pp. 121-133, Jan. 2005.
[12] C. T. Ho and L. H. Chen, “A fast ellipse/circle detector using geometric
symmetry,＂ Pattern Recognition, vol. 28, no. 1, pp. 117–124, Jan. 1995.
[13] C. T. Ho and L. H. Chen, “A high-speed algorithm for elliptical object
detection,＂ IEEE Transactions on Image Processing, vol. 5, no. 3, Mar. 1996.
[14] C. Zhong, D. He, and W. Guoyou, “A new circle targets extraction algorithm,”
IEEE International Conference on Multimedia Information Networking and
Security, vol.1, pp. 301-304, 2009.
[15] C. N. Young and J. J. Zou, “Adaptive circular object detection,” IEEE
International Conference on Signal Processing and Communication Systems, pp.
1-6,2008.
[16] J. Illingworth and J. Kittler, “The adaptive hough transform,” IEEE Transactions
on Pattern Analysis and Machine Intelligence, vol. PAMI-9, no. 5, pp. 690-698,
1987.
[17] H. Li, M. A. Lavin, and R. J. LeMaster, “Fast hough transform: A hierarchical
approach, ” Computer Vision, Graphics, and Image Processing, vol. 36, no. 2-3,
pp. 139-161, Dec.1986.
[18] S. Y. Guo, X. F. Zhang, and F. Zhang, “ Adaptive randomized Hough
transform for circle detection using moving window,＂ IEEE International
46
Conference on Machine Learning and Cybernetics, pp. 3880-3885, Aug. 2006.
[19] P. F. Zhang and Q. M. Li, “Research on iris image preprocessing algorithm,＂
IEEE International Conference on Machine Learning and Cybernetics, vol. 8, pp.
5220-5224, 2005.
[20] J. Canny, “A computational approach to edge detection,＂ IEEE Transactions
on Pattern Analysis and Machine Intelligence, vol. 8, No. 6, pp. 679-698, 1986.