Skip to main content

SIFT: Distinctive Image Features from Scale-Invariant Keypoints

Trace SIFT from extrema in scale space to orientation-normalized 128-dimensional descriptors and ambiguity-aware matching, with original PDF excerpts and inspectable reference operations.

TL;DR

  • SIFT finds local extrema across position and scale, refines their locations and rejects low-contrast or edge-like candidates.
  • Orientation assignment establishes a local frame; a 4×4×8 gradient descriptor preserves coarse spatial structure while tolerating small shifts.
  • Descriptor normalization, clipping and renormalization improve robustness within a limited photometric model. The ratio test checks match ambiguity, and geometric verification checks consistency.
  • The cited matching results depend on the paper’s transformation, noise and database conditions. The runnable reference checks supplied-input operations rather than implementing or benchmarking the complete SIFT pipeline.

Why matching needs a repeatable local frame

Two photographs can contain the same object at different sizes, rotations and positions. Comparing their raw pixels does not provide a stable identity for a small visible region. SIFT gives each selected region a repeatable local coordinate frame, then describes the distribution of gradients within that frame. Matching becomes a comparison of those descriptions, followed by tests of distinctiveness and geometry.

David Lowe’s 2004 paper, “Distinctive Image Features from Scale-Invariant Keypoints”, develops the detector, orientation assignment, descriptor and recognition pipeline together. This review follows the January 5, 2004 author PDF accepted for International Journal of Computer Vision. It expands the earlier 1999 SIFT work; the original publication year is separate from this write-up’s date.

The interactive figures use authored neighborhoods and calculated histogram values. They explain individual operations without pretending to extract features from photographs. The reference does not implement the complete image pyramid, subpixel fitting, descriptor voting or recognition system. Reported matching results below are cited from the paper, with their experimental conditions.

Search for a feature at its characteristic scale

A fixed-size window describes different physical content when the camera moves closer. SIFT searches over both image position and scale so the selected region can grow or shrink with the underlying structure. It builds a Gaussian scale space by smoothing the image at progressively larger σ values:

L(x,y,\sigma)=G(x,y,\sigma)*I(x,y),\qquad D(x,y,\sigma)=L(x,y,k\sigma)-L(x,y,\sigma)

The difference of Gaussians, or DoG, approximates a scale-normalized Laplacian up to a factor related to k−1. Nearby Gaussian images are already needed for feature description, so their difference is convenient to compute. This approximation motivates searching its extrema; it is not the same operation as simply running an edge detector at one blur setting. §3

Each octave covers a factor of two in scale. After enough smoothing, the representation is downsampled and the next octave continues at lower resolution. With s scale intervals per octave, k=2^(1/s). The paper’s sampling analysis favors three intervals per octave, balancing repeatability and the cost of denser sampling. Additional Gaussian and DoG levels provide the neighboring scales needed to detect extrema at the octave boundaries.

A candidate compares its DoG value with eight neighbors at the current scale and nine at each adjacent scale, for twenty-six comparisons. It must exceed all of them or be below all of them. Looking only for maxima in each two-dimensional image misses the scale-selection requirement; looking only for bright blobs misses minima, which are also valid candidates.

A peak must survive scale and curvature tests

The center competes with 26 neighbors across three DoG images. Then the spatial Hessian rejects unstable ridge-like responses. These are separate tests.

Scale below

0.8
0.4
0.5
0.6
0.7
0.3
0.4
0.5
0.6

Scale current

0.3
0.4
0.5
0.6
1.2
0.3
0.4
0.5
0.6

Scale above

0.3
0.4
0.5
0.6
0.7
0.3
0.4
0.5
0.6
1.2
0.8
3

Strict local extremum: yes. Hessian trace²/determinant = 5.33; threshold 12.10: pass. Combined illustrative decision: keep candidate.

Authored DoG neighborhood and diagonal Hessian. Full SIFT additionally localizes extrema with a 3D quadratic fit and rejects low interpolated contrast. It does not test the raw center alone.

The explorer deliberately separates the extremum test from the spatial-curvature test. Raising one neighboring response can invalidate a peak even when the center remains large. Changing the Hessian ratio can invalidate a ridge-like candidate even when it still wins all its local comparisons.

Locate accurately, then reject unstable candidates

