Describing a Keypoint: SIFT and HOG

From 'Where' to 'What': The Job of a Descriptor

In the last two guides you learned to find keypoints — distinctive spots like corners and blobs that an algorithm can re-locate reliably from one image to the next. That answered the question where: a keypoint is a location, plus a scale, and soon an orientation. But a location alone tells you nothing about what that spot actually looks like. If I hand you the coordinates (212, 87) in one photo and ask you to find the same physical point in a second photo, you are stuck — there is no content to compare. This guide tackles the second half of the problem: turning the little patch of pixels around an image keypoint into a description of what is there.

A descriptor is the answer. It is a compact numerical signature computed from the neighborhood of a keypoint — think of it as a fingerprint for that spot. Two fingerprints from the same fingertip look almost identical even if the hand was rotated or the lighting changed; two fingerprints from different fingers look clearly different. A good image descriptor behaves the same way: the patch around the same physical point should produce nearly the same vector of numbers in both photos, while a different point should produce a noticeably different vector. The SIFT descriptor we build in this guide is the most famous example — a list of 128 numbers that summarizes a patch.

Because a descriptor is just a vector of numbers, comparing two of them is simple arithmetic: measure the distance between the vectors. If the distance is tiny, the two patches probably show the same thing; if it is large, they probably do not. The most common choice for SIFT is plain Euclidean distance — the straight-line distance in 128-dimensional space. This is exactly what powers matching: to find correspondences between two images you compute descriptors for the keypoints in each, then pair up the ones whose vectors are closest. We will build that whole matching machinery in Guide 5; for now, just hold onto the idea that describe-then-compare-by-distance is the goal everything in this guide serves.

Orientation: Making Descriptors Rotation-Invariant

Here is a problem that will sink a naive descriptor. Suppose you photograph a coffee mug, then tilt your head and photograph it again. The patch around a keypoint on the logo is now rotated. If we read off the pixels in fixed image coordinates — top-left to bottom-right — the two patches give very different numbers, and the match fails, even though it is the same logo. SIFT solves this with an elegant trick: before describing a patch, it gives the keypoint a dominant orientation, and then measures everything relative to that orientation. It is like reading a paper map: instead of always holding it north-up, you first turn the map so 'up' points the way you are facing, and then every direction on it makes sense from your point of view. Two observers facing different ways will turn the map differently, but once turned, they read the same relative layout.

To find that dominant orientation, SIFT looks at the gradients inside the patch — the same image gradients you met in Guide 1. Recall that a gradient at a pixel points in the direction of steepest brightness increase, and its length measures how strong the edge is there. For orientation we need two numbers at every pixel: the gradient magnitude (how strong) and the gradient direction (which way it points). We estimate them from simple finite differences — comparing a pixel's neighbors on either side.

Gradient magnitude m and orientation θ at each pixel, from finite differences.

Let us unpack this. I(x,y) is the brightness of the pixel at column x, row y. The term I(x+1,y) − I(x−1,y) is the horizontal change in brightness across that pixel (right neighbor minus left neighbor); call it gx. Likewise I(x,y+1) − I(x,y−1) is the vertical change, gy. The magnitude m is simply the length of the vector (gx, gy) by Pythagoras, and the orientation θ is its angle. The function atan2(gy, gx) is a careful version of arctan(gy / gx) that returns the correct angle over the full 0°–360° range and never divides by zero. Worked example: if the right neighbor is brighter than the left by gx = 10, and the bottom is brighter than the top by gy = 10, then m = √(10² + 10²) ≈ 14.1 and θ = atan2(10, 10) = 45° — a fairly strong edge running diagonally.

Now build a histogram of these directions over the region around the keypoint. SIFT uses 36 bins, each covering 10°, spanning the full circle. Every pixel in the region casts a vote into the bin matching its θ, but the vote is weighted by its magnitude m (strong edges count more than faint texture) and by a Gaussian window centered on the keypoint (pixels near the center count more than those at the edge of the region). The tallest bin — the most common, strongest gradient direction — is declared the keypoint's dominant orientation. One refinement matters: if a second bin reaches at least 80% of the peak, SIFT creates an additional keypoint at the same location and scale but with that secondary orientation. So a single spot can yield two SIFT descriptors, which improves matching when the dominant direction is ambiguous.

Building the SIFT Descriptor

We now have an oriented patch: a square window centered on the keypoint, sized in proportion to the keypoint's scale (a keypoint detected coarsely in scale space gets a bigger window than a fine one) and rotated so its dominant orientation points up. From this single canonical patch we build the SIFT descriptor, a vector of 128 numbers. The recipe is a grid of small gradient histograms — the same gradient idea as orientation assignment, but now we keep coarse spatial information about where in the patch each gradient lives.

