We consider image retrieval based on minimum distortion selection of features of color images modelled by Gauss mixtures. The proposed algorithm retrieves the image in a database having minimum distortion when the query image is encoded by a separate Gauss mixture codebook representing each image in the database. We use Gauss mixture vector quantization (GMVQ) for clustering Gauss mixtures, instead of the conventional expectation-maximization (EM) algorithm. Experimental comparison shows that the simpler GMVQ and the EM algorithms have close Gauss mixture parameters with similar convergence speeds. We also provide a new color-interleaving method, reducing the dimension of feature vectors and the size of covariance matrices, thereby reducing computation. This method shows a slightly better retrieval performance than the usual color-interleaving method in HSV color space. Our proposed minimum distortion image retrieval performs better than probabilistic image retrieval.