Chapter 7: Feature Detection and Matching

Once SIFT has localised a keypoint at its characteristic scale and orientation, it must summarise the surrounding appearance so the same point matches from another view. The SIFT descriptor takes a 16×16 patch around the keypoint, splits it into a 4×4 grid of cells, and builds an 8-bin gradient-orientation histogram in each cell; concatenating them gives a 128-dimensional vector. Because the patch is first rotated to the keypoint's dominant gradient direction, the descriptor is rotation-invariant, and normalising the vector to unit length (with a cap at 0.2 and renormalisation) makes it robust to brightness and contrast changes. Gradients are Gaussian-weighted toward the centre so pixels near the edge of the patch matter less. The result is highly discriminative but relatively heavy — 128 floats per point — which motivates the compact binary descriptor next.

SIFT's 128 floats are accurate but costly to store and slow to compare when thousands of features must be matched every frame. BRIEF (Binary Robust Independent Elementary Features) attacks both problems by encoding a patch as a binary string, typically 256 bits. It picks a fixed set of pixel pairs $(x_i, y_i)$ inside a smoothed patch and sets bit $i$ to 1 when $I(x_i) < I(y_i)$ and 0 otherwise, so each bit is one intensity comparison. Matching two such strings is a Hamming distance — an XOR followed by a popcount — which is roughly ten times faster than an L2 distance over SIFT floats and needs only 32 bytes of storage. The price is that BRIEF has no built-in rotation invariance, since its sampling pattern is fixed to the image axes; ORB, from the previous topic, fixes this by rotating the pattern with the keypoint.

Even good descriptors produce false matches, especially in scenes with repetitive texture like brick walls or windows where many points look alike. Lowe's ratio test filters these by comparing a keypoint's two closest candidates: let $d_1$ be the distance to the nearest descriptor and $d_2$ to the second nearest, and accept the match only when $d_1/d_2 < \theta$, with $\theta$ around 0.7 to 0.8. The logic is that a genuinely distinctive match is much closer to its true partner than to any impostor, so a low ratio signals confidence, while a ratio near 1 means two candidates are almost equally close and the match is ambiguous. Lowe found this single test rejects about 90% of wrong matches while keeping about 95% of correct ones, making it one of the highest-leverage steps in the whole matching pipeline.

The ratio test looks in one direction, but matching should be symmetric: if point $f_i$ in image one truly corresponds to $f_j$ in image two, then $f_j$'s best match should be $f_i$ in return. Cross-check enforces exactly this mutual condition, accepting a pair $(i,j)$ only when $f_j$ is the nearest neighbour of $f_i$ and $f_i$ is the nearest neighbour of $f_j$. This catches the many-to-one failures that a one-directional search misses — cases where several points in one image all claim the same partner in the other. It costs roughly twice the nearest-neighbour work but yields markedly higher precision, and it pairs well with the ratio test from the previous concept. Cross-check removes duplicate correspondences; a geometric verifier such as RANSAC then removes the remaining outliers by fitting a consistent transformation.

An edge is fundamentally a place of rapid intensity change, so the natural tool to find one is the derivative. The image gradient $\nabla I = (\partial I/\partial x, \partial I/\partial y)$ collects the rate of change in each direction; its magnitude $|\nabla I| = \sqrt{I_x^2 + I_y^2}$ measures edge strength and its direction $\theta = \arctan(I_y/I_x)$ points across the edge, perpendicular to it. In a discrete image the partials are approximated by finite differences between neighbouring pixels. The crucial catch is that differentiation is ill-posed: it magnifies high-frequency noise, so a raw gradient on a noisy image is unusable. The standard fix is to smooth first with a Gaussian, and because differentiation and convolution commute, we can convolve once with the derivative of a Gaussian — the insight every operator in this topic builds on.

Computing a gradient with a bare two-pixel difference is exquisitely sensitive to noise, so in practice we want an estimate that smooths as it differentiates. The Sobel operator does this with two 3×3 kernels: $G_x$ detects vertical edges by differencing left and right columns, $G_y$ detects horizontal edges by differencing top and bottom rows. The weight of 2 on the centre row or column is what distinguishes Sobel from a plain difference — each kernel factors into a $[1,2,1]$ smoothing filter times a $[-1,0,1]$ derivative filter, so it is separable and cheap, and the smoothing suppresses noise perpendicular to the derivative. That $[1,2,1]$ approximates a small Gaussian, tying Sobel directly to the derivative-of-Gaussian idea from the previous concept. The related Prewitt operator uses uniform $[1,1,1]$ weights and is slightly noisier; Scharr refines the weights for better rotational symmetry.

