“Sliced optimal transport sampling” by Paulin, Bonneel, Coeurjolly, Iehl, Webanck, et al. …
Conference:
Type:
Title:
- Sliced optimal transport sampling
Session/Category Title: Monte Carlo and Perception
Presenter(s)/Author(s):
Abstract:
In this paper, we introduce a numerical technique to generate sample distributions in arbitrary dimension for improved accuracy of Monte Carlo integration. We point out that optimal transport offers theoretical bounds on Monte Carlo integration error, and that the recently-introduced numerical framework of sliced optimal transport (SOT) allows us to formulate a novel and efficient approach to generating well-distributed high-dimensional pointsets. The resulting sliced optimal transport sampling, solely involving repeated 1D solves, is particularly simple and efficient for the common case of a uniform density over a d-dimensional ball. We also construct a volume-preserving map from a d-ball to a d-cube (generalizing the Shirley-Chiu mapping to arbitrary dimensions) to offer fast SOT sampling over d-cubes. We provide ample numerical evidence of the improvement in Monte Carlo integration accuracy that SOT sampling brings compared to existing QMC techniques, and derive a projective variant for rendering which rivals, and at times outperforms, current sampling strategies using low-discrepancy sequences or optimized samples.
References:
1. Franz Aurenhammer, Friedrich Hoffmann, and Boris Aronov. 1998. Minkowski-type theorems and least-squares clustering. Algorithmica 20, 1 (1998), 61–76.Google ScholarCross Ref
2. Martin Bálint and Rafał K. Mantiuk. 2019. Closed Form Transmittance in Heterogeneous Media Using Cosine Noise. In Central European Seminar on Computer Graphics. https://www.cl.cam.ac.uk/~rkm38/pdfs/balint2019cosine_noise.pdfGoogle Scholar
3. Michael Balzer, Thomas Schlömer, and Oliver Deussen. 2009. Capacity-Constrained Point Distributions: A Variant of Lloyd’s Method. ACM Trans. Graph. 28, 3 (2009), 86:1–8.Google ScholarDigital Library
4. Nicolas Bonneel and David Coeurjolly. 2019. SPOT: Sliced Partial Optimal Transport. ACM Trans. Graph. 38, 4 (July 2019).Google ScholarDigital Library
5. Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. 2015. Sliced and Radon Wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision 51, 1 (2015).Google ScholarDigital Library
6. Nicolas Bonnotte. 2013. Unidimensional and evolution methods for optimal transportation. Ph.D. Dissertation. Paris 11.Google Scholar
7. Robert Bridson. 2007. Fast Poisson Disk Sampling in Arbitrary Dimensions. In ACM SIGGRAPH Sketches. 22–23.Google Scholar
8. Per Christensen, Julian Fong, Jonathan Shade, Wayne Wooten, Brenden Schubert, Andrew Kensler, Stephen Friedman, Charlie Kilpatrick, Cliff Ramshaw, Marc Bannister, and et al. 2018a. RenderMan: An Advanced Path-Tracing Architecture for Movie Rendering. ACM Trans. Graph. 37, 3 (2018), Art. 30.Google ScholarDigital Library
9. Per Christensen, Andrew Kensler, and Charlie Kilpatrick. 2018b. Progressive Multi-Jittered Sample Sequences. Computer Graphics Forum 37, 4 (2018), 21–33.Google ScholarCross Ref
10. Robert L. Cook. 1986. Stochastic Sampling in Computer Graphics. ACM Trans. Graph. 5, 1 (Jan. 1986), 51–72.Google ScholarDigital Library
11. Fernando De Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6 (2012), 171.Google Scholar
12. Josef Dick and Friedrich Pillichshammer. 2010. Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press.Google ScholarDigital Library
13. Mark A. Z. Dippé and Erling Henry Wold. 1985. Antialiasing through Stochastic Sampling. Computer Graphics 19, 3 (July 1985), 69–78.Google ScholarDigital Library
14. Fredo Durand. 2011. A frequency analysis of Monte-Carlo and other numerical integration schemes. MIT CSAIL Technical report TR-2011-052 (2011).Google Scholar
15. Raanan Fattal. 2011. Blue-Noise Point Sampling Using Kernel Density Model. ACM Trans. Graph. 30, 4 (July 2011), 48:1–48:12.Google ScholarDigital Library
16. Iliyan Georgiev and Marcos Fajardo. 2016. Blue-Noise Dithered Sampling. 35:1–35:1. https://doi.org/10/gfznbxGoogle Scholar
17. Jens André Griepentrog, Wolfgang Höppner, Hans-Christoph Kaiser, and Joachim Rehberg. 2008. A bi-Lipschitz continuous, volume preserving map from the unit ball onto a cube. Note di Matematica 28, 1 (2008), 177–193.Google Scholar
18. Daniel Heck, Thomas Schlömer, and Oliver Deussen. 2013. Blue Noise Sampling with Controlled Aliasing. ACM Trans. Graph. 32, 3 (2013), 25:1–25:12.Google ScholarDigital Library
19. Eric Heitz and Laurent Belcour. 2019. Distributing Monte Carlo Errors as a Blue Noise in Screen Space by Permuting Pixel Seeds Between Frames. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 149–158.Google Scholar
20. Eric Heitz, Laurent Belcour, Victor Ostromoukhov, David Coeurjolly, and Jean-Claude Iehl. 2019. A Low-Discrepancy Sampler that Distributes Monte Carlo Errors as a Blue Noise in Screen Space. In ACM SIGGRAPH Talk.Google Scholar
21. Edmund Hlavka. 1961. Funktionen von beschränkter Variation in der Theorie der Gleichverteilung. Annali di Matematica Pura ed Applicata 54, 1 (1961), 325–333.Google Scholar
22. Wenzel Jakob. 2013. Mitsuba Renderer. http://www.mitsuba-renderer.org.Google Scholar
23. Wojciech Jarosz, Afnan Enayet, Andrew Kensler, Charlie Kilpatrick, and Per Christensen. 2019. Orthogonal Array Sampling for Monte Carlo Rendering. Computer Graphics Forum 38, 4 (2019), 135–147.Google ScholarCross Ref
24. Stephen Joe and Frances Y Kuo. 2008. Constructing Sobol sequences with better two-dimensional projections. SIAM Journal on Scientific Computing 30, 5 (2008), 2635–2654.Google ScholarDigital Library
25. Leonid Vitalevich Kantorovich. 1948. Functional analysis and applied mathematics. Uspekhi Matematicheskikh Nauk 3, 6 (1948), 89–185.Google Scholar
26. Leonid V. Kantorovich and Gennady S. Rubinstein. 1958. On a space of completely additive functions. Vestnik Leningrad. Univ 13, 7 (1958), 52–59.Google Scholar
27. Alexander Keller. 2004. Stratification by rank-1 lattices. In Monte Carlo and Quasi-Monte Carlo Methods 2002, Harald Niederreiter (Ed.). Springer, 299–313.Google Scholar
28. Alexander Keller. 2013. Quasi-Monte Carlo Image Synthesis in a Nutshell. In MCQMC, Josef Dick, Frances Y. Kuo, Gareth W. Peters, and Ian H. Sloan (Eds.). Springer, 213–249.Google Scholar
29. Johannes Kopf, Daniel Cohen-Or, Oliver Deussen, and Dani Lischinski. 2006. Recursive Wang Tiles for Real-Time Blue Noise. ACM Trans. Graph. 25, 3 (2006), 509–518.Google ScholarDigital Library
30. Christopher Kulla, Alejandro Conty, Clifford Stein, and Larry Gritz. 2018. Sony Pictures Imageworks Arnold. ACM Trans. Graph. 37, 3 (2018).Google ScholarDigital Library
31. Ares Lagae and Philip Dutré. 2006. An Alternative for Wang Tiles: Colored Edges versus Colored Corners. ACM Trans. Graph. 25, 4 (Oct. 2006), 1442–1459.Google ScholarDigital Library
32. Pierre L’Ecuyer and David Munger. 2016. Lattice Builder: A General Software Tool for Constructing Rank-1 Lattice Rules. https://github.com/umontreal-simul/latnetbuilder.Google Scholar
33. Christiane Lemieux. 2009. Monte Carlo and Quasi Monte Carlo Sampling. Springer-Verlag New York.Google Scholar
34. 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
35. Quentin Mérigot. 2011. A multiscale approach to optimal transport. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1583–1592.Google Scholar
36. Don P. Mitchell. 1987. Generating Antialiased Images at Low Sampling Densities. Computer Graphics 21, 4 (Aug. 1987), 65–72.Google ScholarDigital Library
37. Don P Mitchell. 1991. Spectrally optimal sampling for distribution ray tracing. Computer Graphics 25, 4 (1991), 157–164.Google ScholarDigital Library
38. Patrick Mullen, Pooran Memari, Fernando de Goes, and Mathieu Desbrun. 2011. HOT: Hodge-optimized Triangulations. ACM Trans. Graph. 30, 4 (2011), Art. 103.Google Scholar
39. Georges Nader and Gael Guennebaud. 2018. Instant transport maps on 2D grids. ACM Trans. Graph. 37, 6 (2018), 13.Google Scholar
40. Jan Novák, Iliyan Georgiev, Johannes Hanika, and Wojciech Jarosz. 2018. Monte Carlo Methods for Volumetric Light Transport Simulation. 37, 2 (2018).Google Scholar
41. Victor Ostromoukhov, Charles Donohue, and Pierre-Marc Jodoin. 2004. Fast hierarchical importance sampling with blue noise properties. In ACM Trans. Graph., Vol. 23. ACM, 488–495.Google ScholarDigital Library
42. Art B. Owen. 1998. Scrambling Sobol’s and Niederreiter-Xing Points. Journal of Complexity 14, 4 (1998), 466–489.Google ScholarDigital Library
43. A. Cengiz Öztireli. 2016. Integration with Stochastic Point Processes. ACM Trans. Graph. 35, 5 (Aug. 2016), Art. 160.Google ScholarDigital Library
44. 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. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 339–353.Google Scholar
45. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically Based Rendering: From Theory to Implementation (3 ed.). Morgan-Kaufmann.Google Scholar
46. Adrien Pilleboue, Gurprit Singh, David Coeurjolly, Michael Kazhdan, and Victor Ostromoukhov. 2015. Variance Analysis for Monte Carlo Integration. ACM Trans. Graph. 34, 4 (July 2015), 124:1–124:14.Google ScholarDigital Library
47. Francois Pitié, Anil C. Kokaram, and Rozenn Dahyot. 2005. N-Dimensional Probablility Density Function Transfer and Its Application to Colour Transfer. In IEEE Int. Conf. on Computer Vision (ICCV).Google Scholar
48. Hongxing Qin, Yi Chen, Jinlong He, and Baoquan Chen. 2017. Wasserstein blue noise sampling. ACM Trans. Graph. 36, 4 (2017), Art. 137.Google ScholarDigital Library
49. Julien Rabin, Gabriel Peyré, Julie Delon, and Marc Bernot. 2011. Wasserstein barycenter and its application to texture mixing. In International Conference on Scale Space and Variational Methods in Computer Vision. Springer, 435–446.Google Scholar
50. Johann Radon. 1986. On the determination of functions from their integral values along certain manifolds. IEEE Transactions on Medical Imaging 5, 4 (1986), 170–176.Google ScholarCross Ref
51. Bernhard Reinert, Tobias Ritschel, Hans-Peter Seidel, and Iliyan Georgiev. 2016. Projective blue-noise sampling. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 285–295.Google Scholar
52. Mark Rowland, Krzysztof M Choromanski, François Chalus, Aldo Pacchiano, Tamas Sarlos, Richard E Turner, and Adrian Weller. 2018. Geometrically Coupled Monte Carlo Sampling. In Advances in Neural Information Processing Systems. Vol. 31. 195–206.Google Scholar
53. Peter Shirley and Kenneth Chiu. 1997. A low distortion map between disk and square. Journal of Graphics Tools 2, 3 (1997), 45–52.Google ScholarDigital Library
54. Gurprit Singh and Wojciech Jarosz. 2017. Convergence Analysis for Anisotropic Monte Carlo Sampling Spectra. ACM Trans. Graph. 36, 4 (July 2017), 137:1–137:14.Google ScholarDigital Library
55. Gurprit Singh, Kartic Subr, David Coeurjolly, Victor Ostromoukhov, and Wojciech Jarosz. 2019. Fourier Analysis of Correlated Monte Carlo Importance Sampling. Computer Graphics Forum 38, 1 (April 2019).Google ScholarCross Ref
56. 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 Trans. Graph. 34, 4 (2015), Art. 66.Google ScholarDigital Library
57. Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. 2014. Earth Mover’s Distances on Discrete Surfaces. ACM Trans. Graph. 33, 4 (2014), Art. 67.Google ScholarDigital Library
58. Kartic Subr and Jan Kautz. 2013. Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration. ACM Trans. Graph. 32, 4, Article 128 (2013), 12 pages.Google ScholarDigital Library
59. Peter Aundal Toft and John Aasted Sørensen. 1996. The Radon transform-theory and implementation. (1996).Google Scholar
60. Salvatore Torquato, Obioma Uche, and Frank Stillinger. 2006. Random sequential addition of hard spheres in high Euclidean dimensions. Physical Review E 74, 6 (2006), 061308.Google ScholarCross Ref
61. Robert Ulichney. 1987. Digital Halftoning. MIT Press, Cambridge, MA, USA.Google ScholarDigital Library
62. Eric Veach. 1997. Robust Monte Carlo methods for light transport simulation. Stanford University PhD thesis.Google ScholarDigital Library
63. Cédric Villani. 2009. Optimal Transport: Old and New. Fundamental Principles of Mathematical Sciences, Vol. 338. Springer-Verlag.Google ScholarCross Ref
64. Li-Yi Wei. 2010. Multi-Class Blue Noise Sampling. ACM Trans. Graph. 29, 4 (July 2010), 79:1–79:8.Google ScholarDigital Library
65. Yahan Zhou, Haibin Huang, Li-Yi Wei, and Rui Wang. 2012. Point sampling with general noise spectrum. ACM Trans. Graph. 31, 4 (2012), 76.Google ScholarDigital Library
