Corner Detectors - Harris/Plessy Operator

This operator was developed by Chris Harris and Mike Stephens in 1988 [3] as a low-level processing step to aid researchers trying to build interpretations of a robot's environment based on image sequences. Specifically, Harris and Stephens were interested in using motion analysis techniques to interpret the environment based on images from a single mobile camera. Like Moravec, they needed a method to match corresponding points in consecutive image frames, but were interested in tracking both corners and edges between frames.

Harris and Stephens developed this combined corner and edge detector by addressing the limitations of the Moravec operator. The result is a far more desirable detector in terms of detection and repeatability rate at the cost of requiring significantly more computation time. Despite the high computational demand, this algorithm is widely used in practice.

The literature refers to this detector as both the Harris corner detector and the Plessey corner detector.

The Plessey operator differs from the Moravec operator in how the measurement of local autocorrelation is estimated. This measurement allows the variation of the autocorrelation (i.e. intensity variation) over all different orientations to be obtained. The rational for the Plessey operator follows from addressing the limitation of the Moravec operator.

The Moravec operator has an anisotropic response as the intensity variation is only calculated at a discrete set of shifts (namely, in the eight principle directions). To remove this limitation, a function is needed that allows the intensity variation to be measured in any direction. Harris and Stephen performed an analytic expansion of the Moravec operator to derive such a function. This derivation is not complicated, but provides little insight into the derivation of the Plessey operator. Here a more intuitive, but less mathematically rigorous, approach it taken to arrive at the desired function.

The Prewitt operator is commonly used to approximate the gradient of an image. However, in many applications the first-order gradient is approximated using the simple formulas given in Figure 6.1. With these gradient formulas in mind, it is reasonable to suggest that taking the sum of differences between corresponding pixels in the two Moravec windows (see Figure 5.1) is a reasonable approximation of the gradient. As shown in Figure 6.2, the intensity variation calculation for the Moravec operator can now be approximated using the gradient of the image.

The above analysis indicates that the intensity variation can be written as a function of the gradient of the image. For an arbitrary shift (u,v) we can state the intensity variation as:

For a shift in the x-direction where (u,v)=(1,0) or y-direction where (u,v)=(0,1) we have precisely the approximation for the intensity variation derived in Figure 6.2. The results obtained by performing an analytic expansion of the Moravec operator are identical to equation (1) except that there are terms representing higher order properties which Harris and Stephen ignore.

Let us be clear that equation (1) is not equal to the intensity variation calculation performed by the Moravec operator. However, it is suggested by the Moravec operator and performs a similar measure of intensity variation. The benefit of this new measure for intensity variation is that it can measure intensity variation in any direction by appropriate choice of u and v. Critics of the Plessey operator (specifically [6]) have pointed out that although equation (1) does allow an estimate of the intensity variation to be calculated in any direction, it is still anisotropic as these estimates are based on the horizontal and vertical gradients (see the Limitations section for an example of the anisotropic response of the Plessey operator). Despite being anisotropic, equation (1) allows for a strong edge detector as indicated by the popularity of the Plessey corner detector.

How should u and v be selected for a given direction? Figure 6.3 shows that u and v are simply the x and y distances required to construct a line within the unit triangle that is in the desired direction (i.e the unit circle under the Manhattan or city block distance). Clearly measuring the intensity variation in all directions in order to estimate a measure of local autocorrelation is not possible (there are infinitely many directions). This apparent difficulty is addressed in the Large Response to Edges section below.

Since the window used by the Moravec operator is square and binary, the estimate of the intensity variation is considered noisy. Having a square window results in the Euclidean distance from the center pixel of the window to the edge of the window varying for different directions. This is easily resolved by using a circular window. Being binary puts equal emphasis on all intensity variation measures regardless of their distance from the center of the window. Intuitively, more weight should be put on measurements made closer to the center of the window. These two limitations of the Moravec operator are addressed by using a Gaussian window. For a more detailed discussion on these issues please refer to the Limitation section of the Moravec operator.

The measurement of the intensity variation can now be done as illustrated in Figure 6.4 for a horizontal shift and a 3x3 Gaussian window.

It is known the Moravec operator responds too readily to edges since any imperfections in an edge due to noise, pixilation, or intensity quantization may result in the local minimum intensity variation over all shift directions being relatively large. The Plessey operator addresses this limitation by reformulating the cornerness measure to consider the variation between the intensity variation measures in different directions. Recall that the Moravec corner detector considers only the minimum intensity variation measure found over all considered shift directions.

This form of equation (2) is interesting as the matrix M now contains all the differential operators describing the geometry of the image surface at a given point (x,y). The eigenvalues of M will be proportional to the principle curvatures of the image surface and form a rotationally invariant description of M. However, since the components of M are estimated using only the horizontal and vertical gradients, they are not rotationally invariant.

Let us consider the four different types of window positions that were considered by the Moravec operator. These different window positions are shown in Figure 6.5. Position A is interior to an object (or on the background) where it is assumed image intensity will be relatively constant within the window. Since there is little curvature in the surface within this window both the eigenvalues will be relatively small. For local windows straddling an edge, as in position B, there is significant curvature perpendicular to the edge and very little curvature along the edge so one of the eigenvalues will be large and the other small. Both positions C and D, which correspond to a corner and isolated pixel, will have significant curvature in both directions so both eigenvalues will be large.

Let the eigenvalues of M be denoted by λ₁ and λ₂. The above analysis indicates the plane described by λ₁ and λ₂ can be divided into 3 distinct regions as shown in Figure 6.6.

