Range data and an extracted shape model
Suppose you are given a set a range data (this is a set of 3D points which are measured from an object's surface using a range scanner). How can you determine a shape which could have resulted in such data? And how concise a description can be provided? An example of this problem is shown in the picture below, which shows a set of range data (left), along with one possible shape model which describes this data (right).
In addition to estimating the shape of the surface from which the data was scanned, it is also worthwhile to keep the description of this surface as precise as possible. Having a short description of an object makes it easier to reason about the object for indexing or recognition.
This process is complicated by data that is noisy, sparse, or incomplete. There is little hope of accomplishing this task without using a model-based approach. In this case, we have developed a shape representation technique called shape blending. Briefly, this representation allows for two shapes to be combined together by "cutting" the desired parts from each, and "gluing" them together.
Having such a representation isn't enough, however, as there must be a robust and efficient method for estimating such a model. The blending representation was carefully tailored for this purpose. Blending allows for the smooth addition of parts and holes to an object. The smoothness of the process keeps the decisions that have to be made during estimation relatively simple.
Experiments
Below are two experiments showing examples of the automatic estimation of a shape model using the blending representation.
| In this first experiment, partial data from a scanned mug, which is shown from two views in (a), is initially fit using an ellipsoid model in (b). Based on automatic analysis of the result, the model is "split" into two in (c). Then, in (d) and (e), the parameters of each part are estimated separately while maintaining a good geometric connection between them (using blending). The model is split again in (f), and this time, a hole is automatically inserted, leading to the final fit in (g). This repeated application of blending also leads to a qualitative model description in (h) (the labels in the boxes are hand generated). About 70 shape parameters were needed to describe this mug. | 
Estimation of a mug |
| This second experiment involves generated (artificial) data from a two-holed object, shown in (a). It is used to demonstrate the process of blending on a more topologically complex object. As before, after an initial ellipsoid fit in (b), the model is split and re-fit several times in (c) through (f) to reach the final fit in (g). 84 shape parameters were required to describe this object. | 
Estimation of a two-holed box |
There are a number of available on-line publications describing this work (in chronological order):
This paper investigates a simple use of shape blending, where the blending is performed along the primary "axis" of a shape primitive (superquadric ellipsoids and tori). A simple decision procedure determines when to apply a blend, and allows for the combination of topologically distinct primitives (ellipsoid and torus), permitting a data-driven transformation of topology.
This paper generalizes the approach in the CVPR '94 paper to allow for arbitrary, hierarchical blending. There is also a more general decision procedure for applying a blend during estimation. Also presented are more complex estimation examples (such as objects with multiple holes).
This paper describes the initial work in the CVPR '94 paper (and omits many of the unrelated implementation details).
This paper is a comprehensive description of the process
of blending, the shape evolution that results from its
use, and how the decisions for applying blending are
made. The description of the representation here is more
thorough, and is not as confining as the ICCV '95 paper
(which makes implementation a nightmare). The view of
blending is also a bit different, where now, holes are
viewed as simply a special case of an object "part".
Also included are a number of validation experiments
which investigate the accuracy and stability properties
of estimation using blending.
(If you are going to read one of these
papers, this should be the one.)
Links