Histogram of Oriented Gradients

Figure 7.2: Computing the gradient histogram: the magnitude (b) and phase (c) of the gradients are computed from the cells, possibly overlapping, into which the image (a) is divided, and a histogram (d) is constructed for each cell.

The Histogram of Oriented Gradients (HOG) is one of the techniques that has recently achieved the greatest success in effectively describing an area. This method was first used successfully in SIFT to describe feature points and, together with SVMs, to obtain high-performance classifiers (DT05).

Given the window from which the descriptor is to be extracted, the magnitude and phase of a gradient operator (a derivative filter, Sobel, or any other operator) are computed for each point. The extracted phase is then quantized: normally, 6 to 9 bins are computed and, optionally, the phase is calculated with periodicity $\pi$, thereby ignoring the sign of the gradient.

The ideas underlying HOG are both to use the gradient phase to obtain a compact descriptor that is highly invariant to brightness and to divide the window under analysis into subregions, called cells, which may overlap and may have any shape and size. Although HOG cells are normally square, rectangular cells can be found in R-HOG and circular cells in C-HOG.

A portion of the descriptor, consisting of the gradient-magnitude histogram, is extracted from each subregion into which the image is divided. The most widely used HOG variants attempt to normalize brightness and contrast locally. To do this, spatially neighboring cells are grouped into blocks. For each block, a normalization factor is extracted and used to adjust the weight of each subcell.

The histogram bin for each cell into which the area is divided constitutes the descriptor, which is used when comparing points or during training for object recognition.