Earth Mover's Distance

From Wikipedia, the free encyclopedia

 This computer science article is in need of attention from an expert on the subject.
Please help recruit one or improve this article yourself. See the talk page for details.
Please consider using {{Expert-subject}} to associate this request with a WikiProject
This article does not cite any references or sources. (June 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.
This article or section needs to be wikified to meet Wikipedia's quality standards.
Please help improve this article with relevant internal links. (June 2007)

The earth movers distance or EMD is a mathematical measure of the difference between two distributions over some region. Informally, if the distributions are interpreted as two different ways of piling up a certain amount of dirt over the region, the EMD is the cost of turning one pile into the other; which is assumed to be minimum amount of dirt that must be moved, times the distance by which the dirt has to be carried.

from robotics.stanford.edu

EMD is used to compute distances between objects that are defined by a lists of computed features called the signature. The main idea is that the features are defined by the user and thus can be of any type, in any number of dimensions. Moreover the signature can have a various number of features (this claim needs confirmation !) but distances still can be computed between object with different number of features.

In order to do so, the EMD between two object is defined as the level of effort needed to change one object into the other. The definition of the effort rely on the user defined distances for each features used. Also, "the sum of weights of one signature can be different than the sum of weights of the other (partial match)" (source of citation [1]).

Contents

[edit] History

The use of the EMD as a distance measure for monochromatic images was described in 1989 by S. Peleg, M. Werman and H. Rom [1]. The name "earth movers' distance" was proposed by J. Stolfi in 1994 [2], and was used in print in 1998 by Y. Rubner, C. Tomasi and L. G. Guibas[3].

[edit] Related distances

If the signatures are normalized histograms or probability density functions, then EMD is equivalent to Mallows distance / Wasserstein metric [4].

[edit] References

  1. ^ Peleg, S., Werman, M., and Rom, H. 1989. A unified approach to the change of resolution: Space and gray-level. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11:739–742
  2. ^ J. Stolfi, personal communication to L. J. Guibas, 1994
  3. ^ Yossi Rubner, Carlo Tomasi, Leonidas J. Guibas: A Metric for Distributions with Applications to Image Databases. Proceedings ICCV 1998: 59-66
  4. ^ Elizaveta Levina, Peter Bickel. The EarthMover’s Distance is the Mallows Distance: Some Insights from Statistics. In Proceedings of ICCV 2001, Vancouver, Canada, p. 251-256.

[edit] External links

  • formal definition here [2]
Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.