Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 46 ยท Features and Matching

Keypoint Descriptors and Matching

Describe keypoints with normalized patches, match them by nearest neighbour with the ratio test, and use RANSAC to reject outliers and estimate a transform.

Finding keypoints is only half of the job. To line up two photos, track an object, or stitch a panorama, you have to say which keypoint in image A is the same physical point as which keypoint in image B. The coordinates alone cannot tell you, so each keypoint gets a descriptor: a vector of numbers that summarizes how its surroundings look. Two keypoints that see the same scene point should have descriptors that are close to each other.

This lesson builds the whole chain with NumPy on a synthetic pair of images: detect Harris corners (previous lesson), describe them with normalized patches, match them by nearest neighbour with the ratio test, and finally clean up the wrong matches with RANSAC while estimating the transform between the images. Industrial descriptors such as SIFT and ORB are explained at the end, read-only, because the idea is the same.

What a descriptor must do

A good descriptor is:

  • Distinctive: different points get different vectors.
  • Repeatable: the same point gets nearly the same vector when the camera moves, the light changes, or sensor noise appears.
  • Compact: short vectors make matching fast.

The simplest descriptor is the raw patch: cut a square of pixels around the keypoint and flatten it. That is distinctive but fragile, because adding brightness or contrast changes every number. A cheap and effective repair is to normalize the patch: subtract its mean and divide by its standard deviation (a z-score). The result does not change if the lighting is a * pixel + b.

Distance metrics

Matching means measuring how different two descriptors are. The common choices:

  • L2 (Euclidean) distance: the square root of the sum of squared differences. The default for real-valued descriptors.
  • L1 (Manhattan) distance: the sum of absolute differences. Less sensitive to a few big differences.
  • Cosine distance: one minus the cosine of the angle between the vectors; it ignores vector length.
  • Hamming distance: the number of bits that differ. It is used for binary descriptors (ORB, BRIEF) and is extremely fast, because a computer can XOR two bit strings and count the ones.
Python Distances and the value of normalization

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 two patches look nothing alike in raw numbers (distance 0.83), yet after normalization they are identical to rounding error, because one is an affine brightness change of the other.

Matching by nearest neighbour

Given descriptor sets dA (m vectors) and dB (n vectors), build the m by n table of distances and choose, for each row, the column with the smallest value. With NumPy broadcasting the whole table is one expression:

Python
D = np.linalg.norm(dA[:, None, :] - dB[None, :, :], axis=2)

Nearest-neighbour matching has a flaw: it always returns an answer, even when the true partner is not in the other image (it may be out of view). Those matches are wrong, and they look just as confident as the right ones. A famous remedy is the ratio test. For each keypoint, compare the distance to the best match with the distance to the second-best match. If the best is much closer than the runner-up (ratio below about 0.8), the match is distinctive. If the two are almost equally close, the point is ambiguous and should be dropped.

flowchart LR
    K["keypoint in A"] --> B1["best match in B<br/>distance d1"]
    K --> B2["second best<br/>distance d2"]
    B1 --> T{"d1 / d2 < 0.8 ?"}
    B2 --> T
    T -->|yes| Y["keep the match"]
    T -->|no| N["discard: ambiguous"]

The ratio test keeps only matches whose best candidate is clearly better than the runner-up.

A synthetic pair of images

To check our answers we need ground truth, so we build a pair where we know exactly how points moved. Take a larger random field, smooth it so that it looks like texture, and crop two windows that overlap but are offset by (4, -6) pixels. Image B is also dimmer and noisier. A point at (y, x) in A must be at (y - 4, x + 6) in B.

The demo detects up to 60 Harris corners in each image, describes each with a normalized 13 by 13 patch, matches them, and counts how many matches are correct by checking against the known shift.

Python Describe, match and apply the ratio test

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.

In this run all 29 keypoints of A get a nearest neighbour, but only 19 of those are correct. The ratio test removes 6 wrong matches and loses no correct one, leaving 23 matches of which 19 are right, so the set is cleaner but not perfect. Some keypoints in A simply lie outside image B after the shift, and a few wrong matches are confident anyway. You need a method that tolerates a minority of bad matches. That method is RANSAC.

RANSAC: voting for a model

A set of matches is supposed to obey a single geometric rule, for instance "B equals A moved by an affine transform". If you fit the transform by least squares to all matches, a few wild outliers drag the answer away. RANSAC (random sample consensus) sidesteps this by fitting to tiny random subsets:

  1. Pick the minimal number of matches that determine the model (3 for an affine transform, since it has 6 unknowns and each match gives 2 equations).
  2. Fit the model to just those matches.
  3. Count the inliers: matches whose predicted position lies within a few pixels of the observed one.
  4. Repeat many times and keep the model with the most inliers.
  5. Refit on all inliers of the winner for a precise final answer.
