||A Statistical Approach to Boundary-based Corner Detection
||Department of Computer Science and Information Engineering
||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.
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
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  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
|| 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.
 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.
 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.
 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.
 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.
 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.
 X. Chang, L. Gao, and Y. Li, “Corner detection based on morphological disk element,” Proceedings of the American Control Conference, pp. 1994–1999, 2007.
 A. Rosenfeld and E. Johnston, “Angle Detection on Digital Curves,” IEEE Transactions on Computers, vol. c-22, no. 9, pp. 875–878, 1973.
 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.
 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.
 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.
 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.
 C. H. Yeh, “Wavelet-based corner detection using eigenvectors of covariance matrices,” Pattern Recognition Letters, vol.24, no.15, pp. 2797–2806, 2003.
 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.
 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.
 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.
 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.
 S. Segvic, “Detecting salient curvature features using the local control of the feature support,” Proceedings of the Mediterranean Electrotechnical Conference, pp. 61–65, 2002.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 D. F. Morrison, Multivariate Statistical Methods, 4th Ed., Brooks/Core Thomson Learning, Belmont, 2005.
 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.
 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.
 P. Cornic, “Another look at the dominant point detection of digital curves,” Pattern Recognition Letters, vol. 18, no. 1, pp. 13–25, 1997.
 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.
 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.
 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.
 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.
 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.
 R. V. Hogg and E. A. Tanis, Probability and Statistical Inference, 5th ed., Prentice Hall, New Jersey, 1997.
 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.
 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).
 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.
 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.
 A. Rosenfeld, “Digital straight line segments,” IEEE Transactions on Computers, vol. c-23, no. 12, pp. 1264–1269, 1974.