12.0 MATCHING PIXELS AND HUMANS ACROSS SPACE AND TIME🔗⧉

Averaging a burst requires the same scene structure to land at the same output coordinates. Stitching needs corresponding features across viewpoints. Following a hand through video needs an identity that survives many frames. Each task estimates a map, but its assumptions and failure modes differ.

Chapter 12.1, Brute force and Chapter 12.2, Sub-pixel matching establish the alignment objective and precision limits. Chapter 12.3, Sparse matching selects and describes useful locations; Chapter 12.4, Feature tracking follows them through time. Chapter 12.5, Robustness: the ratio test and RANSAC handles ambiguity and inconsistent matches, and Chapter 12.7, Fast matching reduces search cost.

Chapter 12.8, Optical flow estimates a dense displacement field. Textureless regions, repeated patterns and occlusions cannot be resolved from brightness alone, so local models and priors supply missing information. Learned matchers and flow networks improve those models, but a prediction at every pixel is not evidence that every correspondence is observable.

Chapter 12.10, Face tracking and Chapter 12.11, Body pose estimation use semantic models to locate named features. Their outputs need coordinate, visibility and temporal conventions before they can drive an edit or measurement. Throughout the part, Chapter 11.1, Warping provides the separate step that transports image values through an estimated map.

This is the estimation half of the geometry developed in Chapter 11.1, Warping. Given a map, warping transports image content. Given images, matching tries to recover that map, despite noise, ambiguity and missing correspondences. Once matched samples are known, comparatively simple operations such as averaging or blending become useful. Aligned frames of a burst, averaged, reduce noise; aligned views, blended, form a panorama; aligned exposures merge into an HDR image. Skip the alignment and the same average produces a double exposure, with ghosts wherever something moved.

Two independent distinctions organize the problem. Sparse methods seek a limited set of distinctive matches; dense methods estimate a field over the image. Either can operate across viewpoints or across time. A few reliable points may suffice to fit a camera transform, while merging independently moving regions needs more local information. More estimated vectors do not necessarily mean more observed information: a smooth wall can acquire a dense field almost entirely from a prior.

Contents of this part

• 12.1 Brute force
  • 12.1.1 Why you must align first
  • 12.1.2 Brute-force translational alignment (SSD / NCC)
  • 12.1.3 Phase correlation: the whole shift from one FFT
  • 12.1.4 Coarse-to-fine alignment on a pyramid
• 12.2 Sub-pixel matching
  • 12.2.1 Refining the cost: fit a parabola
  • 12.2.2 Refining in the frequency domain: phase correlation
  • 12.2.3 Refining by gradient: the Lucas–Kanade step
  • 12.2.4 What breaks it: peak-locking, texture, and noise
  • 12.2.5 One tool, everywhere downstream
• 12.3 Sparse matching
  • 12.3.1 Where to look: corners, and the structure tensor
  • 12.3.2 Invariance: surviving scale and rotation
  • 12.3.3 Describing a neighborhood: SIFT and its zoo
  • 12.3.4 Matching: nearest neighbor in descriptor space
• 12.4 Feature tracking
  • 12.4.1 Tracking vs dense flow: sparse-but-long vs dense-but-short
  • 12.4.2 KLT = Lucas–Kanade, per feature, iterated over time
  • 12.4.3 Good features to track = where the structure tensor is well-conditioned
  • 12.4.4 What breaks long-term tracking: drift, appearance change, occlusion, and re-detection
  • 12.4.5 Modern point trackers (briefly)
  • 12.4.6 An application: synthetic motion blur from a track
• 12.5 Robustness: the ratio test and RANSAC
  • 12.5.1 The ratio test: reject ambiguous matches before fitting
  • 12.5.2 RANSAC: fit from a minimal random sample, score by consensus
  • 12.5.3 Variants and degeneracy
• 12.6 Deep learning approaches to sparse matching
  • 12.6.1 Learned local features: SIFT's job, done by a network
  • 12.6.2 Learned matching: reason about the whole set at once
  • 12.6.3 The 3-D-aware turn: pointmaps subsume matching
• 12.7 Fast matching
  • 12.7.1 Approximate nearest neighbors for sparse descriptors
  • 12.7.2 PatchMatch: randomized dense correspondence by propagation
  • 12.7.3 Fast high-dimensional matching by random projection
• 12.8 Optical flow
  • 12.8.1 What optical flow is: and whether it is even well-defined
  • 12.8.2 Brightness constancy and the optical-flow constraint
  • 12.8.3 The aperture problem
  • 12.8.4 Lucas–Kanade: local constant-flow least squares (and the structure tensor)
  • 12.8.5 Horn–Schunck: global smoothness regularization
  • 12.8.6 Large motion: coarse-to-fine warping
  • 12.8.7 Learned flow: RAFT (neuralize the classical pipeline)
• 12.9 Deep learning approaches to optical flow
  • 12.9.1 The unrolling principle: neuralize the classical solver
  • 12.9.2 Cost volumes and warping inside the net
  • 12.9.3 RAFT and the recurrent update
• 12.10 Face tracking
  • 12.10.1 Detecting the face
  • 12.10.2 Landmarks: pinning down the features
  • 12.10.3 Tracking across time
  • 12.10.4 Lifting to 3-D: the morphable model
  • 12.10.5 Recognition, and the dark side
  • 12.10.6 Which library to use
• 12.11 Body pose estimation
  • 12.11.1 Top-down vs bottom-up
  • 12.11.2 On-device, real time
  • 12.11.3 Lifting to 3-D: parametric bodies
  • 12.11.4 Which library to use

▸ full collapsible outline of this part