Matching & ratio test

Matching by distance

After detection and description, every feature is a 128-dimensional vector. To find correspondences:

• compute the distance in feature space, here the Euclidean distance between SIFT descriptors,
• match each feature to the one with the lowest distance, its nearest neighbor,
• ignore matches whose distance is above a threshold: no match.

This has two problems:

• The threshold is hard to pick. Distances of correct matches depend on how much the view changed, and those of incorrect ones on the image content, so the two distributions overlap.
• Features that are not distinctive, for example on repetitive structures, have many close neighbors, only one of which is correct. A small distance says nothing about whether the right one was picked.

Nearest neighbor distance ratio

The ratio test compares the distance $d_1$ to the closest neighbor NN1 with the distance $d_2$ to the second closest NN2:

• If $d_1 \approx d_2$, the ratio is close to 1: the match is too close to call.
• If $d_1 \ll d_2$, the ratio tends to 0: one neighbor clearly stands out.

Sorting by the ratio puts the matches in order of confidence. Lowe computed the distribution of the ratio for 40,000 keypoints with hand-labeled ground truth: correct matches pile up at low ratios, incorrect ones near 1. The second nearest neighbor serves as an estimate of how close an incorrect match can be in this part of feature space.

Choosing the threshold

The threshold depends on the application's trade-off between false positives and true positives. With a low threshold such as 0.5 there are few false positives but also fewer matches; a higher threshold such as 0.8 keeps more of the true positives and lets in more false positives. Lowe's choice of 0.8 removes about 90% of the incorrect matches while losing less than 5% of the correct ones. The large plot shows this trade-off for both criteria: each curve starts at the strictest threshold and ends when every match is accepted. A curve that climbs more steeply finds more correct matches for the same number of incorrect ones.

The ground truth here comes from the known transformation: a match is correct if the keypoint in $B$ lies within $\varepsilon$ pixels of the mapped keypoint of $A$. Only features in the region both images show take part. A feature may have no partner at all, if the detector didn't find its point again in $B$; the dashed line shows how many correct matches are possible.

Try this

• Compare the two histograms: the distances of correct and incorrect matches overlap, while their ratios are clearly apart.
• Follow the two curves from the left: before the first incorrect match is accepted, the ratio test has already found many correct ones, the distance threshold only a few.
• Lower the ratio threshold to 0.5: no incorrect matches remain, but about a third of the correct ones are lost too.
• Set the rotation to 0 and the scale to 1, and raise the noise to 0.05: both criteria keep about the same correct matches, but the distance threshold accepts several times more incorrect ones.
• Rotate by 60°, scale to 0.7 and add noise: the distances of correct matches grow, and a fixed distance threshold loses more of them than the ratio test.
• Switch to the shapes image: the squares of the checkerboard and the corners of the rectangles look alike, so even correct matches get ratios close to 1, and no threshold separates them well.
• Set the noise to 0 as well: B is then the same image, every correct match has $d_1 = 0$, and both criteria are perfect.