Shadows cause a significant problem for automated systems which attempt to understand scenes, since shadow boundaries may be incorrectly recognised as a material change, and incorrectly recognised as an object. Shadow identification is therefore an important pre-processing step for applications such as shadow removal, shadow invariant object recognition and shadow invariant object tracking. Many existing shadow identification methods are often limited by the types of shadow boundaries (penumbra) which can be found, by the density (darkness) of the shadows and by the type of surface texture on which the shadows are cast. In addition many of these methods are limited to a specific type of scene, while others result in high levels of false positive (FP) shadow identification. To address these problems, a novel algorithm for automatic shadow identification is proposed, which makes use of a new tree-structured segmentation algorithm for candidate shadow region identification, as well as a combination of colour illumination invariance and texture analysis for shadow verification. The method is tested on a number of indoor and outdoor images exhibiting different types of shadows, surfaces and illumination sources. These results indicate that the proposed method performs well against the state of the art; in particular, the rate of FP identification is reduced from 26 to below 13% when compared with using illumination invariance alone.