flowchart TB
    A["matches from the ratio test"] --> S["sample 3 matches at random"]
    S --> F["fit an affine model"]
    F --> C["count inliers within 2 px"]
    C --> K{"best so far?"}
    K -->|yes| M["remember the model"]
    K -->|no| S
    M --> S
    M --> R["after many rounds: refit on the inliers"]

RANSAC trusts the majority: wild matches almost never agree with each other on one model.

The key insight is that a bad match is wrong in its own random way, so outliers rarely agree with one another, while good matches all agree with the true transform.

Python RANSAC estimates the transform and rejects outliers

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 recovered linear part is the identity (no rotation, no scaling, which is correct because we only shifted) and the translation lands near the true (-4, 6). Plotted, the green lines are all parallel, and the red ones cross them at odd angles, which is the visual signature of wrong matches. Each rejected line is a mistake that would otherwise have damaged a least-squares fit.

For stitching photos you would fit a homography (8 parameters, 4 matches per sample) instead of an affine map. The loop is identical; only the model and the minimal sample size change. The number of rounds needed grows quickly as the share of good matches falls, so also lower your outlier rate with the ratio test.

SIFT, ORB and friends (read-only)

Real matchers replace the plain patch with more robust descriptors. You cannot run them in this browser runner (OpenCV is not available), so here are the ideas:

  • SIFT finds blobs with a difference-of-Gaussians pyramid (image pyramids), estimates a dominant gradient direction, rotates the patch to it, and summarizes the gradients in a 4 by 4 grid of 8-bin orientation histograms: a 128-number vector that tolerates scale change, rotation and moderate lighting changes.
  • ORB detects corners with FAST at several pyramid levels, orients them with an intensity centroid, and builds a 256-bit BRIEF-style descriptor from pairs of pixel comparisons. It is matched with Hamming distance and is fast enough for phones.
  • Learned descriptors (SuperPoint, and matchers such as LightGlue) use neural networks trained on many image pairs; they are the modern default in demanding applications.

With OpenCV the call pattern looks like this (not executed here):

Python
# orb = cv2.ORB_create(nfeatures=500)
# kp1, des1 = orb.detectAndCompute(img1, None)
# kp2, des2 = orb.detectAndCompute(img2, None)
# matcher = cv2.BFMatcher(cv2.NORM_HAMMING)
# knn = matcher.knnMatch(des1, des2, k=2)          # two nearest neighbours for the ratio test
# good = [m for m, n in knn if m.distance < 0.75 * n.distance]
# H, mask = cv2.findHomography(src_pts, dst_pts, cv2.RANSAC, 3.0)

It is exactly the pipeline you just wrote: describe, two nearest neighbours, ratio test, RANSAC.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why do we z-score normalize a patch descriptor?

    Subtracting the mean removes a brightness offset and dividing by the standard deviation removes a contrast factor. Rotation is not handled by this step.
  2. 2. What does the ratio test compare?

    If the best match is not clearly closer than the runner-up, the descriptor is ambiguous and the match is discarded.
  3. 3. Why does RANSAC fit its model to a few random matches instead of all matches at once?

    A few outliers can pull a least-squares fit far off. Fitting small samples and counting inliers finds the model the majority supports, and a final refit on the inliers makes it precise.
  4. 4. How many point matches does the minimal sample need for an affine transform in 2D?

    An affine transform has 6 unknowns and every point match supplies 2 equations (one for y and one for x), so 3 matches are enough.
  5. 5. Which distance is the natural choice for binary descriptors such as ORB?

    Binary descriptors are bit strings; counting the differing bits is quick and meaningful.

Summary

  • A descriptor turns the surroundings of a keypoint into a vector; matching means finding the closest vector in the other image.
  • Normalizing a patch (subtract mean, divide by standard deviation) makes it robust to brightness and contrast changes.
  • Use L2 or cosine distance for real-valued descriptors and Hamming distance for binary ones.
  • Nearest neighbour always answers; the ratio test (best / second best below about 0.8) drops ambiguous matches.
  • RANSAC fits a model to minimal random samples, counts inliers, keeps the best model and refits on its inliers; it tolerates a large share of bad matches.
  • SIFT, ORB and learned descriptors improve robustness to scale, rotation and viewpoint, but the pipeline is the same.

Next, detect straight lines and circles by voting in Hough Transform for Lines and Circles.