“Wasserstein barycentric coordinates: histogram regression using optimal transport”
Conference:
Type:
Title:
- Wasserstein barycentric coordinates: histogram regression using optimal transport
Session/Category Title: CORRESPONDENCE & MAPPING
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
