Robust image corner detection based on scale evolution difference of planar curves

doi:10.1016/j.patrec.2008.11.002

Pattern Recognition Letters

Volume 30, Issue 4, 1 March 2009, Pages 449-455

https://doi.org/10.1016/j.patrec.2008.11.002 Get rights and content

Abstract

In this paper, a new corner detector is proposed based on evolution difference of scale pace, which can well reflect the change of the domination feature between the evolved curves. In Gaussian scale space we use Difference of Gaussian (DoG) to represent these scale evolution differences of planar curves and the response function of the corners is defined as the norm of DoG characterizing the scale evolution differences. The proposed DoG detector not only employs both the low scale and the high one for detecting the candidate corners but also assures the lowest computational complexity among the existing boundary-based detectors. Finally, based on ACU and Error Index criteria the comprehensive performance evaluation of the proposed detector is performed and the results demonstrate that the present detector allows very strong response for corner position and possesses a better detection and localization performance and robustness against noise.

Introduction

Corners in images represent much useful information and they play an important role in describing object features for recognition and identification. Applications that rely on corners include scene analysis, stereo matching, robot navigation, stitching of panoramic photographs and object tracking, among many others. For this reason, considerable work has been performed on corner detection and many algorithms for detecting the corners have been developed in recent years. These algorithms may be divided into two main groups. The first group contains the algorithms that work directly with the values of brightness of images (without segmenting the image in advance), such as Moravec et al., 1977, Harris et al., 1987, Dreschler and Nagel, 1981, Kitchen and Rosenfeld, 1982, Fang and Huang, 1982, Smith and Brady, 1994, Chen et al., 1995, Cheol Bae et al., 2002 etc. detectors. The other group includes the algorithms that extract the boundary first and analyze its shape afterwards. The algorithm we propose falls into this category. In the following, we will briefly describe the main approaches that appeared in the history of boundary-based detectors.

Among all boundary-based detectors Curvature Scale Space (CSS) is one of the most efficient techniques for corner detection and has been used in several corner detectors (Rattarangsi and Chin, 1992, Mokhtarian and Suomela, 1998, Mokhtarian and Suomela, 2001, Mohanna and Mokhtarian, 2001, He and Yung, 2004, Zhang et al., 2007). The main reason is that CSS has very good evolution similarity for the evolved planar curves. For example, as the scale is increased, the noise is smoothed away and the effect of the noise on the domination feature such as the curvature is reduced. However, as the contour evolves, the actual locations of the domination points change. Tracking from high to low scale is necessary to assure that the corner detection is not affected by the noise and the localization of the corners is good. But, this not only increases computing load but also results in other problems. For instance, as the contour evolves, some weak domination points may disappear so that there is difficulty in choosing an appropriate scale for assuring the true corners can be detected. On the other hand, in CSS methods the high order derivative, which is sensitive to the noise, is required for calculating curvature. In order to avoid choosing an appropriate scale due to the single scale detection, Zhang et al. (2007) suggested a scale product function defined as the multiplication of the curvatures of the contour at scales in framework of CSS, and corners were constructed as the local maxima beyond threshold. Although multiscale product can combine several scale information for localizing the corners it also increases computing load. Another popular method is based on wavelet transform of contour orientation (Lee et al., 1995, Quddus and Gabbouj, 2002, Gao et al., 2007) or eigenvectors (Yeh, 2003) of covariance matrices that denote tangent orientation of the planar curves, but there exists some drawbacks such as high false alarm rate besides the difficulty in choosing a proper scale. In fact, since their wavelet functions are chosen as B-Spline ones wavelet transform of contour orientation is essentially equivalent to the second order derivative of the smoothed curves (Lee et al., 1995, Quddus and Gabbouj, 2002, Gao et al., 2007, Yeh, 2003), which is very sensitive to the noise. In Tsai et al. (1999) suggested a good measure for corner response by using the eigenvalues of the covariance Matrices of boundary coordinate points over a small region of support due to the fact that the smaller eigenvalue of covariance matrix reflected shape information of contour and the eigenvalues of the matrix could be used to extract the shape information. Its localization is good and the derivative of planar curves is not required, but it is very difficult to determine an appropriate width of support of region (ROS) for different type images while time complexity of eigenvalues is high. The major reason is that the smaller ROS is, the more sensitive to noise the detector is; the larger ROS is, the higher false alarm or missed rate the adjacent corners results in. Besides the typical boundary-based corner detectors discussed the others are referred to reference reviews of literatures (Tsai, 1997, Masood and Sarfraz, in press, Sobania and Evans, 2005, Arrebola and Sandoval, 2005, Guru and Dinesh, 2004). Based on the previous discussion we have found that the existing boundary-based detectors had considered the evolution similarities of scale space, thus the only single scale used for detecting candidate corners is inevitable and the proper one is difficultly determined.

