Programming Assignment 1: Morphing

Due 11:59pm, 31 January 2001

Computer Graphics 2, 15-463, Carnegie Mellon University
Revision 1: 21 Jan. 2001

Overview

In this assignment you will produce a "morph" animation of your face into another student's face. Each of you will generate two seconds of animation, which we will record onto video for you. The final video will thus be a metamorphosis through each of the faces in the class.

A morph is a simultaneous warp of the image shape and a cross-dissolve of the image colors. The cross-dissolve is the easy part; controlling and doing the warp is the hard part. The warp is controlled by defining a correspondence between the two pictures. The correspondence should map eyes to eyes, mouth to mouth, chin to chin, ears to ears, etc., to get the smoothest transformations possible.

The class directory, which we will abbreviate classdir henceforth, is /afs/andrew.cmu.edu/scs/cs/15-463. Your directory for this assignment is classdir/students/your_login/a1, and we call this a1dir.

We will give you a starting image ("picture A") and an ending image ("picture B") for your animation sequence. On 23 Jan. we will be taking pictures of students in the class, at the end of lecture. If you get your picture taken by us then picture A will be your face. Picture B will be another student or other primate. You will find these pictures in a1dir/a.tif and a1dir/b.tif. (Until those are set, you can experiment with pictures in classdir/pub/src/a1/medit/test).

You'll morph still picture A into still picture B and produce 61 frames of animation numbered 0-60, where frame 0 must be identical to picture A and frame 60 must be identical to picture B. In the video, each frame will be displayed for 1/30 of a second.

There are a variety of different methods you could use to do your morph. The recommended method is the Beier-Neely algorithm described below, or if you're more adventurous and you're interested in extra credit you might try a method of your own invention. Regardless of which method you use the work typically divides into two parts: writing a program to perform the morph given the correspondence, and using an interactive program to define the correspondence. Below, we first summarize the adventurous options, then we explain the Beier-Neely method.

Other Morph Methods

There are many options here: you could choose from one of the following or invent an algorithm of your own:

