On the Computation of the Kantorovich Distance for Images
1996 (English)Report (Other academic)
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 in case the underlying distance-function is l) the L1 – metric, 2) an approximation of the L2 – metric or 3) the square of the L2 – metric, 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.
Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 1996. , 58 p.
LiTH-ISY-R, ISSN 1400-3902 ; 1858
Kantarovich distance, Kantarovich metric, image metrics, Hutchinson metric, transportation problems, primal-dual algorithm.
Mathematics Computer Science
IdentifiersURN: urn:nbn:se:liu:diva-132017OAI: oai:DiVA.org:liu-132017DiVA: diva2:1037252