Why a fitted transform is not yet an image
A registration transform aligns coordinates; a display needs a value at each pixel of a new grid. If maps a moving-image coordinate to a fixed-image coordinate, the fixed-grid value at is obtained by pulling back: evaluate the moving image at . Forward-pushing each original pixel can leave holes or send several values to the same output pixel. Pullback presumes an invertible transform on the region considered; cropping and occlusion can still prevent correspondence. It also asks for values between samples, so one must choose an interpolation rule and an outside-image boundary rule.
Common mistake
(Pushing pixels forward instead of pulling the grid back)
Take the one-dimensional magnification and moving pixels . Pushing forward places their values at , so the output pixels receive nothing and must be patched afterwards. Pulling back assigns every output pixel a value: is read from , between the moving pixels and . Writing where is meant reads the wrong location, even when no holes appear.
Bilinear interpolation
Let four samples on a unit square be , and let denote the horizontal and vertical fractions from the lower-left corner. Bilinear interpolation gives
First interpolate horizontally on the bottom and top edges; then interpolate their results vertically. Reversing this order gives the same formula. The four weights are nonnegative and sum to one, so the result lies between the smallest and largest corner value. This bound relies on staying inside the square; extrapolating with a negative weight need not preserve it.
Common mistake
(Using the min–max bound outside the cell)
With corners , , and the point , the weights are and , which exceeds every corner value. Points beyond the cell must be assigned to the cell that contains them, or handled by the boundary rule; the formula of one cell is not a valid extrapolator.
Theorem 3.3.1
(Exactness for bilinear functions)
If the true continuous image on a cell has the form , its bilinear interpolant from the four corners is exactly everywhere in that cell. The interpolant is continuous across a shared cell edge when the two cells use the same samples on that edge; its first derivative need not be continuous across the edge.
Proof
(Exactness, edge continuity and a derivative jump)
The formula is linear in the corner data. Direct substitution shows that it reproduces each of on the unit cell: for instance has corner values , giving . Hence it reproduces every linear combination of them. Along an edge the weights of the opposite two corners vanish, leaving the same linear interpolation of the shared endpoints from either cell, so the values agree there. Continuity of derivatives does not follow: in one dimension the data at give slopes and on the two neighboring intervals. Using these same values on two equal image rows gives a two-dimensional example.
The derivative jump matters when registration optimizes an objective using image gradients: derivatives at grid lines may be undefined, and a smoother interpolant changes the objective.
Worked example 3.3.2
(A translated output pixel)
Suppose and the fixed output point is . Then . If the moving cell's corners are in the order , the result is . Sampling at instead would use a different location: the direction of matters.
At the image edge the inverse point may fall outside the stored array. Zero padding, clamping and periodic wrapping prescribe different values and may create different artificial edges. No interpolation rule recovers information hidden by occlusion or missing outside the field of view.
Worked example 3.3.3
(Three boundary rules at one edge point)
Consider one image row with stored values and an inverse point , halfway between the missing sample and . Linear interpolation gives , so everything depends on the rule for :
- zero padding, : the value is ;
- clamping, : the value is ;
- periodic wrapping, : the value is .
At an interior point such as all three rules give . The three answers at are modeling choices, not approximations of one true value.
Downsampling and finite Fourier aliases
A pyramid reduces the number of pixels to make large displacements easier to search. But selecting every other sample discards information. For a precise model let , be a complex periodic sequence of length , and define the unnormalized DFT and its inverse by
Theorem 3.3.4
(Two-to-one aliasing of factor-two subsampling)
Let , set for , and let be the length- unnormalized DFT of . For ,
Proof
(Inserting the inverse transform)
At an even index the inverse formula gives
Substituting into and exchanging the two finite sums,
The inner sum is a geometric series with ratio . If , then and the sum is . Otherwise and , so the sum is . For , the indices congruent to are exactly and . Hence , and .
Proof X-ray
Why two frequencies fold into one
The decisive move is the first line: at an even index the exponent equals , so frequency on the fine grid behaves as frequency on the coarse grid. Everything after that is orthogonality of the length- exponentials, which acts as a filter keeping the indices congruent to . The count of survivors uses exactly: two indices per residue class, hence the factor and the pairing . The inverse formula is an exact identity for any array of length , so no band-limit assumption on an underlying continuous image enters. Real values are never used, so the identity holds for complex data, and nothing is approximated: the folding is exact.
Consequently the coarse samples determine only the sum of each pair, not both original coefficients. A chosen retained index set must contain at most one member of each pair: for a real image it should also be closed under conjugate symmetry. If all discarded coefficients are known to vanish, the retained coefficient is twice its associated coarse DFT coefficient, and inverse transformation reconstructs that restricted original sequence. That is a conditional recovery result, not recovery of arbitrary data. At a cutoff frequency the convention must say which boundary bin is retained; a length- Nyquist bin is self-conjugate when is even, and special treatment of cutoff bins may be required to maintain real-valued symmetry.
Worked example 3.3.5
(Recovery depends on which partner is assumed zero)
Let , and . Then , so . The even samples are , with , and the theorem checks: , .
If the retained set is , so that is assumed, then , , and the inverse transform returns , the correct sequence. The sequence has the same even samples, and with retained the same returns it instead. The data cannot choose between them; the assumption does.
Edge case: the real sequence has , with both members of the pair nonzero. Every retained set with one member per pair returns a complex sequence, either or , so none recovers it.
Counterexample mode
Two different signals, identical coarse samples
For , the sequences and differ at odd positions. Yet . Their high and low frequencies become indistinguishable after subsampling. This ambiguity occurs even in exact arithmetic and without measurement noise.
Before subsampling, a low-pass filter can suppress the discarded member of each alias pair. An ideal periodic frequency mask that keeps a conjugate-symmetric set containing at most one member per pair eliminates those folded contributions, but removes the other coefficients; it does not recreate them. Gaussian smoothing attenuates high frequencies but is not an exact band limit. In two dimensions, downsampling both even-sized axes by two folds four frequency bins into each coarse bin and introduces a factor under the analogous DFT convention. Real photographs are finite and rarely periodic: filter boundary choices and truncation affect the result.
Concept lensGeometric
Interpolation and anti-aliasing answer different questions
Interpolation defines values between stored samples for a chosen model. Anti-alias filtering limits the high-frequency content before a coarser sampling grid is used. Bilinear interpolation alone does not guarantee that the effective filter removes all frequencies that would fold together.
Exercises and solutions
Quick check
(A cell has corner values in the order . Evaluate its bilinear interpolant at . Can it exceed anywhere inside the cell?)
Compute the four weights first.
Solution · Answer
The weights are , , and , giving . No value inside the cell exceeds : the weights are nonnegative and sum to one.
Quick check
(Let and . Compute the subsampled sequence and its length-two DFT, and compare the aliasing formula with the length-four coefficients.)
For length two, and .
Solution · Answer
and . The original DFT is , that is , so the formula gives and .
Quick check
(Take of length eight. What happens if one merely keeps even samples? What happens if the periodic two-point average is applied first?)
Evaluate at one even and one odd index.
Solution · Answer
Direct selection yields four ones, making a rapid oscillation appear as a constant. Averaging gives at every position, hence the coarse samples are zero. This filter removes this particular oscillation, not every potentially aliased frequency.