1. Feature Extraction & Matching

Color spaces, edges, SIFT, HOG, Harris corners, Hough transform, feature matching

1. Color Systems

Before extracting features, we need to understand how images encode color. Different color systems emphasize different properties of light, and choosing the right one can make feature extraction more robust.

RGB (Red, Green, Blue)

The human eye has three cone types responding to long (~570nm, red), medium (~540nm, green), and short (~440nm, blue) wavelengths. Camera sensors replicate this with a Bayer filter pattern: 2 green, 1 blue, 1 red cell per pixel (green doubled because human vision is most sensitive to green).

Bayer filter mosaic on a camera sensor array.

HSV (Hue, Saturation, Value)

HSV separates color from lighting, making it more useful for many CV tasks:

• H (Hue): The color itself, angle in $[0, 360)$. 0 = red, 120 = green, 240 = blue.
• S (Saturation): Color purity, $[0, 1]$. 0 = grey, 1 = purest color.
• V (Value): Brightness, $[0, 1]$. 0 = black.

RGB cube and HSV cylinder representations.

2. Features and Image Matching

The core problem: given two or more images, how do we determine if they show the same scene? This is image matching, and it requires extracting features — pieces of information relevant to solving a computational task.

Image Matching Pipeline

1. Extract features invariant to geometric (translation, rotation, scale) and photometric (brightness) transformations
2. Compute descriptors — mathematical representations of local image regions
3. Match descriptors between images by comparing their vector representations

Requirements for Good Features

3. Canny Edge Detection

An edge is a location with a significant change (gradient) in pixel intensity, corresponding to boundaries, texture changes, or shadows. The Canny detector was designed to satisfy three criteria: optimal detection (low error rate), good localization, and single response per edge.

Original image (left) and Canny edge detection result (right).

Convolution: source matrix, kernel, and resulting output.

Sobel filter kernels

Sobel filters compute gradients in X and Y directions:

$G_x = \begin{bmatrix} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{bmatrix} \quad G_y = \begin{bmatrix} -1 & -2 & -1 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{bmatrix}$

$G_x$ detects vertical edges. $G_y$ detects horizontal edges. Combined: $G = \sqrt{G_x^2 + G_y^2}$, $\theta = \arctan(G_y / G_x)$.

4. HOG Descriptor (Histogram of Oriented Gradients)

Edges alone have limited descriptive power and are not rotation-invariant. HOG captures the distribution of gradient orientations in local regions, providing a richer, rotation-invariant feature.

HOG Pipeline

1. Split image into 8x8 blocks
2. Compute gradients (magnitude + orientation) at each pixel
3. Create 4x4 sub-windows, quantize gradients into 8 direction bins
4. Build histogram per sub-window (8 bins, weighted by magnitude)
5. Find dominant orientation of the block
6. Normalize the descriptor relative to the dominant orientation (rotation invariance)
7. Concatenate histograms into the HOG feature vector

HOG pipeline: Image to cell division to gradient orientation to histogram to vectorization.

HOG gradient direction roses overlaid on a person silhouette.

5. SIFT (Scale Invariant Feature Transform)

Edge points lack descriptive power. HOG is descriptive and rotation-invariant but not scale-invariant. SIFT addresses all three: scale invariance, rotation invariance, and rich 128-dimensional descriptors.

SIFT descriptor: 4x4 gradient windows, 8 orientation bins, Gaussian weighting, yielding 128-D vector.

6. Feature Matching

Given features from two images, find correspondences by comparing descriptor vectors.

Euclidean Distance Matching

For each feature $\mathbf{f}_1$ in Image 1, compute the L2 distance to every feature $\mathbf{f}_2$ in Image 2:

The closest match (smallest distance) is the candidate correspondence. Complexity: $O(N \times M \times D)$.

Improving Match Quality

• Lowe's ratio test: Accept match only if $d_1 / d_2 < 0.8$ (best vs second-best). Rejects ambiguous matches.
• Cross-checking: Verify mutual nearest neighbor — if A matches B, B must also match A.
• Approximate search: KD-trees or FLANN for large feature sets.

Detected local features shown as colored squares on a building facade.

7. Hough Transform — Line Detection

After edge detection, edge pixels are fragmented. The Hough Transform detects geometric shapes (especially lines) by converting the problem to a voting scheme in parameter space.

Polar Line Parameterization

Instead of $y = mx + c$ (fails for vertical lines), use: $\rho = x\cos\theta + y\sin\theta$, where $\rho$ is the perpendicular distance from origin to the line, and $\theta$ is the angle of that perpendicular.

Line parameterization: rho is perpendicular distance, theta is angle.

The Voting Algorithm

1. Run Canny to get edge pixels $(x_i, y_i)$
2. For each edge pixel, compute $\rho = x_i\cos\theta + y_i\sin\theta$ for all $\theta \in [0, 360)$
3. Increment the accumulator cell at $(\rho, \theta)$ for each computation
4. Peaks in the accumulator = detected lines (many collinear edge pixels voted for the same $(\rho, \theta)$)

Three edge points generate votes; collinear points share the same (rho, theta) pair.

8. Harris Corner Detector

Interest points are locations with distinctive local properties. Corners are ideal because they have intensity changes in multiple directions, making them unique and repeatable.

Corners detected where intensity changes in multiple directions.

The Mathematics

Intensity change when shifting a window by $(u, v)$:

Using Taylor expansion for small shifts, this becomes:

where $M$ is the structure tensor:

Interpreting R via Eigenvalues

Corner response R heatmap: red/yellow = high corner response.

Harris Detector Workflow

1. Compute gradients $I_x$, $I_y$ (Sobel filters)
2. Compute structure tensor $M$ at each pixel
3. Compute $R = \det(M) - k(\text{trace}(M))^2$
4. Threshold: keep pixels where $R > \text{threshold}$
5. Non-maximum suppression: take only local maxima

9. Haar-like Features

Haar-like features use simple rectangular masks to capture basic intensity patterns in images. The idea is to detect regions where there is a significant difference in intensity between adjacent rectangular sub-regions.

Types of Haar-like Features

Three main types exist:

1. Edge features: Two adjacent rectangles (one white, one black) — detect horizontal or vertical edges
2. Line features: Three rectangles (white-black-white or black-white-black) — detect line-like structures
3. Four-rectangle features: A $2 \times 2$ checkerboard pattern — detect diagonal structures

The three types of Haar-like features. White and black regions are assigned weights $+1$ and $-1$ respectively.

Computation

1. Assign weight $+1$ to white pixels and $-1$ to black pixels in the mask
2. Slide the mask over the image at all positions and scales
3. At each position compute the difference: $\text{white sum} - \text{black sum}$
4. If $|\text{difference}| > \text{threshold}$: a Haar feature is detected at this position

Cascaded Detection

In practice, Haar features are organised into a cascade of stages. Early stages use very few features and quickly reject non-face regions; later stages use more features to verify candidates. This makes detection fast in practice.

Haar cascade for face detection. Stage 0 uses 3 features, Stage 1 adds 10 more, and later stages accumulate 200+ features. Regions failing any stage are immediately discarded.

Properties

Flashcards