圓形/圓弧偵測是電腦視覺研究中相當重要的主題，它被應用的範圍相當廣泛，例如，安全帽之圓形/圓弧偵測 (應用於犯罪預防)、印刷電路板之圓形/圓弧偵測(應用於印刷電路板定位與瑕疵檢測)與纖維橫斷面之圓形/圓弧偵測(應用於混紗纖維橫斷面之成分分析)等等。應用在實務工作時，偵測速度與效率是主要的關鍵。近十年內，多階段式圓形/圓弧偵測方法(Multi-step methods)以多步驟的框架完成快速的圓形/圓弧偵測，其偵測速度是快速且有效率的。多階段式圓形/圓弧偵測方法的主要執行步驟包含：步驟1，隨機選取「初始點」；步驟2，利用幾何圖形特性以找尋可能性「搜尋點」；步驟3，同時使用「初始點」與「搜尋點」以獲得候選圓形/圓弧；步驟4，確認是否為目標圓形/圓弧。

本論文，以多階段式圓形/圓弧偵測的框架為基礎，提高「初始點」被選取的機率，提出一個使偵測速度更快速且更有效率的方法：「快速隨機式的有效偵測圓形/圓弧演算法 (A fast randomized method for efficient circle/arc detection, FRECD)」。該方法推廣圓形/圓弧的幾何對稱，使被選取的「初始點」不再只有侷限於目標圓/圓弧上，反而是包含目標圓/圓弧的附近區域(即使是附近的雜訊點一旦被選用為初始點，也可視為有效點)；因此在本質上具有較高的機率可選中有效的「初始點」，將可有效的降低運算量。
除此之外，我們提出一個改良式的多階段式圓形/圓弧偵測的框架，在隨機選取「初始點」之後，新增一個檢查機制：「以鏡射檢查為基礎的有效偵測圓形/圓弧演算法 (A mirror-checking based algorithm for efficient circle/arc detection)」。此機制利用鏡射方式檢查初始點附近的圖樣(pattern)是否具有足夠的對稱性(亦即是否為有效之初始點)。當對稱性不足時，則不需要再浪費時間於後續的步驟(即多階段式圓形/圓弧偵測的框架步驟2至4)。

本論文使用若干實驗以驗證上述二個方法論的偵測效率與效能，其結果均顯示可有效提昇偵測的速度與效率；除此之外，於理論分析時，亦顯示本論文提出之方法論可有效減少電腦視覺在執行圓形/圓弧偵測時的運算負擔。

Circle/arc detection is an important research topic in computer science, and it has been applied to many fields, such as helmet detection for criminal protection, circle/arc detection in printed circuit board for localization and inspection, and circle/arc detection in fiber images for composition recognition. Recently, multi-step scheme methods have shown their capability of circle/arc detection. The scheme includes four main steps: (1) random picking initial points; (2) finding searching points within a predefined searching region; (3) obtaining a candidate circle; (4) verifying target circles/arcs.

In this thesis, the validation of picking initial point(s) is concerned to decrease time consuming in circle/arc detection. A fast multi-step circle/arc detection method based on the geometric symmetry is proposed: A fast randomized method for efficient circle/arc detection (FRECD). The method removes the limitation of picking the initial point which must lie on the target circles/arcs. It not only increases the probability of picking an initial point, but also uses an empty voting space for circle/arc detection.

Besides, we propose a mirror-checking algorithm to promote the efficiency of the multi-step based methods. We use the algorithm to check whether two patterns around the initial points are mirrored to each other. If they are not mirrored, we will ignore the initial points and find new ones to avoid redundant procedures.

From the experimental results, the proposed fast multi-step circle/arc detection method based on the geometric symmetry provides better performance in picking valid initial point(s) and using less time consuming than previous multi-step based methods. Besides, the statistic analysis also demonstrates that the proposed method is fast and efficient.

