Surface-Normals from Closed Paths

SURFACE-NORMALS FROM CLOSED PATHS

M,J, Brooks Department of Computer Science, University of Essex, Colchester, En!land,

It is now well established that the shading present in an image of an object is a potential source of 3-D shape information. With this in mind, we seek constraints arising out of the assumption that an image portrays an object with a smooth surface, On obtaining a threshold and a depth-invariance constraint (the latter requiring integration around closed curves) we offer a method of shape from shading for the purpose of demonstrating their potential usefulness.

KEY WORDS

Shape from shading, surface-normal, closed path, constraints, depth-invariance.

TOPICS

Vision and image understanding systems.

l, INTRODUCTION

Given an image of a smooth surface, we consider the problem of assigning to each image point an orientation corresponding to the appropriate object surface-normal, thus obtaining a surface­ normal map. This constitutes the core of the shape from shading problem (see [3] and [a]) since 3-D surface data can be recovered from such a map by integration,

Two basic stages can be isolated in the genera­ tion of a surface-normal (s - n) map:

1. The luminance value at each image p~int defines an orbit in the reflectance map 14] . Thus, for each image point, we produce anln­ finite, one-dimensional set of surface-normals.
2. From each of these sets, we select a par­ ticular surface-normal such that the resulting surface-normal map represents a smooth surface.

Given a knowledge of the illumination conditions and surface reflectivity, the first stage is relatively straightforward. It is the second stage on which we shall concentrate,

This woi'k is funded by the Sciance Research Council.

We contend that the assumption that an image depicts a smooth surface is one that has not previously been ful~ exploited, (For instance, Woodham's program [BJ requires substantial clues as to the object shape before being able to run.) Thus we seek constraints imposed by this assump­ tion on dense s-n maps: that is, maps which have an infinitely fine resolution (for we can then use continuous mathematics). These con­ straints are subsequently translated to discrete form prior to application,

1. CONSTRAINING A DENSE SURFACE-NORMAL MAP

2.1 Smoothness

A dense s-n map, u, represents a smooth surface if, and only if, lor any point ~ in the map and 6 > 0. 3 £ > 0 such that, for any a' in an £-neighbourhood of s, the angle in radians bet­ ween u(s) and u(s')-is less than 6, (See Fig. 1,) - - - -

---

Fig. 1 Smoothness definition

2.2 Depth-invariant Loops

Suppose we were to draw a closed loop, Cl, on a continuous surface; we would clearly finish the loop at the same point in space at which we started. Were we now to project the surface or­ thogonally to form a dense s-n map, then provid­ ing all points on the surface were visible with respect to the projection, we would obtain a corresponding closed loop, C2, in the resulting s-n map. If we integrated around C2 over sur­ face-normals to recover depth, then on complet­ ing a tour of C2, we would result in no depth change. Note the similarity between this and the scene ana~sis conce~ts of spatial closure expounded in L5] and [2].

This observation leads to a formal constraint: for a dense s-n map, ~(~), to represent a con­ tinuous surface, the relation

must hold for all closed paths r in the map. Here , s is a point on r with unit derivative ds as shoWn in Fig. 2; p is a unit vector of depth along the direction of projection. For the derivation, see [1]. The above definition has an analogue in the complex analysis theorem of Morera's; see, for example, p.538 of [6].

Fig. 2 · Integrating around a curve r

3, MAKING THE CONSTRAINTS DISCRETE

Computer vision programs operate on tesselated images and so we require the discrete form of the constraints obtained in section 2.

3,1 Thresholding

In attempti~ to import the smoothness defini­ tion of 2.1 into the discrete world, we are, in a strict sense, doomed to failure since any dis­ crete s-n map can represent a smooth surface providing the surface is allowed to fluctuate sufficiently between the sampling points. Due to a lack of information, we cannot be expected to recover this surface. Indeed, if we are ex­ pected to recover the object shape depicted in an image, we are justified in insisting that the image capture the characteristics of the surface. For our purpose, that criterion will be ful­ filled if a piece-wise planar solution (one ~ur­ face-normal per image point) is a satisfactory approximation to the surface, Suppose we were to generate several images of varying resolutions from a wildly fluctuating surface, If we produced a discrete s-n map for each image and computed, for each map, the maxi­ mum angle between any two neighbouring surface­ normals, we would find that, in general, this angle decreased as the resolution increased, So by assuming a minimum level of resolution per object scale and per maximum surface curvature, we place an upper limit, or threshold, on the permissible angular difference between neighbour­ ing normals. (The author has recently improved considerably on a blanket threshold by adopting a functional threshold dependent on surface slant,)