On the contrary, little attention has been paid to the Evolution Difference between the evolved planar curves. In this paper, we have found that among the evolved planar curves there is another feature, which is referred to as evolution difference between the evolved versions. That is, the changes of the evolved curves have distinctive difference between corner positions and non-corner positions. The change in neighborhood of corner points is sharp whereas the change in neighborhood of non-corner positions is weak. Hence, we will employ these intrinsic evolution differences for presenting a new corner detection method, which utilizes both the low scale and the high one for determining the candidate corners. The contributions of this paper are as follows:

•
We illustrate the motivation of the proposed algorithm by analyzing the evolution similarities and the evolution differences among the evolved curves based on scale space technique. Moreover, the evolution differences are viewed as the basic idea of our algorithm (Section 2.1).
•
Based on Gaussian scale space we utilize Difference of Gaussian to reflect the evolution difference, which may be characterized by the norm of DoG. Naturally, the norm of DoG is defined as response function of corner detection (Section 2.2).
•
In order to analyze the corner detection and localization performance of DoG, we discuss the relationship between the extreme points of DoG’s norm and the curvature, and then conclude that the maxima of the DoG’s norm correspond to ones of the curvature. Furthermore, we discuss the advantages of DoG over the curvature (Section 2.3).
•
Finally, we carry out a comprehensive evaluation to study on the detection and localization performances of the detectors. The DoG corner detector outperformed the CSS and wavelet and covariance matrix detectors according to ACU He and Yung, 2004 and Error Index Lowe, 2004 criteria (Section 3).

Section snippets

Motivation

Let C(u) represent a regular planar curve as following: $C (u) = (x (u), y (u))$ where u is the any parameter, and x(u) and y(u) denote coordinate functions of planar curve, respectively.

The planar curve is first smoothed by convolution with Gaussian function $G (u, σ) = \frac{1}{\sqrt{2 π σ^{2}}} \exp (- u^{2} / 2 σ^{2})$ where σ is standard deviation.

We have $C (u, σ) = G (u, σ)^{*} C (u) = (G (u, σ)^{*} x (u), G (u, σ)^{*} y (u)) = (X (u, σ), Y (u, σ))$ where ∗ denotes convolution operator.

As shown in Fig. 1b–f, a leaf curve evolves at different scales according to (2). In the

Performance evaluation and experimentations

In this section, we will compare the proposed DoG detector with Harris et al. (1987) and several typical boundary-based corner detectors including CSS (Mokhtarian and Suomela, 1998), eigenvalues of covariance matrices (Tsai et al., 1999), wavelet transform (Lee et al., 1995), and eigenvectors of covariance matrices (Yeh, 2003) by using two criteria – accuracy (ACU) (Mohanna and Mokhtarian, 2001) and Error Index (Sojka, 2002). For convenience, we simplify these detectors as DoG, Harris, CSS,

Conclusions

In this paper, we first focused on the evolution similarities and the evolution differences of planar curves and found that the evolution difference can better reflect the domination structure feature of the planar curves than the evolution similarities. In the following, based on Gaussian scale space we defined a new operator, i.e. DoG (Difference of Gaussian) operator of planar curves, whose norm represents and characterizes the evolution difference. Furthermore, it has been verified that the

Acknowledgements

This work was supported by Notional Science Foundation (Grand No. 60604007), China, and Chongqing Science Foundation (Grand No. CSTC2005BA2002).

References (27)

F. Arrebola et al.
Corner detection and curve segmentation by multi-resolution chain-code linking
Pattern Recognition
(2005)
S.C. Bae et al.
COP: A new corner detector
Pattern Recognition Lett.
(2002)
C.H. Chen et al.
Wavelet transformation for gray-level corner detection
Pattern Recognition
(1995)
X.T. Gao et al.
Multiscale contour corner detection based on local natural scale and wavelet transform
Image Vision Comput.
(2007)
D.S. Guru et al.
Non-parametric adaptive region of support useful for corner detection: A novel approach
Pattern Recognition
(2004)
L. Kitchen et al.
Gray level corner detection
Pattern Recognition Lett.
(1982)
A. Quddus et al.
Wavelet-based corner detection technique using optimal scale
Pattern Recognition Lett.
(2002)
A. Sobania et al.
Morphological corner detector using paired triangular structuring elements
Pattern Recognition
(2005)
C.-H. Yeh
Wavelet-based corner detection using eigenvectors of covariance matrices
Pattern Recognition Lett.
(2003)
Dreschler, L., Nagel, H.H., 1981. Volumetric model and 3D trajectory of a moving car derived from monocular TV frame...

