Skip to the lesson
FixTheRobot Explore Robotics / Perception / P4 Classical Feature Detection and Matching / P4-T2

Perception · Theory · P4

P4-T2 — Feature Descriptors and Matching

A descriptor turns the neighbourhood of a feature into numbers whose distance says how alike two features are.

  • Lesson 2 of 6
  • Module 4: Classical Feature Detection and Matching
  • Theory
  • About 9 minutes to read

Finding a corner is half the job. To link it with the same corner in another image, the robot has to describe what surrounds it in a way that survives changes of light, a little rotation and noise, and then compare descriptions. This lesson covers the common descriptors (raw patches, gradient histograms, binary tests), the distances used to compare them, and the rules that decide whether a best match is trustworthy.

Learning objectives

After this lesson, you should be able to:

  • Build a normalised patch descriptor and explain which changes it ignores.
  • Describe how gradient-histogram (SIFT) and binary (BRIEF, ORB) descriptors gain invariance and compare them.
  • Match descriptors by nearest neighbour and apply the ratio test and cross-check.
  • Estimate the cost of brute-force matching and name ways to reduce it.

The idea: compare neighbourhoods, not pixels

The coordinates of a corner say where it is. They say nothing about which corner it is. To tell corners apart, the robot looks at what is around each one: the pattern of brightness in a small patch. Two views of the same physical corner should have patches that look alike; two different corners should not.

The simplest descriptor is the patch itself, flattened into a vector. Two problems appear immediately.

  • Lighting: if the second image is darker or has less contrast, every pixel value changes. Subtracting the patch mean and dividing by its norm removes an additive and a multiplicative change of brightness.
  • Geometry: if the camera rotated or zoomed, the patch is rotated or scaled and no longer matches pixel for pixel. Better descriptors assign each feature an orientation and a scale, and describe the patch in that frame.

A descriptor is a promise: two features of the same point give nearby vectors, features of different points give distant ones. Each design choice buys invariance to some change and loses distinctiveness to pay for it.

Three families

DescriptorWhat it storesDistanceStrengthWeakness
Normalised patchPixel values, zero mean, unit normEuclideanSimple; robust to brightness and contrastNot rotation or scale invariant; large
SIFT (gradient histograms)128 numbers: histograms of gradient orientations in 4 × 4 cells, in the feature’s scale and orientationEuclideanRobust to rotation, scale, moderate viewpoint and light changeSlower; larger; historically patented (expired)
BRIEF / ORB (binary)256 bits: results of comparing pairs of pixels in a smoothed patch (ORB adds orientation)Hamming (count of differing bits)Very fast to compute and compare; compactLess distinctive than SIFT; sensitive to large scale change
Learned descriptorsVectors produced by a trained networkEuclidean or cosineCan be the most robustNeeds a network at run time and training data like your scenes
Distances from one feature to eight candidatesTwo bar charts of the descriptor distance from one query feature to eight candidate features. Left: one candidate (number 3) is much closer than all the others, with distance 0.31 against a second best of 0.81: a confident match. Right: three candidates have distances near 0.52, 0.55 and 0.51: an ambiguous case where the best and the second best are almost equal.10.9520.8830.3140.9251.0560.9770.8181.10distinctive: best 0.31, second 0.81, ratio 0.3810.5220.5530.5140.9050.9760.8870.9481.02ambiguous: best 0.51, second 0.52, ratio 0.98The ratio test compares the best with the second best.
Distances from one feature to eight candidates. Left: one candidate is far better than the rest, a confident match. Right: three candidates are almost equally good, an ambiguous case.

The mathematics: normalisation, distances and the ratio test

Normalised patch descriptor

Take the (2r + 1)² pixels around the feature as a vector p. Remove brightness and contrast:

zero-mean, unit-norm patch
p^=p−mean⁡(p)∥p−mean⁡(p) ∥\hat{p}=\frac{p-\operatorname{mean}(p)}{\lVert p-\operatorname{mean}(p)\,\rVert }
p
the raw patch as a vector of pixel values.
mean(p)
the average of the entries: subtracting it removes an additive brightness change.
‖·‖
the Euclidean length: dividing by it removes a multiplicative contrast change.
p̂
the descriptor: it has mean 0 and length 1, so distances between descriptors lie between 0 and 2.

If image B is image A scaled and shifted in brightness, pB = g pA + o (with g > 0), then p̂B = p̂A exactly, apart from noise. For unit-norm vectors the distance and the normalised correlation ρ are linked: ‖p̂1 − p̂2‖² = 2 (1 − ρ).