3,2 ~ ~ £z. ~Integral

We now apply the depth-invariant integral to the discrete case of a 2*2 window of orientations, For a square path of integration (a 2 1 ~2 path) and surface-normal quartet as shown in Fig. 3, then for this window to be representative of a continuous surface, the relation

{: The author has recently become aware of [9] in which dll equi valtmt formula is ( iuuependently) derived.

4. ~ ~ ~ SHADING METHOD

The need to investigate the depth-invariance of all closed paths in a discrete s-n map is an in­ tolerable burden which we finesse by using the following result.

If all 2*2 paths are depth-invariant in a dis­ crete s-n map, then so too is any closed path in the map.

Consider a dense s-n map that represents a con­ tinuous surface. Then the depth-integral around a closed curve r clearly equals the sum of the depth-integrals around the constituent closed curves r 1 and r 2 as shown in Fig. 4,

This splitting can be repeated as often as required and providing the correct direction­ ality is observed, the sum of the depth­ integrals around the constituent curves will equal the depth-integral around r. For a com­ plex anal~sis analogue, see Goursat's proof, on p.526 of L4].

Now, any closed path in a discrete s-n map will consist of linked horizontal and vertical sections (e.g., Fig. 5), But any such path can be dissected into constituent paths that are all 2*2 (e.g., Fig. 6), Further, if these 2*2 paths all integrate to zero in either direction, then so too, by the above, must the bounding closed path,

We now describe a method of shape from shading in order to demonstrate the potential of these constraints. The method is in two stages.

4.1 Obtaining !. ~ of Interpretations !2::, ~ 2·\2 window

As mentioned earlier, each image point specifies, in general, an infinite, one-dimensional subset of all possible surface-normals, Crucial to our method is the quantising of this interval into a finite set of orientations.

We therefore have a potentially vast number of possible combinations of surface-normal inter­ pretations for each 2*2 window, of which the majority are likely to fail either the threshold or depth-invariance test, There is insufficient space here to detail a speedy means of generatir.g a set of legal interpretations, but note that there is considerable scope for Waltz-like fil­ tration on neighbouring surface-normals (see [7]). Also, note that all 2*2 windows can be processed in parallel. This stage has recently been successfully implemented.

4, 2 ~ ~ Encompass

Having generated a set of legal surface-normal interpretations for each 2*2 window, we now want to obtain a set of interpretations for the whole image, To do this, we start by taking a 2*2 window of interpretations and merging this with an intersecting 2*2 window to form a larger area of legal interpretations. We continue to expand this area until the whole image is covered, t hereby obtaining a setaf solution s-n maps.

We define the algorithm inductively by consid­ ering the merging of the interpretations of an n-pixel area and a partially intersecting 2*2 area,

Suppose, in the n-area, pixels are indexed from 1 to n, and that the 2*2 area intersects the n-area at, say, two image points, Let (p 1 , ··· , p ) be a legal interpretation of the m mn n-area such that p . is the orientation of the . t h . _ . m: ~ p~xel, 1 <- ~ <- n, Let (pml' ,,,, pmn) for m = 1, ,,,, k be the set of legal interpreta­ t ions for the n-area,denoted as (p 1 , ·.· , p )k. ~ ~n Let the legal interpretation set for the 2·\2 window be (~a, ~b, ~+l' ~+2 )t where a t b and a,bt [}, r!J,

Now, for all

which checks whether the surface-normals at the points of intersection are equal, If this relation is false, we pass on to the next com­ bination, thereby rejecting the merger, other­ wise we output

as a legal interpretation of the resultant area.

5. CONCLUSION

We have outlined a shape from shading algorithm t hat converges on legal interpretations without needing clues as to the solution shapes, This was done merely to demonstrate the value of the constraints in section 3, The labourious behaviour of the algorithm is clearly inadequate and the author is currently implementing a cooperative algorithm,

ACKNOWLEDGEMENTS

I am grateful to Pat Hayes, Mike Brady, Tony Cohn, Steven Draper and Paul Robertson for their useful comments and to Berthold Horn for his valuable encouragement,