Recently, some image retrieval systems have begun to move away from histogram techniques and begun to make use of segmentation to extract and index features. The representative color or region color descriptor is more compact and can be easily incorporated with spatial features. However, the spatial feature is less investigated and confined to some simple geometric properties, such as centroid, area, etc. In this paper, we present a novel and efficient scheme for extracting, indexing, and retrieving color images. The scheme is built upon a region-based image retrieval and is based on the observed fact that a small number of colors are usually enough to characterize the color information in an image. First, we propose a color clustering method to better capture color properties of the image. Then, we will present a new method to characterize the spatial feature by using spatial histograms. The proposed method computes image features automatically from a given image and they can be used to retrieve images. The experiments were conducted to establish the retrieval capabilities of our approach. The retrieval quality is measured by the retrieval rate. Experimental results are reported indicating that our approach performs very well and gives very good retrieval efficiency.