Earth mover's distance as a metric for image retrieval


Journal Article

We investigate the properties of a metric between two distributions, the Earth Mover's Distance (EMD), for content-based image retrieval. The EMD is based on the minimal cost that must be paid to transform one distribution into the other, in a precise sense, and was first proposed for certain vision problems by Peleg, Werman, and Rom. For image retrieval, we combine this idea with a representation scheme for distributions that is based on vector quantization. This combination leads to an image comparison framework that often accounts for perceptual similarity better than other previously proposed methods. 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.

Full Text

Duke Authors

Cited Authors

  • Rubner, Y; Tomasi, C; Guibas, LJ

Published Date

  • November 1, 2000

Published In

Volume / Issue

  • 40 / 2

Start / End Page

  • 99 - 121

International Standard Serial Number (ISSN)

  • 0920-5691

Digital Object Identifier (DOI)

  • 10.1023/A:1026543900054

Citation Source

  • Scopus