next up previous
Next: References

Shape from Shadow

Yizhou Yu
Department of Computer Science
University of Illinois at Urbana-Champaign

Figure 1: 2D schematic of shadowed and nonshadowed regions on a terrain-like surface. L is the lighting direction determined by the elevation angle tex2html_wrap_inline254. tex2html_wrap_inline256 is an occluder, tex2html_wrap_inline258 is on the shadow boundary caused by tex2html_wrap_inline256, and tex2html_wrap_inline262 is a non-shadowed point.

Let us first consider recovering terrain-like height fields. For the convenience of discrete representation based on pixels, a height field is assumed to be a piecewise constant function with every pixel corresponding to a piece with constant height. Every piece of the height field is represented by the point corresponding to the center of the pixel. We also assume that the distance between the camera and the surface is sufficiently large so that the orthographic projection model is accurate. The surface is illuminated with a collimated light source which can be parameterized by a pair of polar coordinates.

Let us first check what kind of constraints are available from images with shadows. Let h(x) be a height field defined on a planar domain D with a finite area in the image plane and tex2html_wrap_inline268 be the lighting direction pointing downwards with a tilt angle tex2html_wrap_inline270. The normal orientation of this height field is denoted as tex2html_wrap_inline272. The boundary curve of domain D is tex2html_wrap_inline276. The projected vector of tex2html_wrap_inline268 in the domain D is tex2html_wrap_inline282. Let tex2html_wrap_inline284 and tex2html_wrap_inline286 be two arbitrary 2D points in D. The line segment between them is denoted as a vector interval tex2html_wrap_inline290 for convenience. Based on whether a point on the height field is in shadow or not under lighting direction tex2html_wrap_inline268, there are two different sets of constraints (Fig. 1).

Let us first focus on how to represent the inequality constraints (1) and (4) in a graph [5].


A shadow graph can be induced from an image of the height field under an arbitrary lighting direction tex2html_wrap_inline268. Shadowed pixels can be detected from the image, and an occluder can be located for each continuous shadow segment with the knowledge of the lighting direction. For example, if tex2html_wrap_inline290 is a shadow segment and the vector from tex2html_wrap_inline284 to tex2html_wrap_inline286 is in the direction of the projected lighting direction tex2html_wrap_inline282, the point at tex2html_wrap_inline284 is the occluder of all the points in tex2html_wrap_inline290. There should be an edge tex2html_wrap_inline346 with weight tex2html_wrap_inline348 in the induced graph for all tex2html_wrap_inline350. This graph basically encodes the shadow constraints available from the image. All the edge weights in this graph should be positive. However, this graph can have negative weights if the additional antishadow constraints in Eq. (4) are represented as well.

Suppose we have multiple images of the height field under a set of lighting directions tex2html_wrap_inline352. Each of the images has its own shadow graph. Finally, the edges from all of these individual graphs can be accumulated into one graph that is corresponding to all the images.

Proof Suppose there is a circular path in the graph and a node v is on the path. Since all the arcs on this path have positive weights, it is easy to conclude that h(v) > h(v) by starting from v, going through this path and back to v. A contradiction.

When dealing with real images with noise, shadow detection cannot be expected to be error free. Inaccurate shadow segmentations may result in cycles in the induced shadow graphs. Since cycles can lead to the above contradiction, we must convert a cyclic graph into an acyclic one by removing some of the edges in the graph [5].


There are a set of nodes tex2html_wrap_inline380 in tex2html_wrap_inline382 that do not have any incident edges with positive weights, which means they are not shadowed by any other points in any of the images. The highest point(s) of the height field surely belongs to this set because there is no other points which can occlude it(them) from the light sources. The absolute height values of the nodes in tex2html_wrap_inline384 are unrecoverable from shadow constraints. However, if we can recover their height values from other approaches such as stereo, the information embedded in tex2html_wrap_inline382 can be used for obtaining an upper bound of the height at any point in tex2html_wrap_inline388. The set of edges in tex2html_wrap_inline382 connecting tex2html_wrap_inline384 and tex2html_wrap_inline388 becomes the most important for this purpose. Suppose there is a node tex2html_wrap_inline396 and a set of associated edges tex2html_wrap_inline398 such that if an edge tex2html_wrap_inline400, tex2html_wrap_inline402. The upper bound of the height at the point corresponding to node v can be obtained from

Figure 2: A surface reconstruction example from [5]. (a) Input images for a plaster material sample lit from eight lighting directions; (b) a synthetic image of the recovered height field illuminated from the same lighting direction as in the first input image; (c) a synthetic image of the recovered height field illuminated from a novel lighting direction.

