On the computation of motion from sequences of images-A review <s> Z' Z0 <s> Abstract Depth information can be great value in the analysis of scenes of three-dimensional objects. A stereo pair of images allows extraction of such depth information. Use of a number of progressive, closely spaced views has the advantage of reliability over the use of just two views for stereo, and potential savings of computational effort. Such progressive views are naturally available in many applications; such as for a moving robot vehicle, pictures taken at different times in the flight of an aircraft, and for industrial parts placed on a slowly moving conveyor belt. Experimental results on laboratory scenes, including average error and speed of execution, are presented. <s> BIB001 </s> On the computation of motion from sequences of images-A review <s> Z' Z0 <s> Stereopsis and motion parallax are two methods for recovering three-dimensional (3D) shapes. Theoretical analyses of each method show that neither alone can recover rigid 3D shapes correctly unless other information, such as perspective and vertical disparity, is included. The solutions for recovering rigid structure from motion have a reflection ambiguity; the depth scale of the stereoscopic solution will not be known unless the fixation distance is specified in units of interpupil separation. (Hence the configuration will appear distorted.) However, the correct configuration and disposition of a rigid 3D shape can be recovered if stereopsis and motion are integrated, for then a unique solution follows from a set of linear equations. The correct interpretation requires only three points and two stereo views. <s> BIB002
tance from the origin. The image coordinate system (x, y) From  have devised a method for deterequations in eleven unknowns and is thus overdetermined. mining the instantaneous axis of translation for a camera The optic tlow and its derivatives are available using any of undergoing general motion. Their method is based on the the methods outlined in the previous subsection. The overobservation of Longuet-Higgins and Prazdny [101] that two determined system (4.22) may. hence, be solved to yield the surface points which lie on the same ray of projection but structure and motion parameter,. at different depthswill have image velocities that differonly ,Manv interesting observations may be made regarding by the difference in the translational components of their the above equations. Note from (4.21) and (4.22) that Z, is 3-D velocity. Difference vectors are computed at optic flow not recoverable and only scaled translational velocity and discontinuities and the intersection of thesedifference veccurvatures may be computed. Every nonlinear term in (4.22) tors are estimated via an optimization technique similar to is a product ot a structural parameter and a translational that used in [1091. The translational axis is specified by this \elocitv component. Every curvature parameter in (4.22) is procedure and the computation of camera rotation arid multiplied by a component ot translational velocity (V' or translation is simplified. V') which is parallel to the imagt plane. Hence, if there is Prazdny[1111proposed an approach inwhichthevelocity no translation parallel to the image plane, surface curvafield is decomposed into rotational and translational comtures cannot be determined. ponents. The rotational motion is hypothesized and the FOE The nonlinear overdetermined system (4.22) may or may is identified for the resultant translational field. An error not yield a unique solution. Many situations give rise to function of three parameters is used to evaluate the estidependent equations in (4.22) engendering multiple solumated motion. Minimization of the error yields the best tions. A detailed analysis of numerous cases has been preestimate. The algorithm has been tested on data generated ,ented by subbarao  ,[1051 and Waxman eta). [i1021, [ 103] by simulated planar surfaces in motion. %ho have derived closed form solutions for these cases. Bruss and Horn  and Horn [71] discuss the formuSubbarao shows that in general the solution is unique, and lation of an iterative least-mean-squared error approach to at most four soluzions are possible in certain situations, the estimation ot --D motion from optical flow. They make Negahdaripour  also addressed the ambiguity in interno a priori assumptions about the motion. They derive a preting optic flow produced by curved surfaces in motion. system of seven equations, three of which are linear in V', He argues that the ambiguity is at most three-fold for the V', and V', and four which are solved via a numerical case of certain hyperboloids of one sheet viewed by an method. No experimental results, however, have been observer moving parallel to the image. The ambiguities shown. Horn and Weldon  have proposed methods for inherent in interpreting noisy flow fields are discussed by computing purely translational or purely rotational 3-D Adiv  . motion directly from brightness gradients without comAn overview of some of the approaches for computing putingoptical flow. Theyemployontyfirstderivativesofthe structure and motion parameters from optic flow is given image gray levels, and analyticity of the surface is not below. The approaches typically involve restricting the required. Negahdaripour and Horn BIB001 discuss the recovnature of motion to be purely translatory or rotational and/ ery of motion of a camera relative to a planar surface. They or restricting the imaged surface to be planar. These also do not compute optic flow, and use instead the spatial assumptions significantly reduce the complexity of the sysand temporal derivatives of brightness values directly. They tem of equations (4.22) . presen* iterative schemes for solving nine non-linear equaWilliams  considered the computation of the structions based on a least-squares formulation, and also preture of imaged scene components for the situation where sent a closed form solution. the sensor was involved in purely translatory motion. The Chou and Kanatani  use a scheme in which object Focus of Expansion (FOE) of image flow is assumed known motion is initially hypothesized and iteratively refined. They and the scene is considered to consist of planar surfaces. extract features from the images obtained before and after A height and position is hypothesized tor each segmented motion. They do not require that feature correspondence region. An image is generated for the known camera motion be established a priori. [hey transform the first set of feaand compared with the actual image. Error in the hypothtures and evaluate the discrepancy between the estimated esized structure is computed from the difference between feature positions and the true feature positions (in the secthese two images and appropriate corrections are made to ond image) aftcr motion. Assuming infinitesimal motion, the hypothesized scene structure. This procedure is they relate the discrepancy to optic flow parameters. They repeated until the error falls belo v a threshold. This use a numerical least-squares technique to solve the linear approach has also been suggested for detecting the FOE. constraints for a better estimate of the motion. This process An approach for determining scene structure from a is repeated until the estimated motion produces feature sequence of images acquired by a translating camera is positionsthataresufficientlyclosetothetrueonesobtained credited to Lawton  . In this method, features are in the second image after motion. extracted from each image. Several directions of camera In this section we have presented the optic flow approach motion are hypothesized. Each corresponds to a unique for the estimation of motion parameters from a sequence FOE or FOC. Image featuredisplacementsarecomputed for of monocular images. We discussed the basic formulation each motion and compared with actual displacements. The of the problem and outlined some of the recently develmotion corresponding to minimum error in feature disoped techniques for computing the optic flow. The above placements is chosen to be the best estimate. Scene strucdiscussion included the problem of inferring 3-D structure and motion from optic flow and overviews ot some of the Sensitivity to noise is also a problem with the feature solutions to this problem. based techniques though to a lesser degree. The techniques reported in the literature have all been only marginallytolerant tonoise. One methodof decreasing the sensitivity to noise has been to use more than the required In the preceeding se(tions ,,e dis(cu,,,ed two distinct minimum number of features in an iterative least-squares approaches tor the estimation of motion trom monocular technique. Although this usually has a smoothing effect, it image sequent es i.e., feature-based analvsis and optical can cause additional complications. For example, if all the flow, methods. In this section we compare the two additional points chosen are coplanar, then all that has been approaches and discuss some ot the advantages and disachieved is a significant increase in the computation time advantages associated with each of the methods, and probable instability of the solution. The establishment Feature-based approaches require that correspondence of correspondence also becomes computationally expenbe established bet,,'een a sparse set of features extracted sive. from one image with those extracted from the next image Recently, Verri and Poggio [1181 argued that theoptic flow in the sequence. Altho)ugh several methods have been disdoes not correspond to the 2-D velocity field unless very cussed tor extracting and establishing feature corresponspecial conditions are satisfied. They argue against the use den( e, the task is difficult and only partial solutions suitable of optic flow for quantitative estimates of 3-D motion. They for simplistic situations have been developed. In general, apply the theory of stability of dynamical systems to the the process is complicated by occlusion which may cause optic flow formulation and (onclude that theoptic flow may features to be hidden, false features to be generated and provide stable qualitative information such as the Focus of hidden teatures to reappear. Much more work needs to be Expansion and motion discontinuities. (lone in this area before the advent of one or more general When numerical techniques are used tor the solution of techniques that (-an be reliably applied to real imagery. In structure and motion using either approach one must concomparison, the optic flow approach, in general, does not sider the many caveats involved in such a solution. A disrequire any weature correspondence to be established. cussion of these caveats would be inappropriate in this The computation of the optical flow as well as the interpaper and the reader is directed to the literature in numerpretation of motion and structure from optic flow requires ical analysis for possible pitfalls and remedies. the evaluation of first and second partial derivatives of Much attention has been devoted recently by the comimage brightness values and also of the optic flow. Real puter vision community to the use of regularization techimages are, in general, noisy. The evaluation of derivatives niques in many vision tasks including both feature-based is a noise enhancing operation. The higher the order, the formulations and the optic flow approach for motion and more noise sensitive is the derivative. Hence, even in cases structure estimation [119]- [123] . This technique is used to where closed form solutions for the 3-D structure and reformulate certain ill-posed problems into well-posed motion exist, the optical flow techniques do not produce problems. The ill-posed problems are those forwhich either usable results because of the sensitivity to noise [71] . Also, 1) the solution exists but is not unique, or 2) the solution there are discontinuities in theoptical flowdepending upon does not depend continuously on the input data. Regularocclusion, and these regions must be detected reliably othization is typically formulated as an error minimization and erwise violations of the continuity assumption will have involves a stabilizing functional that is applied to the input adverse and global effects on the estimate of optical flow. data and perhaps an additional smoothing parameter. Due In contrast to the method of global minimization, another to the seemingly infinite choiceof possible stabilizing funcapproach depends upon solving a set of constraints in a tions and smoothness parameters it is difficult to specify a small neighborhood. However, the local and global methbest regularizing algorithm for an application. ods rely on similar assumptions of smoothness of optical flow field. The common weakness of both methods is the VI. COMPUTING MOTION FROM A SEQUENCE OF STEREO inaccurate estimates at points where the flow changes IMAGFS sharply or is discontinuous. The global method propagates the errors across the eiiht c image, w-hile the neighborhood The technique described in the previous sections detersize limits the propagation in local methods. Schunck [701 minethemotionand structureofanobjectgiven a sequence and Kearney et al. [116] ,  address these difficulties in of monocular images of the scene. It was seen that in both detail. Kearney et al. present a detailed analysis of the the feature-based methods as well as in the optic flow techsources of errors in local optimization techniques for comniques, the solutions for structure and motion remain puting optical flow [116] . They identify three main sources ambiguous with respect to absolute value of distance of error: between the camera and the scene. In other words, structure and motion parameters are unique only up to a scaling 1) Poor estimation of brightness gradients in highly texfactor. The use of stereoscopy can provide this additional tured image regions.The problem is especiallysevere parameter to uniquely determine depth and hence absofor temporal gradients in moving regions. lute values for the structure and motion parameters. 2) Variations in optic flow across the image violate the The fusion of stereo and motion may be effected with assumption of locally constant flow. Significant error different objectives in mind. Stereoscopic processing may arises t discontinuities in the flow field. be used to aid motion recovery, or con ',rsely, motion anal-3) Insufficient local variation in the orientation of the ysis may be used to help establish feature correspondence brightness gradient which causes error propagation in stereo image pairs. The fusion of these two processing in the ill-conditioned system. modules in human and other biological visual systems has been detected via neurobiological and psychophysiologiparameters that yields the lowest error is chosen. Although cal investigation [124],  . Recent research in both the the solution of the system ot linear equations is easy, the feature-based and optic flow based approaches has estimation of large sets of motion parameters and espeaddrL.,t,, t ie tusion or ,tereosccpic analysis and motion cially the search for the best set of motion parameters is estimation. We outline the salient features of such effort. computationally intensive. An alternative approach has been to use a least-meansquared error analysis [127] ,  . The underlying principle A. Feature Based Anah'sis here is again the invariance of distance between points on The overall analysis consists of the following steps: i) From an object subjected to rigid motion. The formulation is analthe sequences of stereo images, the depth map tor each ogous to the approach followed by Magee and Aggarwal stereo pair is determined, ii) the correspondence between [1301,  for determining motion parameters from three-dimensional features in successive depth maps is sequences of range images. While the direct method of established, and iii) the motion of the objects is computed solution is adopted in  ,  , a two-part iterative based upon the matched features. This formulation of approach is adopted in [127] . The displacement between motion analysis based on sequences of stereo images has the centroids of two sets of registered 3-D points is used several advantages and disadvantages which are briefly disto determine the translation vector. The rotation matrix is cussed below, decomposed into three factors corresponding to rotations Kim and Aggarwal discuss the estimation of motion aboutthez, x, andyaxes. Eachoftheseisindividuallysolved parameters trom a sequence of depth maps extracted from for while the other two are fixed. This is repeated in a cyclic stereo images [63] . The depth map for each stereo pair is manner until a least mean squared error criterion is satcomputed using an edge-based stereo algorithm. 3-D feaisfied. The advantage of the above decomposition is that tures (consisting of lines and points) are extracted from each the 3-D estimation problem reduces to a set of 2-D problems depth map. These features are matched between succeswhich are more tractable. sive depth maps using a two pass relaxation process [61], The above approaches consider the determination of  . In the process of extraction, search and matching, the structure and motioii as separate issues. Hence, if structure search space is limited to the areaofthe motion in the image is first computed (as is usually the case for stereo imagery) by an image differencing technique. then errors accrued due to quantization of disparity will In general, correspondences between two 3-D lines continue to plague the estimation of motion. To alleviate extracted from one depth map and those from another may this problem a new approach has been developed by Kiang, be used to determine the motionofa rigid object, assuming Chou and Aggarwal [132] based on iterative refinement of that the motion is small. Here, a three-dimensional line is both structure and motion estimates. The approach is based specified by a three-dimensional direction and a point on on a 1-D model for triangulation error in stereoscopy. The the line. The same method can be used for three-dimenstrategy for modifying structure and motion estimates is sional point correspondences since two points determine based on the structural relationship between the correa line. In general, three point correspondences, or one line sponding uncertainty polyhedra in successive depth maps. correspondence and one point correspondence are suffiExperimental results using synthetic as well as real data cient to determine the three-dimensional motion pararndemonstrate significant improvement in the estimation of etersof a movingobject. In the formercase, the three points both structure and motion when cempared to the convenshould not be collinear, and in the latter case, the point tional techniques based on reducing least-mean-squared should not lie on the same line. A system of linear equations error in motion alone. is derived and the solution is straightforward. A system Aloimonos and Rigoutsos  have developed a scheme based upon these observations has been implemented to for computing 3-D motion parameters from a sequence of derive the structure and the displacement of the objects stereo imagery which does not require a priori establishbetween the views. In this study the motion of simple toy ment of correspondences. The features extracted from the objects was estimated with excellent results [63] . left and right images are assumed to lie on a planar surface Although it is theoretically quite easy to estimate the Z = pX + qY + c. Perspective imaging geometry is motion parameters given the correspondence between two assumed. The image planes are parallel to the X -Y plane. sets of 3-D points, practical considerations complicate the The parameters p, q, and c are acquired by solving a set of implementation of the system. In stereo imagery, the range linear equations in which the coefficient of each of the values estimated are subject to a great deal of uncertainty unknowns consistsof a function of a sum of the imagecoordue primarily to quantization of disparity. More robust fordinates. The solution of the linear equation provides the mulations of the problem of motion estimation using structure of the scene. Applying this process before and sequences of stereo images have been proposed [126-[128] . after the planar surface undergoes motion allows for the One approach has been to estimate motion parameters via estimation of the motion parameters. The method devela system of linear equations using 3 points in each depth oped was not as robust as was expected and was modified map  . Several sets of 3 points are chosen from the large by including a third camera. The performance of the algonumber of available points and the motion parameters are rithm in presence of noise is described in  . computed for each set. For each set of computed motion Another technique forestimating 3-D motion parameters parameters, all available points in the first depth map are from two 3-D point sets without establishing corresponsubjected to the estimated motion. The discrepancy dence has been presented by Lin et al.  . The algorithm between the points in the second depth map and transis based on the property that a function and its Fourier formed points from the first depth map is computed via a transform must experience the same rotation. The transsimple distance measure. The set of estimated motion lation is first determined from the displacement of the cen-troid. Two functions are defined on the feature set. A corits anu demerits of both approaches were discussed. An relation between the Foui'er transforms of these functions overview of the fusion of stereoscopy and motion analysis, -is determined. The rotation axis and angle are computed especially for aiding the estimation of motion, was prebased on this procedure. Some simulation results have been sented. presented  . The optic flow approach consists of computing the twothe above techniiques are representative of the dimensional field of instantaneous velocities of brightness approaches wherein stereopsis aids the recovery of motion, values (gray levels) in the image plane. Instead of considThere exist many reports in recent literature discussing the ering temporal changec it, image brightness values in comuse of motion in recovering structure, e.g., Jenkin  tial derivatives to the image brightness values. Ineithercase, known motion parameters to simulate stereo. We feel that a relatively dense flow field is estimated, usually at every although this approach is related to the estimation of pixel in the image. The optic flow is then used in conjuncmotion, it is a separate field in itself. Hence, we do not purtion with added constraints or information regarding the sue any further the discussion of the use of known motion scene to compute the actual three-dimensional relative to aid stereopsis, and we limit our discussion to the use of velocities between scene objects and camera. stereoscopy for estimation of motion. The feature-based approach is based on extracting a set of relatively sparse but highly discriminatory set of two-B. Multiple Optic Flow Fields dimensional features in the images corresponding to threedimensional object features in the scene such as corners, In Section IV we discussed the interpretation of optic flow occluding boundar'es of surfaces, and boundaries demarfields obtained from a sequence of monocular images. cating changes in surface reflectivity. Such points, lines and/ Another approach has been to compute multiple optic f:-)w or curves are extracted from each image. Inter-frame corfields from different views, to establish correspondence respondence is then established between these features. between them and reconstruct 3-D velocity vector fields. Constraints are formulated based on assumptions such as Mitiche  assumes that optic flow is computed for each rigid body motion, e.g., the 3-D distance between two feaview in a stereoscopic imaging system for which the stetures on a rigid body remains the same after object/camera reoscopy parameters are known. He further assumes that motion. Such constraints usually result in a system of noncorrespondence between points in the two images are linear equations. The observed displacement of the 2-D available which allows for the estimation of depth. Mitiche image features are used to solve these equations leading shows that given this information it is posssible to compute ultimately to the computation of motion parameters of the 3-D motion parameters in a straightforward manner. objects in the scene. Waxman and Sinha  have used a similar approach. In In the feature-based approach, the main problems addition, they have filtered the optic flow field to minimize encountered are seen to be: 1) establishing and maintaining the effects of noise. Nagel  has also attempted such correspondence between the image plane features, 2) stereo-motion fusion techniques and has devised an robust formulation of the problem which is usually based approach based on the minimization of an error function. on the assumption that the viewed object undergoes rigid Tsukune and Aggarwal [981 have used this approach for motion, and 3) developing appropriate iterative algorithms reconstructing 3-D velocity fields for a scene containing which are stable and accurate. The optic flow based multiple objects in motion. approach suffers from a different set of drawbacks, i.e., 1) Richards BIB002 demonstrated that the relative rate of it is highly noise sensitive due to its dependence on spatiochange of disparity (ratio between temporal rate of change temporal gradients, 2) it requires that motion be smooth of disparity and disparity) due to object/camera motion is and small thus requiring a high rate of image acquisition, a useful aid in establishing feature correspondence within and 3) it requires that motion vary continuously over the a pair of stero images. Waxman and Duncan  used the image. Both approaches also are affected by object occluratio between relative flow and disparity to aid the estabsion and choice of initial/boundary conditions. The use of lishment of stereo correspondence. The relative flow is sequences of stereoscopic images provides three-dimendefined to be the differ -rce between the optic flow at a sional points and lines which somewhat simplify the probpoint in the left image and that at the corresponding point lem of estimating motion. in the right image. Waxman and Duncan show that their Agreat deal of future research effort is warranted tooverratio is identical to the one devised by Richards BIB002 . come the obstacles mentioned above. The significant contributions made by various researchers in this area during VII. CONCLUSION the recent past is to be noted and this trend may be expected to continue in the future. Two workshops, one in Europe In this paper we have reviewed recently developed tech-  and one in the USA [146] are planned in the near future niquesfor estimating structureand motion from sequences to engender progress in this challenging area. of monocular and stereoscopic images. We discussed two distinct approaches: feature-based analysis and optic flow techniques. We described some of the different mathematical formulations that have been developed for each of The authors wish to thank the reviewers, the editor Dr. these tasks. A comparison of the feature-based and optic H. Li, and Dr. W. Martin for their comments, which helped flow methods was then presented in which the relative merin improving this manuscript.