Earth mover's distance

The earth movers distance (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.

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 featuresfact|date=July 2008 but distances still can be computed between object with different number of features.

In order to do so, the EMD between two objects is defined as the level of effort needed to change one object into the other [ [http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/RUBNER/emd.htm Formal definition] ] . The definition of the effort relies on user defined distances for each feature used. Also, "the sum of weights of one signature can be different than the sum of weights of the other (partial match)" [http://myditto.tistory.com/tag/Stanford] .

If the signatures are normalized histograms or probability density functions, then EMD is equivalent to Mallows distance / Wasserstein metric [ 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.] .

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 [Peleg, S., Werman, M., and Rom, H. 1989. A unified approach to the change of resolution: Space and gray-level. IEEE Transactions onPattern Analysis and Machine Intelligence, 11:739–742] . The name "earth movers' distance" was proposed by J. Stolfi in 1994 [J. Stolfi, personal communication to L. J. Guibas, 1994] , and was used in print in 1998 by Y. Rubner, C. Tomasi and L. G. Guibas [Yossi Rubner, Carlo Tomasi, Leonidas J. Guibas: A Metric for Distributions with Applications to Image Databases. Proceedings ICCV 1998: 59-66] .

References