Is What You See What You Get?

1. MOTIVATION

How much information about the shape of an object can be inferred from its image? We are interested in a special aspect of this question: the reconstruction problem, which is to determine the shape of an object from measurements of the light reflected from its surface. Our work is based on Horn's thesis.' He formulated a set of conditions (which are discussed in the next section) which lead to a relation be· tween the perceived brightness of a small patch of a surface and its normal vector. This relation, the image irradiance equation, is a first order panial differential equation (abbre­ viated in the following by FOPDEl and each of its solutions determines the shape of an object. The problem of finding solutions to the image irradiance equation is referred to in the literature as the shape from shading problem.

We will take two approaches towards finding a solution to the shape from shading problem termed as the local and the global approach. By the local approach we mean that only a small patch of an image is used to determine the shape of a surface. To the contrary, in the global approach we ex­ amine images in which a silhouette can be detecte4 (here we refer to the outline of an image as a silhouette).

Intuitively, it seems clear that by looking at an image in which a silhouette can be identified we should be able to conclude more about the shape of a surface whose image we are analyzing than by just looking at a little patch. We will show that from cenain images which contain a silhouette we can uniquely infer the shape of the surface which gives rise to that image. Unfortunately, the global approach is not always satisfactory; there are also many images containing silhou­ ettes which could be the images of infinitely many different surfaces. There are also infinitely many surfaces which local­ ly look the same. So we will determine conditions under which the global approach is better than the local approach. Notwithstanding, one can sometimes draw interesting con­ clusions about the shape of surfaces which give rise to the same image by just looking at a small patch of this image.

The local approach is taken to an extreme when we pose the following question: What can be deduced about the shape of a surface from so-called singular points of an image irradiance equation? At these points the surface normal to all solutions to such an equation is· uniquely determined by the brightness there. We investigate the above stated ques­ tion for a cenain class of image irradiance equations, the so­ called eikonal equations, which describe a variety of physical phenomena. For instance, experimental data suggest that the flux of secondary electrons in a scanning electron micro­ scope can be described by an eikonal equation. 2 By using these secondary electrons to modulate the appropriate de­ vices, an image of a surface is created by the microscope.

Such an image exhibits shading (Ref. I) and therefore to de­ termine the shape of a surface from its image one effectively has to solve an eikonal equation. In the case of eikonal equa­ tions, we show that the absolute value of the Gaussian curva­ ture at a singular point of all surfaces which give rise to a particular image, is the same. Furthermore, assuming that the surface is convex at a singular point, we show that its shape can be uniquely,determined in some neighborhood of such a point from the image intensities alone.

The other aspect of the shape from shading problem which we explore is its solution when the image contains a b­ silhouette (which is defined below). In this case a global ap­ proach is taken. Let us first define the bounding contour of a surface: a point Pis on the bounding contour if the line con­ necting the viewer and P grazes the surface (i.e., if this line lies in the tangent plane of P ). Furthermore we assume that no two parts of a surface obscure each other, i.e., we assume that the bounding contour is not an occluding contour: The image (assuming orthographic projection) of a bounding contour will be called the b-silhouette. The surface normal at a point on a bounding contour is parallel to the normal vec­ tor to the b-silhouette and both vectors lie in the same plane. Thus, some or all of the first order partial derivatives of the function defining the surface are infinite for points on the bounding contour (we will say that some components of the surface gradient are singular along a curve).

For example, the bounding contour of a hemisphere lying on a plane is a circle. Consider a Lambertian surface, which has the property that each surface patch appears equally bright from all viewing directions. If we look at a Lambertian hemisphere such that the viewer and the light source are at the same point, its b-silhouette can be deter­ mined from its image. In this case the image irradiance equa­ tion describing the imaging situation is singular and all the su~!lces which satisfy such an eQuation h~v~ a bounding contour. (In Sec. 4 we extend the notion of a singular func­ tion to equations.)

As the image irradiance equation is a FOPDE, it does not, in general , provide enough information to solve the re­ construction problem uniquely. It remained an open ques­ tion whether there are any imaging situations for which ev­ ery surface gives rise to a different image. As indicated before, taking the global approach towards finding a solu­ tion to the shape from shading problem allows us to answer this question affirmatively by proving a uniqueness result for a class of eikonal equations.

2. THE SHAPE FROM SHADING PROBLEM

We ··assume that the reader is familiar with the Shape from Shading Problem (Ref.3). We will denote the orientation o f a patch of a surface by its gradient (p,q,-1), where p and q are the first order partial derivatives of z with respect to x and y , The image irradiance equation is denoted by R(p,q)=E(x,y).

Unless otherwise stated, we will assume that the functions R (p,q) and E(i.y) are C 1 · We will refer to image irradiance equations of the form

as eikonal equations.

In general, at a point (x.y) in the image plane, the gradi­ ent is constrained by an image irradiance equation to a one­ parameter manifold. Only at so-called singular points does the measured image intensity uniquely define the surface normal there and we will investigate such points further. We now give some relevant definitions.

Definition: Let R (p,q) = E (x.y) be an image irradiance equation. Then a point (x 0 , y 0 , p 0 ,q 0 ) is a critical elemenrif (x 0 , y 0 ) is a stationary point of E (x.y) and ( p0 ,q0 ) IS a station­ ary point of R ( p,q).

The point (x 0 , y 0 , p 0 ,q 0 ) is a critical point of the image irradi­ ance equation if it is a critical element and if the values (x 0 , y 0 , p 0 ,q 0 ) satisfy the image irradiance ~qua~lon . . . The point (x 0 , y 0 , p 0 ,q 0 ) is a singular point1f 1t IS a cnucal point for which the values ( p 0 ,q 0 ) are uniquely determined by

the values (Xo.Yol·

A point Pis an isolated critical element if in some neighbor­ hood of it, it is the only stationary point of E (x.y) andR ( p,q). Isolated critical (singular) points can be defined similarly.

3. SINGULAR POINTS

The question addressed in this section is: How ~uch information about the shape of a surface can one obtatn from a singular point of an eikonal equation? To obtain our results we will impose some technical conditions upon E (x.y) and thus define constrained eikonal equations.

Definition: An eikonal equationp 2 + q 2 = E (x.y) is con­ strained if E (x.y) is a C 3 function satisfying the fo)lowtng conditions in some neighborhood of the point (Xo.Yo) :

• (I) (x 0 .y 0 ) is a stationary point of E (x.y),

1. E (x.y) > 0 for (x.y)7'(x0 ,Yo),
2. E (x.y) vanishes precisely to second order at (Xo.Yol·

Let us discuss these conditions a bit further. Since the reflectance map of an eikonal equation is R ( p,q) = p 2 + q 2 , the point P = (x, y, p,q) = (x0 , y0,0,0) is a critical point of a constrained eikonal equation, whence it follows from condi­ tions 2 and 3 that Pis an isolated singular point. By using a suitable linear transformation we may assume, without loss of generality, that the point (0,0) is the stationary point of E (x.y) . We will denote the (limited) Taylor series expansion of E(x.y) as

E (x.y) = a.x 2 + {3xy + r/ + O((lxl + lYWJ. (3.2) Since E (x.y) is assumed to be positive near the origin,

(3.3) defines a positive bilinear form. Thus the subsequent in­ equality (Ref. 5, p. 182) holds:

Moreover, a and r must be positive.

The first result which we prove in this section is formu­ lated in the following theorem.

Theorem: Let p 2 + q 2 = E (x.y) be a constrained eikonal equation. Then there exists a unique locally convex solution in some neighborhood of the singular point. The theorem can be expressed in other words as: If z = z(x.y) fines the other. Hence this result can: be viewed as a unique­

defines one locally convex solution, then i = - z(x.y) de­ ness result modulo the concave/convex ambiguity. To sim­ plify subsequent discussions, we will say that z(x.y) is a locally convex solution to a constrained eikonal equation if it satisfies the followingpositiuity conditions in some neighbor­ hood of the origin:

• (I) z(O,O) = 0,
• z(x.y)EC 2 ,

(3) z(x.y);;.O.

(3.4)

(3.5)

Lemma: Let p 2 + ·q 2 = E {x,y) be a constrained eikonal equation. If a locally convex solution exists in some neigh­ borhood of the singular point, then it is swept out by quasira­ dial characteristic curves.

Proof of theorem: We have to show that a locally convex solution to a constrained eikonal equation exists and is unique. This is achieved by showing that the unstable mani­ fold is the locally convex solution. It follows from the pre­ vious lemma that if such a solution exists, it is swept out by quasiradial characteristic curves. To prove its existence, we investigate the linearized characteristic equations of a constrained eikonal equation. An easy calculation shows that the matrix A has two positive ual eigenvalues and two negative real eigenvalues. Thus, we can apply the stable manifold theorem which states that there exist exactly two C 2 manifolds, each of which is swept out by quasiradial char­ acteristic curves {Ref. 7, p. 527 and Ref. 6, p. 242). Hence we can deduce that a locally convex solution exists and is unique. From the node theorem, we get that the solution z = z{x,y) satisfying the positivity condition is the unstable manifold, whereas the stable manifold is the surface defined by i = - z{x,y) .·

In the case where E {x,y) is C ~ we can compute the locally convex formal power series solution as shown in the following lemma.

Lemma: Let p 2 + q 2 = E (x,y) be a constrained eikonal equation where E (x,y) is C ~ . Then there exists a unique, locally convex formal power series solution to this equation in some neighborhood of the singular point.

In the case where E (x,y) is analytic we can show the following lemma.

Lemma: Letp 2 + q 2 = E(x,y) be a constrained eikonal equation where E (x,y) is analytic. Then its formal power se­ ries solution is the solution to the equation.

The second main result of this section is formulated in the following theorem.

Theorem: Letp 2 + q 2 = E (x,y) be a constrained eikonal equation. Then at the singular point, the Gaussian curvature of each integral surface has the same absolute value and is determined by the (limited) Taylor series expansion of E (x,y) at that singular point.

Proof Recall that the curvature at the origin, denoted byK, is

Using the Taylor series expansion ( l f E (X , Y l in an eikonal equation, we derive an expres­ sion fonhis curvature in terms of a, {3, and y:

The details of these calculations can be found in Ref. 8 .·

4. 8-SILHOUETTES

As discussed, our goal is to find sufficient constraints such that an image can be interpreted in a unique way when its image irradiance equation is known. We now investigate whether the knowledge of b-silhouettes cari be used to inter­ pret an image and thus study singular image irradiance equations:

Definition: Let R (p,q) = E{x,y) be an image irradiance equation. It is called singular if there exist finite values for x andy denoted by x0 and Yo such that

Note that the b-silhouette consists of such points {x 0 , y 0 ). In this section we will identify three constraints upon an image irradiance equation, one upon the reflectance map, one upon the b-silhouette, and one upon the function E {x,y). If these constraints hold for some image irradiance equation, exactly one surface defined by a C 2 function which satisfies the equation exists.

4.1. Uniqueness theorem

Let

be a singular image irradiance equation. Consider the fol­ lowing constraints upon this equation:

{C2) The b-silhouette defined by w{x,y) = 0 is a closed, smooth curve in the x-y plane. Furthermore, the points {x,y) at which the image irradiance equation is defined lie in the region bounded by this b-silhouette.

(C3) The function E (x,y) has exactly one stationary point (x 0 ,y 0 ) and satisfies the following conditions in some neighborhood of (x0,y0): E (x0,y0) = 0, E (x,y) > 0 for (x,y)# (x 0 ,y 0 ) and E (x,y ) vanishes precisely to second order at (XoJ'ol·

Uniqueness Theorem: Let R ( p,q) = E (x,y) be an image irradiance equation for which constraints C I , C2, and C3 hold and suppose a C 2 integral surface defined by z = z(x,y) of this equation exists. Then the only other solution to the equation is i = - z(x,y).

Proof Let R ( p,q) = E (x,y) be a fixed image irradiance equation for which constraints Cl , C2, and C3 hold. First note that the point P = (x, y, p,q) = (x 0 , y 0 ,0,0) is an isolated singular point of the image irradiance equation. There are then two observations which allow us to prove the theorem. First, as the b-silhouette is a closed curve, an integral surface of the equation has to be compact . Second, from constraints C I and C3 we can deduce that such a surface is convex at the singular point , which allows us to apply results of the pre­ vious section.

4.2. Counterexamples

In the previous section we discussed sufficient con­ straints under which the solution to a singular image irradi­ ance equation is unique. Are these constraints necessary? Although we are not able to answer this question complete­ ly, we now shed some light upon it. In particular, we will try to find the class of image irradiance equations for which most likely there is no set of constraints that assure the exis­ tence of only one global solution.

Image irradiance equations satisfying the constraints of the uniqueness theorem have closed iso-brightness curves, i.e., the curves R {p,q) =care closed. Let us now examine singular image irradiance equations whose iso-brightness curves are not closed. One such image irradiance equation is given by

While constraint C2 holds for (4. ,_), an image irradiance equation whose reflectance map is R ( p,q) = p + q never has a singular point. The_general solution to {4 . ~) is and

where w is any C 1 function.

An'Other example of an image irradiance equation whose iso-brightness curves are not closed is

This equation satisfies constraint C2, i.e., its b-silhouette is a closed and smooth curve. Furthermore the origin is the sin­ gular point of (4.'1 ) and E (x,y) vanishes precisely to second order there although E (x,y) is not positive in the neighbor­ hood of (0,0). One of the solutions to (4.'1) is the sphere

whereas another surface satisfying (4. ~ ) is

where

Recall that constraint C2 expressed the fact that the b­ silhouette is a closed and smooth curve. We now demon­ strate that if the b-silhouette does not obey C2, our unique­ ness result does not hold. An example of an equation for which Cl holds, but whose b-silhouette is not a closed curve, is

Equation (4 . .S ) does not have a singular point. A solution to this equation is

Two other solutions to (4. 5 ) are

Only when the b-silhouette is a closed curve can we deduce that a surface is convex at the singular point, an observation which allows us to prove the uniqueness theorem.· For the following eikonal equation we give two solutions only one of which is convex:

Equation (4 . .S ) has a singular point and it satisfies con­ straints Cl and C3. Two solutions to this equation are

5. CONCLUSION

In this paper, we have investigated the question of how much information concerning the shape of an object can be deduced from its shaded image. Even assuming that ade­ quate data is available to derive an image irradiance equation is insufficient to solve the reconstruction problem uniquely; in general, for a fixed imaging configuration there are many surfaces whic.h have the same shaded image. Thus our goal has been to identify constraints by which the reconstruction problem can be solved uniquely.

We discussed how singular points of an eikonal .equa­ tion constrain its possible solutions. In particular, we proved that for any eikonal equation of a certain type there exists a unique (up to translation in the z direction) positive convex surface which satisfies the equation in some neighborhood of a singular point. ·

However, our ultimate ambition was to answer the fol­ lowing question.

Is there a set of constraints which assure that if an image irradiance equation has a solution, it is unique?

We answered this question affirmatively in Sec. 4. It was shown there that if three constraints on an image irradiance equation are known to fiold, the information about the imag­ ing situation and the surface as captured by this equation allow one to reconstruct the shape of the surface uniquely. Furthermore, one can easily check whether an image irradi­ ance equation satisfies these constraints. It is surprising that our uniqueness theorem holds only when the b-silhouette is a closed curve (constraint C2).

In order to evaluate the usefulness of our uniqueness theorem, we need to know which of the commonly arising image irradiance equations actually obey the above men­ tioned restrictions. In his paper on hill-shading, ' 0 Horn dis­ cusses eighteen different reflectance maps which are applied to solve that problem. Constraint Cl holds for five of those reflectance maps. These equations are of the form

wher:fis a bijection. A reflectance map of the form (5.1) descnbes, for mstance, the situation where the object is Lam­ bertian and the light source and the viewer have the same position. In addition, eikonal equations can be used to auto­ m~tically analyze images taken by a scanning electron mtcroscope.

ACKNOWLEDGMENTS

I would like to thank B. K. P. Horn and R. Melrose for their valuable suggestions and S. M. Trilling for proofread­ ing this paper.