A Graph Matching Approach to 3-D Point Correspondences

A recursive descent tree traversal algorithm is presented to find the point correspondences between two views. Given two sets of noisy 3-D feature points on multiple rigid objects at two time-sequential views, the points at the first view are constructed as a graph and then another graph is derived from those feature points at the second view so that a maximal matching point and minimum matching error is obtained. The correspondence of the vertices is then found. The algorithm can also he used when the number of points at two views are different. Therefore, after matching, the occluded points at either view or both views can be identified. The computation time of the proposed algorithm is large when the number of feature points is large. A data set splitting strategy for such cases, which can significantly reduce the computation time, is presented. Another algorithm presented is one in which motion parameters are estimated from a matched subgraph and are then used to guide the matching for the rest of the nodes. Computer simulations are performed to show the efficiency and accuracy of the algorithm.