本論文提出一種新的二階段霍夫轉換(two-stages Hough Transform)來偵測影像中的直線和圓。此種霍夫轉換最主要的特色是利用二次曲線疊代的方式先算出影像中特徵點的法線向量，進而把n維參數空間分解成n-1維的參數空間。我們利用此種方法來偵測圓並且延伸此種方法來偵測直線。在複雜影像中，大多部分的情況是只有直線和曲線。利用曲線疊代的方式，不只可以計算出特徵點的法線方向也可以計算出曲率。利用直線和曲線的曲率不同的特性，在二階段的直線霍夫轉換裡，可以有效的壓抑曲線不去進行投票，而只讓直線進行投票。在實驗中可以獲得很好的結果。我們並且把這些技術應用在CAD和其他實際的圖形中，發覺效果很好。

A new two-stages Hough transform for detecting lines and circles in digital image is proposed here. The main feature of the new two-stages Hough transform is to evaluate the normal direction of the feature point by using quadratic polynomial fitting and decompose n dimension parameter array into n-1 dimension parameter array. The method is extended to detect lines in the digital image. In complicated images, the most curves are straight lines and circles and arcs. By using quadratic polynomial fitting, the normal direction and the curvature would be computed. By using the property of the different curvature between the lines and arcs, the non-straight lines are suppressed not to vote and only let the straight lines to vote in the two-stages Hough transform with quadratic polynomial fitting. The approach would get good performance in the experiment. The technique would be applied in CAD image and real pattern to get good results.

中文摘要 i
Abstract ii
誌謝 iii
Contents iv
List of Figures vii
List of Tables x
1 Introduction 1
1.1 Survey 1
1.2 Motivation 4
1.3 Organization of the Thesis 4
2 Edge Detection Technique and Hough Transform 5
2.1 Edge detection 5
2.2 Standard Hough Transform 7
2.3 Circular Hough Transform 10
2.3.1 Standard Circular Hough Transform 10
2.3.2 Two-stages Hough Transform (21HT) 11
3 The two-stages Hough Transform with Quadratic Polynomial Fitting for Circle Detection 13
3.1 The Quadratic Polynomial Fitting 15
3.2 The Voting Process 22
3.3 The Normalized Radius Histogram and Cluster Detection 25
3.3.1 The Normalized Radius Histogram 26
3.3.2 Cluster Detection 29
3.4 The Flowchart of the two-stages Hough Transform with Quadratic Polynomial Fitting for Circles Detection 30
3.5 The Experiment with the two-stages Hough Transform with Quadratic Polynomial Fitting for circles Detection 32
3.6 Analysis of the two-stages Hough Transform with Quadratic Polynomial Fitting for circles Detection 50
4 The two-stages Hough Transform with Quadratic Polynomial Fitting for Lines Detection 51
4.1 The Evaluation of the Normal Angle and the Curvature of the Feature Point 52
4.2 The Modified Cluster Detection for Lines 57
4.3 The Complete Flowchart of the two-stages Hough Transform with Quadratic Polynomial Fitting for Lines Detection 59
4.4 The Experiment with the two-stages Hough Transform with Quadratic Polynomial Fitting for Lines Detection 61
4.5 Analysis of the two-stages Hough Transform with quadratic polynomial fitting for Lines Detection 67
5 The two-stages Hough Transform with Quadratic Polynomial Fitting on CAD Application 69
5.1 The Evaluation of the Arcs in the CAD Image 69
5.2 The Evaluation of the Lines in the CAD Image 71
5.3 The Experiment with the two-stages Hough Transform with quadratic polynomial fitting on CAD Application 74
5.4 Analysis on CAD Application 80
6 Conclusion 81
Bibliography 83
Appendix A. 86

