The Optimal Transformation Problem

The optimal transformation problem in step (2)

(2)    g(k+1) = arg ming in G WORK(F(k),x,g(y)).

can be written explicitly in terms of the ground distance function d as

(5)    arg ming in G sumi=1..m, j=1..,n fij d(xi,g(yj)),

where the flow F=(fij) is fixed. The table below shows some cases in which (5) can be solved.

   Transformation Set G       g in G       Ground Distance d   
translation t L2, L1, (L2)2
Euclidean (R,t) (L2)2
similarity (s,R,t) (L2)2
linear A (L2)2
affine (A,t) (L2)2

If we let

[c1 ... cN] = [f11 f12 ... f1n | f21 f22 ... f2n | ... | fm1 fm2 ... fmn],
[a1 ... aN] = [x1 x1 ... x1 | x2 x2 ... x2 | ... | xm xm ... xm], and
[b1 ... bN] = [y1 y2 ... yn | y1 y2 ... yn | ... | y1 y2 ... yn],

where N=mn, then (5) can be rewritten as a single index summation

(6)    ming in G sumr=1..N cr d(ar,g(br)),

In this form, the optimal transformation problem asks for the transformation of one point set which minimizes a sum of weighted distances to corresponding points in another set.

We briefly consider only the easiest case listed in the above table : d=(L2)2 and G=T, the group of translations. In this case, (6) becomes

(7)    mint in T sumr=1..N cr ||ar-(br+t)||2.

It is well known (and easily proven using standard calculus) that the unique optimal translation in the least squares problem (7) is the translation that lines up the centroids of the weighted point sets {(c1,a1), ..., (cN,aN)} and {(c1,b1), ..., (cN,bN)} :

t* = centroid(c,a) - centroid(c,b)

where

centroid(c,a) = sumr=1..N cr ar    /    cS,
centroid(c,b) = sumr=1..N cr br    /    cS,    and
cS = sumr=1..N cr.

In terms of the original flow variables fij and distributions x and y, this solution becomes

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

where we have used the fact that sumi=1..m, j=1..n fij = min(wS,uS) for any feasible flow F between x and y. In the next section, we shall discuss an interesting property of this solution when the distributions x and y have the same total weight.


top Title, Table of Contents, The EMD
prev A Convergent Iteration
next Two Specific Cases


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].

Email comments to scohen@cs.stanford.edu.