A union of spheres representation for 3D objects

Reconstruction of an object from a set of points sampled from its boundary is an important problem in graphics and vision. Several methods exist to compute and display surface (e.g., polygonal) and volumetric (e.g., polyhedral) models of objects from the boundary points. In order to display, transform, and compare objects, it is often convenient or necessary to use different representations of objects. Basic desired properties of representations of objects are efficiency of computation, storage, and display. Other important properties include stability (small changes in the data, such as noise or small distortions, cause small changes in the model), the ability to determine the similarities between two data sets, and the computation of simplified models. A survey of common representations of objects (e.g., surface, octrees, etc.) shows that some important properties are lacking in these representations. In this thesis we study a union of spheres representation (UoS) for the volume enclosed by an object's boundary. We present algorithms to generate stable union of spheres models of objects from various sources of data, such as volumetric data (e.g., data from CT or MRI scanners), range data, and other existing models. The spheres can be simplified to obtain multi-scale models. We present a method to establish correspondence between two objects using their union of spheres models and use this to calculate distances between objects, to register objects, and to interpolate between objects. This establishes a measure to study and compare such models. Examples with simple and complex objects show how this measure corresponds closely to the intuitive human understanding of shape.Science, Faculty ofComputer Science, Department ofGraduat