A Combined Corner and Edge Detector

“A Combined Corner and Edge Detector” is a short paper by Chris Harris and Mike Stephens of Plessey Research Roke Manor, presented at the fourth Alvey Vision Conference in Manchester in 1988. It started from Moravec’s corner detector, fixed three of its weaknesses with an analytic expansion of the window-shift test, a Gaussian window, and a new response function, and classified every pixel as corner, edge, or flat from the local auto-correlation matrix with a single response, $R = \det M - k \, (\operatorname{tr} M)^2$. The corner half of that proposal became the Harris corner detector, one of the most widely used feature detectors; the edge half, which gave the paper its title, did not survive in the same way.

Problem

The paper came out of Alvey Project MMI149, which aimed to understand unconstrained outdoor scenes (roads, buildings, trees, bushes) by motion analysis of a monocular image sequence from a mobile camera. Harris’s earlier work with Pike had tracked isolated feature points through such sequences and estimated their 3D positions with Kalman filters; a companion paper at the same conference by Stephens and Harris names the resulting system DROID. Corners were attractive because they are discrete and can be tracked explicitly, but a set of points gives no connectivity, and the authors wanted edges to build wire-frame descriptions and delimit candidate surfaces.

Edges were hard to use for motion. With unknown camera motion, the aperture problem rules out matching individual edge pixels, and grouping edges into straight-line fragments or parametric curves fails on curved and textured edges, which break up differently in each frame. The authors argued that full 3D recovery of curved edges may be unattainable anyway, and that their connectivity is what matters. That left a narrower requirement: edge filtering that is consistent from frame to frame. Their figures show that the Canny operator, which they cite as Canny’s 1983 MIT technical report, did not provide it. It was not designed for corners and junctions, and in the bushes of their outdoor sequence, edges with responses near the threshold changed topology between frames, so that after linking and junction completion few edges could be matched by eye. Their proposal was to detect corners and edges together, so that junctions would be edges meeting at corners.

Contribution

• A diagnosis of Moravec’s operator. Moravec’s detector computes the sum of squared differences between the image patch under a binary rectangular window and the patch shifted by one pixel in four directions, and marks local maxima of the minimum over shifts. The paper names three faults: an anisotropic response, because only shifts at multiples of 45 degrees are tested; a noisy response, because the window is binary and rectangular; and too ready a response to edges, because only the minimum is used.
• The auto-correlation matrix. A first-order Taylor expansion covers all small shifts at once and turns the shift error into a quadratic form $E(x, y) = (x, y)\, M \,(x, y)^\top$ with a $2 \times 2$ matrix $M$ of windowed gradient products. A Gaussian window replaces the binary one. The paper interprets $M$ as describing the shape of the local auto-correlation function at the origin, with eigenvalues proportional to its principal curvatures.
• A response function. Flat, edge, and corner regions correspond to two small, one large, and two large eigenvalues. Because raising contrast scales both eigenvalues by the same factor, the paper argues that the region boundaries in eigenvalue space should be invariant to that scaling, and it proposes $R = \det M - k \, (\operatorname{tr} M)^2$, which avoids an explicit eigendecomposition. The authors call it an “inspired formulation” and give no derivation beyond this reasoning.
• Edges from the same response. Negative values of $R$ mark edge regions, so one operator yields both feature types.

Method

Gradients were computed with the difference mask $(-1, 0, 1)$ and its transpose, and the products $X^2$, $Y^2$, and $XY$ were smoothed by the window to give the entries $A$, $B$, $C$ of $M$. $R$ is positive in the corner region and negative in the edge regions, and a pixel is flat when the trace falls below a chosen threshold. The paper does not state a value for $k$; later implementations had to choose one, and scikit-image’s corner_harris, for example, defaults to 0.05.

A pixel with positive response becomes a corner if it is a local maximum of $R$ among its eight neighbors. A pixel with negative response becomes an edgel if it is a local minimum of $R$ in the $x$ or $y$ direction, whichever has the larger gradient magnitude, which yields thin edges. Low and high thresholds then give hysteresis on edges, producing a five-level image (background, two corner classes, two edge classes). A clean-up stage, which the authors compare to junction completion, deletes spurs and short isolated edges, bridges short gaps, and links edge ends to corner pixels in the corner regions, giving a connected edge-vertex graph.

Results

The evaluation is qualitative. On a test image, the paper shows the corners found by Moravec’s operator, by the operators of Beaudet and of Kitchen and Rosenfeld, and by the new detector side by side, without a numerical comparison. On a pair of frames from an outdoor sequence it shows the raw corner and edge classification and the completed edge-vertex graph. Edges mostly end in corner regions, and many corners in the bushes are not connected to any edge because they lie in textured areas. The authors state that many corners and edges are directly matchable between the frames, although this is not quantified, and that the junction completion stage was still rudimentary and adaptive thresholding remained to be done. No timing or matching statistics are reported.

Impact

The corner response outlived the system it was built for. Shi and Tomasi (1994) derived a feature-selection criterion from the $2 \times 2$ system solved by a window tracker and accepted a window when the smaller eigenvalue of that matrix exceeds a threshold; it is the same matrix, reached from the tracking side rather than from the geometry of corners.

Systematic comparisons came later. Schmid, Mohr, and Bauckhage (2000) introduced repeatability and information content as criteria and compared several detectors, including Harris and a detector by Förstner that also builds on the auto-correlation matrix. They found that computing the derivatives with Gaussian derivative filters instead of the original difference mask significantly improved Harris’s repeatability, and that this improved version was better than or equivalent to the other detectors in all their repeatability tests and gave the highest information content, while degrading under large scale changes.

That scale weakness motivated the next generation. Mikolajczyk and Schmid (2004) computed a scale-adapted Harris measure at several scales and kept points where a normalized Laplacian peaks over scale (Harris–Laplace), then iterated the second-moment matrix to adapt each neighborhood to affine deformations (Harris–Affine). They noted that Harris-based points respond to corners and highly textured points, while the difference-of-Gaussians detector of SIFT responds mainly to blobs, so the two give complementary features.

Speed was the other pressure. Rosten and Drummond (2006) introduced FAST, a learned intensity-comparison detector, and reported that it processed live PAL video in under 7 percent of the available time where the Harris detector needed 120 percent; in their repeatability tests on 3D scenes, FAST outperformed the existing detectors they compared, Harris among them, when more than about 200 corners per frame were needed.

Limitations

The authors listed their own open issues: rudimentary junction completion and fixed thresholds. Other limits follow from the formulation. The response depends on a constant $k$ the paper leaves unspecified. Because $R$ scales with the fourth power of contrast, absolute thresholds do not transfer between images. The edge classification takes local minima only along the $x$ or $y$ axis, a coarser thinning than non-maximum suppression along the gradient direction. The detector works at a single scale fixed by the window, and the results rest on figures rather than measurements.

What Came After

Later evaluations and implementations treat the method as a corner detector: Schmid et al. and Mikolajczyk and Schmid use only the corner response, and scikit-image’s corner_harris returns the response map from which corner peaks are extracted, with no edge classification. The matrix itself, also called the structure tensor or second-moment matrix, became a common tool: it is the system matrix of the Lucas–Kanade method, the basis of Shi–Tomasi feature selection, and the shape estimator in affine-adapted detectors. Scale-invariant detectors such as SIFT and Harris–Laplace addressed matching across scale changes, and fast detectors such as FAST addressed frame-rate budgets, the two directions in which the 1988 detector was most limited.