HOG, HOF and MBH: Descriptors Before Deep Learning

Between 2005 and 2012, if you wanted to find people in images or recognise what someone was doing in a video, you did not train a network. You computed a histogram of gradient directions, fed it to a linear SVM, and it worked well enough to ship.

Understanding these descriptors is not nostalgia. They are still the fastest thing that works on a CPU with no GPU and no training data, they still beat deep learning on tiny datasets, and — most usefully — a convolutional network’s early layers learn something remarkably close to them. Knowing HOG makes CNNs less mysterious.

Prerequisites: edge detection for gradients, and optical flow for the motion sections.

The problem that made HOG

In 2005 Navneet Dalal and Bill Triggs were trying to find pedestrians in street photographs. The difficulty was not that people are hard to see. It was that no two pedestrians produce similar pixel values.

Consider what varies: clothing colour, skin tone, whether they are backlit or in shade, whether the camera exposed for the sky or the pavement. A template of raw pixels matches nothing.

But now consider what stays constant. Whoever they are, wherever they stand, a standing person has:

• a roughly vertical edge down each side of the torso
• a horizontal-ish edge at the shoulders
• vertical edges down the legs
• a small round region at the top

The shape, expressed as a pattern of edge orientations, is stable even when every pixel value has changed. That observation is HOG.

Building HOG by hand

Let us compute one, on real numbers, all the way to the end.

flowchart TD
  A["Input window<br/>64 × 128 pixels"] --> B["Gradients gx, gy<br/>per pixel"]
  B --> C["Magnitude and angle<br/>per pixel"]
  C --> D["Divide into 8×8 cells<br/>→ 8 × 16 = 128 cells"]
  D --> E["9-bin orientation histogram<br/>per cell, magnitude-weighted"]
  E --> F["Group into 2×2 blocks<br/>sliding by 1 cell<br/>→ 7 × 15 = 105 blocks"]
  F --> G["L2 normalise each<br/>36-value block"]
  G --> H["Concatenate<br/>105 × 36 = 3780"]
  style G fill:#fee,stroke:#c00

Step 1: gradients

For each pixel, take the difference of its neighbours. This is the simplest possible derivative filter — [-1, 0, 1] — and Dalal and Triggs found it beat anything more elaborate, including Sobel with smoothing.

gx(u,v) = I(u+1, v) - I(u-1, v)
gy(u,v) = I(u, v+1) - I(u, v-1)

Here is a real 4×4 patch from the edge of a torso, with the gradients computed for the two interior columns:

Step 2: magnitude and angle

magnitude = sqrt(gx² + gy²)
angle     = atan2(gy, gx)

Take the pixel at row 1, column 1 with gx = 147, gy = 1:

mag   = sqrt(147² + 1²) = sqrt(21610) = 147.0
angle = atan2(1, 147)   = 0.39°

A strong gradient pointing almost exactly horizontally — this is the vertical edge at the side of the torso. (A gradient perpendicular to an edge means the edge itself is vertical.)

Now the pixel at row 0, column 2 with gx = -3, gy = 144:

mag   = sqrt(9 + 20736) = 144.0
angle = atan2(144, -3)  = 91.2°  → unsigned: 91.2°

Equally strong, pointing vertically. That is the horizontal edge at the shoulder.

Step 3: the cell histogram

Divide the window into 8×8 pixel cells. Each cell contains 64 pixels, each contributing its magnitude to a 9-bin histogram over 0–180°, so each bin covers 20°.

The contribution is weighted by magnitude and split between neighbouring bins. A pixel at 85° with magnitude 100 does not dump all 100 into one bin. Bin centres are at 10, 30, 50, 70, 90, 110, 130, 150, 170. The angle 85 sits between centres 70 and 90:

distance to 70 = 15,  distance to 90 = 5,  bin width = 20
share to bin at 90 = (20 - 5) / 20  = 0.75  → 75
share to bin at 70 = (20 - 15) / 20 = 0.25  → 25

Without splitting, a gradient drifting from 79° to 81° would move its entire weight from one bin to another and the descriptor would change discontinuously. With splitting the change is smooth. This is a small implementation detail with a large effect on stability.

Here is a complete cell histogram from a cell on the vertical torso edge:

Compare a cell from the shoulder:

Step 4: block normalisation, the step that matters

Cells are grouped into 2×2 blocks, and each block’s 4 × 9 = 36 values are normalised together:

v_normalised = v / sqrt(||v||² + ε²)

