Figure 1: Top: a Dodge Stealth '94 and a VM Beetle '70 \ Bottom: four frames from a 3D morph between the two cars
The Problem: To develop software to automatically generate a correspondence between two three-dimensional colored surfaces
Motivation: If two objects can be set in correspondence, then a class of objects can be modeled in the following way. All objects are set in correspondence, one by one, with an base object. These correspondences represent warpings of one object to other objects in the same class of instances. When the warpings are combined in a linear network as described in [6], we have created a model of the object class. This model can be used for a variety of purposed as described below.
Previous Work: Similar networks have been successfully built for two-dimensional images. [2] used such a technique to synthesize images of a face under two pose-expression parameters. The important step is to build the correspondences. On images, optical flow algorithms have been found to work well where there are dense correspondences [2] [1]. When a set of correspondences has been built, pixel-wise correspondences can be built using linear combinations of prototypes as demonstrated in [5].
Thomas Vetter and Volker Blanz have produced results of correspondences between three-dimensional models of faces or automobiles. By constructing a cylindrical representation of the object containing both radius and color information, they were able to produce good correspondences using optical flow. However, this projection approach has the problem that it can only represent surfaces with limited curvatures. We would like to remove this constraint.
Approach: For our approach, we first construct a ``pyramid'' of meshes for each of the two objects we would like to set in correspondence. Each pyramid consists of a set of progressively simpler meshes each approximating the original. We use Hoppe's Progressive Meshes [4] or Garland's and Heckbert's Quadric Error Metrics [3] to construct these simpler objects. We start with the two simplest surfaces (one from each pyramid) and find the correspondence between them. Then, using this correspondence as a starting point, we can more easily find the correspondence between the two next more complex surfaces. We continue in this fashion until we have finally found the correspondence between the two fully detailed surfaces thus achieving our goal.
At each stage of the above algorithm, we perform an energy minimization to find the correspondence needed as input for the next stage. We perform gradient descent with respect to the vertices of one surface to minimize an energy function consisting of two terms. The first term is the distance from one surface to the other (the surfaces should match when aligned by the correspondence) and the second term encodes the structural changes which the correspondence induces (we also wish to minimize the degree to which we have to distort one object to set it in correspondence with the other).
This technique provides good automatic correspondences and can be used on a wide variety of surfaces. In fact, due to its general nature, it provides a method of matching any two n-dimensional manifolds in a d-dimensional space. The pyramid structure allows for much faster computations (since most of the work can be done at the lower levels where there are far fewer variables) and provides more accurate results since the important features are matched first thus preventing the algorithm from being confused by lesser features (which are considered later at higher levels of detail).
Although morphs are not the goal of this algorithm, a morph provides a good way of visualizing the correspondence generated. To this end, figure 1 shows one such morph between two cars. Full details of the algorithm and other results can be found in [7].
Difficulty: While correspondences may be obvious to human observers, this apparent triviality of the task is due to the great amount of prior information a human brings to it (such as knowledge about function and use of the object and its subparts). With only shape and color information, the task is much harder.
Impact: Building a linear model of a class of objects can have many benefits. One is as a design tool. Creating novel three-dimensional polygonal shapes for use in computer graphics is not a simple job. By combining known instances of the same class in such a network as described above, a user wishing to design a novel instance of the class can work with the parameters of the model to create the new shape (e.g. a car, cup, or face). The parameters of the network are easier to understand and adjust than the vertices of the points on the mesh. Preliminary results with cars show that some of the parameters found correspond well to natural variations like length or how ``sporty'' the car is. Giving the modeler control over those types of parameters is much more useful than requiring he/she to construct a model in three-dimensional space by specifying vertices and faces.
Future work: We would like to apply this algorithm to other matching tasks (as it is general to any dimensional embedded manifolds) and add additional constraints to insure that the match between two shapes is the same regardless of the order of input.
Figure 1: Top: a Dodge Stealth '94 and a VM Beetle '70 \
Bottom: four frames from a 3D morph between the two cars
Research Support: "An Example-based Modeling System for the Synthesis of 3D Models" funded by ONR under grant number N00014-96-1-0342, OSP Project Number 64363
References:
