Nicolas Bonneel
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.
Supplemental Material
Available for Download
Supplemental files.
- Agueh, M., and Carlier, G. 2011. Barycenters in the Wasserstein space. SIAM J. on Mathematical Analysis 43, 2.Google Scholar
Cross Ref
- 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
- 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
- Bigot, J., and Klein, T. 2012. Consistent estimation of a population barycenter in the Wasserstein space. Preprint arXiv:1212.2562.Google Scholar
- 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
- 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
- Bonneel, N., Sunkavalli, K., Paris, S., and Pfister, H. 2013. Example-Based Video Color Grading. ACM Trans. Graph. (SIGGRAPH) 32, 4. Google ScholarDigital Library
- 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
- Brand, M., and Brand, M. 2003. Charting a manifold. In Adv. in Neural Information Proc. Sys. Google ScholarDigital Library
- 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
- Burkard, R., Dell'Amico, M., and Martello, S. 2009. Assignment Problems. Society for Industrial and App. Math. Google ScholarDigital Library
- Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Trans. Graph. (SIGGRAPH) 28, 3. Google ScholarDigital Library
- Cuturi, M., and Doucet, A. 2014. Fast computation of Wasserstein barycenters. In Int. Conf. on Machine Learning (ICML).Google Scholar
- Cuturi, M. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Adv. in Neural Information Proc. Sys.Google Scholar
- 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
- Filip, J., and Vávra, R. 2014. Template-based sampling of anisotropic BRDFs. Computer Graphics Forum (PG) 33, 7. Google ScholarDigital Library
- 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
- Kantorovich, L. 1942. On the transfer of masses (in russian). Doklady Akademii Nauk 37, 2, 227--229.Google Scholar
- Lewis, A. S., and Overton, M. L. 2013. Nonsmooth optimization via quasi-newton methods. Math. Programming 141.Google Scholar
- Matusik, W., Pfister, H., Brand, M., and McMillan, L. 2003. A data-driven reflectance model. ACM Trans. Graph. (SIGGRAPH) 22, 3. Google ScholarDigital Library
- Mérigot, Q. 2011. A multiscale approach to optimal transport. Computer Graphics Forum (SGP) 30, 5.Google Scholar
- 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
- Neidinger, R. D. 2010. Introduction to automatic differentiation and MATLAB object-oriented programming. SIAM Rev. 52, 3. Google ScholarDigital Library
- Pitié, F., Kokaram, A., and Dahyot, R. 2007. Automated colour grading using colour distribution transfer. Computer Vision and Image Understanding. Google ScholarDigital Library
- Rabin, J., and Papadakis, N. 2015. Convex color image segmentation with optimal transport distances. In Proc. SSVM'15.Google Scholar
- 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
- 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
- Reinhard, E., Ashikhmin, M., Gooch, B., and Shirley, P. 2001. Color transfer between images. IEEE Comput. Graph. Appl. 21, 5. Google ScholarDigital Library
- Rolet, A., Cuturi, M., and Peyré, G. 2016. Fast dictionary learning with a smoothed Wasserstein loss. In Proc. AISTATS'16.Google Scholar
- 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
- 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
- Rustamov, R. M. 2010. Barycentric coordinates on surfaces. Computer Graphics Forum 5, 29.Google Scholar
- 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
- 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
- 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
- Sinkhorn, R. 1964. A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Statist. 35.Google Scholar
- 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
- 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
- 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
- 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
- Villani, C. 2003. Topics in optimal transportation. American Mathematical Soc.Google Scholar
- Villani, C. 2008. Optimal transport: old and new, vol. 338.Google Scholar
- Wills, J., Agarwal, S., Kriegman, D., and Belongie, S. 2009. Toward a perceptual space for gloss. ACM Trans. Graph. 28, 4. Google ScholarDigital Library
Index Terms
- Wasserstein barycentric coordinates: histogram regression using optimal transport
Recommendations
The Ultrametric Gromov–Wasserstein Distance
AbstractWe investigate compact ultrametric measure spaces which form a subset of the collection of all metric measure spaces . In analogy with the notion of the ultrametric Gromov–Hausdorff distance on the collection of ultrametric spaces , we ...
Spherical barycentric coordinates
SGP '06: Proceedings of the fourth Eurographics symposium on Geometry processingWe develop spherical barycentric coordinates. Analogous to classical, planar barycentric coordinates that describe the positions of points in a plane with respect to the vertices of a given planar polygon, spherical barycentric coordinates describe the ...
Interior distance using barycentric coordinates
SGP '09: Proceedings of the Symposium on Geometry ProcessingThis paper introduces a framework for defining a shape-aware distance measure between any two points in the interior of a surface mesh. Our framework is based on embedding the surface mesh into a high-dimensional space in a way that best preserves ...
Comments