Surface correspondence and motion computation from a pair of range images

The estimation of the motion transformation of a moving object from a sequence of images is of prime interest in computer vision. In this paper, the issues in estimating the motion parameters from a pair of range images are addressed, The motion estimation task, in the domain of range image sequences, has two components: (1) extract the surfaces and establish the correspondence of the surfaces over the frames in the sequence of range images, and (2) compute the motion transformation using these surface correspondences. A novel procedure based on a hypergraph representation is presented for finding surface correspondence, Two scenes are modeled as hypergraphs and the hyperedges are matched using a subgraph isomorphism algorithm. The hierarchical representation of hypergraphs not only reduces the search space significantly but also facilitates the encoding of the topological and geometrical information used to direct the search procedure, Results obtained from real range image pairs show that the algorithm is robust and performs well in presence of occlusions and incorrect segmentations. Motion transformation between image frames is computed using the planar and the quadric surface pairings, A least-squares minimization procedure is formulated that estimates the best motion transform, subject to the constraints of rigid motion. For the case of linear feature pairings, the motion computation becomes tractable because the rotation and the translation computations become independent of each other. However, for quadric surfaces this is not true. The equation to be minimized is highly nonlinear and the uniqueness of solution cannot be guaranteed. The solution obtained computes the motion by extracting unique linear features from the quadric surfaces and using them to compute the motion transformation, The main contribution of the work is a surface-based framework for motion estimation from a sequence of range images. The primary issues of correspondence and motion computation are formulated and solved in terms of the surface descriptions. (C) 1996 Academic Press, Inc.