Feature Matching

Feature matching finds points in two or more images that show the same physical point in the scene. These correspondences are the raw material of multi-view geometry: relative camera pose, homographies, and triangulated 3D points are all computed from them.

Matching differs from feature tracking. A tracker follows points between consecutive video frames and assumes small motion, so it can search locally around each point’s previous position. A matcher makes no such assumption: the images may come from different times, viewpoints, scales, and cameras, so each point must be recognized by its appearance rather than found nearby.

Problem Definition

Given images $I_A$ and $I_B$, find pairs of pixel locations $(\mathbf{x}_i^A, \mathbf{x}_j^B)$ that are projections of the same 3D point. Many points have no partner, because they are outside the other view, occluded, or not detected there, so a matcher must decide both which point corresponds to which and whether a point has a correspondence at all.

The correspondences are usually required to be one-to-one, since a 3D point projects to one location in each image. This makes matching an assignment problem, like data association in tracking. The Hungarian algorithm solves it optimally for a given cost matrix, but most feature matchers use cheaper nearest-neighbor rules or learned assignment layers.

Input and Output

The input to matching is a set of keypoints per image, each with a location (often also a scale and orientation) and a descriptor, a vector summarizing the appearance of the surrounding patch. The output is a list of index pairs $(i, j)$, often with a confidence or distance for each. The full pipeline has five stages:

1. Detection of repeatable keypoints, such as corners or blobs.
2. Description of each keypoint, invariant to the expected changes between images.
3. Matching of descriptors across images into candidate pairs.
4. Filtering of ambiguous candidates with local tests.
5. Geometric verification, keeping only candidates consistent with a geometric model.

Detector-free methods replace the first three stages with a network that takes both images and outputs correspondences.

Variants

• Sparse vs. dense. Sparse matching links selected keypoints. Dense matching predicts a correspondence for every pixel or grid cell, as optical flow does between video frames.
• Detector-based vs. detector-free. Detector-free methods can find correspondences anywhere, including low-texture regions where detectors return few repeatable points.
• 2D–2D vs. 2D–3D. Two images give 2D–2D correspondences for relative pose and triangulation. Visual localization matches a query image to the points of a 3D map, and the 2D–3D correspondences give the camera’s absolute pose.
• Narrow vs. wide baseline. Nearby viewpoints look alike and are easy to match. Wide-baseline pairs, with large changes in viewpoint, scale, and appearance, are the main difficulty.

Challenges

• Viewpoint and scale change distort local patches and change how many pixels a point covers.
• Illumination change (day and night, seasons, shadows, exposure) alters intensities.
• Repetitive structure, such as windows on a facade, produces look-alike descriptors, so the nearest neighbor is often the wrong instance.
• Textureless regions, such as blank walls and sky, have few distinctive points.
• Outliers remain even with good descriptors, so the downstream geometry must tolerate them.

Approaches

Classical Descriptors

SIFT, introduced by Lowe, detects blob-like keypoints at the extrema of a difference-of-Gaussians scale space and describes each with a 128-dimensional histogram of gradient orientations, normalized for scale and rotation. SURF approximated similar computations to run faster. Binary descriptors such as BRIEF and ORB encode a patch as a bit string of intensity comparisons, compared with the much cheaper Hamming distance, at some cost in robustness.

Nearest Neighbors and the Ratio Test

Assigning each descriptor in image A to its nearest neighbor in image B always produces a match, even for points with no partner. Lowe proposed comparing the distance to the nearest neighbor, $d_1$, with the distance to the second-nearest, $d_2$, and accepting the match only if

$$\frac{d_1}{d_2} < \tau .$$

A correct match is usually much closer than any other candidate, while an incorrect one tends to have several candidates at similar distances. In the SIFT paper, Lowe used $\tau = 0.8$ and reported that on his test data this removed 90% of false matches while discarding fewer than 5% of correct ones. On repetitive structure, the test also rejects correct but ambiguous matches.

A second common filter is the mutual nearest-neighbor check (cross-check): keep the pair $(i, j)$ only if $j$ is the nearest neighbor of $i$ in B and $i$ is the nearest neighbor of $j$ in A. This enforces a one-to-one result without solving a full assignment problem.

Approximate Nearest-Neighbor Search

Brute-force matching compares every pair of descriptors, which is expensive against large databases, and Lowe noted that exact k-d tree search gives no speedup over it beyond about ten dimensions. Muja and Lowe’s FLANN library provides approximate search with randomized k-d forests and priority search k-means trees for real-valued descriptors, hierarchical clustering trees for binary ones, and automatic choice of algorithm and parameters for a target precision.

Geometric Verification

Local filters cannot catch a match that is distinctive but wrong, so the candidates are checked for agreement on one transformation. The usual tool is RANSAC, introduced by Fischler and Bolles: repeatedly fit a model to a minimal random sample of matches, count the matches consistent with it (inliers), and keep the model with the most support. For a planar scene or a purely rotating camera, the model is a homography, which can be estimated from four correspondences. For a general 3D scene, the model is the epipolar geometry, expressed as the fundamental matrix for uncalibrated cameras (seven or eight correspondences) or the essential matrix for calibrated ones (five). A verified homography can warp one image onto the other, as in panorama stitching.

Learned Features and Learned Matchers

SuperPoint is a fully convolutional network that computes keypoint locations and descriptors for a whole image in one forward pass. It is trained without manual labels: a base detector is first trained on synthetic shapes, then homographic adaptation creates pseudo-ground-truth keypoints on real images by aggregating the detector’s responses over many random homographic warps of each image.

