The Earth Mover's Distance

The Earth Mover's Distance (EMD) is a method to evaluate dissimilarity between two multi-dimensional distributions in some feature space where a distance measure between single features, which we call the ground distance is given. The EMD ``lifts'' this distance from individual features to full distributions.

Intuitively, given two distributions, one can be seen as a mass of earth properly spread in space, the other as a collection of holes in that same space. Then, the EMD measures the least amount of work needed to fill the holes with earth. Here, a unit of work corresponds to transporting a unit of earth by a unit of ground distance.

A distribution can be represented by a set of clusters where each cluster is represented by its mean (or mode), and by the fraction of the distribution that belongs to that cluster. We call such a representation the signature of the distribution. The two signatures can have different sizes, for example, simple distributions have shorter signatures than complex ones.

Computing the EMD is based on a solution to the well-known transportation problem [1]. Suppose that several suppliers, each with a given amount of goods, are required to supply several consumers, each with a given limited capacity. For each supplier-consumer pair, the cost of transporting a single unit of goods is given. The transportation problem is then to find a least-expensive flow of goods from the suppliers to the consumers that satisfies the consumers' demand. Matching signatures can be naturally cast as a transportation problem by defining one signature as the supplier and the other as the consumer, and by setting the cost for a supplier-consumer pair to equal the ground distance between an element in the first signature and an element in the second. Intuitively, the solution is then the minimum amount of ``work'' required to transform one signature into the other.

This can be formalized as the following linear programming problem: Let $P=\{(p_1,w_{p_1}),\ldots,(p_m,w_{p_m})\}$ be the first signature with m clusters, where pi is the cluster representative and wpi is the weight of the cluster; $Q=\{(q_1,w_{q_1}),\ldots,(q_n,w_{q_n})\}$ the second signature with n clusters; and ${\bf D}=[d_{ij}]$ the ground distance matrix where dij is the ground distance between clusters pi and qj.

We want to find a flow ${\bf F}= [f_{ij}]$, with fij the flow between pi and qj, that minimizes the overall cost

\begin{displaymath}\mbox{WORK}(P,Q,{\bf F}) = \sum_{i=1}^{m}\sum_{j=1}^{n} f_{ij}d_{ij} \;,

subject to the following constraints:

\begin{eqnarray*}f_{ij} &\ge& 0 \qquad 1 \le i \le m ,\: 1 \le j \le n \\
...f_{ij} &=&
\min(\sum_{i=1}^{m}w_{p_i},\sum_{j=1}^{n}w_{q_j})\;, \end{eqnarray*}

The first constraint allows moving ``supplies'' from P to Q and not vice versa. The next two constraints limits the amount of supplies that can be sent by the clusters in P to their weights, and the clusters in Q to receive no more supplies than their weights; and the last constraint forces to move the maximum amount of supplies possible. We call this amount the total flow. Once the transportation problem is solved, and we have found the optimal flow ${\bf F}$, the earth mover's distance is defined as the work normalized by the total flow:

\begin{displaymath}\mbox{EMD}(P, Q) =
\frac{\sum_{i=1}^{m}\sum_{j=1}^{n} f_{ij}d_{ij}}
{\sum_{i=1}^{m}\sum_{j=1}^{n} f_{ij}} \;.

The normalization factor is introduced in order to avoid favoring smaller signatures in the case of partial matching.

The EMD has the following advantages

More details on the EMD can be found in [2].

F. L. Hitchcock.
The distribution of a product from several sources to numerous localities.
J. Math. Phys., 20:224-230, 1941.

Y. Rubner, C. Tomasi, and L. J. Guibas.
A metric for distributions with applications to image databases.
In IEEE International Conference on Computer Vision, pages 59-66, January 1998.