A New Algorithm for Detecting Corners in Digital Images

cordet Author: Eduard Sojka, eduard.sojka<AT>vsb.cz

Abstract: The corners and vertices are important features in images, which are frequently used for scene analysis, stereo matching and object tracking. Many algorithms for detecting the corners have been developed up to now. In this presentation, a new and efficient algorithm is presented.

The algorithm is based on measuring the variance of the directions of the gradient of brightness. The probability of the event that the image points belong to the approximation of the straight segments of the isoline of brightness containing the corner candidate being examined is determined using the technique of Bayesian estimations, and then used for computing the angle between the segments intersecting at the candidate.

We believe that the detector we propose is good. In the tests we have carried out, our detector was better (in the successfulness of detection) than other recognised direct corner detectors that are usually used for solving the problem.

Key Words: Corner detection, feature-point detection, digital image processing.

The purpose of this internet presentation is to provide the interested readers with the materials that cannot be published in papers. We present here the source code of the algorithm, the full technical report, results of testing, used test images, etc. The majority of them can be downloaded.

The source code in ANSI C of the algorithm (from 25 May 2003) with accessories can be downloaded here (0.1MB). We also recommend to download some additional examples and test images, which can be done here (1.2MB). You will simply only unzip both the files into one directory.

The full version of the technical report in a zipped postscript file can be downloaded here (1.4MB). The report is divided into two parts. The first part contains the overview of the existing state. The second part contains the desription of the new detector.

Publications describing the detector or its parts

  • E. Sojka, A new approach to detecting the corners in digital images. Accepted for publication in IEEE ICIP 2003.
  • E. Sojka, A new and efficient algorithm for detecting the corners in digital images. Proc. 24th DAGM Symposium, Springer, LNCS 2449, Berlin, NY, 125--132 (2002).
  • E. Sojka, A new algorithm for detecting corners in digital images. Proc. SCCG 2002, ACM SIGGRAPH, NY, 55--62 (2002).

Results of testing the algorithm

In the first tests of the algorithm, the images shown in the following table were used. Below each of the images, the reference solution (the solution that is regarded to be correct) and the solution provided by the new algorithm are available. The process how the reference solutions were obtained is described in the technical report. In the case of synthetic images, however, it should be more or less clear. The Image #2 differs from the Image #1 in the content of noise.

Test images

Image #1

Image #2

Image #3
Reference solutions Solution #1 Solution #2 Solution #3
Solutions provided by the new algorithm Solution #1 Solution #2 Solution #3

We define the total error of the detector to be the sum of the number of missed corners, false detections and superfluous multiple detections (see the report). For all detectors, the values of all their parameters (e.g. thresholds) were set to the values giving the lowest possible total error. The following table shows the values of total errors for the algorithms that have been tested. If you click on an item in the table, you can see more details.

Algorithm/Test image Image #1 Image #2 Image #3
Beaudet 104 185 167
Deriche-Giraudon 140 189 184
Harris-Stephens 30 62 121
Kitchen-Rosenfeld 149 193 169
New algorithm 0 6 79
SUSAN 129 173 169

You can see the results also in the following graphs.

Error index1) for the test images #1-3

1) Error index = 100 * total error / number of corners.

Localisation error1) for the test images #1-3

1) Localisation error is measured in pixels.

Testing the detector with other famous test images

In this series of tests, the corners in the "famous" test images were found by the new detector. The results were only checked visually, since the reference solutions are not known and are not so easy to determine (except for the first two images). The parameters of the detection (they determine, e.g., the number of corners that are found) was set only intuitively to obtain the results that are "optically acceptable". (The detector can sort the corners according to their obviousness and can find a chosen number of the most obvious corners. This feature was not used.)



SUSAN image

Blocks

Lab

House

Pentagon

Testing the influence of noise

This test was carried out i such a way that the Gaussian noise of various levels was added to the test Image #1 (five realisations of noise of each level were used). The corners were then detected by the new detector and by the Harris detector, respectively. For both the detectors and for each noise level, the optimal set of parameters were found. The results of the test are summarised in the following graph.

Error index1) in dependance on noise level

1) Error index = 100 * total error / number of corners.

Testing the stability

This test was carried out i such a way that the Image #1 was rotated by the angles of 0, pi/29, pi/13, pi/7, and pi/4, respectively. The Gaussian noise (with sigma = 5% of image range) was added. The corners were then detected by the Beaudet, Harris, Kitchen, and the new detector, respectively. For each particular detector, the set of its optimal parameters was found for the unrotated image. This set was then also used for detecting the corners in all the rotated images. The results of the test can be seen in the following graph.

Error index1) in dependance on the angle of rotation

1) Error index = 100 * total error / number of corners.