In computer science, the earth mover's distance (EMD)^[1] is a measure of dissimilarity between two frequency distributions, densities, or measures, over a metric space D. Informally, if the distributions are interpreted as two different ways of piling up earth (dirt) over D, the EMD captures the minimum cost of building the smaller pile using dirt taken from the larger, where cost is defined as the amount of dirt moved multiplied by the distance over which it is moved.

The earth mover's distance is also known as Wasserstein metric ${\displaystyle W_{1}}$, Kantorovich–Rubinstein metric, or Mallows's distance.^[2] It is the solution of the optimal transport problem, which in turn is also known as the Monge-Kantorovich problem, or sometimes the Hitchcock–Koopmans transportation problem;^[3] when the measures are uniform over a set of discrete elements, the same optimization problem is known as minimum weight bipartite matching.

The EMD between probability distributions ${\textstyle P}$ and ${\textstyle Q}$ can be defined as an infimum over joint probabilities:

${\displaystyle {\text{EMD}}(P,Q)=\inf \limits _{\gamma \in \Pi (P,Q)}\mathbb {E} _{(x,y)\sim \gamma }\left[d(x,y)\right]\,}$

where ${\displaystyle \Pi (P,Q)}$ is the set of all joint distributions whose marginals are ${\displaystyle P}$ and ${\displaystyle Q}$.

By Kantorovich-Rubinstein duality, this can also be expressed as:

${\displaystyle {\text{EMD}}(P,Q)=\sup \limits _{\|f\|_{L}\leq 1}\,\mathbb {E} _{x\sim P}[f(x)]-\mathbb {E} _{y\sim Q}[f(y)]\,}$

where the supremum is taken over all 1-Lipschitz continuous functions, i.e. ${\displaystyle \|\nabla f(x)\|\leq 1\quad \forall x}$.

The EMD can be computed by solving an instance of transportation problem, using any algorithm for minimum-cost flow problem, e.g. the network simplex algorithm.

The Hungarian algorithm can be used to get the solution if the domain D is the set {0, 1}. If the domain is integral, it can be translated for the same algorithm by representing integral bins as multiple binary bins.

As a special case, if D is a one-dimensional array of "bins" of size n, the EMD can be efficiently computed by scanning the array and keeping track of how much dirt needs to be transported between consecutive bins. Here the bins are zero-indexed:

${\displaystyle {\begin{aligned}{\text{EMD}}_{0}&=0\\{\text{EMD}}_{i+1}&=P_{i}+{\text{EMD}}_{i}-Q_{i}\\{\text{Total Distance}}&=\sum _{i=0}^{n}|{\text{EMD}}_{i}|\end{aligned}}}$

EMD-based similarity analysis (EMDSA) is an important and effective tool in many multimedia information retrieval^[6] and pattern recognition^[7] applications. However, the computational cost of EMD is super-cubic to the number of the "bins" given an arbitrary "D". Efficient and scalable EMD computation techniques for large scale data have been investigated using MapReduce,^[8][9] as well as bulk synchronous parallel and resilient distributed dataset.^[10]

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.^[11] 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.^{[citation needed]} 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.^[1] A typical signature consists of list of pairs ((x₁,m₁), ... (x_n,m_n)), where each x_i is a certain "feature" (e.g., color in an image, letter in a text, etc.), and m_i is "mass" (how many times that feature occurs in the record). Alternatively, x_i may be the centroid of a data cluster, and m_i 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.

EMD analysis has been used for quantitating multivariate changes in biomarkers measured by flow cytometry, with potential applications to other technologies that report distributions of measurements.^[12]

The concept was first introduced by Gaspard Monge in 1781,^[13] in the context 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.^[11] The name "earth mover's distance" was proposed by J. Stolfi in 1994,^[14] and was used in print in 1998 by Y. Rubner, C. Tomasi and L. G. Guibas.^[15]

• Monge–Ampère equation