This project was inspired by the image morphing booths at the local Sega City Playdium. Two people have their photographs taken, and the booth prints out an image of their potential offspring. While the booth processes both images, it displays to the public the features it matched on the two faces, such as eyes, nose, mouth, face contours, and hair. We believe the machine uses some type of feature detection followed by an image warp/morph to accomplish the effect. The output is quite realistic and we wish to discover how it's done.
We originally proposed to include automatic feature detection, but there wasn't enough time so the features have to manually specified.
A naïve morph would be just a cross fade between two images. This looks unrealistic because of ghosting effects due to edges not lining up. A better morph warps the two images to be warped to line up the edges and then doing a cross fade. Lee[1] provides a formal description of this process. Suppose we want to generate a 50% in-between image from the one source image to another source image. Given a warp function we wish to warp the two source images to in-between images such that the features (edges) line up. As shown in the following diagram, source1 is warped, source2 is warped, and then both are cross-faded to generate a morph. The "features" the dark edges we are trying to match.
We chose to use the warp function proposed by proposed by Beier and Neely[2]. Apparently it's the same algorithm used to generate morphs in Michael Jackson's "Black or White" video.
The algorithm is implemented in Matlab and in C (for debugging and speed). We have two different implementations to derive control lines. In one, the user manipulates a spline to generate control lines, and in the other, users draw the control lines directly. Our image morpher has support for different sizes of the two source images the destination image.
This section describes the code and how to use the programs.
morph.tar.gz (191 KB)
The files are located in <project root>/vision/final. The program is divided into the following files:
Spline based control lines (gui front-end):
runs.m (wrapper)
makechild.m (harness to perform the spline-based morph)
Line segment based control lines (gui front-end):
runns.m (wrapper)
makechildns.m (harness to perform the non-spline morph)
The warping algorithm (warp back-end):
mwarp.m
warpengine.slow.m (original implementation)
warpengine.m (optimized vector implementation)
perp.m (find a perpendicular vector)
Spline functions (spline back-end):
psplinalize.m (construct a piecwise periodic cubic spline)
plot_other_segments.m (Like plot_segments.m, but skips every other
line segment)
Some of the spline helper functions (nothing terribly non-trivial) was
taken from the course, CS 370 - Introduction to Scientific Computing,
and were probably written by Dr. Wei-Pai Tang[6].
What we didn't write:
pwCEval.m (Converts a piecewise polynomial into a list of
line segments.)
Locate.m (Locate which peicewise segment a point on a spline point
belongs to (This is actually a helper f'n for pwCEval))
plot_segments.m (Plots a list of line segments)
To use the program you only need to fiddle with runs.m and runns.m. These files just call the morph with the appropriate parameters.
To use the spline based morph, execute runs.m.
To use the non-spline based morph, execute runnss.m. By default this will morph fran.jpg and anish.jpg by 50%.
The C code is located in <project root>/vision/test/mwrapconsole/. It is not relevant to the project. It was done to help with debugging the Matlab algorithm (Visual C has a better debugger than matlab editor) and for speed.
This section describes the algorithm for GUI front-ends, the warp backend algorithm (basically a summary of Neely's description), modifications to allow different source and image sizes, and finally the optimized warp algorithm in warpengine.m (warpengine.slow.m is unoptimized).
The front-end is the mechanism used as a harness for the warp engine. The details of implementation are not of interest to this report. Suffice to say, it serves as the UI to allow the user to choose control-lines that facilitate the operation of the warp algorithm.
The two versions of the front-end impliment a different style of UI. The non-spline front-end yields absolute control to the user, allowing him/her to laboriously choose an arbitrary collection of control-lines. The spline-implementation allows the user to only choose 6 control points, from which, the front-end will construct a periodic spline, whose perimeter will form the control-lines for the warp algorithm. The end result is a much simpler and quicker experience, but yields a less satisfying transformation.
For a more detailed discussion of splines vs. non-spline implemenation, please see the experiments section.
The type of spline used to impliment the front-end of this solution was a piece-wise periodic cubic hermite spline interpolation. This section will briefly describe some of the mechanics of our periodic spline implemenation. For a more detailed derivation, see Van Loan[3].
For simplicity of derivation, the equations of the cubic hermite spline are
built by choosing the Bernstein basis, 
[6] as the basis for the piecewise cubic
polynomial. This gives a piece-wise polynomail of the form:
, 
for an n-segmented piecewise polynomial. (n pieces over n sample points.) Now, to constrain the polynomial, the following properties are chosen:
And to establish perodic continuity, choose:
and 
which can be expressed in the (solvable) matrix form,
The spline method and the non-spline method are just front-ends to generate control line segments, which is the basic requirement for the warp.
Given a warp function and the transition factor t = [0,1] (parametric term specifies the amount of morph from source1 to source2), we generate an in-between set of control lines (call this the destination) using t to linearly interpolate between source1 control lines and source2 control lines. Then source1 and source2 are both warped to the in-between destination image and cross-faded.
The control lines represent a field of influence that pushes pixels around. The three parameters a, b, and p described in Neely are set in warpengine.m as follows.
a = 0.000001 | This forces pixels on the control lines to move exactly with the line. |
b = 2.0 | This value just "felt right". A higher number means pixels closer to control lines are influenced more by the lines than pixels further away from the lines. |
p = 0 | This gives all lines the same weight |
Pixels are mapped from the destination image (which has it's own in-between control lines) to the source image (whish also has it's source control lines) by keeping the relative position of pixels to the control lines the same. In the following figure, the pixel X in the destination is retrieved from the pixel X' in the source image using the destination control line L, and the source control line L'.
u is the parametric distance along the vector, and v is the perpendicular pixel distance from X to the line.
Multiple control lines are handled similarly. For each control line i, a Xi' pixel is generated. A weighted sum of the various Xi' (using the distance from Xi' to the lines i in the weighting function) generates a final X' pixel in the source image.
Neely discusses two interpolation methods to create an in-between destination control line. One is to interpolate the endpoints (we used this method). The side effect of this is that a rotating line would shrink it, shown below:
The second method interpolates the center position, the length, and orientation of each line, which doesn't have the side effect.
Neely's algorithm assumes that the source and destination images have the same size. We allow the two sources and the destination image to have different sizes. We do this by scaling the destination image and control lines appropriately.
Suppose source1 has dimensions (s1.width, s2.height), source2 has dimensions (s2.width, s2.height), and the destination image has dimensions (d.width, d.height). Also, suppose we have a source1 control line s1.PQ (P and Q are endpoints) and a source2 control line s2.PQ, and the transition factor t. The in-between destination control line d1.PQ and d2.PQ is calculate like this in mwarp.m:
scalefactor1.PQ = (d.width/s1.width, d.height/s1.height)
scalefactor2.PQ = (d.width/s2.width, d.height/s2.height)
scaled_s1.PQ = scalefactor1.PQ .* s1.PQ
scaled_s2.PQ = scalefactor2.PQ .* s2.PQ
scaled_d.PQ = scaled_s1.PQ*(t) + scaled_s2.PQ*(1-t)
d1.PQ = d.PQ ./ scalefactor1.PQ
d2.PQ = d.PQ ./ scalefactor2.PQ
Now source1 is warped to destination1 using s1.PQ and d1.PQ, and source2 is warped to destination2 using s2.pQ and d2.PQ. Destination1 and destination2 both have dimensions (d.width, d.height).
In the warp, every destination pixel coordinate X is first scaled into the source image size before being processed (the SCALE vector in warpengine.m):
scaledX = (source.width/destination.width, source.height/destination.height) .* X
Initially the warp algorithm was a direct implementation of the algorithm in Neely (see warpengine.slow.m). It used a triple for loop:
iterate over rows in destination (Height)
iterate over columns in destination (Width)
iterate over each control line( total N )
end
end
end
With 35 control lines, it took 90 minutes to generate a 400x300 morphed, blended destination image.
The optimized warp is still proportional to the number of pixels in the destination image times the number of control lines. However, it's vectorized to take advantage of vector math. The code in warpengine.m is difficult to understand and so a brief explanation follows.
The two inner W and N loops have been replaced by a processing a column vector of height W*N. If W=4 and N=2, then the column vector will have height 8. The source pixels Ps for each x coordinate for each control line are solved for simultaneously. For example, one iteration of the outer loop (H) for a particular y will produce a vector shown below in column labelled Source Pixel
| Column (X_coordinate) | Control Line | Source pixel | Meaning |
| 1 | 1 | Ps11 | Pixel (1,y) mapped to pixel Ps11 generated using control line 1 |
| 1 | 2 | Ps12 | Pixel (1,y) mapped to pixel Ps12 generated using control line 2 |
| 2 | 1 | Ps21 | Pixel (2,y) mapped to pixel Ps21 generated using control line 1 |
| 2 | 2 | Ps22 | Pixel (2,y) mapped to pixel Ps22 generated using control line 2 |
| 3 | 1 | Ps31 | Pixel (3,y) mapped to pixel Ps31 generated using control line 1 |
| 3 | 2 | Ps32 | Pixel (3,y) mapped to pixel Ps32 generated using control line 2 |
| 4 | 1 | Ps41 | Pixel (4,y) mapped to pixel Ps41 generated using control line 1 |
| 4 | 2 | Ps42 | Pixel (4,y) mapped to pixel Ps42 generated using control line 2 |
All control line information (magnitude, perpendicular vector, etc) that doesn't depend on loop variables is pre-calculated.
The rest of the "reshape" calls in the code are used to reorder the vector to extract weight sums from the vector and calculate the final source pixels per x coordinate. In effect, the inner two loops have been one-dimensionalized and so one entire row is solved at a time.
This new code morphs the same 400x300 image with 35 control lines in 2 minutes. This speedup makes generating multiple frames for an animation much less painful, and makes the C version of the code redundant.
The warp can optionally use bilinear filtering. With bilinear filtering, a pixel's colour is the weighted average of the colours of the neighbour integer pixels in the source image. The weights are just the distances to the neighbour pixels.
Fran w. Control Points 
|
25% morph
|
Fran 50% warped 50% morph  Anish 50% warped 
|
75% morph
|
Anish w. Control Points 
|
| Fran w. control spline  |
Fran warped |
Warp w. crossfade  |
Anish warped |
Anish w. control spline  |
| Non-Interpolated | With Bilinear Filtering |
|
|
|
|
|
|
|
|
|
Many things could be added to the morpher.
Firstly, a more helpful GUI would make life simpler. The runns.m GUI doesn't let you move the lines around once they are drawn. You have to start drawing the lines from scratch if you made a mistake.
Secondly, an edge detector could be added to automatically detect features. This won't be as precise as manually adding the features, but implementing it would be an educational experience. The difficulty with edge detection is that the same number of edges must be detected in both the images and they must correspond to the same feature. We wouldn't want an eye edge in the first source image to correspond to a nose edge in the second source image. Somebody has already done this with good results . The catch is that the source images must be more constrained (same background and shadows).
The third improvement, which is in our opinion the most exciting, would be to use different transition factors for different feature sets. For example, we could create an offspring image with varying feature influences from the parents. Weights between the father/mother images could be (50/50) for eyes, (75/25) for the nose and (100/0) for lips. The GUI front end would need to distinguish between different sets of control lines, one per facial feature. In addition, the warp could use a different transition factor from the cross-fade. A better description of this "non-uniform metamorphosis" is given in Wolberg[5].
The morph works quite well. Some 50% morphed images look very realistic. However, the final image still doesn't resemble the images output by Playdium's booth. We now believe they use a non-uniform warp.
[2] Beier, Thaddeus, and Shawn Neely. Features-Based Image Metamorphosis. Computer Graphics (Proc SIGGRAPH '92), 26(2), 1992.
[4] Roger Claypoole, Jim Lewis, Srikrishna Bhashyam, and Kevin Kelly. ELEC 539: Image Morphing. http://www.owlnet.rice.edu/~elec539/Projects97/morphjrks/themainpage.html. (7th April 12, 2001).
[6] Tang, Wei-Pai, CS 370 - Introduction to Scientific Computing - Lecture Slides, Winter 1999.