Descriptor Matching & the Ratio Test

"Being almost as close as the winner sounds flattering until you learn about the ratio test. Apparently, my very existence disqualifies the match."

A Bitterly Disqualified Second-Nearest Neighbor

The chapter so far has been about single images: detect keypoints (Sections 10.1 and 10.2), describe them (Sections 10.3 and 10.4). Now, finally, two images meet. Image one contributes descriptors $\{\mathbf{d}_i\}$, image two contributes $\{\mathbf{e}_j\}$, and the task is to output pairs $(i, j)$ that name the same physical point. The entire design of the descriptors was aimed at making this moment simple: if description worked, corresponding points are nearby in descriptor space, and matching reduces to nearest-neighbor search. The catch, as always, is in what "nearby" fails to guarantee.

1. Nearest Neighbors and Their Lies Beginner

The baseline matcher could not be more direct: for each descriptor in image one, find the closest descriptor in image two (L2 distance for SIFT-family floats, Hamming for ORB-family bits, per Section 10.4), and declare a match. The problem is that nearest-neighbor search always returns an answer. A keypoint whose physical point is occluded in the second image, or outside its frame, still gets a nearest neighbor; it is just a meaningless one. A keypoint on a repetitive structure (one window among forty identical windows on a facade) gets a nearest neighbor that is genuinely similar and very possibly the wrong window. Raw nearest-neighbor output is typically polluted with tens of percent of such false matches, and downstream geometry is exquisitely sensitive to them.

Matching is therefore an exercise in filtering. Three filters do most of the work in practice, in increasing order of insight: an absolute distance threshold (weak, because "close" varies wildly between scenes and descriptors), the mutual cross-check, and the ratio test. Before reaching for any library, it is worth seeing the whole computation honestly in NumPy; the function below is the complete logic of a ratio-test matcher.

import numpy as np

def match_nn_ratio(d1: np.ndarray, d2: np.ndarray, ratio: float = 0.75):
    """Nearest-neighbor matching with Lowe's ratio test, pure NumPy."""
    d1 = d1.astype(np.float32); d2 = d2.astype(np.float32)
    # all pairwise squared distances: ||a||^2 + ||b||^2 - 2 a.b
    dists = (d1**2).sum(1)[:, None] + (d2**2).sum(1)[None, :] - 2 * d1 @ d2.T
    matches = []
    for i, row in enumerate(dists):
        j1, j2 = np.argsort(row)[:2]              # best and second-best
        if np.sqrt(max(row[j1], 0)) < ratio * np.sqrt(max(row[j2], 0)):
            matches.append((i, j1))               # unambiguous: keep it
    return matches

2. The Cross-Check: Symmetry as a Filter Intermediate

The cross-check (mutual nearest neighbor) accepts a pair $(i, j)$ only if $j$ is the nearest neighbor of $i$ and $i$ is the nearest neighbor of $j$. The logic is symmetry: a true correspondence has no reason to prefer one direction, while a spurious one usually arises from descriptor $i$ having no real partner, in which case its arbitrary nearest neighbor $j$ almost certainly has a better partner of its own. Cross-checking is cheap (run matching both ways, intersect) and typically removes a third to a half of false matches. It is the standard default when you cannot afford k-nearest-neighbor queries, and it composes well with everything else. But it has no concept of ambiguity: on that facade of forty identical windows, descriptor $i$ and the wrong window $j$ can happily be each other's nearest neighbors. Detecting ambiguity needs a second opinion, which is exactly what the ratio test collects.

3. Lowe's Ratio Test Intermediate

Here is the question the ratio test asks: how much better is the best candidate than the runner-up? Formally, with $d_1$ the distance from a query descriptor to its nearest neighbor and $d_2$ the distance to the second-nearest, accept the match only if

$$ \frac{d_1}{d_2} \;<\; \tau, \qquad \tau \approx 0.7 \text{ to } 0.8. $$

The reasoning is a small gem of practical statistics. If the match is correct, $d_1$ is drawn from the distribution of "same point, different photo" distances: small, by descriptor design. The second-nearest neighbor, meanwhile, is almost surely some unrelated point, so $d_2$ is a sample from the background distribution of "different points" distances. A correct match therefore shows a wide gap between $d_1$ and $d_2$. If the match is wrong or ambiguous, $d_1$ and $d_2$ are both samples from the background (or both from a set of look-alikes), and the ratio crawls toward 1. The second-nearest neighbor acts as a per-query, self-calibrating estimate of what "meaninglessly close" looks like, which is why the ratio test crushes any fixed absolute threshold: it adapts to the scene, the descriptor, and even the individual keypoint. Figure 10.5.1 draws the two situations.

