Automatic Morphing

We wish to build a morphing algorithm which operates on features automatically extracted from two target images. The first step is to find the edges in the target images. We accomplished this by implementing a Laplacian Edge D etector. Once we find the edges in our images, we divide each image up into a grid, and find the "best line" in each sector. The algorithm finds the best line by correlating various lines with the binary edge-detected image. The most correlated line which surpas ses a minimum threshold is returned for each sector. Although it is possible to check for every possible line, this is very time consuming. Thus, the algorithm only looks for horizontal, vertical, and 45 degree lines. After the algorithm has found the best lines for each sector of both images, it attempts to coordinate the lines between images, and discard any discrepancies. For example, if a horizontal line is found in sector (1,2) of image one and a vertical line is found in sector (1,2) of image two, then these lines are discarded, and the algorithm declares "no line" for that sector! This is done to prevent morphing of drastically different lines; we found that morphs of this type looked very bad (extreme facial distortion). After the algorithm has found lines in both images and matched them together, the final step is to check the length of the lines. If the lines are being passed to a point morpher, then intermediate points must be included in the large lines. This is acc omplished by inserting extra points into lines which exceed a length threshold. Below is an example of algorithm output, using a 12x12 grid. These two images are the common lines found in the images. The following two images show these lines superimposed on the actual images. Clearly, some of the lines correspond to equivalent key features between both images, but a few do not (especially around the mouth and chin, and one line in the middle of the f orehead on the second image). Unfortunately, these few will cause the morphing algorithm problems. Using these lines, we created the following morph: Analysis of the Result: Strong points: The algorithm did a good job of locating the outer edges of the images. Thus, the outline of the morph is very "clean". The nose and eyes also morph well (except for the right eyebrow). Shortcomings: The line in the middle of the forehead on the second image causes a real problem. In the resulting morph, the eyebrow of the first face is pulled up to the forehead, which is not a good morph. Also, the lines around the mouth and chin do not correspond to the same features. On the first image, the lines correspond to the center of the mouth, while on the second image, some of the lines correspond to the upper lip, some to the lower lip, and one to the very top edge of the smile! Also, t he algorithm is attempting to morph the center chin line on the first image to the lower lip line on the second image. The result is a very unnatural morph around the mouth and chin area. Ideas for improvements: 1 - Implement an "outside in" algorithm, that is, an algorithm which attempts to find lines nearer to the edges of the image first, and then works it way toward the center. Such an algorithm would be able to find the outline of a face, but would have a d ifficult time finding facial features. For the most part, our algorithm does okay in this area, so this improvement would not add much to the final morph. 2 - Create an "average eye" filter, that is, a small matrix which is the average of eyes from various images. By computing the mean square error between this matrix and the image matrix at all locations, it should be possible to find the location of the eyes in the target image. However, since this is not a matched filter, the correlation must be done with a loop, and the resulting algorithm will be slow. It might be possible to do the same for the "average mouth". Despite the processing required, thi s improvement would (hopefully) rectify the shortcoming demonstrated above for the mouth and chin of the morph images. 3 - The current algorithm divides both images into the same grid, and maps sectors in a 1:1 fashion. By varying the size, shape, and location of the sectors (and tying them to the features of the image), it may be possible to generate better morphing poi nts. However, this ideas seems very difficult to implement. 4- Use the automatic morpher to find some key points that we know will work (such as the facial outline), and then allow the user to input more points manually. Although not entirely "automatic", this will at least cut down on the amount of input requir ed by a completely manual morpher.
Conclusions: The automatic morpher shows promise, but the results just don't look right. Even if 90% of the features extracted are good matches, the last 10% that are bad cause the morpher to do strange things, and, unfortunately, this results in a "bad morph". We s uspect that a combination of automatic (only picking the features that we have extremely high confidence are good ones) and manual morphing is the best attack.
Click here to go to laplacian page

Click here to go to other methods of edge detection

Click here to return to the main morph page