在使用標準的霍夫轉換時，最大的缺點就是：計算時間長及儲存空間需求大。隨機式霍夫轉換可以有效地改善傳統霍夫轉換的缺點，但是隨機式霍夫轉換並不適合應用在較複雜的影像上，因為在較複雜的影像上要找到目標的機率比較低。
在本研究中，我們首先提出一個改良式的隨機式霍夫轉換來偵測圓形及圓弧。我們先將影像利用邊界路徑切成若干子影像，然後利用圓弧分析方法及密度檢查法來改善其執行效率。
標準霍夫轉換方法中，投票是一個很重要的程序且影響了實際的執行效率。針對這項缺點，我們發展出更有效的投票方法來降低計算量及儲存空間的需求。傳統的投票方法是將影像中每一個點投票給多個圓形候選人，我們則令每一個點只投票給該點最有可能的圓形候選人。
在偵測圓形時，可利用三點來決定一個圓的存在。但在隨機式霍夫轉換上，隨機選取三個點，此三點在同一圓上的機率是非常低的。我們發展一個新的方法，只隨機選取一個點，然後利用我們提出的檢查方法來確認此點是否真的在一個真實的圓上面。這個快速隨機式霍夫轉換的執行時間很短，更適合應用在複雜的影像上。
最後，我們利用霍夫轉換投票的觀念，發展一個方法來自動辦識混紡紗截面影像中的纖維。我們的方法包含二個投票的技術：一個用來得到個別纖維的位置；另一個則用來偵測纖維的種類。我們也與先前的方法比較，我們的方法所使用的參數較少。

The drawbacks of the standard Hough transform (SHT) are the large computation and the large storage requirement. To improve the drawbacks of SHT, the randomized Hough transform (RHT) was proposed. But RHT isn't suitable for detecting the pattern with the complex image because the probability is too low.
In this thesis, we first propose a modified RHT to detect circle/circular arc efficiently. We segment an image into sub-images based on edge information, then we use the proposed circular arc analysis and density check rule to modify RHT for the circle/circular arc detection.
Since the voting method of SHT plays an important role to affect the pattern detection accuracy, we also propose a effective voting method to reduce the computation and the storage requirements of SHT for the circle detection. This method improves the efficiency of circle detection by letting each pixel only belong to one candidate of circle parameters.
Then we describe a proposed fast randomized Hough transform for circle/circular arc detection. We first pick the seed point at random. Then we propose a checking rule to check the seed point is on the true circle or not. Comparing with the previous techniques, the fast randomized Hough transform is required less computation times and is more suitable for the complex image.
At last, we use the proposed method to recognize the fiber patterns in the image of PET/Rayon composite yarn cross section. Our method consists of two voting techniques: the connected component voting (for obtaining single fiber locations) and the circle parameter voting (circle detection, for recognizing the fiber patterns). When comparing with the previous approach, the new method needs fewer parameters and is more flexible.

