Szeliski Chapter 4 — Feature Detection & Matching.

This is the feature chapter for the Computer Vision mid-sem arc. It is where gradients and pyramids become practical matching systems, and where local image structure starts supporting stitching, tracking, recognition, and 3D geometry.

01 Why features are the bridge from pixels to geometry and recognition

Raw pixels are too fragile for many vision tasks. If the camera shifts by a few pixels, the entire image array changes. If lighting changes, pixel intensities change. If an object scales or rotates, a fixed patch no longer lines up. Feature detection and matching solve a practical problem: find image locations and descriptions that are repeatable enough to recognise the same scene part across images.

Chapter 4 is where Szeliski moves from generic image operations to local image evidence. A feature can be a corner, blob, edge point, line, patch, or descriptor vector. Good features should be repeatable under viewpoint and illumination changes, distinctive enough to match, accurately localised, efficient to compute, and numerous enough for robust estimation. Different applications prefer different trade-offs. Image stitching wants reliable matches across views. Tracking wants stable points over time. Recognition wants descriptors that survive object appearance changes. 3D reconstruction wants accurate correspondences.

For CV1-CV7, this chapter covers many exam-famous names: Harris, structure tensor, non-maximum suppression, scale-space, SIFT, nearest-neighbour matching, Lowe ratio test, Canny, Hough transform, and HoG. They are easier to remember if you view them as answers to a single question: how do we turn messy local pixel patterns into stable evidence?

02 Points and patches: repeatability, distinctiveness, locality, and invariance

A point feature usually means an interest point: a location worth describing because its neighbourhood is informative. A flat wall is bad because every nearby patch looks similar. A straight edge is partly informative but ambiguous along the edge direction. A corner is strong because shifting the window in any direction changes appearance. A blob is useful because it has a characteristic centre and scale. A textured patch can be distinctive even if it is not a textbook corner.

Repeatability means the detector finds the same physical scene point in different images. Distinctiveness means the descriptor for that point is not easily confused with many others. Locality means the feature occupies a small neighbourhood, so it can survive partial occlusion and local deformation. Invariance means the feature or descriptor handles transformations such as translation, rotation, scale, affine distortion, brightness shift, or contrast change.

A patch descriptor can be as simple as raw pixel values after normalisation. But raw patches fail under rotation, scale, and illumination changes. More advanced descriptors summarise gradients or binary intensity tests to gain robustness. Chapter 4’s central arc is this progression from local patches to carefully engineered invariant descriptors.

03 Harris corner detector: the structure tensor and the cornerness score

The Harris detector starts with a local question: if I shift a small window around this pixel, how much does the image patch change? In a flat region, small shifts change little. Along an edge, shifts along the edge change little but shifts across the edge change a lot. At a corner, shifts in both directions cause large change. This intuition is formalised using the second-moment matrix, often called the structure tensor:

The eigenvalues \(\lambda_1,\lambda_2\) of \(M\) describe gradient energy in two principal directions. If both are small, the region is flat. If one is large and one small, it is an edge. If both are large, it is a corner. Harris avoids explicitly computing eigenvalues by using

Large positive \(R\) indicates a corner. Negative values often indicate edges. After computing the response, the detector applies thresholding and non-maximum suppression so that only local peaks remain.

04 Non-maximum suppression and adaptive non-maximum suppression

Detectors usually produce a response value at every pixel. If we keep every pixel with a high value, we get clusters of detections around the same structure. Non-maximum suppression keeps only points that are local maxima in a neighbourhood. This turns a response map into a sparse set of features.

Standard non-maximum suppression uses a fixed neighbourhood size. Adaptive non-maximum suppression, often used in feature matching and image stitching pipelines, tries to keep strong points that are also spatially well distributed. For each candidate, it estimates a suppression radius: how far away is the nearest significantly stronger candidate? Points with large radii are kept. This avoids placing all features on one highly textured object while leaving the rest of the image empty.

In practical CV work, feature distribution matters. Homography estimation, fundamental matrix estimation, and tracking become unstable if features are concentrated in a tiny region. ANMS is a simple strategy that improves geometric conditioning without changing the detector response itself.

05 Scale invariance: why a fixed-size corner detector is not enough

A corner detector with a fixed window size has a hidden assumption: the structure appears at that scale. But the same physical point may occupy many pixels in one image and few pixels in another. A small window may see only part of a large blob; a large window may blur away a tiny corner. Scale invariance asks the detector to find both location and characteristic scale.

Scale-space builds a family of progressively smoothed images \(L(x,y,\sigma)=G_\sigma * I(x,y)\). Features are searched not only over \(x,y\), but also over \(\sigma\). A blob detector may look for maxima of the scale-normalised Laplacian:

The \(\sigma^2\) normalisation is important because derivative magnitudes naturally change with scale. Without normalisation, comparisons across scales are biased. SIFT uses Difference of Gaussians as an efficient approximation to Laplacian-of-Gaussian blob detection. The result is a keypoint with location and scale.

06 SIFT step by step: DoG extrema, localisation, orientation, and descriptor

SIFT, the Scale-Invariant Feature Transform, is famous because it combines several good design choices into one robust pipeline. First, it constructs a Gaussian scale-space. Adjacent blurred images are subtracted to form Difference-of-Gaussian images. Local extrema in this 3D volume of \((x,y,\sigma)\) become keypoint candidates. This finds blob-like structures at characteristic scales.

Second, SIFT refines keypoint location and rejects unstable candidates. Low-contrast points are discarded because they are sensitive to noise. Edge-like responses are rejected because they are poorly localised along the edge direction. Third, SIFT assigns one or more dominant orientations based on local gradient directions. By rotating the descriptor frame to this orientation, the descriptor becomes rotation invariant.

Finally, SIFT constructs a descriptor. Around the keypoint, gradients are accumulated into orientation histograms over a \(4\times4\) grid of cells, with 8 orientation bins per cell. That gives \(4\times4\times8=128\) values. The descriptor is normalised to reduce sensitivity to illumination scale, clipped to reduce the effect of large gradients, and normalised again.

The brilliance of SIFT is not one trick. It is the combination: scale selection, orientation alignment, gradient histograms, local pooling, and normalisation. Each part removes a nuisance factor while preserving enough distinctiveness to match.

07 Feature descriptors: raw patches, gradient histograms, binary descriptors, and normalisation

After detection, we need description. A descriptor converts the neighbourhood around a keypoint into a vector that can be compared with descriptors from another image. Raw pixel patches are simple but sensitive to brightness, rotation, and scale. Normalised patches subtract mean and divide by standard deviation, which helps with brightness and contrast but not with geometric changes.

Gradient-based descriptors such as SIFT are more robust because gradients reduce sensitivity to additive brightness shifts and histograms tolerate small localisation errors. HoG, used widely for object detection, also accumulates gradient orientations in local cells. Binary descriptors such as BRIEF, ORB, and FREAK compare pairs of pixel intensities to produce bit strings. They are fast and matched with Hamming distance, which makes them useful for real-time systems.

Descriptor normalisation is not cosmetic. If one image is brighter, raw gradient magnitudes may be larger. Normalising the vector makes matching depend more on pattern than absolute strength. But too much normalisation can also reduce useful contrast information. Again, feature design is a trade-off.

08 Feature matching: nearest neighbours, ratio test, cross-checks, and outliers

Given descriptors from two images, matching often begins with nearest-neighbour search. For a descriptor \(d_i\) in image A, find the descriptor \(d_j\) in image B with the smallest distance. For SIFT-like descriptors, Euclidean distance is common. For binary descriptors, Hamming distance counts bit differences.

Nearest neighbour alone produces many false matches because some features are ambiguous. Lowe’s ratio test compares the closest and second-closest distances. Accept a match only if

The ratio test keeps matches whose best neighbour is clearly better than the runner-up. Cross-checking adds another constraint: A’s best match should also choose A when matched backward from B. Even after these tests, outliers remain. Geometric verification with RANSAC is usually needed before estimating homographies, fundamental matrices, or camera pose.

09 Edges and Canny: derivatives, non-maximum suppression, and hysteresis

An edge is a location of strong intensity change. Derivative filters estimate gradients \(I_x\) and \(I_y\). The gradient magnitude is \(\sqrt{I_x^2+I_y^2}\), and orientation is \(\tan^{-1}(I_y/I_x)\). Because derivatives amplify noise, edge detection usually begins with Gaussian smoothing or derivative-of-Gaussian filters.

Canny edge detection is a classic multi-step method. It smooths the image, computes gradients, thins responses using non-maximum suppression along the gradient direction, and uses hysteresis thresholding. Hysteresis uses a high threshold for strong edge seeds and a low threshold for connected weak edge pixels. This keeps meaningful continuous edges while rejecting isolated weak noise.

Edges are useful for shape, boundaries, vanishing points, lane detection, and line extraction. But not every edge is an object boundary. Shadows, texture, highlights, and surface markings also create edges. This is a major conceptual trap: image edges are intensity events, not guaranteed semantic boundaries.

10 Lines and the Hough transform

Line detection turns local edge evidence into global geometric structure. The Hough transform maps each edge point to a set of possible lines in parameter space. A common line parameterisation is

Each image edge point votes for all \(( ho,\theta)\) lines that could pass through it. If many points lie on the same image line, their votes intersect at a peak in accumulator space. Detecting peaks gives line candidates. The polar form avoids the infinite slope problem of \(y=mx+c\).

