Keywords

1 Introduction

Corner points in images represent critical information in describing object features, which play a crucial and irreplaceable role in computer vision and image processing. Many computer vision tasks rely on the successful detection of corner points, including image matching, object recognition and object tracking, image retrieval, 3-D reconstruction, [1,2,3,4] etc. Feature tracking are also a fundamental problem of image processing research. In tracking problem, a set of efficient algorithms [5,6,7,8,9,10] are proposed for tracking salient objects from images and videos.

However, there still not exists a strict mathematical definition for corners; corners are in the past decades, a substantial number of promising corner detection methods based upon the different corner definitions have been proposed by vision researchers. The existing corner detection methods can be broadly classified into two classes: intensity-based [12,13,14,15,16,17,18,19] and contour-based methods [21,22,23,24,25,26,27]. The presence of two categories methods have their strengths and weaknesses, which makes the corner detection become research hotspot in the field of computer vision and image processing.

This paper is organized as follows. Section 2 gives a systematic review of state-of-the-art corner detection methods. Section 3 presents the new corner detector with detailed flowchart. Section 4 shows the comparison results of the proposed corner detector with other three popular detectors in the respect of repeatability and localization accuracy under affine transforms, JPEG compression and Gaussian noise. Finally, a conclusion is given.

2 Literature Survey

This section presents a review of the existing literature on corner detection methods. In the literature, the terms “point feature”, “dominant point”, “critical point” and “corner” are taken as equivalent. However, the terms “interest point” and “salient point” include not only “corner”, but also junctions and blobs, as well as significant texture variation [11].

2.1 Intensity-Based Methods

The key of the intensity-based corner detection is to extract gray-variation and structural information. Moravec [12] considered corners as points which are not self-similar in an image. Harris and Stephens [13] presented an operation by modifying the Moravec’s interest operator, using the first order derivative to approximate the second derivatives. Lowe [14] proposed a scale invariant feature transform (SIFT), which combines a scale invariant region detector and a descriptor based upon on the gradient distribution in the detected region. Bay et al. [15] presented SURF detector that locates the feature points at which the determinant of the Hessian reaches its maximum. Meanwhile, the low complexity is enabled by employing the box filters and the integral images. Leutenegger et al. [16] proposed BRISK detector, a method for key point detection, description and matching. Later, KAZE detector [17] finds local extreme by diffusing filtering, which is used to provide multi scale spaces and preserves natural image boundaries. Ramakrishnan et al. [18] introduced a novel technique to accelerate the Harris corner detectors, which using simple approximations to quickly prune away non-corners. Wang et al. [19] implemented an adaptive Harris corner detection algorithm based on the iterative threshold; the technique was an improvement of the Harris corner detection algorithm.

2.2 Contour-Based Methods

Contour-based methods first obtain image’s planar curves by some edge detector (e.g., Canny edge detector [20]) and then analyze the properties of the contours’ shape to detect corners. Thereafter, the points of local curvature maxima, line intersects or rapid changes in the edge direction are marked as corners. Kitchen and Rosenfeld [21] developed a corner measure based upon the change of gradient direction along an edge contour multiplied by the local gradient magnitude as follows:

$$ C_{KR} (x,y) = \frac{{I_{xx}^{{}} I_{y}^{2} - 2I_{xy}^{{}} I_{x} I_{y}^{{}} + I_{yy}^{{}} I_{x}^{2} }}{{I_{x}^{2} + I_{y}^{2} }}. $$
(1)

Later, Mokhtarian and Suomela [22] proposed a curvature scale space (CSS) corner detector. For a given parametric vector equation of a planar curve \( \Gamma (u) = \{ x(u),y(u)\} \), the curvature is defined as

$$ K(u,\sigma ) = \frac{{\dot{X}(u,\sigma )\ddot{Y}(u,\sigma ) - \ddot{X}(u,\sigma )\dot{Y}(u,\sigma )}}{{\left[ {\mathop {\text{X}}\limits^{.} (u,\sigma )^{2} + \mathop {\text{Y}}\limits^{.} (u,\sigma )^{2} } \right]^{{{\raise0.7ex\hbox{$3$} \!\mathord{\left/ {\vphantom {3 2}}\right.\kern-0pt} \!\lower0.7ex\hbox{$2$}}}} }} $$
(2)

Where,

$$ \begin{aligned} & \dot{X}(u,\sigma ) = x(u) \otimes \dot{g}(u,\sigma )\quad \ddot{X}(u,\sigma ) = x(u) \otimes \ddot{g}(u,\sigma ) \\ & \dot{Y}(u,\sigma ) = y(u) \otimes \dot{g}(u,\sigma )\quad \, \ddot{Y}(u,\sigma ) = y(u) \otimes \ddot{g}(u,\sigma ) \\ \end{aligned} $$
(3)

