** Yizhou Yu **

Department of Computer Science

University of Illinois at Urbana-Champaign

yyz@cs.uiuc.edu

**Figure 1:**
2D schematic of shadowed and nonshadowed regions on a terrain-like surface.
*L* is the lighting direction determined by the elevation angle .
is an occluder, is on the shadow boundary caused by ,
and 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 be the lighting direction pointing downwards with a
tilt angle . The normal orientation of this height field is denoted as . The boundary
curve of domain *D* is . The projected vector of in the domain *D* is . Let
and be two arbitrary 2D points in *D*. The line segment between them is denoted as a
vector interval for convenience. Based on whether a point on the height field is in
shadow or not under lighting direction , there are two different sets of constraints
(Fig. 1).

- If any point on the line segment is in shadow, the points at
and
are the delimiting points of this shadow segment,
and the point at is the occluding point
generating this shadow segment, we have the following
*shadow*constraints.

where the last equation means the lighting vector falls inside the tangential plane at if the original continuous height field is locally differentiable at . - If the point at is not in shadow, we have the following
*antishadow*constraints.

where and the line segment is in the same direction as .

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 . 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 is a shadow segment and the vector from to is in the direction of the projected lighting direction , the point at is the occluder of all the points in . There should be an edge with weight in the induced graph for all . 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 . 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 in 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 are unrecoverable from shadow constraints. However, if we can recover their
height values from other approaches such as stereo, the information embedded in
can be used for obtaining an upper bound of the height at any point in . The set of
edges in connecting and becomes the most important for this purpose.
Suppose there is a node and a set of associated edges such
that if an edge , . 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 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 and . We can always design a lighting direction from which the point corresponding to shadows the point corresponding to , which means , a contradiction. Since eventually 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 can still be used for obtaining an upper
bound of the height for any point in . Since there may be negative edges pointing from
nodes in to some nodes in , these edges can be used for obtaining a lower bound
for some nodes in . Since it is not guaranteed that there is an edge from each node in
to some node in given a sparse set of images, we can only obtain lower bounds
for a subset of nodes in . 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 . As shown in
Fig. 3, the shadowgram is a binary function defined on
the angle, , and the spatial dimension of the terrain,

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 and 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 . 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.

Mon Jul 22 16:00:47 BST 2002