feature matching

Once two images have been distilled into sets of keypoints with descriptors, feature matching is the step that answers 'which feature in image A is the same physical point as which feature in image B?' Because each descriptor is just a vector (or bit-string) summarizing local appearance, two features that correspond should have very similar descriptors. So matching is fundamentally a nearest-neighbour search: for each descriptor in one image, find the descriptor in the other image that is closest under an appropriate distance, Euclidean distance for floating-point descriptors like SIFT and Hamming distance for binary descriptors like ORB.

The naive approach, brute-force matching, compares every descriptor in A against every descriptor in B; it is exact but quadratic and slow for large sets. Approximate nearest-neighbour libraries such as FLANN (using kd-trees for float descriptors or locality-sensitive hashing for binary ones) trade a tiny amount of accuracy for large speedups, which matters when each image has thousands of features and you are matching against a large database. The key point is that matching only finds the closest descriptor; it does not know whether that closest descriptor is actually a true correspondence.

This is why raw nearest-neighbour matches are heavily contaminated with false matches and must be filtered. The single most important filter is Lowe's ratio test: for each query feature, find its two nearest neighbours and keep the match only if the nearest is substantially closer than the second-nearest (a common ratio threshold is 0.7 to 0.8). The reasoning is that a distinctive, correct match stands out from all alternatives, whereas an ambiguous or repetitive-texture feature has two roughly equally close candidates and should be discarded. A second filter is cross-checking (mutual nearest neighbours): keep a match only if A's best match in B also has A as its best match back, which removes one-sided coincidences.

Even after ratio testing and cross-checking, some wrong matches survive, especially with repeated structure like windows on a building. The final and decisive filter is geometric verification: fit a global geometric model (a homography for a plane, a fundamental or essential matrix for general scenes) to the matches using RANSAC, and discard every match inconsistent with that model as an outlier. This two-stage philosophy, appearance-based matching followed by geometry-based rejection, is the backbone of stitching, recognition, SLAM, and structure-from-motion. Modern learned matchers such as SuperGlue and LightGlue go further, jointly reasoning about all features in both images with attention to resolve ambiguity that pairwise nearest-neighbour matching cannot.