Partial surface matching by using directed footprints

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, scattered uniformly along its boundary or inside its volume. 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 algorithm is based on assigning a directed footprint to every point of the two sets, and locating all the pairs of points (one of each set) whose undirected components of the footprints are sufficiently similar. The algorithm then computes for each such pair of points all the rigid transformations that map the first point to the second, while making the respective direction components of their footprints coincide. A voting scheme is employed for computing transformations which map significantly large number of points of the first set to points of the second set. Experimental results on various examples are presented and show the accurate and robust performance of our algorithm.