Lecture Notes 8 — Resampling and warping🔗⧉

Course notes cut from Computational Photography, an AI-powered Slopendium for this lecture. Each section links back to its home in the book; sections marked optional go beyond what the lecture needs.

Sampling, downsampling, and aliasing🔗⧉

A camera integrates light over each pixel’s spatial footprint and exposure interval, then records those measurements on a grid. We can model this as filtering followed by point sampling. The filtering reduces fine detail, but generally does not remove every frequency the grid cannot resolve. Resizing introduces another sampling step and another opportunity for aliasing. Chapter 6.5, Resampling and upsampling treats reconstruction between samples; here we examine the information lost or confused by the sampling grid.

Aliasing: a high frequency in disguise🔗⧉

Picture photographing a building's facade (rows of fine windows, or a striped shirt) and shrinking the result. Where the stripes are finer than the output pixels, they do not melt into a uniform gray; they reorganize into bold, wrong, low-frequency bands and swirls that are not in the scene at all: moiré. Intuitively, when a pixel must summarize detail it cannot represent, it ought to return the local average, a neutral gray. Instead, the leftover high frequency gets misread as a low one.

The clean case is a single sine wave (Figure 6.4.1⛶ fullscreen). Sample a high-frequency sine too coarsely (fewer than two samples per cycle) and the samples you collect fall into a pattern indistinguishable from a lower-frequency sine. The original travels in disguise as a different frequency; that impostor frequency is its alias. The damage is not blur (lost detail you could shrug off); it is corruption: energy that lands at the wrong frequency and masquerades as real structure. The same masquerade plays out in 2-D on a real photograph (Figure 6.4.2⛶ fullscreen): a facade's regular window grid is a high spatial frequency, and sampling it too coarsely without a pre-filter folds that grid down into bold, slow moiré bands that are not in the building.

In two dimensions, aliasing has a direction🔗⧉

optional

in the book↗

On a rectangular 2-D grid, aliasing folds each frequency coordinate by the sampling rate along that axis. A frequency vector can therefore change both length and orientation. A purely vertical grille does not acquire an arbitrary diagonal orientation on an aligned rectangular grid; both frequency coordinates and the grid geometry determine the alias.

A sharp slanted edge contains arbitrarily high frequencies perpendicular to the edge. Point-sampling it produces a staircase whose pattern depends on its position relative to the grid. Pixel-area integration softens the staircase, though a box footprint is not an ideal band limit. Rendering and image reduction use the same prefiltering principle.

For example, sample a sinusoid with frequency components 0.6 cycles per pixel horizontally and 0.2 vertically on an integer pixel grid. Subtracting one horizontal cycle per pixel changes its frequency vector to (−0.4, 0.2) without changing the samples: the phase difference at every integer horizontal coordinate is a whole number of cycles. The apparent orientation changes because the horizontal component has folded while the vertical component has not. A regular texture containing several frequency components can therefore produce moiré at orientations absent from the visible coarse structure of the original texture.

Sampling in the frequency domain: spectral replicas🔗⧉

optional

in the book↗

In the frequency domain the mechanism is vivid. Sampling on a grid is multiplying the signal by a comb of spikes, and multiplying by a comb in space replicates the spectrum: it pastes shifted copies of the signal's spectrum at every multiple of the sampling rate. If the original spectrum is narrow enough (band-limited below Nyquist), the copies sit side by side without touching and the original can be isolated. If it is too wide, the copies overlap, the tails fold back over the genuine low frequencies, and that overlap is aliasing. Seen this way the fix is obvious: band-limit the signal before you sample it. Run a low-pass filter (a blur) first, to delete the frequencies above Nyquist that would otherwise fold, then sample. This pre-filter (anti-aliasing) trades a little sharpness for the removal of false structure, and it is why a well-written image-shrinking routine blurs before it downsamples. The space-versus-frequency tradeoff returns: a perfectly sharp cutoff in frequency is a sinc spread out forever in space, so practical pre-filters compromise.

Figure 6.4.4⛶ fullscreen draws the multiplication in space first, then the replicated spectrum it produces.

💡 Big lesson (L6.14) — sampling replicates the spectrum; aliasing is the replicas overlapping🔗

Sampling on a grid is multiplication by a comb (a train of deltas), and a comb's Fourier transform is another comb, so sampling replicates the signal's spectrum at every multiple of the sampling rate. If the spectrum is band-limited below Nyquist the copies sit side by side and the original is recoverable; if it is not, the copies overlap, and the folded-over tails land on top of the genuine low frequencies as aliasing: energy appearing at completely wrong frequencies (moiré, the backward wagon-wheel). The cure is to band-limit before sampling: low-pass away everything above Nyquist first, then sample.

Seeing it: sampling and pre-filtering, hands on🔗⧉

The demos below show this directly. The first demo is the one-dimensional story (a single signal, your hand on the sampling rate), and the second is the two-dimensional one, the same physics on a real photograph where aliasing shows up as moiré.

The full sampling pipeline generalizes to two dimensions just as cleanly, and the spectral picture is the most revealing part: in 2-D, sampling replicates the spectrum on a whole lattice of copies, and aliasing is a copy drifting in to overlap the baseband.

The ideal reconstruction filter: sinc, and why it is unreachable🔗⧉

optional

in the book↗

For uniform spacing $T=1/f_s$, ideal reconstruction of a signal band-limited below Nyquist is

$$I(x)=\sum_{n=-\infty}^{\infty} I(nT)\operatorname{sinc}(x/T-n),\qquad \operatorname{sinc}(z)=\frac{\sin(\pi z)}{\pi z},\quad \operatorname{sinc}(0)=1.$$

Each sample contributes a shifted sinc. At the sample locations, every other sinc is zero. The infinite sum makes exact reconstruction impractical for a finite image. Practical kernels limit support and trade passband attenuation, stopband leakage, and ringing. Sharp low-pass filtering can overshoot an edge even before truncation; truncation is not the sole cause. Chapter 6.5, Resampling and upsampling develops the usable kernels.

💡 Big lesson (L6.15) — the ideal sampling filter is a sinc, which does not exist in practice🔗

Ideal band limiting and ideal interpolation use sinc kernels, scaled for their respective grids. Their infinite support requires approximation in finite computations. A finite filter trades computation and frequency selectivity; inspect both aliasing and edge overshoot.

Figure 6.4.9⛶ fullscreen puts the whole chain in one place, one column per step: the input, the prefilter, the samples, the reconstruction, and the reconstruction as a viewer perceives it.

Practical filters: from the box to bicubic and Lanczos🔗⧉

Downsampling needs a prefilter, and the previous section named the ideal one: a sinc scaled to the output spacing, whose transform is a box that keeps every frequency the coarser grid can hold and removes all the others. The sinc cannot be used as it is. It is infinitely wide, so every output pixel would read the whole image, and its lobes decay so slowly that truncating it changes its response, while its negative lobes overshoot at edges (Figure 6.4.10⛶ fullscreen). Every practical prefilter is therefore a finite kernel that approximates it. The crudest is the box: averaging each $q\times q$ block of pixels into one output pixel, the usual way to halve an image. Its transform is itself a sinc, which keeps only 0.64 of the signal at the new Nyquist frequency and lets through as much as a fifth beyond it. The tent and the Gaussian are smoother, and the cubics and the Lanczos windowed sinc come closest to the ideal. The same kernels, used at the input's spacing rather than the output's, reconstruct a continuous image from its samples, which is how upsampling uses them (Chapter 6.5, Resampling and upsampling), and the trade-offs below hold for both uses.

So every practical prefilter or reconstruction kernel is an approximation of sinc with finite support, balancing two competing evils that are clearest in the frequency domain (Figure 6.4.8⛶ fullscreen). A kernel that is too gentle loses medium frequencies (its response rolls off early and the image goes soft), while one too aggressive lets high frequencies alias: it leaks past the grid's limit and admits jaggies and moiré. Every kernel is a point on this blur-versus-alias tradeoff. The two famous families both live on it.