1. Take the oriented, scale-sized patch around the keypoint and divide it into a regular 4×4 grid of square cells (16 cells in total).
2. At every pixel compute the gradient magnitude m and orientation θ, exactly as in Section 2, and rotate each orientation by subtracting the keypoint's dominant angle so the description is rotation-relative.
3. Within each of the 16 cells, accumulate an 8-bin histogram of gradient orientations (each bin spans 45°), adding each pixel's magnitude — weighted by the Gaussian window — into the matching bin.
4. Concatenate all 16 cells' 8-bin histograms into one long vector, then normalize it (next equation) to tame illumination.

Two supporting tricks keep this robust. First, a Gaussian weighting window over the whole patch down-weights pixels far from the center; those outer pixels are the most likely to drift in or out of the patch under a small viewpoint change, so trusting them less makes the descriptor steadier. Second, and more subtle, is trilinear interpolation. A pixel sitting right on the boundary between two cells, or with a direction right between two orientation bins, should not be dumped entirely into one bin — a tiny shift of the patch would then flip its whole vote to the neighbor and the descriptor would jump. Instead each gradient is spread softly across the neighboring bins in all three dimensions — the two spatial axes (which cell) and the orientation axis (which angle bin) — in proportion to how close it is to each. This smearing removes hard boundary jumps and is a big part of why SIFT is stable to small shifts.

The 128-dimensional SIFT vector.

Count it explicitly: 4×4 = 16 spatial cells, each contributing an 8-value orientation histogram, gives 16×8 = 128 numbers — the canonical SIFT length. The choice of 4×4×8 is a deliberate compromise. More spatial cells (say 8×8) would pin down where each gradient sits more precisely, but make the descriptor brittle: a small misalignment of the patch would scramble which cell each gradient falls in. Fewer cells (say 2×2) would be very tolerant of shifts but throw away so much layout that distinct patches start to look alike. The 4×4 grid with 8 directions sits at the sweet spot: enough spatial structure to be distinctive, enough pooling to forgive the small shifts that survive imperfect detection.

Two-stage normalization for illumination robustness.

Finally, normalize. v is the 128-vector and ‖v‖ is its Euclidean length. Dividing by that length (v ← v/‖v‖) makes the vector unit-length, which cancels any overall scaling of contrast: brighten the whole patch and every gradient grows by the same factor, but after rescaling to length 1 the descriptor is unchanged. That handles linear lighting changes. But strong directional light, or a camera that saturates (clips to pure white), can pump up a few gradients enormously. So we clip every component to at most 0.2 (v_i ← min(v_i, 0.2)), capping the influence of any single huge gradient, and then renormalize to unit length again. The result is a descriptor that barely flinches at brightness, contrast, and saturation changes — exactly the illumination invariance we listed as a goal in Section 1.

# Build a 128-D SIFT descriptor from one oriented keypoint patch
def sift_descriptor(patch, dominant_angle):
    # patch: square image window, already sized by the keypoint's scale
    gx, gy = finite_differences(patch)               # per-pixel gradients
    mag    = sqrt(gx**2 + gy**2)                      # magnitude  m(x,y)
    ang    = (atan2(gy, gx) - dominant_angle) % 360  # rotation-relative orientation
    w      = gaussian_window(patch.shape)            # down-weight far pixels

    hist = zeros((4, 4, 8))                           # 4x4 cells, 8 orientation bins
    for (x, y) in patch.pixels():
        cell_x, cell_y = cell_index(x, y)            # which of the 4x4 cells
        bin            = ang[y, x] / 45.0            # which of the 8 bins (45 deg each)
        vote           = mag[y, x] * w[y, x]         # magnitude, Gaussian-weighted
        # trilinear interpolation: split 'vote' softly across the neighboring
        # (cell_x, cell_y, orientation) bins in proportion to distance
        add_trilinear(hist, cell_x, cell_y, bin, vote)

    v = hist.flatten()                               # length 16 * 8 = 128
    v = v / norm(v)                                  # unit length
    v = minimum(v, 0.2)                              # clip large components
    v = v / norm(v)                                  # renormalize
    return v                                          # the SIFT descriptor

HOG: Describing Whole Regions, Not Just Keypoints

The histogram of oriented gradients (HOG) is SIFT's close sibling, born from the same insight but used very differently. Where SIFT computes a descriptor only at a handful of sparse, scale-selected keypoints, HOG is applied densely: it lays a fixed grid over an entire region — a whole detection window — and describes all of it. This made HOG the workhorse feature for object detection in the late 2000s, most famously for pedestrian detection: slide a window across the image, compute its HOG vector, and let a classifier decide 'person / not person'.