Hough transforms are robust to gaps because points do not need to be connected. They are also robust to some noise because voting aggregates evidence. But accumulator resolution matters: too coarse merges lines; too fine spreads votes. Computational cost can be high if the parameter space is large.

11 Successive approximation, line segments, and practical fitting

Hough gives candidate global lines, but many applications need finite line segments. Successive approximation methods, split-and-merge algorithms, and iterative line fitting convert edge chains into simpler geometric primitives. A common strategy is to trace connected edge pixels, fit a line to a chain, measure deviation, split where error is high, and repeat until segments approximate the curve well.

Least-squares line fitting minimises distances between points and a line, but ordinary vertical-residual fitting is biased when lines are near vertical. Orthogonal distance fitting is better for geometry. Robust fitting is needed when outliers exist. RANSAC can fit a line by repeatedly sampling two points, counting inliers, and keeping the model with strongest support.

In lecture terms, this is the move from pixel-level edges to geometric primitives. Edges are local. Lines and segments are structured. Once you have segments, you can reason about vanishing points, rectangles, document boundaries, lane markings, and man-made scene geometry.

12 HoG: histograms of oriented gradients for object shape

HoG, Histograms of Oriented Gradients, describes local shape by counting gradient orientations in cells. It became famous for pedestrian detection, but the idea is broader: object shape is often captured better by local edge orientation distributions than by raw colour. Like SIFT, HoG uses gradient histograms. Unlike SIFT, it is typically computed densely over a detection window rather than sparsely at keypoints.

A typical HoG pipeline computes gradients, bins orientations in small cells, groups cells into blocks, normalises each block, and concatenates the results. Block normalisation gives robustness to local illumination and contrast changes. A classifier such as a linear SVM can then learn which gradient patterns indicate an object.

HoG is a useful historical bridge to CNNs. Early convolutional layers often learn oriented edge-like filters, and pooling/normalisation provide some local robustness. Modern networks replaced hand-crafted HoG in many tasks, but understanding HoG still teaches why gradients, cells, blocks, and local normalisation are powerful.

13 How Chapter 4 connects to CV lectures and project work

In the CV1-CV7 sequence, Chapter 4 is the feature engineering centre. It uses Chapter 3’s gradients, smoothing, pyramids, histograms, and non-maximum suppression to build real correspondence tools. Harris and SIFT are especially important because they show two levels of maturity: corners are good local structures, while SIFT turns local structures into scale- and rotation-aware descriptors that can be matched across images.

For project work, the usual pipeline is detect features, compute descriptors, match descriptors, remove ambiguous matches, estimate a geometric model with RANSAC, and then use inliers for stitching, tracking, localisation, or 3D reconstruction. If the result fails, debug each stage separately. Are there enough features? Are they distributed well? Are descriptors distinctive? Is the ratio threshold too strict or too loose? Are matches geometrically consistent? Is there repetitive texture?

Modern learned features exist, but the classical chapter remains valuable because it exposes the design logic. Repeatability, distinctiveness, invariance, localisation, and efficiency are still the criteria used to judge learned detectors and descriptors.

14 Worked revision example: stitching two overlapping images

Image stitching is a perfect example because it uses almost every major idea in Chapter 4. Suppose you take two overlapping photos of the same building from roughly the same camera centre, or of a faraway scene where parallax is small. The goal is to align them into a panorama. A pixel-by-pixel comparison will fail because the images are shifted, rotated, slightly scaled, and photometrically different. Instead, we detect features independently in both images.

First, choose a detector. Harris corners can work if scale change is small. SIFT is safer when the images differ in scale or rotation. The detector should produce repeatable locations on windows, roof corners, signs, brick intersections, or other textured structures. Then apply non-maximum suppression so clusters collapse into single points. If all features lie on one textured sign, adaptive non-maximum suppression can improve spatial coverage. Good coverage matters because the homography should be constrained across the overlap, not only in a small region.

Second, compute descriptors. A raw patch may fail if one image is rotated or exposed differently. SIFT descriptors summarise local gradient orientation patterns in a scale- and orientation-normalised frame, making them more stable. Third, match descriptors using nearest neighbours. At this stage there will be false matches: repeated windows, similar bricks, and accidental texture similarities. Lowe’s ratio test removes matches where the best candidate is not clearly better than the second best. Cross-checking can remove additional asymmetric matches.

Fourth, estimate the geometric model. For a panorama under the right assumptions, a homography maps points from one image to the other. But false matches still exist, so use RANSAC. It samples minimal sets of correspondences, estimates a homography, counts inliers under a reprojection-error threshold, and keeps the model with the best support. The inlier matches are the ones that agree with one coherent projective warp. This is the step that turns descriptor similarity into geometric consistency.

