Two Specific Cases

In this section, we examine two specific cases in which there is a direct solution to the EMD under transformation problem.

Equal-Weight Distributions under Translation with d=(L2)2

Recall the unique solution (8)

(8)    t* = sumi=1..m, j=1..n fij xi    /    min(wS,uS)    -    sumi=1..m, j=1..n fij yj    /    min(wS,uS)

to the optimal transformation problem when the transformation set is translation and the ground distance is the Euclidean distance squared. When x and y are equal-weight distributions, we must have

(9)    sumj=1..n fij = wi    and    sumi=1..m fij = uj

for any feasible flow between x and y. This is because all the mass in both distributions must be matched when the two distributions have the same total weight. Substituting (9) into (8), we see that

t* = centroid(x) - centroid(y),

where

 centroid(x) = sumi=1..m wi xi    /    wS,    and centroid(y) = sumj=1..n uj yj    /    uS.

Here we have also used the fact that x and y are equal-weight distributions: wS=uS=min(wS,uS).

We have shown that the optimal translation in this case does not depend on the feasible flow used. The translation t* which lines up the centroids of x and y is the unique optimal translation for every feasible flow. To compute the EMD under translation between equal-weight distributions with d=(L2)2, we simply compute EMD(x,y+centroid(x)-centroid(y)). Although our iteration is not needed here, it is guaranteed to converge to the global minimum of the WORK function in this case. In fact, it will converge in only a couple of steps since g(2)=g(1)=t*.

Equal-Weight Distributions in 1D under Translation

In this section, we consider matching equal-weight distributions on the real line under translation, with the absolute value (d=L1) as the ground distance. Consider the distributions shown in the left half of the figure below, where x is the dark distribution and y is the light distribution.

It turns out that there is a simple solution to computing the EMD between equal weight distributions in 1D that involves the cumulative distribution functions (CDFs) of the distributions. The CDF for x starts at 0, increases an amount wi at each point xi, and eventually becomes constant=wS at the largest point xm. The CDF for x is the bold staircase graph, while the CDF for y is the regular thickness staircase graph. Since x and y are equal-weight distributions, the two CDFs become constant at the same value wS=uS. The EMD between x and y is equal to the area between the CDFs of x and y divided by the total weight wS=uS. The area between the CDFs is shaded, and the corresponding optimal flow is indicated with arrows. This optimal flow is called the CDF flow, and is denoted FCDF.

The CDF flow is given by

fCDFij = | [Wi-1,Wi] intersect [Uj-1,Uj] |,    i=1..m, j=1..n,

where

Wi = sumk=1..i wk    and    Uj = suml=1..j uj

are the partial sums of the distribution weight vectors w and u, W0 = U0 = 0, and |X| denotes the size of interval X. The partial sums U0, U1, ..., Un are the same for y and every translated version of y. This means that the CDF flow is an optimal flow between x and y+t for every translation t. An EMD computation between x and a translation of y is shown in the right half of the above figure. To compute the EMD under translation between equal-weight distributions in 1D with d=L1, we simply solve the optimal translation problem for the fixed flow F=FCDF. The optimal translation problem with d=L1 is covered in [1].

The ideas and results contained in this document are part of my thesis, which will be published as a Stanford computer science technical report in June 1999.

S. Cohen. Finding Color and Shape Patterns in Images. Thesis Technical Report STAN-CS-TR-99-?. To be published June 1999.

Similar ideas applied to the EMD under translation have already been published in the technical report [1].