Report Number: CS-TN-98-86
Institution: Stanford University, Department of Computer Science
Title: The Earth Mover's Distance as a Metric for Image Retrieval
Author: Rubner, Yossi
Author: Tomasi, Carlo
Author: Guibas, Leonidas J.
Date: September 1998
Abstract: We introduce a metric between two distributions that we call
the Earth Mover's Distance (EMD). The EMD is based on the
minimal cost that must be paid to transform one distribution
into the other, in a precise sense. We show that the EMD has
attractive properties for content-based image retrieval. The
most important one, as we show, is that it matches perceptual
similarity better than other distances used for image
retrieval. The EMD is based on a solution to the
transportation problem from linear optimization, for which
efficient algorithms are available, and also allows naturally
for partial matching. It is more robust than histogram
matching techniques, in that it can operate on
variable-length representations of the distributions that
avoid quantization and other binning problems typical of
histograms. When used to compare distributions with the same
overall mass, the EMD is a true metric. In this paper we
focus on applications to color and texture, and we compare
the retrieval performance of the EMD with that of other
distances.
http://i.stanford.edu/pub/cstr/reports/cs/tn/98/86/CS-TN-98-86.pdf