The sampled extremum is an initial estimate. The paper fits a three-dimensional quadratic Taylor expansion in x, y and scale, then solves for the interpolated offset. If the offset indicates a closer sample, the fit is moved and repeated. Contrast is evaluated at the fitted position, rather than inferred solely from the original grid value. With image intensities normalized to [0,1], the reported experiments reject extrema whose interpolated absolute DoG value is below 0.03. §4, Equations 2–3

High contrast alone is insufficient. A long edge can give a strong response while leaving position along the edge uncertain. SIFT examines the two-dimensional spatial Hessian at the candidate. One large principal curvature and one small curvature signal that instability. The trace and determinant give a cheap test of their ratio without explicitly finding both eigenvalues:

\frac{\operatorname{Tr}(H)^2}{\det H}<\frac{(r+1)^2}{r},\qquad r=10

A nonpositive determinant is rejected. At the paper’s ratio threshold, the right side is 12.1. This curvature test is different from nonmaximum suppression and from rejecting low contrast. Figure 5 illustrates their cumulative effects: an example 233×189 image yields 832 initial extrema, 729 after contrast rejection and 536 after edge-response rejection. Those are counts for that particular image and parameter setting, not expected keypoint counts for every photograph. §4.1 and Figure 5

Orientation provides a local reference frame

Once location and scale are assigned, SIFT estimates a dominant orientation from gradients in the corresponding Gaussian-smoothed image. Its orientation histogram has 36 bins, with contributions weighted by gradient magnitude and a Gaussian window whose σ is 1.5 times the keypoint scale. The strongest peak supplies an orientation, and nearby histogram values refine the peak position. §5

A location can produce more than one oriented keypoint. Other local peaks reaching at least 80% of the strongest peak receive their own orientation assignments. The paper reports that about 15% of points receive multiple orientations, helping stability when a region has competing dominant structures. These are multiple frames at the same position and scale, not evidence that the detector accidentally found duplicate spatial extrema.

To compare rotated views, the descriptor rotates both sample coordinates and gradient directions relative to the selected keypoint orientation. Merely subtracting an angle from histogram labels while leaving the spatial sampling grid fixed would not implement the complete normalization. Rotation invariance also depends on repeatably assigning the same frame; it is not an unconditional property of any 128-number vector.

A descriptor keeps coarse geometry and tolerates small shifts

The SIFT descriptor pools oriented gradients into a 4×4 array of spatial histograms, each with eight orientation bins, giving 128 components. The spatial layout matters. One global orientation histogram would discard where the gradients occur, making different patterns harder to distinguish. At the same time, pooling within subregions is more tolerant of small positional errors than matching raw pixels. §6.1

A Gaussian window downweights gradients far from the center. Trilinear interpolation distributes each sample between neighboring spatial and orientation bins, avoiding sudden jumps when a gradient crosses a cell boundary or an angular boundary. The original figure uses a 2×2 drawing for legibility, while the experimental descriptor uses 4×4; counting the schematic’s arrows is not a reliable way to infer its dimensionality.

Sixteen spatial cells, eight orientation bins each

Select a spatial cell in an authored 128-component histogram. Adjust clipping to see normalize → clip → renormalize. Below, rotate the orientation reference to see how a gradient is expressed relative to the keypoint.

0°45°90°135°180°225°270°315°

0.432 · 0.049 · 0.049 · 0.049 · 0.049 · 0.049 · 0.049 · 0.049

0.2
90
0

128 = 4 × 4 × 8 dimensions. Final L2 norm: 1.0000. Relative orientation bin position: 2.00. Renormalization can raise a final component above the clipping threshold.

Calculated descriptor arithmetic on fixed nonnegative histogram values. Full SIFT forms Gaussian-weighted, trilinearly interpolated votes; this explorer does not extract descriptors from an image. Bin position is fractional before interpolation.

The explorer starts from an authored, nonnegative histogram vector. It implements the next three operations exactly: L2 normalize, clip components at 0.2, then L2 normalize again. The first normalization reduces sensitivity to an overall gradient-magnitude scale. Clipping limits the influence of a few very strong gradients, which may be affected disproportionately by illumination changes or saturation.

