Computation of the Kantorovich Distance for Images (Metod foer Beraekning avKantorovich-Avstandet foer Bilder)

摘要

We introduce some concepts, in particular the notion of a transportation image,and give the definition of the Kantorovich distance between images in terms of transportation images. In section 3, we formulate the Kantorovich distance as the solution to a linear programming problem, and in section 4, we present the dual version of this linear programming problem. In sections 5 to 11, we present the primal-dual algorithm for the transportation problem and in section 12, we make some comments regarding the primal-dual algorithm when applied to large transportation problems. In section 13, we make a short digress and present the Kantorovich distance for probability measures, and present the duality theorem in this situation. In section 14, we repeat the formulation of the definition of the Kantorovich distance for images, in section 15, we briefly discuss how one can handle images with unequal total grey values and in section 16, we describe the so called 'subtraction step' which one always can do when the underlying distance-function is a metric. In sections 17 and 18, we describe the properties that reduce the search for the so called admissable arcs, which decreases the computation time considerably. In section 19, we discuss how to obtain 'arc-minimal' solutions.