Combining Sources of Information in Vision I. Computing Shape from Shading and Motion

1. ProceM of image formation

The ability to obtain three-dimensional shape from two dimensional intensity images is an important part of vision. The human visual system in particular is able to use shading cues to infer changes in surface orientation fairly accurately, with or without the aid of· texture or surface markings. The direction of illumination is required to be known in order to obtain accurate three-dimensional surface shape from two dimensional shading because changes in image intensity are primarily a function of changes in surface orientation relative to the illuminant, for many of the surfaces in our visual environment. For the purposes of this paper we use the fol­ lowing simple and universally accepted model. Assuming orthographic projection, if ft is the surface normal at a point o..n the ima~~:e~ surface, Tis the illuminant direction, and f is the flux emitted towards the surl'ace, aild-··w-e· .. ii.ssume a Lambertian reflectance function for the surface, the image intensity function is given by i = pf(J't·1), where p is the albedo of the surface, a constant depending on the surface, and "·"denotes the vector inner product.

2. Motivation and Previoua Work

Most of the work in shape from shading assumes that the albedo of the surface in view and the illuminant direction are known a priori. The only work done on illuminant direction determination is due to Pentland [5], Brooks and Horn [6], Brown and Ballard [7], and Lee and Rosenfeld [8].

It is easy to prove that the illuminant direction cannot be recovered from only one intensity image of a Lambertian sur­ face without other assumptions. In the sequel, we prove that from two intensity images (moving object or moving observer), with the correspondence between them established, we can uniquely recover the illuminant direction, and thence the shape. In this paper we do not deal with the computation of correspondence (retinal motion). We &Blume that it has been obtained by some method such as those described in the recent literature. See [4] for detailed references.

3. Technical Prerequisites

In this section we develop two technical results, one con­ cerning the relationship among shape, intensity, displacements, and the lighting direction, and the other concerning the parameters of a small motion (small rotation) of the shape. We begin with the following theorem.

Theorem 1: Suppose that two views (under rigid motion) of the same Lambertian, locally planar surface are given; let I 1

and I 2 be the two intensity functions. Suppose also that t~e displacement vector field ( u(x,y), v(x,y)), (x,y)EO IS known where n is the domain of the image, i.e. a point (x ,y) in ~he first image moves to the point (x+u(x,y),y+v(x,y)) in the second i~age. If the lighting direction is l = (l 1 ,l 2 ,l 3 ) and the gril.<hent of the surface point whose image is the point (x ,y) is (p ,q ), then the follow­ ing relation holds:

It is clear that equation (1) is local, i.e. it involves the gradient at a point (x ,y) and the displacements around the point (x ,y ), along with the global direction of lighting. Proof: See [4] .

We now proceed to state the following theorem.

Theorem 2: Suppose that the surface S (locally planar) is moving with a rigid motion, and the camera model is the one described in the previous theorem. Let the gradient of the sur­ face (with respect to the first frame) be (p(x,y),q(x,y)). It is known that this motion can be considered as a translation ( dx ,dy ,dz) plus a rotation by an angle (} about an a.xis (n[ +n? +n/ = 1). If the rotation angle (} is small, then the following relations hold:

• (a) The displacement vector field ( u (x ,y ),v(x ,y )) is given by

v(x.tll = dy+Cx-Az{x,![) where A"= n 1 d, B = n2b, C = n 30, and z(x,y) is the depth of the surface point whose projection is the

Proof: See [4].

4. Development of the Motion/Illumination Con­ atralnt

If we let 1/A =a and 1/B = b and B/A = k and use part (b) of Theorem 2 to substitute in equation (1) for p and q, we get the following equation:

Equation {2) is a polynomial in l 1 ,l 2 ,l 3 and b. Considering equation {2) at four points we get a polynomial system of four equations in four unknowns. These equations are independent. This can be formally proved using the Jacobian of the system. A simple but tedious calculation of the Jacobian of this system shows that the Jacobian is non-zero (except in degenerate cases). This means (inverse function theorem), that the func­ tion defined by the equations of the system is locally an iso­ morphism, which means that its zeros are isolated. But from Whitney's theorem, the set of zeros of this algebraic system is an algebraic set and as such it has finitely many components. The conclusion is that the set of solutions of the system is finite (uniqueness). If we now consider equation {2) at five points, we get a system of five equations in four unknowns, which barring degeneracy will have at most one solution.

It is clear from the above discussion that two intensity images of a Lambertian surface, with the correspondence between them established, gives the illumination direction uniquely. In the next section we present an algorithm for the recovery of the light source direction, based on the constraint developed in this section.

5. The Algorithm tor Finding Illuminant Direction

We use the Gaussian sphere formalism (azimuth­ elevation) to represent the vector that denotes the light source direction. More specifically we set

l 1 = cost/>cosO

l 2 =sinO

where (} and 4> are the azimuth and elevation. Now we con­ sider equation (2) at n points in the images, and we get n equations eq 1 , e92, ... , eq" in the unknowns b, 0, t/>. Then the following algorithm gives a solution:

l3 = sint/>cosO

~roof: See [4] .

6.2. How to Utilize the Constraints

Now we show how to utilize the constraints to recover the three-dimensional shape of the object in view, using shad­ ing and motion. It is assumed that the illuminant direction has already been computed using the algorithm described in the previous sections. Up to now, we have developed two con­ straints on shape that also involve the displacements and the illuminant direction. The motion/illumination constraint is a conic in p and q with coefficients that depend on the relative intensities, the displacements, and the illuminant direction (eq. 1). The motion constraint is again a conic in p and q, with coefficients that depend on the displacement vectors ( eq. 2}. Finally, the image. irradiance equation

which determines the intensity I(x ,y) at a point (x ,y) of the image as a function of the shape n of the world point whose image is the point (x ,y ), the illuminant direction T, and the albedo p of the surface, is another constraint on p and q that is also a conic. In the sequel we will call the above constraint the image irradiance constraint. It is worth summarizing at this point that we have at our disposal three constraints on the shape p ,q of a point whose image is the point (x ,y ); each of these constraints is a conic in gradient space. Figure 1 gives a geometrical description of the constraints.

6.3. Computing Shape When the Albedo is Known

When the albedo is known, we have at our disposal three constraints at every image point for the computation of shape:

for all 8

for alli/J

{get n quadratic equations in b. Check if they have a common solution. If yes, out­ put 8,1/J.}

We have implemented the above algorithm and it works successfully for synthetic images. Due to lack of space we do .not describe them. The interested reader is referred to [4].

6. · Computing Shape from Shading and Motion

This section discusses the problem of uniquely determin­ ing shape from shading and motion. Before we proceed, we need some technical preliminaries.

6.1. The Motion Constraint

Theorem 3: With the assumptions and notation of Theorem 1, the gradient (p ,q) of a surface point whose image is the point (x ,y) with displacement vector ( u ,v) satisfies the constraint

the motion/illumination constraint, say F 1(p ,q) = 0; the motion constraint, say F 2 (p ,q) = 0; and the image irradi­ ance constraint, say F 3 (p ,q) = 0. These are three equations, each of degree two, and their system, barring degeneracy, will have at most one solution .

The solution can be easily found by solving the system of equations F;(p,q) = 0, i = 1, 2, 3. But if the input is noisy, since this method is local, i.e. shape is computed at every point separately, we might get results corrupted by noise. To avoid this, we adopt an iterative technique, at the expense of assuming that the surface in view is smooth. We prove, however, that our method will converge to a unique solution . We assume that we know the shape at the occluding boundaries. Because of the fact that gradient space is unbounded, we use stereographic shape coordinates ( €,n ). In this case, all possible orientations are contained in a disc of radius two and (€,n) represents an orientation at the occlud­ ing boundary iff (l + n 2 = 4. Furthermore, assuming that orientations (€,n) with e + n 2 = 4 occur only at the boun­ daries and substituting the values of p and q in terms of e and n from

and

in F;(P ,q) = 0, i = 1, 2, 3, we get equations in ( €,n) that are polynomials in € and n . Let us denote them by G;(€,n,x,y) = 0, i = 1, 2, 3, where fori= 1 we have the motion/illumination constraint, for i = 2 the motion con­ straint and for i = 3 the image/irradiance constraint. The reason why G; is a function of x and y as well (where x ,y are the image coordinates) is that the coefficients in G; = 0 for i = 1, 2 are functions of position in the image plane.

Trying to find a solution that satisfies G; = 0 for = 1, 2, 3 and is smooth, we wish to minimize the functional

where D is the unit square region in the x-y plane (where the image appears) with mesh size m; the surface in view is assumed to have derivatives that are square integrable; and A is a constant (regularization) that weights the relative impor­ tance of the constraints and smoothness. We follow a standard numerical analysis technique, widely used in the area of partial differential equations [9, 10]. We discretize e by using difference operators instead of differential ones and summa­ tions instead of integrals. Let n = k 2 and k + 1 = 1/m. The desired surface is the one that minimizes

and where €; ,j, n; · represent the surface orientation at the regular grid point (im ,jm ). This minimization is subject to boundary conditions, i.e. €; .i, nij are known if ( im , jm) belong to the boundary. We assume that the surface normal at a boundary point ( i ,j) is parallel to the image plane (i.e. aJ + ni~ = 4). We have 888Umed for simplicity and without loss of generality that the boundarv is square. The analysis for a nonsquare boundary is very involved (using finite element methodology), and it will not be .Presented here.

then there exists

at most one solution for the minimization problem.

6.3.1. Learning the regularized algorithm

In the previous section we gave an algorithm for comput­ ing shape, using the actual constraints and the smoothness of the surface in view. The results depend on the choice of the parameter A, and even though any choice of A in a.n interval will result in a convergent algorithm, it does not mea.n tha.t the solutions we will get will reflect the reality (physical plausi­ bility). To achieve this, we would have to train the system with examples, so that the best A is chosen. A method tha.t can be used for this is the cross-validation technique [12]. Another can be found in [13] .

6.4. Computing Shape When the Albedo ia Not Known See [4] .

6.5. Implementation and Experiments

Due to lack of space we do not describe our experimental results. The interested reader is refered to [4] .

7. Conclusions and Future Directions

We have presented a theory of how to compute the illuminant direction and shape uniquely from shading a.nd reti­ nal motion. Our input consists of two intensity images in a. dynamic sequence, with the correspondence between the two frames established. In the pa.st, only the work of Grimson [15] ha.s combined shading with another source of information, in particular stereo.

It is clear from the preceding sections that a. similar theory can be developed when very genera.! (i.e. not only La.mbertia.n) reflectance maps a.re used. It is one of our future goals to extend our theory to reflectance ma.ps tha.t model the illumination due to the sun a.nd sb.