Finding the Same Point Twice: SIFT, the Ratio Test and RANSAC

Image Formation ended with a homography: given four point pairs, one matrix maps one image onto the other. This post is about where those point pairs come from. To stitch a panorama, track a camera or reconstruct a scene, a program has to find the same physical point in two different images, automatically, even when the second image is rotated, scaled, darker or seen from a different angle.

The classical solution has four steps: detect distinctive points, describe each one with a vector, match the vectors, and verify the matches geometrically, because many of them will be wrong. Each step comes with a lab, and the claims about robustness are tested on photos transformed in known ways, so every match can be checked against the truth.

1. The Pipeline

The split matters. Matching compares only descriptors: it has no idea where the points are. Verification uses only geometry: it asks which matches a single transformation can explain. The two are often mixed up. RANSAC is the verification step, a way to estimate a transformation when many of the matches are wrong. ICP (iterative closest point) is something else entirely: it aligns two 3D point clouds when no correspondences are known at all, by alternating between nearest-point pairing and re-estimating the motion.

2. What Makes a Good Keypoint?

A keypoint is useful if it can be found again: in the other image, its position should be unambiguous. Take a small window and compare it with the same window shifted by $u = (u, v)$ , using a weighted sum of squared differences:

E (u) = i \sum w (x_{i}) [I (x_{i} + u) - I (x_{i})]^{2}

This is the window compared with itself (Moravec, 1980): it measures how well the window could be told apart from its shifted versions. For a good keypoint, $E$ has a single sharp minimum at $u = 0$ . There are three cases:

Flat region: $E$ stays near zero in every direction. The window could be anywhere nearby.
Edge: $E$ grows when the window moves across the edge, but not along it: a valley instead of a pit. Only the motion perpendicular to the edge can be measured. This is the aperture problem, and it is why edges (for example from a Sobel filter) make poor keypoints, even though they are easy to detect.
Corner: $E$ grows in every direction. The position is well defined.

For small shifts, a Taylor expansion turns $E$ into a quadratic form, $E (u) \approx u^{⊤} M u$ , with the structure tensor built from the image gradients $I_{x}, I_{y}$ :

M = i \sum w (x_{i}) [I_{x}^{2} I_{x} I_{y} I_{x} I_{y} I_{y}^{2}]

Its two eigenvalues say how fast $E$ grows in the steepest and the flattest direction: both small for a flat region, one large for an edge, both large for a corner. Harris and Stephens (1988) score corners with $R = det M - k (tr M)^{2}$ ( $k \approx 0.04$ ), which avoids computing the eigenvalues; Shi and Tomasi (1994) use the smaller eigenvalue directly. Move the window over a photo:

3. The Right Scale: Difference of Gaussians

A corner detector works at one fixed window size. But the same structure appears larger or smaller depending on the distance to the camera, and a corner at one scale can be a smooth curve at another. Scale-space theory (Lindeberg, 1998) handles this by looking at the image at all levels of blur at once, and picking for each structure the scale where a normalised detector responds most strongly: its characteristic scale.

SIFT (Lowe, 2004) uses the difference of Gaussians (DoG): blur the image with $σ$ and with $kσ$ and subtract. This approximates the scale-normalised Laplacian of Gaussian, $(k - 1) σ^{2} \nabla^{2} G$ , which responds to blobs, not edges: dark spots on a light background or the reverse. Each blob’s response peaks at a $σ$ proportional to its size:

SIFT builds this scale space in octaves: within an octave the blur grows by $k = 2^{1/3}$ (three intervals), and after each octave the image is halved. A sample is a keypoint candidate if it is a maximum or minimum among its 26 neighbours: 8 in the same DoG image and 9 each in the scales above and below. Candidates are then refined and filtered:

a quadratic fit (Taylor expansion of the DoG) moves each one to a sub-pixel, sub-scale position;
candidates with low contrast ( $∣ D ∣ < 0.03$ for an image in $[0, 1]$ , in Lowe’s paper) are discarded;
candidates on edges are discarded too: there the DoG is strongly curved across the edge but flat along it. Lowe checks the ratio of the two principal curvatures with the $2 \times 2$ Hessian, the same test as Harris in disguise, and rejects ratios above 10.

