In this paper, we present a new and effective image indexing technique that employs local uni-color and bi-color distributions and local directional distribution of intensity gradient. The image is divided into 4 by 4 non-overlapping blocks. Each block, based on its gradient magnitude, is classified as uniform or non-uniform. Using the average of each color component for the pixels of a uniform block, its representative color is found. Then the histogram of uni-color uniform blocks of the image, HUCUB, is constructed. To each non-uniform block, two representative colors are assigned. Then the histogram of bi-color non-uniform blocks, HBCNB, is created. To represent the shape content of the image, the histogram of directional changes in intensity gradient, HDCIG, is introduced. Experimental results on a database of 2250 images are reported.