“Wasserstein barycentric coordinates: histogram regression using optimal transport”

  • ©Nicolas Bonneel, Gabriel Peyré, and Marco Cuturi




    Wasserstein barycentric coordinates: histogram regression using optimal transport

Session/Category Title: CORRESPONDENCE & MAPPING




    This article defines a new way to perform intuitive and geometrically faithful regressions on histogram-valued data. It leverages the theory of optimal transport, and in particular the definition of Wasserstein barycenters, to introduce for the first time the notion of barycentric coordinates for histograms. These coordinates take into account the underlying geometry of the ground space on which the histograms are defined, and are thus particularly meaningful for applications in graphics to shapes, color or material modification. Beside this abstract construction, we propose a fast numerical optimization scheme to solve this backward problem (finding the barycentric coordinates of a given histogram) with a low computational overhead with respect to the forward problem (computing the barycenter). This scheme relies on a backward algorithmic differentiation of the Sinkhorn algorithm which is used to optimize the entropic regularization of Wasserstein barycenters. We showcase an illustrative set of applications of these Wasserstein coordinates to various problems in computer graphics: shape approximation, BRDF acquisition and color editing.


    1. Agueh, M., and Carlier, G. 2011. Barycenters in the Wasserstein space. SIAM J. on Mathematical Analysis 43, 2.Google ScholarCross Ref
    2. Benamou, J.-D., and Brenier, Y. 2000. A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numerische Mathematik 84, 3, 375–393.Google ScholarCross Ref
    3. Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, M., and Peyré, G. 2015. Iterative Bregman projections for regularized transportation problems. SIAM J. on Sci. Computing 2, 37.Google Scholar
    4. Bigot, J., and Klein, T. 2012. Consistent estimation of a population barycenter in the Wasserstein space. Preprint arXiv:1212.2562.Google Scholar
    5. Bigot, J., Gouet, R., Klein, T., and López, A. 2015. Geodesic PCA in the Wasserstein space by Convex PCA. Annales de l’Institut Henri Poincaré B: Probability and Statistics.Google Scholar
    6. Bonneel, N., van de Panne, M., Paris, S., and Heidrich, W. 2011. Displacement interpolation using lagrangian mass transport. ACM Trans. Graph. (SIGGRAPH Asia) 30, 6. Google ScholarDigital Library
    7. Bonneel, N., Sunkavalli, K., Paris, S., and Pfister, H. 2013. Example-Based Video Color Grading. ACM Trans. Graph. (SIGGRAPH) 32, 4. Google ScholarDigital Library
    8. Bonneel, N., Rabin, J., Peyré, G., and Pfister, H. 2015. Sliced and Radon Wasserstein barycenters of measures. J. of Mathematical Imaging and Vision 51, 1. Google ScholarDigital Library
    9. Brand, M., and Brand, M. 2003. Charting a manifold. In Adv. in Neural Information Proc. Sys. Google ScholarDigital Library
    10. Bregman, L. M. 1967. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics 7, 3, 200–217.Google Scholar
    11. Burkard, R., Dell’Amico, M., and Martello, S. 2009. Assignment Problems. Society for Industrial and App. Math. Google ScholarDigital Library
    12. Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Trans. Graph. (SIGGRAPH) 28, 3. Google ScholarDigital Library
    13. Cuturi, M., and Doucet, A. 2014. Fast computation of Wasserstein barycenters. In Int. Conf. on Machine Learning (ICML).Google Scholar
    14. Cuturi, M. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Adv. in Neural Information Proc. Sys.Google Scholar
    15. 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 Mathematical Statistics 11, 4.Google ScholarCross Ref
    16. Filip, J., and Vávra, R. 2014. Template-based sampling of anisotropic BRDFs. Computer Graphics Forum (PG) 33, 7. Google ScholarDigital Library
    17. Haker, S., Zhu, L., Tannenbaum, A., and Angenent, S. Optimal mass transport for registration and warping. International Journal of Computer Vision 60, 3. Google ScholarDigital Library
    18. Kantorovich, L. 1942. On the transfer of masses (in russian). Doklady Akademii Nauk 37, 2, 227–229.Google Scholar
    19. Lewis, A. S., and Overton, M. L. 2013. Nonsmooth optimization via quasi-newton methods. Math. Programming 141.Google Scholar
    20. Matusik, W., Pfister, H., Brand, M., and McMillan, L. 2003. A data-driven reflectance model. ACM Trans. Graph. (SIGGRAPH) 22, 3. Google ScholarDigital Library
    21. Mérigot, Q. 2011. A multiscale approach to optimal transport. Computer Graphics Forum (SGP) 30, 5.Google Scholar
    22. Monge, G. 1781. Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences, 666–704.Google Scholar
    23. Neidinger, R. D. 2010. Introduction to automatic differentiation and MATLAB object-oriented programming. SIAM Rev. 52, 3. Google ScholarDigital Library
    24. Pitié, F., Kokaram, A., and Dahyot, R. 2007. Automated colour grading using colour distribution transfer. Computer Vision and Image Understanding. Google ScholarDigital Library
    25. Rabin, J., and Papadakis, N. 2015. Convex color image segmentation with optimal transport distances. In Proc. SSVM’15.Google Scholar
    26. Rabin, J., Delon, J., and Gousseau, Y. 2010. Regularization of transportation maps for color and contrast transfer. In IEEE International Conference on Image Processing (ICIP).Google Scholar
    27. Rabin, J., Peyré, G., Delon, J., and Bernot, M. 2012. Wasserstein barycenter and its application to texture mixing. In Scale Space and Variational Methods in Computer Vision. Google ScholarDigital Library
    28. Reinhard, E., Ashikhmin, M., Gooch, B., and Shirley, P. 2001. Color transfer between images. IEEE Comput. Graph. Appl. 21, 5. Google ScholarDigital Library
    29. Rolet, A., Cuturi, M., and Peyré, G. 2016. Fast dictionary learning with a smoothed Wasserstein loss. In Proc. AISTATS’16.Google Scholar
    30. Rubner, Y., Tomasi, C., and Guibas, L. 1998. A metric for distributions with applications to image databases. In Computer Vision, 1998. Sixth International Conference on, 59–66. Google ScholarDigital Library
    31. Rubner, Y., Tomasi, C., and Guibas, M. J. 2000. The earth mover’s distance as a metric for image retrieval. International J. of Computer Vision 40, 2000. Google ScholarDigital Library
    32. Rustamov, R. M. 2010. Barycentric coordinates on surfaces. Computer Graphics Forum 5, 29.Google Scholar
    33. Sandler, R., and Lindenbaum, M. 2009. Nonnegative matrix factorization with earth mover’s distance metric. In IEEE Computer Vision and Pattern Recognition (CVPR).Google Scholar
    34. Schmidt, M. W., van den Berg, E., Friedlander, M. P., and Murphy, K. P. 2009. Optimizing costly functions with simple constraints: A limited-memory projected quasi-newton algorithm. In International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 5.Google Scholar
    35. Seguy, V., and Cuturi, M. 2015. Principal geodesic analysis for probability measures under the optimal transport metric. In Adv. in Neural Information Proc. Sys. Google ScholarDigital Library
    36. Sinkhorn, R. 1964. A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Statist. 35.Google Scholar
    37. Solomon, J., Rustamov, R., Guibas, L., and Butscher, A. 2014. Earth mover’s distances on discrete surfaces. ACM Trans. Graph. (SIGGRAPH) 33, 4. Google ScholarDigital Library
    38. Solomon, J., Rustamov, R., Guibas, L., and Butscher, A. 2014. Wasserstein propagation for semi-supervised learning. In Int. Conf. on Machine Learning (ICML).Google Scholar
    39. Solomon, J., de Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyen, A., Du, T., and Guibas, L. 2015. Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. ACM Trans. Graph. (SIGGRAPH) 34, 4. Google ScholarDigital Library
    40. Srivastava, S., Cevher, V., Tran-Dinh, Q., and Dunson, D. B. 2015. Wasp: Scalable bayes via barycenters of subset posteriors. In International Conference on Artificial Intelligence and Statistics.Google Scholar
    41. Villani, C. 2003. Topics in optimal transportation. American Mathematical Soc.Google Scholar
    42. Villani, C. 2008. Optimal transport: old and new, vol. 338.Google Scholar
    43. Wills, J., Agarwal, S., Kriegman, D., and Belongie, S. 2009. Toward a perceptual space for gloss. ACM Trans. Graph. 28, 4. Google ScholarDigital Library

ACM Digital Library Publication: