Structure from Motion Without Correspondence: General Principle

STRUCTURE FROM MOTION WITHOUT CORRESPONDENCE: GENERAL PRINCIPLE

Ken-ichi Kanatani*

Center for Automation Research University of Maryland College Park, MD 20742

intersection between the plane and the z-axis, be a reference point. The motion is instantaneously specified by translation velocity (a, b, c) at the reference point and rotation velocity (wl, wz, w3) araund it ~.e., with rotation axis orientation ~wz, w3) and angular velocity l(w1)2 + (wz)2 + (w 3 )2 (rad/sec) screwwise around it). Our goal is to compute p , q, r, a, b, c, w1, wz and w3 from an image sequence without using point-to-point correspondence.

ABSTRACT

A general principle is given for detection of the 3D structure and motion from an image sequence without using point-to-point correspondence. The procedure consists of two stages: (i) determination of the "flow parameters" from "features" without using correspondence and (ii) computation of the 3D structure and motion from these flow parameters. The first stage is done by solving equations of functionals, and the second stage is described in analytical expressions.

I INTRODUCTION

Schemes t o recovery the 3D structure and motion from a 2D image sequence have been studied by many people, e.g ., [1- 6], but most of them are based on the point-to-point correspondence, which requires a large amount of implementation effort. There do exist methods which do not require the correspondence [7 - 9], but they can be used only to trace the motion along time, starting from a given initial information, and the results are obtained only numerically.

In this paper, we present a general mathematical principle to detect the 3D structure and motion without using correspondence. Yet, the solution at particular time is given in analytical expressions, giving geometrical interpretations and proving the existence of the spurious Solution [6], etc . The procedure consists of two stages. First, we extract, without using correspondence, the "'flow parameters" which completely characterize the viewed motion for each planar region of the object. This is done by measuring "features" of the image. The next stage is the computation of structure and motion from these flow parameters, and the solution is given in the form of analytical expressions.

II OPTICAL FLOW AND FLOW PARAMETERS

