histogram of oriented gradients

The Histogram of Oriented Gradients (HOG), introduced by Navneet Dalal and Bill Triggs in 2005 for pedestrian detection, captures the shape of an object by summarizing the local distribution of edge directions, while deliberately throwing away exactly where each edge sits. The intuition is that a standing person, a car, or a face has a characteristic silhouette of gradients: strong vertical edges at the sides of a torso, a rounded gradient pattern at the head, and so on. If you record, region by region, which gradient directions are present and how strong they are, you get a description of shape that tolerates small shifts and deformations, because a leg that moves a few pixels still contributes the same orientations to the same general region.

Unlike SIFT, which describes sparse keypoints, HOG is a dense descriptor computed over a regular grid covering a whole detection window. The image window is divided into small connected regions called cells (for example 8 by 8 pixels). In each cell, the gradient orientation of every pixel is sorted into one of several orientation bins (commonly 9 bins spanning 0 to 180 degrees, treating opposite directions as equivalent), and each pixel votes into its bin weighted by its gradient magnitude. The result per cell is a small histogram describing the dominant edge directions there.

The step that gives HOG its robustness is block normalization. Raw histograms are sensitive to lighting and contrast: brighten the image and all gradient magnitudes scale up. HOG groups cells into larger overlapping blocks (for example 2 by 2 cells), and within each block it normalizes the concatenated histograms to unit length so that local contrast is divided out. Because blocks overlap, each cell contributes to several normalizations, which adds redundancy and stability. Concatenating the normalized block descriptors across the whole window yields one long feature vector, typically a few thousand numbers, describing the window's shape.

HOG combined with a linear support vector machine was the state of the art for pedestrian and object detection in the late 2000s, and HOG features powered the influential Deformable Parts Model. Sliding a HOG-plus-SVM classifier across positions and scales detects objects; this is dense and somewhat slow, mitigated by integral-histogram tricks. HOG has since been superseded by convolutional networks, which learn richer multi-layer features, and by transformer detectors like DETR. Yet HOG remains pedagogically central and still useful where training data is scarce or compute is tight, and its core idea, pooling gradient orientations into spatial cells with local normalization, echoes directly in the first layers of modern CNNs.