Surface matching is the process that compares surfaces and decides whether they are similar. In three-dimensional (3-D) computer vision, surface matching plays a prominent role. Surface matching can be used for object recognition;​ by comparing two surfaces, an association between a known object and sensed data is established. By computing the 3-D transformation that aligns two surfaces, surface matching can also be used for surface registration. Surface matching is difficult because the coordinate system in which to compare two surfaces is undefined. The typical approach to surface matching is to transform the surfaces being compared into representations where comparison of surfaces is straightforward. Surface matching is further complicated by characteristics of sensed data, including clutter, occlusion and sensor noise.

This thesis describes a data level representation of surfaces used for surface matching. In our representation, surface shape is described by a dense collection of oriented points, 3-D points with surface normal. Using a single point basis constructed from an oriented point, the position of other points on the surface can be described by two parameters. The accumulation of these parameters for many points on the surface results in an image at each oriented point. These images, localized descriptions of the global shape of the surface, are invariant to rigid transformations. Through correlation of images, point correspondences between two surfaces can be established. When two surfaces have many point correspondences, they match. Taken together, the oriented points and associated images make up our surface representation. Because the image generation process can be visualized as a sheet spinning about the normal of a point, the images in our representation are called spin-images.

Spin-images combine the descriptive nature of global object properties with the robustness to partial views and clutter of local shape descriptions. Through adjustment of spin-image generation parameters, spin-images can be smoothly transformed from global to local representations. Since they are object-centered representations, spin-images can be compared without alignment of surfaces. However, spin-images are constructed with respect to specific surface points, so they can also be used to align surfaces. Because spin-images are constructed without surface fitting or optimization, they are simple to construct and analyze.

We demonstrate the usefulness of spin-images by applying them to two problems in 3-D computer vision. First we show that surface registration using spin-images is accurate enough to build complete models of objects from multiple range images. Without a calibrated image acquisition system, we have built twenty models of objects with complicated shapes. We also apply spin-images to the problem of recognizing complete 3-D models of objects in partial scenes containing clutter and occlusion. Using spin-images, we have simultaneously recognized multiple objects from a library containing twenty models. We also verify experimentally that spin-image matching is robust to scene clutter by recognizing objects in 100 scenes containing clutter and occlusion.