[1] P. V. C. Hough, “Methods and Means for Recognizing Complex Patterns,”U.S. Patent 069654, 1962.
[2] C. Kimme, D. Ballard, and J. Sklansky, “Finding Circles by an array of Accumulators,”Communications of the ACM, vol. 18, no. 2, pp. 120-122, 1975.
[3] D. H. Ballard, “Generalizing the Hough Transform to Detect Arbitrary Shapes,”Pattern Recognition, vol. 13, no. 2, pp. 111-122, 1981.
[4] H. K. Yuen, J. Princen, J. Illingworth, and J. Kittler, “Comparative Study of Hough Transform Methods for Circle Finding,”Image and Vision Computing, vol. 8, no. 1, pp. 71-77, 1990.
[5] J. Illingworth and J. Kittler, “The Adaptive Hough Transform,” IEEE Transactions on Pattern and Machine Intelligence, vol. 9, no. 5, pp. 690-697, 1987.
[6] L. Xu, E. Oja, and P. Kultanen, “A New Curve Detection Method:Randomized Hough Transform,” Pattern Recognition Letters, vol. 11, no. 5, pp. 331-338, 1990.
[7] X. Cao and F. Deravi, “An Efficient Method for Multi-Circle Detection,” in Proc. 3th Int’l Conf. IEEE Computer Vision, Osaka, Japan, pp. 744-747, 1990.
[8] D. M. Tsai, “A Machine Vision Approach for Detecting and Inspecting Circular Parts,” Advanced Manufacturing Technology, vol. 15, no. 3, pp. 217-221, 1999.
[9] R. Takiyama and N. Ono, “A Least Square Error Estimation of the Center and Radii of Concentric Arcs,” Pattern Recognition Letters, vol. 10, no. 4, pp. 237-242, 1989.
[10] R. C. Gonzalez and R. E. Woods, Digital Image Processing. Reading, MA: Addison-Wesley Publishing, 1996.
[11] J. Canny, “A Computational Approach to Edge Detection,”IEEE Trans. PAMI, vol. 8, no. 6, pp. 679-698, 1986.
[12] R. O. Duda and P. E. Hart, “Use of the Hough Transform to Detect Lines and Curves in Picture,”Comm. ACM, vol. 15, no. 1, pp. 11-15, 1972.
[13] J. Y. Goulermas and P. Liatsis, “Incorporating Gradient Estimations in a Circle-Finding Probabilistic Hough Transform,” Pattern Analysis & Applications, vol. 2, no. 3, pp. 239-250, 1999.
[14] 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, pp. 15-26, 1999.
[15] Z. Kulpa, “On the Properities of Discrete Circles, Rings, and Disks,” Computer Graphics and Image Processing, vol. 10, no. 4, pp. 348-365, 1979.
[16] M. Doros, “Algorithm for Generation of Discrete Circles, Rings and Disks,” Computer Graphics and Image Processing, vol. 10, no. 4, pp. 366-371, 1979.
[17] Z. Kulpa, “A Note on the Paper by B. K. P. Horn: “Circle Generation for Display Devices”,” Computer Graphics and Image Processing, vol. 9, no. 1, pp. 102-103, 1979.
[18] M. J. Bazin and J. W. Benoit, “Offine Global Approach to Pattern Recognition for Bubble Chamber,” IEEE Trans on Nuclear Science, vol. ns-12, no. 4, pp. 291, 1965.
[19] P. Bastian and L. Dunn, “Global Approach to Pattern Recognition for Bubble Chamber,” IEEE Trans on Computer, vol. c-20, no. 1, pp. 995, 1971.
[20] F. O’Gorman and M. B. Clowes, “Finding Picture Edges Through Collinearity of Feature Points,” in Proc. 3th IJCAI IEEE T-COMP, Stanford, CA, pp. 449-456,1976.
[21] G. Gerig and F. Klein, “Fast Contour Identification through Efficient Hough Transform and Simplified Interpretation,” in Proc. 8th IJCP, Paris, French, pp. 498-500, 1986.
[22] A. A. Kassiam, T. Tan, and K.H. Tan, “A Comparative Study of Efficient Generalized Hough Transform Techniques,” Image and Vision Computing, vol. 17, no. 10, pp. 737-748, 1999.
[23] D. Ma and X. Chen, “Hough Transform Using Slope and Curvature as Local Properties to Detect Arbitrary 2D Shapes,” in Proc. 9th Int’l Conf on Pattern Recognition, Rome, Italy, pp. 511-513, 1988.