Signal Processing - July 2017 - 45

continuous formulation is helpful in problems where a point-topoint assignment is desired, Kantarovich's formulation is more
general and also covers the case of discrete (Dirac) masses (in
our case, signal intensities). These not only differ in mathematical formulation but also have consequences with regard to
their respective numerical solutions as well as applications.

Monge's continuous formulation
The Monge optimal mass transport problem is formulated as
follows. Consider two signals or images I0 and I1 defined over
their respective domains X 0 and X 1 . Here, X 0 and X 1 are
typically subsets of R d and can often be taken as the unit
square (or cube in three dimensions). Although a detailed
measure-theoretic formulation is typically required (see [24]),
we bypass the rigorous formulation here and simply assume
that I 0 (x) and I 1 (y) correspond to signal intensities at positions x ! X 0 and y ! X 1. For digital signals, an interpolating
model can be used to construct these functions defined over
continuous domains from sampled discrete data. The signals
are required to be nonnegative, i.e., I 0 (x) $ 0 6x ! X 0
and I 1 (y) $ 0 6y ! X 1. In addition, the total amount of
signal  (or mass) for both signals should be equal to the
same constant (which is generally chosen to be 1):
#X0 I 0 (x) dx = #X1 I 1 (y) dy = 1. In other words, I0 and I1 are
assumed to be probability density functions (PDFs).
Monge's optimal transportation problem is to find a function f: X 0 " X 1 that pushes I0 onto I1 and minimizes the
objective function,
M (I 0, I 1) = inf

#

f ! MP X 0

c (x, f (x)) I 0 (x) dx,

(1)

more than a century, the answers to questions regarding
existence and characterization of the Monge's problem
remained unknown.
For certain measures, the Monge's formulation of the optimal transport problem is ill posed in the sense that there is no
transport map to rearrange one PDF to another. For instance,
consider the case where I0 is a Dirac mass and I1 is not. Kantorovich's formulation alleviates this problem by finding the
optimal transport plan as opposed to the transport map.

Kantorovich's formulation
Kantorovich formulated the transport problem by optimizing
over transportation plans, which we denote as c. One can
think of c as the joint distribution of I0 and I1 describing
how much mass is being moved to different coordinates; i.e.,
let A be a subset of X 0 and similarly B 3 X 1 . For notational simplicity, we will not make a distinction between a
probability distribution and its density. More precisely,
we associate a probability distribution to a signal I 0 by
I 0 (A) = # I 0 (x) dx.
A
The quantity c (A # B) tells us how much mass in set A is
being moved to set B. Here, the MP constraint can be expressed
as c (X 0 # B) = I 1 (B) and c (A # X 1) = I 0 (A) . Kantorovich's
formulation for the optimal transport problem can then be
written as
K (I 0, I 1) = min
! MP
c

c (x, y) dc (x, y) .

(4)

1

f

I0

I1

X

Y

B
A = {x : f (x ) ∈ B }

(2)

1{x : f (x )∈B} I0(x )dx = 1B I1(y )dy = 1{x : f (x )∈B} det (D f (x ))I1(f (x ))dx

If f is one to one, this just means that for A 1 X 0,

(a)

#A I 0 (x) dx = #f(A) I 1 (y) dy.

γ (x, y )
0.5

Such maps f ! MP are sometimes called transport maps
or mass-preserving maps. Simply put, the Monge formulation
of the problem seeks to rearrange signal I0 into signal I1 while
minimizing a specific cost function. In cases when f is smooth
and one to one, then the requirement (2) can be written in a
differential form as
det (Df (x)) I 1 ( f (x)) = I 0 (x)

0

Note that the integration notation dc (x, y) is meant to represent the fact that this integral is more general than the routine

where c: X 0 # X 1 " R + is the cost of moving pixel intensity
I 0 (x) from x to f(x) [Monge considered the Euclidean distance
as the cost function in his original formulation,
c (x, f (x)) = x - f (x) @, and MP stands for a measure preserving map that moves all the signal intensity from I0 to I1. That
is, for a subset B 1 X 1 the MP requirement is that

#{x : f(x) ! B} I 0 (x) dx = #B I 1 (y) dy.

#X # X

x1

0.25

y3

0.25

y3
y2

0.25
x2

y2

0.25

y1

0.5
x1

3
I0(x ) = δ (x - x1)
4
+ 1 δ (x - x2)
4

(3)

almost everywhere, where Df is the Jacobian of f [see
Figure 1(a)]. Note that both the objective function and the
constraint in (1) are nonlinear with respect to f(x). Hence, for

y1

x2

1
1
I1(y ) = δ (y - y1) + δ (y - y2)
2
4
+ 1 δ (y - y3)
4
(b)

FIGURE 1. (a) The Monge transport map and (b) Kantorovich's
transport plan.

IEEE SIGNAL PROCESSING MAGAZINE

|

July 2017

|

45
Table of Contents for the Digital Edition of Signal Processing - July 2017
