11.1 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.

11.1.1 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.

11.1.2 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.

11.1.3 Resampling: a quick reminder🔗⧉

Inverse warping leaves one question: read $\text{in}$ at the fractional coordinate $f^{-1}(x,y)$. An image stores only samples, so to read between them we reconstruct the continuous signal and re-sample it, or resample it, and the reconstruction filter is the whole choice: nearest neighbor (blocky, but the only safe option for label maps, where averaging classes is meaningless), bilinear (the smooth, cheap default, mildly soft), and bicubic / Lanczos (sharper, via a wider analytic kernel with small negative lobes, at the cost of a little ringing). This is exactly the reconstruction-filter machinery built in full in Chapter 6.5, Resampling and upsampling, in Part 6, Linear methods and Fourier analysis. The warp engine simply calls it at each output pixel, so we do not re-derive it here.

The one thing a warp must keep front of mind is the split between enlarging and shrinking. Upsampling reads more densely than the samples sit, so reconstruction uses its native source-scale support (a cubic kernel still spans several source samples). Downsampling throws samples away, and reconstruction alone aliases; detail too fine for the coarser grid folds down into bold false moiré. The fix is the discipline from BASIC restated for warps: prefilter before you downsample: area-average first, equivalently widen the resampling kernel in proportion to the downscale factor and renormalize so each output pixel gathers over its whole input footprint. Enlarging needs no prefilter; shrinking always does. This is big lesson L16 (placed in Chapter 6.5, Resampling and upsampling; the frequency-domain why, folding above the new Nyquist, is L6.8show, Chapter 6.3, Fourier), and it governs every geometric resample in this part: the shrinking corners of a rectification, a stabilization crop, optical-flow rendering. We lean on it throughout and flag it where it bites.

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

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),

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),

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.

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

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:

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.

11.1.6 Specifying the warp III: feature lines (Beier–Neely)🔗⧉

Some features are more naturally specified by lines than by points, such as an eyebrow, a jawline, or the edge of a roof. Feature-based field warping Beier & Neely lets the user draw pairs of directed line segments, before and after. For the backward lookup below, unprimed endpoints specify the destination segment and primed endpoints the source segment. Each segment pair sets up a local coordinate frame: a coordinate $u$ measured along the segment (normalized, $0$ at $\mathbf{P}$ and $1$ at $\mathbf{Q}$) and a coordinate $v$ measured perpendicular to it (in absolute distance units). For a single segment we inverse-warp: read a destination point $\mathbf{X}$'s coordinates $(u,v)$ in the destination frame and reconstruct the matching point in the source frame,

with $\perp(\cdot)$ the $90°$ rotation. A reported subtlety from the original work: $u$ scales with the segment (so a stretched feature carries its interior along) but $v$ is kept absolute. The authors tried scaling $v$ too and it looked worse. With multiple segments, each segment $i$ proposes its own displaced point $\mathbf{X}'_i$, and the final position is a distance-weighted average of those proposals, with weight

where $\ell_i$ is the segment's length (longer segments carry more authority), $d_i$ is the distance from the point to the segment (nearer segments dominate), and $a,b,p$ tune the falloff. This is the technique behind the morph in Michael Jackson's Black or White video and a perennial course project; it is built here and used in Chapter 11.3, Morphing (Figure 11.1.9⛶ fullscreen).

Figure 11.1.10⛶ fullscreen takes one output pixel through this computation, starting with a single segment.

With two segments, each proposes its own source point and the warp averages them.

The weights form a field over the whole output.

11.1.7 Liquify: brush-driven warping🔗⧉

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.