“Convolutional wasserstein distances: efficient optimal transportation on geometric domains”

  • ©Manish Mandad, David Cohen-Steiner, and Pierre Alliez




    Convolutional wasserstein distances: efficient optimal transportation on geometric domains


Session Title: Meshing Around



    This paper introduces a new class of algorithms for optimization problems involving optimal transportation over geometric domains. Our main contribution is to show that optimal transportation can be made tractable over large domains used in graphics, such as images and triangle meshes, improving performance by orders of magnitude compared to previous work. To this end, we approximate optimal transportation distances using entropic regularization. The resulting objective contains a geodesic distance-based kernel that can be approximated with the heat kernel. This approach leads to simple iterative numerical schemes with linear convergence, in which each iteration only requires Gaussian convolution or the solution of a sparse, pre-factored linear system. We demonstrate the versatility and efficiency of our method on tasks including reflectance interpolation, color transfer, and geometry processing.


    1. Agueh, M., and Carlier, G. 2011. Barycenters in the Wasserstein space. SIAM J. Math. Anal. 43, 2, 904–924.Google ScholarCross Ref
    2. Ashikhmin, M., and Shirley, P. 2000. An anisotropic Phong BRDF model. J. of Graph. Tools 5, 2, 25–32. Google ScholarDigital Library
    3. Aubry, M., Schlickewei, U., and Cremers, D. 2011. The wave kernel signature: A quantum mechanical approach to shape analysis. In Proc. ICCV Workshops, 1626–1633.Google Scholar
    4. Benamou, J.-D., and Brenier, Y. 2000. A computational fluid mechanics solution of the Monge-Kantorovich mass transfer problem. Numerische Mathematik 84, 3, 375–393.Google ScholarCross Ref
    5. Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L., and Peyré, G. 2015. Iterative Bregman projections for regularized transportation problems. SIAM J. Sci. Comp., to appear.Google Scholar
    6. Blinn, J. F. 1977. Models of light reflection for computer synthesized pictures. In Proc. SIGGRAPH, vol. 11, 192–198. Google ScholarDigital Library
    7. Bonneel, N., van de Panne, M., Paris, S., and Heidrich, W. 2011. Displacement interpolation using Lagrangian mass transport. ACM Trans. Graph. 30, 6 (Dec.), 158:1–158:12. Google ScholarDigital Library
    8. Bonneel, N., Rabin, J., Peyré, G., and Pfister, H. 2014. Sliced and Radon Wasserstein barycenters of measures. J. Math. Imaging and Vision, to appear. Google ScholarDigital Library
    9. Bregman, L. 1967. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comp. Math. and Math. Physics 7, 3, 200–217.Google ScholarCross Ref
    10. Burkard, R., and Çela, E. 1999. Linear assignment problems and extensions. Handbook of Combinatorial Optimization: Supplement 1, 75.Google ScholarCross Ref
    11. Burkard, R., Dell’Amico, M., and Martello, S. 2009. Assignment Problems. SIAM. Google ScholarDigital Library
    12. Carlier, G., Oberman, A., and Oudet, E. 2014. Numerical methods for matching for teams and Wasserstein barycenters. Preprint, Ceremade.Google Scholar
    13. Cover, T., and Thomas, J. 2006. Elements of Information Theory. Wiley. Google ScholarDigital Library
    14. Crane, K., Weischedel, C., and Wardetzky, M. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Trans. Graph. 32, 5 (Oct.), 152:1–152:11. Google ScholarDigital Library
    15. Cuturi, M., and Doucet, A. 2014. Fast computation of Wasserstein barycenters. In Proc. ICML, vol. 32.Google Scholar
    16. Cuturi, M. 2013. Sinkhorn distances: Lightspeed computation of optimal transportation. In Proc. NIPS, vol. 26. 2292–2300.Google Scholar
    17. Davis, T. A. 2006. Direct Methods for Sparse Linear Systems. SIAM. Google ScholarDigital Library
    18. de Goes, F., Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2011. An optimal transport approach to robust reconstruction and simplification of 2d shapes. In Computer Graph. Forum, vol. 30, 1593–1602.Google ScholarCross Ref
    19. de Goes, F., Breeden, K., Ostromoukhov, V., and Desbrun, M. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6 (Nov.), 171:1–171:11. Google ScholarDigital Library
    20. de Goes, F., Memari, P., Mullen, P., and Desbrun, M. 2014. Weighted triangulations for geometry processing. ACM Trans. Graph. 33, 3. Google ScholarDigital Library
    21. Delon, J. 2006. Movie and video scale-time equalization application to flicker reduction. IEEE Trans. on Image Proc. 15, 1, 241–248. Google ScholarDigital Library
    22. Deming, W. E., and Stephan, F. F. 1940. On a least squares adjustment of a sampled frequency table when the expected marginal totals are known. Annals Math. Stat. 11, 4, 427–444.Google ScholarCross Ref
    23. Deriche, R. 1993. Recursively implementing the Gaussian and its derivatives. Tech. Rep. RR-1893.Google Scholar
    24. Desbrun, M., Meyer, M., Schröder, P., and Barr, A. H. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In Proc. SIGGRAPH, 317–324. Google ScholarDigital Library
    25. Escalante, R., and Raydan, M. 2011. Alternating Projection Methods. Fundamentals of Algorithms. SIAM. Google ScholarDigital Library
    26. Ferradans, S., Papadakis, N., Peyré, G., and Aujol, J.-F. 2014. Regularized discrete optimal transport. SIAM J. Imaging Sci. 7, 3, 1853–1882.Google ScholarCross Ref
    27. Franklin, J., and Lorenz, J. 1989. On the scaling of multidimensional matrices. Linear Algebra and its Applications 114, 717–735.Google Scholar
    28. Johnson, D. B. 1977. Efficient algorithms for shortest paths in sparse networks. J. ACM 24, 1 (Jan.), 1–13. Google ScholarDigital Library
    29. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3 (July), 561–566. Google ScholarDigital Library
    30. Kantorovich, L. 1942. On the transfer of masses (in Russian). Doklady Akademii Nauk 37, 2, 227–229.Google Scholar
    31. Kim, Y.-H., and Pass, B. 2013. Multi-marginal optimal transport on Riemannian manifolds. arXiv:1303.6251.Google Scholar
    32. Knight, P. 2008. The Sinkhorn–Knopp algorithm: Convergence and applications. SIAM J. on Matrix Anal. and Applications 30, 1, 261–275. Google ScholarDigital Library
    33. Léonard, C. 2012. From the Schrödinger problem to the Monge-Kantorovich problem. J. Funct. Anal. 262, 4, 1879–1920.Google ScholarCross Ref
    34. Lipman, Y., and Daubechies, I. 2011. Conformal Wasserstein distances: Comparing surfaces in polynomial time. Adv. Math. 227, 3, 1047–1077.Google ScholarCross Ref
    35. MacNeal, R. 1949. The Solution of Partial Differential Equations by means of Electrical Networks. PhD thesis, Caltech.Google Scholar
    36. Malliavin, P., and Stroock, D. W. 1996. Short time behavior of the heat kernel and its logarithmic derivatives. J. Differential Geom. 44, 3, 550–570.Google ScholarCross Ref
    37. McCann, R. J. 1997. A convexity principle for interacting gases. Adv. Math. 128, 1, 153–179.Google ScholarCross Ref
    38. Mérigot, Q. 2011. A multiscale approach to optimal transport. Comp. Graph. Forum 30, 5, 1583–1592.Google ScholarCross Ref
    39. Mosek ApS, 2014. Mosek version 7. https://mosek.com.Google Scholar
    40. Papadakis, N., Provenzi, E., and Caselles, V. 2011. A variational model for histogram transfer of color images. IEEE Trans. Image Proc. 20, 6, 1682–1695. Google ScholarDigital Library
    41. Pharr, M., and Humphreys, G. 2010. Physically Based Rendering, Second Edition: From Theory To Implementation. Morgan Kaufmann, July. Google ScholarDigital Library
    42. Pitié, F., Kokaram, A. C., and Dahyot, R. 2007. Automated colour grading using colour distribution transfer. Comp. Vision and Image Understanding 107 (July), 123–137. Google ScholarDigital Library
    43. Rubner, Y., Tomasi, C., and Guibas, L. J. 2000. The earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vision 40, 2 (Nov.), 99–121. Google ScholarDigital Library
    44. Schwartzburg, Y., Testuz, R., Tagliasacchi, A., and Pauly, M. 2014. High-contrast computational caustic design. ACM Trans. Graph. 33, 4 (July), 74:1–74:11. Google ScholarDigital Library
    45. Sinkhorn, R. 1964. A relationship between arbitrary positive matrices and doubly stochastic matrices. Annals of Math. Stat. 35, 2, 876–879.Google ScholarCross Ref
    46. Sinkhorn, R. 1967. Diagonal equivalence to matrices with prescribed row and column sums. American Math. Monthly 74, 4, 402–405.Google ScholarCross Ref
    47. Solomon, J., Nguyen, A., Butscher, A., Ben-Chen, M., and Guibas, L. 2012. Soft maps between surfaces. Comp. Graph. Forum 31, 5 (Aug.), 1617–1626. Google ScholarDigital Library
    48. Solomon, J., Guibas, L., and Butscher, A. 2013. Dirichlet energy for analysis and synthesis of soft maps. Comp. Graph. Forum 32, 5, 197–206.Google ScholarDigital Library
    49. Solomon, J., Rustamov, R., Guibas, L., and Butscher, A. 2014. Earth mover’s distances on discrete surfaces. ACM Trans. Graph. 33, 4 (July), 67:1–67:12. Google ScholarDigital Library
    50. Solomon, J., Rustamov, R., Leonidas, G., and Butscher, A. 2014. Wasserstein propagation for semi-supervised learning. In Proc. ICML, 306–314.Google Scholar
    51. Varadhan, S. R. S. 1967. On the behavior of the fundamental solution of the heat equation with variable coefficients. Comm. on Pure and Applied Math. 20, 2, 431–455.Google ScholarCross Ref
    52. Villani, C. 2003. Topics in Optimal Transportation. Graduate Studies in Mathematics. AMS.Google Scholar
    53. Zhao, X., Su, Z., Gu, X. D., Kaufman, A., Sun, J., Gao, J., and Luo, F. 2013. Area-preservation mapping using optimal mass transport. IEEE Trans. Vis. and Comp. Graphics 19, 12. Google ScholarDigital Library
    54. Zhu, J.-Y., Lee, Y. J., and Efros, A. A. 2014. AverageExplorer: Interactive exploration and alignment of visual data collections. ACM Trans. Graph. 33, 4 (July), 160:1–160:11. Google ScholarDigital Library

ACM Digital Library Publication: