臺灣博碩士論文加值系統

圖形偵測是影像分析、電腦視覺、及數位影像處理等研究中重要的課題，傳統的霍夫轉換已被廣泛應用於有雜訊環境的二維影像中，偵測和定位任意形狀的平面物件，如直線、圓形、橢圓形、多邊形等；雖然這些方法仍存在著一些缺點，需要繁複的計算與龐大的容量，更局限於單線條的偵測，不適於直接對具有寬度的帶狀圖形作處理，然而實際上大部分物件影像是具有寬度的，因此使用這些方法時，就得先對影像執行單線細化處理，取出圖形的邊緣來做偵測，偵測結果再還原至原圖執行後續處理。近年來，拜半導體技術進步之賜，處理器的運算速度與儲存容量增進了千、百萬倍，解決了傳統霍夫轉換法的部分問題。本研究首先提出以延伸霍夫轉換法為基礎，對具有寬度的帶狀圖形直接偵測的演算法，不必經由影像細化(或邊緣偵測)，以影像原圖直接輸入，執行霍夫轉換運算，所得結果亦毋須再執行圖形還原動作，偵測出之帶狀圖形的各點位置可直接運用於後續之圖形處理。論文中並以圓形帶、橢圓形帶、三角形帶及多邊形等圖形為例，說明與探討延伸霍夫演算法之應用。同時並利用物件形狀的幾何性質來減少霍夫空間的參數數量，可以明顯地提升偵測的速度與減少運算的儲存空間。

Feature extraction is an important task in image analysis, computer vision and digital image processing. The Hough Transform is an effective approach of simple curve detection in a binary image. However, the computational complexity and the size of the accumulator array increase poly nomially with the number of Hough parameters, and it is not suitable to use it directly to detect band shape objects in images. There are a large number of band shape objects exist in the actual scenes. In many applications, quick detection their position in the image accurately and effectively is required. A new method using extended Hough transform (EHT) for detecting thick pattern, called band pattern, is proposed in this dissertation, that uses a binary image as the direct input, requiring neither preprocessing steps of edge detection nor post-processing steps to recover the band in the original image. Thus, the useful position relationship existing among the pixels of a band pattern is kept, and certain costly post-processing steps to recover the bands in the original image are not required. Several experiments include recognitions of circular bands, ellipse bands, triangle bands, polygon, and general objects in an actual scene are given to show the feasibility and applicability of the proposed approach. Besides, we combined the geometric attributes of detecting objects to reduce the number of Hough parameters thus reduce the computation time and the amount of storage.

中文摘要 i
ABSTRACT ii
誌謝 iii
LIST OF CONTENTS iv
LIST OF TABLES vi
LIST OF FIGURES vii
Chapter 1 INTRODUCTION 1
1.1 Research Motivation 1
1.2 The Basic Hough Transform 2
1.3 Basic Curve Detection Methods Based on
Hough Transform 3
1.4 Limitations and Extensions 7
1.5 Overview of Proposed Approaches and Other
Auxiliary Methods Used 8
1.6 Dissertation Organization 15
Chapter 2 Circular Band Detection 17
2.1 A Review of CHT Method to Detect Circles 18
2.2 Proposed Method for Detecting Circular
Bands in Images 18
2.3 Algorithms 23
2.4 Experimental Results 29
2.5 Discussions and Summary 33
Chapter 3 Ellipse Band Detection 36
3.1 A Review of CHT Method to Detect Ellipse 37
3.2 Proposed Method for Detecting Multiple-
Ellipse Bands in Image 38
3.3 Algorithms 40
3.4 Experimental Results 52
3.5 Discussions and Summary 55
Chapter 4 Triangle band Detection 56
4.1 A Review of CHT Method to Detect Triangular
56
4.2 Proposed Method for Detecting Multiple-
Triangle bands in Image 58
4.3 Algorithms 59
4.4 Experimental Results 70
4.5 Discussions and Summary 73
Chapter 5 Regular Polygon Detection 75
5.1 A Review of CHT Method to Detect Regular
Polygon 75
5.2 Proposed Method for Detecting Regular
Polygon in Image 76
5.3 Algorithms 78
5.4 Experimental Results 84
5.5 Discussions and Summary 87
Chapter 6 Conclusions 90
6.1 Conclusion of experimental results 90
6.2 Comparison of Approach Algorithms 90
6.3 Extension of Application 91
6.4 Further Works 92
References 94
Appendix
A Derivation of the circular band formula 98
B Derivation of the ellipse band formula 99
Notation 101