[1] Chiu, S. H., Liaw, J. J. and Lin, K. H., “A Fast Randomized Hough Transform for Circle/Circular Arc Recognition,” International Journal of Pattern Recognition and Artificial Intelligence, Vol. 24 No. 3, pp. 457-474, 2010.
[2] Chen, C. H., Lin, Y. T., Wen, C. Y., Wang, L. C., Lin, K. H., Chiu, S. H., Yang, Y. H., Lee, J. H. and Chiang, B. L., “Quantitative assessment of allergic shiners in children with allergic rhinitis,” The Journal of Allergy and Clinical Immunology, Vol. 123, Issue 3, pp. 665-671.e6, 2009.
[3] Luo, C. H., Wen, C. Y., Yuan, C. S., Liaw, J. J., and Chiu, S. H., “Investigation of urban atmospheric visibility by high-frequency extraction: model development and field test,” Atmospheric Environment, Vol. 39, No. 14, pp. 2545-2552, 2005.
[4] Luo, C. H., Yang, S., Wen, C. Y., Syu, M. Y., Lin, K. H., Chiu, S. H. and Chang, C. P., “Fluorescent aerosol leakage quantification for protective clothing with an entropy-based image processor for industrial and medical workers,” Journal of Aerosol Science, Vol. 42, Issue 7, pp. 491-496, 2011.
[5] Liaw, J. J., “Fast Circle/Circular arc Detection Methods Based on the Modified Hough Transform,” Ph.D. dissertation, National Taiwan University of Science and Technology, Taipei, Taiwan (2005).
[6] Lu, C. P., “A Study of Digital Signal Separation and Pattern Recognition,” Ph.D. dissertation, National Taiwan University of Science and Technology, Taipei, Taiwan (2006).
[7] Yamaguchi, T., Nagata, K., Truong, P. Q., Fujio, M. and Inoue, K., “Pattern recognition of EEG signal during motor imagery by using SOM,” International Journal of Innovative Computing, Information and Control, Vol. 4, No. 10, pp. 2617-2630, 2008.
[8] Tamura, H., Gotoh, T., Okumura, D., Tanaka, H. and Tanno, K., “A study on the s-EMG pattern recognition using neural network,” International Journal of Innovative Computing, Information and Control, Vol. 5, No. 12(B), pp. 4877-4884, 2009.
[9] Lu, N. and Feng, Z., “Accumulative intersection space based corner detection algorithm,” International Journal of Pattern Recognition and Artificial Intelligence, Vol. 22, pp. 1159-1586, 2008.
[10] Rianto, Y., Kondo, S. and Kim, T., “Detection of roads from satellite images using optimal search,” International Journal of Pattern Recognition and Artificial Intelligence, Vol. 14, pp. 1008-1023, 2000.
 
[11] Kim, H., Katsumata, Y., Itai, Y., Tan, J. K. and Ishikawa, S., “Automatic detection of GGO candidate regions by using density and shape features,” International Journal of Innovative Computing, Information and Control, Vol. 6, No. 1, pp. 255-263, 2010.
[12] Ganzalez, R. C. and Woods, R. E., Digital Image Processing, 3rd Edition, Prentice Hall, 2008.
[13] Suetake, N. and Uchino, E., “Generalized fuzzy Hough transform for detecting arbitrary shapes in a vague and noisy image,” Soft Computing, Vol. 10, No. 12, pp. 1161-1168, 2006.
[14] Roy, P. P., Pal, U. and Llados, J., “Seal object detection in document images using GHT of local component shapes,” Proc. of the ACM Symposium on Applied Computing, Sierre, Switzerland, pp. 23-27, 2010.
[15] Chung, C. H., Cheng, S. C. and Chang, C. C., “Adaptive image segmentation for region-based object retrieval using generalized Hough transform,” Pattern Recognition, Vol. 43, No. 10, pp. 3219-3232, 2010.
[16] Ballard, D. H., “Generalizing the Hough transform to detect arbitrary shapes,” Pattern Recognition, Vol. 13, No. 2, pp. 111-122, 1981.

