Convolutional Wasserstein Distances: Efficient Optimal Transportation on Geometric Domains
Convolutional Wasserstein Distances: Efficient Optimal Transportation on Geometric Domains
复制标题
DOI：
10.1145/2766963
复制
发表时间：
2015-08-01
影响因子：
6.2
通讯作者：
Guibas, Leonidas
中科院分区：
文献类型：
--
作者：
Solomon, Justin;de Goes, Fernando;Guibas, Leonidas
本文介绍了一类新的算法，用于解决几何域上涉及最优运输的优化问题。我们的主要贡献是表明，最佳运输可以在图形中使用的大域，如图像和三角形网格，提高性能的数量级相比，以前的工作。为此，我们使用熵正则化近似最佳运输距离。由此产生的目标包含一个测地线的距离为基础的内核，可以近似与热内核。这种方法导致简单的迭代数值方案与线性收敛，其中每次迭代只需要高斯卷积或稀疏的，预分解的线性系统的解决方案。我们证明了我们的方法的多功能性和效率的任务，包括反射插值，颜色转移，和几何处理。
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.