Take a Cartesian xy-coordinate system image plane and the z -axis perpendicular Consider a plane moving in the scene. Let qy + r be its equation. Let (0, 0, on the to it. z = px + r), the Let (0, 0, - f), the point away from the image plane by f on the negative side, be the viewpoint. A point (X, Y, Z) in space is projected to (fX/(f + Z), fY/(f + Z)) on the image plane. If the point is on the plane z = px + qy + r moving as described above, it induces the following "optical flo~·" at point (x, y ) on the image plane (cf. Kanatani [8, 9]:

* On leave from the Department of Computer Science, Gunma University, Kiryu, Gunma 376, Japan.

where 8 parameters ua, va, A, B, C, D, E and F are given by

In other words, what we are viewing is a very restricted form of motion whose velocities are specified only by 8 parameters ua, Vo, A, B, C, D, E and F. If these parameters are the same, motionb seem identical to the viewer. Hence, our procedure is divided into two stages. First, we will show how to detect the "flow parameters" ua, Vo, A, B, C, D, E and F from an image sequence without using point-to-point correspondence. Next, we will show how to solve simultaneaus non-linear equations (2) for p , q, r, a, b, c, w1, wz and w3 not simply "numerically" but also "analytically ." Here, the "focal length" f of the camera is assumed to be a known constant.

If we take the limit f + oo of a length f, we obtain the following approximation" large focal "orthographic

and if we omit terms of O(l/f 2 ) but retain 0(1/f), we obtain the following Orthographie approximation" terms of "pseudo-

Here, we consider only the planar motion. However, if the object is not planar, we can decompose the object surface image into small planar or almost planar regions by fitting the form of eqns (1) to the observed flow, say by the least square error method. Thus, the subsequent analysis applies to objects of arbitrary shape.

III ESTIMATION OF FLOW PARAMETERS FROM FEATURES

Let X(x, y) represent an image. For example, if the image consists of gray-levels, X(x, y) denotes its intensity at point (x, y ). If the image consists of colors, X(x, y) may be a vector value function corresponding to R, G and B. If the image consists of points and lines, X(x, y ) has delta-function-like singularities. In any case, we define a "feature" F[X ] of image X(x, y ) as a "functional," i.e., a map F(.] from the set of images X(x, y) to real numbers.

Consider the time change when there exists an optical flow (u(x, y), v(x, y )) on the image plane. If X(x, y) is an image at time t, it changes at

time t + öt after a short time interval into

where Xx and Xy are partial derivatives. Then, the corresponding feature F[X] becomes F[X] + DF[X] öt + where in general the "change rate" DF (.] is a "linear functional" in u(x, y ) and v (x, y ). In view of the optical flow of eqns (1), this means that we have a "linear" equation of the form

Here, C1(.], ... , c8 [.] are functionals derived from the given feature F (.], so that they are known functionals. The change rate DF(.] can be estimated by difference schemes. For example, observe an image at time t and compute its feature P(t). Next, observe the image at time t + öt after a short time .interval and compute its feature F(t + öt) . Then, DF[X] is approximated by (F(t + öt ) F(t))/ot or by other higher order difference schemes. Thus, all quantities except uo, Vo, A, B, C, D, E and F in eqn (6) are directly computed from the image sequence without using point-to-point correspondence. Hence, if we prepare 8 or more independent functionals F1 [ .] , F2 [ . ] , .. · , we obtain a set of simultaneaus "linear" equations in uo, Vo, A, B, C, D, E and F of the form of eqn (6) to determine them.

The idea of using feature s was a lready introduced by Amari [10, 11] and Kana tani [7- 9]. However, they did not divide the process into two stages as described here but tried to compute p , q , r, a, b, c , w1, w2 and w3 directly. This leads to a set of simultaneaus "non-linea r" equations, which i s difficult to solve. Kanatani [7 - 9] proposed an iterative method which traces the motion a l ong time, starting from known initial values of p, q and r . Here, however, we divide the pr ocess into two s tages and first determine the "flow parameters," which can be computed by solving a set of "linear" equations. This poses no computational problem. The desired p , q , r, a , b , c , w1 , w2 and w3 are given in terms of the flow parameters as i s shown subsequently.

As for the feature functionals, we can choose those used by Amari [10, 11] and Kanatani [7- 9]. Amari [10, 11] used weighted integral (or "filter") F[X] = JJm(x, y)X(x, y )dxdy of various m(x, y ) over a fixed window for gray-level images. Invoking a mathematics called "stereology," Kanatani [7] used, for textured surfaces, Fourier coefficients of function N(8), where N(8) is the number of intersections, per unit length, between parallel lines of orientation e and the texture on the image plane . When no texture exists and only circumference contours are available, Kanatani (8] used Fourier coefficients of D(8), which is the caliper diameter of the contour measured by two parallel lines of orientation e. Kanatani [9] also used line integral Jm(x, y )ds of various m(x, y ) along the contour and surface integral JJm(x, y)dxdy of various m(x, y ) inside the contour. In any case, a set of linear equations of the form of eqn (6) is obtained, and the flow parameters are determined immediately. However, the accuracy and reliability heavily depends on the choice of the features.

IV STRUCTURE AND MOTION FROM FLOW PARAMETERS

Suppose we have already computed the flow parameters u0, v 0, A, B, C, D, E and F by the method described in the previous section. Or, if the point-to-point correspondence happens to be available, they are immediately determined, say by the least-square-error fitting of eqns (1). What we want is p, q, r, a, b, c, w1, w2 and w3 . First, compute

where i is the imaginary unit, and hence Uo , K and S are complex numbers. Define cornplex variables V = a + ib, P = p + iq and W = w1 + iw2. Then, V, c , P, r, W and w3 are given as follows.

In the case of the orthographic approximation, we get

where e(.) denotes exp(i.), arg the argument and * the complex conjugate. Here, k is an indeterminate scale factor. Thus, (i) the absolute depth r and the velocity c in the z-direction are indeterminate, (ii) an indeterminate scale factor k is involved, and (iii) there exist two types of solutions, one is the true one and the other a spurious one. They are indistinguishable because they yield identical flow parameters. However, if we observe two or more planar regions of the same rigidly moving object, we can pick up the true one because w1, w2 and w3 must be common to all. The fact that an indeterminate scale factor k is necessarily involved was already pointed out by Sugihara and Sugie [5], but the existence of the spurious solution and the explicit forms of eqns (8) have not been known.

In the case of approximation, we get the pseudo-orthographic

where Re[.] and Im(.] designate the real and the imaginary part, respectively. Hence, (i) the absolute depth r is indeterminate, but (ii) a/(f + r) , b/(f + r), c/(f + r), p, q, wl, w2 and w3 are uniquely determined.

In the case of the pure central projection, we obtain

Here, P and Ware given as functions of c', and c' is determined from eqn (11). Eqn (11) is proved to have only one non-zero solution. Since the uniqueness of the Solution is guaranteed, a simpliest solution metbad is to assume an appropriate value of c' = c/(f + r), say by the pseudo-orthographic approximation (9), compute the right-hand side of eqn (11) and repeat the process, using the new value of c', until convergence. We see that (i) the absolute depth r is indeterminate, (ii) a/ (f + r), b/(f + r) and c/(f + r) are uniquely determined and (iii) there exist two sets of solutions for p , q, w1 , w2 and w3, one is the true one and the other a spurious one, and they are indistinguishable because they yield the same flow parameters. The spurious solution is eliminated by observing two or more planar regions of the same rigidly moving object because wl, w2 and w3 must to be common to them.

Numerical schemes of recovering 3D structure and motion from point-to-point correspondence pairs have been known [1- 4], and the existence of the spurious solution was pointed out by Longuet­ Higgins (6]. However, analytical expressions like eqns (10) and (11) have not been known. The parameters of eqns (7) have physical meanings: Uo "translation," T "divergence," R "rotation," S "shearing," and K "fanning." They are transformed by a coordinate rotation by 8 an the image plane as

i.e., Uo and K (as well as V, P and (relative) invariants of "weight" "vectors"), S is an (relative) invariant.of - 2 (or a "tensor"), and T and R (as well as and w3) are (absolute) invariants of weight "scalars"). W) are 1 (or weight r, c 0 (or