[17] Nixon, M. S. and Aguado, A. S., Feature Extraction and Image Processing, 2nd Edition, Newnes, New York. 2002.
[18] Hough, P. V. C., “A method and means for recognizing complex patterns,” U.S. Pat., 3069654 (1962).
[19] Duda, R. D. and Hart, P. E., “Use of the Hough transform to detect lines and curves in pictures,” Communications of the Association of Computing Machinery, Vol. 15, pp. 11-15, 1972.
[20] Walsh, D., and Raftery, A. E., “Accurate and efficient curve detection in images: The importance sampling Hough transform,” Pattern Recognition, Vol. 35, No. 7, pp. 1421-1431, 2002.
[21] Xu, L., “A unified perspective and new results on RHT computing, mixture based learning, and multi-learner based problem solving,” Pattern Recognition, Vol. 40, No. 8, pp. 2129-2153, 2007.
[22] Fernandes, L. A. F. and Oliveira, M. M., “Real-time line detection through an improved Hough transform voting scheme,” Pattern Recognition, Vol. 41, No. 1, pp. 299-314, 2008.
 
[23] Guo, S., Pridmore, T., Kong, Y. and Zhang, X., “An improved Hough transform voting scheme utilizing surround suppression,” Pattern Recognition Letters, Vol. 30, No. 13, pp. 1241-1252, 2009.
[24] Huang, J., You, X., Tang, Y. Y., Du, L., and Yuan, Y., “A novel iris segmentation using radial-suppression edge detection,” Signal Processing, Vol. 89, No. 12, pp. 2630-2643, 2009.
[25] Luo, Y., Liu, J. and Shi, X., “An improved method of RHT to localize circle applied in intelligent transportation system,” ICALIP 2008 - 2008 International Conference on Audio, Language and Image Processing, Processing, Shanghai, China, No. 4589970, pp. 335-338, 2008.
[26] D’Orazio, T., Ancona, N., Cicirelli, G. and Nitti, M., “A ball detection algorithm for real soccer image sequences,” in Int. Conf. on Pattern Recognition (ICPR), DC, USA, Vol. 16, No. 1, pp. 210-213, 2002.
[27] 陳庭軒，「微型鑽針專用砂輪輪廓半徑量測最佳化方法」，碩士論文，國立台灣科技大學，台北市 (2007)。
[28] Kim, H. S., Lee, B. R. and Kim, R. J., “Development of Computer-vision-based Pipe Inspection System,” Proceeding - The 1st International Forum On Strategic Technology "e-Vehicle Technology", No. 4107416, pp. 403-406, 2006.
[29] Wen, C. Y., Chiu, S. H., Liaw, J. J., and Lu, C. P., “The safety helmet detection for ATM's surveillance system via the modified Hough transform,” IEEE Annual International Carnahan Conference on Security Technology, Proceedings, Taipei, Taiwan, pp. 364-369, 2003.
[30] Qiao, N., Ye, Y., Huang, Y., Liu, L. and Wang, Y., “Method of circle detection in pcb optics image based on improved point Hough transform,” in Proc. of SPIE – The International Society for Optical Engineering, pp. 72832Y-1-5, 2009.
[31] Chiu, S. H., and Liaw, J. J., “Fiber recognition of PET/rayon composite yarn cross sections using voting techniques,” Textile Research Journal, Vol. 75, No. 5, pp. 442-448, 2005.
[32] Illingworth, J. and Kittler, J., “A survey of the Hough transform,” Computer Vision. Graphics, and Image Processing, Vol. 44, pp. 87-116, 1988.
[33] Qingsong, X., Juan, S., and Tiantian, L., “A detection and recognition method for prohibition traffic signs,” in Int. Conf. on Image Analysis and Signal Processing, Zhejiang, China, pp. 583-586, 2010.
[34] Shahid, M. and Nawaz, T., “Iris detection based on pupil prospect point and horizontal projections,” in Proc. of SPIE – The International Society for Optical Engineering, Singapore, Singapore, pp. 754628-1-754628-6, 2010.
[35] Shamsi, M., Saad, P. B., Ibrahim, S. B., A. Rasouli and N. B. Abdulrahim, “A new accurate technique for Iris boundary detection,” WSEAS Transactions on Computers, Vol. 9, pp. 654-663, 2010.
[36] Wu, J., Si, M., Tan, F. and Gu, C., “Real-time automatic road sign detection,” in Proc. of the 5th Int. Conf. on Image and Graphics, Suzhou, China, pp. 540-544, 2009.
[37] Amin, A., “Recognition of hand-printed Latin characters based generalized Hough transform and decision tree learning techniques,” International Journal of Pattern Recognition and Artificial Intelligence, Vol. 14, pp. 369-387, 2000.
[38] Chutatape, O. and Guo, L. A., “A modified Hough transform for line detection and its performance,” Pattern Recognition, Vol. 32, pp. 181-192, 1999.
[39] Davies, E. R., “A modified Hough scheme for general circle location,” Pattern Recognition Letters, Vol. 7, pp. 37-43, 1987.
[40] Wang, F., Yuan, Z., Zheng, N. and Liu, Y., “A fast, memory-efficient and parallelizable arc/circle segmentation algorithm,” Applied Mathematics and Computation, Vol. 205, No. 2, pp. 841-848, 2008.
 
