
系統識別號 
U00020508200902282200 
中文論文名稱

基於統計分析之邊界轉折點偵測方法 
英文論文名稱

A Statistical Approach to Boundarybased Corner Detection 
校院名稱 
淡江大學 
系所名稱(中) 
資訊工程學系博士班 
系所名稱(英) 
Department of Computer Science and Information Engineering 
學年度 
97 
學期 
2 
出版年 
98 
研究生中文姓名 
陳俊文 
研究生英文姓名 
ChunWen Chen 
電子信箱 
g8190387@tkgis.tku.edu.tw 
學號 
688190387 
學位類別 
博士 
語文別 
英文 
口試日期 
20090622 
論文頁數 
83頁 
口試委員 
指導教授洪文斌 委員楊鎮華 委員陳伯榮 委員楊接期 委員郭經華 委員洪文斌

中文關鍵字 
轉折點偵測
曲率測量
最佳化方法
門檻值估計

英文關鍵字 
corner detection
curvature measure
optimization method
threshold estimation

學科別分類 
學科別＞應用科學＞資訊工程

中文摘要 
影像上的轉折點具有幾何轉換(如平移、旋轉、縮放…等)之不變性，在電腦視覺的研究領域，一直都是重要的辨識特徵。近年來，偵測邊界轉折點已被廣泛應用在多邊形逼近、曲線密合、自動光學檢測、影像切割、影像校正與形變、物體辨識、運動速寫等各方面。偵測邊界轉折點時，需先將影像主體自背景分離出來，接著在物體邊界上找出曲率變化明顯的轉折點位置。然而影像在數位化過程，因量化處理與雜訊干擾，往往造成邊界上的鋸齒現象，影響偵測邊界轉折點的成效。
本文提出一種能有效抵抗量化處理與雜訊干擾的邊界轉折點偵測方法。此演算法包含三個要件：運用共變數矩陣特徵值衡量邊界像素之曲率，藉由折線模型估計任意角度之曲率門檻值，以及依據鑑別力指數高低決定支援區間長度。實驗顯示，不論是處理乾淨的或者帶雜訊的影像，我們提出的演算法在偵測邊界轉折點的表現上均優於其他對照方法。此結果植基於我們同時改進了傳統作法在衡量曲率屬性與決定支援區間長度兩方面潛藏之問題。 
英文摘要 
Corners have been one of the most important features in computer vision since they are invariant to geometric transformations, such as translation, rotation and scaling. Boundarybased corner detectors, segmenting objects from an image first and then locating the discontinuities on the object boundaries, have been widely applied to polygonal approximation, spline curve fitting, automated visual inspection, image segmentation, image registration, shape morphing, handwriting/environment/object recognition, motion sketch, etc. The accuracy of corner detection on boundaries is primarily influenced by quantization and noises.
In this thesis, we propose a robust boundarybased corner detection algorithm for diverse images. The algorithm is composed of three components: a new measure of significance based on the eigenvalues of covariance matrices, threshold estimation of the measure of significance of any angle, and an optimization procedure based on a discriminant criterion for determining the length of region of support. The experimental results show that our algorithm outperforms other methods, even in the noisy samples. These robust results are due to not only the reliable measure of significance but also the discriminating optimization procedure of our algorithm. 
論文目次 
CONTENTS
List of Figures V
List of Tables VII
Chapter 1 Introduction 1
1.1. Boundarybased corner detection 1
1.2. General corner detection procedure 2
Chapter 2 New measure of significance 5
2.1. Measures of significance 6
2.1.1. Tsai et al.’s observations on eigenvalues 7
2.1.2. Exploring properties of eigenvalues 9
2.1.3. Revealing Tsai et al.’s mistake 16
2.2. Revision of using eigenvalues 18
2.3. Experiments 22
2.3.1. Artificial samples 23
2.3.2. Real objects 28
Chapter 3 Optimizing region of support 31
3.1. Adaptive region of support 32
3.2. Global perspective optimization 35
3.2.1. Measure of separability 36
3.2.2. Optimization procedure 37
3.2.3. Threshold estimation 38
3.3. Experiments 41
3.3.1. Illustrative example 41
3.3.2. Validity analysis 44
Chapter 4 Performance analysis 54
4.1. Robustness 54
4.2. Time complexity 61
Chapter 5 Conclusion 64
References 67
Appendix Some proofs 74
A.1. Eigenvalues and projected variances 74
A.2. The eigenvalues are invariant to translations and rotations 75
A.3. “f” is invariant to linear transformation of the curvature estimates 80
A.4. The lower bound of region of support 82
List of Figures
Fig. 1 Three different types of digitized curves 8
Fig. 2 Angle with symmetric axis y = x 10
Fig. 3 λL and λS of straight lines with different θ 11
Fig. 4 λL and λS of circular arcs with different r 11
Fig. 5 λL and λS of angles of different φ with symmetric axis y = x (Fig. 2) 12
Fig. 6 λL and λS of angles of different φ with symmetric axis x = 0 (Fig. 1(c)) 13
Fig. 7 λL and λS of angles of different φ with symmetric axis y = (tan 26.5°) x 16
Fig. 8 Small eigenvalues of a cone shape 17
Fig. 9 Corner detection by naive corner indices λm 20
Fig. 10 λM and λS of angles with different φ which are symmetric at y = x 21
Fig. 11 Corner detection by modified corner indices λM 22
Fig. 12 An oxalislike object of size 240 × 240 pixels 24
Fig. 13 Detected corners in Tsai et al.’s method using λS 26
Fig. 14 Results of Tsai et al.’s method of Fig. 12(a) using λS 27
Fig. 15 Results of our modified method of Fig. 12(a) using λM 28
Fig. 16 Reproductions of Tsai et al.’s four real objects 29
Fig. 17 Detected corners of Fig. 16 using λM 29
Fig. 18 Typical preprocessing of boundarybased corner detection in our study 34
Fig. 19 The included angle model for estimating threshold 39
Fig. 20 Detected corners of boundaries in Fig. 18 (with 0%, 10%, 20%, 30%, and 40% noise) for k = 12 41
Fig. 21 f(k) values of boundaries in Fig. 18 43
Fig. 22 Detected corners of boundaries in Fig. 18 (with 0%, 10%, 20%, 30%, and 40% noise) for optimum k 43
Fig. 23 Boundaries of four Chinese characters with (a) 0% and (b) 20% noise 45
Fig. 24 f(k) values of boundaries in Fig. 23 46
Fig. 25 Test boundaries and the assigned corners 55
Fig. 26 Boundaries with 20% saltandpepper noise 55
List of Tables
Table 1 The eigenvalues λS for circles and angles 9
Table 2 The calculated λS values in our experiment 18
Table 3 Comparison of corner detection results 25
Table 4 Length of region of support of Fig. 18 35
Table 5 Optimum length of region of support of Fig. 18 43
Table 6 Comparison of detected corners of Figs. 20 and 22 44
Table 7 Results of corner detection of Fig. 23 47
Table 8 Detected corners of boundaries in Fig. 23 49
Table 9 Results of corner detection by different measures of significance 56
Table 10 Results of corner detection by online testing [58] 57
Table 11 The results of detected corners of Fig. 25 and Fig. 26 58
Table 12 Numbers of operations for the optimization procedure 62

