Hypergraph Based Feature Matching in a Sequence of Range Images

Abstract The key issue in motion estimation and tracking an object over a sequence of images is establishing correspondence between the features of the object in the different images of the sequence. This paper considers the problem of establishing correspondences between surfaces in a sequence of range images. We present a novel procedure for finding correspondence and show the results on real range image sequences. A hypergraph search procedure forms the basis for the algorithm that computes the correspondence between surfaces. The solution uses geometrical and topological information derived from the scenes to direct the search procedure. Two scenes are modeled as hypergraphs and the hyperedges are matched using a sub-graph isomorphism algorithm. Further, we present a sub-hypergraph isomorphism procedure to establish the correspondences between the surface patches and demonstrate the algorithm on different types of real range image sequences. We present results that show that the algorithm is robust and performs well in presence of occlusions and incorrect segmentations.