SIFT descriptor step by step, interactive demo

What a descriptor should do

Detection gives each keypoint a position and a scale, for example from the Difference of Gaussians. The descriptor extracts a vector from the patch around it that is robust: it stays nearly the same when the patch is seen again under a different viewpoint or light, and distinctive: different patches give different vectors. It should also be compact and fast to compute and compare. Most descriptors are templates, histograms, or combinations of both, and most use edge and gradient information, which captures texture; color is rarely used. SIFT is a set of local histograms of oriented gradients.

The steps

Gradients. The gradient magnitude and orientation are computed on the Gaussian image $L$ closest to the keypoint's scale: $m = \sqrt{L_x^2 + L_y^2}$ , $\phi = \operatorname{atan2}(L_y, L_x)$ .
Orientation estimation. A histogram of 36 bins of 10° collects the orientations within a radius of $3 \cdot 1.5\sigma$ , each weighted by its magnitude and a Gaussian of $1.5\sigma$ . The highest peak gives the dominant orientation $\theta$ , refined with a parabola through three bins. Every other peak of at least 80% of the highest creates an extra keypoint with its own orientation.
Normalize the orientation. The patch is rotated so that $\theta$ points along the x axis: a grid of 16 × 16 samples is laid out in the keypoint's frame, rotated by $\theta$ , with a spacing proportional to $\sigma$ . Every orientation is measured relative to $\theta$ .
Histograms. The grid is divided into 4 × 4 subregions of 4 × 4 samples. Each subregion gets a histogram of 8 orientations, 45° each. Each sample votes with its gradient magnitude, weighted by a Gaussian over the window, so gradients near the center count more. Votes are split between neighboring subregions and bins, so a small shift or rotation changes the histograms gradually.
Vector. The 4 × 4 × 8 = 128 values are lined up into one vector.

Illumination

Two steps make the descriptor robust to changes of brightness $I + b$ and contrast $\alpha I$ :

It works in gradient space, where the offset $b$ disappears.
The vector is normalized to unit length (L2), which removes the factor $\alpha$ .

Non-linear illumination effects, such as saturation or specular highlights, can make a few gradients very large, and those would then dominate the whole descriptor. So all values above 0.2 are clamped to 0.2, and the vector is normalized again. The descriptor then depends less on the exact magnitudes and more on the distribution of orientations.

In practice

The same keypoint in the transformed image is described at the mapped position and scale, which is known here, so only the descriptor is tested and not the detector. Efficient implementations compute the oriented histograms with steerable filters, filters whose orientation can be set to that of each histogram bin. SURF is a fast approximation of the same idea with box filters on integral images, about six times faster at similar quality. How the vectors are compared is the topic of matching and the ratio test.

Try this

Rotate the image by 90°: the arrows in the gradient view turn with it, the orientation histogram shifts by 9 bins, and the descriptor stays almost the same.
Rotate by 30° and turn off the orientation assignment: without the normalization, the histograms of the cells no longer line up, and the distance grows several times.
Scale the image by 1.5: the window grows with the keypoint's scale, and the descriptor still fits, as long as the window stays inside the image.
Change contrast and brightness moderately: the distance stays at 0. Raise the contrast to 2: bright regions clip at white, their gradients vanish, and the distance jumps.
Set γ to 0.5 or 2: a non-linear change alters the relative gradient magnitudes, and unlike an affine change it is not undone by the normalization. The distance grows to about 0.1 to 0.2: much less than without orientation assignment or with clipping.
Pick a keypoint on the checkerboard of the shapes image or on the picket fence of the landscape: its orientation histogram often has more than one peak above 80%, so it gets several descriptors.