The files in this directory contain the code necessary to implement
a morph (metamorphosis) sequence. The process is based on a mesh warping
algorithm introduced by Douglas Smythe for a special effect sequence
in the movie "Willow" in 1988. The algorithm, described in [Smythe 90]
and [Wolberg 90], has since been used in several films and commercials.
The self-contained code given here is adapted from a program listing
in [Wolberg 90].

The mesh warping algorithm is used to deform one image into another.
The input includes a source image I1 and two meshes, M1 and M2.
Mesh M1 is used to select landmark positions in I1, and M2 identifies 
their corresponding positions in the output image.  In this manner,
arbitrary points in I1 can be "pulled" to new positions. Although the
use of a (parametric) mesh might seem to place unnecessary constraints
on the positions of these points, a large class of useful transformations
is possible.  It is important, though, that the mesh not self-interesect
in order to avoid the image from folding upon itself.
The benefit of using a mesh derives from the simplicity in interpolating
the new positions of intermediate points (between the mesh points).
A bilinear or bicubic function can be used. We use a Catmull-Rom cubic
spline to implement bicubic interpolation here.

There are two executables that the user can compile: warp and morph.
They are created by typing "make warp" and "make morph", respectively.
In "warp", I1 is simply deformed based on the correspondence points
given in meshes M1 and M2. In "morph", a second image I2 is used to
designate the target image. Not only is I1 deformed, but it simultaneously
undergoes a cross-dissolve with a warped version of I2 to create the
illusion of a metamorphosis.
The user must specify the number of frames to generate in this transformation.
The basic idea is that each frame in the transformation uses an interpolated
mesh M3 as the set of target positions for the input mesh points.
M3 is computed by performing linear interpolation between respective
points in M1 and M2.
The "warp" program actually plays an important role here since both
I1 and I2 are each warped using M3 as the target mesh.
Thus, I1 is warped using meshes M1 and M3. In addition, I2 is warped
using meshes M2 and M3. Now that the landmarks of the source and target
images are aligned, they are cross-dissolved to generate a morph frame.

FILES:
Makefile:	dependency rules for creating "warp" and "morph"
meshwarp.h	header file
warp.c:		main function for "warp"
morph.c:	main function for "morph"
meshwarp.c:	workhorse mesh warping code
util.c:		image I/O and memory allocation functions
catmullrom.c:	Catmull-Rom cubic spline interpolation.
face.bw:	source image
cat.bw:		target image
face.XY:	source mesh
cat.XY:		target mesh

RUNNING THE PROGRAMS:
WARP:
After you type "make warp", an executable file called "warp" will
be created. You can invoke it by typing:
warp face.bw face.XY cat.XY out.bw

You may notice that the output has a distorted grid-like pattern on it.
This is not an artifact of the algorithm, but rather it is due to the
grid pattern that appears in the input after scanning it from a magazine.

MORPH:
After you type "make morph", an executable file called "morph" will
be created. You can invoke it by typing:
morph face.bw cat.bw face.XY cat.XY 10 out

This will create a 10-frame animation stored in files out_000.bw,
out_001.bw, out_002.bw, ... out_009.bw

COMMENTS:
This code works on grayscale images only. Extending the program to
handle 3 RGB color channels is straightforward.

The code is missing a program to help the user create and edit meshes.
A good mesh editor is a critical component to any mesh warping program.
That code is not given here because it falls outside of the scope of
this presentation. Instead, sample meshes face.XY and cat.XY are provided.

The reader should be aware that such an interface should allow the user
to control the cross-dissolve schedule at each mesh point, as well as its
position. This permits the intensities in different regions of the image
to interpolate at different rates.

REFERENCES:
[Smythe 90]
	Smythe, Douglas B., "A Two-Pass Mesh Warping Algorithm for
	Object Transformation and Image Interpolation," ILM Technical
	Memo #1030, Computer Graphics Department, Lucasfilm Ltd., 1990.
[Wolberg 90]
	Wolberg, George, "Digital Image Warping," IEEE Computer Society
	Press, Los Alamitos, CA, 1990.
