Classical Features: Harris Corners, SIFT, HOG and Bag of Visual Words

In the 2000s, the most important question in computer vision was: what features should we extract from an image? Brilliant hand-engineered answers — Harris corners, SIFT, HOG — powered panorama stitching, object recognition and pedestrian detection. They remain widely used in 3-D reconstruction, visual SLAM for robots and image registration, and they illuminate what deep networks later learned automatically.

Interest points: Harris corners#

Good features are distinctive and repeatable. Corners qualify: shifting a small window at a corner changes its contents in every direction. Harris and Stephens (1988) formalised this with the structure tensor:

Eigenvalues of $\mathbf{M}$ describe intensity change: both small → flat region; one large → edge; both large → corner. The Harris response $R = \det\mathbf{M} - k(\text{tr}\,\mathbf{M})^2$ avoids computing eigenvalues explicitly.

SIFT: scale-invariant features#

David Lowe's Scale-Invariant Feature Transform (1999, 2004) was one of the most influential vision algorithms ever. It finds keypoints and descriptors that are invariant to scale and rotation and robust to illumination and viewpoint changes.

1. Scale-space extrema: build a pyramid of Gaussian-blurred images and compute differences of Gaussians (DoG), approximating the scale-normalised Laplacian. Keypoints are local extrema in space and scale — each has a characteristic size.
2. Keypoint refinement: sub-pixel localisation; reject low-contrast points and points on edges.
3. Orientation assignment: the dominant gradient direction in the neighbourhood, so descriptors can be rotated to a canonical orientation.
4. Descriptor: a $16 \times 16$ neighbourhood divided into $4 \times 4$ cells, each summarised by an 8-bin histogram of gradient orientations → a 128-dimensional vector, normalised for illumination robustness.

Matching: find each descriptor's nearest neighbour in another image, and accept it only if it is much closer than the second-nearest (Lowe's ratio test, e.g. ratio < 0.75). Then use RANSAC to fit a geometric transformation (homography or fundamental matrix) robustly, rejecting outlier matches.

import cv2
import numpy as np

img1 = cv2.imread("scene_left.jpg", cv2.IMREAD_GRAYSCALE)
img2 = cv2.imread("scene_right.jpg", cv2.IMREAD_GRAYSCALE)
sift = cv2.SIFT_create()
kp1, des1 = sift.detectAndCompute(img1, None)
kp2, des2 = sift.detectAndCompute(img2, None)

matches = cv2.BFMatcher().knnMatch(des1, des2, k=2)
good = [m for m, n in matches if m.distance < 0.75 * n.distance]     # ratio test
src = np.float32([kp1[m.queryIdx].pt for m in good]).reshape(-1, 1, 2)
dst = np.float32([kp2[m.trainIdx].pt for m in good]).reshape(-1, 1, 2)
H, inliers = cv2.findHomography(src, dst, cv2.RANSAC, 5.0)          # robust alignment
print(len(kp1), "keypoints;", len(good), "good matches;", int(inliers.sum()), "RANSAC inliers")

This is the core of panorama stitching. Faster alternatives include SURF and ORB (binary descriptors, free of patent restrictions historically associated with SIFT and SURF; SIFT's patent has since expired).

HOG: histograms of oriented gradients#

Dalal and Triggs (2005) designed HOG for pedestrian detection:

1. Compute gradients.
2. Divide the detection window into small cells (e.g. $8 \times 8$ pixels) and build a histogram of gradient orientations (9 bins) per cell, weighted by magnitude.
3. Normalise histograms over overlapping blocks of cells for illumination invariance.
4. Concatenate into a feature vector and classify with a linear SVM, sliding the window over the image at multiple scales.

HOG captures shape through the distribution of edge directions. The later Deformable Part Models (Felzenszwalb et al.) extended HOG with movable parts and dominated detection benchmarks until deep learning.

from skimage.feature import hog
from skimage import io, color
features, hog_image = hog(color.rgb2gray(io.imread("person.jpg")), orientations=9,
                          pixels_per_cell=(8, 8), cells_per_block=(2, 2), visualize=True)
print(features.shape)

Bag of visual words#

To classify whole images, the bag-of-visual-words model borrowed from text retrieval:

1. Extract local descriptors (e.g. SIFT) from many training images.
2. Cluster them with k-means into a visual vocabulary of, say, 1,000 "words".
3. Represent each image as a histogram of visual-word occurrences.
4. Train an SVM (often with a $\chi^2$ kernel) on the histograms.

Extensions — spatial pyramid matching, VLAD, Fisher vectors — added spatial layout and richer statistics and were state of the art just before 2012.

Classical vs learned features#