An improvement of the primal-dual algorithm in order to compute the Kantorovich distance for images.

Let P and Q denote two digital grey-valued images with equal total grey value.
Let (x,y) denote a generic pixel in image P and let p(x,y) denote its grey value.
Similarly, let (u,v) denote a generic pixel in image Q and q(u,v) its grey value.
Let d((x,y),(u,v)) be a distance function between pixels.

The Kantorovich distance, between P and Q is the minimum cost to transfer the
"mass" {p(x,y): (x,y) pixel of P} representing the image P, to the "mass" {q(u,v):(u,v) pixel of Q} representing the image Q, when the cost-function is determined by the distance function d((x,y),(u,v)).

In principle this problem is a standard balanced transportation problem, and methods for solving such a problem is taught at technical universities all over the world.

The problem though - when trying to use available programs from the internet or implement one's own computer program based on standard algorithms - for computing the Kantorovich distance for images with equal total grey value, is that the number of pixels in the two images is often too large for such programs to be applicable.

In this talk I shall show that by using properties of the distance function d((x,y),(u,v)) it is possible to reduce the computation time of the Kantorovich distance between images of equal total grey value considerably. Roughly speaking the computitonal complexity decreases from order 3 to order 2 and since the number of pixels can be of order several hundred thousands, this reduction can make a big difference in computation time.

As distance function I will consider the Manhattan metric (d((x,y),(u,v))=|x-u|+|y-v|), the square of the Euclidean metric and the Euclidean metric.