Lanczos is sinc literally windowed by a wider sinc:

over a support of $a$ samples on each side (and zero beyond, with $k(0)=1$). It hugs the ideal closely and looks crisp, at the cost of some ringing near strong edges, the surviving side-lobes of the truncated sinc (Figure 6.4.11⛶ fullscreen).

Bicubic uses a piecewise cubic polynomial: smooth, compact (four samples wide in 1-D), the standard default in image editors. It typically carries small negative lobes to the sides, and those are not a bug: they give the reconstruction a built-in mild sharpening (much like the unsharp mask) that makes upscaled images crisper. The cubic kernel is not unique: there is a family. Once you impose the natural requirements (the kernel should be symmetric, should be smooth where the cubic pieces meet, and should sum to one so it preserves brightness), a cubic still has two free parameters left. Mitchell and Netravali (1988) named them $B$ and $C$ (an open-access summary with the kernel formula is the Wikipedia article on Mitchell–Netravali filters); the result is a single piecewise cubic, supported over four samples (two on each side):

one cubic whose two knobs slide it between sharper and smoother. Three points of the $(B,C)$ plane are the canonical members worth knowing by name:

• $(B,C)=(1,0)$, the cubic B-spline: the smoothest member, all-positive (no negative lobes), and approximating rather than interpolating, so it visibly blurs;
• $(B,C)=(0,\tfrac12)$, Catmull–Rom: interpolating (it passes exactly through the samples) with pronounced negative lobes, so it looks sharp;
• $(B,C)=(\tfrac13,\tfrac13)$, Mitchell–Netravali: the balanced default, sitting between the two and chosen as a useful compromise among visible artifacts.

A separable 2-D kernel $k(x)k(y)$ generally treats axes and diagonals differently. The continuous Gaussian is both separable and radially symmetric; truncation on a square only approximates that symmetry. For a rectangular sampling lattice, ideal rectangular-band reconstruction uses a separable product of sincs. It is not radially symmetric. A circular passband has a radial jinc kernel and discards some frequencies allowed near the corners of the rectangular Nyquist region.

Mitchell and Netravali (1988) found their balance by running a perceptual study mapping which $(B,C)$ choices look best, charting where each lands among three failure modes: residual blur (too little negative lobe), ringing (ghost edges from too-strong negative lobes), and anisotropy (a visible preference for the horizontal / vertical / diagonal directions). A broad region of the $(B,C)$ map looks satisfactory, but different points suit different images, which is exactly why Photoshop and friends offer you a choice of bicubic ("bicubic smoother" for enlargements, "bicubic sharper" for reductions) rather than one fixed filter. There is no universally best answer, only a tradeoff you tune to the image: a slightly blurry original can afford a sharper kernel, a crisp one cannot.

Real software exposes exactly these kernel choices. Photoshop's Image Size resample menu lets you pick Nearest Neighbor, Bilinear, Bicubic, Bicubic Smoother (for enlargements), Bicubic Sharper (for reductions), and Preserve Details: the very box / tent / cubic family, and the smooth-versus-sharp bicubic tradeoff, turned into a dropdown (Figure 6.4.14⛶ fullscreen).

A separable kernel is cheap because a horizontal one-dimensional operation followed by a vertical one replaces a full two-dimensional neighborhood sum. The price can be directional behavior. Rotate a slanted edge while keeping the sampling grid fixed and compare the result: a square product footprint can treat the axis-aligned and diagonal cases differently. The continuous Gaussian shows that separability and radial symmetry can coexist, because the product of its two one-dimensional exponentials depends only on squared radius. A product of sinc kernels instead corresponds to the rectangular frequency region of the sampling grid. Choosing a circular footprint changes that region; it is not merely a more accurate implementation of the same filter.

Resampling and upsampling🔗⧉

Domain operations: moving pixels around🔗⧉

Recall the three families of image operation from Chapter 8.3, Tone point operations, sorted by what each output pixel is allowed to read. Resampling is the domain family: the underlying continuous image is remapped in position; discrete resampling generally blends its recorded colors. Formally a domain transform applies a function $f$ from the plane to itself (from $\mathbb{R}^2$ to $\mathbb{R}^2$) to the image's coordinates, with the rule that if the point $(x,y)$ carried color $c$ in the input, then $f(x,y)$ carries that same color $c$ in the output. The range (the colors) is untouched; only the domain (the coordinates) is remapped.

That one definition spans a huge amount of ground. When $f$ is a uniform scale it is resizing; a rotation straightens a horizon; an affine or perspective $f$ fixes keystoning or stitches a panorama; and a freely chosen $f$ is a warp: picture the image printed on rubber and stretched. The free-form case, including how a user even specifies such an $f$ (and the morphing it unlocks), gets its own Chapter 11.2, Antialiasing for complex transforms. Here we take $f$ as given and concentrate on the hard part shared by every domain transform: the new positions almost never land on the input grid, so we must invent values between the samples.

Start with scaling up🔗⧉

optional

in the book↗

Start with the friendliest case, scaling an image up, say by an integer factor $k$. The output has $k$ times as many pixels along each axis, so most output pixels sit between input pixels and have no value of their own: we have too few samples and must fill in the gaps. (Downsampling is the opposite complaint, too many input samples crowding into each output pixel, and, surprisingly, it needs a slightly different fix. Hold that thought; the machinery is almost identical.) Upsampling is the cleaner place to build intuition, so we begin there.

Figure 6.5.1⛶ fullscreen follows one small image through every method of this chapter, one stage per method; its first stage is the input itself.

The naive idea, and why it leaves gaps🔗⧉

Here is the instinct nearly everyone has first: loop over the input pixels, and for each one compute where it lands in the output and write its color there. To scale up by $k$, the input pixel at $(x,y)$ goes to output location $(k\,x,\ k\,y)$:

This is forward mapping: push each input pixel forward to its destination. It is intuitive, and it is broken. Scale up by $k=2$ and you write output pixels $(0,0),(2,0),(4,0),\dots$ while every odd-coordinate pixel is never touched: a regular lattice of black holes (Figure 6.5.2⛶ fullscreen, left). The output is mostly gaps, because spreading $N$ input pixels over $k^2 N$ output positions can fill at most $N$ of them: one cell of every $2\times2$ block, three left empty.

You might try to patch it with an inner loop that paints the little square between four placed pixels. That limps along for an axis-aligned enlargement, but the instant $f$ is a rotation the gaps stop being neat squares: they become slivers at odd angles, and "fill the gap" no longer has an easy shape. Forward mapping fights you. We need a different loop.

The second stage of Figure 6.5.1⛶ fullscreen runs this naive loop on a real image.

Loop over the output, use the inverse transform🔗⧉

The fix is to turn the loop inside out. Instead of pushing inputs forward, iterate over the output pixels (all of them, so none can be skipped) and for each one ask where did this come from in the input? That means applying the inverse transform $f^{-1}$ to the output coordinate and reading the input there:

For a scale-up by $k$ the inverse divides by $k$, so output pixel $(x,y)$ reads the input at $(x/k,\ y/k)$. Now every output pixel receives exactly one value and there are no gaps by construction. This is inverse mapping: loop over output pixels and use the inverse transform when it exists. An occlusion, a fold, or a location outside the source also needs an explicit visibility or boundary rule. It is the same "where-from, not where-to" reflex as the flip in convolution (to fill a destination, reach back into the source), and it is the single most important habit in this chapter. (Figure 6.5.2⛶ fullscreen sets the two loops side by side.)

