Partial surface matching by using directed footprints

In this paper we present a new technique for partial surface and volume mat ching of images in three dimensions. In this problem, we are given two obje cts in 3-space, each represented as a set of points, scattered uniformly al ong its boundary or inside its volume. The goal is to find a rigid motion o f one object which makes a sufficiently large portion of its boundary lying sufficiently close to a corresponding portion of the boundary of the secon d object. This is an important problem in pattern recognition and in comput er vision, with many industrial, medical, and chemical applications. Our al gorithm is based on assigning a directed footprint to every point of the tw o sets, and locating all the pairs of points (one of each set) whose undire cted components of the footprints are sufficiently similar. The algorithm t hen computes for each such pair of points all the rigid transformations tha t map the first point to the second, while making the respective direction components of their footprints coincide. A voting scheme is employed for co mputing transformations which map significantly large number of points of t he first set to points of the second set. Experimental results on various e xamples are presented and show the accurate and robust performance of our a lgorithm. (C) 1999 Elsevier Science B.V. All rights reserved.