12.2 Sub-pixel matching⧉
A burst can be misaligned by a fraction of a pixel. The true motion of a patch between two frames is almost never a whole number: it is 3.4 pixels, or −0.27, while a search over integer shifts can only report 3 or 0. Integer shifts leave edge residuals that blur a merge, so refine the best discrete match using the local cost or image derivatives.
It is tempting to treat this as a rounding nicety, but it is the opposite: in a great many methods the whole result lives in the fractional part. Burst super-resolution (Chapter 14.2, Multi-frame super-resolution) recovers detail only because it knows each frame's offset to a fraction of a pixel. Round those offsets to integers and the entire effect vanishes. Stereo depth is inversely proportional to disparity, so a one-pixel quantization of disparity turns a smooth slanted wall into a flight of discrete steps. Optical flow that snaps to integer motion jitters and crawls. The pattern that fixes all of them is one move, applied everywhere: match to the nearest pixel, then refine continuously around it. This chapter is the three standard ways to do that refinement, and the one bias that quietly corrupts all of them.
12.2.1 Refining the cost: fit a parabola⧉
The simplest and most common refinement reads the shape of the matching cost near its minimum. Brute-force matching gives you a sampled cost curve $C(d)$, such as the sum of squared differences or one minus normalized correlation, evaluated at integer offsets. The integer minimum is at some $d_0$; the true minimum lies between samples. If the cost is smooth and roughly quadratic near its bottom (it usually is, because SSD of a shifted patch is locally parabolic), you can recover the sub-pixel minimum by fitting a parabola through the lowest sample and its two neighbors and reading off the vertex (Figure 12.2.1):
Three cost values and one division give a fractional offset. It costs almost nothing, which is why it is the default in stereo and burst alignment. In 2-D you do the same thing along each axis (or fit a 2-D quadric to the $3\times3$ neighborhood of the minimum) to get a fractional $(\hat u, \hat v)$.
A three-sample parabola approximates the local objective. Its shape depends on scene texture, blur, sampling and the cost, not a universal triangular SSD peak. Check positive curvature for a minimum, reject a near-zero denominator and avoid extrapolating beyond the fitted neighborhood. Axis-wise fits also ignore mixed curvature in a two-dimensional cost.
A mismatch between the fitted model and the real peak biases the estimate, and the bias has a direction. Suppose the true cost is sharper than a parabola, close to a V, with its minimum a fraction $\delta$ of a pixel from the lowest sample. A parabola through the three samples then puts its vertex at $\delta/(2-2\delta)$ for $0\le\delta\le\tfrac12$: exact at $\delta=0$ and $\delta=\tfrac12$, and too close to the integer sample in between ($0.17$ instead of $0.25$). That pull toward the grid is the peak-locking described below. Using a model closer to the actual peak, such as a V-shaped (equiangular) fit for a sharp peak or a parabola on the logarithm of a Gaussian-like similarity score, reduces the bias; which one fits depends on the texture, the blur and the cost, so check it on synthetic shifts.
12.2.2 Refining in the frequency domain: phase correlation⧉
The second technique sidesteps the cost curve entirely and uses a fact from the Fourier domain: a shift in space is a linear phase ramp in frequency. If two image patches differ by a pure translation $\delta$, their Fourier transforms differ only by a phase factor $e^{-i\,2\pi f \cdot \delta}$. The magnitudes are identical, and all the shift information lives in the phase. Phase correlation extracts it: compute the cross-power spectrum (the product of one transform with the other's conjugate, normalized to unit magnitude), and its phase is exactly that ramp. Inverse-transform it and you get a sharp peak whose integer location is the whole-pixel shift; the slope of the phase ramp, fit across frequencies, gives the sub-pixel part directly, with no parabola and no interpolation of the image.
The robust modern recipe is the upsampled-DFT refinement of Guizar-Sicairos, Thurman & Fienup (2008) Guizar-Sicairos et al. 2008: locate the correlation peak to the nearest pixel cheaply with one FFT, then evaluate the cross-correlation on a finely upsampled grid only in a small neighborhood of that peak using a matrix-multiply DFT, evaluating the objective at a chosen fractional-pixel spacing without zero-padding the whole image. That grid spacing is not a guarantee of estimation accuracy. Phase correlation is global and texture-tolerant because it pools the shift evidence over the entire patch and is insensitive to illumination offsets, which is exactly why it shows up in whole-frame burst alignment (Chapter 12.1, Brute force); its limitation is that it assumes a single dominant translation, so it wants per-tile application on a scene with depth or independent motion.
12.2.3 Refining by gradient: the Lucas–Kanade step⧉
The third technique is the one that connects this chapter to the next: instead of searching for the shift, solve for it. Around the integer match, assume brightness constancy: the patch in frame two is the patch in frame one, merely displaced, and linearize: a small displacement $(\hat u,\hat v)$ changes the intensity by the image gradient dotted with the displacement. Setting the residual to zero over the patch gives the Lucas–Kanade equations, a $2\times2$ linear system in $(\hat u,\hat v)$ whose solution is the fractional motion that best cancels the difference between the two patches Lucas & Kanade 1981. Because the linearization is only valid for small motion, you iterate: solve for a fractional update, warp the patch by it, interpolating as in Chapter 6.5, Resampling and upsampling, and re-solve, converging on the true sub-pixel displacement in a few steps.
This is the same idea from a different entry point: the parabola fit reads the curvature of the cost, Lucas–Kanade reads the gradient of the image, approaching the same local quadratic from the data instead of the cost. It is the doorway to Chapter 12.8, Optical flow (per-pixel Lucas–Kanade) and to feature tracking (Chapter 12.4, Feature tracking, the KLT tracker is iterated Lucas–Kanade per feature), and it inherits their nemesis: where the patch has gradient in only one direction (an edge), the $2\times2$ system is singular and the displacement along the edge is unrecoverable. This is the aperture problem.
For a translation $d$, define residuals $r_i=I_2(x_i+d)-I_1(x_i)$ and rows $J_i=\nabla I_2(x_i+d)^\top$. A forward-additive Lucas–Kanade step solves
Use valid samples and nonnegative weights, test the small system for adequate information, and recompute the residual after the update. An iteration cap and a residual check complement the step-size stopping rule. Different gradient/template conventions require different update rules.
12.2.4 What breaks it: peak-locking, texture, and noise⧉
Sub-pixel estimates fail in characteristic ways, and the most insidious is peak-locking (also called pixel-locking): a systematic bias that pulls the estimate toward integer positions, so that a plot of estimated shift against true shift is not the clean diagonal you want but a staircase, flat near each integer and steep between (Figure 12.2.2). It comes from the model mismatch above, namely fitting a parabola to a non-parabolic peak, and it is pernicious precisely because it is invisible in any single estimate and only shows up as structured error across many. The cures are to match the fit to the true cost shape (a Gaussian peak model only when justified by the measured peak), to pre-filter so the signal is band-limited, and to use a better image interpolant (windowed-sinc rather than bilinear) inside any warping step, since bilinear interpolation itself injects a shift-dependent bias.
The other failure modes are the familiar ones of all matching. Low texture leaves the cost curve flat near its minimum, so the parabola's curvature, which is the denominator in the vertex formula, is tiny and the estimate is dominated by noise; this is the aperture problem again, now in the cost curve. Noise perturbs the three cost samples and hence the fit, with variance that scales inversely with the patch's gradient energy (the same structure-tensor quantity that decides whether a feature is trackable, Chapter 12.4, Feature tracking). And occlusion or non-translational motion violate the single-shift assumption outright, so robust pipelines test the refined match (does the warped patch actually agree?) and discard the ones that do not. The standard evaluation, used throughout the registration literature, is to shift an image by a known fraction of a pixel, recover it, and measure the residual. Its mean is the bias (peak-locking), its spread is the noise sensitivity.
12.2.5 One tool, everywhere downstream⧉
Sub-pixel matching is the quiet prerequisite the rest of the correspondence machinery assumes. The integer match localizes; the sub-pixel refinement provides most of the precision, and that precision is what matters in burst super-resolution (the offsets it fuses on), in stereo (the disparity it turns into depth), and in tracking and flow (the motion it accumulates without drift). Three techniques cover it: a parabola on the cost (cheap, ubiquitous, biased if you fit the wrong shape), phase correlation in the Fourier domain (global, texture-tolerant, single-shift), and the Lucas–Kanade gradient step (iterative, the doorway to flow). Remember one caution, peak-locking, and one discipline: recover a known shift and measure the residual, and you have the accuracy that Chapter 14.2, Multi-frame super-resolution and stereo depth are built on.