Feature Descriptors

A feature descriptor is a vector computed from the image around a keypoint, designed so that the same physical point seen in two images produces two nearby vectors, while different points produce distant ones. Feature detection decides where to look; the descriptor decides what the point looks like, in a form that can be compared with a distance. Descriptors make feature matching possible across viewpoints, times, and cameras. They are also called local descriptors or local feature descriptors.

Definition

A local feature descriptor is a function that maps an image and a keypoint (a location, usually with a scale and an orientation) to a fixed-length vector, real-valued or binary, that summarizes the appearance of the keypoint’s neighborhood. Its aim is to be invariant (or at least robust) to the changes expected between images, such as rotation, scale, viewpoint, illumination, and noise, while remaining distinctive, so that the correct match can be picked out among many candidates.

Intuition

To recognize a spot on a building facade in a second photo, comparing the single pixel is useless: thousands of pixels share its color. A small patch around it is far more informative, but a patch copied pixel by pixel changes as soon as the camera rotates, moves closer, or the sun goes behind a cloud.

A good descriptor keeps the information that survives those changes and throws away the rest. Gradient directions survive a change of brightness; their arrangement relative to the strongest local direction survives a rotation; coarse spatial pooling survives small misalignments. Every ignored change, however, is information that could have told two points apart.

Formal Definition

Let $I$ be an image and $k = (\mathbf{x}, \sigma, \theta)$ a keypoint with position, scale, and orientation. A descriptor is a function

$$f(I, k) \in \mathbb{R}^D \quad \text{or} \quad f(I, k) \in \{0, 1\}^D ,$$

usually computed on a patch resampled in the keypoint’s own frame, so that position, scale, and orientation are factored out before anything is measured. Descriptors are compared with a distance $d$. Real-valued descriptors use the Euclidean distance

$$d(\mathbf{a}, \mathbf{b}) = \lVert \mathbf{a} - \mathbf{b} \rVert_2 ,$$

and binary descriptors use the Hamming distance, the number of differing bits,

$$d_H(\mathbf{a}, \mathbf{b}) = \sum_{i=1}^{D} a_i \oplus b_i ,$$