There is one immediate wrinkle, and it is the real subject of everything that follows. Inverse mapping is clean, but $f^{-1}(x,y)$ lands at a fractional coordinate: $(x/k,y/k)$ is rarely an integer, and under a rotation it essentially never is. There is no pixel sitting at $(1.3, 4.7)$. So the genuine content of resampling is the question we have been circling: given the input samples, what value should we report at a position between them? Every method below is one answer.

Nearest neighbor🔗⧉

Round the fractional coordinate to the nearest sample and copy its value. At $1.3$, return $I[1]$; at $1.8$, return $I[2]$. Truncating the coordinate instead gives a different, biased convention. Nearest neighbor is appropriate for categorical labels and for deliberately showing the original pixels, but looks blocky on photographs.

It works and it is fast, but the result is conspicuously blocky: a whole range of fractional positions all snap to the same input pixel, so an upscaled image looks like fat rectangular tiles (Figure 6.4.16⛶ fullscreen, nearest panel), each input pixel becoming a hard $k\times k$ block. Occasionally that is precisely what you want (pixel art, or a debug view where you want to see the literal samples), but as a general-purpose resize it is the floor, not the goal. As the challenge for nearest neighbor: try upscaling a face by $8\times$ this way and watch it turn to mosaic. We do much better by interpolating between samples instead of snapping to one.

The third stage of Figure 6.5.1⛶ fullscreen replaces that scatter with a gather and rounds.

Linear interpolation, in 1-D first🔗⧉

Drop to one dimension, where the idea is cleanest. An image row is a 1-D array of values, and we want the value at $1.3$, between the samples at $1$ and $2$. The natural move is to blend the two neighbors in proportion to how close the query sits to each. At $1.3$ we are $0.3$ of the way from $1$ toward $2$, so

This is linear interpolation, and there is one detail that trips up everyone at first: the weights run opposite to the distances. The neighbor you are $0.3$ away from gets weight $0.7$, not $0.3$, because you want weight $1$ when you sit exactly on a sample and $0$ when you are a full step away. Say it back in words: take a weighted average of the two bracketing samples, weighting each by one minus the distance to it. Geometrically, the reconstructed signal is just the straight line connecting consecutive samples (Figure 6.5.3⛶ fullscreen).

Bilinear, in 2-D🔗⧉

In two dimensions we now have four surrounding samples (the corners of the unit square the query falls inside) and two fractional coordinates to interpolate against. The clean construction is to do 1-D linear interpolation twice: first along $x$, then along $y$ (Figure 6.5.4⛶ fullscreen). Blend the top pair of pixels horizontally to get one value, blend the bottom pair horizontally to get another, then blend those two results vertically with the $y$ fraction. The four corner weights come out as products of the $x$- and $y$-blend factors, which is exactly why this is bilinear: linear in each axis, but their product, not a single plane through all four points.

That last point is a real subtlety. Four arbitrary corner values do not in general lie on a flat plane, so a "purely linear" 2-D surface through all four simply does not exist. Bilinear sidesteps this by being linear separately in each direction (the product of two tents), which is well-defined and cheap. The resulting surface is doubly ruled: dead straight along every horizontal and every vertical line, yet curved overall, twisting into a saddle when the four corners disagree (Figure 6.5.5⛶ fullscreen). The only way to get a truly planar piecewise-linear reconstruction is to triangulate: cut each square into two triangles and interpolate within each, since three corners do fix a plane.

The next stage of Figure 6.5.1⛶ fullscreen applies bilinear interpolation to the whole image.

Choosing the diagonal of each cell from the data is data-dependent triangulation, introduced for image reconstruction by Yu, Morse and Sederberg (2001); the per-cell rule of the sidebar is the pixel-level version of Su and Willis (2004), and the fifth stage of Figure 6.5.1⛶ fullscreen runs it after bilinear.

Putting the two halves together (the inverse-mapping loop and the bilinear sample) gives the whole upsampler. Loop over output pixels, send each back through $f^{-1}$ to a fractional input location, split that into its integer cell and fractional offsets, and blend the four corners:

for each output pixel (x, y):
    (u, v) = f⁻¹(x, y)                  # fractional input location
    x0, y0 = floor(u), floor(v)
    s, t = u - x0, v - y0               # fractional offsets in [0, 1)
    top = (1 - s)·I[x0, y0]   + s·I[x0+1, y0]
    bot = (1 - s)·I[x0, y0+1] + s·I[x0+1, y0+1]
    out[x, y] = (1 - t)·top + t·bot     # blend the two rows vertically

Read it back: the two horizontal blends collapse the top and bottom edges of the cell, and the final vertical blend combines them: 1-D linear interpolation done twice. Bilinear is the workhorse default: cheap, no blocky tiles, smooth enough for most resizing, and the reconstruction you get for free from a graphics-hardware texture lookup (Figure 6.4.16⛶ fullscreen, bilinear panel). But it has a ceiling. The reconstructed surface has creases (it is only continuous, not smooth, kinking at every sample) and on a strong upscale it reads a touch soft. To push past it we need to look at more than four neighbors, and the "interpolate between neighbors" story does not generalize gracefully. We need a better lens, but first a word on what any of this costs.

The convolution perspective🔗⧉

Here is the more general formulation. So far we have described reconstruction as interpolating between neighbors. That picture is fine for linear interpolation and for upsampling, but it has two failings: it does not extend cleanly to fancier reconstructions, and it does not extend to downsampling at all. Since this whole chapter is fundamentally about (re)sampling, the Fourier-flavored view from Chapter 6.4, Sampling, downsampling, and aliasing has much better insight to offer. In practice that view means one thing: reconstruction is convolution.

Concretely, the output value at a fractional location is a weighted sum of nearby input pixels, with the weights read off a smooth analytical kernel $k$ centered at the desired (non-integer) location. Slide a continuous kernel so its center sits exactly on the query point $f^{-1}(x,y)$, evaluate the kernel at each surrounding integer input pixel to get that pixel's weight, and sum. The general resampling formula is

summing over input pixels $x'$ in the neighborhood, the kernel evaluated at the offset between the query and each pixel. In words: to find an output pixel, inverse-transform it to a fractional input location, drop a smooth kernel centered there, and accumulate kernel-weight times pixel-value over the nearby samples. It is convolution, but where convolution in the earlier chapter lived purely on the integer grid, here the kernel is a continuous function we can evaluate at any fractional offset (ask for $k(-0.7)$ and it answers), because the center is non-integer.

The resampler needs weights for fractional offsets. A formula for a real-valued argument supplies them, as do a lookup table or a bank of filters for quantized fractional phases. A list of integer-offset convolution taps alone does not specify interpolation between taps. Nearest neighbor’s box kernel is discontinuous, so continuity is not a requirement.

Bilinear is already a special case. The linear-interpolation weights $0.7$ and $0.3$ are exactly the values of a triangular (tent) kernel, one that is $1$ at its center and falls linearly to $0$ one sample away on each side, evaluated at the offsets to the two neighbors. So "interpolate linearly" and "convolve with a tent" are the same operation, seen two ways. Nearest neighbor is the same story with a box kernel (a flat $1$ over a one-pixel window). Once reconstruction is "convolve with a kernel," choosing a better reconstruction is just choosing a better kernel.

Figure 6.5.7⛶ fullscreen draws these kernels as 2-D kernels $k(x)\,k(y)$, each with its profile, an upsampling made with it, and its Fourier transform, starting with the box and the tent.

The box and the tent are the crudest kernels. Better ones, the Mitchell–Netravali cubics $k_{BC}$ and the Lanczos windowed sinc, are developed as approximations of the ideal sinc in Chapter 6.4, Sampling, downsampling, and aliasing, where they first serve as prefilters for downsampling. As reconstruction kernels they upsample with less blur than the tent and without the box's blocks, at the price of some overshoot near edges.

