With recent improvements in methods for the acquisition and rendering of 3D models, the need for retrieval of models from large repositories of 3D shapes has gained prominence in the graphics and vision communities. A variety of methods have been proposed that enable the efficient querying of model repositories for a desired 3D shape. Many of these methods use a 3D model as a query and attempt to retrieve models from the database that have a similar shape. In this thesis, we begin by introducing a new shape descriptor that is well suited to the task of 3D model retrieval. The descriptor is designed to enable efficient comparison of 3D shapes and is constructed to approximate the performance of a standard metric for comparing 3D models, thereby satisfying the requirements of efficiency and discriminability that are necessary for an effective, real-time shape retrieval system. We compare our descriptor to other existing descriptors in empirical retrieval experiments, demonstrating that the new shape descriptor provides improved retrieval accuracy and is better suited to the task of shape matching.

One of the specific challenges in matching 3D shapes arises from the fact that in many applications, models should be considered to be the same if they differ by a similarity transformation. Thus in order to match two models, a measure of similarity needs to be computed at the optimal translation, scale and rotation. In this thesis, we review a number of approaches for addressing the alignment challenge and provide new methods for addressing this issue that give rise to better shape matching algorithms.

Additionally, we present two general methods for improving the performance of many extant 3D model matching algorithms by providing a general framework for augmenting existing shape representations with global shape information characterizing salient shape properties. The first approach leverages symmetry information to augment existing representations with information characterizing a model s self-similarity. The second approach factors the shape matching equation as the disjoint product of anisotropy and geometric comparisons improving the matching performance of many shape metrics by facilitating the task of shape registration. In order to describe the symmetries of a 3D model, we present the symmetry descriptor, a collection of spherical functions characterizing the symmetries of a model. These spherical functions are indexed by the type of symmetry, (e.g. reflective symmetry, axial symmetry, 2-fold rotational symmetry, etc.) with the value at each point giving a continuous measure of the symmetry of a model about the corresponding axis. We describe an efficient signal processing method for computing these descriptors, giving the symmetry descriptors of spherical and 3D shape representations in order O(b⁴) time, where b is the bandwidth of the spherical or 3D representation.

Using the observation that it is easier to establish correspondences between two models that are isotropic than between two models with different anisotropic scales, we provide an iterative approach for transforming an anisotropic 3D model into an isotropic one. Two 3D models can then be compared by transforming each model into an isotropic one and then using one of the existant shape matching algorithms to obtain a shape representation of each of the isotropic models. We prove that the iterative approach is guaranteed to converge to an isotropic model, and show that in practice the convergence is efficient.

For both these methods, we show that many of the existing shape representations can be augmented with the obtained global shape information (either symmetry or initial anisotropic scale). We provide empirical results demonstrating that the new, augmented representation is more discriminating providing a representation of a 3D model that gives rise to improved matching performance in shape retrieval experiments. Finally, since the augmentation of both symmetry and anisotropy information can be done in a pre-processing step, and since the augmentation does not significantly increase the complexity of the shape representations, the new shape representations provide more discriminating matching performance without effecting the efficiency of retrieval making them particulary valueable for applications that seek to retrieve models from large repositories of 3D shapes.

@phdthesis{:2004:SRA,
   author = "Michael Kazhdan",
   title = "Shape Representations and Algorithms for {3D} Model Retrieval",
   school = "Princeton University",
   year = "2004",
   month = jun
}