Distinctive Image Features from Scale-Invariant Keypoints

Before SIFT, recognizing an object across different images was a patchwork of brittle tricks. Change the camera distance and a template shrinks or grows. Rotate the camera and edges rearrange. Change the lighting and intensities shift.

The core challenge: find the same physical point in two images and describe it so that the description survives scale changes, rotation, and illumination shifts — all without any learning or training data. The description must be local (so partial occlusion doesn't destroy it) and distinctive (so each point's description differs from every other).

Objects exist at a particular scale: a sugar cube on a table is clearly visible, but from an airplane the cube vanishes. To detect features at every possible scale, SIFT constructs a scale space — a stack of progressively blurred copies of the image.

Each blur level uses a Gaussian kernel with a larger standard deviation $\sigma$. The image is organized into octaves: each octave halves the image resolution, and within each octave the blur increases by a constant factor $k$. This means a feature that appears small in one octave may appear large in another — SIFT checks them all.

Next, SIFT approximates the Laplacian of Gaussian (LoG) — a blob detector — with a cheaper operation: the Difference of Gaussians (DoG). Each DoG image is simply one blur level minus the next. The result highlights regions where intensity changes abruptly — exactly the places that make good keypoints.

The raw extrema from Stage 1 are approximate — they sit on the discrete pixel grid. SIFT refines each candidate using a Taylor expansion of the DoG function, fitting a 3D quadratic to find the sub-pixel, sub-scale true extremum. Think of it as focusing a microscope: the pixel grid gives a blurry location, the Taylor fit sharpens it.

Two filters then discard bad candidates:

• Low-contrast filter: if the DoG value at the refined extremum is below a threshold (|D| < 0.03), the point is too faint to be reliable — discard it.

• Edge filter: a point along an edge (like a wall) is poorly localized in one direction. SIFT checks the ratio of the principal curvatures (eigenvalues of the Hessian). If the ratio exceeds a threshold (typically 10), the point is edge-like — discard it.

To achieve rotation invariance, SIFT measures the dominant gradient direction around each keypoint. It builds an orientation histogram with 36 bins (each covering 10°), weighted by gradient magnitude and a Gaussian window centered on the keypoint.

The bin with the highest peak becomes the keypoint's canonical orientation. Any bin within 80% of the peak spawns an additional keypoint at the same location with that orientation — so a corner viewed from two angles can generate two entries. From this point on, all measurements are made relative to this orientation, which is why rotating the image does not change the final descriptor.

Now each keypoint has a location, a scale, and an orientation. The final step is to describe what the neighborhood looks like in a way that is compact, distinctive, and invariant.

SIFT takes a 16×16 pixel patch around the keypoint (aligned to the canonical orientation and scaled appropriately), divides it into a 4×4 grid of sub-regions (each 4×4 pixels), and in each sub-region computes a histogram of 8 gradient orientations. Stacking 4×4×8 = 128 values into a single vector produces the SIFT descriptor.

The descriptor is then normalized to unit length for illumination invariance: if all pixel intensities double, gradients double, but after normalization the vector is unchanged. A clipping step (capping values at 0.2 and re-normalizing) further reduces the effect of large gradients from non-linear illumination changes.

Given two images, SIFT extracts keypoints from each, then matches descriptors using nearest-neighbor search in the 128-D space. But a raw nearest neighbor is often wrong — a descriptor might simply match the closest one available, even if the true match is absent.

Lowe's elegant solution is the ratio test: compute the distance to the closest and second-closest neighbors. If the ratio $d_1/d_2 < 0.8$, the match is accepted; otherwise, it's rejected as ambiguous. This single test eliminates ~90% of false matches while keeping ~95% of correct ones.

Let's now walk through all four stages together. From a raw image, SIFT produces a set of keypoints, each with a location (x, y), a scale (σ), an orientation (θ), and a 128-D descriptor — a complete "ID card" for that spot in the image. Two images of the same scene may produce hundreds of these ID cards, and matching them reveals which points are the same physical location.

SIFT's design principles — build a scale space, detect stable extrema, describe with local gradients, match with a ratio test — became the blueprint for a generation of feature methods. Even deep-learned features like SuperPoint and SuperGlue use SIFT-era evaluation protocols and often compare against SIFT as a baseline.