Wiki
Core13 min read

Feature detection and matching

Corners, scale-invariant descriptors, ratio-test matching and RANSAC — the pipeline that gets from two images to a geometric transformation.

Show someone two photographs of the same building from different angles and they immediately see the correspondence: this window matches that window, the corners of that doorway match. The problem of feature matching is to make that effortless perception precise and repeatable, so that a program can find thousands of such correspondences and use them to compute the geometry between the two views.

The key insight is that not every pixel is worth remembering. Flat regions look the same everywhere and edges look the same along their length. What is distinctive is a corner — a point where the image changes sharply in two directions at once, so a small patch around it is unique.

Why corners and not edges

Slide a small window over a flat area and nothing changes in any direction; slide it along an edge and nothing changes along the edge. Slide it over a corner and the patch content changes no matter which way you move. That change in every direction is exactly the quantity Harris and Stephens measure, and it is why corners are the anchors of matching.

The widget computes the Harris corner response on a tiny patch, builds an 8-bin gradient-orientation descriptor around each corner, matches descriptors between the reference and a shifted query, and then uses RANSAC to find the translation that the consensus of matches agrees on.

Harris corners, orientation descriptors and a RANSAC translation vote — the query image is the reference shifted by the sliders, with independent noise.

reference

query (shifted)

true shift
(2, 1)
matches
1
RANSAC inliers
1 / 1
estimated shift
(2, 0)

match displacement scatter — consensus set clusters at the true shift

+Δy+Δx

Green dots are RANSAC inliers, red are rejected outliers. The ring is the fitted translation.

Illustrative: a 16×16 single-channel patch, translation-only model, hand-tuned Harris k and thresholds, and a simplified descriptor without SIFT scale-space. Real SIFT adds Gaussian pyramids, sub-pixel keypoints and orientation assignment; the pipeline shape — detect, describe, match, robustly fit — is exactly this.

Harris corners from the structure tensor

For image gradients Ix,IyI_x, I_y, sum the products over a small window ww:

M=∑w[Ix2IxIyIxIyIy2]=[ACCB].M = \sum_{w} \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix} = \begin{bmatrix} A & C \\ C & B \end{bmatrix}.

The eigenvalues of MM are both large exactly at a corner, both small in a flat region, and one large with one small on an edge. Harris avoids computing them with the response

R=det⁡(M)−k (trace⁡M)2=AB−C2−k(A+B)2,R = \det(M) - k\,(\operatorname{trace} M)^2 = AB - C^2 - k(A+B)^2,

with kk typically around 0.040.04. Peaks of RR above a small fraction of its maximum, thinned by non-maximum suppression, are the candidate keypoints.

Descriptors and the ratio test

A keypoint is a location; a descriptor is a small vector that summarises its neighbourhood so that corresponding keypoints have similar vectors even under rotation, scale and illumination change. SIFT builds a histogram of gradient orientations weighted by magnitude, normalises it, and (importantly) subtracts the dominant orientation so the descriptor rotates with the patch.

Given a reference descriptor and candidate query descriptors, matching takes the nearest neighbour in descriptor space. Lowe's ratio test keeps a match only if its distance is below a fraction (often 0.80.8) of the second-nearest distance — ambiguous matches, which tend to be wrong, fail the test.

Robust fitting with RANSAC

Even after the ratio test some matches are wrong. RANSAC fits a model by random sampling: draw a minimal set of matches, fit the transformation, count how many matches agree within a tolerance (the consensus set), and repeat, keeping the largest consensus. The final model is re-fit on its inliers. It is the standard defence whenever a fraction of your data is outlier.

Matching is not correspondence truth

A low descriptor distance means "looks similar", not "is the same physical point". Repeated textures — windows on a façade, tiles on a floor — produce many near-identical descriptors and will confuse any matcher. RANSAC filters gross outliers but cannot repair systematically ambiguous texture; that needs geometric verification at a higher level.

Illustrative vs real

The widget uses a 16×16 single-channel patch, translation-only motion, a simplified orientation-histogram descriptor and a Harris detector without scale-space. Real SIFT adds Gaussian pyramids for scale, sub-pixel keypoint refinement, orientation assignment and 128-dimensional descriptors; ORB, SURF and learned descriptors such as SuperPoint and SuperGlue are different trade-offs of the same detect–describe–match–verify skeleton.

Check yourself

Eduspheria wiki · Applied AI, Classical computer vision

0 / 5 answered

  1. 1A structure tensor has A = 9, B = 4, C = 0. With k = 0.04, what is the Harris response R?
    Numeric answer
  2. 2Where is the Harris response large?
    Multiple choice
  3. 3The ratio test rejects a match when its nearest-neighbour distance is too close to the second-nearest distance.
    True / false
  4. 4Which algorithm estimates a transformation by repeatedly fitting to random minimal subsets and keeping the largest consensus set?
    Short answer
  5. 5If a descriptor match is kept only when its best distance is strictly less than 0.8 × the second-best distance, and the second-best distance is 50, what is the largest kept best distance?
    Numeric answer

From the exam paper

Modeled on NITJ AI-502, AI-504 and AI-604, End-Sem May–June 2025

0 / 5 answered

  1. 1A 3×3 patch has top row 52, 55, 59 and bottom row 70, 75, 80; the middle row is multiplied by zero. A Prewitt y-filter weights the top row by −1 and the bottom row by +1. What is the filter response at the centre pixel?
    Numeric answer
  2. 2A Harris detector finds structure-tensor eigenvalues λ1 = 800 and λ2 = 50. Which region type is this?
    Multiple choice
  3. 3At a Difference-of-Gaussian keypoint the second derivatives are Dxx = 12, Dyy = 9 and Dxy = 4. What is the determinant of the Hessian matrix?
    Numeric answer
  4. 4For the same Hessian with Dxx = 12, Dyy = 9 and Dxy = 4, what is its trace?
    Numeric answer
  5. 5Using the SIFT ratio test with r = 10, should this keypoint (trace squared divided by determinant ≈ 4.79) be retained?
    Multiple choice

Where next: corners and matches give us correspondences between frames; we use them to localise and follow whole objects with detection and tracking.