To improve the discrimination power of color indexing techniques we encode a minimal amount of spatial information in the index. We tesselate each image with five partially overlapping, fuzzy regions. In the index we store for each region in an image its average color and the covariance matrix of the color distribution. A similiarity function of these color features is used to match query images with images in the database. In addition we propose two measures to evaluate the performance of image indexing techniques. We present experimental results using an image database which contains more than 11,600 color images.