Page 171 -

150 3 Image processing

vertical horizontal shear vertical shear horizontal
upsample + upsample + downsample downsample

(a) (b) (c) (d) (e)

Figure 3.50 Four-pass rotation (Szeliski, Winder, and Uyttendaele 2010): (a) original pixel grid, image, and its
Fourier transform; (b) vertical upsampling; (c) horizontal shear and upsampling; (d) vertical shear and downsam-
pling; (e) horizontal downsampling. The general affine case looks similar except that the first two stages perform
general resampling.

leaving the rest of the face intact. 19 To perform such a transformation, different amounts of
motion are required in different parts of the image. Figure 3.51 shows some of the commonly
used approaches.
The first approach, shown in Figure 3.51a–b, is to specify a sparse set of corresponding
points. The displacement of these points can then be interpolated to a dense displacement field
(Chapter 8) using a variety of techniques (Nielson 1993). One possibility is to triangulate
the set of points in one image (de Berg, Cheong, van Kreveld et al. 2006; Litwinowicz and
Williams 1994; Buck, Finkelstein, Jacobs et al. 2000) and to use an affine motion model
(Table 3.5), specified by the three triangle vertices, inside each triangle. If the destination
image is triangulated according to the new vertex locations, an inverse warping algorithm
(Figure 3.47) can be used. If the source image is triangulated and used as a texture map,
computer graphics rendering algorithms can be used to draw the new image (but care must
be taken along triangle edges to avoid potential aliasing).
Alternative methods for interpolating a sparse set of displacements include moving nearby
quadrilateral mesh vertices, as shown in Figure 3.51a, using variational (energy minimizing)
interpolants such as regularization (Litwinowicz and Williams 1994), see Section 3.7.1,or
using locally weighted (radial basis function) combinations of displacements (Nielson 1993).
(See (Section 12.3.1) for additional scattered data interpolation techniques.) If quadrilateral

19 Rowland and Perrett (1995); Pighin, Hecker, Lischinski et al. (1998); Blanz and Vetter (1999); Leyvand, Cohen-
Or, Dror et al. (2008) show more sophisticated examples of changing facial expression and appearance.