[41] Zhu, X., Rangayyan, R. M. and Ells, A. L., “Detection of the optic nerve head in fundus images of the retina using the Hough transform for circles,” Journal of Digital Imaging, Vol. 23, pp. 332-341, 2010.
[42] Foresti, G. L., Regazzoni, C. S. and Vernazza, G., “Circular arc extract ion by direct clustering in a 3D Hough parameter space,” Signal Processing, Vol. 41, pp. 203-224, 1995.
[43] Pei, S. C. and Horng, J. H., “Circular arc detection based on Hough transform,” Pattern Recognition Letters, Vol. 16, pp. 615-625, 1995.
[44] Ioannou, D., Huda, W. and Laine, A. F., “Circle recognition though a 2D Hough transform and radius histogramming,” Image and Vision Computing, Vol. 17, pp. 15-26, 1999.
[45] Rad, A. A., Faez, K. and Qaragozlou, N., “Fast Circle Detection Using Gradient Pair Vectors,” Proceedings of the Seventh International Conference on Digital Image Computing: Techniques and Applications, Sydney, Dicta, pp. 879-887, 2003.
[46] Chen, G., Ji, J. and Sun, L., “A novel circle detector based on sub-image point pairs,” Proceedings of the 2008 IEEE International Conference on Information and Automation, ICIA 2008, Zhangjiajie, Hunan, China, 4608081, pp. 661-666, 2008.
 
[47] Kim, H. S., and Kim, J. H., “A two-step circle detection algorithm from the intersecting chords,” Pattern Recognition Letters, Vol. 22, No. 6-7, pp. 787-798, 2001.
[48] Chen, T. C. and Chung, K. L., “An efficient randomized algorithm for detecting circles,” Computer Vision and Image Understanding, Vol. 83, No. 2, pp. 172-191, 2001.
[49] Chiu, S. H. and Liaw, J. J., “An effective voting method for circle detection,” Pattern Recognition Letters, Vol. 26, No. 2, pp. 121-133, 2005.
[50] Guo, S. Y., Zhang, X. F., and Zhang, F., “Adaptive randomized Hough transform for circle detection using moving window,” Proceedings of the 2006 International Conference on Machine Learning and Cybernetics 2006, Dalian, China, No. 4028748, pp. 3880-3885, 2006.
[51] Xing, C. and Wang, J., “An improved method for circle detection,” in Lecture Notes in Computer Science (LNCS), pp. 463-468, 2008.
[52] Kiryati, N., Eldar, Y. and Bruckstein, A. M., “A probabilistic Hough transform,” Pattern Recognition, Vol. 24, No. 4, pp. 303-316, 1991.
 
