(2) | g^{(k+1)} | = | arg | min_{g in G} | WORK(F^{(k)},x,g(y)). |
can be written explicitly in terms of the ground distance function d as
where the flow F=(f_{ij}) 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 | L_{2}, L_{1}, (L_{2})^{2} |
Euclidean | (R,t) | (L_{2})^{2} |
similarity | (s,R,t) | (L_{2})^{2} |
linear | A | (L_{2})^{2} |
affine | (A,t) | (L_{2})^{2} |
If we let
[c_{1} ... c_{N}] | = | [f_{11} f_{12} ... f_{1n} | f_{21} f_{22} ... f_{2n} | ... | f_{m1} f_{m2} ... f_{mn}], |
[a_{1} ... a_{N}] | = | [x_{1} x_{1} ... x_{1} | x_{2} x_{2} ... x_{2} | ... | x_{m} x_{m} ... x_{m}], and |
[b_{1} ... b_{N}] | = | [y_{1} y_{2} ... y_{n} | y_{1} y_{2} ... y_{n} | ... | y_{1} y_{2} ... y_{n}], |
where N=mn, then (5) can be rewritten as a single index summation
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=(L_{2})^{2} and G=T, the group of translations. In this case, (6) becomes
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 {(c_{1},a_{1}), ..., (c_{N},a_{N})} and {(c_{1},b_{1}), ..., (c_{N},b_{N})} :
t^{*} | = | centroid(c,a) - centroid(c,b) |
where
centroid(c,a) | = | sum_{r=1..N} c_{r} a_{r} / c^{S}, |
centroid(c,b) | = | sum_{r=1..N} c_{r} b_{r} / c^{S}, and |
c^{S} | = | sum_{r=1..N} c_{r}. |
In terms of the original flow variables f_{ij} and distributions x and y, this solution becomes
where we have used the fact that sum_{i=1..m, j=1..n} f_{ij} = min(w^{S},u^{S}) 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.