Removing shadows casted by moving foreground objects in a scene is a critical problem for many vision-based applications. We propose two algorithms that examine color/texture invariants, and exploit spatial-temporal consistency to detect shadows efficiently and reliably. The first algorithm assumes a static background model while the second algorithm addresses the perturbations of dynamic background in natural scenes. The experimental results show that the proposed methods can detect penumbra as well as umbra in different kinds of scenarios under various illumination conditions.