So SIFT keypoints are blob-like structures with a well-defined position and scale: each one comes as $(x, y, σ)$ .

4. Describing a Keypoint

To compare keypoints between images, each one needs a numerical descriptor that stays the same when the image changes. SIFT’s descriptor is built in a frame that moves with the keypoint:

Orientation. Around the keypoint, gradient orientations are collected in a 36-bin histogram (10° per bin), weighted by gradient magnitude and a Gaussian window. The highest peak gives the keypoint’s orientation $θ$ ; any other peak above 80% of it creates an extra keypoint with that orientation. The orientation must cover the full circle, so it uses $atan2 (I_{y}, I_{x})$ , not $tan^{- 1} (I_{y} / I_{x})$ , which cannot tell a gradient from its opposite.
The descriptor. In a window rotated to $θ$ and scaled with $σ$ , the gradients are pooled into $4 \times 4$ cells, each with an 8-bin orientation histogram:

Because the window is aligned with $(x, y, σ, θ)$ , the descriptor does not change when the image is rotated or scaled. A change in brightness that adds a constant does not change gradients at all, and normalising the vector removes a contrast factor. Clipping at 0.2 limits the influence of a few very strong gradients, for example from a non-linear lighting change.

Binary descriptors trade some robustness for speed. ORB (Rublee et al., 2011) detects corners with FAST on an image pyramid, assigns an orientation from the intensity centroid of the patch, and describes it with 256 rotated BRIEF tests: each bit says whether one pixel of a fixed pair is brighter than the other. Two descriptors are compared with the Hamming distance (XOR and a bit count), which is far cheaper than a Euclidean distance between 128-d vectors.

5. Matching: The Ratio Test

Each keypoint in image A is compared with all keypoints in image B. Three ways to decide which pairs to keep:

Nearest neighbour: every keypoint gets its closest descriptor. But many keypoints in A have no partner in B at all (not detected, or outside the second image), and they get matched anyway.
A distance threshold: keep pairs closer than some fixed $t$ . The problem is that a good distance depends on the patch: distinctive patches are far from everything, repetitive ones (windows, tiles, leaves) are close to many wrong partners.
Lowe’s ratio test: compare the nearest distance $d_{1}$ with the second nearest $d_{2}$ , and keep the match if $d_{1} / d_{2} < 0.8$ . A correct match is usually much closer than any alternative; a wrong one is about as close as the runner-up. The test adapts to each keypoint.

Try all three on 600 SIFT keypoints. The right image is the left one rotated by 25°, scaled by 0.85, seen from a different viewpoint and darkened, so every match can be checked against the true position:

On this pair, only 230 of the 600 nearest-neighbour matches are correct. The ratio test at 0.8 keeps 231 matches, of which 221 are correct (95.7%), and loses only 9 of the 230 correct ones. The browser’s matching gives exactly the same numbers as OpenCV’s BFMatcher on the same descriptors.

Over four photos and a harder transformation (rotation 30°, scale 0.7, viewpoint change, darkening), the ratio test behaves like this:

Ratio threshold	SIFT: precision, correct kept	ORB: precision, correct kept
0.6	99.4%, 88.4%	98.7%, 31.2%
0.7	97.5%, 91.3%	97.0%, 46.7%
0.8	88.9%, 93.7%	92.5%, 62.6%
0.9	65.0%, 96.6%	79.8%, 80.0%
1.0 (no test)	26.8%, 100%	50.1%, 97.4%

At 0.8, the test removes 95.7% of SIFT’s wrong matches while keeping 93.7% of the correct ones, close to what Lowe reported in 2004 (90% of false matches removed, less than 5% of correct ones lost). For ORB the same threshold throws away more than a third of the correct matches; binary descriptors have coarser distances, and their best ratio is usually set differently.

6. Verification: RANSAC

Even after the ratio test, some matches are wrong, and least squares cannot handle that: a single far-off match can pull the whole estimate away. On the lab’s pair, a homography fitted by least squares to all 305 candidate matches (ratio < 0.9) is off by about 128 px at the image corners.

RANSAC (random sample consensus; Fischler & Bolles, 1981) turns the problem around: instead of using all matches, it repeatedly guesses from the smallest possible subset and lets the data vote.

A sample of 4 matches that contains a wrong one gives a wrong homography, which few other matches agree with. A sample of 4 correct matches gives (nearly) the right homography, and all the other correct matches agree with it. Afterwards, the homography is refitted by least squares on the inliers of the best sample. On the lab’s pair, that refit is within a fraction of a pixel of the truth:

How many iterations?

If a fraction $w$ of the matches is correct, a random sample of $s = 4$ is all-correct with probability $w^{s}$ , and at least one of $k$ samples is all-correct with probability $1 - (1 - w^{s})^{k}$ . Solving for $k$ :

k = \frac{lo g ( 1 - p )}{lo g ( 1 - w ^{s} )}

For $w = 50%$ and $p = 99%$ , $k = 72$ . Since $w$ is unknown, implementations usually start with a pessimistic guess and update $k$ whenever a better model reveals a larger inlier ratio. To check the formula, I ran RANSAC 200 times for each setting on synthetic matches (200 pairs, a known homography, 0.5 px noise on the correct ones, random outliers):

The formula is optimistic. With 50% outliers and 50 iterations it promises 96% success; the best minimal sample was close enough to the truth (within 5 px at the image corners) in 62.5% of the trials, and in 89.5% after refitting on its inliers. With 80% outliers and 1,000 iterations: 79.8% promised, 45% and 67.5% measured. The formula assumes that every all-inlier sample produces the correct model, but 4 noisy points that happen to lie close together or almost on a line give a poor homography with few supporters. This gap is known (Chum et al., 2003), and it is what improved variants address: LO-RANSAC refines promising models locally, MSAC/MLESAC (Torr & Zisserman, 2000) score models by their residuals instead of a hard inlier count, and MAGSAC (Barath et al., 2019) removes the need for a fixed threshold.

7. How Robust Are SIFT and ORB?

Robustness claims are easy to make and easy to test. I took four CC0 photos (640 × 480), transformed each one in a controlled way (rotation, scaling, viewpoint change, brightness, gamma, blur, noise), detected and matched SIFT and ORB features (2,000 keypoints, ratio test 0.8), and checked every match against the known transformation. “Homography found” means RANSAC’s estimate was within 5 px of the truth at the image corners. The whole experiment runs in 45 seconds on a laptop CPU (script):

The results, condensed:

Change	SIFT	ORB
Rotation, 15°–180°	homography always found; precision ≥ 96%	always found; precision drops to 81% at 180°
Shrinking to 0.4×	always found	always found
Enlarging 2× and 2.8×	always found	found in none of the 4 photos
Viewpoint change (corners moved up to 30%)	always found	always found
Darkening to 30%	254 correct matches (1,518 at full brightness); found in 3 of 4	722 correct; found in 4 of 4
Blur σ = 6 px	found in 3 of 4	found in none
Noise σ = 30 grey levels	always found	always found

Two results are worth a closer look. SIFT’s weakness to darkening comes from the detector, not the descriptor: the descriptor is normalised, but keypoints are kept only if their DoG response exceeds an absolute contrast threshold, and darkening an image lowers every contrast. Fewer keypoints survive, and the remaining ones are less stable. ORB’s failure when the second image is enlarged is likely tied to its pyramid: it builds 8 levels by shrinking each image by 1.2 per level, and with a fixed budget of 2,000 keypoints, mostly at the fine levels, the coarse levels of the enlarged image may not hold enough matching keypoints. SIFT, with its continuous scale space and sub-scale refinement, found the homography at every scale tested.

These synthetic changes are easier than real photo pairs taken at different times, under different lighting and from very different angles. Benchmarks such as HPatches (Balntas et al., 2017) and the Image Matching Challenge (Jin et al., 2021) test exactly that; in the latter, a well-tuned SIFT with a good RANSAC remained competitive with many learned methods of its time.

