|
Morphing
Morphing is a transformation of images. It is used in many animations and movies to warp a first image into a second image. The morph process transforms two images so that they have the same "shape" -- the resulting images can then be cross dissolved to produce a sequence. In this project, I investigated two morphing algorithms -- Feature Base Image Metamorphosis and View Morphing.
Feature-Based Image Metamorphosis
This algorithm was devised by Beier and Neely in 1992. The basic idea is that feature lines are interactively selected by the "animator" in the two images. These feature lines creates a reverse mapping, i.e. we calculate pixel by pixel the destination image by sampling the correct pixel from the source image (This is different than forward mapping in which we calculate the destination of each pixel in the source image).
Field Morphing Algorithm
We calculate the following:
where Q and P define a line in the destination image, Q' and P' define the corresponding line in the source image, X defines the destination image coordinate, and X' defines the source image pixel coordinate. The value u is the position along the line and v is the distance from the line. Note that the value for u ranges from 0 to 1 as we move from P to Q and is less than 0 or greater than 1 outside the range. The algorithm for one feature line is as follows:
Intuitively, each pixel coordinate is transformed by a rotation, translation, and/or a scale. The value of u is normalized by the length of the line which means the images are scaled along the direction of the lines by the ratio of the length of the lines. If the two lines are the same length and orientation but different positions specify a translation. Next we have to see how multiple feature lines can be incorporated into this algorithm. This will allow for more complex transformations.
Each feature line has a corresponding influence around the neighboring pixels. This is given by the following formula:
a is the line strength value. A smaller value affects pixels close to the line more then pixels far away providing more local control. Larger values make impact both close and far pixels. This will allow for a more smooth warping, but with less precise control. I used a value of 2.
b is the fall off value. This determines how the relative strength of different lines falls off with distance. If the value is large, only the line closest to a pixel will affect it. If b is zero, each pixel is affected by all lines equally. b should be in the range of [0.5, 2]. I used a value of 2.
p is the line length value. The value of p is typically in the range of [0, 1]; if p is zero, all lines have the same weight. A value greater than zero gives a greater relative weight to longer lines.
For multiple lines, the algorithm is as follows:
The figure above shows influence of two lines P1'Q1' and P2'Q2'. The location X' is a weighted average of pixel locations X1' and X2'. The pixel X' in the source image maps to X in the destination image.
Two Image Morphing
A morph operation blends between two images I0 and I1. A set of corresponding lines are defined in I0 and I1. A new set of lines are calculated for each intermediate frame I of the transformation. This is accomplished by interpolating endpoints of the lines in I0 and I1. The two resulting images (i.e. applying the algorithm to I0 and I1) are then simple cross-dissolved.
Running Time
The running time of the algorithm is proportional to the size of the image times the number of lines in the set. We must compute the influence from all lines before a pixel can be warped. The running time of two images of size 254 by 248 with 5 feature lines breaks down as the following:
- First Image Morph: 1.6820 seconds
- Copying Pixels for first image: 0.4410 seconds
- Second Image Morph: 1.6620 seconds
- Copying Pixels for second image: 0.4010 seconds
With 12 feature lines, the time is:
- First Image Morph: 4.1560 seconds
- Copying Pixels for first image: 0.4300 seconds
- Second Image Morph: 4.3870 seconds
- Copying Pixels for second image: 0.4130 seconds
Results
The top two pictures show the two original images with only 5 feature lines selected. As shown, the picture of Madonna is centered. Britney is tilting her head. The next two images are the warped images. Notice that Madonna's head is slightly tilted and Britney's is a little more straight. Their mouths are now about the same size as well as their eyes. The final image shows the resulting metamorphosis. This is the halfway point of the sequence. This algorithm works really well -- the results are very good and it is easy to use. The animator has total control over how the warping works. Everything is specified by the animator. Adding line segments increases control in a specific area without affecting other areas too much.
Click here for the entire morphing sequence.
View Morphing
View morphing is a image morphing technique by Steven Seitz and Charles Dyer. The fundamental idea is that view morphing develops a method to preserve the 3D shape of images in the morph. When morphing between different views of an object, view morphing creates new views of the object with a more realistic transition. View morphing is a 2-dimensional morph that tries to keep the 3-dimensional feel. On a high level, the view morphing algorithm consists of three steps. First the two images, I0 and I1, are pre-warped to I0' and I1'. This brings the image planes into alignment without changing the optical centers of the cameras. Second we morph the pre-warped images, to Is'. This is accomplished by linearly interpolating positions and colors of corresponding points using any morphing technique (for example we could use the feature-based morphing algorithm as described above). Third we postwarp. This transforms the image plane of the new view to its desired position and orientation, Is.
Pre-Warp
The prewarping transformations, H0 and H1,are calculated from a set of point correspondences. These transformations when applied to I0 and I1 creates two images where corresponding points in the two warped images appear in the same scanline. This can be accomplished by the following algorithm as presented by Seitz.
First we must be able to prewarp the images without having the projection matrices. We can use the fundamental matrix. The fundamental matrix is a 3 by 3 rank 2 matrix that satisfies the relation:
We compute the fundamental matrix using Hartley's 8-point algorithm. This algorithm needs a minimum of 8 corresponding points from the 2 images. The image points are normalized so that their mean is zeo and the RMS distance from the origin is sqrt(2).
To calculate H0 and H1, we must make the image planes parallel by applying a 3D rotation followed by a 2D transformation to algin the corresponding scanlines. To make the two views parallel, we can rotate each image plane Ii about the line di given by the intersection of E with Ii. This is done by rotating the epipole (the epipole represents the projection of C1 into I0). We rotate the epipole e0 by the following:
The angle of rotation is determined to be
A similar rotation is performed on I1. I1 can be made parallel to E by rotating about any line d1.
Applying these rotational transformations to I0 and I1 make the two image planes parallel. It is then useful to add an additional affine warp to align the scanlines. This simplifies the morph step to a scanline interpolation. We must rotate the epipolar lines so that they are horizontal. These rotations are given by:
After applying these image plane rotations, the fundamental matrix has the form of:
The second image is vertically scaled and translated by the matrix
Finally the prewarping transforms inv(H0) and inv(H1) are given by
Postwarp requires a transformation Hs for each in-between image. Seitz and Dyer suggests that it is convenient to provide Hs indirectly by establishing constraints on the in-between images. A simple way of doing this is to specify the paths of four image points through the entire morph transition.
Fundamental Matrix Results
The above two images show the points used to calculate the fundamental matrix.
Each epipoloar line in the bottom picture corresponds to an "X" in the top picture. Each line was drawn using only the x and y coordinate of the "X" location and the fundamental matrix as computed using the 8-point algorithm.
This shows the epipolar lines in the first view. This was similarly calculated like above.
Pre Warp Results
The above two images show the prewarped sheds. From looking at these two images, it appears as if corresponding points are in the same scanline.
View Morphing Einstein
The top picture is a picture of Albert Einstein. The bottom picture is the same picture flipped vertically.
The above two pictures show the images after the prewarping algorithm has been applied.
Click here for the entire morphing sequence. Note that I omitted the post-warp step in this sequence. I am having trouble implementing this part correctly.
This is from Seitz's article. The top row shows the effects of feature morphing. In ti the shape of the object is distorted. The bottom row shows view morphing. This keeps the shape of the blade as the viewpoint is changed.
This is another example from Seitz's article. Feature-based morphing was applied to the top row of the Mona Lisa. The bottom row shows a similar transformation but using the view morphing algorithm. The second example is a little more realistic transformation, preserving some of the 3-dimensional structure.
Conclusion
As presented in the View Morphing paper, the idea is very cool! Realistic transformations can between two images -- from different viewpoints or a mirror image or even two different images -- can be morphed using a 2-dimensional technique but the 3-dimensional structure is still visible. Viewpoints and changes in projective shape can be handled by the view morphing algorithm. This technique can be applied to situations where no knowledge of the 3D shape is required. There are many issues associated with this morphing technique. Occulisions can affect the output greatly. Also the feature points selected can dramatically impact the final results. Just selecting the corresponding image points can be a difficult task. Although my implementation definitely needs improvement -- especially the post-warping step, the basic steps in the algorithm do work. The details of the algorithm were challenging to implement. Both view morphing and feature-based morphing provide very interesting ways of morphing images. Additionally, view morphing can even use feature-based morphing for the actual morph part. Thus we can think of view morphing as an extension onto image morphing, at least in certain cases. It provides a 3-dimensional perspective for 2-dimensional operatiions.
Code
|
|
|