參考文獻 
[1] H. H. Oh and S. I. Chien, “Exact corner location using attentional generalized symmetry transform,” Pattern Recognition Letters, vol.23, no.11, pp. 1361–1372, 2002.
[2] G. Olague, B. Hernandez, and E. Dunn, “Hybrid evolutionary ridge regression approach for highaccurate corner extraction,” Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol.1, pp. 744–749, 2003.
[3] G. Tolt, “A fuzzy approach for detecting multijunctions in edgeness images,” Proceedings of the Fourth IASTED International Conference on Visualization, Imaging, and Image Processing, pp. 420–424, 2004.
[4] G. Olague and B. Hernandez, “A new accurate and flexible model based multicorner detector for measurement and recognition,” Pattern Recognition Letters, vol.26, no.1, pp. 27–41, 2005.
[5] F. Y. Shih, C. F. Chuang, and V. Gaddipati, “A modified regulated morphological corner detector,” Pattern Recognition Letters, vol.26, no.7, pp. 931–937, 2005.
[6] A. Sobania and J. P. O. Evans, “Morphological corner detector using paired triangular structuring elements,” Pattern Recognition, vol. 38, no. 7, pp. 1087–1098, 2005.
[7] X. Chang, L. Gao, and Y. Li, “Corner detection based on morphological disk element,” Proceedings of the American Control Conference, pp. 1994–1999, 2007.
[8] A. Rosenfeld and E. Johnston, “Angle Detection on Digital Curves,” IEEE Transactions on Computers, vol. c22, no. 9, pp. 875–878, 1973.
[9] A. Rosenfeld and J. S. Weszka, “An Improved Method of Angle Detection on Digital Curves,” IEEE Transactions on Computers, vol. c24, no. 9, pp. 940–941, 1975.
[10] T. H. Sun, C. C. Lo, P. S. Yu, and F. C. Tien, “Boundarybased corner detection using Kcosine,” Proceedings of IEEE International Conference on Systems, Man and Cybernetics, pp. 1106–1111, 2007.
[11] C. H. Teh and R. T. Chin, “On the Detection of Dominant Points on Digital Curves,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 8, pp. 859–872, 1989.
[12] D. M. Tsai, H. T. Hou, and H. J. Su, “Boundarybased corner detection using eigenvalues of covariance matrices,” Pattern Recognition Letters, vol.20, no.1, pp. 31–40, 1999.
[13] C. H. Yeh, “Waveletbased corner detection using eigenvectors of covariance matrices,” Pattern Recognition Letters, vol.24, no.15, pp. 2797–2806, 2003.
[14] J. F. Khan, K. Barner, and R. Adhami, “Feature point detection utilizing the empirical mode decomposition,” Eurasip Journal on Advances in Signal Processing, no. 287061, 2008.
[15] L. Xu, D. Yang, M. Hong, X. Zhang, and J. Huang, “Corner detection based on determinants of covariance matrices of planar curve,” Chinese Journal of Scientific Instrument, vol. 30, no. 1, pp. 91–95, 2009.
[16] D. S. Guru, R. Dinesh, and P. Nagabhushan, “Boundary based corner detection and localization using new ‘cornerity’ index: a robust approach,” Proceedings of the 1st Canadian Conference on Computer and Robot Vision, pp. 417–423, 2004.
[17] D. Chetverikov and Z. Szabo, “A Simple and Efficient Algorithm for Detection of High Curvature Points in Planar Curves,” Proceedings of the 23rd Workshop of the Austrian Pattern Recognition Group, pp. 175–184, 1999.
[18] S. Segvic, “Detecting salient curvature features using the local control of the feature support,” Proceedings of the Mediterranean Electrotechnical Conference, pp. 61–65, 2002.
[19] D. S. Guru and R. Dinesh, “Nonparametric adaptive region of support useful for corner detection: a novel approach,” Pattern Recognition, vol.37, no.1, pp. 165–168, 2004.
[20] M. Sarfraz, A. Rasheed, and Z. Muzaffar, “A novel linear time corner detection algorithm,” Proceedings of the Conference on Computer Graphics, Imaging and Vision: New Trends, pp. 191–196, 2005.
[21] M. Awrangjeb and G. Lu, “Robust image corner detection based on the chordtopoint distance accumulation technique,” IEEE Transactions on Multimedia, vol. 10, no. 6, pp. 10591072, 2008.
[22] X. Zhang, H. Wang, M. Hong, L. Xu, D. Yang, and B. C. Lovell, “Robust image corner detection based on scale evolution difference of planar curves,” Pattern Recognition Letters, vol. 30, no. 4, pp. 449–455, 2009.
[23] R. Dinesh, S. S. Damle, and D. S. Guru, “A splitbased method for polygonal approximation of shape curves,” Lecture Notes in Computer Science, vol. 3776, pp. 382–387, 2005.
[24] K. L. Chung, P. H. Liao, and J. M. Chang, “Novel efficient twopass algorithm for closed polygonal approximation based on LISE and curvature constraint criteria,” Journal of Visual Communication and Image Representation, vol. 19, no. 4, pp. 219–230, 2008.
[25] M. Sarfraz, M. R. Asim, and A. Masood, “Capturing outlines using cubic Bezier curves,” Proceedings of the 2004 International Conference on Information and Communication Technologies: From Theory to Applications, pp. 539–540, 2004.
[26] F. Yahya, J. M. Ali, A. A. Majid, and A. Ibrahim, “An automatic generation of G^1 curve fitting of arabic characters,” Proceedings of the Third International Conference on Computer Graphics, Imaging and Visualization: Techniques and Applications, pp. 542–547, 2006.
[27] C. H. Yeh and D. M. Tsai, “A rotationinvariant and nonreferential approach for ball grid array (BGA) substrate conducting path inspection,” International Journal of Advanced Manufacturing Technology, vol.17, no.6, pp. 412–424, 2001.
[28] C. H. Yeh and D. M. Tsai, “Waveletbased approach for ball grid array (BGA) substrate conduct paths inspection,” International Journal of Production Research, vol.39, no.18, pp. 4281–4299, 2001.
[29] C. H. Yeh, T. C. Shen, and F. C. Wu, “A case study: Passive component inspection using a 1D wavelet transform,” International Journal of Advanced Manufacturing Technology, vol.22, no.1112, pp. 899–910, 2003.
[30] F. C. Tien and C. H. Yeh, “Using eigenvalues of covariance matrices for automated visual inspection of microdrills,” International Journal of Advanced Manufacturing Technology, vol.26, no.7–8, pp. 741–749, 2005.
[31] J. H. Sossa Azuela, G. Guzman Lugo, and R. Sotelo Rangel, “Counting the number of blobs in an image,” Proceedings of the 2001 IEEE International Conference on Image Processing, vol.1, pp. 1086–1089, 2001.
[32] M. Färber, J. Ehrhardt, and H. Handels, “Automatic atlasbased contour extraction of anatomical structures in medical images,” International Congress Series, vol. 1281, pp. 272–277, 2005.
[33] M. Färber, J. Ehrhardt, and H. Handels, “Livewirebased segmentation using similarities between corresponding image structures,” Computerized Medical Imaging and Graphics, vol. 31, no. 7, pp. 549–560, 2007.
[34] L. Yang, O. Tuzel, P. Meer, and D. J. Foran, “Automatic image analysis of histopathology specimens using concave vertex graph,” Proceedings of the 11th International Conference on Medical Image Computing and ComputerAssisted Intervention, pp. 833–841, 2008.
[35] Z. Su, Y. Wei, L. Xuesong, and C. Yazhu, “Integrated shape corresponding information by landmark sliding for nonrigid registration between CT and ultrasound images,” Proceedings of the 3rd International Conference on Intelligent System and Knowledge Engineering, pp. 1130–1135, 2008.
[36] W. Yang and J. Feng, “2D shape morphing via automatic feature matching and hierarchical interpolation,” Computers and Graphics, vol. 33, no. 3, pp. 414–423, 2009.
[37] Y. Ma and G. Leedham, “Online recognition of handwritten Renqun shorthand for fast mobile Chinese text entry,” Pattern Recognition Letters, vol. 28, no. 7, pp. 873–883, 2007.
[38] H. Hile and G. Borriello, “Positioning and orientation in indoor environments using camera phones,” IEEE Computer Graphics and Applications, vol. 28, no. 4, pp. 32–39, 2008.
[39] T. H. Sun and F. C. Tien, “Invariant object recognition using eigenvalues of covariance matrices and autocorrelation,” Proceedings of the 25th IASTED International MultiConference: Artificial Intelligence and Applications, pp. 47–52, 2007.
[40] T. H. Sun, C. S. Liu, and F. C. Tien, “Invariant 2D object recognition using eigenvalues of covariance matrices, resampling and autocorrelation,” Expert Systems with Applications, vol. 35, no. 4, pp. 1966–1977, 2008.
[41] T. H. Sun, H. C. Horng, C. S. Liu, and F. C. Tien, “Invariant 2D object recognition using KRA and GRA,” Expert Systems with Applications, vol. 36, no. 9, pp. 11517–11527, 2009.
[42] M. Thorne, D. Burke, and M. Van De Panne, “Motion doodles: An interface for sketching character motion,” ACM Transactions on Graphics, vol. 23, no. 3, pp. 424–431, 2004.
[43] J. W. Hsieh, S. L. Yu, and Y. S. Chen, “Motionbased video retrieval by trajectory matching,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 3, pp. 396–409, 2006.
[44] Y. Kitamura, R. Rong, Y. Hirano, K. Asai, and F. Kishino, “Video agent: Interactive autonomous agents generated from realworld creatures,” Proceedings of the ACM Symposium on Virtual Reality Software and Technology, pp. 30–38, 2008.
[45] D. S. Guru, B. H. Shekar, and P. Nagabhushan, “A simple and robust line detection algorithm based on small eigenvalue analysis,” Pattern Recognition Letters, vol.25, no.1, pp. 1–13, 2004.
[46] C. Hu, C. Tanaka, R. Okai, and T. Ohtani, “Automatic determination of fiber orientation on OSB surface using line detection method based on small eigenvalue analysis,” Annals of Forest Science, vol.62, no.5, pp. 385–390, 2005.
[47] D. F. Morrison, Multivariate Statistical Methods, 4th Ed., Brooks/Core Thomson Learning, Belmont, 2005.
[48] R. Dinesh and D. S. Guru, “Efficient nonparametric corner detection: an approach based on small eigenvalue,” Proceedings of the 4th Canadian Conference on Computer and Robot Vision, pp. 250–257, 2007.
[49] A. Rattarangsi and R. T. Chin, “Scalebased detection of corners of planar curves,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14, no.4, pp. 430–449, 1992.
[50] P. Cornic, “Another look at the dominant point detection of digital curves,” Pattern Recognition Letters, vol. 18, no. 1, pp. 13–25, 1997.
[51] J. M. IñestaQuereda, M. BuendíaGomez, and M. Á. SartiMartínez, “Reliable polygonal approximations of imaged real objects through dominant point detection,” Pattern Recognition, vol. 31, no. 6, pp. 685–697, 1998.
[52] M. Marji and P. Siy, “A new algorithm for dominant points detection and polygonization of digital curves,” Pattern Recognition, vol. 36, no. 10, pp. 2239–2251, 2003.
[53] W. Qian and X. Lin, “Curvature calculation and corners extraction of image contour,” Proceedings of the 2007 IEEE International Conference on Mechatronics and Automation, ICMA 2007, pp. 1219–1223, 2007.
[54] T. Kubota, “A shape representation with elastic quadratic polynomialspreservation of high curvature points under noisy conditions,” International Journal of Computer Vision, vol. 82, no. 2, pp. 133–155, 2009.
[55] C. Di Ruberto and A. Morgera, “A new iterative approach for dominant points extraction in planar curves,” WSEAS Transactions on Computers, vol. 8, no. 3, pp. 482–493, 2009.
[56] R. V. Hogg and E. A. Tanis, Probability and Statistical Inference, 5th ed., Prentice Hall, New Jersey, 1997.
[57] A. Dutta, A. Kar, and B. N. Chatterji, “Corner detection algorithms for digital images in last three decades,” IETE Technical Review, vol. 25, no. 3, pp. 123–133, 2008.
[58] D. Chetverikov and Z. Szabo, “Detection of High Curvature Points in Planar Curves,” http://visual.ipan.sztaki.hu/corner/cornerweb.html (visited, 2009/02/15).
[59] C. Xingzhi, G. Liqun, and W. Jianhua, “Corner detection based on convex corner point element,” Proceedings of the 2007 IEEE International Conference on Control and Automation, pp. 182–186, 2007.
[60] H. Liu, L. J. Latecki, and W. Liu, “A unified curvature definition for regular, polygonal, and digital planar curves,” International Journal of Computer Vision, vol. 80, no. 1, pp. 104–124, 2008.
[61] A. Rosenfeld, “Digital straight line segments,” IEEE Transactions on Computers, vol. c23, no. 12, pp. 1264–1269, 1974.

論文使用權限 
同意紙本無償授權給館內讀者為學術之目的重製使用，於20090813公開。同意授權瀏覽/列印電子全文服務，於20090813起公開。 