Hamming distance for binary descriptors

Hamming distance
dH(x, y)=number of bit positions where x and y differ=popcount⁡(x XOR y)d_{H}(x,\,y)=\text{number of bit positions where}\,x\,\text{and}\,y\,\text{differ}=\operatorname{popcount}(x\,\mathrm{XOR}\,y)

On modern CPUs this is a few instructions per 64 bits, so comparing 256-bit descriptors is faster than comparing 128 floating-point numbers by a large factor.

Matching rules

For a feature in image A with descriptor f, compute the distances d1 ≤ d2 ≤ … to all descriptors in B. The nearest neighbour is the candidate; the question is whether to trust it.

ratio test (Lowe)
accept if d1d2<ρmax⁡\frac{\text{accept if}\,d1}{d2}<\rho _{\max}
typical ρmax⁡≈0.7 to 0.8\text{typical}\,\rho _{\max}\approx 0.7\,\text{to}\,0.8
accept if the nearest neighbour of the candidate in A is the original feature

The ratio test says that a good match must be clearly better than the alternatives: when the best and second best are nearly equal, the choice between them is arbitrary, and the match is as likely to be wrong as right. Lowe’s paper reports that a ratio threshold of 0.8 eliminated about 90% of the false matches while discarding less than 5% of the correct ones on the data he studied; the numbers depend on the descriptor and the scene, so the threshold must be tuned. The cross-check demands that the match be mutual.

Cost

Brute-force matching of N features against M costs N·M distance computations of dimension D: 1000 × 1000 × 128 ≈ 128 million multiply-adds per image pair for SIFT-like descriptors. Approximate nearest-neighbour structures (k-d trees, hierarchical clustering, locality-sensitive hashing; FLANN is a library of these) cut this by orders of magnitude at the price of occasionally missing the true nearest neighbour. Restricting the search to a window around the predicted position (from odometry or a motion model) cuts it further and removes many false candidates for free.

A worked example: normalisation and the ratio test

A patch of four pixels in image A is [80, 120, 90, 130]. In the darker image B the same patch reads [60, 100, 70, 110]: the whole patch is 20 grey levels darker.

effect of normalisation
raw distance=40.0\text{raw distance}=40.0
normalised A=[−0.606, 0.364, −0.364, 0.606]\text{normalised}\,A=[-0.606,\,0.364,\,-0.364,\,0.606]
normalised B=[−0.606, 0.364, −0.364, 0.606]\text{normalised}\,B=[-0.606,\,0.364,\,-0.364,\,0.606]
normalised distance=0.000\text{normalised distance}=0.000

Before normalisation the two descriptions of the same point are 40 apart, a distance that two genuinely different patches could easily have. After normalisation the distance is 0.000: the brightness change has vanished. This is why Stage 1 and Stage 2 of Lab P4-L2 improve so much when normalisation is turned on.

The ratio test on the two cases of the figure

Left case: best distance 0.31, second best 0.81, ratio 0.31/0.81 = 0.38. The best is more than twice as good as the runner-up: accept. Right case: best 0.51, second 0.52, ratio 0.51/0.52 = 0.98. Three candidates (1, 2 and 3 at 0.52, 0.55 and 0.51) are within noise of each other: reject. A plain nearest-neighbour rule would accept both; in the second case, it picks candidate 3, which is right about one time in three. This is typical of repeated structures such as windows or shelves, where several candidates are genuinely alike.

A binary descriptor

Two 16-bit descriptors: 1011001110100101 and 1001001010100111. They differ in 3 positions, so dH = 3. For a 256-bit ORB descriptor, a Hamming distance below about 50 to 64 is a typical acceptance range; again the right value depends on the scene.

Counting the cost

A robot extracts 500 ORB features per frame (32 bytes each) and matches against the previous frame. Brute-force Hamming matching takes 500 × 500 = 250 000 comparisons of 256 bits, about a millisecond on a laptop CPU. With 500 SIFT features the same job is 250 000 × 128 multiply-adds, about 32 million, still only a few milliseconds but ten times more than ORB, and the descriptor extraction itself is much slower. On an embedded processor, these differences decide the choice.

Engineering implications and limitations

Match the descriptor to the compute. ORB or BRIEF on a small embedded CPU; SIFT or a learned descriptor where more compute and robustness are available. Measure on your data; the ranking depends on the scene and the camera motion.

