Active Color Image Analysis for Recognizing Shadows

1 Shadows and Image Understanding

Many existing computer vision modules assume that shadows in an image have been accounted for prior to their application. For instance, object recognition sys­ tems assume that one can recover intrinsic properties of an object despite irradiance changes such as shadows. Similarly, shape from shading algorithms assume that surface radiance does not include shadow effects. In ad­ dition, it has long been recognized that identifying shad­ ows in an image constrains the geometric interpretation of the pictured scene [Waltz, 1975; Shafer, 1985a]. How­ ever, despite the acknowledged importance of identify shadows for image understanding, attempts to date have been overly simplistic. In aerial image interpretation, for instance, shadows are considered to be those parts of an image whose values are below a threshold and are adja­ cent to a rectangular shape (a building) on the side away from the direction of illumination [Nagao et al., 1979;

Huertas and Nevatia, 1988; Irvin and McKeown, 1988; Liow and Pavlidis, 1990].

In this work, we present a color image segmentation al­ gorithm that recovers image regions amenable to shadow recognition . In addition, we sketch how this technique fits in with a larger system to enable an active observer to recognize shadows in images of a scene.

We begin with a physical model for color image for­ mation for a single surface material directly lit and in shadow. We discuss the limitations of previous color im­ age work for shadows and present our assumptions and techniques for addressing the problem. In particular, we use an observer that can actively cast a shadow into the scene in order to examine the illumination conditions. Finally, we present results and a discussion of our work.

2 Spectral Model of Shadows

2.1 Shadows Without Other Reflectance Effects

Let D(>. ,p) be the amount of energy emitted at each wavelength >. by a direct source of illumination D as measured at the back-projection of pixel p onto a given surface. In addition to the light D(>.,p), the light A'(>., p) that has been reflected or scattered in the en­ vironment and any other direct sources of illumination L1(>.,p), . . . , Ln(>.,p) also strike the surface. Assume now that an object is brought between the light source D and the surface. The reflected light in the scene changes due to reflections off the obstructing object, call it now A(>.,p). So, the illumination striking the surface is

where a E (0 ... 1] indicates that the light source D will be only partially obstructed at some locations on the surface if D is not a point light source. The partial obstruction of an extended light source results in the penumbra of a shadow.

Let S(>.,p) be the surface reflectance (albedo) . For the moment, assume that S(>.,p) is independent of the view­ ing direction and direction of illumination; and hence, that there are no specularities (high-lights) nor shading across the surface. Let Qj(>.) be the weighting func­ tion of the observer's camera system for the jth filter

(j E [1, ... , m]). Then, the camera measurement from the surface directly lit and in shadow for one filter is

where E(A,p) = A(A,p) + L:~1 Li(A,p), and A is the range in which Q1(A) is non-zero.

where D(p) and E(p) are m element vectors. From the above equations it follows that the image of the surface directly lit and in shadow is

Equation 2 is the parametric form of a line with parame­ ter a. The end-point of the line at a = 0 corresponds to the shadow umbra. The end-point at a = 1 corresponds to the surface directly lit . The open interval of the line (0 <a< 1) corresponds to the shadow penumbra.

Our images were taken with three color filters : red, green, and blue. Some images were converted to the form (So , S1 , S2) =(brightness , sin A, cosA) , where A ranges over the visible wavelengths [Lee, 1991]. This space is convenient for describing hue and color saturation. Hue is defined as tan -l ( ~) . Color saturation is defined as

~ ~. Equation 2 holds in both color spaces.

2.2 Shading, Inter-Reflections, and Specularities

Variations in the amount of light striking a surface due to a change in geometry (shading) can complicate the model we have described above. For a scene with a single light source, no inter-reflections, and a uniformly colored Lambertian surface which receives varying amounts of il­ lumination due to surface curvature or varying distance from the the light source, the reflection from the surface will describe a linear cluster in color space [Shafer , 1985b; Lee, 1991]. This linear cluster will lie along the lin­ ear cluster resulting from a shadow penumbra under the same illumination conditions.

In the case where a uniformly colored Lambertian sur­ face is illuminated by light in varying amounts from two distinctly colored lights, the reflection from the sur­ face will describe a planar cluster in color space due to changes in the term E(p) in Equation 2. If the surface is illuminated by light in varying amounts from multiple, distinctly colored lights, the reflection from the surface will describe a volume in color space [Lee, 1991]. For multiple, differently colored light sources, the reflection distortion in color space due to a shadow will be super­ imposed on the volumetric cluster due to shading.

