Abstract: This work proposes to compare the spatial organization of colors between images through a global optimization procedure relying on the Earth Mover's Distance. The resulting distance between images is applied to image retrieval. Unlike most region-based retrieval systems, no segmentation of images is needed for the query. We then address the decision stage of the retrieval, that is the problem of automatically deciding which images from a database match a query. To this aim, we make use of an a contrario method. Two images are matched if their proximity is unlikely to be due to chance; more precisely, a matching threshold on distances is computed by controlling the average number of false matchings in an unsupervised way. This threshold is adaptive, yielding different numbers of result images depending on the query and the database.