“Convolutional wasserstein distances: efficient optimal transportation on geometric domains”
Conference:
Type(s):
Title:
- Convolutional wasserstein distances: efficient optimal transportation on geometric domains
Session/Category Title: Meshing Around
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