1. Compute the gradient magnitude and orientation at every pixel of the window — the same finite differences as before.
2. Pool orientations into a histogram over each small cell of a regular grid (e.g. 8×8-pixel cells), typically using 9 bins spread over 0°–180° (unsigned gradients, so opposite directions share a bin).
3. Group neighboring cells into larger overlapping blocks (e.g. 2×2 cells), and normalize the combined histogram within each block for contrast robustness.
4. Slide the block one cell at a time so each cell is normalized several times under different neighbors, then concatenate all block vectors into one long descriptor for the whole window.

L2 block normalization with a stabilizing constant ε.

Here v is the stacked histogram of all cells inside one block, ‖v‖ its Euclidean length, and ε a small positive constant. Dividing by √(‖v‖² + ε²) rescales the block to roughly unit length, which removes the effect of local contrast — a brightly lit patch and a dim one with the same pattern of edges normalize to nearly the same vector. The ε is there for safety: in a flat, textureless region all gradients are near zero, so ‖v‖ ≈ 0 and a plain division would blow up or divide by zero; adding ε² inside the square root keeps the result finite and gently sends near-empty blocks toward zero instead of amplifying their noise. The crucial design choice is that blocks overlap: because each cell is normalized several times against different sets of neighbors, the descriptor copes well with shadows and uneven lighting that change contrast across the window.

It is worth stating the contrast bluntly. SIFT describes points; HOG describes regions. SIFT picks a few scale-selected, rotation-aligned keypoints and produces one descriptor each, tuned for matching the same physical point across images. HOG ignores keypoints entirely, tiles a whole window on a fixed grid with no per-feature rotation, and produces one big descriptor for the window, tuned for classifying its contents. SIFT's invariances (scale, rotation) are what you want when the same object appears at different sizes and angles; HOG's fixed geometry is fine — even helpful — when you have normalized your detection windows to a standard size and upright pose, because the rigid layout itself becomes a discriminative cue (a pedestrian's head-over-torso-over-legs structure).

Why Histograms of Gradients Work So Well

Take a step back. SIFT and HOG differ in where they are applied, but their robustness comes from the same three ideas, repeated. Understanding these principles matters more than memorizing either pipeline — almost every classical descriptor, and even the early layers of convolutional networks, are variations on the same theme.

One: use gradients, not raw intensities. A gradient measures the difference between neighboring pixels, so it throws away the absolute brightness level and keeps only how the brightness is changing. Add a constant to every pixel — turn up the room lights — and every gradient is unchanged. That single choice buys most of the illumination tolerance for free, before any normalization, because edges and texture survive lighting changes that wash out raw pixel values.

Two: pool into histograms. Inside a cell we do not record which exact pixel had a given gradient direction — we just tally how much gradient energy points each way. This deliberate forgetting of precise position is what tolerates small deformations: if the patch shifts a pixel or two, or the surface bends slightly, the individual gradients move around inside the cell but the histogram of the cell barely changes. Pooling trades a little spatial precision for a lot of robustness to the small geometric wobbles that real cameras and real scenes always introduce.

Three: normalize. Dividing a descriptor (or block) by its own length removes the overall contrast factor, so a faint, low-contrast view of a pattern and a bold, high-contrast view of the same pattern land at almost the same vector. The optional clipping in SIFT goes one step further, capping freak values from saturation. Between them, gradients handle additive brightness, normalization handles multiplicative contrast, and the descriptor ends up reading the shape of the local structure rather than its photometric accident.

Strengths, Costs, and When to Reach for SIFT

Time for an honest balance sheet. The strengths are real and were genuinely transformative: SIFT and HOG produce descriptors that are highly distinctive and robust to rotation, illumination, and modest viewpoint change, which made reliable wide-baseline matching, panorama stitching, and pedestrian detection practical for the first time. For many matching and recognition tasks they were the state of the art for over a decade, and they remain a strong, learning-free baseline today.

The cost is speed and size. A SIFT descriptor is a 128-dimensional floating-point vector, and computing it — gradients, orientation, weighted histograms, trilinear interpolation, two normalizations — is not cheap, repeated over hundreds or thousands of keypoints per image. Matching is worse: comparing two images means measuring Euclidean distance across all 128 dimensions for every candidate pair of keypoints, so the work grows with the product of the two keypoint counts. On a 30-frames-per-second video stream, or a phone with a modest CPU and a battery to protect, that bill comes due fast.

A note on licensing, stated carefully: SIFT was patented, which for years pushed many open-source projects toward alternatives. That patent has since expired, so SIFT is now free to use (for example, it lives in the main OpenCV module again). HOG was never encumbered in the same way. So today the reason to prefer a faster descriptor is performance, not licensing — which is exactly the motivation for the next guide.