The third stage of Figure 6.5.7⛶ fullscreen draws any member of the family in 2-D, with its Fourier transform.

The sixth stage of Figure 6.5.1⛶ fullscreen upsamples with any member of this family.

Its last stage swaps the cubic for the Lanczos kernel, with order $a$ from 2 to 4.

The last stage of Figure 6.5.7⛶ fullscreen draws the Lanczos kernel the same way, for orders 2 to 4.

Upsampling vs. downsampling: scale the kernel🔗⧉

We have promised twice that downsampling reuses the same machinery; now we cash it in. Whether you scale up or down, you run the same convolution with the same family of kernels. The only thing that changes is how you scale the kernel.

When upsampling, the kernel keeps a fixed footprint in the input image (about four pixels wide for bicubic, however much you enlarge) because the input samples are already dense enough; you are just reading between them. So for upsampling the kernel width in input space is constant (a useful corollary: clamp the kernel's scale factor at $1$, never narrower).

Downsampling is the harder case, and not by a little. Pick one input pixel per output pixel (nearest neighbor, no blur) and you get aliasing: a fine texture turns into bold, wrong, low-frequency moiré (a brick wall or a striped shirt shot from far away dissolving into wide phantom bands; Figure 6.5.13⛶ fullscreen). This is not a cosmetic glitch but the wagon-wheel / Prudential-tower effect from Chapter 6.4, Sampling, downsampling, and aliasing: detail finer than the output grid can represent does not vanish, it folds down and masquerades as coarse structure.

Widen the filter in proportion to the reduction. In one dimension, let $q=W_{\mathrm{in}}/W_{\mathrm{out}}$ and $a_s=\max(1,q)$. A practical normalized resampler uses

The source coordinate is $u$. The sum covers the stretched kernel’s support. A fivefold reduction stretches a four-sample cubic support to twenty input samples, not five. Normalization preserves a constant image when the denominator is nonzero. Finite support still permits residual aliasing. How much depends on the kernel as well as its width. A box as wide as the reduction, the plain average of each block, is the most common prefilter and one of the leakiest: the sidelobes of its transform pass a fine periodic texture. Shrinking the facade of Figure 6.5.8 threefold, 88% of the energy that ends up in the output band is aliased with a box prefilter, against 9% with a Gaussian and 2% with Lanczos-3 (stage prefilter).

Pixel-center conventions also matter. With centers at integer indices and image edges at half-integers, use $u=(x+1/2)W_{\mathrm{in}}/W_{\mathrm{out}}-1/2$. This differs from aligning the first and last centers. Choose one convention and use it consistently when composing transforms.

Not every resize function widens it. Parmar et al. found that several widely used libraries reduce an image with a kernel of fixed width by default; Figure 6.5.12⛶ fullscreen puts that behavior beside the alternatives and traces the aliasing to the kernel.

The effect is ugliest on real, regular structure: the rows of windows on a glass facade, shrunk for a thumbnail, break into sweeping moiré if you decimate without prefiltering (Figure 6.5.13⛶ fullscreen).

Run the same experiment yourself in the interactive version below: one image, your choice of total angle and step size (the total is rounded to a whole number of steps), and any of five filters, and when you pick bicubic, the same $(B, C)$ handle from above to dial the cubic between blur and ring.

For a far deeper practical treatment of resampling filters, their windows, and the subtle quality differences between them, Nicolas Robidoux's analysis for ImageMagick is the reference worth reading (<https://usage.imagemagick.org/filter/nicolas/>); it is the kind of care that separates a library taking resampling seriously from one that ships a default and hopes.

Practical implementation choices🔗⧉

optional

in the book↗

For a reproducible resize, specify the coordinate convention, kernel and scale, boundary extension, processing domain, and alpha treatment. Check that a constant image stays constant, an identity transform reproduces samples for an interpolating kernel, and a fine pattern is adequately filtered during reduction. Compose successive transforms before sampling.

---

Warping🔗⧉

Print a photograph onto a sheet of rubber and stretch it: pinch a corner, bow the middle, slide one edge. The pixels glide to new positions and the picture rides along: a face slims, a bent line straightens, a tilted building stands up. Nothing about the colors changed; what changed is where each color lives. That is a warp, and it is the single operation underneath a large range of this book's geometry: lens-distortion correction, video stabilization, panorama reprojection, morphing, image-based rendering, even the cosmetic "liquify" slider. One primitive, reused everywhere, which is exactly why it opens this part.

Formally a warp is a map of the image domain: a function $f:\mathbb{R}^2\to\mathbb{R}^2$ that moves positions while leaving the range (the colors) untouched. If the input had color $c$ at $(x,y)$, the output has that same $c$ at $f(x,y)$. It is the geometric twin of a point operation: a point operation edits the range (the colors) and leaves the domain fixed; a warp edits the domain (the positions) and leaves the range fixed.

The map and the sampler have separate responsibilities. The map supplies coordinates; the sampler reconstructs values and filters the source footprint. A valid coordinate alone does not establish visibility or adequate antialiasing.

Warping is a domain transform: move where, not what🔗⧉

Hold onto the rubber-sheet image, because it is the correct mental model for every warp in the book, from a sub-pixel lens-distortion correction to a full perspective rectification to "slim the subject." The warp deforms where pixels live and leaves their colors alone. Contrast it once more with a tone or point operation, which recolors each pixel in place: warping is the domain operation to that range operation, and the two are orthogonal; you can do either without the other, and morphing (later in the part) does both at once, a domain warp plus a range cross-fade.

Before building the machinery, note why this one primitive is everywhere, because the motivation is the whole reason the chapter comes first. Optical-aberration and lens-distortion correction are warps. Video stabilization is a warp (a different one per frame). Panorama reprojection, aligning each photo to a reference view, fixing the apparent shift of a rotated camera, is a warp. Wide-angle distortion correction, morphable face models, image-based rendering, the cosmetic slim: all warps. Learn to transport pixels along a map once and you have the engine for all of them. That observation, that nearly every geometric operation in the book is "build a map, then move the pixels along it," is the part's central lesson L17.

Forward vs inverse warping: why output-driven wins🔗⧉

We met forward and inverse mapping for scaling in Chapter 6.5, Resampling and upsampling, and the conclusion carries over to any warp $f$. Pushing each input pixel to $f(x,y)$ leaves holes where the warp stretches and piles pixels up where it compresses. Looping over the output pixels instead, and pulling each one back through the inverse map,

fills every output pixel exactly once, and leaves a single question: how to read the input at the fractional location $f^{-1}(x,y)$ (Figure 11.1.2⛶ fullscreen).

for each output pixel (x, y):
    (x', y') = f⁻¹(x, y)               # pull back to the source location
    out[x, y] = resample(in, x', y')   # read in at the fractional spot

Forward splatting remains useful when only a forward map is known, as with optical flow, but it then needs explicit handling of holes and overlaps.

An invertible affine or projective map has a matrix inverse. A fitted map may be singular or poorly conditioned, however, and a free-form field can fold or leave gaps. Forward flow cannot generally be inverted by negating it at the same coordinates: corresponding vectors live at different locations. Estimate a backward field or invert/splat with explicit visibility and coverage handling. Occluded or newly exposed content has no valid correspondence.

One more practical point that is not a corner case: $f^{-1}(x,y)$ can land outside the input. You must pick a boundary policy: zero/black padding, clamp-to-edge (replicate the border pixel), mirror, or mark as undefined (transparent, via an alpha channel). This matters constantly, because rectification and stabilization both produce outputs whose corners read past the original image border. Reading off the edge is the common case, not the exception.

Specifying the warp I: parametric models and the degrees-of-freedom (DOF) ladder🔗⧉

optional

in the book↗

We have a transport engine; we now need maps $f$ to feed it. The easiest maps are parametric, low-parameter functions you fit to a handful of correspondences and then apply everywhere. They form a natural degrees-of-freedom ladder, each rung adding freedom and, in exchange, giving up a preserved property (Figure 11.1.3⛶ fullscreen).

At the bottom is translation (2 DOF), which preserves everything but absolute position. Add rotation and you get a rigid / Euclidean transform (3 DOF), which preserves lengths and angles. Add uniform scale and you get a similarity (4 DOF), which preserves angles and length ratios, that is, shape. Loosen further to an affine map (6 DOF),

$$ \begin{pmatrix} x' \\ y' \end{pmatrix} = A \begin{pmatrix} x \\ y \end{pmatrix} + \mathbf{t}, $$

which preserves parallelism and ratios along a line but no longer angles or lengths: straight lines stay straight, parallel lines stay parallel, and a square becomes a parallelogram. At the top of the practical ladder is the projective transform or homography (8 DOF),

$$ \begin{pmatrix} x' \\ y' \\ w' \end{pmatrix} = H \begin{pmatrix} x \\ y \\ 1 \end{pmatrix}, \qquad (x,y) \mapsto \left(\frac{x'}{w'},\, \frac{y'}{w'}\right), $$

which preserves straight lines only. Parallels may now converge to a vanishing point, and a square can become any quadrilateral. This is the rung that does genuine perspective, and it is the engine of the next chapter's rectification and of panorama stitching.

The homography looks non-linear in $(x,y)$ because of the division by $w'$, and that is exactly why we use homogeneous coordinates: in homogeneous coordinates it is a single $3\times3$ matrix multiply followed by the perspective divide, restoring linearity to the part that matters. A plane induces a homography between views even when the camera translates. Pure camera rotation also induces a homography, for points at any depth, provided the camera model is appropriate. These are two distinct reasons a homography can align images without a per-pixel depth map. We do not re-derive any of this here; the full development lives in FUNDAMENTALS: Pinhole, and the solve for $H$ from correspondences is built in Chapter 20.1, Manual panorama stitching from multiple views, whose homography machinery this chapter shares wholesale.

A nondegenerate affine fit needs three noncollinear point pairs; a homography needs four pairs in general position. Additional pairs support a least-squares fit, but outliers require rejection or a resistant objective. Normalize coordinates for a homography’s linear initialization, then evaluate geometric reprojection error. Chapter 12.5, Robustness: the ratio test and RANSAC develops the outlier handling.

The strengths and the limit are two sides of one coin. Parametric warps are global, smooth, and low-parameter, which makes them a good choice when the deformation really is rigid, affine, or projective: a flat surface, a rotating camera, a lens model. But by the same token they cannot express a local, free-form deformation such as a smile, a face morph, or a hand-drawn stretch of one limb. For that we need a field built from sparse, local control, which is the next section.

This is regression with the warp parameters as the unknowns. Each point pair contributes two coordinate equations. An affine fit is linear in its six parameters. A homogeneous linear initialization for a homography instead finds a null vector, commonly by singular value decomposition, before any geometric refinement. Counting equations explains the minimum number of pairs; checking their configuration explains why that count alone is insufficient.

Specifying the warp II: free-form warps from sparse correspondences🔗⧉

optional

in the book↗

When the deformation is local, the user supplies a sparse set of correspondences, such as a few control points or pairs of feature segments, and we must manufacture a dense warp field $f$, defined at every pixel, by interpolating those sparse constraints. Three constructions interpolate point controls, trading smoothness against locality: a triangulation, a grid of splines, and a thin-plate spline. Feature lines, which take segments instead of points, have their own section next, and a further idea layers a shape-preserving regularizer on top. The canonical reference across all of this is Wolberg's Digital Image Warping.

The simplest is the mesh / triangulation warp, which is piecewise-affine. Triangulate the control points (Delaunay, say); inside each triangle, the three vertex correspondences exactly determine an affine map (6 DOF, 3 points), so you warp each triangle by its own affine. It is fast, exact at the controls, and the standard morphing workhorse. Its weakness is that it is only $C^0$, continuous but creased, with derivative jumps at triangle edges, and its quality depends on how well the triangulation is chosen (Figure 11.1.5⛶ fullscreen).

A triangulation can be made smooth without giving up its locality. The classical answer comes from finite elements: the Clough–Tocher interpolant splits each triangle into three at an interior point, fits a cubic on each of the three pieces, and matches them so that the field and its first derivatives are continuous across every edge Clough & Tocher 1965. It still passes through the control displacements, needs a gradient estimated at each vertex, and is the standard smooth interpolant for scattered two-dimensional data. Subdivision is another route. Subdivision surfaces smooth a triangle mesh by splitting every triangle into four, again and again, and replacing each value by a local average of its neighbors; Loop's rules converge to a surface that is twice differentiable except at vertices with an unusual number of neighbors Loop 1987 (Loop subdivision). Applied in the plane, to a displacement or any other value stored at the vertices, the same rules turn the creased piecewise-affine field into a smooth one. Davis, Levoy and Durand used exactly this to blend the views of an unstructured light field: each captured view gets a weight of one at its own vertex of a triangulation of the viewpoints and zero at the others, and subdividing those weights gives smooth blending functions where barycentric weights would crease Davis et al. 2012. The catch is that Loop's scheme approximates rather than interpolates: the limit does not pass through the vertex values, so a dragged control point does not end up where it was dropped. That is harmless for blending weights and wrong for a warp, which needs either a sparse linear solve for the vertex values whose limits hit the targets, or an interpolating scheme. The butterfly scheme keeps every existing vertex and places each new one with a stencil of eight neighbors shaped like a butterfly, so its limit passes through the controls Dyn, Levin & Gregory 1990 (butterfly); a modified version extends it to meshes of any connectivity and makes it continuously differentiable everywhere Zorin, Schröder & Sweldens 1996 (modified butterfly). Figure 11.1.7⛶ fullscreen compares the four on one set of controls (view compare). A map of the warp's derivative shows ridges along the triangle edges for Clough–Tocher and butterfly, which are only once differentiable, and none for Loop. Unsolved, Loop's limit misses a dragged control by up to about five percent of the image width and shrinks the whole warp; solving for the vertex values removes the miss (view loop). The last view shows the light-field use: one vertex at one and the others at zero, piecewise linear against Loop (view weights).

The first morph in a feature film used a different kind of mesh, a grid with splines between its nodes. For Willow (1988), in which a sorceress changes through a series of animals back into a woman, Doug Smythe at Industrial Light & Magic wrote a two-pass mesh warp Smythe 1990 (two-pass mesh warping). The artist lays a regular grid of control points over the first image and moves its nodes onto the matching features of the second. The two meshes have the same topology, so node $(i,j)$ of one corresponds to node $(i,j)$ of the other, and nothing needs to be triangulated. Between the nodes the warp is interpolated with cubic splines (Catmull–Rom splines in Wolberg's description), not with flat triangles, so the field is smooth across the grid lines and shows none of the creases of a triangulation Wolberg 1990 (Figure 11.1.8⛶ fullscreen, stage grids). We follow the algorithm on a photograph in Figure 11.1.8⛶ fullscreen, one step per stage.

The warp itself is computed in two one-dimensional passes, following Catmull and Smith's separable scheme Catmull & Smith 1980. An intermediate mesh $M_I$ takes its $x$ coordinates from the destination mesh $M_1$ and its $y$ coordinates from the source mesh $M_0$. The first pass moves pixels only horizontally, from $M_0$ to $M_I$: a spline through each column of nodes gives, on every image row, the $x$ positions where the vertical grid lines cross that row in both meshes, and a spline through those crossings maps every $x$ of the row to its new position. The row is then resampled with a one-dimensional filter. The second pass does the same vertically, from $M_I$ to $M_1$ (Figure 11.1.8⛶ fullscreen, stages pass1 and pass2).

mesh_warp(img, M0, M1):                       # M0, M1: grids of node positions, same size
    MI = nodes with x from M1 and y from M0
    for each row y of the image:                          # pass 1: horizontal
        xs0 = x where each column of M0 crosses row y     # spline through that column's nodes
        xsI = x where each column of MI crosses row y
        g = spline through the pairs (xs0, xsI)           # 1-D map for this row
        tmp[y, :] = resample_1d(img[y, :], g)
    for each column x of tmp:                             # pass 2: vertical
        ysI = y where each row of MI crosses column x
        ys1 = y where each row of M1 crosses column x
        h = spline through the pairs (ysI, ys1)
        out[:, x] = resample_1d(tmp[:, x], h)
    return out

Each pass is a set of one-dimensional resamplings, which are cheap and easy to filter well, and this mattered on the computers of 1988. The separable scheme has a known weakness: where the warp rotates a region by a large angle, the first pass squeezes it into a sliver before the second pass expands it again, the bottleneck problem of two-pass warps. For a rotation by $\theta$ the first pass compresses the region to $\cos\theta$ of its width and the second stretches it back by $1/\cos\theta$. The decomposition itself is exact; the loss comes from resampling a squeezed image, and it grows quickly with the angle: on a portrait, about 1 gray level of error against a one-pass warp at 30°, 4 at 60° and 12 at 80° (stage compare, which also sets the grid warp beside triangles and bilinear cells). The grid lines also must not cross, or the one-dimensional maps fold over. For a morph, the node positions are interpolated, $M(t)=(1-t)\,M_0+t\,M_1$, both images are warped to $M(t)$, and the two warped images are cross-dissolved (Chapter 11.3, Morphing; stage morph).

A grid trades freedom for smoothness and speed. The artist must work within the grid's topology and often moves many nodes to describe one feature, an edge that runs diagonally across the cells for instance. That burden is what Beier and Neely's feature lines, below, set out to remove Beier & Neely 1992. Later spline methods kept the grid but freed the controls: a tensor-product B-spline grid can be fitted to scattered points or lines, with a coarse-to-fine hierarchy of grids that adds detail only where the constraints require it Lee, Wolberg & Shin 1997.

For smoothness without creases, the thin-plate spline (TPS), a radial-basis-function interpolant. Fit a field that passes through the control displacements while bending as little as possible:

$$ f(\mathbf{p}) = A\mathbf{p} + \mathbf{t} + \sum_i w_i\,\phi\big(\lVert \mathbf{p} - \mathbf{c}_i \rVert\big), $$

an affine "global" part plus a sum of radial basis functions centered at the control points $\mathbf{c}_i$. The thin-plate kernel $\phi(r) = r^2 \log r$ is the one that minimizes integrated second-derivative (bending) energy, giving the smoothest possible interpolant, with the literal physical analogy of a thin metal plate bent to pass through pins at the constraints. The weights $w_i$ (together with $A,\mathbf{t}$) come from a small linear system. The result is smooth everywhere, with no creases, but it has global support: every control point influences every pixel, so it can be less local than a mesh, and the solve costs roughly $O(n^2)$–$O(n^3)$ in the number of controls. It is the go-to for smooth medical and facial registration and for morphometrics, following Bookstein.

The catch shared by all these constructions is that interpolating positions alone lets shapes shear and squash unnaturally: drag one handle and an unconstrained fit will stretch and skew the whole region. The fix is a shape-preserving regularizer: as-rigid-as-possible (ARAP) Igarashi et al. 2005 or moving-least-squares (MLS) Schaefer et al. 2006 deformation, which keeps each local neighborhood close to a pure rotation so a dragged limb bends without stretching. That regularizer is important enough to get its own chapter: we defer it to Chapter 11.5, Shape-preserving warping and only flag here that plain position-interpolation is not shape-preserving.

Compose maps before resampling where possible. If forward maps are $f_1$ then $f_2$, the combined backward lookup is $f_1^{-1}\circ f_2^{-1}$. Repeatedly resampling the image adds blur and rounding. Test an identity map, an integer translation and an affine ramp; declare whether integer coordinates denote pixel centers.

For a thin-plate spline in two dimensions, a common basis is $\phi(r)=r^2\log r$ with $\phi(0)=0$. The radial coefficients need affine side constraints, such as $\sum_iw_i=0$ and $\sum_iw_i\mathbf c_i^\top=0$. Smooth interpolation does not guarantee an invertible map. Reject collapsed triangles or folded regions if the application requires one-to-one transport.

The constructions trade locality, smoothness and control against one another, and the choice usually follows from the input you have. A piecewise-affine mesh is fast and exact at the controls, and it suits a face morph where creases along triangle edges are tolerable. A thin-plate spline gives a smooth field from a few scattered points, at the price of global support, so every control moves every pixel. Beier–Neely suits controls that are naturally lines, such as the edge of a jaw or an eyebrow. When dragging handles must not shear or squash the content, use a shape-preserving warp (Chapter 11.5, Shape-preserving warping). A camera rotation, a plane or a lens model calls for a parametric fit by least squares instead. In every case the application step is the same: build the map, then inverse-warp and resample.

Liquify: brush-driven warping🔗⧉

optional

in the book↗

Everything this chapter built, a dense map $f$ authored from sparse local input, then applied by resampling, is exactly what you are doing when you push pixels around with Photoshop's Liquify tool (the cosmetic "slim the waist / widen the smile" slider in spirit). Adobe does not publish the algorithm, but its documented behavior is the standard mesh warp. Under the hood Liquify keeps an editable mesh over the image, which you can show on screen and save to disk, and each brush stamps a smooth, radially-weighted displacement onto the mesh vertices beneath the cursor: Forward Warp pushes them along the drag, Twirl rotates them, Pucker and Bloat pull them in or out. The displacements accumulate as you stroke, Freeze masks pin regions you want protected, and Reconstruct relaxes the field back toward the identity. Because the brush specifies where pixels go, it authors the warp in the forward direction; the picture you see is that deformed grid resampled with interpolation. This is the forward-vs-inverse and reconstruction-filter machinery of this chapter, now driven by a paintbrush.

Face-aware deformation can use detected landmarks as semantic handles for eye, mouth or jaw adjustments. The detector and deformation model both affect the result; similar controls do not establish that different software uses an identical mesh algorithm.

---

A deformation brush also makes the need for shape constraints visible. A position edit can bend a nearby architectural line or narrow a limb along with the intended feature. The operator must inspect the surrounding geometry, protect it with controls, or use a deformation model that penalizes the unwanted change. Chapter 11.5, Shape-preserving warping develops that last option.

Morphing🔗⧉

Two photographs of two different faces, and the goal is a film clip that turns one into the other, not as a cut or a fade, but a single face that becomes another, the way the dancers shapeshift through each other at the end of Michael Jackson's Black or White. The obvious tool is the cross-dissolve: at each in-between time $t$, set every output pixel to the linear blend of the two inputs,

Run it and the result disappoints in one very specific way. Halfway through, at $t=0.5$, you do not see a plausible single face. You see a ghost: four faint eyes, two noses, a doubled mouth, all translucent and superimposed. The blend is doing exactly what you asked, averaging colors at fixed pixel locations, but the two faces' features sit at different pixels. The left image's left eye lands on the right image's eyebrow; the right image's mouth lands on the left image's chin. Averaging colors across that misalignment double-exposes every feature.

The diagnosis is sharp, and it is the whole chapter. A cross-dissolve interpolates only the range, the color at each location. To get a believable in-between you must also interpolate the domain, the location of every feature, so that both pairs of eyes travel to the same place before you average them. Metamorphosis is what you get when you do both: warp each image so its features move toward a common intermediate shape, then cross-dissolve the now-aligned images. The one idea to hold is the separation of shape and color: interpolate where things are and what color they are as two independent linear blends, applied together.

A morph uses correspondences to create an intermediate shape, warps both inputs into it, and blends their appearance. The correspondence model is what prevents doubled features; a color blend alone cannot do that.

Why a cross-dissolve isn't enough: the ghosting motivation🔗⧉

The goal is to smoothly turn one image into another, where "smooth" carries a strong requirement: each in-between $I_t$ should look like a plausible single image, not a visible blend of two. A face becoming a face; one video keyframe becoming the next.

The naive attempt is cross-fading (a.k.a. cross-dissolve): linearly interpolate colors pixel by pixel, $\text{out}[y,x]=(1-t)\,I_0[y,x]+t\,I_1[y,x]$. This is the right idea for color (at $t=0$ you get $I_0$, at $t=1$ you get $I_1$, and the color glides linearly between), but it ignores position entirely.

It ghosts because the two images' features are not aligned: eyes, mouth, and silhouette sit at different pixels. Blending colors at fixed locations superimposes a left-image eye onto a right-image cheek, and the result is a translucent double exposure, four eyes, two mouths (Figure 11.3.1⛶ fullscreen). And you generally cannot repair this with a single global alignment. Translating, rotating, or scaling one image as a whole can register a couple of features at the cost of the rest, because two faces differ locally and non-rigidly: the jaws are differently shaped, the eyes differently spaced. No one rigid motion brings all the features into register at once.

So cross-fading interpolates only the range (color). A believable in-between demands that we also interpolate the domain, the location of every feature, and that is a warp, the missing half. The plan for the rest of the chapter: get a dense shape interpolation from sparse correspondence, and combine it with the color interpolation we already have.

Two interpolations: domain (shape) and range (color)🔗⧉

The cure has two knobs. Name them precisely, because the method is their product.

Range interpolation (color) is the cross-dissolve we already have: at a location $x$, blend the two colors,

a straight linear blend of pixel values.

Domain interpolation (location) treats a feature point as a vector and interpolates where it is. For a corresponding pair, a point $P$ in $I_0$ and the matching point $Q$ in $I_1$, the in-between location is

At $t=0$ the feature sits where $I_0$ put it; at $t=1$ where $I_1$ put it; in between it travels straight along the segment $PQ$ (Figure 11.3.2⛶ fullscreen). This is interpolation of the domain, the coordinate grid itself, as opposed to the color living on it.

To realize a domain interpolation as an image operation we warp: move pixels spatially while leaving their colors alone, $C'(x,y) = C\big(f(x,y)\big)$. In practice we use the inverse / backward map (for each output pixel, look up where it came from, $\text{out}(x,y)=\text{im}\big(f^{-1}(x,y)\big)$), so every output pixel is filled (no holes) and resampling is well-defined. This is exactly the engine of Chapter 11.1, Warping; morphing is one of its biggest customers, calling it twice per frame (once for each source image).

The morph in one line: interpolate the domain like a vector, then interpolate the range (color). A morph is the product of a shape interpolation and a color interpolation: two independent linear blends, applied together (Figure 11.3.2⛶ fullscreen).

The morphing recipe (combine both)🔗⧉

The inputs are the two images $I_0$ and $I_1$, plus sparse correspondences the user marks on both: matching line segments, or matching mesh vertices (which primitive is the next two sections). The output is a sequence of in-betweens $I_t$, $t\in(0,1)$. Each frame is built in four steps:

1. Interpolate the feature geometry to an intermediate shape: each corresponding pair (point, segment, or vertex) goes to its in-between location $P_t=(1-t)\,P_0+t\,P_1$.
2. Build two dense warp fields from the sparse pairs: one carrying $I_0$'s features onto the intermediate shape, the other carrying $I_1$'s features onto the same intermediate shape.
3. Warp both images to that common shape. Now $I_0$ and $I_1$ are feature-aligned: both pairs of eyes land on the same pixels, both mouths coincide.
4. Cross-dissolve the two warped images, $I_t=(1-t)\,\text{warp}(I_0)+t\,\text{warp}(I_1)$. Because they are now aligned, the blend is sharp, with no ghosting (Figure 11.3.3⛶ fullscreen).

A natural question is why warp both images, not just one. You could warp $I_0$ all the way onto $I_1$'s shape and dissolve, but then features would slide the whole distance while colors merely faded, and the early and late frames would be badly over-distorted (one image stretched to fit the other's geometry while still wearing its own colors). Meeting in the middle, with both images warped only partway, to the shared intermediate shape, keeps each warp small and symmetric, and is what makes the motion read as a single object transforming rather than one picture deforming into another.

The recipe interpolates both shape and color, and the endpoints prove it. At $t=0$ the intermediate shape equals $I_0$'s own shape, so the warp of $I_0$ is the identity, and the color weight on $I_1$ is zero: the output is exactly $I_0$. Symmetrically at $t=1$ the output is exactly $I_1$. The morph passes cleanly through both originals.

One cross-reference closes the loop. The correspondences here are user-specified and sparse: a person draws a few lines or drags a few vertices. The automatic, dense way to obtain correspondence between two images is Chapter 12.8, Optical flow, and that is precisely what frame-interpolation and slow-motion methods use to morph between video frames without any hand-drawn lines (Chapter 30.4, Frame interpolation and slow-motion synthesis).

Write the two backward maps from intermediate coordinates to the inputs as $b_{0,t}$ and $b_{1,t}$. Then

The tildes indicate reconstruction and footprint filtering. For radiometric blending use a common linear-light representation; encoded-value blending gives a different transition. Use masks where one input is invalid or occluded. With meshes, share connectivity across both inputs and the intermediate shape, and reject zero-area or flipped triangles. Matching endpoints does not guarantee valid geometry at every intermediate time.

Mesh / triangulation morphing (the alternative warp)🔗⧉

optional

in the book↗

The second way to get a dense warp swaps lines for a mesh of corresponding control points placed on both images (or a regular grid deformed to match features). Triangulate the points; each triangle in $I_0$ corresponds to the matching triangle in $I_1$.

The warp is then trivially local: within each triangle the map is a single affine (barycentric) transform, which is fast to evaluate and invertible when both triangles have nonzero area. The intermediate shape is the mesh with its vertices interpolated to $P_t=(1-t)P_0+tP_1$; warp each source by its per-triangle affine onto that mesh, then cross-dissolve. Spline and free-form mesh variants (Wolberg's Digital Image Warping; multilevel free-form warps) trade the piecewise-affine creases at triangle edges for a smoother field.

Field versus mesh, the trade-off (Figure 11.3.6⛶ fullscreen). A mesh warp has local support: moving a vertex disturbs only its incident triangles, which makes it fast, predictable, and free of the far-line fights that plague field warps, but the control net is fiddly to author, and triangle edges can crease if the triangulation is poor. A field (Beier–Neely) warp has global, line-based control that is sparse and intuitive to draw, but it is slower and can fold. Same job: turn sparse correspondence into a dense warp, checking separately for folds and degeneracy, expressed in two different bases (a triangulation versus a set of influence lines).

Either way, the warp is a domain transform that must reconstruct and prefilter as it resamples (minified regions averaged down, magnified regions smoothly interpolated up), exactly the elliptical weighted average (EWA) Heckbert 1989 / mip machinery of Chapter 11.1, Warping. Because a morph stretches some regions hard while crushing others, it is a genuine stress test for good resampling: cut corners on the prefilter and the in-betweens alias and shimmer.

View morphing: the geometrically-correct in-between of two views🔗⧉

optional

in the book↗

There is a case where the flat 2-D morph above is silently wrong. Suppose $I_0$ and $I_1$ are not two arbitrary pictures but two photographs of the same 3-D scene from different viewpoints, such as a face rotating between two camera angles. A naive linear morph then bends straight lines and shrinks the object: the in-between is not a valid view of any rigid scene (Figure 11.3.7⛶ fullscreen). The reason is fundamental. Linearly interpolating image positions is not the same as interpolating the underlying 3-D geometry. A straight edge in the world projects to a straight line in both photos, but the midpoint of its two image projections is generally not where that edge would project from an in-between camera; the linear average cuts a chord across the true projective path, so straight lines sag and the silhouette pinches inward.

The fix, due to Seitz and Dyer (1996) in View Morphing, restores physical validity with three steps:

1. Prewarp both images by homographies that rectify them to a common plane, so the two image planes become parallel and corresponding epipolar lines are horizontal and aligned (the same rectification used in stereo).
2. Linearly interpolate the now-rectified images, a plain morph. But in this rectified frame the linear interpolation is geometrically correct, because corresponding points are constrained to move along aligned scanlines, so averaging their positions tracks the true motion.
3. Postwarp the interpolated result by an interpolated homography to the desired in-between view.

Under rectified equal-intrinsic cameras translated parallel to their image planes, a fixed visible 3-D point moves linearly in image coordinates along the baseline. This is the special geometry exploited by view morphing Seitz & Dyer 1996. It does not imply that every camera motion admits a plain linear image blend. Correspondences, visibility and the pre/postwarps still determine whether the interpolated view is valid.

The connection outward is direct. View morphing needs corresponding points between the two views and the epipolar geometry relating them: exactly the correspondence problem of Chapter 12.8, Optical flow and stereo. Supply that correspondence densely and automatically and you can synthesize in-between views with no hand-drawn lines at all: the bridge from morphing to image-based rendering, and to flow-driven frame interpolation (Chapter 30.4, Frame interpolation and slow-motion synthesis), where the two "views" are simply adjacent video frames.

Recap: big lessons in this lecture🔗

💡 Big lesson (L6.13) — Nyquist–Shannon: sample above twice the highest frequency, or it aliases🔗

Sample above twice the highest retained frequency. If the signal is too detailed for the grid, low-pass it before sampling. This applies to space and time. Real prefilters have finite transition bands, so allow a margin below Nyquist and check residual aliasing.

💡 Big lesson (L6.14) — sampling replicates the spectrum; aliasing is the replicas overlapping🔗

Sampling on a grid is multiplication by a comb (a train of deltas), and a comb's Fourier transform is another comb, so sampling replicates the signal's spectrum at every multiple of the sampling rate. If the spectrum is band-limited below Nyquist the copies sit side by side and the original is recoverable; if it is not, the copies overlap, and the folded-over tails land on top of the genuine low frequencies as aliasing: energy appearing at completely wrong frequencies (moiré, the backward wagon-wheel). The cure is to band-limit before sampling: low-pass away everything above Nyquist first, then sample.

💡 Big lesson (L6.15) — the ideal sampling filter is a sinc, which does not exist in practice🔗

Ideal band limiting and ideal interpolation use sinc kernels, scaled for their respective grids. Their infinite support requires approximation in finite computations. A finite filter trades computation and frequency selectivity; inspect both aliasing and edge overshoot.

💡 Big lesson (L6.16) — a resampling / anti-aliasing filter trades the ideal sinc against compact support🔗

Fourier analysis says the perfect reconstruction and anti-aliasing filter is the sinc, a perfect box in frequency. But the sinc is infinitely wide and rings when truncated, so no real filter can be it. Every practical kernel (bilinear, bicubic, Lanczos) is a deliberate compromise between approximating that idealized sinc (what Fourier wants) and staying compactly supported (what computation, and ringing, demand): reach wider and you approach sinc; truncate harder and it gets cheaper and less ringy but further from ideal.

💡 Big lesson (L6.17) — choosing a resampling filter trades passband droop against stopband leak🔗

Read off the frequency response, the same compromise is a tug-of-war between two errors. Passband droop: a too-gentle filter attenuates frequencies below Nyquist that the grid could have represented, so the image goes soft. Stopband leak: a too-aggressive filter lets frequencies above Nyquist through, which alias into jaggies and moiré. A good kernel sits at the sweet spot (flat passband up to Nyquist, sharp rejection beyond) and box, tent, bicubic and Lanczos are just different points on this droop-versus-leak curve.

💡 Big lesson (L6.18) — bicubic (and friends) are convolution with a fixed kernel, not polynomial regression🔗

The cubic-convolution filters used here evaluate a fixed piecewise-cubic kernel at fractional offsets and sum weighted samples. They do not solve a regression for every output pixel. Other methods also called bicubic interpolation use polynomial or spline constructions; the name alone does not identify the algorithm or its downsampling behavior.

💡 Big lesson (L6.19) — resample by gathering, rarely by scattering🔗

Loop over output pixels and pull back through $f^{-1}$ to find where each one reads from. Gathering fills every output exactly once; scattering pushes input pixels forward and leaves holes whose shape depends on the transform, a lattice of gaps under a scale and tilted slivers under a rotation. The same reflex governs warping, morphing, texture mapping, and flow-based reprojection later. Scattering earns its place only when the forward map is the thing you actually have, as in splatting a point cloud, and then it needs an explicit accumulation and normalization pass.

💡 Big lesson (L6.20) — every resampling pass multiplies the spectrum again, so resample once🔗

Repeated resampling accumulates blur, ringing, and sampling error. For repeated fixed convolution the frequency response is exactly $H^N$; for rotations it is only an illustration because the grid and effective filter change at each pass. Compose geometric transforms and resample the original once.

💡 Big lesson (L17, recurrence)

Almost every geometric algorithm in the book has the same two-part shape: first establish a coordinate map between two images (or between an image and a target frame), then transport the pixels along it. This part builds that machinery and its first uses: warping makes the map explicit and applies it, perspective rectification solves the map (a homography) from geometric constraints, and morphing interpolates between two maps. The same shape recurs across the book: panorama stitching estimates the map from matched features (in the multiple-exposure part), optical flow estimates a dense map from brightness constancy (in the matching part), and stabilization smooths a map over time while frame interpolation renders along one (in the video part). Separating the two halves, what the map is versus how you transport pixels through it, is what lets one transport engine (inverse warp + resample, built in the next two sections) serve this part and recur throughout the book; only the map changes from task to task. (L17 is registered in the part introduction, Warping and morphing; this chapter is the transport engine, and the chapters that follow are different ways of finding the map.)

💡 Big lesson (L17, recurrence)

A morph is a correspondence field plus transport, then a blend. To interpolate between two images you cannot average their colors where they sit; you must first establish a correspondence between their features, transport (warp) both images along that correspondence to a common intermediate shape, and only then blend. Separating the manipulation into a domain part (the warp: where features are) and a range part (the color blend: what they are), and interpolating each linearly, is what makes the in-between read as one object transforming rather than two pictures fighting. The same three-part shape (correspond, transport, blend) drives panorama de-ghosting, multi-frame super-resolution's sub-pixel alignment, and flow-driven frame interpolation; the only thing that changes is how the correspondence is obtained (here, sparse user lines; in Chapter 12.8, Optical flow, a dense automatic field).

💡 Big lesson (recurrence) — align before you blend

Averaging two images only makes sense once their features sit at the same place. A plain cross-dissolve blends colors at fixed coordinates, so any misalignment double-exposes into a ghost; the cure is always to warp into correspondence first, then average. You have already met this move under other names: panorama de-ghosting registers overlapping frames before feathering them, and multi-frame super-resolution aligns sub-pixel-shifted shots before merging (cross-ref Chapter 20.3, Blending). Morphing takes the lesson to its limit: it interpolates the alignment itself smoothly over $t$, rather than aligning once. The dense, automatic aligner that makes this work without hand-drawn lines is Chapter 12.8, Optical flow.