Corners and Keypoints

The problem is not “what is in this photo”, it is narrower and more mechanical than that: given a point in one photo, find the same physical point — the same rivet, the same window corner — in a second photo of the same scene shot from a different angle, a different crop, a different light. Solve that reliably and panorama stitching, 3D reconstruction, and tracking an object across video frames all become the same problem solved twice.

Comparing raw pixels does not work. The pixel that sat at row 40, column 120 in the first photo is not at the same coordinates in the second, and even if you found the right coordinates, its brightness has already changed with the light.

Look at a three-by-three patch of clear sky. Now look at the patch of sky next to it. They are identical, and so is every other patch of sky in the photo. A flat, uniform region carries no information about where inside itself it is — slide a window over it in any direction and the view does not change. It is unlocatable, in principle, not just in practice.

Now look at a corner — two edges meeting, like the top of a window frame. Slide the window in any direction and the view changes. Up, down, left, right, diagonally — every direction shows you something different. That property, not the sharpness of the angle, is what a corner detector is actually testing for, and it is exactly what makes a corner locatable again in a second photo.

An edge sits in between. Slide the window across an edge and the view changes sharply; slide it along the edge and it barely changes at all. That makes an edge locatable in one direction and ambiguous in the other, which is why detectors prefer corners, where no direction is ambiguous.

Here is that test as arithmetic, on a bright square. The score adds up how brightness changes across and down a small window, and is only large when it changes in both directions at once.

import numpy as np # A bright square on a dark background.image = np.zeros((20, 20))image[5:15, 5:15] = 1.0 gy, gx = np.gradient(image)   # brightness change down and across def corner_score(r, c, k=0.05):    # Sum gradient products over a 5x5 window (the "structure tensor").    win = (slice(r - 2, r + 3), slice(c - 2, c + 3))    a, b, d = (gx[win] ** 2).sum(), (gx[win] * gy[win]).sum(), (gy[win] ** 2).sum()    # Big only when brightness changes in two directions at once.    return (a * d - b * b) - k * (a + d) ** 2 for name, (r, c) in {"flat patch": (10, 10), "edge": (5, 10), "corner": (5, 5)}.items():    print(f"{name:10} score {corner_score(r, c):6.2f}")

The flat patch scores 0, the edge scores below 0, and the corner scores 1.74. This is the idea behind the Harris corner detector.

Finding a corner is only half the job. You still need to recognise it again in a second photo, and “the pixels near coordinate (140, 62)” is useless once the camera has moved. The answer is a descriptor: a small vector of numbers computed from the neighbourhood around the keypoint, built deliberately so that rotating the patch, brightening it, or scaling it changes the descriptor as little as possible.

A typical descriptor looks at the local pattern of gradient directions — which way brightness is changing, and how much, in the ring of pixels around the point — and bins that into a fixed-length numeric fingerprint. Two photos of the same corner, shot from different angles, should produce two descriptors that are close to each other in that numeric space, even though not one raw pixel value matches.

Detect a few hundred keypoints in each photo, compute a descriptor for each one, and matching the photos becomes matching the descriptors: for every keypoint in photo one, find the keypoint in photo two whose descriptor is numerically closest. Enough consistent matches and you can work out exactly how the camera moved between the two shots — which is the whole basis of panorama stitching.