liu.seSearch for publications in DiVA
Change search

On the Computation of the Kantorovich Distance for Images
##### Abstract [en]

The Kantorovich distance for images can be defined for grey valued images with equal total grey value. Computing the Kantorovich distance is equivalent to solving a large transportation problem. The cost-function of this transportation problem depends on which distance-function one uses to measure distances between pixels.

In this paper we present an algorithm, which is roughly of the order $\small\mathcal O\text(N^{2.2})$ in case the underlying distance-function is l) the L1 – metric, 2) an approximation of the L2metric or 3) the square of the L2metric, where N is equal to the number of pixels in the two images. The algorithm is based on the classical primal-dual algorithm.

The algorithm also gives rise to a transportation plan from one image to the other and we also show how this transportation plan can be used for interpolation and possibly also for compression and discrimination.

##### Series
LiTH-ISY-R, ISSN 1400-3902 ; 1858
##### Keyword [en]
Kantarovich distance, Kantarovich metric, image metrics, Hutchinson metric, transportation problems, primal-dual algorithm.
##### National Category
Mathematics Computer Science
##### Identifiers
OAI: oai:DiVA.org:liu-132017DiVA: diva2:1037252
Available from: 2016-10-14 Created: 2016-10-14 Last updated: 2016-10-14Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 13292 kBChecksum SHA-512
Type fulltextMimetype application/pdf

#### Search in DiVA

Kaijser, Thomas
##### By organisation
Department of MathematicsThe Institute of Technology
##### On the subject
MathematicsComputer Science