To classify pixels, the three lines dividing the plane in Figure 6.6 must be selected. However, it is useful to have a measure of cornerness instead of just a discrete label for each pixel. A measure of cornerness allows edges to be thinned and improves localization of corners by taking local maxima to be the true position of corners or edges. Harris and Stephens proposed the following cornerness measure:

Figures 6.7-6.9 show contours of C(x,y) for k=0.2, k=0.1, and k=0.05, respectively. Empirical testing has indicated that values of k = 0.04 to 0.06 give the best results. Comparing these plots to Figure 6.6 indicates that edges have a negative cornerness measure while corners and interior points have a positive cornerness measure. A threshold value is required to distinguish between corners and interior points. From the figures it is clear that the interior points have a very small cornerness measure. In practice, the threshold must be set high enough to avoid the detection of false corners which may have a relatively large cornerness value due to noise. As for the Moravec operator, corners are the local maximum in the thresholded cornerness map.

Input: grayscale image, Gaussian variance (window typically has a radius of 3 times the standard deviation), k value, threshold T
Output: map indicating position of each detected corner

1. For each pixel (x, y) in the image calculate the autocorrelation matrix M:

2. Construct the cornerness map by calculating the cornerness measure C(x, y) for each pixel (x, y):

3. Threshold the interest map by setting all C(x, y) below a threshold T to zero.

4. Perform non-maximal suppression to find local maxima.

All non-zero points remaining in the cornerness map are corners.

The Plessey operator was applied to the three test images discussed in the Introduction.

Figure 6.10 shows the Plessey operator applied to the artificial test image (variance = 0.7, k=0.14, threshold=10). The Plessey operator detects all of the corners except one, but has poor localization at many of the corners and does detect a few false corners. It has a higher detection rate than the Moravec operator as it finds far fewer false corners.

Figure 6.11 shows the Plessey operator applied to the blocks test image. Parameters were chosen in order to detect most of the corners while trying to minimize the number of false corners detected. The Plessey operator does a reasonable job of finding the majority of true corners. Comparing these results to the Moravec operator again indicates that the Plessey operator has a better detection rate, although there are still a number of false corners detected and some corners are missed.

Figure 6.12 shows the Plessey operator applied to the house test image. Parameters were manually set high enough to avoid detecting corners due to the texture of the house. Clearly some corners have not been detected, but the results are reasonable and much improved over the Moravec operator.

The above results were obtained using a 5x5 window and manually picking a variance, k value, and threshold for each image that gave desirable results. To see the effect of different parameter values use the Corner Detection Applet. Results obtained here can also be compared with the results given on the Detection of Interest Points website.

Despite the widespread use of the Plessey corner detection algorithm, it suffers from a number of limitations.

The Plessey corner detector is one of the most computationally demanding corner detectors in use. Comparing the Moravec and Plessey corner detection algorithms shows they differ only in how the cornerness measure is calculated and this is true for most interest point corner detectors. The Plessey operator is far more expensive to compute than the Moravec operator mainly because it requires convolution with a Gaussian window.

Any algorithm using gradient or high-order derivative terms will likely be sensitive to noise. To understand why, consider the effect on the response of the Plessey operator to salt noise in the interior region of a black object. Any pixel affected by the salt noise will have a large gradient in all directions. That is, the salt noise is essentially an isolated pixel so has high intensity variation in all directions which is precisely how a corner is defined under both the Moravec and Plessey operators. The effect of noise is reduced by increasing the size of the Gaussian window as this causes more pixels to be considered when calculating the gradient, thus reducing the relative weight of any pixels affected by noise. However, increasing the Gaussian window size increases the computational demand of the algorithm.

The Plessey operator has poor localization at all junctions, except L-Junctions. Figure 6.13 demonstrates why the localization is poor at T-junctions where the two "smaller" regions have similar intensity, and the "larger" region has a very different intensity from the two smaller regions. The gradient perpendicular to the edge between the smaller regions will be constant until the Gaussian window starts to enter the larger region. At this point, the gradient perpendicular to the edge between the smaller regions starts to decrease, but the gradient parallel to this edge starts to grow. The cornerness measure is a function of these two gradients and is maximal somewhere along this edge and not at the true T-junction position.

Other factors leading to poor localization are beyond the scope of this website, but can be found in [9].

Like the Moravec operator, the Plessey operator has an anisotropic response. The Plessey operator is commonly misinterpreted to be rotationally invariant (i.e. have an isotropic response) as the autocorrelation matrix M is indeed rotationally invariant. However, the Plessey operator is anisotropic since the elements of M are calculated using only the horizontal and vertical gradients. Figure 6.14 illustrated that the corners detected vary greatly with rotation (both of these images were generated with the same parameter values!). [6] empirically verifies that the response of the Plessey operator varies most with a 45° degree rotation and proposes using derivatives of the Gaussian function to construct the elements of M which results in an isotropic corner detector. As illustrated in Figure 6.14, a side-effect of this anisotropic response is diagonal edges can be falsely detected as corners.

Figure 6.14: Rotational instability of Plessey operator due to anisotropic response

The Plessey corner detector is widely used thanks to its improved detection rate over the Moravec corner detector and high repeatability rate. However, it is computationally demanding, sensitive to noise since it relies on gradient information, has poor localization on many junction types, and is not rotationally invariant. Sensitivity to noise can be reduced by using a larger window size, but this further increases the computational demand of the algorithm and adversely affect localization. The significance of poor localization of certain junction types is application dependent and the widespread use of this algorithm suggests this limitation can be overcome. Even with its anisotropic response, it is still more robust in terms of repeatability than the Moravec corner detector and recent modifications to the Plessey algorithm have made the response isotropic which will help ensure the Plessey corner detector remains popular.