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.
Corner detection is important for feature extraction and
pattern recognition. In , Harris and Stephens proposed a
corner detection algorithm. First, they used a quadratic
polynomial to approximate the variation around [m, n]:
where Am,n, Bm,n, and Cm,n were calculated from the correlations
between the variations and a window function:
If both the two eigenvalues of Hm,n are large, then we
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 , 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
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 L1[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 L1[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
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 .
(D) In , Harris classified the pixel into only three
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.
(Step 1) First, find the orthonormal polynomial set that
orthogonal respect to a weighting function w[m, n]. That is
and the parameters aj,k should be chosen
properly such that
We can use the Gram-Schmidt algorithm to find aj,k.
example, if we choose the weighting function as
then the orthogonal polynomials are
(Step 2) Then, we do the inner product for L1[m,
n, x, y] is
(defined in (5)) and Φk[x, y], where k = 1, 2, 3, 4, 5, 6:
Note that Qm,n[x, y] ≈ L1[m, n, x,
y] (defined in (5)). Then,
we expand Qm,n[x, y] as a function of principal axes
and the principal axes
are the eigenvectors of
and c2,m,n are the corresponding
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 Xm,n-axis (denoted by +Xm,n)
Similarly, the variations along the negative part of Xm,n-axis
(denoted by –Xm,n) and along the positive
parts of Ym,n-axis (denoted by +Ym,n
and –Ym,n) are:
We may choose t as . Then, we choose a
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
(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 Qm,n[x, y] in a
where Xm,n = rcosθ,
Ym,n = rsinθ, and
Qm,n[x, y] is defined
in (16) and (17). Eq. (24) has an analytic solution:
Why is the cornity defined as the integration of Qm,n[x,
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 Qm,n(x, y) is near to zero.
If [m, n] is at a
corner, then the integration of Qm,n[x, y]
will be far from
zero. Thus, Qm,n[x, y] is good for cornity
(Step 7) If a pixel [m, n] is a corner candidate and
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:
Fig. 2 Corner detection and edge detection for Star image.
moreover, we classify the adjective pixels into four
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.
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
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.
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.
 C. Harris and M. Stephens, “A combined corner and edge
detection”, Proc. 4th 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
Fig. 7 Using the proposed algorithm to do edge detection.
 A. F. Nikiforov, S. K. Suslov, and V. B. Uvarov,
Orthogonal Polynomials of a Discrete Variables,
Berlin; New York: Springer-Verlag, 1991.
 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.
 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.
 N. C. Overgaard, “On a Modification to the Harris
Corner Detector”, Symposium Svenska Sällskapet för
Bildanalys, Stockholm, 2003.