The light reflected from one surface onto a second sur­ face serves as a source of irradiance for the second sur­ face. As such, inter-reflections complicate our shadow model in the same way that multiple light source do.

If a surface is not perfectly Lambertian, then the image of that surface may include specularities. Specularities from the obstructed light source cannot occur in the um­ bra of a shadow. Specularities from the obstructed light source that fall within the penumbra are visible but their shape will be truncated at the boundary of the umbra. Diffuse specularities due to a rough, microfaceted sur­ face [Torrance and Sparrow, 1967] can, however, become dimmer in a penumbra because the specular irradiance at a point on the image can be due to microfacets in the umbra as well as in the penumbra of a shadow.

3 Assumptions for Shadow Recognition

Many researchers assume that the light illuminating a shadow and the obstructed light are spectrally propor­ tional. Hence, that E(p) = .BD(p) [Rubin and Richards, 1988]. And, the color cluster for a single material di­ rectly lit and in shadow is a linear cluster that if ex­ tended would pass through the origin. Gershon et al. [1986] refer to such shadows as ideal shadows. They also considered the somewhat more general case of E(p) = .BD(p) + K(p) where K(p) = [kl> . .. kmJT is constant . This case is referred to as that of non-ideal shadows.

Rather than require a strong, global constraint on the scene illumination as in [Rubin and Richards, 1988; Gershon et al. , 1986], we prefer to use a weaker, local constraint during our initial color image segmentation. We want to insure that we can segment an image into regions such that if shadows are present, a uniformly colored surface directly lit and in shadow will be rep­ resented by a single region when the scene is lit by a compact light source or a cross section of the penumbra of a shadow will be represented as a single region when multiple compact light sources are present. Only those segmented regions with a linear model will be shadow candidate regions. The shadow candidate regions will be further analyzed for evidence to support or refute the hypothesis that a shadow is present. In general this will require bringing both geometric and spectral information to bear. Hear we concentrate on spectral information.

In order to meet our goal for image segmentation, we will make the following assumption:

Linear Color Cluster Assumption for Penumbrae: We assume that the light irradiating a penumbra, with the exception of the the partially obstructed light , does not vary or varies insignificantly.

Consequently, the variation in reflection in a penumbra on a uniformly colored surface is due entirely to the ob­ struction of a direct light source. And, in order to find regions of an image that could represent the same sur­ face lit and in shadow across a penumbra we present a scheme in which an image is segmented into line-like or uniform color clusters.

However under our assumption, line-like color clusters can still originate from physical phenomenon other than shadows. Shading, inter-reflections, highlights, or ma­ terial changes may also produce line-like color clusters [Klinker et a/., 199(l; Lee, 1991]. We will examine later how to distinguish the case of shadows.

The analysis discussed so far was done strictly in color space and ignores image or scene locality. Because all the pixels in an image of a complicated scene taken together may result in many line-like color clusters, we introduce local image continuity as a constraint in our color image segmentation. So, we will only be looking for contigu­ ous sets of pixels in an image that form line-like color clusters. This restricts our image interpretation to those shadows for which the same surface can be seen directly lit and adjacently in shadow. Note also that the bound­ ary of the shadow must include a penumbra for our sys­ tem to work. This means that we cannot handle scenes with point light sources. Fortunately, true point light sources are rare in non-laboratory environments. The importance of penumbra in detecting shadows has also been noted by lJiang and Ward, 1992].

4 Color Image Segmentation

Our color image segmentation is founded on three ideas. First, to find line-like models in color space which are our shadow candidate regions. Second, to dove-tail the processing between color-space and image-space in order to take into account aspects of each. And finally, the realization that segmentation should be the search for the best description of an image in terms of primitives [Leonardis et a/., 1990]. Figure 1 provides an outline of the control structure of the algorithm.

The bulk of the work is accomplished through a seg­ mentation by region growing and pruning algorithm [Leonardis et a/., 1990]. Which in outline is:

WHILE change DO LOOP

• Grow each region based on the region model.
• Update each region to fit .the new and old data.
• Consider a higher order model.
• Prune away regions based on overlap, size, goodness of fit, and model order.

END LOOP

Our region models are uniform or linear functions in color space, while [Leonardis et a/., 1990] uses bivariate polynomials functions of pixel location.

Region growing is initiated by finding seed regions. Seed regions are found based either on strong color sam­ ples found in a color histogram of the image, or based on uniformly colored image areas within a grid of 7x7 pixel squares which is over laid on the image. The process first attempts to find seed regions through color histogram­ ming because these regions are often large. The algo­ rithm switches to the grid method when compact strong peaks with low color variance can no longer be found in the histogram (see [Funka-Lea, 1992] for the algorithm) .

We have used a two dimensional color space for the histogramming. The 2D color spaces used were

( Green Blue) and (§.J. §..:L). We believe that any one Red 1 Red So ' So or two dimensional color space that de-emphasizes color brightness is a suitable choice for the initial histogram­ ming. (See Figure 2 for a sample 2D color histogram.)

The initial 3D color models for seed regions are either uniformly colored or correspond to lines in 3D color space that pass through the origin. If a uniform region does not grow during an iteration then a linear model is tried. The linear model is accepted if the error is relatively small and the region can be grown by a considerable amount. Through the process of choosing a new model during updating, linear models need no longer pass through the origin. Consequently, we can recover shadows that are not ideal shadows. See [Leonardis et a/., 1990] for the details of model updating an pruning.

The tolerance criteria for region growing is determined based on the variance of the peak in the histogram or on the fit error of a model from the grid method. The tolerance is varied uniformly with pixel intensity because greater color variation is possible for brighter pixels.

Our image segmentation decouples the region models from pixel coordinates. This insures that a a single ma­ terial lit by a single light source on which numerous shad­ ows are cast is still recovered as one image region. Our post-segmentation processing will concentrate on analyz­ ing individual regions to see if they contain shadows and will not need to compare regions that are not adjacent.

5 Employing an Active Observer

Because line-like color clusters can result from physical events besides shadow, our observer must examine the shadow candidate regions found by our color segmenta­ tion procedure to determine if a shadow is present.

The simplest shadow criteria for the linear color clus­ ters follows from the fact that shadows are darker than the same surface directly lit. Consequently, for a color space whose bases are band-limited functions (such as red, green, blue) , the linear color cluster for a shadow must not get brighter along any of the bases in one di­ rection along the line.

If all the shadows in a scene are illuminated by simi­ larly colored light, we expect the shadows to show a sim­ ilar relative change in brightness, hue and color satura­ tion. We judge any trends in the color of shadows based on experiments the observer does by actively casting its own shadows by extending a probe into the environment. If we assume the environment is unchanging during the extension of the shadow probe then any shadows that are cast and are visible can be easily detected by taking the difference of images. We assume the observer is mo­ bile and that in time the observer will image a shadow that it has cast, if shadows are possible.

The first use of the probe shadow is to provide a par­ tial segmentation of the image. We segment the image area of the probe shadow using our color segmentation algorithm. Then, we allow the results to grow into the surrounding parts of the image. Thus, we assume that the shadow we cast on a material will look like other shadows cast on the same material.

Next, we examine the situational information gained from the probe shadow. If no shadow is cast, we infer that there is no compact light source. If the shadow has no detectable penumbra, we infer that there is a point light source and that our shadow recognition system is not applicable. If we find disjoint shadows cast by the probe, then there must be multiple compact light sources present . If only one compact light source is indicated, then shadows cast on a single material will lie within im­ age regions. However, if there are multiple compact light sources, then a shadow cast on a single material may be found across several contiguous regions. In future work we will address the problem of recognizing that a shadow that is split over several regions is a single shadow.

Note that the observer can test the validity of the Lin­ ear Color Cluster Assumption for Penumbrae for those shadows that it casts. The penumbra of these shadows can be found independently of our segmentation algo­ rithm (see [Funka-Lea, 1992]) and the penumbra color values can be tested against a linear color model.

We now examine the spectral characteristics of the scene illumination inferred from the probe shadow. First, the observer tests if the ratio of the brightness of the probe umbra to the same surface directly lit is con­ stant for a variety of surfaces (i.e. ideal shadows) . If it is, then the observer can use this ratio as a criteria for de­ tecting shadows. If the ratio is not tightly bounded, we assume that the color trends we see in the probe shadow will hold for all the shadows in the scene. For instance, if all the probe shadows show a bias towards blue then we will expect all shadows to follow this rule under the present lighting conditions. We look for trends along the criteria of hue and saturation among the probe shadows. (This is similar in spirit to the pull factor for non-ideal shadows of Gershon et al. [1986].)

6 Results

Figure 2 shows the complete processing of one image. In the image, a red block is at the right and a green block is in the center. The coordinates of the pictured 2D color histogram are (~,?a) . Unsaturated colors are near the origin and saturated colors are at the periphery. Red is to the right, green at the bottom, and blue is at the upper left corner . Strong responses can be seen for the white background (near the center) and for the red block (near the right). There is a weaker response for the green block not in shadow (at the bottom center) . The green block in shadow is a line from green to red.

The top right picture in the figure shows in white the segmented region found from the probe shadow. At the bottom of the figure are shown the gray-scale coded regions from segmentation. Some image locations re­ main unexplained after segmentation. In areas where no seed region is fit and no region is grown, the im­ age is better explained by texture, edges, or higher or­ der color models . In the area where the two blocks meet, there are strong inter-reflections This results lo­ cally in a non-line-like color cluster which our system was not designed to recover. (See [Klinker et al., 1990; Lee, 1991] for recovering inter-reflections.) The shadows in the scene are recognized as compatible with the probe results of a nearly ideal shadow with a slight bias to red.

In the next two figures no probe was used and only the success of the segmentation algorithm is tested.

Figure 3 demonstrates that our method can handle complex, natural shadows. This example also demon­ strates the recovery of the umbra, penumbra, and di­ rectly lit parts of a surface (the road). Some small parts of this image remain unexplained due to camera noise, cracks on the road, and variations in the ground cover. Note that the partially shadowed exterior of the green garbage can is successfully recovered against the grass. However, the shadowed tree trunks and the interior of the garbage can are not distinguished from the grass in shadow due to the lack of hue data with low brightness.

In Figure 4 the scene i!) illuminated by two compact light sources. This is evident in the two specularities on the plastic ball in the center of the image. On the right side of the image is an arch of colored wooden blocks which casts a shadow across the ball and the ground. Because of the illumination situation, there is shading within the shadow cast on the ball. Consequently, we cannot expect to recover the ball with one line-like color cluster model. However, if our assumptions hold, we should be able to recover at least the penumbra of the shadow as one region. In fact, the penumbra and most of the ball is recovered as a single region. This demon­ strates how weak a constraint the Linear Color Cluster Assumption is on the illumination. Again, small parts of the image remain unexplained; this is mainly on account of specularities and color variations on the wood blocks.

7 Conclusion

We have presented a general algorithm for segmenting color images into regions that form uniform or linear clusters in color space. Under our Linear Color Cluster Assumption for Penumbrae, shadows are represented as piece-wise linear color clusters and the width of a penum­ bra will always be a single segmented region. Conse­ quently, all linear color clusters become shadow candi­ date regions. Many of these regions can be discounted as shadows because they do not show a darkening simulta­ neously along red, green, and blue. Other regions can be discounted because they show color trends not compati­ ble with the results from the probe shadow. For a com­ plete shadow recognition system, geometric constraints would also need to be brought to bear [Funka-Lea, 1992].

Rather than rely on restrictive or untestable assump­ tions, or high level knowledge about the scene illumina­ tion [Gershon et al., 1986] , we have made use of an ob­ server than can actively cast shadows. For relatively un­ cluttered scenes where shadows are present, the observer will be likely to cast a visible shadow. By addressing the problem of shadow recognition prior to recovering high level scene knowledge, we have a system that meets the needs of a large number of visual modules for geometric recovery that assume that shadows have been accounted for. In addition, because of our need for only relatively week a priori assumptions, our system can handle scenes with complex geometry and illumination.

Acknowledgments

We strongly thank S. W. Lee for his insight on color. We thank C. Thorpe and T . Jochem for making images from the Carnegie Mellon University Navlab available. This research was supported in part by: AFOSR Grants 88-0244, 88-0296; Army/DAAL 03-89-C-0031PRI ; NSF Grants CISE/CDA 88-22719, IRI 89-06770; ARPA Grant N0014-88-K-0630; and Dupont Corp.