In the 2004 SIFT paper, Lowe quantified the test on a large ground-truth set: at $\tau = 0.8$, the ratio test discarded about 90 percent of false matches while sacrificing under 5 percent of correct ones. Practitioners since have mostly tightened it to 0.7 to 0.75 for geometry pipelines (precision matters more when RANSAC iterations are at stake) and loosened it toward 0.8 for retrieval. The standard recipe, end to end, looks like this:

import cv2

img1 = cv2.imread("ridge_left.jpg", cv2.IMREAD_GRAYSCALE)
img2 = cv2.imread("ridge_right.jpg", cv2.IMREAD_GRAYSCALE)

sift = cv2.SIFT_create(nfeatures=3000)
k1, d1 = sift.detectAndCompute(img1, None)
k2, d2 = sift.detectAndCompute(img2, None)

bf = cv2.BFMatcher(cv2.NORM_L2)               # no crossCheck with knnMatch
pairs = bf.knnMatch(d1, d2, k=2)              # two best candidates per query
good = [m for m, n in pairs if m.distance < 0.75 * n.distance]
print(f"{len(pairs)} candidates -> {len(good)} after ratio test")
# 3000 candidates -> 642 after ratio test

vis = cv2.drawMatches(img1, k1, img2, k2, good, None,
                      flags=cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)
cv2.imwrite("matches.jpg", vis)

Look at the printed numbers: four out of five candidates died at the gate. That attrition is normal and healthy. With ORB descriptors the same recipe applies with cv2.NORM_HAMMING; the ratio of two Hamming distances is just as meaningful as the ratio of two Euclidean ones.

4. Scaling Up: Approximate Search With FLANN Intermediate

Brute force compares every query against every candidate: fine at 2,000 versus 2,000, painful at 100,000 versus 10 million, which is where panorama engines, reconstruction farms, and image-retrieval systems operate. The classical answer is approximate nearest-neighbor search: index the candidate descriptors in a space-partitioning structure, accept a small probability of missing the true neighbor, gain orders of magnitude in speed. OpenCV bundles FLANN (Fast Library for Approximate Nearest Neighbors), with two indexes you should know: randomized KD-tree forests for float descriptors, and multi-probe locality-sensitive hashing (LSH) for binary ones.

# Float descriptors (SIFT family): forest of randomized KD-trees
FLANN_INDEX_KDTREE = 1
flann = cv2.FlannBasedMatcher(
    dict(algorithm=FLANN_INDEX_KDTREE, trees=5),
    dict(checks=50))            # leaves visited: the accuracy/speed dial
pairs = flann.knnMatch(d1, d2, k=2)
good = [m for m, n in pairs if m.distance < 0.75 * n.distance]
print(len(good))                # within a few matches of brute force

# Binary descriptors (ORB/AKAZE): multi-probe LSH instead
FLANN_INDEX_LSH = 6
index_params = dict(algorithm=FLANN_INDEX_LSH,
                    table_number=6, key_size=12, multi_probe_level=1)

A rule of thumb worth keeping: below roughly 5,000 descriptors per image, optimized brute force usually wins (no index to build, perfect recall); above that, and especially when one side of the match is a persistent database queried many times, approximate search dominates. The idea of organizing descriptors for sub-linear lookup grows in two directions later in the book: quantizing them into visual words for the retrieval systems of Chapter 16, and, in the modern era, embedding whole images for vector search, where Chapter 34's CLIP vectors play the role descriptors play here.

5. What Matching Cannot Fix Beginner

Run the recipe on a real pair and inspect the drawn matches; you will find the picture mostly right and stubbornly imperfect. A few lines cross the image at impossible angles, connecting a roof corner to a fence post: confidently wrong matches the ratio test cannot see. Some correct correspondences died at the gate because the scene really does repeat. This is the honest endpoint of descriptor-space reasoning: every filter in this section judges matches one at a time, in isolation, and no amount of per-match cleverness can exploit the one constraint that binds all true matches together: they were produced by the same camera motion looking at the same rigid scene. Enforcing that collective constraint, and surviving the outliers that violate it, is robust model fitting, and it is where this chapter has been heading all along. The payoff arrives in Section 10.6, and it is what the two-view geometry of Chapter 13 will inherit.