Maximal matching of 3-D points for multiple-object motion estimation

Determining the relative motion/position between an observer and its environment is an important problem in computer vision. A major task is to find corresponding object features. In this paper, an efficient algorithm for matching 3-D points of multiple rigid objects is presented. The point-matching algorithm determines the correspondence by initiating a pairing of a triplet of noncollinear sensed points with a triplet of reference points and searching for new pairs of corresponding points, one at a time, using local distance and angular constraints. The pairing of each subsequent sensed point with a reference point is determined if the tetrahedron formed by the sensed point and the initial triplet is congruent to that formed by the corresponding reference points. Only simple computations are required in the algorithm. Global consistency of the pairings found by the algorithm is ensured without using model tests. The algorithm can be easily extended to incorporate other geometrical or non-geometrical object attributes to further prune the matching. Results of running the algorithm on synthetic and real data are given.