which a processor computes with an XOR followed by a population count. The ideal descriptor satisfies $d(f(I, k), f(I', k')) \ll d(f(I, k), f(I', k''))$ whenever $k'$ in image $I'$ shows the same scene point as $k$ and $k''$ shows a different one.

Properties

Invariance against distinctiveness. Each invariance removes information. A descriptor that ignores rotation cannot distinguish a “6” from a “9”, and one that pools over a large neighborhood blurs together structures that a finer grid would separate. A tracker between consecutive video frames needs almost no invariance; wide-baseline matching needs a great deal.

Invariance by normalization. Descriptors usually do not achieve invariance through the measurements themselves but through a canonical frame supplied by the detector. Sampling the patch at the keypoint’s scale gives scale invariance, and rotating it to the keypoint’s dominant orientation gives rotation invariance. This makes the descriptor only as reliable as the detector’s scale and orientation estimates.

Illumination normalization. An affine intensity change $I' = aI + b$ is removed by subtracting the mean and dividing by the norm (for raw intensities) or, for gradients, which already ignore $b$, by normalizing the vector to unit length. Lowe’s SIFT descriptor additionally clips large entries and renormalizes, to reduce the influence of non-linear effects such as saturation.

Dimensionality. Longer descriptors can be more distinctive, but they cost memory and make nearest-neighbor search harder. Typical sizes range from 32 bytes (a 256-bit binary string) to 128 or 256 floating-point numbers.

Families of Descriptors

Raw patches and normalized cross-correlation

The simplest descriptor is the patch itself, flattened into a vector. Subtracting the mean and dividing by the norm turns the Euclidean distance into a function of normalized cross-correlation (NCC), which removes affine changes of intensity. Patches work when the images differ only slightly, as in stereo and video tracking, but a small rotation or scale error moves every sample. In Mikolajczyk and Schmid’s comparison, cross-correlation gave unstable results and was more sensitive to detector errors than the other high-dimensional descriptors.

Gradient-histogram descriptors

SIFT, introduced by Lowe, divides the oriented patch into a $4 \times 4$ grid of cells and builds an 8-bin histogram of gradient orientations in each, weighted by gradient magnitude and a Gaussian window, giving 128 numbers. Pooling gradients into cells lets them shift by a few pixels without changing the descriptor much, which tolerates small viewpoint changes and localization errors far better than raw patches. Histograms of oriented gradients (HOG) apply the same idea densely over a detection window. Mikolajczyk and Schmid proposed GLOH (gradient location and orientation histogram), which replaces SIFT’s square grid with a log-polar grid of 17 location bins and 16 orientation bins, and reduces the resulting 272 dimensions to 128 with principal component analysis.

SURF

SURF (Speeded-Up Robust Features), by Bay, Tuytelaars, and Van Gool, reorganized SIFT-like computations for speed. Its detector uses a Hessian-based measure and its descriptor uses Haar wavelet responses in $x$ and $y$; both are evaluated with box filters on an integral image, which gives the sum over any rectangle in constant time. Each of $4 \times 4$ subregions contributes the sums of the responses and of their absolute values, $(\sum d_x, \sum d_y, \sum |d_x|, \sum |d_y|)$, giving a 64-dimensional vector normalized to unit length.

Binary descriptors

BRIEF, by Calonder et al. (2010), skips gradients entirely. After smoothing the patch, it compares the intensities at $n_d$ fixed pairs of points $(\mathbf{p}_i, \mathbf{q}_i)$ and records one bit per test,

$$b_i = \begin{cases} 1 & I(\mathbf{p}_i) < I(\mathbf{q}_i) \\ 0 & \text{otherwise.} \end{cases}$$

The authors reported that 256 or even 128 bits often suffice for good matching, and the Hamming distance makes comparison far cheaper than the Euclidean distance between floating-point vectors. BRIEF has no orientation normalization, so it is not rotation invariant. ORB (Rublee et al., 2011) addresses this: it assigns each FAST keypoint an orientation from the intensity centroid of its patch, rotates the BRIEF tests accordingly, and selects a set of 256 tests that have high variance and low correlation once steered. The authors reported ORB to be about two orders of magnitude faster than SIFT while performing as well in many of their experiments. BRISK (Leutenegger et al., 2011) and FREAK (Alahi et al., 2012) replace BRIEF’s random pairs with fixed sampling patterns of concentric rings, FREAK’s retina-inspired and denser near the center, from which they also estimate orientation. Binary descriptors are the usual choice on mobile and embedded systems and in real-time SLAM, at some cost in robustness to large viewpoint and illumination changes.

Learned descriptors

Learned descriptors replace the hand-designed function with a neural network trained so that matching patches are close and non-matching ones are far apart. HardNet (Mishchuk et al., 2017) is representative of patch-based networks: it trains the L2-Net architecture with a loss modeled on Lowe’s matching criterion, pushing each matching pair closer than the nearest non-matching patch in the batch, and outputs a 128-dimensional descriptor, the size of SIFT’s. SuperPoint (DeTone et al., 2018) instead runs a fully convolutional network on the whole image and outputs keypoints and a dense field of 256-dimensional descriptors in one pass. Learned descriptors are now common in structure from motion and localization pipelines, often paired with learned matchers, which are covered in feature matching.

Evaluation

Mikolajczyk and Schmid (2005) compared ten descriptors, including SIFT, GLOH, shape context, PCA-SIFT, steerable filters, and cross-correlation, on real images with known geometric and photometric transformations, scoring them by recall against precision. In most of their tests GLOH obtained the best results, closely followed by SIFT; the ranking was largely the same across interest region detectors, and gradient moments and steerable filters were the best low-dimensional descriptors.

HPatches (Balntas et al., 2017) was built because earlier datasets left evaluation details unspecified and had become nearly saturated. It provides patches extracted from 116 image sequences, 57 with photometric changes and 59 with viewpoint changes, and defines strict protocols for patch verification, image matching, and patch retrieval. Its authors reported that a simple normalization of hand-crafted descriptors could raise their performance to the level of the learned descriptors they tested.

Matching Descriptors

Descriptors are matched by exact or approximate nearest-neighbor search, usually filtered with Lowe’s ratio test, which accepts a match only if the nearest neighbor is clearly closer than the second-nearest, and then verified geometrically with RANSAC; both are covered in feature matching.

Examples

The example compares four descriptors of the same keypoint under three changes: a contrast and brightness change, a 30° rotation about the keypoint, and additive noise. The raw patch is compared directly; the NCC patch is mean-subtracted and normalized; the two gradient-histogram descriptors are simplified SIFT-like $4 \times 4 \times 8$ grids, one computed in the image’s fixed frame and one rotated to the dominant gradient orientation found with a 36-bin histogram. Each distance is divided by the median distance from the original descriptor to the descriptors of about 200 other keypoints in the same image, so values well below 1 mean the point would still be recognized.

import numpy as np
from scipy import ndimage

rng = np.random.default_rng(1)
# Smooth random texture standing in for an image; intensities in [0, 1].
image = ndimage.gaussian_filter(rng.random((201, 201)), 3.0)
image = (image - image.min()) / (image.max() - image.min())
center, radius = (100, 100), 16

def region(img, c=center, r=radius):
    """Pixel offsets (dy, dx) and values inside a disk around c."""
    dy, dx = np.mgrid[-r:r + 1, -r:r + 1]
    inside = dy**2 + dx**2 <= r**2
    return dy[inside], dx[inside], img[c[0] - r:c[0] + r + 1, c[1] - r:c[1] + r + 1][inside]

def raw_patch(img, c=center):
    return region(img, c)[2]

def ncc_patch(img, c=center):
    v = raw_patch(img, c)
    v = v - v.mean()
    return v / np.linalg.norm(v)

def grad_hist(img, c=center, rotate=True, grid=4, bins=8):
    """SIFT-like grid of gradient-orientation histograms (simplified)."""
    smooth = ndimage.gaussian_filter(img, 1.0)
    gy, gx = np.gradient(smooth)
    mag, ang = np.hypot(gx, gy), np.arctan2(gy, gx)
    dy, dx, m = region(mag, c)
    a = region(ang, c)[2]
    w = m * np.exp(-(dx**2 + dy**2) / (2 * (radius / 2) ** 2))  # Gaussian window
    theta = 0.0
    if rotate:  # dominant orientation from a 36-bin histogram
        h, _ = np.histogram(a, bins=36, range=(-np.pi, np.pi), weights=w)
        h = ndimage.uniform_filter1d(h, 3, mode="wrap")  # smooth circularly
        k = np.argmax(h)
        l, r = h[k - 1], h[(k + 1) % 36]
        offset = 0.5 * (l - r) / (l - 2 * h[k] + r)  # parabolic peak interpolation
        theta = -np.pi + (k + 0.5 + offset) * 2 * np.pi / 36
    # Express positions and orientations in the keypoint's rotated frame.
    cos, sin = np.cos(theta), np.sin(theta)
    u, v = cos * dx + sin * dy, -sin * dx + cos * dy
    rel = np.mod(a - theta, 2 * np.pi)
    iu = np.clip(((u + radius) / (2 * radius + 1) * grid).astype(int), 0, grid - 1)
    iv = np.clip(((v + radius) / (2 * radius + 1) * grid).astype(int), 0, grid - 1)
    io = np.minimum((rel / (2 * np.pi) * bins).astype(int), bins - 1)
    d = np.zeros((grid, grid, bins))
    np.add.at(d, (iv, iu, io), w)
    d = d.ravel() / np.linalg.norm(d)
    d = np.minimum(d, 0.2)  # clip large values, as SIFT does
    return d / np.linalg.norm(d)

versions = {  # transformed copies of the image, keypoint still at the center
    "bright": 1.5 * image + 0.2,  # contrast and brightness change
    "rotate": ndimage.rotate(image, 30, reshape=False, order=3, mode="reflect"),
    "noise": image + rng.normal(0, 0.02, image.shape),
}
descriptors = {
    "raw patch": raw_patch,
    "NCC patch": ncc_patch,
    "grad hist, fixed frame": lambda im, c=center: grad_hist(im, c, rotate=False),
    "grad hist, rotated": grad_hist,
}

# Scale of comparison: median distance to other keypoints in the same image.
others = [tuple(p) for p in rng.integers(30, 171, size=(200, 2))
          if np.hypot(*(p - np.array(center))) > 2 * radius]

print(f"{'descriptor':<24}{'dim':>5}" + "".join(f"{k:>9}" for k in versions))
for name, f in descriptors.items():
    ref = f(image)
    typical = np.median([np.linalg.norm(f(image, p) - ref) for p in others])
    row = [np.linalg.norm(f(im) - ref) / typical for im in versions.values()]
    print(f"{name:<24}{ref.size:>5}" + "".join(f"{x:>9.2f}" for x in row))

Output:

descriptor                dim   bright   rotate    noise
raw patch                 797     2.72     0.71     0.12
NCC patch                 797     0.00     0.83     0.13
grad hist, fixed frame    128     0.00     0.84     0.15
grad hist, rotated        128     0.00     0.17     0.23

The raw patch is more than twice as far from its brightened self as from a typical unrelated point, while NCC and the normalized gradient histograms remove the change exactly. None of the first three survives the rotation. Rotating the histogram grid to the dominant orientation brings the rotated copy close again, with about a sixth of the patch’s dimensions. The price is visible in the last column: noise perturbs the estimated orientation, so the rotation-normalized descriptor moves more under noise than the others. Invariance is never free.

Common Misconceptions

• “A descriptor is invariant by itself.” Most descriptors rely on the detector’s scale and orientation; with a wrong orientation, a rotation-normalized descriptor is computed in the wrong frame and fails.
• “More invariance is always better.” Unneeded invariance costs distinctiveness and adds failure modes. Upright descriptors that skip orientation assignment, such as U-SURF or BRIEF itself, avoid orientation errors and can be preferable when the camera does not rotate about its optical axis.
• “Descriptor distance measures similarity on an absolute scale.” Some descriptors are much more distinctive than others, so distances are meaningful mainly relative to other candidates, which is why the ratio test outperforms a fixed threshold.
• “Learned descriptors have made hand-crafted ones obsolete.” The HPatches authors found that properly normalized hand-crafted descriptors could match the learned ones they evaluated, and SIFT and ORB remain widely used where speed or the lack of suitable training data matters.

Where It Is Used

• Feature matching across viewpoints for relative pose, panorama stitching, and the estimation of homographies and epipolar geometry.
• Structure from motion and visual localization, which match descriptors across many images or against a 3D map.
• SLAM and visual odometry, often with binary descriptors such as ORB for speed, complementing frame-to-frame feature tracking.
• Object recognition and image retrieval, from Lowe’s SIFT recognition system to bag-of-visual-words retrieval, which quantizes descriptors into visual words.
• Image registration in medical, aerial, and satellite imagery.