An excellent source for applications of the EMD in content-based image retrieval is the work of Y. Rubner. He has successfully applied the EMD to measure global color similarity between images ([5,6,7]) and texture similarity ([4,5,7]). In these cases, the feature space in which the distribution points live and the ground distance used to compare the points are different, but the same EMD framework is applied.

The EMD is a metric between equal-weight distributions whenever the
underlying ground distance is a metric between points. The difficult part
in the proof of this statement is to show that the triangle inequality
holds. Assume that distributions have total weight one, so that the EMD
is exactly the minimum of amount of work to change one distribution into
another. One way to morph **x** into **z** is to use a minimum work
morph of **x** into **y**, and then use a minimum work morph of
**y** into **z**. The cost of the morph through **y**
is EMD(**x**,**y**)+EMD(**y**,**z**). Since
EMD(**x**,**z**) is the minimum amount of work required to change
**x** into **z**, it cannot be more than the work for the particular
morph through **y**. A formal proof of the metric property can be found
in [5].

Another interesting property of the EMD is that the ground distance between the centroids of equal-weight distributions is a lower bound on their EMD for any ground distance between points induced by a vector norm (e.g. the Euclidean distance between points is the Euclidean norm of their difference). There are also lower bounds for the equal-weight case which use the EMD between projections of the distributions onto lines through the origin. The EMD between equal-weight 1D distributions can be computed much more efficiently than the EMD between more general distributions. Some information on the EMD in 1D can be found in this document, in the section on the EMD under translation in 1D. The technical report [1] covers the previously mentioned lower bounds, as well as centroid-based and projection-based lower bounds which can be applied in the partial matching case.

The EMD is more general than the way I have described it thus far.
There is actually nothing in its formulation that assumes
the x_{i}'s and the y_{j}'s in distributions **x**
and **y** are points. The defining linear program uses only the distance
d(x_{i},y_{j}), so x_{i} and y_{j} could
be any objects between which a distance can be computed. It is not
necessary that these objects have a point representation, or that the
ground distance is some standard point distance such as L_{2} or
L_{1}. In general, the EMD is a distance measure between two sets
of weighted objects which is built upon a distance between individual
objects.

top | Title, Table of Contents, The EMD |

prev | Formal Definition |

next | The Earth Mover's Distance Under Transformations |

Email comments to scohen@cs.stanford.edu.