Recovering Three Dimensional Shape from a Single Image of Curved Objects

1 Introduction

In this paper, we study the problem of recovering the three­ dimensional shape of the visible surfaces in a scene from a single two--dimensional image. We restrict our attention to scenes com­ posed of opaque solid objects bounded by piecewise smooth sur­ faces with no markings or texture on them. By three-dimensional shape we mean a map of surface normal vectors-or equivalently relative depth-along the lines of Marr's 2 !D sketch, Horn's nee­ dle diagram, or Barrow and Tennenbaum's intrinsic images.

The two sources of information about 3-D shape in a seg­ mented image of the class of scenes permitted by us are (a) the line drawing, and (b) the pixel brightness values. Both have been the subject of considerable research in computational vision. Work on line drawing interpretation of scenes containing curved objects has been most successful in qualitative characterization, e.g., in terms of line labels [8] or sign of gaussian curvature [6]. Attempts [1] ha.ve also been made to obtain numerical surface orientation information by making additional assumptions.

Use of pixel brightness values in a single smooth surface patch has been the theme of the shape-from-shading work of Horn and his colleagues [5], [2]. Here the goal has been to solve the im­ age irradiance equation-an equation relating surface orientation to brightness-by supplying the surface normal direction along the

Recovering three dimensional shape from a single image of curved objects

Jitendra Malik

Computer Science Division, EECS University of California, Berkeley

boundary of the patch. It is usually assumed that the reflectance map R(n), which specifies the radiance of a. surface patch as a function of its orientation, is known. For the canonical case of lambertian surfaces illuminated by a point light source, this implies knowing the light source direction. Three-dimensional shape recovery is possible if the patch happens to be bounded by limbs (called occluding contours by some authors) which makes the boundary surface normal calculation easy. No use is made of other kinds of lines e.g. projections of edges(tangent plane discontinuities). Consequently · the approach cannot be directly employed on images of general piecewise smooth curved objects.

The question which can then be posed is-are there any schemee which try to exploit all the information in a segmented image, i.e., both line drawing and shading constraints, in order to recover quantitative 3-D shape. This has been done for the special case of polyhedra. by Sugihara [12]. For scenes containing curved ob­ jects, the problem is significantly harder and Sugihara's approach does not have a natural generalization. To the best of our knowl­ edge there was no method for 3-D shape recovery for the class of curved objects bounded by piecewise smooth surfaces.

In this paper, we develop such a method. The scheme builds upon, and exploits, past work on line drawing interpretation­ specifically the line labelling work of Malik [8], [9],-and the work of Horn and his colleagues on shape-from-shading. A more de­ tailed account of this scheme can be found in [10] .

2 Constraints from a line drawing

In order to study the constraints imposed by a. line drawing on the shape of the scene, it is convenient first to obtain a. qualitative characterization of each line. This is done by associating with it a label from the set{+,-,~,-+,~~,-+-+}. The first four of these labels denote edges which correspond in the scene to the in­ tersections of surfaces with distinct tangent planes. These labels have the usual significance as in the Huffman-Clowes label set for polyhedra. The { ~.:...., -+-+} labels denote limbs which corre­ spond to curves along which the surface curves smoothly around to occlude itself. As one walks in the direction of the twin arrows the surface lies to the right. See Figure 1 for an example.

For curved objects the label can change along a. line as can be seen on edge AB in Figure 2 (section 3.2). We therefore need to distinguish between two different senses of line labelling. A dense labeUing is a function which maps the set of all points on curves in the drawing into the set of labels. The dense labelling problem is to find all the dense la.bellings of a. drawing which can correspond to a. projection of some scene. Currently no algorithm is known for finding the dense labelling of a. line drawing of curved objects using only the information available in a line drawing. In the context of Figure 2, it means that there is no algorithm for exactly locating X, the point of transition from convex to occluding.

Alternatively, we could restrict our attention to sufficiently small neighborhoods of the junctions of the line drawing. For each line segment (between junctions) we now have to specify only two labels-one at each end. Of the 6 2" combinatorially possible label assignments to the n lines in a drawing only a small subset correspond to physically possible scenes. We refer to these as legal sparse labellings. The determination of all legal sparse labellings of a particular line drawing is the sparse labelling problem. Note that the set of legal sparse labellings is always a finite set (usually small).

The sparse labelling problem has been tackled successfully-by Huffman[4] and Clowes [3] for trihedral objects, by Mackworth [7] and Sugihara [12] for arbitrary polyhedra, and by Malik [8], [9] for curved objects.

Line labelling is important precisely because lines with differ­ ent labels correspond to different types of constraints. At limbs one can determine the surface orientation uniquely. It can be shown [1], [5] that n, the unit surface normal, lies in the image plane and is in the direction of Nc -the outward pointing unit vector in the image plane drawn perpendicular to the projection of the limb. See Figure 1.

At an edge, the constraint is weaker. Let e be the unit tangent vector to the edge at a point, and let n1 and n2 be the unit surface normals to the tangent planes to the two faces It and h at the point. Let e be oriented such that when one walks on the edge in the direction of e , the face It is to the left (see Figure 1). Now e is perpendicular to n1 because e lies in the tangent plane to the face ft. Similarly e is perpendicular to n2. Therefore e is parallel to n1 X n2. We do not know the vector e, but from a line drawing we can determine its orthographic projection into the image plane. We thus have the constraint (n1 X n2)proj = A~roj· Here the notation Vproj is used for the orthographic projection of v into the image plane . .>. is a positive scalar if the edge is convex, negative if the edge is concave. Note that this constraint is equally valid for occluding convex edges, where one of the surface normals corresponds to a hidden face.

For later use, it is convenient to develop an alternative version of the orientation constraint. Let N c be a unit vector in the image plane perpendicular to eproi· As (n1 X n2)proj = .>.eproj, it follows that (n1 X n2)proj · Nc = 0. As N~ has no component in the z­ direction, this is equivalent to saying that (n1 X n2) · Nc = 0, or using the vector triple product notation [n1 n2 Nc] = 0.

3 Image constraints on 3-D shape

If the dense labelling of a line drawing is known, the problem of three-dimensional shape recovery can be formulated as that of finding a piecewise smooth function n(x, y) which minimizes the following functional

Here I is the entire image, E the edges, L the limbs, and B the set of all curves (edges and limbs). In the two line integrals s is the arc length parameter along the curve. n1(s) and n2(s) are the two limits of the discontinuous function n(x, y) when a point on an edge is approached on its two faces.

The first term measures the error in satisfying the image · ir­ radiance equation, and the second and third terms measure the errors in trying to satisfy the line drawing constraints. The last term is a 'regularization term' [11], [13] intended to select a par­ ticularly smooth solution.

Note that we have not ensured that the position constraints corresponding to the line labelling are satisfied nor that the re­ sulting n( x, y) is integrable. How this can be done is discussed in [10].

One could find the Euler equation and develop a numerical scheme for minimizing this functional-however that would be a futile exercise as there is no available algorithm for determining the dense labelling in advance. Of course, we could seek to recover the dense labelling as part of the process of finding the shape n(x, y). This leads to a difficult global minimization prohl<>m, which is discussed in [10].

In this paper we develop an alternative approach. While we do not know how to precompute the dense labelling, the set of legal sparse labellings of the drawing can in fact be precomputed using the line labelling algorithm developed in Malik [8]. To exploit this knowledge, we need to formulate the image constraints in a slightly different way.

It is convenient to partition the constraints into the follow­ ing three classes: (a) constraints in the interior of an im?ge area, (b) constraints in the neighborhood of an image curve, (c) con­ straints in the neighborhood of a junction. Surface continuity requirements provide the cross-coupling among the solutions of these constraint sets. In the next three subsections we analyze each of these and develop schemes for local shape recovery.

3.1 Shape constraints inside an area

The only source of constraint is the shading and we wish to find the 'smoothest' surface consistent with the pixel brightness values. This is exactly the shape from shading problem which has been studied by Horn and his colleagues and we can adopt their analy­ ses and algorithms unchanged. Specifically, we use the relaxation scheme suggested by Brooks and Horn [2], section 4.2 .

The Horn-Brooks relaxation scheme, just like the other algo­ rithms for this problem, requires knowledge of the direction of the surface normal along the boundary of the patch. Empirical evi­ dence suggests that knowing the surface normal along a significant fraction of the boundary is adequate in practice.

3.2 Shape constraints along an image curve

At a limb, the surface normal is uniquely determined by the direc­ tion of the projected curve. So the interesting case is that of an edge, where there are both shading and line drawing constraints. We want to use these to determine the surface normals n1(s) and n2(s) on the two faces fi and h as a function of the arc length parameter s along the edge. To do this, we have to measure the brightness values E1(s), E2(s) on the two sides of the edge in the line drawing.

To determine n1 and n2 one has to solve for 4 independent parameters. (While there are 3 components of n, the unit length constraint means that only two are independent.) If the edge is connect (convex or concave), there are two equations due to shad­ ing: E1 = R(nt) and E2 = R(n2)· The direction of the edge gives us one more equation [n1 n2 Nc] = 0, still leaving us one equa,. tion short. It is not possible to solve for nl> n2 by just looking at the neighborhood of a point on an edge, just as in the stan­ dard shape-from-shading problem it is not possible to compute n locally. We need to make use of boundary conditions, and max­ imize smoothness-points which are physically close should have similar surface normals . To do this, we incorporate a 'regular­ ization term' J(n~(s)) 2 + (n~(s)) 2 ds where n~(s), n~(s) are the derivatives of nt(s) and n2(s) with respect to arc length. We thus have the following composite functional

