Distinctive Image Features from Scale-Invariant Keypoints

David Lowe of the University of British Columbia introduced the Scale Invariant Feature Transform (SIFT) in “Object Recognition from Local Scale-Invariant Features”, presented at the Seventh International Conference on Computer Vision (ICCV) in Corfu in September 1999. He described it in full in “Distinctive Image Features from Scale-Invariant Keypoints”, published in the International Journal of Computer Vision in 2004. The journal paper presents itself as a more in-depth development and analysis of the conference paper, with improvements in stability and invariance, so this article treats the two as one publication and notes where they differ. Together they turned an image into a large set of local features that could be matched across changes in scale, rotation, illumination, and moderate viewpoint, and showed that a few such matches suffice to recognize an object in clutter. The 1999 paper received the 2011 Helmholtz Prize. The algorithm as used today is described in the SIFT article.

Problem

Lowe framed the task as recognizing specific objects in cluttered real-world scenes, where features must be unaffected by nearby clutter and partial occlusion, at least partly invariant to illumination and 3D projection, and distinctive enough to pick one object among many. Line segments, edge groupings, and regions had worked for some object classes but, he argued, were not detected often or stably enough.

The closest prior work was Schmid and Mohr’s 1997 recognition system, which placed descriptors at Harris corners and found objects by looking for groups of matches consistent in orientation and location. Both papers point to the same weakness: the Harris detector is sensitive to changes in image scale. The 1999 paper adds that it examines the image at a single scale, so it responds to different points once the scale changes, and gives no scale at which to sample a descriptor.

Contribution

• Keypoints detected in scale space. Locations and scales are taken at extrema of a difference-of-Gaussian (DoG) function, computed efficiently in an image pyramid, so the same points are found when the image is rescaled, and each comes with an explicit scale.
• A canonical local frame. Each keypoint gets an orientation from local gradient directions, so the region is described relative to its position, scale, and orientation rather than with rotation-invariant measures.
• A descriptor that tolerates distortion. Gradients are pooled into coarse spatial cells by orientation, so features may shift by a few pixels without changing the vector much. Lowe tied the idea to complex cells in visual cortex, following Edelman, Intrator, and Poggio.
• A recognition system built on many features. Matches found by approximate nearest-neighbor search vote for an object pose in a Hough transform, and clusters of at least three are verified with a least-squares affine fit.

Method

1999. The conference version built its pyramid from two Gaussian blurs of $\sigma = \sqrt{2}$, subtracting them to form the DoG, and resampled each level with a pixel spacing of 1.5. The input was first doubled in size, which gave on the order of 1,000 keys for a $512 \times 512$ image, about four times as many as without doubling. Keys were placed at the sample point of each extremum. Gradient magnitudes were capped at 0.1 of their maximum possible value to reduce the effect of illumination changes, and a smoothed 36-bin orientation histogram gave each key a single orientation. The descriptor sampled gradients within a radius of 8 pixels into 8 orientation planes on a $4 \times 4$ grid, and repeated this one octave higher on a $2 \times 2$ grid, for $8 \times 4 \times 4 + 8 \times 2 \times 2 = 160$ elements. Matching used Beis and Lowe’s best-bin-first search, a k-d tree variant, with the coarser scale weighted double; the verification step solved for six affine parameters by least squares and discarded matches that disagreed with the solution.

2004. The journal version restated the detector as octaves of $s$ intervals with $k = 2^{1/s}$ and derived the DoG’s link to Lindeberg’s scale-normalized Laplacian,

$$G(x, y, k\sigma) - G(x, y, \sigma) \approx (k - 1)\, \sigma^2 \nabla^2 G .$$

It set parameters by experiment on 32 images under synthetic transformations, where the true position of every feature is known: three scales per octave gave the highest repeatability, and an initial blur of $\sigma = 1.6$ came close to the best at reasonable cost. The main changes were:

• Interpolated keypoints. A quadratic Taylor fit to the DoG locates each extremum in position and scale, a method Lowe credits to Matthew Brown (Brown and Lowe, 2002). Extrema with $|D(\hat{\mathbf{x}})| < 0.03$ are dropped.
• Edge rejection. A test on the trace and determinant of the $2 \times 2$ Hessian, borrowed from Harris and Stephens, discards extrema whose principal curvatures differ by more than a factor of 10. On one example image these two tests cut 832 extrema to 536 keypoints.
• Multiple orientations. Every histogram peak within 80% of the highest creates its own keypoint; about 15% of points receive more than one.
• The 128-element descriptor. A $4 \times 4$ grid of 8-bin histograms over a $16 \times 16$ sample window, with trilinear interpolation, normalized to unit length, clipped at 0.2, and renormalized. The single-scale grid replaced the two-scale 160-element vector.
• The ratio test. A match is rejected when the nearest descriptor is not closer than 0.8 times the second nearest.
• Stronger verification. Inliers must agree within half the Hough bin widths, the fit is iterated, a top-down pass adds further consistent matches, and a probabilistic model from Lowe’s 2001 paper accepts an object only if the probability of a correct interpretation exceeds 0.98.

	1999 (ICCV)	2004 (IJCV)
