Monday, December 8, 2008

Feature Based Image Metamorphosis

Morphing is an image processing technique. Metamorphosis a.k.a Morphing is the transformation from one image to another. The main steps in morphing can be summarized as:

      Image warping + cross dissolving

This technique has many interesting applications. Animation effects like making animals talk are the outcome of this technique. This effect has also been successfully applied in the entertainment industry. e.g: Michael Jackson's Black or White video (http://www.youtube.com/watch?v=IisX9N6-dBc), an Indian movie where a song shows ageing effect via morphing (http://www.youtube.com/watch?v=BXvWy4pdLcs).

The morphing technique that I have implemented is called Feature Based Image Metamorphosis, a technique published by Thaddeus Beier and Shawn Neely in 1992. The main idea behind this is to create a transformation between source image and destination image. This transformation is created using inverse transform where every pixel in the destination image is mapped to some pixel in the source image. This creates a distortion of the source image with respect to the destination image. The distortion is controlled by specifying pairs of control lines (one line for each image). These control lines are vectors i.e they have direction.

Let us look at a single pair of lines and understand how the distortion happens.
Let PQ be the vector in destination image and P'Q' be the vector in the source image. For each pixel X in the destination image, the distance 'u' from P along PQ and the perpendicular distance 'v' to PQ is calculated. The pixel X' is obtained by applying values 'u' and 'v' to P'Q'. The color at pixel X' is applied to X.

For getting finer control, more than one pair of lines can be defined for the images. Instead of performing a simple averaging to combine the effect of each line on each pixel, following weighting parameters are defined in the paper:

a: determine position of pixels on the line
  Large value => smooth warping, lesser control
b: Strength of relative lines with distance
  Large value => each pixel affected by line nearest to it.
  0 => all lines affect equally.
p: Effect of length of the line
  0 => all lines have same weight
  1 => longer lines have greater relative weight

The pseudo-code for the algorithm is as follows:

For each pixel X in destination
  DSUM = (0,0)
  Weightsum = 0
  For each line PiQi
     Calculate u,v based on PiQi
     Calculate X'i based on u,v and P'iQ'i
     Calculate displacement = Di = X'i – Xi for this line
     Calculate dist = shortest distance from X to PiQi
     weight = (length^p / (a+dist))^b
     DSUM += Di * weight
     weightsum +=weight
     X' = X + DSUM / weightsum
   DestinationImage (X) = sourceImage(X')


Feature Based Metamorphosis described above is also called Field Morphing. This is because the multiple pair of vectors and the weighting parameters create a field like effect.

This algorithm has the advantage of being intuitive and simple to implement. The other plus point is that it allows the user to define control points. However this technique is computationally expensive. Each pixel needs to be compared against every control line. As the number of lines and size of image increases, so does the computation time. This makes the algorithm slow. Also, to get a good morphing effect, large number of control lines need to be specified.

While this technique has its disadvantages, the advantages and the simplicity have made it state of the art. Some interesting effects I was able to create are presented below:

FACIAL MORPHING



ANIMATION EFFECT




Reference
[1] Thaddeus Beier, Shawn Neely, "Feature-Based Image Metamorphosis", SIGGRAPH July 1992.