SIFT

SIFT

SIFT (Scale-Invariant Feature Transform) is a feature detector and descriptor that produces keypoints invariant to scale, rotation, and moderate illumination change, along with a 128-dimensional descriptor vector used for matching. It is the canonical feature in classical computer vision and remains a baseline against which every modern detector (ORB, SuperPoint) is measured.

The pipeline has four stages:

1. Scale-space extrema detection. Build a Gaussian scale-space pyramid $L(x,y,\sigma )=G(x,y,\sigma )\ast I(x,y)$ and compute the difference of Gaussians (DoG) across adjacent scales:
   $D(x,y,\sigma )=L(x,y,k\sigma )-L(x,y,\sigma ).$
   Keypoints are local extrema of $D$ over the $3\times 3\times 3$ spatial-scale neighborhood.

2. Keypoint localization. Subpixel refinement via a Taylor expansion of $D$; reject low-contrast and edge-like extrema using the Hessian determinant-to-trace ratio (same criterion as Harris).

3. Orientation assignment. Compute a gradient orientation histogram in a neighborhood around the keypoint, weighted by magnitude and a Gaussian window. The peak orientation (and any secondary peak within 80% of it) becomes the keypoint’s canonical orientation.

4. Descriptor construction. Rotate the $16\times 16$ patch around the keypoint to its canonical orientation, divide into a $4\times 4$ grid of subregions, compute an 8-bin gradient orientation histogram in each subregion, and concatenate into a $4\cdot 4\cdot 8=128$-dimensional descriptor. Normalize to unit length; clip values above $0.2$; renormalize.

Descriptors are matched across images by nearest-neighbor search in descriptor space, filtered by Lowe’s ratio test.

Intuition

Harris corners are local features but not scale-invariant: zooming in on an image changes which pixels look corner-like. SIFT layers two ideas on top of Harris to fix this. First, scale selection: search for features not just spatially but across a Gaussian pyramid, picking the scale at which each feature is most distinctive (automatic scale selection via DoG extrema). Second, a rich descriptor: once a keypoint is localized and oriented, summarize the gradient pattern in its neighborhood as a fingerprint that can be compared against other fingerprints by simple Euclidean distance.

The geometric invariances are earned one at a time: scale invariance from the pyramid, rotation invariance from the canonical orientation assignment, illumination invariance from gradient-based descriptors and the normalize-clip-renormalize step. The descriptor’s grid-of-histograms structure trades exact pixel-matching for tolerance to small spatial deformations — two patches agree on their descriptor as long as they agree on the distribution of gradients in corresponding subregions, which is much more forgiving than requiring pixel-perfect alignment.

Properties

Scale-Space Construction

(Gaussian pyramid) Successive blurs with $\sigma ,k\sigma ,k^2\sigma ,\dots$ produce an octave of scales; downsampling by 2 starts the next octave.

Typical parameters: ${\sigma }_0=1.6$, $s=3$ scales per octave, $k=2^{1/s}$. The pyramid covers several octaves of scale (often 4–6) to catch features at all sizes.

(Difference of Gaussians) DoG approximates the scale-normalized Laplacian ${\sigma }^2{\nabla }^{2}L$, whose extrema are the characteristic scales.

Analytically, $G(x,y,k\sigma )-G(x,y,\sigma )\approx (k-1){\sigma }^2{\nabla }^{2}G$, so DoG is a cheap approximation to the Laplacian without convolving with a second-derivative kernel. Extrema of DoG in the joint spatial-scale domain mark “blobs” at their characteristic scales.

Keypoint Filtering

(Subpixel localization) A second-order Taylor expansion of $D$ about the discrete extremum yields the offset to the true continuum maximum.

Setting $\partial D/\partial x=0$ gives a linear system whose solution $\hat{x}$ is the subpixel offset. If $|\hat{x}|>0.5$ in any dimension, the keypoint is reassigned to the nearest neighbor and the solve is repeated.

(Edge rejection) Extrema along edges have one small and one large principal curvature; ratioing the Hessian’s trace and determinant flags them.

The $2\times 2$ Hessian of $D$ in the spatial plane has eigenvalues $\alpha \ge \beta$. If $\alpha /\beta =r$, then ${\mathrm{tr}}^2(H)/\det (H)=(r+1{)}^2/r$, which is minimized at $r=1$. SIFT rejects keypoints with $r>10$, eliminating edge-like responses.

Descriptor Design

(Rotation normalization) Each keypoint is rotated to its dominant gradient orientation before descriptor extraction.

The orientation histogram has 36 bins covering $[0,2\pi )$, each weighted by gradient magnitude times a Gaussian centered on the keypoint. The argmax (fitted with a parabola for subbin accuracy) becomes the canonical orientation; the patch is then rotated so this direction is “up.”

(Spatial-orientation histogram) The descriptor is a $4\times 4$ spatial grid of 8-bin orientation histograms, giving $128$ dimensions.

Gradients in the $16\times 16$ patch are accumulated into the closest four spatial subregions and closest two orientation bins using trilinear interpolation. This smoothing reduces aliasing when the patch is slightly misaligned.

(Illumination normalization) Unit-length normalization, clipping at $0.2$, and renormalization provide robustness to contrast changes.

Brightness offsets are removed by gradient differencing. Contrast changes are removed by the first normalization. Nonlinear illumination (e.g., a highlight dominating one bin) is mitigated by clipping, after which the second normalization restores unit length.

Matching

(Nearest neighbor in descriptor space) Descriptors are matched by Euclidean distance; efficient search uses KD-trees or approximate NN libraries.

With 128-D descriptors and thousands of keypoints per image, exact NN is slow. Practical systems use FLANN or similar approximate nearest-neighbor structures; the approximation rarely hurts match quality.

(Lowe’s ratio test) A match is kept only if the nearest neighbor is substantially closer than the second-nearest.

If $d_1$ and $d_2$ are the distances to the nearest and second-nearest descriptors, the match is accepted iff $d_1/d_2<0.8$. The intuition: an unambiguous match has one clear winner; a wrong match has many nearly-equidistant competitors. This single test discards the majority of false matches at the cost of rejecting a small fraction of correct ones.

Successors and Variants

(SURF) Uses integral images and box filters to approximate DoG extrema at a fraction of the cost.

SURF descriptors are 64-dimensional (Haar-wavelet responses in a $4\times 4$ grid) and are much faster to compute than SIFT, with comparable matching accuracy.

(ORB) Combines FAST corners with rotation-aware BRIEF binary descriptors; ~ 100× faster than SIFT.

ORB descriptors are 256-bit binary strings matched by Hamming distance, making them ideal for real-time systems (VO, SLAM).

(SuperPoint) Jointly learns detector and descriptor in a single CNN.

Trained with self-supervised homographic adaptation. Dominates SIFT on modern benchmarks but requires GPU inference.

See Also

• Scale-Invariant Detection — the DoG extrema that underlie SIFT’s detector
• 4.3.1. MOPS — a simpler (rotation-normalized) descriptor
• 4.4. Feature Matching — the matching stage that consumes SIFT descriptors
• 4.4.1. RANSAC — the geometric filter applied to SIFT matches