[53] Kiryati, N., Kalviainen, H. and Alaoutinen, S., “Randomized or probabilistic Hough transform: unified performance evaluation,” Pattern Recognition Letters, Vol. 21, pp. 1157-1164, 2000.
[54] Xu, L., Oja, E. and Kultanen, P., “A new curve detection method: randomized Hough transform (RHT),” Pattern Recognition Letters, Vol. 11, No. 5, pp. 331-338, 1990.
[55] Xu, L. and Oja, E., “Randomized Hough Transform (RHT): Basic Mechanisms, Algorithms, and Computational Complexities,” CVGIP: Image Understanding, Vol. 57, No. 2, pp. 131-154, 1993.
[56] Bergen, J. R., and Shvaytser, H., “A probabilistic algorithm for computing Hough transforms,” Journal of Algorithms, Vol. 12, No. 4, pp. 639-656, 1991.
[57] Jiang, L. Y., “Fast detection of multi-circle with randomized Hough transform,” Optoelectronics Letters, Vol. 5, No. 1, pp. 0397-0400, 2009.
[58] Zhang, M. and Cao, H., “A new method of circle’s center and radius detection in image processing,” Proceedings of the IEEE International Conference on Automation and Logistics, ICAL 2008, Qingdao, China, No. 4636537, pp. 2239-2242, 2008.
 
[59] Walpole, R. E., Myers, R. H., Myers, S. L. and Ye, K., Probability & Statistics for Engineers & Scientists, Eighth Edition, Pearson Prentice Hall, 2007.
[60] Chung, K. L. and Huang, Y. H., “A pruning-and-voting strategy to speed up the detection for lines, circles, and ellipses,” Journal of Information Science and Engineering, Vol. 24, pp. 503-520, 2008.
[61] Chung, K. L. and Huang, Y. H., “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, pp. 132-149, 2007.
[62] Chiu, S. H. and Liaw, J. J., “A proposed circle/circular arc detection method using the modified randomized Hough transform,” Journal of the Chinese Institute of Engineers, Vol. 29, pp. 533-538, 2006.
[63] Silveira, M., “An algorithm for the detection of multiple concentric circles,” in Lecture Notes in Computer Science (LNCS), pp. 271-278, 2005.
[64] Ho, C. T. and Chen, L. H., “A fast ellipse/circle detector using geometric symmetry,” Pattern Recognition, Vol. 28, pp. 117-124, 1995.
 
[65] Shang, F., Liu, J., Zhang, X. and Tian, D., “An improved circle detection method based on right triangles inscribed in a circle,” 2009 World Congress on Computer Science and Information Engineering, CSIE 2009 6, Los Angeles, CA, No. 5170725, pp. 382-387, 2009.
[66] Shang, F., Wang, F., Tian, D. and Zhao, Z., “A method for circle detection based on right triangles inscribed in a circle,” Acta Optica Sinica, pp. 739-743, 2009.
[67] Zhang, X. and Zhu, L., “Alleviating the computational load of the probabilistic algorithms for circles detection using the connectivity represented by graph,” Mach. Vision. Appl. (article in press), pp. 1-12, 2010.
[68] Torii, A. and Imiya, A., “The randomized-Hough-transform-based method for great-circle detection on sphere,” Pattern Recognition Letters, Vol. 28, pp. 1186-1192, 2007.
[69] Goulermas, J. Y. and Liatsis, P., “Incorporating gradient estimations in a circle-finding probabilistic Hough transform,” Pattern Analysis and Applications, Vol. 2, pp. 239-259, 1999.
[70] Kalviainen, H., and Hirvonen, P., “An extension to the randomized Hough transform exploiting connectivity,” Pattern Recognition Letters, Vol. 18, pp. 77-85, 1997.
[71] Sreecholpech, C. and Thainimit S., “A Robust Model-based Iris Segmentation,” 2009 International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS 2009), No. 5383767, pp. 599-602, 2009.
[72] Atiquzzaman M., “Coarse-to-Fine Search Technique to Detect Circles in Images,” The International Journal of Advanced Manufacturing Technology, Vol. 15, No. 2, pp. 96-102, 1999.