Here, \( \otimes \) is the convolution operator, \( \sigma \) is the scale factor, \( \dot{g}(u,\sigma ) \) and \( \ddot{g}(u,\sigma ) \) are the first- and second derivatives of Gaussian \( g(u,\sigma ) \), respectively. To improve corner localization and noise suppression, an enhanced CSS algorithm [23] is proposed by using different scales of the CSS for contours with different length. He and Yung [24] used an adaptive curvature threshold in a dynamic region of support to judge corners. The chord-to-distance accumulation technique [25] is applied to compute curvature and detect corners. Zhang and Shui [26] presented a contour-based corner detector using the angle difference of the principal directions of anisotropic Gaussian directional derivatives (ANDDs) on contours. Lin et al. [27] introduced two novel corner detectors to measure the response of contour points using Manhattan distance and Euclidean distance.

3 Proposed Corner Detector

In this section, we give a new corner detection method using a maximum point-to-chord distance. Like the most contour-based methods, our proposed corner detector first uses Canny to extract image’s planar curves. Then the maximum point-to-chord distance algorithm is applied to each curve to estimate an initial corner point. Next, the curvature on each initial corner point is computed. Finally, non-maximum suppression and threshold are used to remove weak corner points with low curvature and the final corner points are detected.

3.1 Planar Curves Extraction

Canny edge detector is one of the most widely used edge detectors in contour-based corner detectors and has also become a standard gauge in edge detection. An edge pixel is defined as if the gradient magnitudes at either side of it are lower than itself. However, the output contours may have small gaps and these gaps may possibly contain corners. These small gaps are formed because of two main reasons. First, the gradient magnitudes around junctions become very small, which results in the exclusion of junctions from the edge map. Although in some branching edges, the gradient magnitudes are not small but the maximal value is not at the gradient direction which will be discarded after the non-maximum suppression. Therefore, filling the small gaps between contours before corner detection is a necessary work to avoid loss of corners.

3.2 The Maximum Point-to-Chord Distance

After we extract the planar curves from the Sect. 3.1, we use a maximum point-to-chord distance method to select the corner point on the image. The detailed algorithm is outlined as follows:

  1. 1.

    Let \( C \) be a set of \( N \) discrete point \( P_{1} \) to \( P_{N} \) that compose a curve in sequence \( C = \left\{ {P_{1} ,P_{2} ,P_{3} , \ldots ,P_{N} } \right\} \).

  2. 2.

    Connect \( P_{1} \) and \( P_{N} \) with a line, so we get a chord \( L_{1,N} \).

  3. 3.

    The perpendicular distance of all points in the curve \( C \) to the chord \( L_{1,N} \) is measured, denoted as \( D = \left\{ {D_{1,L} ,D_{2,L} ,D_{3,L} , \ldots ,D_{N,L} } \right\} \).

  4. 4.

    Find the maximal distance \( D_{max} \) in \( D \) and the corresponding point \( P_{max} \).

  5. 5.

    If the maximal distance \( D_{max} \) is beyond a threshold \( T_{min} \), mark the corresponding point \( P_{max} \) as a corner point, and divide the curve \( C \) into two curves \( C_{1} \) and \( C_{2} \).

  6. 6.

    Repeat the step 1–6 for \( C_{1} \) and \( C_{2} \), until the maximal distance \( D_{max} \) is below a threshold \( T_{min} \) (Fig. 1).

    Fig. 1.
    figure 1

    Diagrammatic sketch of point-to-chord distance calculation

    Full size image

3.3 False Corner Removal

After the maximum point-to-chord distance algorithm that presented in Sect. 3.2, we got a series of initial corner points. Although the threshold \( T_{min} \) prevents the weak corner to be selected, there are still some occasions that our algorithm could choose some weak corner as the output corner points. These false corners have a common characteristic that they are located in flat curves, which have low curvature value. Thus, by removing the initial corner with low curvature value, the false corners could be eliminated. After the curvature of each corner point been computed, the non-maximum suppression algorithm and a threshold are used to suppress the corner points with small curvature and too close to other corner points. Figure 2 shows the false corner removal result.

Fig. 2.
figure 2

False corner removal

Full size image

4 Experimental Results and Performance Evaluation

In this section, we focus on experiments and performance evaluation. The proposed detector is compared with three popular detectors (Harris [13], BRISK [16], He and Yung [24] and CPDA [25]). The average repeatability and localization error is used to evaluation the four detectors including our proposed detector with no manual intervention. The evaluation programmer can be running on any size of database, apply basic transformations like rotation, scaling, shear, image quality compression and Gaussian noise. Each image in the input database is applied these transformations and the average repeatability and localization error are computed for each detector. Finally, the average repeatability and localization error curves are drawn to have a visualized performance comparison of each detector.

4.1 Database and Transformation