Why this is the important step: gradient magnitudes scale directly with contrast. Move a person from bright sun into shade and every magnitude in the window drops by a factor of four. The ratios between bins stay the same. Normalisation keeps the ratios and discards the scale.

Watch it work:

Blocks overlap — they slide by one cell, not two. So every interior cell appears in four different blocks and is normalised four different ways, each relative to a different set of neighbours. That redundancy costs descriptor length and buys robustness, because a cell that gets an unlucky normalisation in one block gets a sensible one in another.

Step 5: the arithmetic

Now the number everyone quotes, derived rather than recited.

3780 numbers per window. Those go into a linear SVM, which learns one weight per number. Detection means sliding this window across the image at multiple scales and evaluating a dot product at each position.

HOG’s limits, honestly

The last three are what deep learning fixed, and it is worth being precise about how. A CNN is not better at describing edges — its first layer learns oriented edge filters that look strikingly like HOG bins. It is better because it stacks many such layers, so later layers describe parts and arrangements of parts rather than one rigid grid, and because it learns which combinations matter from data rather than being told.

Adding motion: HOF

HOG describes shape. Video needs motion, and the change required is smaller than you might expect.

Each pixel has a flow vector (u, v) from optical flow. Then:

magnitude = sqrt(u² + v²)
angle     = atan2(v, u)

That is identical in form to the gradient case. The only genuine differences are:

Flow angles are signed. Moving left and moving right are different actions, so you use the full 0–360° range rather than folding to 180°.

There is an extra bin. Typically B = 4 directional bins covering 90° each, plus one bin for “no significant motion”. Pixels whose flow magnitude falls below a threshold go into that bin. This matters because background pixels have near-zero flow with essentially random direction, and without a no-motion bin that random direction pollutes the real bins.

Take a walking person, with these flow vectors sampled from a cell:

The two background rows show the no-motion bin earning its place. Their angles are 21.8° and −71.6°, which are meaningless — they come from rounding noise in the flow estimate. Without the threshold those would vote into real bins as if they were genuine motion.

Cancelling the camera: MBH

HOF has one bad failure mode. If the camera pans, every pixel gets flow in the pan direction — including the static background. A handheld camera makes the whole HOF histogram spike in one direction, and the action is buried.

The reasoning is one line of calculus. If the camera adds a constant (c₁, c₂) to every flow vector, the flow becomes (u + c₁, v + c₂). Differentiate with respect to position:

∂(u + c₁)/∂x = ∂u/∂x + 0 = ∂u/∂x

The constant differentiates away. MBH computes ∂u/∂x, ∂u/∂y, ∂v/∂x, ∂v/∂y and builds HOG-style histograms over those, giving two descriptors: MBHx from the u-field and MBHy from the v-field.

Concretely, a row of flow u-values across a walking person against a background, first with a static camera and then with the camera panning right at 4 px/frame:

The flow values differ by 4 everywhere. The derivatives are identical. That is MBH, and it is why it was the strongest single descriptor in the dense-trajectory action-recognition work that dominated the field before deep video models.

Turning many descriptors into one vector

A practical problem sits between these descriptors and a classifier. HOG on a fixed window gives a fixed 3780 numbers, fine. But a video clip gives you thousands of local descriptors at varying counts, and an SVM needs one fixed-length vector.

The answer was bag of visual words, borrowed directly from text retrieval.

flowchart TD
  A["Extract local descriptors<br/>from all training videos"] --> B["k-means cluster them<br/>into K = 4000 groups"]
  B --> C["Each cluster centre<br/>= one 'visual word'"]
  C --> D["For a new clip:<br/>assign each descriptor<br/>to its nearest word"]
  D --> E["Count occurrences<br/>→ K-dimensional histogram"]
  E --> F["L2 normalise"]
  F --> G["Linear or χ² SVM<br/>→ action label"]

The clip is now described as “300 of word 12, 45 of word 891, 0 of word 3002…” regardless of how many descriptors it produced or how long it was.

The name is honest about the method’s main weakness: a bag has no order. Two clips with the same descriptors in a completely different spatial and temporal arrangement produce the same histogram. Spatial pyramids — building separate histograms for image sub-regions and concatenating — partly patched this, which is exactly the kind of hand-designed workaround that deep learning made unnecessary.

Running it

import cv2
import numpy as np

# HOG with the standard person parameters
hog = cv2.HOGDescriptor(
    _winSize=(64, 128),
    _blockSize=(16, 16),      # 2×2 cells
    _blockStride=(8, 8),      # slide by 1 cell → overlapping
    _cellSize=(8, 8),
    _nbins=9,
)

