Determining 3-D Motion of Planar Objects from Image Brightness Patterns

1. Introduction

The problem of determining rigid object motion and sur­ face strncture from a sequence of image frames has been the topic of many rccent research papers in the area of machine vision. Mnch of the theoretical work has been restricted to using the optical fiow, the apparent veloc­ ity of brightness patterns in the image. Three types of approaches, discrete, differential, and Ieast-squares, have been commonly pursued.

In the discrek approach, information about a finite number of points is used to reconstruct the motion [3,7,1113]. To do this, one has to identify and match feature points in a sequence of images. The minimum number of points rcquired depends on the number of image frames. In the differential approach, one uses the optical fiow and its first and second derivatives at a single point [8,15] . In thc Ieast-squares approach, the ootical fiow is used at every image point [1,2,16].

In general, to compute the optical fiow, une exploits a constraint equation between the optical fiow and the image brightness gradients. Locally, the brightness variations in time varying images only provide one constraint on the two components of the optical fiow. Therefore, an additional constraint will be requircd to compute the local fiow field. For instance, one may assume that the fiow field varies smoothly [5,6], or that it is locally quadratic [15].

In this paper, we restriet ourselves to planar surfaces where only three parameters are necded to specüy the surface structure. We determine the motion and surface parameters directly from the image brightness gradients, without having to compute the optical fiow as an interme­ diate step.

2. Problem Formulation

Horn and Schunk [6] have derived a constraint equation between the optical fiow ( u, v), the apparent velocity of brightncss patterns in the image, and the spatial-temporal gradients of the brightness patterns (Ex, Ey, Et), when the incident illumination is uniform across the surface. This constraint equation is of the form:

In nractice. the brightness gradients are estimated from the gray Ievels in consecutive imagt: frames using finite difference methods.

