Skip to main content
SpringerLink
Log in

A Parallel Method for Earth Mover’s Distance

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

Abstract

We propose a new algorithm to approximate the Earth Mover’s distance (EMD). Our main idea is motivated by the theory of optimal transport, in which EMD can be reformulated as a familiar \(L_1\) type minimization. We use a regularization which gives us a unique solution for this \(L_1\) 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Beckmann, M.: A continuous model of transportation. Econometrica 20, 643–660 (1952)

    Article  MathSciNet  MATH  Google Scholar 

  2. Benamou, J.-D., Brenier, Y.: A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numer. Math. 84(3), 375–393 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  3. Benamou, J.-D., Carlier, G.: Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations. J. Optim. Theory Appl. 167(1), 1–26 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  4. Benamou, J.-D., Carlier, G., Hatchi, R.: A numerical solution to Monge’s problem with a Finsler distance as cost. M2AN (2016)

  5. Briceño-Arias, L.M., Kalise, D., Silva, F.J.: Proximal methods for stationary mean field games with local couplings. arXiv:1608.07701 (2016)

  6. Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40, 120–145 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Evans, L., Gangbo, W.: Differential equations methods for the Monge-Kantorovich mass transfer problem. Mem. AMS. 653, 137 (1999)

    MATH  Google Scholar 

  8. Goldstein, T., Osher, S.: The split Bregman method for L1-regularized problems. SIAM J. Imaging Sci. 2(2), 323–343 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  9. Gudmundsson, J., Klein, O., Knauer, C., Small, M.: Manhattan networks and algorithmic applications for the earth movers distance. In EWCG (2007)

  10. He, B., Yuan, X.: Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective. SIAM J. Imaging Sci. 5(1), 119–149 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  11. Levina, E., Bickel, P.: The earth mover’s distance is the Mallows distance: some insights from statistics. In: Proceedings of the Eighth IEEE International Conference on Computer Vision, 2001. ICCV 2001, vol. 2, pp. 251–256 (2001)

  12. Ling, H., Okada, K.: An efficient earth Mover’s distance algorithm for robust histogram comparison. PAMI 29(5), 840–853 (2007)

    Article  Google Scholar 

  13. Métivier, L., Brossier, R., Mérigot, Q., Oudet, E., Virieux, J.: Measuring the misfit between seismograms using an optimal transport distance: application to full waveform inversion. Geophys. J. Int. 205(1), 345–377 (2016)

    Article  MATH  Google Scholar 

  14. Papadakis, N., Peyré, G., Oudet, E.: Optimal transport with proximal splitting. SIAM J. Imaging Sci. 7(1), 212–238 (2014). SIAM

  15. Pele, O., Werman, M.: Fast and robust earth mover’s distances. In: Proceedings of the 2009 IEEE 12th International Conference on Computer Vision, pp. 460–467 (2009)

  16. Pock, T., Chambolle, A.: Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In: Proceedings of the 2011 International Conference on Computer Vision, pp. 1762–1769. IEEE (2011)

  17. Rockafellar, R.T.: Conjugate duality and optimization. Soc. Ind. Appl, Math (1974)

    Book  MATH  Google Scholar 

  18. Rubner, Y., Tomasi, C., Guibas, L.: The earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vis. 40(2), 99–121 (2000)

    Article  MATH  Google Scholar 

  19. Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Phys. D Nonlinear Phenom. 60(1), 259–268 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  20. Ryu, E.K., Boyd, S.: Primer on monotone operator methods. Appl. Comput. Math. 15(1), 3–43 (2016)

    MathSciNet  MATH  Google Scholar 

  21. Santambrogio, F.: Absolute continuity and summability of transport densities: simpler proofs and new estimates. Calc. Var. Partial Differ. Equ. 36(3), 343–354 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  22. Solomon, J., Rustamov, R., Guibas, L., Butscher, A.: Earth mover’s distances on discrete surfaces. ACM Trans. Graph. (TOG) 33(4), 67 (2014)

    Article  Google Scholar 

  23. Villani, C.: Topics in Optimal Transportation, vol. 58. American Mathematical Soc, Providence (2003)

    MATH  Google Scholar 

  24. Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for \(\ell _1\)-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1(1), 143–168 (2008)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of California, Los Angeles, CA, USA

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

Authors
  1. Wuchen Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ernest K. Ryu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stanley Osher
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wotao Yin
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Wilfrid Gangbo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wuchen Li.

Additional information

This work is partially supported by ONR Grants N000141410683, N000141210838 and DOE Grant DE-SC00183838.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, W., Ryu, E.K., Osher, S. et al. A Parallel Method for Earth Mover’s Distance. J Sci Comput 75, 182–197 (2018). https://doi.org/10.1007/s10915-017-0529-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10915-017-0529-1

Keywords

Search

Navigation