Image Metamorphosis Using Snakes and Free-Form Deformations

Seung-Yong Lee, Kyung-Yong Chwa, Sung Yong Shin, George Wolberg

Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH)

Pages 439-448, 1995

Motivation

The problem of smoothly transforming one image into another is of interest to the entertainment industry for making interesting visual effects in movies. This process is called image metamorphosis.

We would like to make the process of image metamorphosis as easy and accurate as possible. In particular, we want to make as much of the process automatic as possible (make it easy). We also want the metamorphosis to accurately reflect which features in a source image are transformed into which features in a destination image (make it accurate).

Goal of This Paper

This paper presents solutions to the following image metamorphosis problems:

Feature specification: Use snakes to find features. Snakes are formed by balancing image forces (forces pushing the snake toward features such as lines and edges) against constraint forces (forces pulling a snake toward a desired feature among nearby features). This balancing is done by energy minimization [8].
Warp generation: Use multilevel free-form deformations (MFFDs) to make smooth one-to-one warps between pairs of feature points.
Transition control: Simplify the MFFD method to control geometry and color blending.

Related Work

Earlier work on warp generation includes:

Mesh-based methods: Nonuniformity in the mesh itself represents features [14] [19]. Warping is done between corresponding mesh points using spline interpolation or Bézier clipping [15]. Mesh-based methods are fast and intuitive, but it can be difficult to use a control mesh to specify all the arbitrary features.
Field morphing: Line segments specify features in two images and are used to guide the morphing process. This method takes into account all the features specified by the animator, but suffers from undesired distortions. See [2].
Surface-based feature warps: If corresponding features in two images are each specified by a set of points, we can simply create a smooth surface connecting the points to specify a warp [16] [19]. Similar methods with the thin plate surface model have also been proposed [10] [12]. An advantage of these methods is that, if feature A in a source image corresponds to feature A' in a destination image, then part of the warp consists of directly transforming A into A'.
Energy minimization: Suppose we are given a set of pairs (x, y) where x is a feature point in a source image and y is the feature point in a destination image corresponding to x. Then we can create a C¹-continuous one-to-one warp that smoothly deforms each source feature point x into each destination feature point y by an energy minimization method [11]. This method transforms features directly, but unfortunately is computationally expensive.

This paper presents a new multilevel free-form deformation (MFFD) technique to derive a C²-continuous one-to-one warp that directly maps features to features. The technique is based on a 2D B-spline approximation and is much simpler and faster than the energy minimization method above.

Free-form deformation (FFD) is a technique for a deforming 3D object by deforming a parallelepiped lattice containing the object. See [17] [4] [5] [7].

Work on transition control includes:

Mesh warping: For each point in a mesh, we assign a transition curve that represents the path of the point throughout the warping process [19]. For a complicated mesh, a Bézier function can be defined over the mesh to control transition, instead of having a transition curve for each point [14].
Transition surfaces: At a few spaced out positions in the source image, we compute the transition rates for those points. Then we construct a smooth surface representing the transition rates for all points in the image. This surface can then be used to find transition curves for all points in the source image.

As mentioned earlier, this paper also constructs a smooth surface for transition control.

Feature specification is the most tedious part of morphing for animators. Work on feature specification consists mainly of computer vision techniques [3]. This paper uses snakes [8] from computer vision to reduce the burden of feature specification.

Other relevant work: [1] [6] [9] [13] [18].

Results

Snakes help an animator easily and accurately represent the position of a feature and establish feature correspondences between two images. The MFFD deformation technique is fast even when the number of features is large, and the generated warps are visually interesting. Multilevel B-spline interpolation efficiently constructs a C²-continuous surface for transition control.

Bibliography

1: D. H. Ballard and C. M. Brown.
Computer Vision.
Prentice-Hall, 1982.
2: T. Beier and S. Neely.
Feature-based image metamorphosis.
Computer Graphics (SIGGRAPH), 26(2):35-42, 1992.
Summary available .
3: P. J. Benson.
Morph transformation of the facial image.
Image and Vision Computing, 12(10):691-696, 1994.
4: S. Coquillart.
Extended free-form deformation: A sculpturing tool for 3d geometric modeling.
Computer Graphics (SIGGRAPH), 24(4):187-196, 1990.
5: S. Coquillart and P. Jancene.
Animated free-form deformation: An interactive animation technique.
Computer Graphics (SIGGRAPH), 25(4):23-26, 1991.
6: T. Goodman and K. Unsworth.
Injective bivariate maps.
Technical Report CS94/02, Dundee University, U. K., 1994.
7: W. M. Hsu, J. F. Hughes, and H. Kaufman.
Direct manipulation of free-form deformations.
Computer Graphics (SIGGRAPH), 26(2):177-184, 1992.
8: M. Kass, A. Witkin, and D. Terzopoulos.
Snakes: Active contour models.
International Journal of Computer Vision, pages 321-331, 1988.
9: S.-Y. Lee.
Image Morphing Using Scattered Feature Interpolations.
PhD thesis, KAIST, 1995.
10: S.-Y. Lee, K.-Y. Chwa, J. Hahn, and S. Y. Shin.
Image morphing using deformable surfaces.
In Proceedings of Computer Animation, pages 31-39. IEEE Computer Society Press, 1994.
11: S.-Y. Lee, K.-Y. Chwa, J. Hahn, and S. Y. Shin.
Image morphing using deformation techniques.
The Journal of Visualization and Computer Animation, 6(3), 1995.
12: P. Litwinowicz and L. Williams.
Animating images with drawings.
In SIGGRAPH 94 Conference Proceedings, pages 409-412. ACM Press, 1994.
13: G. H. Meisters and C. Olech.
Locally one-to-one mappings and a classical theorem on schlicht functions.
Duke Mathematical Journal, 30:63-80, 1963.
14: T. Nishita, T. Fujii, and E. Nakarnae.
Metamorphosis using bézier clipping.
In Proceedings of the First Pacific Conference on Computer Graphics and Applications, pages 162-173. World Scientific Publishing Co., 1993.
15: T. Nishita, T. Sederberg, and M. Kakimoto.
Ray tracing trimmed rational surface patches.
Computer Graphics (SIGGRAPH), 24(4):337-345, 1990.
16: D. Ruprecht and H. Müller.
Image warping with scattered data interpolation.
IEEE Computer Graphics and Applications, 15(2):37-43, 1995.
17: T. W. Sederberg and S. R. Parry.
Free-form deformation of solid geometric models.
Computer Graphics (SIGGRAPH), 20(4):151-160, 1986.
18: D. Terzopoulos.
Multilevel computational processes for visual surface reconstruction.
Computer Vision, Graphics, and Image Processing, 24:52-96, 1983.
19: G. Wolberg.
Digital Image Warping.
IEEE Computer Society Press, 1990.