Histogram of Oriented Gradients (HOG)

The HOG descriptor begins by computing the intensity gradient for each pixel in the image. This is typically done using simple 1-D centered, point discrete derivative masks (e.g., [-1, 0, 1]) applied in the horizontal and vertical directions. The result is a gradient vector at each pixel, characterized by its magnitude (strength) and orientation (direction). This step transforms the raw pixel values into a representation of local edge structure, which is fundamental to capturing object contours.

The image is divided into small, connected spatial regions called cells (e.g., 8x8 pixels). Within each cell, a local 1-D histogram of gradient orientations is compiled. The contribution of each pixel's gradient to the histogram is weighted by its magnitude, making stronger edges more influential. The orientation range (0-180° or 0-360°) is divided into a fixed number of orientation bins (typically 9). This process converts the dense gradient field into a more compact, localized histogram representation that is robust to small deformations.

To achieve illumination invariance and reduce the impact of shadowing, local histograms are normalized. This is done by grouping cells into larger, overlapping spatial blocks (e.g., 2x2 cells). The histograms from all cells in a block are concatenated into a vector and then normalized, often using L2-Hys normalization (L2-norm followed by clipping and renormalization). This step ensures the descriptor is robust to changes in lighting conditions and foreground-background contrast, which is critical for real-world object detection.

For object detection, a classifier (originally a linear SVM) is trained on HOG features extracted from positive and negative training image patches. During inference, a detection window of fixed size (e.g., 64x128 pixels for pedestrian detection) is slid across the image at multiple scales. At each window position, the HOG descriptor is computed and passed to the classifier to score the likelihood of an object's presence. This generates a heatmap of detections, which are then consolidated using non-maximum suppression.

HOG is engineered for specific types of invariance crucial for object detection:

• Geometric invariance: It is robust to small translations and rotations within a cell due to the histogram binning process.
• Photometric invariance: Local contrast normalization provides robustness to changes in illumination and shadowing.
• Deformation tolerance: The local histogram representation allows for some flexibility in object shape, as long as the overall gradient structure is preserved within the cells and blocks.

HOG represents the paradigm of handcrafted features, where domain expertise explicitly designs the feature extraction pipeline. This contrasts with modern deep convolutional neural networks (CNNs), which learn hierarchical feature representations directly from data. While CNNs generally provide superior performance, HOG remains relevant for its computational efficiency, interpretability, and effectiveness in applications with limited training data or on hardware with strict power constraints.

A pioneering algorithm for detecting and describing local image features. Like HOG, it is a handcrafted descriptor, but it is designed to be invariant to image scale and rotation. It works by:

• Identifying keypoints using a difference-of-Gaussians function.
• Assigning a dominant orientation based on local image gradients.
• Creating a descriptor from histograms of gradients around the keypoint. SIFT was crucial for tasks like image stitching and object recognition before the deep learning era, offering robustness that HOG alone did not provide.

The pattern of apparent motion of objects between consecutive video frames. While HOG analyzes static image gradients, optical flow estimates motion vectors by tracking intensity patterns over time. Core methods include:

• Lucas-Kanade: Assumes small, consistent motion in a local neighborhood.
• Farnebäck: A dense optical flow method using polynomial expansion. Optical flow is a fundamental temporal feature for video analysis, used in action recognition, video compression, and autonomous navigation to complement spatial descriptors like HOG.

Deep learning architectures that automatically learn hierarchical feature representations from raw pixel data. CNNs rendered handcrafted descriptors like HOG largely obsolete for many tasks by learning optimal filters through backpropagation. Key layers include:

• Convolutional Layers: Apply learnable filters to extract local features.
• Pooling Layers: Downsample feature maps for translation invariance.
• Fully Connected Layers: Perform final classification or regression. CNNs learn features analogous to edge detectors (like HOG) in early layers and complex object parts in deeper layers, offering superior performance on large datasets.

An architecture that builds a multi-scale feature pyramid from a single input image. It addresses a key limitation of single-scale descriptors like HOG by efficiently constructing rich, multi-scale feature maps. The FPN uses:

• A bottom-up pathway (a standard CNN backbone like ResNet).
• A top-down pathway with lateral connections to combine high-resolution, low-semantic features with low-resolution, high-semantic features. This pyramid structure is essential for modern object detectors to accurately identify objects at vastly different scales, a problem where classic HOG struggled.

A low-level image processing operation that identifies points where image brightness changes sharply. HOG is built upon this fundamental concept, as it computes gradients to find edges. Classic edge detection algorithms include:

• Sobel & Prewitt Operators: Use convolution kernels to approximate gradients.
• Canny Edge Detector: A multi-stage algorithm involving Gaussian smoothing, gradient calculation, non-maximum suppression, and hysteresis thresholding. These operators produce raw edge maps, while HOG aggregates and bins these gradient orientations into histograms within cells to create a more structured descriptor for object shape.

A classical object detection framework that was a direct successor and major application of HOG features. DPM models objects as a collection of parts arranged in a latent spatial configuration. Its architecture involves:

• A root filter (a coarse HOG template for the whole object).
• Multiple part filters (higher-resolution HOG templates for object parts).
• A spatial model defining allowed deformations between parts. DPM, often called a "mixture of HOG templates," was a state-of-the-art detector before being surpassed by deep learning methods like R-CNN and YOLO.