New tools and techniques are needed for effective on-line searching and retrieval of images and video. Color indexing is one process by which the images and videos in the database are retrieved on the basis of their color content. A color indexing system requires that several important objectives are satisfied, namely: automated extraction of color, efficient indexing and effective retrieval. In practice it has been difficult to design a system that simultaneously meets all of these goals. In this paper we propose and evaluate a new system for color indexing that provides for automated extraction of local color regions, efficient indexing and excellent query performance. The system uses the back-projection of binary color sets to identify salient color regions in images and video. By way of iteration over a large number of color sets, localized and arbitrarily shaped color regions are extracted. These are indexed directly by color set value which enables very fast indexing of the collection. Furthermore, information extracted from the regions such as the size, shape and position enables a rich variety of queries that specify not only color content but also the spatial relationships and composition of color regions.