Partial surface and volume matching in three dimensions

In this paper we present a new technique for partial surface and volume matching of images in three dimensions. In this problem we are given two objects in 3-space, each represented as a set of points, and the goal is to find a rigid motion of one object which makes a sufficiently large portion of its boundary lying sufficiently close to a corresponding portion of the boundary of the second object. This is an important problem in pattern recognition and in computer vision, with many industrial, medical, and chemical applications. Our method treats separately the rotation and the translation components of the Euclidean motion that we seek. The algorithm steps through a sequence of rotations, in a steepest-descent style, and uses a novel technique for scoring the match for any fixed rotation. Experimental results on various examples, involving data from industrial applications, medical imaging, and molecular biology, are presented, and show the accurate and robust performance of our algorithm.