COMPUTING THE KANTOROVICH DISTANCE FOR IMAGES

Computing the Kantorovich distance for images is equivalent to solving a very large transportation problem. The cost-function of this transp ortation problem depends on which distance-function one uses to measur e distances between pixels. In this paper we present an algorithm, wit h a computational complexity of roughly order O(N-2), where N is equal to the number of pixels in the two images, in case the underlying dis tance-function is the L-1-metric, an approximation of the L-2-metric o r the square of the L-2-metric; a standard algorithm would have a comp utational complexity of order O(N-3). The algorithm is based on the cl assical primal-dual algorithm. The algorithm also gives rise to a tran sportation plan from one image to the other and we also show how this transportation plan can be used for interpolation and;possibly also fo r compression and discrimination.