“Instant transport maps on 2D grids”
Conference:
Type(s):
Title:
- Instant transport maps on 2D grids
Session/Category Title: Mapping + transport
Presenter(s)/Author(s):
Moderator(s):
Abstract:
In this paper, we introduce a novel and extremely fast algorithm to compute continuous transport maps between 2D probability densities discretized on uniform grids. The core of our method is a novel iterative solver computing the L2 optimal transport map from a grid to the uniform density in the 2D Euclidean plane. A transport map between arbitrary densities is then recovered through numerical inversion and composition. In this case, the resulting map is only approximately optimal, but it is continuous and density preserving. Our solver is derivative-free, and it converges in a few cheap iterations. We demonstrate interactive performance in various applications such as adaptive sampling, feature sensitive remeshing, and caustic design.
References:
1. F. Aurenhammer, F. Hoffmann, and B. Aronov. 1998. Minkowski-Type Theorems and Least-Squares Clustering. Algorithmica 20, 1 (1998), 61–76.Google ScholarCross Ref
2. J.-D. Benamou, Y. Brenier, and K. Guittet. 2002. The Monge-Kantorovitch mass transfer and its computational fluid mechanics formulation. International Journal for Numerical Methods in Fluids 40, 1–2 (2002), 21–30.Google ScholarCross Ref
3. Jean-David Benamou, Brittany D. Froese, and Adam M. Oberman. 2014. Numerical Solution of the Optimal Transportation Problem Using the Monge-Ampère Equation. J. Comput. Phys. 260 (2014), 107–126. Google ScholarDigital Library
4. Nicolas Bonneel, Michiel van de Panne, Sylvain Paris, and Wolfgang Heidrich. 2011. Displacement interpolation using Lagrangian mass transport. ACM Transactions on Graphics 30, 6 (2011), 1. Google ScholarDigital Library
5. Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Levy. 2010. Polygon Mesh Processing.Google Scholar
6. Yann Brenier. 1991. Polar factorization and monotone rearrangement of vector-valued functions. Comm. Pure Appl. Math. 44, 4 (1991), 375–417.Google ScholarCross Ref
7. C. G. Broyden. 1965. A Class of Methods for Solving Nonlinear Simultaneous Equations. Math. Comp. (1965).Google Scholar
8. Marco Cuturi. 2013. Sinkhorn Distances: Lightspeed Computation of Optimal Transport. In NIPS, Vol. 26. 2292–2300. Google ScholarDigital Library
9. Fernando de Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue Noise Through Optimal Transport. ACM Transactions on Graphics 31, 6 (2012). Google ScholarDigital Library
10. G.L. Delzanno, L. Chacón, J.M. Finn, Y. Chung, and G. Lapenta. 2008. An optimal robust equidistribution method for two-dimensional grid adaptation based on Monge-Kantorovich optimization. J. Comput. Phys. 227, 23 (2008), 9841 — 9864. Google ScholarDigital Library
11. Fernando de Goes, Pooran Memari, Patrick Mullen, and Mathieu Desbrun. 2014. Weighted Triangulations for Geometry Processing. ACM Transactions on Graphics 33, 3, Article 28 (2014), 13 pages. Google ScholarDigital Library
12. Xianfeng Gu, Feng Luo, Jian Sun, and Shing Tung Yau. 2016. Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Ampere equations. Asian Journal of Mathematics 20, 2 (2016), 383–398.Google ScholarCross Ref
13. W. W. Hager and H. Zhang. 2006. A survey of nonlinear conjugate gradient methods. Pacific journal of Optimization 2, 1 (2006), 35–58.Google Scholar
14. Steven Haker, Lei Zhu, Allen Tannenbaum, and Sigurd Angenent. 2004. Optimal Mass Transport for Registration and Warping. International Journal of Computer Vision 60, 3 (2004), 225–240. Google ScholarDigital Library
15. A.S. Householder. 1953. Principles of Numerical Analysis. McGraw-Hill. 135–138 pages.Google Scholar
16. L. Kantorovich. 1942. On the transfer of masses (in Russian). Doklady Akademii Nauk 37, 2 (1942), 227–229.Google Scholar
17. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Transactions on Graphics 35, 4 (2016), 134:1–134:11. Google ScholarDigital Library
18. Thibaud Lambert, Pierre Bénard, and Gael Guennebaud. 2016. Multi-Resolution Meshes for Feature-Aware Hardware Tessellation. Computer Graphics Forum (2016).Google Scholar
19. Bruno Lévy. 2015. A Numerical Algorithm for L2 Semi-Discrete Optimal Transport in 3D. ESAIM: Mathematical Modelling and Numerical Analysis 49, 6 (2015), 1693–1715.Google ScholarCross Ref
20. Bruno Lévy. 2017. Geogram. (2017). http://alice.loria.fr/software/geogramGoogle Scholar
21. Bruno Lévy and Erica L. Schwindt. 2018. Notions of optimal transport theory and how to implement them on a computer. Computers & Graphics 72 (2018), 135 — 148.Google ScholarCross Ref
22. Ruipeng Li. 2017. On Parallel Solution of Sparse Triangular Linear Systems in CUDA. CoRR (2017).Google Scholar
23. Manish Mandad, David Cohen-Steiner, Leif Kobbelt, Pierre Alliez, and Mathieu Desbrun. 2017. Variance-Minimizing Transport Plans for Inter-surface Mapping. ACM Transactions on Graphics 36 (2017), 14. Google ScholarDigital Library
24. Quentin Mérigot. 2011. A Multiscale Approach to Optimal Transport. Computer Graphics Forum 30, 5 (2011), 1583–1592.Google ScholarCross Ref
25. Ján Morovic and Pei-Li Sun. 2003. Accurate 3D Image Colour Histogram Transformation. Pattern Recogn. Lett. 24, 11 (2003), 1725–1735. Google ScholarDigital Library
26. Vincent Nivoliers, Bruno Lévy, and Christophe Geuzaine. 2015. Anisotropic and feature sensitive triangular remeshing using normal lifting. J. Comput. Appl. Math. 289 (2015). Google ScholarDigital Library
27. J. Nocedal and S. Wright. 2006. Numerical Optimization. Springer New York.Google Scholar
28. Nicolas Papadakis, Gabriel Peyré, and Edouard Oudet. 2014. Optimal Transport with Proximal Splitting. SIAM Journal on Imaging Sciences 7, 1 (2014), 212–238.Google ScholarCross Ref
29. Hélène Perrier, David Coeurjolly, Feng Xie, Matt Pharr, Pat Hanrahan, and Victor Ostromoukhov. 2018. Sequences with Low-Discrepancy Blue-Noise 2-D Projections. Computer Graphics Forum 37 (2018).Google Scholar
30. Gabriel Peyré and Marco Cuturi. 2018. Computational Optimal Transport. (2018). arXiv:arXiv:1803.00567Google Scholar
31. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically Based Rendering: From Theory to Implementation (3rd ed.). Morgan Kaufmann Publishers Inc. Google ScholarDigital Library
32. Hongxing Qin, Yi Chen, Jinlong He, and Baoquan Chen. 2017. Wasserstein Blue Noise Sampling. ACM Transactions on Graphics 36, 5 (2017). Google ScholarDigital Library
33. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Transactions on Graphics 36, 2 (2017), 16:1–16:16. Google ScholarDigital Library
34. Yuliy Schwartzburg, Romain Testuz, Andrea Tagliasacchi, and Mark Pauly. 2014. High-contrast Computational Caustic Design. ACM Transactions on Graphics 33, 4 (2014), 74:1–74:11. Google ScholarDigital Library
35. Justin Solomon. 2018. Optimal Transport on Discrete Domains. (2018). arXiv:arXiv:1801.07745Google Scholar
36. Justin Solomon, Fernando de Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. 2015. Convolutional Wasserstein Distances: Efficient Optimal Transportation on Geometric Domains. ACM Transactions on Graphics 34, 4 (2015), 66:1–66:11. Google ScholarDigital Library
37. C. Villani. 2008. Optimal Transport: Old and New. Springer Berlin Heidelberg.Google Scholar
38. Shi-Qing Xin, Bruno Lévy, Zhonggui Chen, Lei Chu, Yaohui Yu, Changhe Tu, and Wenping Wang. 2016. Centroidal Power Diagrams with Capacity Constraints: Computation, Applications, and Extension. ACM Transactions on Graphics 35, 6 (2016), 244:1–244:12. Google ScholarDigital Library
39. Xin Zhao, Zhengyu Su, X Gu, Arie Kaufman, Jian Sun, Jie Gao, and Feng Luo. 2013. Area-Preservation Mapping using Optimal Mass Transport. Visualization and Computer Graphics, IEEE Transactions on 19, 12 (2013), 2838–2847. Google ScholarDigital Library
