Skip to the lesson
FixTheRobot Explore Robotics / Perception / P4 Classical Feature Detection and Matching / P4-T1

Perception · Theory · P4

P4-T1 — Corners, Edges and Local Features

A good feature can be found again. Corners can be located in two directions; edges and flat areas cannot.

  • Lesson 1 of 6
  • Module 4: Classical Feature Detection and Matching
  • Theory
  • About 10 minutes to read

To relate two images, or two moments of a video, a robot needs points it can recognise again: local features. Not every pixel qualifies. A flat wall looks the same everywhere, and a straight edge looks the same along its whole length, so neither can be pinned down. A corner can. This lesson explains why, derives the Harris detector from the idea of sliding a small window, shows the numbers for a flat region, an edge and a corner, and describes the other detectors and what they trade.

Learning objectives

After this lesson, you should be able to:

  • Explain the aperture problem and why corners make better features than edges and flat regions.
  • List the properties of a good local feature: repeatability, distinctiveness, locality and efficiency.
  • Compute the Harris response from the structure tensor and classify flat, edge and corner from its eigenvalues.
  • Name other detectors (Shi–Tomasi, FAST, blob detectors) and the problem of scale.

The idea: which small windows can you find again?

Look at an image through a small window and try to say where in the image the window is. In a flat region you cannot: every position looks the same. On a straight edge you can say how far across the edge you are, but not how far along it: the window can slide along the edge and look the same. This is the aperture problem. At a corner, sliding the window in any direction changes what you see, so the position is determined.

Flat region, edge and corner seen through a small windowThree square windows. The first is flat: a window can slide in any direction and nothing changes. The second has a straight edge: sliding along the edge changes nothing, so the position along it is ambiguous. The third has a corner: sliding in any direction changes the content, so it can be located.no change in any directionchange in one direction onlyslides along the edge unnoticedchange in both directions flatedgecorner
The same small window on a flat region, an edge and a corner. Only the corner changes in every sliding direction, so only the corner can be located.

A feature is a place where the image is distinctive in every direction. That is what lets a program find it again.

What makes a good local feature

PropertyMeaningWhy a robot cares
RepeatabilityFound again when the view, light or scale changesA feature that appears in one frame only cannot be matched
DistinctivenessIts neighbourhood differs from most others (for matching)Unique features give unambiguous matches
LocalityDepends on a small region onlySurvives occlusion and clutter: partly hidden objects still have features
AccuracyPosition is precise, ideally to a fraction of a pixelPose and depth estimation use these positions
EfficiencyFast to compute and compactMust run at frame rate on the robot
QuantityEnough features, well spread over the imageGeometry is poorly determined if features cluster in one corner

Corners satisfy the first four well for man-made scenes. In natural scenes (grass, foliage, rocks) the useful features are blobs and textured patches, found by blob detectors.

The mathematics: the structure tensor and the Harris response

Slide a window w by a small shift (u, v) and measure how much the image changes:

change of the window under a shift
E(u, v)=∑x, y w(x, y)[I(x+u, y+v)−I(x, y)]2E(u,\,v)=\sum _{x,\,y}\,w(x,\,y)[I(x+u,\,y+v)-I(x,\,y)]^{2}

For a small shift, a first-order Taylor expansion I(x + u, y + v) ≈ I + Ixu + Iyv gives

structure tensor
E(u, v)≈[u v] M[u v]⊤E(u,\,v)\approx [u\,v]\,M[u\,v]^{\top}
M=∑ w[Ix2Ix IyIx IyIy2]=[abbd]M=\sum \,w\begin{bmatrix}\mathrm{Ix}^{2} & \mathrm{Ix}\,\mathrm{Iy} \\ \mathrm{Ix}\,\mathrm{Iy} & \mathrm{Iy}^{2}\end{bmatrix}=\begin{bmatrix}a & b \\ b & d\end{bmatrix}
Ix, Iy
image gradients along x and y at a pixel (Lesson P2-T5).
w(x, y)
the window weights (a box or a Gaussian) that sum the products over the neighbourhood.
M
the structure tensor (second-moment matrix): a 2 × 2 summary of how the gradient directions are distributed around the pixel.
a, b, d
the three numbers Σ w Ix², Σ w Ix Iy, Σ w Iy².

