在影像處理和圖形識別領域，圓形偵測是很重要且基本的方法。本論文分為兩部份，第一部份提出了以法線為基礎的抽樣策略來決定候選圓，較傳統的隨機式測圓有更高的機率使得候選圓成為真圓，大大的降低了計算時間。為了提昇準確率，第二部份提出以重新投票為基礎的精煉策略。實驗結果顯示和先前有關的隨機式測圓相比，以我們提出的以法線為基礎的抽樣策略和以重新投票為基礎的精煉策略來測圓，大大的降低了計算時間且有更好的準確率。

Circle-detection is an important and fundamental operation in image
processing and pattern recognition. This thesis first presents a new
gradient line-based sampling strategy to determine a candidate
circle and the determined candidate circle has higher probability to
be promoted to a true circle when compared with the traditional
randomized strategy; it leads to significantly computational effect.
Further, for enhancing the detection accuracy, a new revoting-based
refinement strategy is presented. Experimental results demonstrated
that our proposed gradient line-based sampling strategy and
revoting-based refinement strategy can significantly improve
computing time performance and the detection accuracy for circle
detection when compared with previous randomized related algorithms.

[1] D. H. Ballard, “Generalizing the Hough transform to detect arbitrary shapes,” Pattern Recognition, Vol. 13, No. 2, 1981, pp. 111–122.
[2] J. E. Bresenham, “Algorithm for computer control of a digital plotter,” IBM System Journal, Vol. 4, No. 1, 1965, pp. 25–30.
[3] J. E. Bresenham, “A linear algorithm for incremental digital display of circular arcs,”Communications of the ACM, Vol. 20, No. 2, 1977, pp. 100–106.
[4] T. C. Chen and K. L. Chung, “An efficient randomized algorithm for detecting circles,”Computer Vision and Image Understanding, Vol. 83, No. 2, 2001, pp. 172–191.
[5] S. H. Chiu and J. J. Liaw, “An effective voting method for circle detection,” Pattern Recognition Letters, Vol. 26, No. 1, 2005, pp. 121–133.
[6] 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, Vol. 190, No. 1, 2007, pp. 132–149.
[7] K. L. Chung and Y. H. Huang, “A pruning-and-voting strategy to speed up the detection for lines, circles, and ellipses,” Journal of Information Science and Engineering, Vol. 24, No. 2, 2008, pp. 503–520.
[8] E. R. Davies, “Truncating the Hough transform parameter space can be beneficial,”Pattern Recognition Letters, Vol. 24, No. 1–3, 2003, pp. 129–135.
[9] E. R. Davies, Machine Vision: Theory, Algorithms, Practicalities, third ed., Morgan Kaufmann, San Fransisco, CA, 2004.
[10] R. O. Duda and P. E. Hart, “Use of the Hough transformation to detect lines and curves in pictures,” Communications of the ACM, Vol. 15, No. 1, 1972, pp. 11–15.
[11] D. A. Forsyth, Computer Vision: A Modern Approach, Prentice-Hall, New Jersey, 2002.
[12] R. Gonzalez and R. Woods, Digital Image Processing, Addison Wesley, New York, 1992.
[13] C. T. Ho and L. H. Chen, “A fast ellipse/circle detector using geometric symmetry,”Pattern Recognition, Vol. 28, No. 1, 1995, pp. 117–124.
[14] P. V. C. Hough, “Method and means for recognizing complex patterns,” US Patent# 3,069,654, 1962.
[15] P. V. C. Hough, Method and means for recognizing complex patterns, Addison Wesley, New York, 1992.
[16] D. Hearn and M. P. Baker, Computer Graphics, third ed., Prentice-Hall, New Jersey, 1997.
[17] J. Illingworth and J. Kittler, “The adaptive Hough transform,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 9, No. 5, 1987, pp. 690–698.
[18] J. Illingworth and J. Kittler, “Survey: Survey of the Hough Transforms,” Computer Vision, Graphics, and Image Processing, Vol. 44, No. 1, 1988, pp. 87–116.
[19] D. Ioannou, W. Huda, and A. F. Laine, “Circle recognition through a 2D Hough transform and radius histogramming,” Image and Vision Computing, Vol. 17, No. 1, 1999, pp. 15–26.
[20] R. Jain, R. Kasturi, and B. G. Schunck, Machine Vision, McGraw-Hill, Columbus, OH, 1995.
[21] M. R. Kappel, “An ellipse-drawing algorithms for faster displays,” Fundamental Algorithms for Computer Graphics, 1985, pp. 257–280.
[22] H. S. Kim and J. H. Kim, “A two-step circle detection from the intersecting chords,”Pattern Recognition Letters, Vol. 22, No. 6–7, 2001, pp. 787–798.
[23] C. Kimme, D. Ballard, and J. Sklansky, “Finding circles by an array of accumulator,”Communications of the ACM, Vol. 18, No. 2, 1975, pp. 120–122.
[24] N. Kiryati, Y. Eldar, and A. M. Bruckstein, “A probabilistic Hough transform,”Pattern Recognition, Vol. 24, No. 4, 1991, pp. 303–316.
[25] J. R. J. Lee, M. L. Smith, L. N. Smith and P. S. Midha, “Robust and efficient automated detection of tooling defects in polished stone,” Computers in Industry, Vol. 56, No. 8, 2005, pp. 787–801.
[26] L. Xu, E. Oja, and P. Kultanan, “A new curve detection method: randomized Hough transform (RHT),” Pattern Recognition Letters, Vol. 11, No. 5, 1990, pp. 331–338.
[27] L. Xu and E. Oja, “Randomized Hough transform (RHT): basic mechanisms, algorithms, and computational complexities,” Computer Vision Graphic Image Process: Image Understanding, Vol. 57, No. 2, 1993, pp. 131–154.
[28] 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, 1992, pp. 1007–1022.
[29] A. Yl¨a-J¨a¨aski and N. Kiryati, “Adaptive termination of voting in probabilistic Hough transform,” IEEE Trans on Pattern Analysis and Machine Intelligence, Vol. 16, No. 9, 1994, pp. 911–915.