CORNER AND EDGE DETECTIONS

ABSTRACT

A more accurate algorithm for corner and edge detections
that is the improved form of the well-known Harris’ algorithm
is introduced. First, instead of approximating |L[m+x,
n+y]–L[m, n]|^2 just in terms of x ^2, xy, and y^2, we will approximate
|L[m+x, n+y]–L[m, n]|(L[m+x, n+y]–L[m, n]) by
the linear combination of x^2, xy, y^2, x, y, and 1. With the
modifications, we can observe the sign of variation . It can
avoid misjudging the pixel at a dot or on a ridge as a corner
and is also helpful for increasing the robustness to
noise. Moreover, we also use orthogonal polynomial expansion
and table looking up and define the cornity as the
“integration” of the quadratic function to further improve
the performance. From simulations, our algorithm can
much reduce the probability of regarding a non-corner
pixel as a corner. In addition, our algorithm is also effective
for edge detection.

Index terms: corner detection, edge detection,
quadratic polynomial, ridge detection, noise immunity

1. INTRODUCTION

Corner detection is important for feature extraction and
pattern recognition. In [1], Harris and Stephens proposed a
corner detection algorithm. First, they used a quadratic
polynomial to approximate the variation around [m, n]:

remained terms, (1)

where A_m,n, B_m,n, and C_m,n were calculated from the correlations
between the variations and a window function:

Then the variations along the principal axes can be calculated
from the eigen values of the following 2*2 matrix:

If both the two eigenvalues of H_m,n are large, then we recognize
the pixel [m, n] as a corner. Harris and Stephens
proposed a systematic and effective way to detect corners.

However, the algorithm has some problems, such as the
ability to distinguish the corner from the peak or the dip
and the robustness to noise should be improved. In [5], an
improved algorithm based on modifying the detection
criterion was proposed. In this paper, we apply many new
ideas listed in Section 2 to improve Harris’ algorithm for
corner detection.

2. IDEAS FOR IMPROVING PERFORMANCE

(A) Instead of approximating |L[m+x, n+y]-L[m, n]|^2, we
use a quadratic polynomial to approximate L₁[m, n, x, y]:

This modification is helpful for improving the robustness
to noise. Suppose that the image is interfered by a
noise η[m, n], i.e., H[m, n] = L[m, n] + η[m, n], and

then we can prove that

Thus, the mean of (1) is affected by noise, but from (9)
the mean of L₁[m, n, x, y] will be not affected by noise.

The sign of variation is also important to distinguish
a corner from a peak. For both a corner pixel and a peak,
the variations along all the directions are large, as in Fig.
1. If we observe only the amplitude of variations, as Harris’
algorithm, they are hard to distinguish. In contrast, if
the sign of variations can be observed, we can distinguish
them. For a peak, the signs of variations along all
the directions are negative. For a corner, sometimes
variation is positive and sometimes it is negative.

(B) We will approximate the variation by the linear combination
of x^2, xy, y^2, x, y, and 1, see (16). For Harris’ algorithm
in (1), only the terms of x^2, xy, and y^2 are used.
Note that x^2 and y^2 are even-even bases (i.e., even respect
to both x and y) and xy is an odd-odd basis. Using
them is hard to observe even-odd and odd-even variations.
Thus, to observe all types of variations, we should
use the terms of x (an odd-even basis) and y (an evenodd
basis). With these terms, we can observe more
styles of variations and classify the pixel into more types.

C) Instead of (3), we use “orthogonal polynomial expansion”
to find the coefficients . It can assure that the mean
square error of approximation to be minimal [2].

(D) In [1], Harris classified the pixel into only three types:
corners, edges, and plains. In this paper, with the help of
Case table (see Table 1), we classify the pixel into corners,
edges, ridges, valleys, peaks, saddles, and plains.

(E) From derivations and experiments, we find that, to
achieve the best accuracy, it is better to define the cornity
as the “integration” of the quadratic function. See Step 6.

3. ALGORITHM

(Step 1) First, find the orthonormal polynomial set that is
orthogonal respect to a weighting function w[m, n]. That is

and the parameters a_j,k should be chosen properly such that

We can use the Gram-Schmidt algorithm to find a_j,k. For
example, if we choose the weighting function as

then the orthogonal polynomials are

(Step 2) Then, we do the inner product for L₁[m, n, x, y] is
(defined in (5)) and Φ_k[x, y], where k = 1, 2, 3, 4, 5, 6:

(Step 3) Then we ex press the variation around [m, n] by:

Note that Q_m,n[x, y] ≈ L₁[m, n, x, y] (defined in (5)). Then,
we expand Q_m,n[x, y] as a function of principal axes

where
and the principal axes
are the eigenvectors of

c_1,m,n and c_2,m,n are the corresponding eigenvalues, and

Fig. 1 Variations of gray levels along four principal directions
for the pixel at a corner, on an edge, at a peak, and on a ridge.

Table 1 Case table

(Step 4) From (19), we can observe the variation along the
two principal axes. For example, the variation along the
positive part of X_m,n-axis (denoted by +X_m,n) is:

Similarly, the variations along the negative part of X_m,n-axis
(denoted by –X_m,n) and along the positive and negative
parts of Y_m,n-axis (denoted by +Y_m,n and –Y_m,n) are:

We may choose t as . Then, we choose a threshold

Harris’ algorithm classifies the variation into only 3 types.
For our algorithm, there are four directions
and for each direction there are 3 types of variations
. In sum, there are 3^4 = 81 types of variations