J.'1(s), l-'2(s) are Lagrange multipliers intended to ensure that the normals n1(s) and n2(s) have unit length.

Minimizing this functional is an exercise in the calculus of variations. We have to find the Euler equations, eliminate the Lagrange multipliers and come up with a suitable finite difference scheme. These calculations [10] result in the following scheme for computing n;+I given knowledge of n;-l , ni and n~:

To compute n;+l, we use

Here a = A1/ A3 and ,B = A2/ A3 . If n~, nf, ng, n~ are known, these schemes tell us how to 'grow' the solution. The iteration can in fact be started just given the values of n1, n2 at the initial point . As n~ and n~ are both equal to 0 at the initial point (natural boundary conditions), we assume n~ = n~ and n~ = ng.

It should be pointed out that the analysis in this section has been for connect edges-if the edge is occluding, we do not know the brightness values for the occluded face and thus have one less constraint. For curved objects, an edge can change its label from convex to occluding between junctions e.g. at point X in Figure 2. However we know (8] that such points correspond to invisible limbs, and therefore can be detected by checking if nz is sufficiently small. In Figure 2, n2z = 0 at X. The iterations in (2) and (3) should be stopped at this point.

When n2(s) is known along the edge, it is possible to recover nt(s) even when n1 unknown at initial point. Use Newton's method to compute n1 at initial point. This can be done be­ cause we now have two constraints on n1 viz. Et = R(nt) and (n1 n2 Nc] = 0. As these constraints are non-linear, there is no guarantee of a unique solution. However it can be proved that for a reflectance map arising from a lambertian surface illuminated with a point light source, there can only be one or two solutions. We use the iterative scheme in (2) above to propagate each of the

solutions, and pick the one which corresponds to the smaller error as measured by the functional in (1).

3.3 Shape constraints at a vertex

At a vertex we have (a) shading constraints from the brightness values on the faces which meet at the vertex, and (b) line drawing constraints from the projections of the edges incident at a vertex. Under certain conditions, there are enough constraints to uniquely determine the surface normals on each of the faces purely from the local information.

Consider vertex A in Figure 3 and enumerate the constraints on n1, n2, and n3. There are 6 independent parameters (2 for each surface normal) and 6 independent equations (3 from brightness values on the faces, 3 from the directions of the projections of the edges). There are as many independent equations as unknowns. As the equations are nonlinear, we are not guaranteed a unique solution. However, pruning using our additional knowledge about the three edges being convex or concave typically leaves us with only one solution.

It can be seen that the method described above works for any vertex with n ;::: 3 faces if and only if they are all visible. If any of the faces at the vertex is hidden, the constraint due

to the brightness value on that face is missing, and there are fewer equations than unknowns. However if there is exactly one hidden face, and the surface normal on one of the faces at the vertex is known (perhaps by propagation of information on one of the faces/edges that it lies on), then the number of independent equations again becomes equal to the number of unknowns and one can solve for the rest of the surface normals. In Figure 3, once n4 is known, ns and n6 can be determined.

4 Global Shape Recovery

In sections 3.1-3.3 we studied the constraint sets for image ar­ eas, curves and junctions, and developed numerical schemes for local shape recovery. In [10), we show how these combine to form a global shape recovery algorithm. Here we will illustrate this algorithm on two examples.

The hatched parts of the figures denote what has been freshly computed in a particular iteration. In figure 4, the computation starts with determination of the surface normals to the three faces at A, using the vertex shape recovery procedure, followed by the computation of the surface normals along AB, AC and AD using the edge shape recovery procedure described by the equations (2) and (3). This generates the boundary conditions needed for

applying the Horn- Brooks shape from shading algorithm to each face. In figure 5, the first two stages are self-evident, and the third stage makes use of the procedure for computing n1 ( s) given n2(s) along the edge described in the last paragraph of section 3.2. Finally the Horn-Brooks shape from shading algorithm is applied to the top face.

1 In the &ell8e that it corresponds to the particular acene being imaged. They are all consistent with the line drawing in!ormation.

In the examples just considered, we started from the correct labelling. What is actually available to us are a set of sparse la­ bellings among which only one is correct 1 . When we start from an incorrect sparse labelling, the 3-D shape computed will be in­ correct and hence will not satisfy the line drawing and shading constraints within the margin of error permitted by the inaccu­ racies in the data ( i.e. noise in pixel brightness values, errors in estimates of edge direction etc. ). This gives us a way to prune away the shapes resulting from incorrect labellings. We refer the reader to [10) for the complete algorithm and a study of the effects of noise.