The shape of E(u, v) is given by the eigenvalues λ1 ≥ λ2 of M:

Regionλ1λ2Meaning
FlatsmallsmallE is small in every direction: not locatable
EdgelargesmallE changes across the edge but not along it: locatable in one direction
CornerlargelargeE changes in every direction: locatable

Harris and Stephens (1988) scored this without computing eigenvalues, using the determinant and the trace (det = λ1λ2, trace = λ1 + λ2):

Harris response
R=det⁡(M)−k⋅trace⁡(M)2=(a d−b2)−k(a+d)2R=\det (M)-k\cdot \operatorname{trace} (M)^{2}=(a\,d-b^{2})-k(a+d)^{2}
k≈0.04 to 0.06k\approx 0.04\,\text{to}\,0.06

R is large and positive for corners, negative for edges and near zero for flat regions. Shi and Tomasi (1994) use the smaller eigenvalue λ2 directly, which needs no constant k and has a clearer meaning: the corner is as good as its weaker direction.

Other detectors, briefly

  • FAST: tests whether a contiguous arc of pixels on a circle around the candidate is all brighter or all darker than the centre. Very fast; it is the corner detector inside ORB.
  • Blob detectors (Laplacian of Gaussian, difference of Gaussians): respond to bright or dark spots of a given size. SIFT and SURF detect blobs at many scales.
  • Learned detectors: neural networks trained to output repeatable keypoints and descriptors; they can be more robust to light and viewpoint and need a GPU or an accelerator on a robot.

Scale

A corner seen from twice as far looks like a different, smaller corner: in a window of fixed size, a gentle bend becomes a sharp corner, and a sharp corner shrinks to a dot. A detector with a single window size is not scale invariant. Scale-space methods compute the response at several smoothing levels (an image pyramid or Gaussian scale space) and keep points that are maxima both in position and in scale. The feature then comes with a scale, which the descriptor uses to normalise its patch (Lesson P4-T2).

A worked example: the numbers for flat, edge and corner

Take three idealised windows. Suppose the gradient strength is 30 grey levels per pixel and the window has 9 pixels.

Windowa = Σ Ix²b = Σ Ix Iyd = Σ Iy²λ1, λ2R (k = 0.05)
Flat0000, 00
Vertical edge (gradient in x only)8100008100, 0-3280500
Corner (gradients in both)4050040504050, 405013122000
Diagonal edge4050405040508100, 0-3280500

The total gradient energy a + d is the same (8100) for the vertical edge, the corner and the diagonal edge: it cannot tell them apart, which is why the starter in Lab P4-L1 Stage 2 (score = a + d) marks edges as corners. The Harris score separates them: strongly positive (13122000) for the corner and negative (-3280500) for the edges. Note also that the diagonal edge has b ≠ 0, but its eigenvalues are (8100, 0): it is still an edge. This is why the eigenvalues, not the entries of M, carry the meaning.

Choosing and selecting features

The response is not yet a list of features. A practical detector (Lab P4-L1, Stage 3) adds a threshold relative to the strongest response, non-maximum suppression to keep one point per corner and a limit on the number of points, often with a spatial grid so that features are spread over the image and not clustered on the most textured object. Repeatability is then measured on pairs of images with a known transform: the fraction of features in the first that have a feature within a pixel or two of their true position in the second.

What typically goes wrong

SituationWhat happens to the detector
Blur or noiseGradients shrink or are corrupted: fewer corners, more noise points
Low contrast or poor lightResponses fall below the fixed threshold: no features at all
Repetitive texture (a grid of tiles)Many equally good corners, but not distinctive
Textureless surfaces (a white wall)No corners: the robot is blind to that region
Zoom or large viewpoint changeCorners change appearance and may not be re-detected
Moving objectsGood corners on things that do not describe the robot’s motion

Engineering implications and limitations

Spread the features. Divide the image into a grid and keep the strongest few in each cell. Geometry estimation is much better conditioned when features cover the image than when they cluster on one textured object.

Normalise the threshold. A threshold on the absolute response depends on image contrast, which depends on the exposure. A threshold relative to the strongest response, or a fixed number of features per cell, adapts to the light (Lessons P2-T6 and P4-T1).

