影像上的轉折點具有幾何轉換(如平移、旋轉、縮放…等)之不變性，在電腦視覺的研究領域，一直都是重要的辨識特徵。近年來，偵測邊界轉折點已被廣泛應用在多邊形逼近、曲線密合、自動光學檢測、影像切割、影像校正與形變、物體辨識、運動速寫等各方面。偵測邊界轉折點時，需先將影像主體自背景分離出來，接著在物體邊界上找出曲率變化明顯的轉折點位置。然而影像在數位化過程，因量化處理與雜訊干擾，往往造成邊界上的鋸齒現象，影響偵測邊界轉折點的成效。
本文提出一種能有效抵抗量化處理與雜訊干擾的邊界轉折點偵測方法。此演算法包含三個要件：運用共變數矩陣特徵值衡量邊界像素之曲率，藉由折線模型估計任意角度之曲率門檻值，以及依據鑑別力指數高低決定支援區間長度。實驗顯示，不論是處理乾淨的或者帶雜訊的影像，我們提出的演算法在偵測邊界轉折點的表現上均優於其他對照方法。此結果植基於我們同時改進了傳統作法在衡量曲率屬性與決定支援區間長度兩方面潛藏之問題。

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. Boundary-based 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 boundary-based 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. Boundary-based 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 oxalis-like 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 boundary-based 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% salt-and-pepper 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 high-accurate 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 multi-junctions 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 multi-corner 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. c-22, 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. c-24, no. 9, pp. 940–941, 1975.
[10]	T. H. Sun, C. C. Lo, P. S. Yu, and F. C. Tien, “Boundary-based corner detection using K-cosine,” 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, “Boundary-based corner detection using eigenvalues of covariance matrices,” Pattern Recognition Letters, vol.20, no.1, pp. 31–40, 1999.
[13]	C. H. Yeh, “Wavelet-based 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, “Non-parametric 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 chord-to-point distance accumulation technique,” IEEE Transactions on Multimedia, vol. 10, no. 6, pp. 1059-1072, 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 split-based 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 two-pass 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 rotation-invariant and non-referential 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, “Wavelet-based 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.11-12, 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 atlas-based 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, “Live-wire-based 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 Computer-Assisted Intervention, pp. 833–841, 2008.
[35]	Z. Su, Y. Wei, L. Xuesong, and C. Yazhu, “Integrated shape corresponding information by landmark sliding for non-rigid 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, “On-line 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 Multi-Conference: 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, re-sampling 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, “Motion-based 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 real-world 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 non-parametric 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, “Scale-based 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ñesta-Quereda, M. Buendía-Gomez, and M. Á. Sarti-Martí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 polynomials-preservation 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. c-23, no. 12, pp. 1264–1269, 1974.