The second normalization is essential. It also means that 0.2 is not an upper bound on the final vector: rescaling the clipped vector to unit length can raise some components above that value. Applying a square-root transform would instead introduce the different RootSIFT representation; it is not part of this paper’s descriptor.

The original argument for photometric robustness has a defined scope. A constant brightness offset cancels in differences, and a positive multiplicative contrast change is removed by normalization in the ideal model. Shadows, saturation, surface-dependent illumination and severe viewpoint changes need not follow that model. SIFT is designed to tolerate a useful range of distortions; it is not fully affine-invariant or invariant to arbitrary three-dimensional appearance change.

Match against ambiguity, not just absolute distance

A query descriptor’s nearest neighbor might still be a poor match. Repetitive texture can produce several nearly identical candidates. A fixed distance threshold does not distinguish that ambiguity from a highly distinctive descriptor whose nearest incorrect alternative is much farther away.

SIFT compares the nearest distance d1 with the runner-up distance d2. A low d1/d2 ratio indicates a separated best candidate. The paper uses a threshold of 0.8, and discusses selecting a runner-up from a different object when several training images of the same object are known. §7.1

A nearest neighbor can still be ambiguous

Compare the nearest and second-nearest descriptor distances. A close runner-up makes the best candidate less distinctive, even when its absolute distance is small.

0.6
1
0.8

d1 / d2 = 0.600 < 0.80 → accept distinctive candidate

Unsquared Euclidean distances and a strict ratio comparison. The paper uses 0.8 and describes the second neighbor from a different object when multiple training views are known. This test alone does not verify geometric consistency.

Our reference uses a strict ratio comparison, a common implementation convention; the original prose describes rejecting values greater than 0.8. All distances here are unsquared Euclidean distances. An implementation using squared distances must square the threshold too: comparing d1²/d2² with 0.8 changes the decision relative to comparing d1/d2 with 0.8.

A ratio-test pass is still only a candidate correspondence. The recognition system clusters matches by pose using a Hough-transform approach and verifies consistency using a least-squares pose fit. Those later checks reject accidental correspondences that individually look distinctive but cannot agree on a plausible object placement. The complete pipeline therefore combines local appearance evidence with geometric agreement.

What the matching experiments establish

Descriptor dimensionality is evaluated under a 50-degree planar viewpoint tilt with 4% added image noise, matching against a database of 40,000 keypoints. Figure 8 compares spatial-histogram sizes and orientation-bin counts. The chosen 4×4×8 representation balances discrimination against sensitivity to distortion; increasing the number of cells or bins is not monotonically beneficial under those difficult conditions. §6.2

For the ratio test, Figure 11 uses random scale and orientation changes, a 30-degree depth rotation and 2% image noise, again against 40,000 database keypoints. In that experiment, rejecting ratios above 0.8 removes 90% of false matches while discarding fewer than 5% of correct matches. This is evidence for a useful operating point on that study’s distribution, not a universal false-match guarantee for every camera, scene or database. Changing the distractor population can change the nearest-neighbor distance distribution. §7.1, Figure 11

The experiments also separate repeatable detection from descriptor matching. If a location or scale fails to repeat, no excellent descriptor can recover that missing correspondence. Conversely, a repeatable keypoint can still have an ambiguous descriptor. Treating the detector and descriptor as distinct failure points helps interpret why a downstream matching system fails.

Original sources alongside runnable operations

The annotated rows show original excerpts for the scale-space neighborhood, Hessian criterion, descriptor postprocessing and ratio test. The standard-library Python is intentionally limited to those supplied-input operations. It omits full Gaussian-weighted, trilinearly interpolated image descriptors and makes no claim to reproduce a SIFT benchmark.

1. Compare all 26 scale-space neighbors

Original paper

Figure 2: extrema across scale

Three 3×3 neighborhoods minus the center → 26 comparisons.

Math and tensor shapes

\begin{aligned}D(x,y,\sigma)&=L(x,y,k\sigma)\\ &\quad-L(x,y,\sigma)\end{aligned}

Three 3×3 neighborhoods minus the center → 26 comparisons.

The reference checks strict maxima or minima in a supplied neighborhood. It does not construct a Gaussian pyramid or refine keypoints. Full SIFT performs a 3D Taylor fit in position and scale and evaluates contrast at the interpolated location.

Python implementation