img = cv2.imread("person.png", cv2.IMREAD_GRAYSCALE)
win = cv2.resize(img, (64, 128))
d = hog.compute(win)
print(d.shape)                 # (3780, 1) — the number we derived

The bundled pedestrian detector:

hog.setSVMDetector(cv2.HOGDescriptor_getDefaultPeopleDetector())

boxes, weights = hog.detectMultiScale(
    frame,
    winStride=(8, 8),          # smaller = more windows, slower, better recall
    padding=(16, 16),
    scale=1.05,                # pyramid step; 1.05 is fine-grained, 1.2 is fast
)
for (x, y, w, h), score in zip(boxes, weights):
    if score > 0.6:
        cv2.rectangle(frame, (x, y), (x + w, y + h), (0, 255, 0), 2)

scale is the parameter to reach for first. At 1.05 the pyramid has many levels and finds people at more sizes; at 1.2 it has few and runs several times faster. If you know your camera geometry, restrict the size range instead — it is free accuracy and free speed.

Computing HOF and MBH from a flow field:

prev = cv2.cvtColor(frame1, cv2.COLOR_BGR2GRAY)
nxt  = cv2.cvtColor(frame2, cv2.COLOR_BGR2GRAY)

flow = cv2.calcOpticalFlowFarneback(prev, nxt, None,
                                    0.5, 3, 15, 3, 5, 1.2, 0)
u, v = flow[..., 0], flow[..., 1]

# HOF: bin the flow directions
mag, ang = cv2.cartToPolar(u, v, angleInDegrees=True)   # ang in 0..360
moving = mag > 0.5                                      # no-motion threshold
hof, _ = np.histogram(ang[moving], bins=4, range=(0, 360),
                      weights=mag[moving])
hof = np.append(hof, (~moving).sum())                   # the no-motion bin

# MBH: gradients of each flow component, then the same construction
dudx = cv2.Sobel(u, cv2.CV_32F, 1, 0, ksize=3)
dudy = cv2.Sobel(u, cv2.CV_32F, 0, 1, ksize=3)
mbhx_mag, mbhx_ang = cv2.cartToPolar(dudx, dudy, angleInDegrees=True)

Note the no-motion threshold of 0.5 pixels. Tune it on your own footage — too low and sensor noise fills the directional bins, too high and slow genuine motion disappears.

Practice task

About an hour.

1. Run OpenCV’s pedestrian detector on ten street photos. Record what it finds and what it misses. Sort the misses into: occluded, unusual pose, too small, cluttered background.
2. Take one photo where it works. Darken it by 60%, then brighten it by 60%. Does the detection survive? This is block normalisation doing its job — confirm it empirically.
3. Rotate the same photo by 10, 20 and 30 degrees. Find the angle where detection breaks.
4. Compute HOG on one 64×128 crop and confirm the length is 3780. Then change _cellSize to (6,6) and recompute the expected length by hand before running it. Check your arithmetic against the output.
5. On a short video, compute Farnebäck flow and build a 5-bin HOF per frame. Plot the dominant bin over time for a clip of someone walking across the frame, then for a clip shot from a panning phone. The second should look wrong — that is the failure MBH exists to fix.

Step 5 makes MBH’s motivation obvious in a way that no explanation does.

Summary

HOG describes a region by the distribution of its edge orientations rather than its pixel values, which is what lets one template match people wearing anything under any lighting. The pipeline — gradients, magnitude-weighted orientation histograms per 8×8 cell, L2 normalisation over overlapping 2×2 blocks, concatenation — produces exactly 3780 numbers for the standard 64×128 person window, and block normalisation is the step doing most of the work.

HOF keeps the construction and swaps image gradients for optical-flow vectors, so it describes motion direction instead of shape, with signed angles and an explicit no-motion bin. MBH takes spatial gradients of the flow field, which cancels any constant camera motion and leaves only genuine motion boundaries. Bag of visual words turned variable numbers of local descriptors into one fixed-length histogram an SVM could consume.

These methods lost to deep learning on cluttered, occluded, pose-varying data. They still win when you have no GPU, no dataset, and a scene you control — and understanding them makes what a CNN’s first layers are doing considerably less mysterious.

What comes next

Your first image classifier is where the learned alternative starts. Read it with HOG in mind: the network’s first convolutional layer learns oriented edge filters that closely resemble HOG’s orientation bins — the difference is that it discovers them from data and then stacks many more layers on top.

CNN architectures from LeNet to ResNet traces how that stacking developed, and the history of computer vision places HOG in the wider arc from Roberts to transformers.