Tune the ratio from data, not from habit. Collect pairs with known correspondences (known motion or a calibration target), plot precision and recall against the ratio threshold, and choose the point that suits the next stage. RANSAC tolerates a lot of wrong matches; a SLAM back end may need cleaner ones.

Use a motion prior to narrow the search. If odometry says the camera moved at most 20 pixels, restrict candidates to that window. This is faster and removes the matches to a different but look-alike object far away.

Always check the matches against geometry. No descriptor rule removes all wrong matches. Follow matching with a geometric check (Lessons P4-T4 and P4-T5).

Mind invariance you do not need. Rotation invariance is useful for a hand-held camera and harmful for a camera on a ground robot, where “which way is up” in the image helps distinguish features (a 6 and a 9). Choose the invariance your motion needs, and no more.

Record the match statistics. The number of candidates, the ratio-test pass rate and the distribution of distances are cheap health indicators. A sudden drop in the pass rate says the scene became ambiguous, blurred or dark.

Common misconceptions

“The nearest neighbour is the match.”

The nearest neighbour is the best candidate. Whether it is a match depends on how much better it is than the runner-up and on whether the other image contains the feature at all.

“A smaller distance threshold gives better matches.”

An absolute threshold ignores context: in a scene full of repeated structure many wrong pairs are close. The ratio to the second best is a better indicator of ambiguity.

“Binary descriptors are just a faster SIFT.”

They are a different trade-off: much faster and smaller, less distinctive, and less robust to large scale and viewpoint changes.

“Normalising removes all lighting effects.”

It removes a uniform change of brightness and contrast over the patch. Shadows, highlights and changes across the patch are not removed.

Engineering takeaways

  1. A descriptor summarises a feature’s neighbourhood; matching compares descriptors with a distance (Euclidean for vectors, Hamming for bits).
  2. Normalising a patch (zero mean, unit norm) removes brightness and contrast changes; SIFT and ORB add rotation and scale invariance.
  3. Accept a nearest neighbour only if d1/d2 < about 0.8 and the match is mutual (cross-check).
  4. Brute-force matching costs N·M distances; use approximate search, binary descriptors or a motion prior to cut it.
  5. Tune thresholds on data with known correspondences, and always follow with a geometric check.

References and further reading

Original papers; the worked numbers were computed for this lesson.

  • Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision 60(2): SIFT, and the ratio test.
  • Calonder, M., Lepetit, V., Strecha, C. and Fua, P. (2010). BRIEF: Binary robust independent elementary features. ECCV.
  • Rublee, E., Rabaud, V., Konolige, K. and Bradski, G. (2011). ORB: An efficient alternative to SIFT or SURF. ICCV: oriented FAST and rotated BRIEF.
  • Muja, M. and Lowe, D. G. (2009). Fast approximate nearest neighbors with automatic algorithm configuration. VISAPP: FLANN.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

An image pair differs by a brightness change pB = 0.7 pA + 15. Does a zero-mean unit-norm descriptor change? Does a descriptor based on raw pixels?

Explanation

The normalised descriptor does not change (the gain 0.7 and the offset 15 are removed by the subtraction of the mean and the division by the norm). The raw-pixel descriptor changes everywhere, so its distance between the two views of the same point can be as large as for different points.

Question 2

A query’s nearest and second-nearest distances are 0.40 and 0.44. Another query has 0.30 and 0.70. With a ratio threshold of 0.8, which is accepted, and why is the first risky?

Explanation

Ratios are 0.91 and 0.43. The second is accepted and the first rejected. The first is risky because the runner-up is almost as close: the choice between them is nearly arbitrary, as happens with repeated structure.

Question 3

Two 256-bit descriptors differ in 38 bits. Is this a good match? What additional information do you need to decide?

Explanation

It depends on the descriptor and scene: typical acceptance thresholds for ORB are around 50 to 64, so 38 is a good distance, but you also need the distance to the second-best candidate (ratio test) and the distribution of distances in your data to see whether 38 is unusually low.

What’s next

Next: what to do with matches once you have them: correspondences, inliers and outliers, and how a few wrong matches can ruin an estimate.

Practice this lesson

Match Features Between Images

Describe patches, match them and measure precision against ground truth.

Next lesson

P4-T3 — Correspondences and Outliers

Define a correspondence, separate inliers and outliers and measure their effect.

Nothing below is required to finish this lesson.