Let us exam the asymptotic behavior of this upper bound when we increase the number of input images with lighting directions covering the whole lighting hemisphere. The set tex2html_wrap_inline384 will shrink and approach its limit which is the set of the highest points of the height field. Otherwise, assume there is a pair of nodes tex2html_wrap_inline408 and tex2html_wrap_inline410. We can always design a lighting direction from which the point corresponding to tex2html_wrap_inline412 shadows the point corresponding to tex2html_wrap_inline414, which means tex2html_wrap_inline416, a contradiction. Since eventually tex2html_wrap_inline384 only has nodes at the same height, we do not need to seek their relative height through other reconstruction techniques. Our interest should be focused on the relative height of other points compared to the highest points whose height can always be set to zero.

See proof in [5].

It is clear that the antishadow constraints can be derived from the shadow constraints if we have a very dense set of images since the height field itself can be recovered from the shadow constraints alone according to the above Proposition. However, if we only have a sparse set of images, this is not necessarily true. Representing these antishadow constraints in a shadow graph usually can provide additional information. According to Eq. (4), antishadow constraints transform to additional edges with negative weights. Cycles can appear in the resulting graph. However, the accumulated weight of any cycle can not be positive according to the following Proposition.


The transitive closure of a shadow graph G with cycles is still well-defined because negative cycles do not interfere with the objective to seek paths with maximum accumulated weights according to the definition. The resulting graph tex2html_wrap_inline382 can still be used for obtaining an upper bound of the height for any point in tex2html_wrap_inline388. Since there may be negative edges pointing from nodes in tex2html_wrap_inline388 to some nodes in tex2html_wrap_inline384, these edges can be used for obtaining a lower bound for some nodes in tex2html_wrap_inline388. Since it is not guaranteed that there is an edge from each node in tex2html_wrap_inline388 to some node in tex2html_wrap_inline384 given a sparse set of images, we can only obtain lower bounds for a subset of nodes in tex2html_wrap_inline388. And these lower bounds may appear useful in combination with other surface reconstruction techniques.

Figure 3: (a) A shadowgram for a one-dimensional terrain-like surface; (b) a shadowgram for a one-dimensional non terrain-like surface.

Shadow information can also be described using another representation known as a Shadowgram [3, 1]. Let us first look at shadowgrams for a one-dimensional terrain-like surface illuminated by a collimated light source parameterized by a single angle tex2html_wrap_inline254. As shown in Fig. 3, the shadowgram is a binary function defined on the angle, tex2html_wrap_inline254, and the spatial dimension of the terrain, x. A white entry in the shadowgram indicates that image pixel x was lit when the light source was at angle tex2html_wrap_inline254, while a black entry indicates that it was shadowed. It was shown in [3] that the shadowgram generated by a terrain-like surface can be completely described by two curves bounding the black regions: tex2html_wrap_inline456 and tex2html_wrap_inline458. For a specific point x, tex2html_wrap_inline462 and tex2html_wrap_inline464 represent the lighting angles at which x is lit for the first and last time, respectively. Therefore, tex2html_wrap_inline468. If the light source travels from horizon to horizon, it is possible that one of these angles might be equal to 0 or tex2html_wrap_inline470. tex2html_wrap_inline472 unless the point in question is a global maximum of the scene. Because one has this guarantee, it is possible to reconstruct the surface by integrating tex2html_wrap_inline456 and tex2html_wrap_inline458.

When the one-dimensional surface is non terrain-like, the shadowgram possesses not only two curves, but also some white holes where one would expect darkness if the surface were a terrain. Here tex2html_wrap_inline462 and tex2html_wrap_inline464 are not defined as first and last lighting curves, but rather as the envelope of the shadowgram which lies closest to the middle horizontal line defined by tex2html_wrap_inline482. It is shown in [4] that using these two curves to reconstruct the surface will produce the surface's generated terrain which is defined to be its upper envelope. Furthermore, the holes in the shadowgram may be used to carve pieces out of the generated terrain for reconstructing some of the hidden parts of the surface.

In a general situation, a surface in a 3D space is parameterized by two variables, and the lighting direction is defined by two angles. The shadowgram thus becomes a four-dimensional function defined on all these four variables. It becomes so complicated that often three dimensional cross sections are investigated [1].

If there are additional assumptions on the smoothness of the surface (e.g. it is twice differentiable), one may find that it is possible to reconstruct a spline approximation of the original surface from shadow constraints available at a sparse set of locations [2]. The normal constraint in Eq.(3), which has not been made use of so far, becomes important in spline surface reconstruction.

next up previous
Next: References

Bob Fisher
Mon Jul 22 16:00:47 BST 2002