As can be seen from Fig. 3, fifteen images collected from standard evaluation dataset [29] are used to evaluate the four detectors including our proposed detector.

Fig. 3.
figure 3

Fifteen standard test images

Full size image

Each image from the dataset is transformed by the following six types of transformations:

  1. 1.

    Rotations: Rotate from −90° to 90° in 10° increments for each transformation.

  2. 2.

    Uniform Scaling: Scale factors \( s_{x} = s_{y} \), in 0.1 increments from 0.5 to 2.0.

  3. 3.

    Non-uniform Scaling: Scale factors \( s_{x} = 1 \) and \( s_{y} \) in 0.1 increments from 0.5 to 2.0.

  4. 4.

    Shear transforms: Shear factor \( c \) in 0.1 increments from −1.0 to 1.0.

    $$ \left[ {\begin{array}{*{20}c} {x^{\prime } } \\ {y^{\prime } } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} 1 & c \\ 0 & 1 \\ \end{array} } \right]\left[ {\begin{array}{*{20}c} x \\ y \\ \end{array} } \right] $$
  5. 5.

    JPEG quality compression: JPEG quality factor in 5% increments from 5% to 100%.

  6. 6.

    Gaussian noise: zero mean white Gaussian noise at 15 standard deviation in [1, 15] at 1 apart.

4.2 Evaluation Criterion

We employ the performance evaluation metrics that used in [28]. The average repeatability and localization error represent the robustness and consistency of the detectors under different transformations that we introduced in 4.1.

The average repeatability \( R_{avg} \) measures the average number of detected corner point in the same position between original images and transformed images. It is defined as

$$ R_{avg} = (1/2) \times N_{r} \times (1/N_{o} + 1/N_{t} ). $$
(4)

Where \( N_{o} \) and \( N_{t} \) denote the number of interest point from original images and transformed images respectively. \( N_{r} \) is the number of repeated interest points between them. Let \( p_{i} \) be one of the corner point detected in the original images, \( q_{j} \) be the corner point detected in the corresponding geometric transformed image.

The localization error \( L_{e} \) is defined as the average distance between the corner points detected in the original images with those detected in the transformed images.

$$ L_{e} = \sqrt {\frac{1}{{N_{r} }}\sum\limits_{i = 1}^{{N_{r} }} {\left( {x_{oi} - x_{ti} } \right)^{2} + \left( {y_{oi} - y_{ti} } \right)^{2} } } . $$
(5)

Where \( (x_{oi} ,y_{oi} ) \) and \( (x_{oi} ,y_{oi} ) \) are the location of repeated corner \( i \) in the original and transformed images respectively.

4.3 Summary of the Proposed Parameter Setting

In this subsection, we summarized the proposed parameter setting. The parameters \( T_{min} \) and the non-maximum suppression threshold were decided by experimentation. Figure 4 shows the effect of the point-to-chord distance \( T_{min} \) on the proposed corner detector. When it was set small, the average repeatability was relatively high, but its robustness to localization was quite low. However, when it was increased above 6, both the average repeatability and localization error remain stable. Therefore, we have chosen \( T_{min} = 6 \) as default for the detector. Figure 5 shows the average repeatability did not change much. Thus, we selected the parameter produced the least localization error as default value.

Fig. 4.
figure 4

The effect of threshold \( T_{\hbox{min} } \) on the new corner detector

Full size image
Fig. 5.
figure 5

The effect of threshold \( T_{nms} \) on the new corner detector

Full size image

4.4 Comparative Results

In this section, a comparison of the average repeatability and localization error between the proposed and three other detectors (Harris [13], BRISK [16], He and Yung [24] and CPDA [25]) are presented.

The results of the average repeatability and localization error under six different transforms are shown in Fig. 6. In general, the four corner detectors achieved the highest average repeatability in JPEG quality compression and the worst localization error in shear transformation. The proposed and CPDA corner detectors performed better than other detectors in geometric transformations. In terms of JPEG quality compression and Gaussian noise, the proposed method achieves the highest average repeatability and lowest localization error than other three detectors. The experimental results show that the proposed detector attains better overall performance.

Fig. 6.
figure 6figure 6

Comparison of average repeatability (a) and localization error (b) under six different transforms

Full size image

5 Conclusion

This paper proposed a new robust corner detection algorithm based on a maximum point-to-chord distance. Like the most of the contour-based corner detectors, the first step is to extract the edge map of original image and extracts edge contours from it. Compared with the existing corner detection algorithms based on curvature calculation, the proposed algorithm does not need to calculate the first- and second- derivatives, avoids the calculation error caused by the local variation effectively and very robust to noise. It can be seen from the experiment result that the proposed corner detector performs better than other three classical detectors in term of robustness. Corner detection algorithm of this paper has good detection performance. Future tasks may continuously improve its detection performance and apply it in many of computer vision research.