The objective of the project is to implement and study the efficiency of two algorithms for the extraction of shadow free images.
This project won the Distinguished Project Award of VISL 2005
Abstract
The objective of the project is to implement and study the efficiency of two algorithms for the extraction of shadow free images.
The first algorithm was proposed by Yair Weiss in 2001, and the second algorithm was proposed by Graham D. Finlayson, Steven D. Hordley and Mark S. Drew in 2002.
In both algorithms, the key for a successful shadow removal is an accurate detection of the shadow edges in the original image or image sequence, and an efficient reconstruction of the shadow free image out of an edges image that does not contain these shadow edges.
Background:
Shadows in images may cause problems to several important algorithms in the fields of image processing and computer vision, such as segmentation and object tracking, and removing them can greatly improve the results of these algorithms. The problem is divided into two parts: Identifying strong shadow edges and removing those shadow edges.
The Weiss algorithm deals with this problem in a sequence of images, taken at the same scene but with different lighting conditions while the Finlayson-Hordley-Drew (F.H.D.) algorithm removes shadows from a single RGB image.
The solution:
Two approaches were observed in this project:
The Weiss algorithm:
The algorithm defines a reflectance image, which is an image that is invariant to light changes, and an illumination image, which represents the light changes in the scene.
The following connection is established:
I – image
R – reflectance
L – illumination
The input is a sequence of images, taken at the same place with different lighting, where the goal is to extract the reflectance image since it should be without shadows.
Figure 1 – Example of input sequence
The claim at the core of the algorithm is that the derivatives of a natural image have a Laplacian distribution: 
and that this property is strong enough even when working in log-space, so the ML estimator of each derivative of the reflectance image is the median of the derivatives at the same point over the sequence. The product of this estimator is couple of derivative images of the approximated reflectance image (each image using a different differential filter).
– Original image in log-space
– Derivative filter (n from a set of N)
-Estimated derivatives of reflectance image (using the n-th filter)
The reflectance image can be reconstructed from its derivatives by using a pseudo-inverse filter:
– Reverse filter of 
– Pseudo-inverse filter
– Reconstructed reflectance image in log-space
Figure 2 – The Weiss algorithm flow-chart
Figure 3 – The effectiveness of Weiss` algorithm in extracting reflectance image in compare to a simple median
Figure 4 – Using the Weiss algorithm, the original image was separated to the reflectance image and illumination image. Afterwards, a new reflectance image can be created. Multipying it with the illumination image creates a convincing new reconstructed scene
The Finlayson-Hordley-Drew (F.H.D.) algorithm:
This algorithm removes strong shadows from a single RGB image.
The basic idea is that a shadow has a distinguished boundary. Removing the shadow boundary from the image derivatives and reconstructing the image should remove the shadow. The main problem here is to determine the shadow edge.
To define a shadow edge the algorithm requires some constraints on the image:
The lighting in the scene should be Planckian (like sun light) and the camera’s sensors should be narrow-banded (their response can be approximated by a Dirac Delta function).
A Planckian light can be describes by Planck’s law:
– Constants
– Temperature
– Wavelength
These constraints ensures the extraction of 1D-illuminant invariant image, which is an image that has a certain gray value for each color in the original image, regardless of the lighting. This means that shadows should not appear in this image.
The process needs special calibration. Taking several images of the same scene in different lighting can give us the following graph, where each line represents the same color but in different illumination.
Figure 5 – Example for calibration for the F.H.D. Algorithm
Rotating these results will give us a constant x-value for each color, regardless of the illumination.
Figure 6 – Rotating the graph produces invariant values
Figure 7 – Original and Invariant image. Notice that all the shadows are gone
A shadow edge image can be created by applying edge-detection on the invariant image and the original image, and selecting the edges that exist in the original image but not in the invariant image. This raw shadow edge image can then be manually modified to get better results.
Reintegrating the edges information can be done in several methods, one of them is to remove the edges from the original image derivatives and using a pseudo-inverse filter to reconstruct the shadow free image (the same as in Weiss algorithm).
Figure 8 – F.H.D. algorithm flow-chart and example. The invariant image is extracted from the original image. The shadow edges are found by looking at both the original and invariant image edges (automatic mask), and this mask is manually modified. Removing those edges from the original image derivatives and reconstructing the image produces a shadow free image
Figure 9 – Example for the F.H.D. Algorithm
Tools
The algorithms were implemented in MATLAB running on a personal computer.
The images for the Weiss algorithm were taken in a Nikon Coolpix 995 digital camera and the images for the F.H.D. algorithm in a Nikon D-100 digital camera.
Nikon Coolpix 995 Nikon D-100
Conclusions
Weiss Algorithm
Pros
- Easy to implement
- Fully automatic
- Surprisingly effective – assumes very little
Cons
- Requires multiple images of a static scene in different lighting
- Highly sensitive to input – scene content and sequence length
- Ineffective in removing vague shadows
- Can’t remove static shadows
- High complexity – filtering the images and finding median are high cost functions.
F.H.D. Algorithm
Pros
- Uses a single image
- Preserves the natural colors of the image
- Removes static shadows
- Can use alternative reintegration methods (like Retinex, etc.)
Cons
- The algorithm has three stages – overall sensitivity is high.
- Can’t remove shadows from gray-scale images
- Some area in the image are smoothened – looses image information
- The best results are obtained Manually
Algorithm Comparison
- Both algorithms are robust and effective
- Weiss: Uses one simple stage.
- F.H.D.: Uses three less-than-optimal stages.
- Weiss: Ensures optimal results for optimal input.
- F.H.D.: The results can change even with similar input.
- Weiss: The algorithm’s development has probably reached its limits.
- F.H.D.: Great potential for further development
Acknowledgments
We would like to thank Dr. Yoav Y. Schechner and the VISL staff for their help and guidance during the project, and also to Mr. Bernard Sarel from the Weizmann Institute of Science for his contribution.
We are also grateful to the Ollendorff Minerva Center Fund for supporting this project.