Justin Solomon
Fernando de Goes
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
Available for Download
zip
a66-solomon.zip (4.3 MB)
Supplemental files
- Agueh, M., and Carlier, G. 2011. Barycenters in the Wasserstein space. SIAM J. Math. Anal. 43, 2, 904--924.Google Scholar
Cross Ref
- Ashikhmin, M., and Shirley, P. 2000. An anisotropic Phong BRDF model. J. of Graph. Tools 5, 2, 25--32. Google ScholarDigital Library
- 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
- 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
- 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
- Blinn, J. F. 1977. Models of light reflection for computer synthesized pictures. In Proc. SIGGRAPH, vol. 11, 192--198. Google ScholarDigital Library
- 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
- 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
- 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
- Burkard, R., and Çela, E. 1999. Linear assignment problems and extensions. Handbook of Combinatorial Optimization: Supplement 1, 75.Google ScholarCross Ref
- Burkard, R., Dell'Amico, M., and Martello, S. 2009. Assignment Problems. SIAM. Google ScholarDigital Library
- Carlier, G., Oberman, A., and Oudet, E. 2014. Numerical methods for matching for teams and Wasserstein barycenters. Preprint, Ceremade.Google Scholar
- Cover, T., and Thomas, J. 2006. Elements of Information Theory. Wiley. Google ScholarDigital Library
- 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
- Cuturi, M., and Doucet, A. 2014. Fast computation of Wasserstein barycenters. In Proc. ICML, vol. 32.Google Scholar
- Cuturi, M. 2013. Sinkhorn distances: Lightspeed computation of optimal transportation. In Proc. NIPS, vol. 26. 2292--2300.Google Scholar
- Davis, T. A. 2006. Direct Methods for Sparse Linear Systems. SIAM. Google ScholarDigital Library
- 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
- 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
- de Goes, F., Memari, P., Mullen, P., and Desbrun, M. 2014. Weighted triangulations for geometry processing. ACM Trans. Graph. 33, 3. Google ScholarDigital Library
- 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
- 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
- Deriche, R. 1993. Recursively implementing the Gaussian and its derivatives. Tech. Rep. RR-1893.Google Scholar
- 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
- Escalante, R., and Raydan, M. 2011. Alternating Projection Methods. Fundamentals of Algorithms. SIAM. Google ScholarDigital Library
- 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
- Franklin, J., and Lorenz, J. 1989. On the scaling of multidimensional matrices. Linear Algebra and its Applications 114, 717--735.Google Scholar
- Johnson, D. B. 1977. Efficient algorithms for shortest paths in sparse networks. J. ACM 24, 1 (Jan.), 1--13. Google ScholarDigital Library
- 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
- Kantorovich, L. 1942. On the transfer of masses (in Russian). Doklady Akademii Nauk 37, 2, 227--229.Google Scholar
- Kim, Y.-H., and Pass, B. 2013. Multi-marginal optimal transport on Riemannian manifolds. arXiv:1303.6251.Google Scholar
- Knight, P. 2008. The Sinkhorn--Knopp algorithm: Convergence and applications. SIAM J. on Matrix Anal. and Applications 30, 1, 261--275. Google ScholarDigital Library
- Léonard, C. 2012. From the Schrödinger problem to the Monge-Kantorovich problem. J. Funct. Anal. 262, 4, 1879--1920.Google ScholarCross Ref
- Lipman, Y., and Daubechies, I. 2011. Conformal Wasserstein distances: Comparing surfaces in polynomial time. Adv. Math. 227, 3, 1047--1077.Google ScholarCross Ref
- MacNeal, R. 1949. The Solution of Partial Differential Equations by means of Electrical Networks. PhD thesis, Caltech.Google Scholar
- 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
- McCann, R. J. 1997. A convexity principle for interacting gases. Adv. Math. 128, 1, 153--179.Google ScholarCross Ref
- Mérigot, Q. 2011. A multiscale approach to optimal transport. Comp. Graph. Forum 30, 5, 1583--1592.Google ScholarCross Ref
- Mosek ApS, 2014. Mosek version 7. https://mosek.com.Google Scholar
- 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
- Pharr, M., and Humphreys, G. 2010. Physically Based Rendering, Second Edition: From Theory To Implementation. Morgan Kaufmann, July. Google ScholarDigital Library
- 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
- 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
- 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
- Sinkhorn, R. 1964. A relationship between arbitrary positive matrices and doubly stochastic matrices. Annals of Math. Stat. 35, 2, 876--879.Google ScholarCross Ref
- Sinkhorn, R. 1967. Diagonal equivalence to matrices with prescribed row and column sums. American Math. Monthly 74, 4, 402--405.Google ScholarCross Ref
- 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
- 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
- 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
- Solomon, J., Rustamov, R., Leonidas, G., and Butscher, A. 2014. Wasserstein propagation for semi-supervised learning. In Proc. ICML, 306--314.Google Scholar
- 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
- Villani, C. 2003. Topics in Optimal Transportation. Graduate Studies in Mathematics. AMS.Google Scholar
- 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
- 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
Index Terms
- Convolutional wasserstein distances: efficient optimal transportation on geometric domains
Recommendations
Earth mover's distances on discrete surfaces
We introduce a novel method for computing the earth mover's distance (EMD) between probability distributions on a discrete surface. Rather than using a large linear program with a quadratic number of variables, we apply the theory of optimal ...
Variational Wasserstein Clustering
Computer Vision – ECCV 2018AbstractWe propose a new clustering method based on optimal transportation. We discuss the connection between optimal transportation and k-means clustering, solve optimal transportation with the variational principle, and investigate the use of power ...
Generalized sliced wasserstein distances
NIPS'19: Proceedings of the 33rd International Conference on Neural Information Processing SystemsThe Wasserstein distance and its variations, e.g., the sliced-Wasserstein (SW) distance, have recently drawn attention from the machine learning community. The SW distance, specifically, was shown to have similar properties to the Wasserstein distance, ...
Comments