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 pa per, the issues in estimating the motion parameters from a pair of ran ge images are addressed, The motion estimation task, in the domain of range image sequences, has two components: (1) extract the surfaces an d establish the correspondence of the surfaces over the frames in the sequence of range images, and (2) compute the motion transformation us ing these surface correspondences. A novel procedure based on a hyperg raph representation is presented for finding surface correspondence, T wo scenes are modeled as hypergraphs and the hyperedges are matched us ing a subgraph isomorphism algorithm. The hierarchical representation of hypergraphs not only reduces the search space significantly but als o facilitates the encoding of the topological and geometrical informat ion used to direct the search procedure, Results obtained from real ra nge image pairs show that the algorithm is robust and performs well in presence of occlusions and incorrect segmentations. Motion transforma tion between image frames is computed using the planar and the quadric surface pairings, A least-squares minimization procedure is formulate d 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 s urfaces this is not true. The equation to be minimized is highly nonli near and the uniqueness of solution cannot be guaranteed. The solution obtained computes the motion by extracting unique linear features fro m the quadric surfaces and using them to compute the motion transforma tion, The main contribution of the work is a surface-based framework f or motion estimation from a sequence of range images. The primary issu es of correspondence and motion computation are formulated and solved in terms of the surface descriptions. (C) 1996 Academic Press, Inc.