Convolutional wasserstein distances

Justin Solomon (1) , Fernando de Goes (2) , Gabriel Peyré (3, 4) , Marco Cuturi (5) , Adrian Butscher (6) , Andy Nguyen (1) , Tao Du (1) , Leonidas Guibas (1)

1 Stanford University
2 Pixar Animation Studios
3 MOKAPLAN - Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales
4 CEREMADE - CEntre de REcherches en MAthématiques de la DEcision
5 Graduate School of Informatics [Kyoto]
6 Autodesk [Paris]

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 result- ing 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.

Mots clés: displacement interpolation; Optimal transportation; Wasserstein distances; entropy

Domaines: Traitement du signal et de l'image [eess.SP]; Synthèse d'image et réalité virtuelle [cs.GR]

Justin Solomon, Fernando de Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, et al.. Convolutional wasserstein distances. ACM Transactions on Graphics, 2015, 34 (4), pp.66:1-66:11. ⟨10.1145/2766963⟩. ⟨hal-01188953⟩