The gradient and Sobel give edge strength, but a usable edge map needs thin, clean, connected contours — not a thick smear of high-gradient pixels. The Canny detector is the classic four-stage pipeline that delivers this. It first Gaussian-smooths to control noise, then computes gradient magnitude and direction (via Sobel), then applies non-maximum suppression to thin each ridge to a single-pixel width by keeping only local maxima along the gradient direction, and finally applies hysteresis thresholding with a high and a low threshold. Hysteresis is the clever part: pixels above the high threshold are certain edges, and weaker pixels between the two thresholds are kept only if they connect to a certain edge, which bridges gaps without admitting isolated noise. Canny proved this design is optimal for step edges under three criteria — good detection, accurate localisation, and single response — which is why it remains a default decades later.

The gradient-based methods above find edges as maxima of the first derivative, but there is an alternative worth knowing: edges are also where the second derivative crosses zero. The Laplacian of Gaussian combines both steps into one operator, $\nabla^2 G$, which first smooths with a Gaussian of scale $\sigma$ and then takes the Laplacian, the sum of second spatial derivatives. Edges appear as the zero-crossings of $\nabla^2(G * I)$, and because the operator is circularly symmetric it responds to edges of any orientation equally, unlike a single directional gradient. The scale $\sigma$ selects how coarse the detected edges are. Crucially, the Difference of Gaussians approximates LoG — $G(k\sigma) - G(\sigma) \approx (k-1)\sigma^2 \nabla^2 G$ — which is precisely the cheap blob detector SIFT uses across scales, linking edge detection theory back to the feature detectors that opened this chapter.

Detecting a line by testing every pair of edge pixels is hopeless when pixels are scattered and broken, so the Hough Transform reframes the problem in parameter space. It describes a line not by slope and intercept — which blow up for vertical lines — but by the normal form $\rho = x\cos\theta + y\sin\theta$, where $\rho$ is the perpendicular distance from the origin and $\theta$ the angle of the line's normal, both bounded and well-behaved. A single image point $(x,y)$ satisfies this equation for a whole family of $(\rho, \theta)$ pairs, tracing a sinusoid in parameter space. The key fact is that collinear image points produce sinusoids that all cross at one $(\rho, \theta)$ — the parameters of their common line. Finding lines therefore becomes finding intersections in parameter space, which the accumulator of the next concept counts.

The voting idea only becomes an algorithm once parameter space is made discrete and countable, which is the accumulator's job. It is a 2D array whose axes are quantised $\theta$ and $\rho$ bins, and it works exactly like a histogram of lines: for each edge pixel, increment every cell along that pixel's sinusoid $\rho = x\cos\theta + y\sin\theta$. Where many pixels are collinear, their sinusoids pile votes into the same cell, so a strong line shows up as a bright peak $A(\rho,\theta)$ that clears a threshold. The bin resolution is the central trade-off: fine bins localise lines precisely but cost memory and can split one line's votes across neighbours, while coarse bins are robust but imprecise. Because quantisation scatters votes slightly, the accumulator is often Gaussian-smoothed before peaks are extracted, so a true line is not missed by falling between two cells.

The same voting principle extends beyond lines to any shape with a small number of parameters, and circles are the classic next step. A circle is defined by $(x-a)^2 + (y-b)^2 = r^2$, so its parameters are the centre $(a,b)$ and radius $r$ — three numbers, which means a 3D accumulator rather than 2D. That extra dimension is expensive: a full search over centre and radius has cost proportional to image area times the radius range. Two tricks tame it. If the radius is known in advance the problem collapses back to a 2D centre search, and more powerfully, the gradient direction at each edge pixel points along the line toward the circle's centre, so a pixel can vote along a single ray instead of a full circle of candidate centres. The generalised Hough transform pushes the idea further, detecting arbitrary shapes by storing edge-to-reference displacement vectors in a lookup table.

The standard Hough transform votes with every edge pixel and returns infinite lines, which is both slow on dense edge maps and awkward when you actually want a line's endpoints. The probabilistic Hough transform speeds things up by voting with only a random subset of $m$ edge pixels, cutting the work roughly in proportion to the sample size while still finding well-supported lines with high probability — a line backed by many pixels is very likely to be hit by the sample. The progressive variant goes further: it accumulates votes incrementally, checks for a supported line after each vote, then traces that line in the image and removes its supporting pixels before continuing. This yields actual line segments with real endpoints rather than infinite lines, and typically runs several times faster than the full transform. The trade-off is that very short segments, backed by few pixels, may be missed by the random sampling.