Feature Analysis and Registration of Scanned Surfaces

Natasha Gelfand, Ph.D. Dissertation, Stanford University, September 2006


In the last decade there have been significant technological advances in the design of tools for digitizing 3D shape of objects, leading to large repositories of 3D data, and the need to develop efficient algorithms to process and analyze scanned 3D shapes.

Most 3D scanners produce as their output a set of point samples corresponding to the shape of the digitized object as seen from a single viewpoint. To digitize the entire shape, several scanning passes are required, with either the scanner or the object being re-positioned between the scans. The problem of shape registration deals with computing the relative transformations between the scans to bring all scans into a common coordinate system. In this thesis we present several algorithms for registration of scanned surfaces. Our algorithms are based on analyzing local and global surface properties of the input shapes to improve the convergence of registration and the quality of the computed alignment.

First, we present an algorithm for automatic approximate alignment of two partially overlapping 3D shapes (data and model) without any assumption about their initial positions. The algorithm uses the distribution of values of a robust shape descriptor to select a set of feature points on the data shape and compute their potential corresponding points on the model shape. The resulting correspondence search space is explored using an efficient branch and bound algorithm based on distance matrix comparisons, and the best set of corresponding point pairs is used to compute the aligning transformation. The resulting alignment algorithm is used for registration of partially overlapping scanned surfaces, for simple symmetry detection, and for matching and segmentation of shapes undergoing articulated motion.

Next, we develop a surface descriptor based on surface self-similarity under continuous rigid motion, called surface slippage. We show that by analyzing a certain matrix computed from the point positions and surface normals of a pointset, one can differentiate among pointsets that correspond to planes, spheres, surfaces of revolution and surfaces of linear extrusion. We use the slippage descriptor to develop a segmentation algorithm for reverse engineering surfaces of mechanical parts, a problem that is frequently encountered in the field of Computer Aided Design.

Finally we apply surface slippage in the context of the Iterated Closest Point (ICP) algorithm, which is a widely used method for local registration of two 3D shapes. The quality of the alignment obtained by this algorithm depends heavily on choosing good corresponding points from the two datasets. If too many points are chosen from featureless regions of the data, ICP can converge slowly or find the wrong pose, especially in the presence of noise. Performing slippage analysis on the input shapes allows us to select a set of features on the input that minimizes the uncertainty in the final pose and improves the algorithm's convergence.


Dissertation [PDF 61Mb]
Defense slides [PPT 15Mb]