8. Putting It Together: Panoramas

A panorama is the textbook application (Brown & Lowe, 2007): detect SIFT features in all images, match them with the ratio test, estimate the homography between overlapping images with RANSAC, and warp everything into one frame. As Image Formation showed, one homography per image pair is exact only if the camera rotates about its centre (or the scene is flat); for wide panoramas the images are projected onto a cylinder or sphere instead of a plane. Two more steps make the result look seamless: gain compensation equalises the exposure of the images, and multi-band blending (Burt & Adelson, 1983) blends low frequencies over a wide region and high frequencies over a narrow one. Simply averaging overlapping images leaves visible seams and “ghosts” of anything that moved.

9. Learned Features

Each step of this pipeline has a learned counterpart. SuperPoint (DeTone et al., 2018) detects and describes keypoints with one network, trained on synthetic shapes and then on homography-warped real images, a form of self-supervision. DISK (Tyszkiewicz et al., 2020) and ALIKED (Zhao et al., 2023) learn detection and description end to end. SuperGlue (Sarlin et al., 2020) and LightGlue (Lindenberger et al., 2023) replace nearest-neighbour matching and the ratio test with a Transformer that uses self- and cross-attention between the two sets of keypoints, the same attention as in Attention from Scratch. LoFTR (Sun et al., 2021) skips keypoints altogether and matches dense Transformer features. OpenCV 5 now ships DISK, ALIKED and a LightGlue matcher next to SIFT and ORB. These are the subject of a later post.

10. Common Claims, Checked

Claim	Verdict
”RANSAC and ICP are methods for matching features.”	Matching pairs descriptors (nearest neighbour, ratio test). RANSAC verifies matches by robustly fitting a transformation; ICP aligns 3D point clouds without known correspondences.
”Edges are good keypoints.”	No: along an edge the position is undetermined (the aperture problem). Good keypoints have strong gradients in two directions: corners and blobs.
”SIFT’s DoG detects edges.”	The DoG responds to blobs. SIFT explicitly rejects keypoints on edges, using the ratio of principal curvatures.
”SIFT compares each sample with its 8 neighbours.”	With 26: 8 in the same scale and 9 each in the scales above and below. Both maxima and minima are kept.
”The keypoint orientation is $tan^{- 1} (I_{y} / I_{x})$ .”	That only covers 180°. SIFT uses the full-circle $atan2$ and takes the peak of a 36-bin, magnitude-weighted orientation histogram.
”SIFT is invariant to illumination.”	The descriptor is invariant to a brightness offset and a contrast factor. The detector is not: its contrast threshold is absolute. Darkened to 30%, SIFT kept 254 of 1,518 correct matches and failed on 1 of 4 photos.
”SIFT is the best detector.”	It depends on the change. In the tests above, SIFT handled scaling and blur better than ORB, ORB handled darkening better and is much faster. Learned methods now beat both on hard benchmarks.
”A distance threshold decides which matches are correct.”	A fixed threshold suits no image completely. The ratio test adapts per keypoint: at 0.8 it removed 95.7% of SIFT’s wrong matches and kept 93.7% of the correct ones.
”With enough matches, least squares will average out the wrong ones.”	Least squares has no defence against outliers: on the lab’s pair it was 128 px off. RANSAC, then a refit on its inliers, was within a fraction of a pixel.
” $k = lo g (1 - p) / lo g (1 - w^{4})$ iterations give success with probability $p$ .”	Only if every all-inlier sample gives the right model. Measured with noise, success was lower: 62.5% instead of 96% (50% outliers, 50 iterations), 89.5% with a refit. Iterate more, or use LO-RANSAC.
”Panoramas are made by translating, rotating and scaling images, then averaging them.”	Overlapping photos from a rotating camera are related by homographies (or projected onto a cylinder). Gain compensation and multi-band blending avoid the seams and ghosts that averaging produces.

Summary