Keypoint position	Sample point	Quadratic interpolation in position and scale
Rejection tests	None described	Contrast $0.03$, edge ratio $r = 10$
Orientations per keypoint	One	One per peak within 80% of the highest
Descriptor	160 elements, two scales	128 elements, $4 \times 4 \times 8$, one scale
Match filtering	Nearest neighbor only	Distance ratio below 0.8
Acceptance	At least 3 agreeing matches after outlier removal	Probabilistic test, probability above 0.98

For recognition, both versions cluster matches with a Hough transform rather than a robust fit such as RANSAC. The 2004 paper explains why: the correct matches for one object can be under 1% of all matches, and RANSAC and least median of squares perform poorly once inliers fall much below 50%.

The details of each step are in the SIFT article; feature matching covers the ratio test.

Results

The 1999 paper measured stability on 20 images, about 15,000 keys. Under a combination of contrast, brightness, rotation, scale, stretch, and noise changes, 78.6% of keys reappeared at the predicted location and scale and 71.8% also matched in orientation. In recognition experiments, planar objects were recognized up to at least 60° of rotation away from the camera and 3D objects over about 20° of rotation in depth. Recognizing all objects in a $384 \times 512$ image took about 1.5 seconds on a Sun Sparc 10.

The 2004 paper quantified each stage against a database of 40,000 keypoints. Orientation assignment stayed accurate 95% of the time even with 10% pixel noise, and most matching failures came from detecting location and scale. The $4 \times 4 \times 8$ descriptor was chosen as the best size for a 50° tilt with 4% noise, and final matching accuracy stayed above 50% out to a 50° viewpoint change. The ratio test removed 90% of false matches while discarding less than 5% of correct ones, and stopping best-bin-first after 200 candidates sped up search over 100,000 keypoints by about two orders of magnitude with under 5% loss of correct matches. Recognition of all objects in the paper’s example scenes took under 0.3 seconds on a 2 GHz Pentium 4. Lowe reported reliable recognition of textured planar surfaces up to 50° of rotation in depth and of 3D objects up to about 30°.

Impact

The journal paper is widely cited, and SIFT became the reference local feature against which others were measured. In Mikolajczyk and Schmid’s 2005 comparison of ten descriptors, SIFT-based descriptors performed best; their extension GLOH obtained the best results in most tests, closely followed by SIFT, and SIFT did relatively better when matches were filtered with the nearest-neighbor distance ratio. The 2004 paper names panorama assembly, 3D reconstruction, and robot localization as further applications, and Brown and Lowe’s 2007 panorama stitching system matches images with SIFT features.

The PAMI Technical Committee lists the 1999 paper among the three winners of the 2011 Helmholtz Prize, which recognizes ICCV papers from about ten years earlier that have had a significant impact on the field.

The University of British Columbia held U.S. patent 6,711,293 on the method, with Lowe as inventor, filed in March 2000 and granted in March 2004; it expired in 2020. OpenCV 3.0 had moved SIFT into the separate xfeatures2d contributed module, and OpenCV 4.4.0 (July 2020) moved it into the main repository, noting in its release log that the patent had expired.

Limitations

• Partial affine invariance. The frame normalizes only position, scale, and orientation. The 2004 paper argues that this suffices for most 3D objects, since training views are needed every 30° or so anyway, but notes that affine-invariant detectors keep better repeatability beyond about 50° of tilt, citing Mikolajczyk’s experiments.
• Viewpoint limits for 3D objects. Reliable recognition reached only about 30° of rotation in depth, so Lowe recommended combining features from several training views.
• Synthetic evaluation. Parameters were set on images with synthetic transformations; the journal paper itself calls for systematic testing on data with full 3D viewpoint and illumination changes.
• Intensity only. Lowe suggested adding color and texture descriptors and combining many feature types.
• Affine pose model. Verification approximates 3D pose with an affine transformation and wide error bounds; solving for the fundamental matrix needs at least seven matches, against three for the affine model.

What Came After

Variants appeared even before the journal paper was published. Ke and Sukthankar (CVPR 2004) kept SIFT’s keypoints but applied principal component analysis to the normalized gradient patch, reporting a more compact and more distinctive descriptor. Bay, Tuytelaars, and Van Gool’s SURF (2006) used integral images and a Hessian-based detector, reporting performance comparable to or better than earlier schemes at much lower cost. Rublee and colleagues presented ORB (2011) explicitly as an alternative to SIFT or SURF, reporting a binary descriptor two orders of magnitude faster than SIFT that performed as well in many situations. Arandjelović and Zisserman (2012) showed that comparing SIFT vectors with a Hellinger kernel, which they called RootSIFT, improved object retrieval with no extra processing or storage.

The journal paper’s conclusion also anticipated learning features from data. When learned descriptors arrived, SIFT was their baseline. Schönberger and colleagues (2017) found that advanced hand-crafted variants, RootSIFT-PCA and DSP-SIFT, still performed on par with or better than the learned descriptors they tested, especially for image-based reconstruction, and that the learned ones varied widely across datasets. The feature descriptors article surveys these descendants.