Feature matching with SIFT and ORB

SIFT#

Lowe (2004), Distinctive image features from scale-invariant keypoints, IJCV 60(2). Four stages:

Scale-space extrema detection. Build a Gaussian pyramid and take differences of adjacent blur levels, approximating the scale-normalised Laplacian:

$$ D(x, y, \sigma) = \bigl(G(x,y,k\sigma) - G(x,y,\sigma)\bigr) * I(x,y) \approx (k-1)\,\sigma^2 \nabla^2 G * I $$

Keypoints are local extrema of $D$ over the 3x3x3 neighbourhood in $(x, y, \sigma)$. Detecting at the scale of the extremum is what gives scale invariance.

Keypoint localisation. Fit a 3D quadratic to $D$ around each extremum and take its analytic extremum, giving sub-pixel and sub-scale position. Reject low-contrast points, and reject edge responses by thresholding the ratio of principal curvatures of the 2x2 Hessian — the same Harris criterion, applied in scale space.

Orientation assignment. Build a 36-bin histogram of gradient orientations in a neighbourhood, weighted by gradient magnitude and a Gaussian. The dominant peak defines the keypoint's orientation; peaks within 80% of it spawn duplicate keypoints. Describing relative to this orientation is what gives rotation invariance.

Descriptor. A 4x4 grid of 8-bin orientation histograms, computed in the rotated frame, gives $4 \times 4 \times 8 = 128$ values, normalised to unit length, clipped at 0.2, and renormalised. The clipping suppresses the effect of large gradient magnitudes from non-linear illumination change.

ORB#

Rublee et al. (ICCV 2011), ORB: an efficient alternative to SIFT or SURF. Two contributions on top of existing parts.

oFAST. FAST corners (Rosten and Drummond, 2006) have no orientation. ORB adds one from the intensity centroid: with moments $m_{pq} = \sum_{x,y} x^p y^q I(x,y)$, the orientation is $\theta = \operatorname{atan2}(m_{01}, m_{10})$. It is a single pass over the patch.

rBRIEF. BRIEF (Calonder et al., 2010) is a binary string whose bits are intensity comparisons at 256 point pairs. It is not rotation invariant, so ORB rotates the sampling pattern by $\theta$. Rotating a randomly-chosen pattern destroys BRIEF's carefully high variance and low correlation, so ORB learns the 256 pairs greedily from a training set, selecting for variance near 0.5 and low pairwise correlation. That learned pattern is baked into the implementation.

Scale invariance comes from running oFAST over an image pyramid, which is coarser than SIFT's continuous scale-space search — one reason ORB's localisation error is roughly double SIFT's in the run above.

Why the ratio test works#

Lowe's ratio test keeps a match when

$$ \frac{d_1}{d_2} < \tau, \qquad \tau \approx 0.75 $$

where $d_1$ and $d_2$ are the distances to the nearest and second-nearest descriptors.

The justification is a likelihood ratio. In a high-dimensional descriptor space, the distance from a query to a random descriptor is tightly concentrated — the concentration-of-measure effect. So $d_2$ is an estimate of "how far away things are when they are not the answer". If $d_1$ is not much smaller than that reference, the nearest neighbour carries no evidence. The test is a per-query normalisation, which is why a single global distance threshold works so much worse.

Lowe's original figure shows the test rejecting about 90% of false matches while discarding about 5% of correct ones.

Cost#

Descriptor matching by brute force is $O(n_1 n_2 d)$. For $n = 2000$ and $d = 128$, that is around $5\times10^8$ operations per pair — the dominant cost in a classical SfM pipeline, and why approximate nearest neighbour (FLANN, or a k-d tree with a bounded search) is standard beyond a few thousand features.

For binary descriptors, LSH with multi-probe is the usual index, and Hamming distance makes the brute-force baseline much cheaper than for floats.

What replaced them#

SuperPoint (DeTone et al., CVPRW 2018) learns detection and description jointly, self-supervised by Homographic Adaptation: apply random homographies to unlabelled images and keep points detected consistently across them.

SuperGlue (Sarlin et al., CVPR 2020) reframes matching as optimal transport between the two keypoint sets, using attention over both intra- and inter-image keypoints and a Sinkhorn solver, with an explicit dustbin for unmatched points. This replaced the nearest-neighbour-plus-ratio-test pipeline entirely, and it uses context: a keypoint's match is decided partly by where its neighbours matched.

LightGlue (Lindenberger et al., ICCV 2023) makes it adaptive — easier pairs exit early, and confidently-unmatchable points are pruned — reaching comparable accuracy at a fraction of the cost.

Detector-free matching. LoFTR (Sun et al., CVPR 2021) and RoMa skip keypoints entirely, producing dense coarse-to-fine correspondences with transformers. These dominate on low-texture and wide-baseline pairs where no detector fires at all — the failure mode classical methods cannot escape.

Classical features remain in wide use because they need no GPU, no weights and no licence review. On well-textured scenes with moderate baselines the accuracy gap is also small. COLMAP still defaults to SIFT; ORB-SLAM3 still uses ORB.

What to learn next#

• RANSAC for robust fitting — surviving the wrong matches this lesson measured.
• Structure from motion — turning matches across many photos into a 3D model.
• Visual SLAM — the same matching, running live on a moving robot.