Finally, warp and blend. The homography moves one image into the other image’s coordinate system. Interpolation resamples pixels. Exposure differences may create seams, so blending or gain compensation may be needed. Notice how Chapter 4 depends on earlier chapters: image formation explains why a homography is valid only under planar or pure-rotation assumptions; image processing explains smoothing, gradients, pyramids, and warping; feature detection supplies robust correspondences.

This example also gives a debugging checklist. If there are too few matches, lower the detector threshold, improve contrast, or use a more robust detector. If matches are many but wrong, tighten the ratio threshold or use better descriptors. If RANSAC finds few inliers, the scene may violate the homography assumption because of parallax, moving objects, or rolling shutter. If alignment is good in one region and bad elsewhere, the scene may be non-planar. If the geometry is correct but the seam is visible, the problem is photometric blending, not feature matching. This separation of failure modes is exactly what makes the chapter practically valuable.

There is a second stitching lesson: descriptor matching is not the same as recognition. A SIFT match says two local gradient patterns are similar under the descriptor’s assumptions. It does not say the same object category is present, and it does not say the match is globally correct. Repetitive structures such as building windows, tiles, railings, and book spines create many locally plausible but globally wrong matches. This is why geometric verification is not an optional final polish; it is part of the definition of a reliable correspondence pipeline.

Feature scale also affects stitching quality. If features are too tiny, they may be unstable under blur, compression, and viewpoint change. If they are too large, they may cover regions that are not truly planar or that include moving objects. SIFT’s scale selection helps, but it does not remove the need to inspect matches. A useful visual debugging step is to draw matches before and after ratio testing, then draw only RANSAC inliers. The progression often reveals exactly where the pipeline is failing.

Finally, remember that modern learned matchers still follow the same conceptual stages. They may learn keypoints, descriptors, matching scores, or outlier rejection, but they still need repeatable evidence, distinctive representation, and consistency checks. Classical Chapter 4 vocabulary therefore remains useful even when the implementation changes. If a learned matcher fails on low texture, repetitive patterns, motion blur, or strong viewpoint change, the explanation usually sounds very similar to the classical failure modes.

For exam diagrams, draw the pipeline rather than isolated boxes. A Harris answer should show gradients, products of gradients, Gaussian windowing, response score, thresholding, and NMS. A SIFT answer should show scale-space, DoG extrema, localisation, orientation, descriptor grid, and matching. A Canny answer should show smoothing, gradients, thinning, and hysteresis. Pipeline memory is stronger than name memory.

Also practise explaining failure cases in words. Low texture gives too few stable detections. Repetition gives ambiguous descriptors. Motion blur weakens gradients. Viewpoint change breaks simple patch assumptions. Illumination change changes raw intensities. Occlusion removes correspondences. These are not random bugs; each one attacks a specific requirement of useful features.

15 References and extra reads

The primary reference is Richard Szeliski, Computer Vision: Algorithms and Applications, 2nd edition, Chapter 4. Also read the original Harris and Stephens corner detector paper, David Lowe’s SIFT paper, Canny’s edge detection paper, and practical OpenCV tutorials for Harris, SIFT/ORB, BFMatcher/FLANN, Canny, and Hough lines. For HoG, read Dalal and Triggs on pedestrian detection.

Good exercises are: implement Harris from gradients and a Gaussian window, compare NMS radii, build a small DoG scale-space, match SIFT descriptors with and without the ratio test, run RANSAC after matching, tune Canny thresholds, and visualise Hough accumulator peaks. These experiments turn names into intuition.

FAQ Quick questions students usually ask

Why are corners better than edges for matching?

Edges are ambiguous along their length: many positions look similar. Corners change in two directions, so they are better local anchors.

Why does SIFT use gradients instead of raw pixels?

Gradients reduce sensitivity to brightness shifts and capture local shape. Histograms add tolerance to small localisation errors.

What does the ratio test reject?

It rejects descriptors whose nearest neighbour is not much better than the second nearest, which usually means the match is ambiguous.

Is Canny an edge detector or a line detector?

Canny detects edge pixels. Line detection, such as Hough transform, groups edge evidence into line models.

Why still learn classical features if CNNs exist?

Classical features teach repeatability, invariance, localisation, and matching logic, which remain important even in learned systems.

!! Exam traps, implementation gotchas, and debugging smells

++ Takeaways and chapter cheatsheet

• Good features are repeatable, distinctive, local, well-localised, efficient, and robust to expected changes.
• Harris uses the structure tensor to identify patches that change strongly in two directions.
• Scale-space and SIFT handle unknown feature size and rotation through DoG extrema, orientation assignment, and gradient histograms.
• Matching needs ambiguity rejection, especially Lowe ratio test and geometric verification.
• Canny turns gradients into thin connected edges; Hough turns edge votes into line hypotheses.
• HoG and SIFT show why gradient orientation histograms are powerful for both matching and detection.