(Step 5) For the typical corner in Fig. 1, the variation
along one axis is and along another axis is
Thus, we conclude that if and
the pixel should be at the corner. If a pixel is on an
edge, then the variation along one principal axis is
and along another principal axis is . We use Table 1
(Case table) to summarize the relations between the variation
style and the most possible location of a pixel. With it,
we can conclude the pixel is at a corner, on an edge, on a
plane, on a ridge, in a valley, or at a peak.

(Step 6) In Step 5, we just obtain the “corner candidates”.
Sometimes, the pixel that is not at a corner but
near the corner will be recognized as a corner after Step 5.
Thus we should use the cornity score to choose the corner
from the corner candidates. We find that the most effective
way is to define the cornity as the integ ration of the
quadratic polynomial Q_m,n[x, y] in a circular region:

where X_m,n = rcosθ, Y_m,n = rsinθ, and Q_m,n[x, y] is defined
in (16) and (17). Eq. (24) has an analytic solution:

Why is the cornity defined as the integration of Q_m,n[x, y]?
Note that Qm,n[x,y] approximates the variation around [m,n]

If [m, n] is on a plain (L[m+x, n+y]-L[m, n]=0) or an edge
(L[m+x, n+y]-L[m, n]=-(L[m-x, n-y]-L[m, n])), then the
integration of Q_m,n(x, y) is near to zero. If [m, n] is at a
corner, then the integration of Q_m,n[x, y] will be far from
zero. Thus, Q_m,n[x, y] is good for cornity measurement.

(Step 7) If a pixel [m, n] is a corner candidate and
cornity[m, n]≥cornity for . (27)
then [m, n] is recognized as a corner.

4. EDGE DETECTION

Our algorithm can not only detect the corner but also
detect the edge, the ridge, the valley, and the plain regions.
To detect the edge, Steps 1~5 are the same as those of
corner detection. In Step 6, we define the edge score as:

E score also has an analytic solution.

For an “edge candidate” pixel [m, n], if At least 17 adjective
pixels satisfy:

E score ≤ E E score[m, n] for

Fig. 2 Corner detection and edge detection for Star image.

moreover, we classify the adjective pixels into four
quadrants
and for each quadrant, there should be at least
one pixel that satisfies (33), then, we can treat [m, n] as a
pixel on an edge.

5. EXPERIMENTS

We first give an example in Fig. 2. We fol low Steps
1~4 and use the Case table in Step 5 to find the corner and
the edge candidates (shown in Figs. 2(a)(b)). Then, we use
the “cornity” and “E score” and to select corners and
edges from the corner and edge candidates. The results are
shown in Fig. 2(c)(d), which show corners and edges are
detected successfully.

Then we do some experiments to compare the performances
of the proposed and the Harris’ algorithm for
the image in Fig. 3(a). When using Harris’ algorithm, the
results of corner detection is shown in Fig. 3(b). Note that
some pixels at the dots, on the ridge, in the valley, or in a
noise-interfered plain are treated as corners. From common
senses, they should not be corners. However, since
Harris’ algorithm observes just the “amplitudes” of variations,
and these pixels have large variations along two
principle axes, they are misjudged as corners.

If we use the proposed algorithm, we can distinguish a
corner from an isolated pixel, a belt valley, and a belt
ridge according to the “sign” of variation. The result is
shown in Fig. 3(c). Note that no non-corner pixel is misjudged
as a corner. Especially, no pixel in the lower-right
part (the noised-interfered plain) is regarded as a corner. It
proves the theory in (9), i.e., the proposed algorithm is
much more robust to noise.

In Fig. 4, we also do s experiment and show that the
proposed algorithm can avoid regarding the Gaussian-like
noise interfered region as a corner.

Fig. 3 (a) Image consists of three dots (upper-left), a valley (upper-
right), a ridge (lower-left), and a noise-interfered region
(lower-right). (b)(c) The results of corner detections.

Fig. 4 Corner detection results for the plain interfered by Gaussian-
like noise .

We also do the experiment for a natural image in Figs.
5 and 6. It is obvious that, when using the proposed algorithm,
the probability of misjudging the pixel in a valley,
on a ridge, or at the isolated dots as a corner can be much
reduced. Our algorithm can also detect most of the edges
of Lena image successfully, as in Fig. 7.

6. CONCLUSIONS

We introduced an improved algorithm for corner and
edge detections. For the proposed algorithm, since the
“sign” of variations is considered, the difference among a
corner, a belt ridge, and an isolated dot can be observed.
Due to the same reason, our algorithm is more robust to
noise, which was proven in Figs. 3, 4 and 6. We also apply
orthogonal polynomial expansion, case table and the
new definition of cornity to improve the performance.

7. REFERENCES

[1] C. Harris and M. Stephens, “A combined corner and edge
detection”, Proc. 4^th Alvey Vision Conf., 1988, pp. 189-192.

Fig. 5 Using Harris’ algorithm to do corner detection

Fig. 6 Using the proposed algorithm to do corner detection.

Fig. 7 Using the proposed algorithm to do edge detection.

[2] A. F. Nikiforov, S. K. Suslov, and V. B. Uvarov, Classical
Orthogonal Polynomials of a Discrete Variables,
Berlin; New York: Springer-Verlag, 1991.

[3] S. M. Smith and M. Brady, “SUSAN–a new approach
to low level image processing”, Int. J. Computer Vision,
vol. 23, no. 1, 1997, pp. 45-78.

[4] H. Wang and M. Brady, “ Real -time corner detection
algorithm for motion estimation”, Image and Vision
Computing, vol. 13, no. 9, 1995, pp. 695-703.

[5] N. C. Overgaard, “On a Modification to the Harris
Corner Detector”, Symposium Svenska Sällskapet för
Bildanalys, Stockholm, 2003.