sift.py · extrema
python
def is_extremum(center, neighbors):
    """Eight same-scale neighbors, nine above and nine below."""
    if len(neighbors)!=26:
        raise ValueError('Expected 26 neighbors')
    return all(center>v for v in neighbors) or all(center<v for v in neighbors)

2. Reject unstable edge-like responses

Original paper

§4.1: eliminating edge responses

Spatial Hessian 2×2 at the candidate; threshold 12.1.

Math and tensor shapes

\begin{aligned}\det H&>0\\ \frac{\operatorname{Tr}(H)^2}{\det H}&<\frac{(r+1)^2}{r}\\ r&=10\end{aligned}

Spatial Hessian 2×2 at the candidate; threshold 12.1.

The trace/determinant ratio tests whether one principal curvature overwhelms the other. It is distinct from contrast rejection: a large DoG response can still lie on an unstable edge. Nonpositive determinant is rejected before dividing.

Python implementation

sift.py · edge
python
def edge_score(dxx,dyy,dxy):
    determinant=dxx*dyy-dxy*dxy
    return math.inf if determinant<=0 else (dxx+dyy)**2/determinant


def edge_accepted(dxx,dyy,dxy,r=10):
    return edge_score(dxx,dyy,dxy)<(r+1)**2/r

3. Normalize, clip, and normalize again

Original paper

§6.1: descriptor normalization

4×4 spatial cells × 8 orientation bins = 128 components.

Math and tensor shapes

\begin{aligned}\hat v&=v/\|v\|_2\\ u_j&=\min(\hat v_j,0.2)\\ d&=u/\|u\|_2\end{aligned}

4×4 spatial cells × 8 orientation bins = 128 components.

This operation receives already accumulated nonnegative histogram values. Full SIFT rotates sample coordinates and gradient directions, applies a Gaussian window, and distributes votes with trilinear interpolation. These preceding operations are deliberately omitted. The final normalization may raise a component above 0.2.

Python implementation

sift.py · descriptor
python
def normalize_descriptor(values,clip=0.2):
    """L2 normalize, clip components, then L2 normalize again; not RootSIFT."""
    norm=math.sqrt(sum(v*v for v in values))
    if norm==0:
        return [0.0]*len(values)
    clipped=[min(v/norm,clip) for v in values]
    norm=math.sqrt(sum(v*v for v in clipped))
    return [v/norm for v in clipped]


def orientation_bin(angle,reference=0,bins=8):
    return ((angle-reference)%360)/360*bins

4. Reject a best match without enough separation

Original paper

§7.1: nearest-neighbor distance ratio

Two unsquared Euclidean distances for each query descriptor.

Math and tensor shapes

\begin{aligned}\frac{\|d-q_1\|_2}{\|d-q_2\|_2}&<\tau\\ \tau&=0.8\end{aligned}

Two unsquared Euclidean distances for each query descriptor.

The strict comparison is a conventional implementation boundary; the original prose describes rejecting ratios greater than 0.8. If using squared distances, compare against 0.8². An undefined zero runner-up distance is rejected. Passing the ratio test still requires geometric verification for object recognition.

Python implementation

sift.py · matching
python
def ratio_accepted(first,second,threshold=0.8):
    """Unsquared Euclidean distances. Reject an undefined second distance."""
    return first>=0 and second>0 and first/second<threshold

Original source excerpts: David G. Lowe. International Journal of Computer Vision 60(2), 91–110 (2004), author PDF. Cropped and rasterized from the hash-pinned author PDF; colors unchanged. Source page, rectangle and image hashes are recorded in the crop manifest. No open license is asserted where none was verified.

Run python examples/sift.py or add --json for deterministic parity values. Checks include strict extrema, rejection of a highly anisotropic Hessian, orientation wrapping and unit-norm descriptor output. Download the reference, requirements and provenance notes.

SIFT’s useful organizing idea is the order of its commitments: find a repeatable position and scale, establish an orientation frame, summarize local structure in that frame, then ask whether the best correspondence is sufficiently distinctive and geometrically consistent. Each stage removes a particular source of ambiguity. Keeping those stages visible is more explanatory than treating the final 128-dimensional vector as a generic image embedding.

If you found this paper review helpful, consider sharing it with others.

Mastodon