Idea	Why
Detect → describe → match → verify	Each step solves one problem; matching uses appearance, verification geometry
Structure tensor, Harris	Corners can be relocated; edges suffer from the aperture problem
DoG scale space, 26 neighbours	Each keypoint gets a position and a characteristic scale
SIFT descriptor: 4 × 4 × 8, normalised	Invariant to rotation, scale and affine brightness changes
ORB: FAST + rotated BRIEF, Hamming distance	Much faster, less robust to large scale changes
Ratio test $d_{1} / d_{2} < 0.8$	Removes most wrong matches, keeps most correct ones
RANSAC + refit on inliers	Robust to many wrong matches; needs more iterations than the formula suggests

Next: From Two Views to 3D: Epipolar Geometry, Triangulation and Bundle Adjustment: when the camera moves instead of only rotating, no homography fits. Epipolar geometry, the essential and fundamental matrices, triangulation, and bundle adjustment recover the camera motion and the scene’s depth.

References

Keypoints and descriptors

Moravec, H. P. (1980). Obstacle avoidance and navigation in the real world by a seeing robot rover. PhD thesis, Stanford University.
Harris, C., & Stephens, M. (1988). A combined corner and edge detector. Alvey Vision Conference.
Shi, J., & Tomasi, C. (1994). Good features to track. CVPR.
Lindeberg, T. (1998). Feature detection with automatic scale selection. IJCV, 30(2).
Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. IJCV, 60(2).
Bay, H., Tuytelaars, T., & Van Gool, L. (2006). SURF: Speeded up robust features. ECCV.
Rosten, E., & Drummond, T. (2006). Machine learning for high-speed corner detection. ECCV.
Calonder, M., Lepetit, V., Strecha, C., & Fua, P. (2010). BRIEF: Binary robust independent elementary features. ECCV.
Rublee, E., Rabaud, V., Konolige, K., & Bradski, G. (2011). ORB: An efficient alternative to SIFT or SURF. ICCV.

Robust estimation

Fischler, M. A., & Bolles, R. C. (1981). Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6).
Rousseeuw, P. J. (1984). Least median of squares regression. Journal of the American Statistical Association, 79(388).
Torr, P. H. S., & Zisserman, A. (2000). MLESAC: A new robust estimator with application to estimating image geometry. CVIU, 78(1).
Chum, O., Matas, J., & Kittler, J. (2003). Locally optimized RANSAC. DAGM.
Barath, D., Matas, J., & Noskova, J. (2019). MAGSAC: Marginalizing sample consensus. CVPR.

Applications and benchmarks

Burt, P. J., & Adelson, E. H. (1983). A multiresolution spline with application to image mosaics. ACM Transactions on Graphics, 2(4).
Brown, M., & Lowe, D. G. (2007). Automatic panoramic image stitching using invariant features. IJCV, 74(1).
Balntas, V., Lenc, K., Vedaldi, A., & Mikolajczyk, K. (2017). HPatches: A benchmark and evaluation of handcrafted and learned local descriptors. CVPR.
Jin, Y., Mishkin, D., Mishchuk, A., Matas, J., Fua, P., Yi, K. M., & Trulls, E. (2021). Image matching across wide baselines: From paper to practice. IJCV, 129.

Learned features and matchers

DeTone, D., Malisiewicz, T., & Rabinovich, A. (2018). SuperPoint: Self-supervised interest point detection and description. CVPR Workshops.
Tyszkiewicz, M. J., Fua, P., & Trulls, E. (2020). DISK: Learning local features with policy gradient. NeurIPS.
Sarlin, P.-E., DeTone, D., Malisiewicz, T., & Rabinovich, A. (2020). SuperGlue: Learning feature matching with graph neural networks. CVPR.
Sun, J., Shen, Z., Wang, Y., Bao, H., & Zhou, X. (2021). LoFTR: Detector-free local feature matching with Transformers. CVPR.
Zhao, X., Wu, X., Chen, W., Chen, P. C. Y., Xu, Q., & Li, Z. (2023). ALIKED: A lighter keypoint and descriptor extraction network via deformable transformation. IEEE Transactions on Instrumentation and Measurement.
Lindenberger, P., Sarlin, P.-E., & Pollefeys, M. (2023). LightGlue: Local feature matching at light speed. ICCV.

Notes

Explorer