Any rigid body motion can be decomposed into transla­ twnal and rotational components. We can either consider the motion of an object relative to a stationary camera, or equivalently the motion of a camera relative to a station­ ary object (navigation). In either case, the relative motion between the object and the camera and the object struc­ ture are to be determined from sequenccs of iniage frames. Let t = (U,V, W)T and w = (A, B, CjT denote the vec­ tors of translational and rotational velocity, respectively (T denotes the transpose of a vector), and Iet the point r = (x, y, 1jT in the imageplane be the perspective projec­ tion of the point r =(X, Y, Z(X, Y)JT on the rigid object. lt can be shown that the optical fiow generated in the im­ age plane by the relative motion between the camera and the obiect is given by[2]:

Substituting equations (2) into (1), and simplüying the re­ sults, we obtain the brightness change constraint equation for the case of rigid body motion:

whcre c = Et, and

Fora planar surface, (r · n) Z = 1, where n = (p,q,r)T is the normal to the surface. Substituting for Z into equation (3) yields:

This is the brightness change constraint equation for a rigid planar object undergoing 3-D motion. We will exploit it to recover the motion and surface parameters.

3. Least-Squares Formulation

Given perfect data, only a few points are sufficient to de­ termine the nine unknowns (three components of w, t, and n)-or rather, eight, since we can only recover the distance to the plane and the translational velocity up to a scale fac­ tor (Equation ( 4) will remain invariant if n is multiplied by a scale factor and t is divided by the same factor). In practice, this constraint equation will not be satisfied at each in1age point due to additive sensor noise, quanti­ zation of the in1age brightness Ievels and finite difference approxaimation used to estimate the brightness gradients. Therefore, a Ieast-squares formulation seems appropriate in developing a robust algorithm.

A suitable choice of surface and motion parameters should minimize some measure of error in equation (4) for every image point. We will formulate the following unconstrained optimization problem:

Find the surface n, and motion parameters w and t, that minimize the expression:

where the integration is performed over the relevant region 0 of the image plane. Necessary conditions for minimizing equation (5) with respect to w, t, and n include:

Performing the indicated differentiations in (6) we get:

These comprise nine nonlinear simultaneous equations that can be solved for the six motion parameters, t and w, and the three surface parameters, n.

4. An Iterative Solution Procerlure

We now present an iterative solution procedure for solving the nine simultaneous equations defined previously. First, some observations about equations (7) are in order:

1. Equation (7a) is linear in w, t, and n.
2. Equation (7b) is linear in w and t, but quadratic in n.
3. Equation (7c) is linear in w and n, but quadratic in t.

Several iterative schemes for solving equations (7) can be considered. The two we have implemented are as follows:

1. Solve the linear equations in (7a) and (7b) for w and t in terms of n , and the linear equations in (7c) for n in terms of w and t in an iterative procedure.
2. Solve the linear equations in (7a) and (7b) for wand t in terms of n, and the linear equations in (7a) and (7c) for w and n in terms oft in an iterative procedure.

The second scheme involves more computation, but con­ verges faster. We will only describe the first scheme here (see [10] for more details on both schemes).

Expanding equations (7), collecting terms, and simpli­ fying the results yield:

where

Given the surface parameters n, the motion parameters w and t can be determined from equation (8) . Similarly, given the motion parameters w and t, equation (9) can be solved for the surface parameters n. Based on these observations, we adopt the following iterative scheme:

1. Start with an initial guess for the surface parameters.
2. Solvc the matrix equation (8) for motion parametcrs.
3. Solve the matrix equation (9) for surface parameters.
4. Evaluate the improvement in the solution tu either go to (2) for tht: next iteration or stop if the solution has not improved.

The solution of equation (8) for w and t can be deter­ mined analytically, and can be written in many forms . For example, if M1 is invertible, we have

Similarily, the solution of equation {9) is given by:

Since all arrays in equations {10) and {11) are either 3 x 3 matrices or vectors of length 3, the solutions for w, t, and n can be determined easily.

5. Implementation

Let us consider the computations involved during one it­ eration. Using tensor notation {implicit summation over repeated indeces), we have:

In the above equations, (cv;), (v;vj), (cs;rj), (rkViBj), and (rkT!SiSJ) depend only on x, y, Ex, Ey, and Et, and so can be integrated over the image once. Therefore, the updating of the coefficients at each iteration only involves 27 multiplications to compute M2, 9 to compute d2, and 42 to compute each of M4, N, and g {note that M4 and N are symmetric). This gives a total of 162 multip)ications per Jteratwn. l"urther, solving equations {10) and (11) for w, t, and n requires a total of 117 multiplications.

This iterative scheme has been implemented and tested for many cases. We will present a selected example in section 7.

6. Uniqueness

Our analytical as weil as simulation r~sults show {see [10] for proof) that there exists at most two solutions that gen­ erate the same optical fiow {The existance but not neces­ sarily the uniqueness of a dual solution has been shown in several papers [4,9,12,14]). The two solutions are related as follows:

where k is any arbitrary constant chosen to scale the sur­ face and translational motion parameters. Note that when the translational motion is perpendicular to the planar sur­ face, a unique solution is obtained. Further, when the component of translationai moiion aiong the line of sighi {Z-axis) is zero, the planar surface for the dual solution is parallel to the line of sight. In this case, the dual solution can be viewed as a degenerate one.

7. Experimental results

In the following example, we will demonstrate the sensi­ tivity of the scheme to the initial condition. The image brightness function was generated using a multiplicative sinusoidal pattern { one that varies sinusoidally in both x and y directions), a 45° field of view was assumed, and the brightness gradients were computed analytically to avoid errors due to quantization and finite differencing of bright­ ness values {In practice, the brightness values in two image frames are discretized first, and are then used to compute the brightness gradients using finite difference methods). Table 1 shows the results of two tests using different initial conditions. In each case, the algorithm converges to one of the two possible (true or dual) solutions. The results show that the error in each parameter after less than 30 iterations is within 10% of the true value.

In similar tests, with various motion and surface pa­ rameters, accurate results have been obtain.ed in less than 40 iterations with a variety of initial conditions. More im­ portantly, the algorithm eventually converged to one of the two possible solutions. The results havf' not been as satisfactory for the particular case where the translational motion component i~ ( almost) perpendicular to the planar surface {The solution is unique in this case). In these cases, several hundred iterations were required to achieve reason­ able accuracy. It appears that the behavior resembles that observed when the Newton-Raphson method is applied to a problem where two roots are very close to one another.

8. Summary

The problem of recovering the orientation of a planar sur­ face and its motion from a sequence of images was inves­ tigated and formulated as one of unconstrained optimiza­ tion. Using conditions for optimality, the problem was reduced to solving a set of nine nonlinear algebraic equa­ tions and an implemented procedure based on an iterative scheme for solving these equations was presented. Through a selected example, it was shown that the algorithm could cunverge to either of two possible solutions (or the only SO­ lution when the translational motion vector is perpendicu­ lar to the surface). In practice, once a solution is obtained, the dual solution can be computed from equation {13). In several other cases tested, solutions with good accuracy have been obtained after 10-40 iterations.

9. Acknowledgments

This report describes research done at the Artificial lntel­ ligence Laboratory of the Massachusetts Institute of Tech­ nology. Support for the Laboratory's Artificial Intelligence research is provided in part by the System Development Foundation.

Table 1. Test Results for a Selected Example

True Rotational Motion

True Tran~lational Motion

1'ruc Surfacc Parameters

Dual Il.otational Motion

Dual 1'ranslatioual Motion

Dual Surfacc Parametcrs

Initial Guess A = .003 D = .001 C = -.01

U = .0005 V = -.005 W =.0125

p = .2

q = .4

r = 1.

A = .013 D = -.001 C = -.0112

U = .0025 V = .005 W = .0125

p = .04 q = -.4 r = 1.

p = -.5 q = -1.5 r= 1

Initial Guess p == -10( q== -5

r==1

Note that without loss of gencrality, we have set r = 1, since the distance to the plane and the translational motion component can only be recovcred up to a scale factor.

10. References

• [1) Adiv, G. , "DPt<·rmining 3-D Motion and Strurtnre from Op­ t.ical Flow G<'llcrat.cd by Scveral Moving Obj<'rt.s," COINS TR. 84-07, Computer aud luformation Sricm·<·, University of Massachusetts, Amhcrst , MA, April 1984.
• [2) Druss, A.Il.. , Horn, D.K.P. , "Passive Navigation ," Computer Vision, Graphics, and Image Processing, Vol. 21 , pp. 3- 20, 1983.
• [3) Fang, .J .Q., Huang, T.S., "Solving Threc -Dimensional Small­ Il.otation Motion Equations: Uniqucncss, Algorithms, and Numerical R.esults," Computer Vision, Graphics, and Image Processing, Val. 26, pp. 183- 206, 1984.
• [4) Hay, C.J ., "Optical Motion and Space Perception, an Ex­ tension of Gibson's Analysis," Psychological Review, Vol. 73, pp. 550- 565, 1966.
• [5) Hildreth, E.C., The Mcasurement of Visual Motion, MIT Press, 1983.
• [6) Horn, D.K.P. , Schunck, D.G., "Determining Optical Flow," A rtijicial Intelligence, Vol. 17, pp. 185- 203, 1981.
• Longuct-Higgins, H.C., "A Computer Algorithm for Recon­ structing a Scene from Two Projections," Nature , Vol. 293, pp. 131- 133, 1981.
• Longuet-Higgins, H.C., Prazdny, K. , "The Interpretation of a Moving Retina! Image," Procecdings of the Royal Society of London, Series D, Vol. 208, pp. 385- 397, 1980.
• [9) Maybank, S.J ., "The Angular Velocity Associated with the Optical Flow Field Duc to a Single Moving Rigid Plane," Proceedings of the Sixth European Conf erence on Artijicial Intelligence, pp. 641- 644 , September 1984.
• [10) Negahdaripour, S., Horn, D.K.P. , "Direct Passive Naviga­ tion ," A.l . Memo 821, MIT A.l. Lab, February 1985.
• [l.l] Sngihara, K., Sugie, N., "Recovery of R.igid Strnct.ure from Orthographically Projccted Optical Flow," TR 8304, Depart­ meut of Information Science, Nagoya University, Nagoya, Japan, October 1983.
• [12) Tsai, R.Y. , Huang, T.S. , Zhu, W.L., "Three-Dimmsional Mo­ tion Parameters of a lligid Planar Palrh, 11: Singular Valne Decornposition," IEEE Trans . on Acoustics, Speech, and Sig­ nal Processing, Vol. ASSP-30, No. 4, August 1982.
• Tsai, R.Y., Ilnang, T.S., "UniqnenP~~ m1d E~tirnation of Three-Dimcnsional Motion ParamPtPrs of Il.1gid Objects with Curvcd Surfaces," IEEE Tran.~ activns on ]'altern Ana{y,sis and Machine lntelligence, Vol. PAMI-6, No. 1, Jauuary 1984.
• [14) Waxman, A.M. , Ulhuan, S. , "Smfare St.rnct.nrP awl 3-D Mo­ tion from lmagP Flow: A Kin<'mat.ic Analysis," CA!l-TR-24, Comp. Vis. Lab, Cl'ntcr for Automat ion Il.<·search, Univ. of Maryland , Collcg<' Park, MD, OctobPr 1983.
• [15) Waxman, A.M. , Wohn , K. , "Contom Evolntiou, Ncighbor­ hood Ddormat.ion and Clobal Image Flow: Planar Surfaces in Motion," CAR-TR-58, Comp. Vis . Lab, C<·ntcr for Au­ tomation Research, UHiv. of Maryland, College Park, MD, April1984.
• [16) Wohn , K. , Davis, L.S. , Thrift , P. , "Motion Est.irnation Dased on Multiple Loral Constraint~ an<l NonlinPar Smoothing," Pattern Recognition, Vol. 16, No. 6, pp. 563-570, 1983.