Use a pyramid. Detect on several scales so that features survive zoom and distance changes, and so that coarse scales give stable features in blurred frames. Production detectors (ORB, SIFT) all do.

Measure repeatability on your data. Take pairs of frames from your robot with known motion or a known transform, and compute the repeatability and the localisation error of the detector. A detector that is good on benchmark images can be poor on a particular camera’s blur and noise.

Know what you are blind to. A corridor of plain walls, a floor with no texture, glass walls and uniform snow or sand all lack corners. Detect this condition (too few features, uneven spread) and fall back on other sensing.

Mind the cost. Harris with a Gaussian window and non-maximum suppression on a 640 × 480 image takes a few milliseconds on a desktop CPU and tens on a small embedded one. FAST is several times faster and often preferred on robots with limited compute.

Common misconceptions

“A feature is any bright or dark spot.”

Brightness alone does not make a point locatable. A feature must be distinctive in its structure in two directions, and stable under changes of light and view.

“Edges are good features because they are easy to see.”

An edge pins down position only across itself. Matching an edge point to another point along the same edge is ambiguous.

“More features are always better.”

More features cost time and add false matches. A moderate number, well distributed and distinctive, beats a large number of clustered, weak ones.

“Harris corners are scale invariant.”

They are not. The same corner at a different distance may not be detected at all. Scale-space detectors add this.

Engineering takeaways

  1. The aperture problem: only points that change in two directions can be located. Corners qualify, edges and flat regions do not.
  2. Good features are repeatable, distinctive, local, accurate and efficient, and should be spread over the image.
  3. The structure tensor M summarises gradient directions; its eigenvalues classify flat (both small), edge (one large) and corner (both large).
  4. Harris R = det(M) − k·trace(M)² avoids the eigenvalues; Shi–Tomasi uses the smaller one; FAST is a fast circle test; blob detectors work across scales.
  5. Select features with a relative threshold, non-maximum suppression and a spatial grid; measure repeatability on pairs with a known transform.

References and further reading

Original papers and a standard text; the worked table was computed for this lesson.

  • Harris, C. and Stephens, M. (1988). A combined corner and edge detector. Proceedings of the Alvey Vision Conference: the Harris detector.
  • Shi, J. and Tomasi, C. (1994). Good features to track. IEEE CVPR: the minimum-eigenvalue criterion.
  • Rosten, E. and Drummond, T. (2006). Machine learning for high-speed corner detection. ECCV: the FAST detector.
  • Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision 60(2): scale-space detection with difference of Gaussians (SIFT).
  • Szeliski, R. (2022). Computer Vision: Algorithms and Applications, 2nd ed. Springer: chapter 7, feature detection and matching.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

A structure tensor has eigenvalues 5200 and 40 in one window and 3100 and 2900 in another. Which window is a corner, which an edge, and which Harris scores would you expect (k = 0.05)?

Explanation

The second (3100, 2900) is a corner: both eigenvalues are large. The first (5200, 40) is an edge: one large, one tiny. Harris R = λ1λ2 − k(λ1 + λ2)²: for the first, 208 000 − 0.05 × 27 457 600 ≈ −1.16 million (negative); for the second, 8 990 000 − 0.05 × 36 000 000 = 7 190 000 (large positive).

Question 2

A robot navigates a long corridor with plain white walls and a polished floor. Why does a corner-based visual system struggle, and what would you add?

Explanation

There are almost no corners: walls and floor are textureless and the reflections of lights move, so the detector finds few or unstable features, and those found sit on the doors and signs at intervals. Add another sensor (LiDAR, odometry or IMU), active illumination or projected texture, or deliberately place markers.

Question 3

Why do detectors use non-maximum suppression, and what goes wrong without it?

Explanation

The response around a true corner is a hill several pixels wide, and every pixel on it is above the threshold. Without suppression the strongest N points are all neighbours of the best corner, so the list contains one real corner many times and misses the others.

What’s next

Next: describing the neighbourhood of a feature so that it can be matched with the feature in another image.

Practice this lesson

Detect Image Features

Implement a corner detector and tune it for repeatability.

Next lesson

P4-T2 — Feature Descriptors and Matching

Build a patch descriptor and match by distance with a ratio test.

Nothing below is required to finish this lesson.