Earth mover's distance

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer science, the earth mover's distance (EMD) is a measure of the distance between two probability distributions over a region D. In mathematics, this is known as the Wasserstein metric. Informally, if the distributions are interpreted as two different ways of piling up a certain amount of dirt over the region D, the EMD is the minimum cost of turning one pile into the other; where the cost is assumed to be amount of dirt moved times the distance by which it is moved.[1]

The above definition is valid only if the two distributions have the same integral (informally, if the two piles have the same amount of dirt), as in normalized histograms or probability density functions. In that case, the EMD is equivalent to the 1st Mallows distance or 1st Wasserstein distance between the two distributions.[2][3]

Extensions[edit]

Some applications may require the comparison of distributions with different total masses. One approach is to allow for a partial match, where dirt from the most massive distribution is rearranged to make the least massive, and any leftover "dirt" is discarded at no cost. Under this approach, the EMD is no longer a true distance between distributions.

Another approach is to allow for mass to be created or destroyed, on a global and/or local level, as an alternative to transportation, but with a cost penalty. In that case one must specify a real parameter σ, the ratio between the cost of creating or destroying one unit of "dirt", and the cost of transporting it by a unit distance. This is equivalent to minimizing the sum of the earth moving cost plus σ times the L1 distance between the rearranged pile and the second distribution.

Notationally, if \pi:P\to Q is a partial function which is a bijection on subsets P'\subset P and Q'\subset Q, then one is interested in the distance function

|P-Q|_\pi = |P\setminus P'| + |Q\setminus Q'|

where P\setminus P' denotes set minus. Here, P' would be the portion of the earth that was moved; thus P\setminus P' would be the portion not moved, and |P\setminus P'| the size of the pile not moved. By symmetry, one contemplates Q'\subset Q as the pile at the destination that 'got there' from P, as compared to the total Q that we want to have there. Formally, this distance indicates how much an injective correspondence differs from an isomorphism.

Computing the EMD[edit]

If the domain D is discrete, the EMD can be computed by solving an instance transportation problem, which can be solved by the so-called Hungarian algorithm. In particular, if D is a one-dimensional array of "bins" the EMD can be efficiently computed by scanning the array and keeping track of how much dirt needs to be transported between consecutive bins. For example:

EMD0 = 0
EMDi+1 = ( Ai + EMDi ) - Bi
TotalDistance = ∑ | EMDi |

EMD based Similarity Analysis[edit]

EMD based Similarity Analysis (EMDSA) is an important and effective tool in many multimedia information retrieval[4] and pattern recognition[5] applications. However, the computational cost of EMD is super-cubic to the number of the "bins" given an arbitrary "D".

Applications[edit]

An early application of the EMD in computer science was to compare two grayscale images that may differ due to dithering, blurring, or local deformations.[6] In this case, the region is the image's domain, and the total amount of light (or ink) is the "dirt" to be rearranged.

The EMD is widely used in content-based image retrieval to compute distances between the color histograms of two digital images. In this case, the region is the RGB color cube, and each image pixel is a parcel of "dirt". The same technique can be used for any other quantitative pixel attribute, such as luminance, gradient, apparent motion in a video frame, etc..

More generally, the EMD is used in pattern recognition to compare generic summaries or surrogates of data records called signatures. A typical signature consists of list of pairs ((x1,m1), … (xn,mn)), where each xi is a certain "feature" (e.g., color in an image, letter in a text, etc.), and mi is "mass" (how many times that feature occurs the record). Alternatively, xi may be the centroid of a data cluster, and mi the number of entities in that cluster. To compare two such signatures with the EMD, one must define a distance between features, which is interpreted as the cost of turning a unit mass of one feature into a unit mass of the other. The EMD between two signatures is then the minimum cost of turning one of them into the other.

History[edit]

The concept was first introduced by Gaspard Monge in 1781,[7] and anchors the field of transportation theory. The use of the EMD as a distance measure for monochromatic images was described in 1989 by S. Peleg, M. Werman and H. Rom.[6] The name "earth movers' distance" was proposed by J. Stolfi in 1994,[8] and was used in print in 1998 by Y. Rubner, C. Tomasi and L. G. Guibas.[9]

References[edit]

  1. ^ Formal definition
  2. ^ Elizaveta Levina; Peter Bickel (2001). "The EarthMover’s Distance is the Mallows Distance: Some Insights from Statistics". Proceedings of ICCV 2001 (Vancouver, Canada): 251–256. 
  3. ^ C. L. Mallows (1972). "A note on asymptotic joint normality". Annals of Mathematical Statistics 43 (2): 508–515. doi:10.1214/aoms/1177692631. 
  4. ^ Mark A. Ruzon; Carlo Tomasi (2001). "Edge, Junction, and Corner Detection Using Color Distributions". IEEE Transaction on Pattern Analysis and Machine Intelligence. 
  5. ^ Kristen Grauman; Trevor Darrel (2004). "Fast contour matching using approximate earth mover's distance". Proceedings of CVPR 2004. 
  6. ^ a b S. Peleg; M. Werman; H. Rom (1989). "A unified approach to the change of resolution: Space and gray-level". IEEE Transactions on Pattern Analysis and Machine Intelligence 11: 739–742. doi:10.1109/34.192468. 
  7. ^ "Mémoire sur la théorie des déblais et des remblais". Histoire de l’Académie Royale des Science, Année 1781, avec les Mémoires de Mathématique et de Physique. 1781. 
  8. ^ J. Stolfi, personal communication to L. J. Guibas, 1994
  9. ^ Yossi Rubner; Carlo Tomasi; Leonidas J. Guibas (1998). "A Metric for Distributions with Applications to Image Databases". Proceedings ICCV 1998: 59–66. 

External links[edit]