SuperGlue moved learning into the matching stage. It treats the two keypoint sets as a graph and refines each descriptor with alternating self-attention (within an image) and cross-attention (across images). The refined descriptors define a score matrix, which is augmented with a “dustbin” row and column for points without a match. A differentiable optimal transport layer, solved with the Sinkhorn algorithm, turns the scores into a soft partial assignment. LightGlue revised SuperGlue’s design to be faster and easier to train, and adapts to the difficulty of each pair: it stops after fewer layers when its predictions are confident and prunes points it judges unmatchable.

Detector-Free Dense Matching

LoFTR removes the detector entirely. It extracts feature maps from both images, transforms them with self- and cross-attention layers, matches all positions at a coarse resolution, and then refines the selected matches at a finer resolution. Its authors argue that the global receptive field of the transformer lets it find matches in low-texture regions where detectors produce few repeatable points.

Practical Example

Brute-force matching of synthetic descriptors. Image B holds noisy copies of 200 of image A’s 300 points, 40 near-duplicates imitating repetitive structure, and 100 unrelated descriptors:

import numpy as np

rng = np.random.default_rng(0)
dim = 64

def normalize(x):
    return x / np.linalg.norm(x, axis=1, keepdims=True)

# Image A: 300 keypoint descriptors. The first 200 are also visible in image B.
desc_a = normalize(rng.normal(size=(300, dim)))

# Image B: noisy copies of the 200 shared points, plus 40 "repetitive" near-duplicates
# of the first 40 shared points and 100 unrelated descriptors.
shared = normalize(desc_a[:200] + 0.35 * rng.normal(size=(200, dim)) / np.sqrt(dim))
repeats = normalize(desc_a[:40] + 0.35 * rng.normal(size=(40, dim)) / np.sqrt(dim))
clutter = normalize(rng.normal(size=(100, dim)))
desc_b = np.vstack([shared, repeats, clutter])
gt = {i: i for i in range(200)}  # A index -> correct B index

# Brute-force distances between every pair of descriptors.
dist = np.linalg.norm(desc_a[:, None, :] - desc_b[None, :, :], axis=2)

order = np.argsort(dist, axis=1)
nn, second = order[:, 0], order[:, 1]
rows = np.arange(len(desc_a))
ratio = dist[rows, nn] / dist[rows, second]
mutual = np.argmin(dist, axis=0)[nn] == rows

def report(name, keep):
    matches = [(i, nn[i]) for i in np.flatnonzero(keep)]
    correct = sum(gt.get(i) == j for i, j in matches)
    print(f"{name:<22} matches={len(matches):3d}  "
          f"precision={correct / max(len(matches), 1):.2f}  recall={correct / len(gt):.2f}")

report("nearest neighbor", np.ones(len(desc_a), bool))
report("ratio test (0.8)", ratio < 0.8)
report("mutual check", mutual)
report("ratio + mutual", (ratio < 0.8) & mutual)

Output:

nearest neighbor       matches=300  precision=0.61  recall=0.92
ratio test (0.8)       matches=164  precision=0.99  recall=0.81
mutual check           matches=214  precision=0.86  recall=0.92
ratio + mutual         matches=164  precision=0.99  recall=0.81

Plain nearest neighbors match every point, including the 100 without a partner. The mutual check removes most of those but keeps wrong matches to near-duplicates. The ratio test rejects both, but also drops correct matches whose near-duplicate is almost as close, so recall falls; here the mutual check adds nothing on top of it.

Datasets and Benchmarks

HPatches (Balntas et al.) contains 116 image sequences, 57 with illumination changes and 59 with viewpoint changes, each with a reference image, five target images, and ground-truth homographies. It defines three descriptor tasks on patches extracted from them (patch verification, image matching, and patch retrieval), and its sequences are also widely used for homography estimation from full images. PhotoTourism, internet photos of landmarks with poses from structure from motion, is used in the benchmark of Jin et al. behind the Image Matching Challenge, which scores matchers by the accuracy of the resulting camera poses rather than by match counts. MegaDepth, internet photo collections with depth maps from multi-view stereo, is a common outdoor training set, and ScanNet, indoor RGB-D video with ground-truth poses and depth, is used for indoor training and evaluation.

Evaluation Metrics

Matching is measured by precision (the fraction of predicted matches that are correct) and recall (the fraction of ground-truth correspondences found), with a match counted as correct within a pixel threshold of the ground truth. Because matches feed a geometric estimator, results are also reported downstream. Homography estimation accuracy, as in SuperGlue’s evaluation, measures the reprojection error of the image corners under the estimated homography and reports the area under the cumulative error curve up to a pixel threshold. Pose AUC takes the relative pose error as the larger of the rotation and translation angular errors and reports the area under its cumulative curve up to thresholds such as 5°, 10°, and 20°.

Applications

• Structure from motion matches many photos to recover camera poses and a sparse 3D point cloud.
• Panorama stitching matches overlapping photos and warps them into a common frame.
• Visual localization matches a query image to a prebuilt 3D map.
• SLAM and visual odometry match keyframes against each other and the map, alongside frame-to-frame feature tracking.
• Object recognition and image retrieval use matching to verify candidates, as in Lowe’s SIFT recognition system.

Open Problems

• Extreme appearance change, such as day–night, seasonal, and cross-modal (visible–thermal) matching.
• Symmetric scenes, where matches between two different but similar-looking parts of a building can be geometrically consistent, so verification does not catch them.
• Accuracy vs. cost. Dense, detector-free matchers are generally slower and more memory-hungry than sparse matching, which limits them on embedded and real-time systems.
• Generalization of learned matchers trained on landmarks or indoor scans to other domains, such as aerial, medical, or underwater images.