Triangulated Piecewise Affine Warp. Specify the correspondence in terms of pairs of corresponding points in pictures A and B. Triangulate the points in picture A, use a triangulation with the same topology (connectedness) in picture B. This defines corresponding triangles. Now use an affine warp for each triangle, as discussed in lecture. The trickiest part to implement is probably the triangulation. The easiest way to do this is to have the user define it interactively; harder but slicker would be to use Delaunay triangulation (see a computational geometry book). You could probably use our medit program, described below, to create the corresponding points.
Piecewise Affine on a Grid. This is a simpler variant of the above. Instead of defining the correspondence with a general triangulation, use a grid (a network of quadrilaterals, where each internal vertex has four edges). Split each quadrilateral into two triangles. The topology of the triangulation becomes trivial. In this case you'd have to write your own interactive grid editor (not too hard).
Piecewise Cubic on a Grid. This is the high class variant of the previous. Instead of piecewise linear over triangles, use piecewise cubic over squares in the destination image. This would be simple to do if we always had quadrilaterals of the source image mapping to squares of the destination, but we don't; we have quads mapping to quads. Therefore I think this method is rather tricky.
Relaxation. Relaxation means that you smooth out the mapping grid to make it interpolate specified correspondence points. For now, let's call destination coordinates (x,y) and source coordinates (u,v). As diagrammed in lecture, if you think of the mapping functions u(x,y) and v(x,y) as height field surfaces, we want to find a smooth surface that interpolates (passes through) specified correspondence points {x[i],y[i],u[i],v[i] for i=1..k}. These points are called constraints. If your picture is nx*ny pixels, create arrays (or "grids") U[x,y] and V[x,y]. Freeze U[x[i],y[i]]=u[i] etc for all time, but for all other pixels in the 2-D array, "relax" their values to the average of their four neighbors. Do this repeatedly. (This converges to a solution to Poisson's equation -- Laplacian equals zero except at constraint points). If you do all your work on an nx*ny resolution grid, it will be too slow, so instead create a set of grids of size 2*2, 4*4, 8*8, ..., 2^r*2^r, where max(nx,ny)<=2^r. Map the constraints to each of the coarser grids. Solve the problem in a coarse-to-fine progression, relaxing on each grid until it converges to a solution (stops changing much), then interpolate the solution on the coarser grid to the finer grid, and repeat until you get up to full resolution. See the paper by Litwinowicz in the Proceedings of SIGGRAPH 94 (I have a copy if the E&S library doesn't).

If you plan to attempt one of the above methods, it would be wise to start early, and feel free to ask for help.

Follow the "what to submit" instructions under Beier-Neely below, except you should write up a brief description of how your algorithm works, and if you don't use medit, in place of item 3, include any data files that are involved.

Beier-Neely Morph Method

Alternatively, you can implement the algorithm described in the paper: Thaddeus Beier and Shawn Neely, "Feature-Based Image Metamorphosis", SIGGRAPH '92 Proceedings, pp. 35-42, which we have provided. Read it, whether you're implementing this method or not.

Your job will consist of two parts: writing a program to perform the morph given the correspondence, and using our interactive medit program to define the correspondence.

Part 1: Write morph

Write a program called morph which, when run with the arguments:

morph picA picB linesfile warpfrac dissolvefrac morphpic

will read picture files picA and picB, line segment file linesfile, and warp between A and B by warpfrac, and cross-dissolve by dissolvefrac, writing the resulting picture to picture file morphpic.

You should use the TIFF picture file format. As discussed on the software web page, we are supplying a subroutine library libpicio for reading and writing TIFF files. See the macro PIC_PIXEL in classdir/include/pic.h.

The line segment file linesfile contains a list of line segment pairs for pictures A and B, plus three parameters at the beginning of the file. Our morph editor will write out this file, but your code will need to read the file. The format is ascii:

a b p n
P_1Ax P_1Ay Q_1Ax Q_1Ay P_1Bx P_1By Q_1Bx Q_1By
P_2Ax P_2Ay Q_2Ax Q_2Ay P_2Bx P_2By Q_2Bx Q_2By
...
P_nAx P_nAy Q_nAx Q_nAy P_nBx P_nBy Q_nBx Q_nBy

where n is the number of line segment pairs, and the parameters a, b, and p are explained in the paper. The ith line segment pair consists of the line segment in picture A between points (P_iAx,P_iAy) and (Q_iAx,Q_iAy), and the line segment in picture B between points (P_iBx,P_iBy) and (Q_iBx,Q_iBy). Coordinates in the file are normalized to the range [0,1], so you will need to multiply the x's by the width of the pictures and multiply the y's by the height of the pictures. (0,0) is the upper left.

For example, the following lines file contains two line segment pairs, and defines a correspondence involving a 90 degree rotation:

.01 2 .2 2
0 0 1 0 1 0 1 1
0 0 0 1 1 0 0 0

This is a short example. A typical lines file to specify a good morph might require 40 line segment pairs or so. See figures 7-11 of the paper.

The parameters warpfrac and dissolvefrac control warping and cross-dissolve, respectively. They both lie in the range [0,1]. They are the only parameters that will vary from frame to frame in the animation. For your starting frame, they will both equal 0, and for your ending frame, they will both equal 1. When you produce the final frame files, you will want them to be equal for all frames, but during debugging of your morph program, it can be helpful to have independent control of these two parameters.

Your morph program will need to perform the following (conceptual) steps:

Read in two picture files and one lines file.
Compute "destination" line segments by linearly interpolating between PQ_iA and PQ_iB by warpfraction. These line segments define the "destination shape".
Warp picture A to the destination shape, computing a new picture. We'll call the result "Warped A".
Warp picture B to the destination shape, computing a new picture. We'll call the result "Warped B".
Cross dissolve between Warped A and Warped B by dissolvefrac.
Write the resulting picture to a picture file.

In the warping steps (3 & 4), do bilinear interpolation, as described in lecture, so that the resampled picture won't appear blocky. Note that steps 3-6 can be combined into one pass; the list above is a list of conceptual steps.

The morphpic that you write out should have the same size in pixels as picA and picB.

Part 2: Design and generate your piece of the animation

The second part of the assignment involves designing your piece of the animation by running our medit program to specify the correspondence between pictures A and B, and then generating your animation.

As of 21 January, medit runs on Suns (and SGI's) only, not on the Linux machines. But we expect to release versions that run on Linux PC's in a few days. (In the meantime, you can work on part 1.) medit seems to work best on the Suns with 8-bit color in Wean 5202/4. It also works on the 24-bit Suns in 5201, but the colors look strange.

medit is an program that lets you interactively create, move, and delete line segments, and at the push of a button it will run your morph program (by forking off a process) so you can preview still frames from your animation. Sliders in medit allow you to control the morph fractions. To run medit, give it the name of your two picture files: "medit picA picB". It can read either TIFF or PPM picture files. After editing the line segments to your satisfaction, hit the Save Lines File button to save them to a file. Use the filename morph.lines for the line segments that you use for your final animation. See the medit documentation.

The parameters a, b, and p affecting the correspondence are described in the paper. If you find that the picture is not going where you tell it (e.g. the eyes aren't lined up, even though you've placed line segments on them), it could be because a is too large, b is too small, or p is too large. We recommend the default settings: a=.01, b=2, and p=.2.

If your morph program is not working, or you want to compare its results to that of a "correct" morph program, choose Algorithm: Their Morph button and the official morph program will be used.

You can generate frames by setting up your morph and morph.lines files and running the shell script classdir/pub/shell/genanim, which writes out picture files into your a1dir/anim directory. Various programs can be used to preview your animation, including common Andrew tools such as animate, or the xplay program, which we wrote specifically for this purpose. (On SGI's, try dmconvert and movieplayer).

xplay reads a sequence of TIFF or PPM picture files and displays them in quick succession using X Windows. Run "xplay -" for more info. You can find medit and xplay in classdir/pub/bin.

Note that generating your final frame files could take an hour of CPU time, so LEAVE YOURSELF SEVERAL HOURS BEFORE THE DEADLINE TO COMPUTE YOUR FRAMES. These files will be big, so be aware of your disk quota.

What to Submit

A correct submission consists of four parts that should go in a1dir.

Source code to your morph program.
61 frames with filenames anim/f00.tif, anim/f01.tif, ..., anim/f60.tif. These frames must be generated by your morph program (we will check this).
morph.lines, the line segment file from which you generated your frames.
A file named README containing a brief summary of the contents of your source files (a line or two each should do) and any comments to us that you'd like to make about problems you had or extra things you did, if any. Please also tell us how long your morph program takes to run per frame (seconds) and what machine type you ran on (be specific, e.g. "Dell GX300/700s running Linux" or "Sun in Wean 5201").

Submissions that don't conform to the above instructions (e.g. frame files with a different naming convention) will be penalized.

We'll do demos during our class period on Thursday 1 Feb., in the Wean cluster, at which we will want to see your completed frames, your running morph program, and your code.

Tips

Running morph at full resolution will probably take a few seconds to several minutes, depending on the speed of your hardware and software, the number of line segments you use, and your programming style. If you find that morph is taking too long when you are running the medit program, we suggest that you work with lower resolution picture files. You could use the programs convert, xv, or tifftopnm and pnmscale in /usr/contributed/bin to make shrunk versions of your picA and picB, then run medit on these until your correspondence is well set, only using the full resolution pictures to generate your final frames. If your program is running too slowly, use profiling tools to identify hot spots, pre-compute common subexpressions, try integer arithmetic where possible, and compile with the optimizer (that's partly how we got "Their Morph" to be so fast). Also, it's OK if you hard-wire b=2, for example, to speed things up.

If you find the quantization objectionable, try the -newcm option to xplay and medit. This will give the created windows a new colormap and use all 256 colors on an 8 bit display.

Check that your bilinear interpolation is working correctly. One way to do this is to use medit to set up a test warp that maps a small region of one picture into a much bigger region, and view the resulting picture with xplay -gray. The resulting picture should look continuous (no contouring or jaggies).

If your source pixel coordinates fall out of range, what should you do? Definitely don't try to read a pixel whose coordinates are out of range with PIC_PIXEL! I suggest you simply return black (0,0,0) in such cases.

There is a small typo on page 37 of Beier-Neely: line 7 of the pseudocode should say D[i]=X'[i]-X, not X'[i]-X[i]. This was fixed already with whiteout in the copies distributed in class.

Your Beier-Neely code should ignore zero-length line segments.

Have fun!

15-463, Computer Graphics 2
Paul Heckbert