Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 46 ยท Features and Matching

Corner Detection

Learn why corners make good landmarks, how the structure tensor tells flat, edge and corner apart, and write the Harris detector with non-maximum suppression.

If you want to match two photos of the same scene, you need landmarks: points that can be found again in both pictures. A flat patch of wall is a bad landmark, because every neighbouring patch looks the same. A point on a straight edge is better, but you can slide along the edge and it looks identical, so its position is ambiguous. A corner, where two edges with different directions meet, is the first kind of point that is truly pinned down: move in any direction and the picture changes.

This lesson derives that idea in a few lines of math, then implements the classic Harris corner detector from scratch with NumPy and SciPy. It relies on image gradients and Gaussian smoothing. In the next lesson you will describe and match the points you find here.

Why corners

Take a small window around a pixel and ask: how much does the window's content change if I shift the window a little? Three cases:

  • Flat region. Shifting in any direction changes nothing.
  • Edge. Shifting along the edge changes nothing; shifting across it changes a lot.
  • Corner. Shifting in any direction changes the content a lot.
flowchart LR
    F["Flat<br/>no change in any direction"] --> R1["both eigenvalues small"]
    E["Edge<br/>change in one direction only"] --> R2["one large, one small"]
    C["Corner<br/>change in every direction"] --> R3["both large"]

The three window types and what the structure tensor reports for each.

The Harris detector turns this into numbers using image gradients. Let Ix and Iy be the horizontal and vertical derivatives. For a window, add up the products into a 2 by 2 matrix called the structure tensor (also called the second-moment matrix):

TEXT
M = [ sum(Ix*Ix)   sum(Ix*Iy) ]
    [ sum(Ix*Iy)   sum(Iy*Iy) ]

Its two eigenvalues describe how strongly the window changes along its two principal directions. Both near zero means flat, one large and one small means an edge, and two large eigenvalues means a corner. The next demo computes M for three hand-made 9 by 9 patches and prints the eigenvalues.

Python Flat, edge and corner patches

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The flat patch has no gradients at all, the edge has one large eigenvalue and one zero, and the corner has two comparable ones. The last column, R, is the Harris response, explained next.

The Harris response

Computing eigenvalues for every pixel is slightly wasteful, and Harris and Stephens found a shortcut. The determinant of M equals the product of the eigenvalues, and the trace equals their sum, and neither needs an eigen-solver:

TEXT
R = det(M) - k * trace(M)^2

with k a small constant, typically 0.04 to 0.06. The sign tells the story:

  • R is large and positive when both eigenvalues are large (corner).
  • R is negative when one eigenvalue dominates (edge). In the demo above the edge patch gave a negative R.
  • R is near zero when both are small (flat).

For the full image, you compute Ix and Iy once, then form the three product images Ix*Ix, Iy*Iy and Ix*Iy. Instead of a hard box window you smooth each product image with a Gaussian, so nearby pixels count more. That Gaussian smoothing is the "sum over the window" from the formula above, done for all windows at once.

Harris from scratch

The function below is the whole detector in eight lines. The test image has a rectangle and a triangle, so we expect four plus three corners.

Python Harris response on a synthetic image

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the response picture. Each corner is a bright blob rather than a single pixel, and the straight edges are slightly negative (dark in the colour map). The blobs contain over a hundred pixels above the 10% level, but you want exactly one point per corner. That is the job of non-maximum suppression.

Non-maximum suppression and thresholds

A corner candidate must pass two tests:

  1. Strong enough: R exceeds a threshold. Because the scale of R depends on image contrast (here it is around 0.0005), it is practical to use a threshold relative to the largest response, such as 0.1 * R.max().
  2. Locally largest: no pixel within a given radius has a bigger response. ndi.maximum_filter(R, size=...) replaces every pixel with the maximum of its neighbourhood, so maximum_filter(R) == R is true exactly at local peaks.

Combining the two yields a short list of coordinates. The demo also shows how the threshold changes the result.

Python Picking corners and tuning the threshold

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All seven true corners are found, and each is at most a pixel inside the shape's border because of the smoothing. With a very strict threshold of 0.5 only the four rectangle corners survive: the triangle has lower contrast (0.8 instead of 1.0) and its acute corner angle gives a weaker response. That is a general lesson. A single global threshold trades missed corners against false ones, and on real photos you usually keep the best N corners by response instead of a fixed level.

Choosing parameters

  • Gradient smoothing (the first Gaussian). More smoothing suppresses noise but moves and blurs corners.
  • Window sigma (the second Gaussian). A larger window averages gradients over more pixels. Corners then become wider blobs and nearby corners can merge.
  • k. Larger k penalizes edges more strongly and finds fewer corners; 0.04 to 0.06 is the usual range.
  • NMS radius. It sets the minimum spacing between corners. Too small gives clusters of duplicates around one corner, too large drops legitimate close pairs.
  • Textured regions. On a noisy or highly textured surface the response peaks everywhere. Real pipelines choose the strongest N points, often forcing an even spread over the image.

Harris is not scale invariant. A corner on a very smooth, rounded shape can vanish when you zoom out, and a rounded blob can look like a corner when you zoom in. To handle size changes, run the detector at several pyramid levels, as in image pyramids, and keep points that are strong across scales.

Harris is rotation invariant (the eigenvalues do not change when the image rotates) and fairly robust to brightness shifts, which is why it is still taught as the reference corner detector. Faster alternatives such as FAST test a ring of 16 pixels around each candidate and are common in real-time systems, but they follow the same plan: find a score, then keep the local maxima.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which description matches the structure tensor of a point on a straight edge?

    Gradients on an edge all point across it, so the image changes in only one direction. That gives one large eigenvalue and one near zero.
  2. 2. What does a strongly negative Harris response R usually indicate?

    R = det - k * trace^2. When one eigenvalue dominates, the determinant is small but the trace squared is large, so R is negative.
  3. 3. Why do we apply non-maximum suppression after thresholding the Harris response?

    A corner produces a cluster of high responses. Keeping only pixels that are the maximum of their neighbourhood leaves one point per corner.
  4. 4. A student sets an absolute Harris threshold that works on one photo, but it finds almost nothing on a low-contrast photo. What is a better strategy?

    The size of R scales with image contrast squared, so absolute thresholds do not transfer. A relative threshold or a fixed number of best points adapts to each image.

Summary

  • A good landmark changes in every direction when you shift a small window; corners do, edges and flat regions do not.
  • The structure tensor sums gradient products over a window; two large eigenvalues mean a corner, one means an edge, none means flat.
  • The Harris response R = det(M) - k * trace(M)^2 avoids computing eigenvalues; it is positive at corners and negative at edges.
  • In code: smooth, take gradients, Gaussian-smooth the three product images, then combine them with array arithmetic.
  • Keep points that exceed a relative threshold and are local maxima (maximum_filter(R) == R).
  • Harris is rotation invariant but not scale invariant; use pyramids for size changes.

Next, describe the points you found and match them between two images in Keypoint Descriptors and Matching.