Alberto, B., Pietro C. and Paolo, M., 2007. Real time road signs recognition. Proceedings of the 2007 IEEE Intelligent Vehicles Symposium, Turkey, 981-986.
Alim, F., Messaoudi, K., Seddiki, S. and Kerdjidj, O., 2012. Modified circular Hough transform using FPGA. 24th International Conference on Microelectronics, 1-4.
Assidig, A.A., Khalifa, O.O., Islam, M.R. and Khan, S., 2008. Real time lane detection for autonomous vehicles, International Conference on Computer and Communication Engineering (ICCCE), 82-88.
Ballard, D.H., 1981. Generalizing the Hough transform to detect arbitrary shapes. Pattern Recognition, 13(2), 111–122
Barnes, N., Gareth, L. and David, S., 2010. The regular polygon detector. Pattern Recognition. 43, 592–602.
Borkar, A.M., Hayes, H. and Smith, M.T., 2012. A novel lane detection system with efficient ground truth generation. IEEE Trans. on Intel. Trans. Sys., 13(1), 365-374.
Canny,1986, A computational approach to edge detection, IEEE Trans on Pattern Anal and Mach Intell, Vol 8, No. 6, pp. 679-698.
Chiu, S.H., Liaw, J.J. and Lin, K.H., 2010. A fast randomized Hough transform for circle/circular arc recognition. Int. J. Patt. Recogn. Artif. Intel., 24, 457.
Cuevas, E., Wario, F. and Osuna-Enciso, V., 2012. Fast algorithm for multiple-circle detection on images using learning automata. IET Image Processing, 6 (8), 1124-1135.
Cuevas, E., Wario, F. and Zaldivar, D., 2012. Circle detection on images using learning automata. IET Computer Vision, 6 (2), 121-132.
Duda, P.V.C., and Hart, P.E., 1972. Use of the Hough transform to detect lines and curves in pictures. Communications of the Association Computing Machinery, 15(1), 11-15. ITS U.S.
Davies, E. R., 1988, A modified Hough scheme for general circle location. Pattern Recognition Letters, Vol 7, pp. 37-43.
Falim, F., Messaoudi, K., Seddiki, S., and Kerdjidj, O., 2012. Modified circular Hough transform using FPGA, 24th International Conference onMicroelectronics, 1–4.
Gates, J.W., Haseyama, M. and Kitajima, H., 2000. Real-time polygon extraction from complex images. Circuits and Systems, Proceeding ISCAS 2000 Geneva. The 2000 IEEE Int’l Symp. on, 5, 309–312.
Gopalan, R., Hong, T., Shneier, M. and Chellappa, R., 2012. A learning approach towards detection and tracking of lane markings. IEEE Trans. on Intel. Trans. Sys., 13(3), 1088–1098.
Guil, N. and Zapata, L. 1997. Lower order circle and ellipse Hough transform. Pattern Recognition 30(10), 1729-1744.
He, Jiang-Ping, Ma, Yan, “Triangle detection based on windowed Hough transform”, Department of Information Engineering, Lanzhou University of Finance and Economics, Lanzhou 730020, China.
Hilario G.M., and Francisco, L.F., Saturnino, M.B., Sergio, L.A., and Pedro, G.J., 2007. Road-sign detection and recognition based on SVM, IEEE Trans. on Intelligent transportation systems, 8, No. 2.
Hough, P.V.C., 1962. Method and means for recognizing complex pattern. US Patent 3069654.
Illingworth, J. and Kittler, J. 1988. A survey of the Hough transform. Computer Vision, Graphics, and Image Processing, 44, 87-116.
Khan, M. Taha, 2008, “Real-Time Recognition System for Traffic Signs”, Master Thesis, Dalarna University, Sweden, U. K..
Kimme, C., Ballard, D. and Sklansky, J., 1975. Finding circles by an array of accumulators. Comm. Mach. 18, 120-122.
Leavers, V.F., 1993. Which Hough transform? Computer Vision Graphics and Image Understanding: Image Processing, 58 (2), 50-64.
Liu, H. M. and Wang, Z. H., 2011, “Detection of Arbitrary Triangle,” in: Proceedings of the 4th International Congress on Image and Signal Processing.
Lo, R.C. and Tsai, W.H., 1995. Gray-scale Hough transform for thick line detection in gray-scale images. Pattern Recognition 28, 647-661.
Lo, R.C., 1996. Extensions of Hough transform and their applications. Doctor dissertation, National Chiao-Tung University.
Lo, R. C. and Hsu, H. C., 2016. A circular band extraction method based on extended Hough transform. Int. J. Patt. Recogn. Artif. Intell.
Lou, D., Smart,P., and Macleod, J. E.S., 1995. Circular Hough transform for roundness measurement of objects. Pattern Recognition 28, 1745-1749.
Marzotto, R., Zoratti, P., Bagni, D., Colombari, A. and Murino, V., 2010. A real-time versatile roadway path extraction and tracking on an FPGA platform. Computer Vision and Image Understanding, 114(11), 1164–1179.
McLaughlin, R.A. 1998. Randomized Hough transform: Improved ellipse detection with comparison. Pattern Recognition Letters 19, 299-305.
Milanfar, P., Karl, W.C. and Willsky, A.S., 1995. Reconstructing polygons from moments with connections to array processing. IEEE Trans. Signal Process. 43 (2), 432-443.
Milanfar, P., 1995. On the Hough transform of a polygon. Pattern Recognition Lett. 17, 209-210.
Muammar, H.K. and Nixon, M. 1991. Tri-stage Hough transform for multiple ellipse extraction. IEE proceeding-e 138(1): 27-35.
Nick, B., Robert, B. and Naoki, S. 1999. A method to detect and characterize ellipses using the Hough transform. IEEE Transactions on Pattern Analysis and Machine Intelligence. 21, No. 7.
Pei, S.C. and Horng, J.H., 1995. Circular arc detection based on Hough transform. Pattern Recognition letters 16, 615-625.
Privitera, C. M., Stark, L. W., 2000, “Algorithm for defining visual regions-of-interest: Comparison with eye fixations,” IEEE Trans. Pattern Anal. Machine Intell.,Vol: 22, no. 9, pp. 970-982.
Rosenfeld, A. and Wei, I., 1995. A convex polygon is determined by its Hough transform. Pattern Recognition Lett. 16, 305-306.
Sewisy, A.A. and Leberl, F. 2001. Detection ellipse by finding lines of symmetry in the images via a Hough transform applied to straight lines. Image and Vision Computing 19, 857- 866.
Sheng, H., Chen, Q. G. and Shang, M., 2012. Circular road sign detection and recognition based on Hough transform. In: Proc. IEEE Conf. Image and Signal Processing (CISP), 1214-1218.
Shi, J., Xiao, Z.H. and Chang, Q., 2009. An algorithm for recognizing geometrical shapes automatically based on tunable filter. Journal of North University of China (Natural Science Edition), 30(5), 467-471.
Shaw, D., and Barnes, N., 2004. Regular polygon detection as an interest point operator for slam. In Proc. ACRA’04, 2004. www.araa.asn.au/acra/acra2004.
Siddharth, M. and David, W. P., 2007. Matching flexible polygons to fields of corners extracted from images. ICIAR 2007, Lecture Notes in Computer Science, 4633, 447–459.
TahaKhan, M., 2008. Real-time recognition system for traffic signs. Master Thesis, Dalarna University, Sweden, U. K.
Torii, A. and Imiya, A., 2007. The randomized-Hough -transform -based method for great-circle detection on sphere. Pattern Recognition Letters, 28, 1186-1192.
Wu, B.F., Lin, C.T. and Chen, Y.L., 2009. Dynamic calibration and occlusion handling algorithms for lane tracking. IEEE Trans. on Industrial Electronics, 56(5).
Wu, S. and Liu, X.J., 2012. Parallelization research of circle detection based on Hough transform. International Journal of Computer Science Issues (IJCSI), 9(3), 481-486.
Xiang, Z., Xiaodong, K. and Guihua, Z. 2008. A new method of ellipse detection based on Hough transform. Electronic Engineering, Shanghai Jiao tong University, Shanghai 200030.
Yip, R.K.K., Tam, P.K.S. and Leung, D.N.K., 1992. Modification of Hough transform for circles and ellipses detection using a 2-dimensional array. Pattern Recognition, 25, 1007-1022.
Zuo, J.Y. and Schmid, N.A., 2010. On a methodology for robust segmentation of non-ideal iris images. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 40, 703-718.