A simple stereo algorithm is presented for determining the three-dimensional position of object points in a scene. In this algorithm two independent measures of similarity, the zero-crossing pattern and the intensity gradient, are combined to improve the matching process. Zero-crossing neighborhoods are classified into 16 possible patterns according to their local connectivity. In the matching process a relaxation method is used to find the best matches. Three constraints are incorporated into a single relaxation process, namely, disparity continuity, figural continuity, and smoothness of the probability of matching.

The motion of a three-dimensional object is determined from a sequence of stereo images by extracting three-dimensional features, establishing correspondences between these features, and finally, computing the rigid motion parameters. Three-dimensional features are extracted from the depth map of a scene. A two-pass relaxation method is developed for matching features extracted from successive depth maps. In each iteration, geometrical relationships between a feature and its neighbors in one map are compared to those between a candidate in the other map and its neighbors to update the matching probability of the candidate. The comparison of the geometrical relationship is based on the principle of conservation of distance and angle between features during rigid motion. The use of three-dimensional features allows one to find the rotation and translation components of motion separately via solving linear equations. Experimental results using several sets of real data are presented to illustrate results and difficulties.

A new three-dimensional object representation scheme called rectangular parallelepiped coding is presented. Rectangular parallelepiped coding is an extension to three-dimensional space of the two-dimensional rectangular coding scheme. It is a volume-based representation of three-dimensional objects constructed from three orthogonal views (silhouettes) of the object using volume intersection method and is coded as a list of rectangular parallelepipeds. The representation is versatile and easily edited. For the objects coded in this representation, the operations of translation, rotation, and scaling are easily performed and the properties of volume, surface, and moments are easily computed. Examples are given for which processing time and storage requirements are examined.