A Parallel Method for Earth Mover's Distance

Wuchen Li, Ernest K. Ryu, Stanley Osher, Wotao Yin, and Wilfrid Gangbo

To appear in Journal of Scientific Computing’17

Overview

This paper presents a new, parallel algorithm to approximate the Earth Mover's distance (EMD). By the theory of optimal transport, EMD can be reformulated as a familiar L1 type minimization. We use a regularization that gives us a unique solution for this L1 type problem. The new regularized minimization is very similar to problems which have been solved in the fields of compressed sensing and image processing, where several fast methods are available. In this paper, we adopt a primal-dual algorithm designed there, which uses very simple updates at each iteration and is shown to converge very rapidly. Several numerical examples are provided.

 

Left is the EMD-L2 map between the standing cat and the crouching cat.

Right is the EMD-L1 map between the two cats.

Citation

W. Li, E. Ryu, S. Osher, W. Yin, and W. Gangbo, A Parallel Method for Earth Mover's Distance. Journal of Scientific Computing, to appear, 2017.


« Back