1.Abouelela, A., H. Abbas, H. Eldeeb and S. Nassar, "Statistical approach for textile fault detection," Proceedings of the IEEE International Conference on System, Man and Cybernetics, 8-11 Oct., Nashville, U.S.A., Vol. 4, pp. 2857-2862 (2000).
2.Aguado, A. S., E. Montiel and M. S. Nixon, "Invariant characterization of the Hough transform for pose estimation of arbitrary shapes," Pattern Recognition, Vol. 35, No. 5, pp. 1083-1097 (2002).
3.Atiquzzaman, M., "Multiresolution Hough Transform - an Efficient Method of Detection Patterns in Images," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 14, No. 11, pp. 1090-1095 (1992).
4.Bahlmann, C., G. Heidemann and H. Ritter, "Artificial neural networks for automated quality control of textile seams," Pattern Recognition, Vol. 32, No. 6, pp. 1049-1060 (1999).
5.Bakir, T. and S. J. Reeves, "A filter design method for minimizing ringing in a region of interest in MR spectroscopic images," IEEE Transactions on Medical Imaging, Vol. 19, No. 6, pp. 585-600 (2000).
6.Ballard, D. H., "Generalizing the Hough transform to detect arbitrary shapes," Pattern Recognition, Vol. 13, No. 2, pp. 111-122 (1981).
7.Bennett, N., R. Burridge and N. Saito, "A method to detect and characterized ellipses using the Hough transform," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 21, No. 7, pp. 652-657 (1999).
8.Bergen, J. R. and H. Shvaytser, "A probabilistic algorithm for computing Hough transform," Journal of Algorithms, Vol. 12, No.4, pp. 639-656 (1991).
9.Brejl, M. and M. Sonka, "Object localization and border detection criteria design in edge-based image segmentation: automated learning from examples," IEEE Transactions on Medical Imaging, Vol. 19, No. 10, pp. 973-985 (2000).
10.Brown, C. M., "Inherent bias and noise in the Hough transform," IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-5, No. 5, pp. 493-505 (1983).
11.Canales, V. F., M. P. Cagigal and P. M. Prieto, "Spatial Fourier transform of binary images using hardware operations: applications to object movement characterization," Optical Engineering, Vol. 37, No. 7, pp. 2182-2185 (1998).
12.Casasent, D. and P. Krishnapuram, "Curved object location by Hough transform and in versions," Pattern Recognition, Vol. 20, No. 2, pp. 181-188 (1987).
13.Ching, Y.-T., "Detecting line segments in an image - a new implementation for Hough transform," Pattern Recognition Letters, Vol. 22, No. 3-4, pp. 421-429 (2001).
14.Chiu, S.-H. and J.-J. Liaw, "A proposed circle/circular arc detection method using the modified randomized Hough transform," Journal of the Chinese Institute of Engineers, (accepted).
15.Chiu, S.-H. and J.-J. Liaw, "An effective voting method for circle detection," Pattern Recognition Letters, Vol. 26, No. 2, pp. 121-133 (2005).
16.Chiu, S.-H. and J.-J. Liaw, "Fiber recognition of PET/rayon composite yarn cross sections using voting techniques," Textile Research Journal, (accepted).
17.Chiu, S.-H., J.-Y. Chen and J.-H. Lee, "Fiber recognition and distribution analysis of PET/rayon composite yarn cross sections using image processing techniques," Textile Research Journal, Vol. 69, No.6, pp. 417-422 (1999).
18.Chiu, S.-H., S. Chou, J.-J. Liaw and C.-Y. Wen, "Textural defect segmentation using a Fourier-domain maximum likelihood estimation method," Textile Research Journal, Vol. 72, No. 3, pp. 253-258 (2002).
19.Chutatape, O. and L. Guo, "A Modified Hough Transform for Line Detection and Its Performance," Pattern Recognition, Vol. 32, No. 2, pp. 181-192 (1999).
20.Clausi, D. A. and M. E. Jernigan, "Designing Gabor filters for optimal texture separability," Pattern Recognition, Vol. 33, No. 11, pp. 1835-1849 (2000).
21.Conker, R. S., "A dual plane variation of the Hough transform for detecting non- concentric circles of different radii," Computer Vision, Graphics, and Image Processing, Vol. 43, No. 2, pp. 115-132 (1988).
22.Davies, E. R., "A modified Hough scheme for general circle location," Pattern Recognition Letters, Vol. 7, No. 1, pp. 37-43 (1988).
23.Duda, R. D. and P. E. Hart, "Use of the Hough transform to detect lines and curves in pictures," Communications of ACM, Vol. 15, No. 1, pp. 11-15 (1972).
24.Diou, A., Y. Voisin and C. Santo, "The Hough transform - a new approach," Proceedings of Industrial Electronics Conference, 5-10 Aug., Taipei, Taiwan, Vol. 3, pp. 1612-1617 (1996).
25.Ecabert, O. and J.-P. Thrian, "Adaptive Hough transform for the detection natural shapes under weak affine transforms," Pattern Recognition Letters, Vol. 25, No. 12, pp. 1411-1419 (2004).
26.Foresti, G. L., C. S. Regazzoni and G. Vernazza, "Circular arc extraction by direct clustering in a 3D Hough parameter space," Signal Processing, Vol. 41, No. 2, pp. 203-224 (1995).
27.Galambos, C., J. Matas and J. Kittler, "Progressive probabilistic Hough transform for line detection," IEE Proceedings of Vision, Image and Signal Processing, Vol. 148, No. 3, pp. 158-165 (2001).
28.Goneid, A., S. EI-Gindi and A. Sewisy, "Method for the Hough transform detection of circles and ellipses using 1-dimensional array," Proceedings of IEEE International Conference on System, Man and Cybernetics, 12-15 Oct., Orlando, U.S.A., Vol. 4, pp. 3154-3157 (1997).
29.Gonzalez, R. C. and R. E. Woods, Digital Image Processing, Second Edition, Prentice Hall, New Jersey (2002).
30.Goulermas, J. Y. and P. Liatsis, "Incorporating gradient estimations in a circle-finding probabilistic Hough transform," Pattern Analysis and Applications Vol. 2, No. 3, pp. 239-250 (1999).
31.Grimson, W. E. L. and D. P. Huttenlocher, "On the sensitivity of the Hough transform for object recognition," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, No. 3, pp. 255-274 (1990).
32.Guo, L. and O. Chutatape, "Influence of discretization in image space on Hough transform," Pattern Recognition, Vol. 32, No. 4, pp. 635-644 (1999).
33.Harikumar, G. and Y. Bresler, "Perfect blind restoration of images blurred by multiple filters: theory and efficient algorithms," IEEE Transactions on Image Processing, Vol. 8, No.2, pp. 202-219 (1999).
34.Hough, P. V. C., "A method and means for recognizing complex patterns," U.S. Patent 3,069,654. (1962).
35.Illingworth, J. and J. Kittler, "The adaptive Hough transform," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-9, No. 5, pp. 690-698 (1987).
36.Illinggworth, J. and J. Kittler, "A survey of the Hough transform," Computer Vision, Graphics, and Image Processing, Vol. 44, No. 1, pp. 87-116 (1988).
37.Immerkar, J. "Some remarks on the straight line Hough transform," Pattern Recognition Letters, Vol. 19, No. 12, pp. 1133-1135 (1998).
38.Ioannou, D. and 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).
39.Jain, R., R. Kasturi and B. G. Schunck, Machine Vision, McGraw-Hill, New York (1995).
40.Jia, K., S. Fang and S. Dun, "Fast lossless color image compressing method using neural network,," Proceedings of IEEE Region 10 Annual International Conference, 28-31 Oct., Beijing, China, Vol. 1, pp. 249-252 (2002).
41.Kalviainen, H. and P. Hirvonen, "An extension to the randomized Hough transform exploiting connectivity," Pattern Recognition Letters, Vol. 18, pp. 77-85 (1997).
42.Kalviainen, H., P. Hirvonen, L. Xu and E. Oja, "Probabilistic and non-probabilistic Hough transform: overview and comparisons," Image and Vision Computing, Vol. 13, No.4, pp. 239-252 (1995).
43.Kiryati, N., H. Kalviainen and S. Aloutinen, "Randomized or Probabilistic Hough Transform: Unified Performance Evaluation," Pattern Recognitions Letters, Vol. 21, No. 13-14, pp. 1157-1164 (2000).
44.Kiryati, N., Y. Eldar and A. M. Bruckstein, "A Probabilistic Hough Transform," Pattern Recognition, Vol. 24, No. 4, pp. 303-316 (1991).
45.Kultanen, P., L. Xu and E. Oja, "Randomized Hough transform (RHT)," Proceedings of International Conference on Pattern Recognition, 16-21 Jun., Atlantic, U.S.A, Vol. 1, pp. 631-635 (1990).
46.Lam, E. Y., "Image restoration in digital photography," IEEE Transactions on Consumer Electronics, Vol. 49, No. 2, pp. 269-274 (2003).
47.Lam, W. C. Y., L. T. S. Lam, K. S. Y. Yuen and D. N. K. Leung, "An analysis on quantizing the Hough space," Pattern Recognition Letters, Vol. 15, No.11, pp. 1127-1135 (1994).
48.Landau, U. M., "Estimation of circular arc center and its radius," Computer Vision, Graphics, and Image Processing, Vol. 38, No. 3, pp. 317-326 (1987).
49.Leavers, V. F., "Which Hough transform?" CVGIP: Image Understanding, Vol. 58, No.12, pp. 250-264 (1993).
50.Leu, J.-G., "Image enlargement based on a step edge model," Pattern Recognition, Vol. 33, No. 12, pp. 2055-2073 (2000).
51.Li, H., M. A. Lavin and R. J. LeMaster, "Fast Hough Transform: a hierarchical approach," Computer Vision Graphics Image Processing, Vol. 36, No. 2-3, pp. 139-161 (1986).
52.Liaw, J.-J. and S.-H. Chiu, "A fast randomized Hough transform for circle/circular arc recognition," (submitted).
53.Luo, C.-H., C.-Y. Wen, J.-J. Liw, S.-H. Chiu and W.-M. G. Lee, "Texture characterization of atmospheric fine particles by fractional Brownian motion analysis," Atmospheric Environment, Vol. 38, No. 6, pp. 935-940 (2004).
54.Luo, D. S., P. Smart and J. E. S. Macleod, "Circular Hough transform for roundness measurement of objects," Pattern Recognition, Vol. 28, No. 11, pp. 1745-1749 (1995).
55.Lo, R. O. and W. H. Tsai, "Gray-scale Hough transform for thick line detection in gray-scale images," Pattern Recognition, Vol. 28, No. 5, pp. 647-661 (1995).
56.McLaughlin, R. A., "Randomized Hough transform: Improved ellipse detection with comparison," Pattern Recognition Letters, Vol. 19, No. 3-4, pp. 299-305 (1998).
57.Millan, M. S., J. Escofet, H. C. Abril, R. Navarro and Y. Torres, "Automatic quality control of textile webs by image processing," Proceedings of SPIE - The International Society for Optical Engineering, Vol. 3572, pp. 349-352 (1999).
58.Milanfar, P., "On the Hough transform of a polygon," Pattern Recognition Letters, Vol. 17, No. 2, pp. 209-210 (1996).
59.Montiel, E., A. S. Aguado and M. S. Nixon, "Improving the Hough transform gathering process for affine transformations," Pattern Recognition Letters, Vol. 22, No. 9, pp. 959-969 (2001).
60.Murphy, L. M., "Linear feature detection and enhancement in noisy image via random transform," Pattern Recognition Letters, Vol. 4, No. 4, pp. 279-284 (1986).
61.Nagao, M. and S. Nakajima, "On the relation between the Hough transformation and the projection curves of a rectangular window," Pattern Recognition Letters, Vol. 6, No.3, pp. 185-188 (1987).
62.Palmer, P. L., J. Kittler and M. Petrou, "Using focus of attention with the Hough transform for accurate line parameter estimation," Pattern Recognition, Vol. 27, No. 9, pp. 1127-1134 (1994).
63.Pei, S.-C. and J.-H. Horng, "Circular arc detection based on Hough transform," Pattern Recognition Letters, Vol. 16, No. 6, pp. 615-625 (1995).
64.Shaked, D., O. Yaron and N. Kiryati, "Deriving stopping rules for the probabilistic Hough transform by sequential analysis," Computer Vision and Image Understanding, Vol. 63, No. 3, pp. 512-526 (1996).
65.Sklansky, J., "On the Hough technique for curve detection," IEEE Transactions on Computer, C-27, No.10, pp. 923-926 (1978).
66.Theodoridis, S. and K. Koutroumbas, Pattern Recognition, Academic Press, New York (1999).
67.Thibodeaux, D. P. and J. P. Evan, "Cotton fiber maturity by image analysis," Textile Research Journal, Vol. 56, No. 2, pp. 130-139 (1986).
68.Thomas, S. M. and Y. T. Chan, "A simple approach for the estimation of circular arc center and its radius," Computer Vision, Graphics, and Image Processing, Vol. 45, No. 3, pp. 362-370 (1989).
69.Tsai, W.-H. and S.-L. Chou, "Detection of generalized principal axes in rotationally symmetric shapes," Pattern Recognition, Vol. 24, No.2, pp. 95-104 (1991).
70.Van Veen, T. M. and F. C. A. Groen, "Discretization errors in the Hough transform," Pattern Recognition, Vol. 14, No. 1-6, pp. 137-145 (1981).
71.Walsh, D. and A. E. Raftery, "Accurate and efficient curve detection in images: the importance sampling Hough transform," Pattern Recognition, Vol. 35, No. 7, pp. 1421-1431 (2002).
72.Wen, C.-Y., S.-H. Chiu, J.-J. Liaw and C.-P. Lu, "The safety helmet detection for ATM's surveillance system via the modified Hough transform," Proceedings of 37th Annual IEEE International Carnahan Conference on Security Technology, 14-16 Oct., Taipei, Taiwan, pp. 364-369, (2003).
73.Wen, C.-Y., S.-H. Chiu, W.-S. Hsu and G.-H. Hsu, "Defect segmentation of texture images with wavelet transform and co-occurrence matrix," Textile Research Journal, Vol. 71, No. 8, pp. 743-749 (2001).
74.Wong, K. K., C. H. Tse, K. S. Ng, T. H. Lee and L. M. Cheng, "Adaptive water marking," IEEE Transactions on Consumer Electronics, Vol. 43, No.4, pp. 1003-1009 (1997).
75.Xu, B., B. Pourdeyehimi and J. Sobus, "Characterizing fiber crimp by image analysis: definition, algorithms, and techniques," Textile Research Journal, Vol. 62, No. 2, pp. 73-80 (1992).
76.Xu, B. and Y. L. Ting, "Fiber image analysis, part 1: fiber image enhancement," Journal of the Textile Industry, Vol. 87, No. 2, pp. 274-283 (1996).
77.Xu, L., E. Oja and P. Kultanen, "A New Curve Detection Method: Randomized Hough Transform," Pattern Recognition Letters, Vol. 11, No. 5, pp. 331-338 (1990).
78.Xu, W.-R., H.-G. Zhang, J. Guo and G. Chen, "Discrimination between printed and handwritten characters for check OCR system," Proceedings of the First International conference on Machine Learning and Cybernetics, 4-5 Nov., Beijing, China, Vol. 2, pp. 1048-1053 (2002).
79.Yang, M. C. K., J. S. Lee, C. C. Lien and C. L. Huang, "Hough transform modified by line connectivity and line thickness," IEEE Transactions on Pattern analysis and Machine Intelligence, Vol. 19, No. 8, pp. 905-910 (1997).
80.Yla-Jaaski, A. and N. Kiryati, "Adaptive termination of voting in the probabilistic circular Hough transform," IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI 16, No. 9, pp. 911-915 (1994).
81.Yip, R. K. K., 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 (1992).
82.Yuen, K. S. Y., L. T. S. Lam and D. N. K. Leung, "Connective Hough transform," Image and Vision Computing, Vol. 11, No.5, pp. 295-301 (1993).
83.http://robotics.eecs.berkeley.edu/~mayi/imgproc/