Corners & Keypoints: Harris, ORB, SIFT
An edge is ambiguous along its own length — every point on a straight line looks like every other point on that line. A corner isn't. That's the entire reason this chapter exists.
11.1 Why corners, specifically
A good "landmark" for matching two images has to be locally unique — not just anywhere brightness changes. Flat areas don't count (nothing distinctive). Straight edges don't fully count either (slide along the edge and it looks the same). Corners are the sweet spot: distinctive no matter which way you nudge your view.
Consider sliding a small window over an image and asking: how much does the content inside the window change if I nudge it slightly in any direction? Over a flat region, nothing changes. Along a straight edge, sliding along the edge produces almost no change (the classic "aperture problem") even though sliding across it changes a lot. Only at a corner does the window's content change significantly no matter which direction you nudge it. That directional robustness is precisely what makes a corner locatable and matchable — and it's the intuition the Harris detector formalizes mathematically.
Imagine looking at a photo through a tiny round hole cut in a piece of paper — you can only see a small patch at a time. Slide that hole along a plain wall: no change, you can't tell where you are. Slide it along a straight fence line: it still looks the same fence-stripe pattern no matter where along the fence you are, so you can't tell exactly where you are along the fence, even though you could tell if you drifted off it. Slide it to the corner where two walls meet: now the view is unique — nudge the hole any direction at all and the picture visibly changes. That's why corners make good, locatable landmarks and edges alone don't.
11.2 The Harris corner detector
Harris turns "how much does the window change in every direction" into a single number per pixel by packing gradient information into a small 2×2 matrix and checking its eigenvalues. High score in both of two "directions of variation" means corner; the formula below is just a cheap shortcut for checking that.
Harris quantifies "change under a small shift" using the local structure tensor — a matrix built from the image gradients in a window, capturing how gradient direction varies locally:
The two eigenvalues of M summarize the local structure: both small → flat region; one
large, one small → edge (change is large in one direction only); both large → corner. Rather than
computing eigenvalues directly, Harris uses a cheaper combined score:
Picture the local gradients in a window as a scatter of little arrows, all pointing "uphill" in brightness. On a flat patch, the arrows are all near-zero length, pointing every which way — no strong direction, both eigenvalues small. On a straight edge, nearly every arrow points the same way, perpendicular to the edge — one strong direction, one weak one, so one big eigenvalue and one small one. At a true corner, the arrows point in genuinely different directions (because two edges meet at different angles) — both eigenvalues come out large. The eigenvalues are just a precise way of asking "do the gradient arrows here agree on one direction, or point multiple ways?"
Harris corners are rotation-invariant (the eigenvalue structure doesn't care which way the corner is rotated) but not scale-invariant — a corner that produces a strong response at one image resolution may be nearly invisible zoomed in, since the fixed window size samples a completely different amount of real-world structure. This is precisely the limitation that motivated SIFT.
11.3 Scale-invariance: SIFT's scale-space
Harris's fixed-size window fails if the same corner appears bigger or smaller in two images (zoomed in vs. zoomed out). SIFT fixes this by checking many blur levels at once, like checking a photo at several zoom levels simultaneously and picking whichever zoom level a feature looks most "corner-like" at.
SIFT (Scale-Invariant Feature Transform) detects keypoints by building a stack of the image blurred at increasing σ (a "scale-space"), then taking the Difference of Gaussians (DoG) between adjacent levels — a fast approximation of the Laplacian-of-Gaussian from Chapter 8. Keypoints are found where a pixel is a local extremum compared to its 8 spatial neighbors and the corresponding pixels one scale level up and down — 26 neighbors total. A keypoint found this way carries a natural characteristic scale: the σ level at which it was detected, which is what makes SIFT keypoints comparable across images at different resolutions or camera distances.
Once a keypoint's location and scale are fixed, SIFT assigns it a dominant orientation from the local gradient histogram, then builds its descriptor — a 128-dimensional vector from a 4×4 grid of 8-bin gradient orientation histograms — relative to that orientation. This is what makes SIFT descriptors rotation-invariant: the descriptor is computed in a coordinate frame that rotates along with the keypoint's own dominant gradient direction, so rotating the whole image produces the same descriptor values, just recomputed in the rotated frame.
11.4 ORB: engineering for speed
SIFT is accurate but slow. ORB trades some of that accuracy for roughly 100× less computation, by using simple pixel-brightness comparisons instead of gradient math — which is exactly why it's the realistic choice for an FPGA-constrained pipeline.
ORB (Oriented FAST and Rotated BRIEF) targets real-time and embedded use, trading some of SIFT's robustness for roughly two orders of magnitude less computation:
- FAST keypoint detection — a corner test based on comparing a pixel to a ring of 16 surrounding pixels, checking for a contiguous arc that's all clearly brighter or darker. No gradients, no eigen-decomposition — just pixel comparisons, extremely cheap.
- Orientation assigned via the intensity centroid of a patch (a cheap, single-pass approximation to a dominant gradient direction) rather than SIFT's gradient histogram.
- BRIEF descriptor, rotated to the assigned orientation ("Rotated BRIEF" / rBRIEF) — a 256-bit binary string, each bit the result of one greater-than/less-than comparison between two pixel intensities at fixed, learned positions in the patch. Comparing two ORB descriptors is a single Hamming distance (XOR + popcount) — far cheaper than SIFT's Euclidean distance over 128 floats, and the reason ORB is a natural choice whenever there's an FPGA-target real-time inference constraint.
11.5 Descriptor matching and the ratio test
Finding the closest match isn't enough — you need the best match to be clearly better than the second-best, or you probably just found an ambiguous, unreliable match rather than a real correspondence. The ratio test throws out exactly those wishy-washy matches.
Once keypoints and descriptors exist in both images, matching means, for each keypoint in image A, finding its nearest descriptor in image B (Euclidean distance for SIFT-like float descriptors, Hamming distance for ORB's binary descriptor). A raw nearest-neighbor match is unreliable on its own — Lowe's ratio test compares the distance to the best match against the distance to the second-best match, and rejects the match unless the best is meaningfully better than the second-best (typically requiring the ratio to be below about 0.7–0.8). This single filter removes most of the spurious matches that arise from repetitive or low-texture regions — both of which are common in DEM and LiDAR intensity imagery.
Imagine trying to identify a person in a crowd photo by matching their face against a database. If your best match scores 95% similar and the next-best candidate scores only 40% similar, you can be confident — there's a clear winner. But if your "best match" scores 95% and the runner-up also scores 93%, that's a red flag, not a good sign — it usually means the photo is ambiguous (bad lighting, a common face shape) rather than that you've found two great matches. The ratio test is exactly this "is the winner clearly ahead, or is this too close to call" check, applied to keypoint descriptors.
It's a frequently reported result that ORB and Harris matching between a DEM and orthoimage produce noisy, inconsistent lines. Given the material above, that's consistent with two compounding effects rather than a flaw specific to either detector: first, DEM "texture" is driven by elevation discontinuities while orthoimage texture is driven by reflectance — so the same physical corner (a crater rim) can produce a strong Harris/FAST response in one modality and a weak one in the other, purely because the two signals don't co-vary in intensity even where they co-vary in geometry. Second, ORB's BRIEF descriptor encodes raw intensity comparisons, which are exactly the quantities that differ most between the two modalities — a geometrically identical corner can still produce a very different binary descriptor across modalities. This is the core argument, later in this reference (Chapter 13), for why cross-modal registration usually needs either a modality-bridging representation (e.g. matching on slope/gradient-direction rather than raw intensity) or a learned descriptor trained explicitly to be invariant to the LiDAR/optical intensity gap — not just a better handcrafted detector.