Fang, J.Q., Huang, T.S., 1982. A corner finding algorithm for image analysis and registration. In: Proc. AAAI Conf.,...

Harris, C.G., 1987. Determination of ego-motion from matched points. In: Proc. Alvey Vision Conf., Cambridge,...

N.H.C. He, X.C. Yung, 2004. Curvature scale space corner detector with adaptive threshold and dynamic region of...

Cited by (58)

A dedicated benchmark for contour-based corner detection evaluation
2023, Image and Vision Computing
Numerous contour-based corner detection (CBCD) algorithms have been proposed recently, necessitating effective and practical evaluation. Most existing methods evaluate corner detection accuracy through metrics between the testing image and its attacked versions or rely on image-specific ground truth for corner evaluation. These methods use images as input, failing to solely evaluate the corner detection performance but combining it with contour extraction evaluation. Since contour extraction is another important research topic and existing CBCD algorithms almost have no contribution to contour extraction, this intertwining may negatively impact the evaluation results, hindering corner detection development. Furthermore, most evaluation methods directly provide simple statistical scores of evaluation metrics, such as the mean value, which are inadequate to reflect the overall performance distribution. This study presents a novel benchmark that is specifically designed for assessing CBCD methods, which includes two major contributions. Firstly, we design two dedicated datasets, one with the ground-truth corner and the other without them. The dedicated contours instead of images are employed as input to evaluate numerous CBCD methods, eliminating the impact of the extracted contour quality. When the ground-truth corners are unavailable, we employ additional contour attacks, including Gaussian noise, projective, and combined geometry on contours, to simulate real-world complex image processes compared with the attacks in existing evaluation methods. Secondly, we evaluate the performance of twelve CBCD methods using six distinct metrics based on the constructed contour datasets. To gain a deep insight into the overall performance distribution, the sign test method for hypothesis testing is utilized alongside some simple statistical measures for evaluation metric analysis. Experimental results demonstrated that no individual method performs the best across all six evaluation metrics, while different CBCD algorithms have their positive scenarios. The evaluation code will be publicly available at https://github.com/roylin1229/CBCD_eva.
Robust corner detection with fractional calculus for magnetic resonance imaging
2021, Biomedical Signal Processing and Control
Citation Excerpt :
Therefore, how to obtain corners and improve the accuracy of detection has become a research hot spot [9–12]. There are many corner detection methods depending on the classical integer-order derivative, especially 1st-order [13–15,9] or 2nd-order differentiation [16,10]. Some popular corner detection methods (such as Harris, Shi–Tomasi, SUSAN and their advanced versions, etc.) are generally accomplished by calculating the gradient so that differential gradient operations naturally become the key technology of corner detection and location [17,18,4].
In medical image processing and analyzing, corners are one of the most important features, which makes point-based registration and diagnosis studies essential. However, existing corner detectors are impressible to noise. This work proposes an order-steerable and robust image corner detector, while a fractional gradient operator consisting of fractional-order forward and backward differentiation and integration is derived. The fractional gradient operator achieving a 90° phase shift as the traditional first derivative does provides a new idea to calculate the gradient in an image. Qualitative and quantitative comparison experiments with exiting detection methods based on integer-order derivative are performed on simulated and real medical slices. The comparison experiments indicate that the present corner detector in this paper allows very strong response for corner detection and provides a better ability of detecting and locating image corners and robustness against noise.
Robust corner detection using the eigenvector-based angle estimator
2017, Journal of Visual Communication and Image Representation
Citation Excerpt :
This is because EAE and WEAE directly considered angle as a representation of discrete curvature and overcame one weakness of CPDA, which is that the curvature values of the CPDA detector, which were estimated to measure the sharpness of the corners, may not be proportional to the angles of the corners [39]. Eigenvector [22] did not perform well; the reason was that the wavelet transform of contour orientation is essentially equivalent to the second-order derivative of the smoothed curves, which is very sensitive to the noise [33]. EAE and WEAE did not have this problem since they had not adopted any derivative of curve-point locations.
Angle is an intuitive and important property for representing corners. This fact motivates us to present a novel angle-based corner detector, named Eigenvector-based Angle Estimator (EAE). EAE estimates the angle of each point in a contour via computing the eigenvectors of the covariance matrix of boundary points over a small Region of Support (RoS). Since EAE is sensitive to uniform scaling due to the fixed RoS, an enhanced version of EAE named Weighted EAE (WEAE) is proposed. WEAE achieves robustness to uniform scaling by weighting the boundary points using their distances from the target point. Experimental results demonstrate that EAE and WEAE can efficiently achieve promising performance in comparisons with several recent state-of-the-art approaches under two commonly used evaluation metrics, namely, Average Repeatability (AR) and Localization Error (LE).
Lead curve detection in drawings with complex cross-points
2015, Neurocomputing
Lead curve detection in design drawings is a critical problem in a wide range of applications ranging from checking similar drawings in patent granting to constructing hyperlinks between image and text description in digitalization. The difficulty of the problem are two folds: unknown end point of lead curve and complex crossings. However, most previous curve detection algorithms are usually applied in simple or no crossing situations. We make four contributions in solving the problem: (1) we transform the problem into a new problem that finds an optimal path with the best score in the cross-point graph. We introduce the “cross-point graph” representation which captures the topology of cross-point connectedness. Based on the original drawing and the corresponding cross-point graph, we introduce the coupling concept “curve-path”, which correlates the curve in the original drawing with the corresponding path in the cross-point graph. (2) we design a set of joint feature representations for curve-path which describes different characteristics of a curve and its corresponding path. (3) we define a task specific loss function for our customized structured SVM. We propose a mixed negative instance sampling strategy to learn the weights of different joint feature representations. We prune the search space effectively for fast lead curve detection. (4) we build a software to efficiently facilitate manual lead curve labeling. We release the patent drawing dataset with groundtruth to public for lead curve detection research. The extensive experimental results prove the effectiveness of our methods.
Effective and efficient contour-based corner detectors
2015, Pattern Recognition
Citation Excerpt :
There are also detectors that apply other mechanisms to process the curve before deriving the corners. Zhang et al. [18] proposed a detector which applies multiple levels of Difference of Gaussian (DoG) on a curve to obtain several corresponding planar curves. These planar curves are then used for detecting the corners.
Corner detection is an essential operation in many computer vision applications. Among the contour-based corner detectors in the literature, the Chord-to-Point Distance Accumulation (CPDA) detector is reported to have one of the highest repeatability in detecting robust corners and the lowest localization error. However, based on our analysis, we found that the CPDA detector often fails to accurately detect the true corners when a curve has multiple corners but the sharpness of one or a few of them is much more prominent than the rest. This detector also might not perform well when the corners are closely located. Furthermore, the CPDA detector is also computationally very expensive. To overcome these weaknesses, we propose two effective and efficient corner detectors using simple triangular theory and distance calculation. Our experimental results show that our proposed detectors outperform CPDA and nine other existing corner detectors in terms of repeatability. Our proposed detectors also have a relatively low or comparable localization error and are computationally more efficient.
A survey of recent advances in visual feature detection
2015, Neurocomputing
Feature detection is a fundamental and important problem in computer vision and image processing. It is a low-level processing step which serves as the essential part for computer vision based applications. The goal of this paper is to present a survey of recent progress and advances in visual feature detection. Firstly we describe the relations among edges, corners and blobs from the psychological view. Secondly we classify the algorithms in detecting edges, corners and blobs into different categories and provide detailed descriptions for representative recent algorithms in each category. Considering that machine learning becomes more involved in visual feature detection, we put more emphasis on machine learning based feature detection methods. Thirdly, evaluation standards and databases are also introduced. Through this survey we would like to present the recent progress in visual feature detection and identify future trends as well as challenges.

View all citing articles on Scopus

View full text

Robust image corner detection based on scale evolution difference of planar curves

Abstract

Introduction

Section snippets

Motivation

Performance evaluation and experimentations

Conclusions

Acknowledgements

Pattern Recognition

Pattern Recognition Lett.

Pattern Recognition

Image Vision Comput.

Pattern Recognition

Pattern Recognition Lett.

Pattern Recognition Lett.

Pattern Recognition

Pattern Recognition Lett.