“Optimal multiple importance sampling” by Kondapaneni, Vévoda, Grittmann, Skrivan, Slusallek, et al. …
Conference:
Type(s):
Title:
- Optimal multiple importance sampling
Session/Category Title: Light Science
Presenter(s)/Author(s):
Abstract:
Multiple Importance Sampling (MIS) is a key technique for achieving robustness of Monte Carlo estimators in computer graphics and other fields. We derive optimal weighting functions for MIS that provably minimize the variance of an MIS estimator, given a set of sampling techniques. We show that the resulting variance reduction over the balance heuristic can be higher than predicted by the variance bounds derived by Veach and Guibas, who assumed only non-negative weights in their proof. We theoretically analyze the variance of the optimal MIS weights and show the relation to the variance of the balance heuristic. Furthermore, we establish a connection between the new weighting functions and control variates as previously applied to mixture sampling. We apply the new optimal weights to integration problems in light transport and show that they allow for new design considerations when choosing the appropriate sampling techniques for a given integration problem.
References:
1. James Arvo. 1995. Stratified Sampling of Spherical Triangles. In Proc. SIGGRAPH 1995. ACM, New York, NY, USA, 437–438. Google ScholarDigital Library
2. Gilles Aubert and Pierre Kornprobst. 2006. Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations (2nd ed.). Springer. Google ScholarDigital Library
3. Benedikt Bitterli. 2016. Rendering resources. https://benedikt-bitterli.me/resources/.Google Scholar
4. Olivier Cappé, Randal Douc, Arnaud Guillin, Jean-Michel Marin, and Christian P. Robert. 2008. Adaptive importance sampling in general mixture classes. Statistics and Computing 18, 4 (01 Dec 2008), 447–459. Google ScholarDigital Library
5. Victor Elvira, Luca Martino, David Luengo, and Mónica F. Bugallo. 2015. Generalized multiple importance sampling. arXiv:1511.03095.Google Scholar
6. Victor Elvira, Luca Martino, David Luengo, and Monica F. Bugallo. 2016. Heretical multiple importance sampling. IEEE Signal Processing Letters 23, 10 (Oct 2016).Google ScholarCross Ref
7. Shaohua Fan, Stephen Chenney, Bo Hu, Kam Wah Tsui, and Yu Chi Lai. 2006. Optimizing control variate estimators for rendering. Comput. Graph. Forum (EUROGRAPHICS 2006) 25, 3 (2006), 351–357.Google Scholar
8. Iliyan Georgiev, Jaroslav Křivánek, Tomáš Davidovič, and Philipp Slusallek. 2012a. Light Transport Simulation with Vertex Connection and Merging. ACM Trans. Graph. (SIGGRAPH Asia 2012) 31, 6, Article 192 (Nov. 2012), 10 pages. Google ScholarDigital Library
9. Iliyan Georgiev, Jaroslav Křivánek, Stefan Popov, and Philipp Slusallek. 2012b. Importance Caching for Complex Illumination. Comput. Graph. Forum (EUROGRAPHICS 2012) 31, 2pt3 (May 2012), 701–710. Google ScholarDigital Library
10. Paul Glasserman. 2003. Monte Carlo method in financial engineering. Springer-Verlag, New York, USA.Google Scholar
11. Adrien Gruson, Mickaël Ribardière, Martin Šik, Jiří Vorba, Rémi Cozot, Kadi Bouatouch, and Jaroslav Křivánek. 2016. A Spatial Target Function for Metropolis Photon Tracing. ACM Trans. Graph. 36, 4, Article 75a (Nov. 2016). Google ScholarDigital Library
12. Toshiya Hachisuka, Anton S. Kaplanyan, and Carsten Dachsbacher. 2014. Multiplexed Metropolis Light Transport. ACM Trans. Graph. (SIGGRAPH 2014) 33, 4 (2014). Google ScholarDigital Library
13. Toshiya Hachisuka, Jacopo Pantaleoni, and Henrik Wann Jensen. 2012. A Path Space Extension for Robust Light Transport Simulation. ACM Trans. Graph. (SIGGRAPH Asia 2012) 31, 6, Article 191 (Nov. 2012), 10 pages. Google ScholarDigital Library
14. Vlastimil Havran and Mateu Sbert. 2014. Optimal Combination of Techniques in Multiple Importance Sampling. In Proc. VRCAI ’14. ACM, New York, NY, 141–150. Google ScholarDigital Library
15. Hera Y. He and Art B. Owen. 2014. Optimal mixture weights in multiple importance sampling. (2014), 1–22. arXiv:1411.3954Google Scholar
16. Sebastian Herholz, Oskar Elek, Jiří Vorba, Hendrik Lensch, and Jaroslav Křivánek. 2016. Product Importance Sampling for Light Transport Path Guiding. Comput. Graph. Forum (EGSR 2016) 35, 4 (2016), 67–77. Google ScholarDigital Library
17. Malvin H. Kalos and Paula A. Whitlock. 2008. Monte Carlo Methods (2nd ed.). Wiley-VCH.Google Scholar
18. Csaba Kelemen, László Szirmay-Kalos, György Antal, and Ferenc Csonka. 2002. A Simple and Robust Mutation Strategy for the Metropolis Light Transport Algorithm. Computer Graphics Forum 21, 3 (2002), 531–540.Google ScholarCross Ref
19. A. Keller, L. Fascione, M. Fajardo, I. Georgiev, P. Christensen, J. Hanika, C. Eisenacher, and G. Nichols. 2015. The Path Tracing Revolution in the Movie Industry. In ACM SIGGRAPH 2015 Courses. Article 24. Google ScholarDigital Library
20. Jaroslav Křivánek, Iliyan Georgiev, Toshiya Hachisuka, Petr Vévoda, Martin Šik, Derek Nowrouzezahrai, and Wojciech Jarosz. 2014. Unifying Points, Beams, and Paths in Volumetric Light Transport Simulation. ACM Trans. Graph. (SIGGRAPH 2014) 33, 4, Article 103 (July 2014), 13 pages. Google ScholarDigital Library
21. Stephen S. Lavenberg, Thomas L. Moeller, and Peter D. Welch. 1982. Statistical Results on Control Variables with Application to Queueing Network Simulation. Operations Research 30, 1 (1982), 182–202. Google ScholarDigital Library
22. H. Lu, R. Pacanowski, and X. Granier. 2013. Second-Order Approximation for Variance Reduction in Multiple Importance Sampling. Comput. Graph. Forum (EGSR 2013) 32, 7 (2013), 131–136.Google Scholar
23. Thomas Müller, Markus Gross, and Jan Novák. 2017. Practical Path Guiding for Efficient Light-Transport Simulation. Comput. Graph. Forum (EGSR 2017) 36, 4 (2017), 91–100. Google ScholarDigital Library
24. Art Owen and Yi Zhou. 2000. Safe and Effective Importance Sampling. J. Amer. Statist. Assoc. 95, 449 (2000), 135–143.Google ScholarCross Ref
25. Anthony Pajot, Loic Barthe, Mathias Paulin, and Pierre Poulin. 2011. Representativity for Robust and Adaptive Multiple Importance Sampling. IEEE Transactions on Visualization and Computer Graphics 17, 8 (Aug. 2011), 1108–1121. Google ScholarDigital Library
26. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically Based Rendering: From Theory to Implementation (3rd ed.). Morgan Kaufmann. Google ScholarDigital Library
27. Stefan Popov, Ravi Ramamoorthi, Fredo Durand, and George Drettakis. 2015. Probabilistic Connections for Bidirectional Path Tracing. Comput. Graph. Forum (EGSR 2015) 34, 4 (July 2015), 75–86. Google ScholarDigital Library
28. Reuven Y. Rubinstein and Ruth Marcus. 1985. Efficiency of Multivariate Control Variates in Monte Carlo Simulation. Operations Research 33, 3 (1985), 661–677. Google ScholarDigital Library
29. Mateu Sbert and Vlastimil Havran. 2017. Adaptive Multiple Importance Sampling for General Functions. Vis. Comput. 33, 6–8 (June 2017), 845–855. Google ScholarDigital Library
30. Mateu Sbert, Vlastimil Havran, and Laszlo Szirmay-Kalos. 2016. Variance Analysis of Multi-sample and One-sample Multiple Importance Sampling. Computer Graphics Forum 35, 7 (2016), 451–460. Google ScholarDigital Library
31. Mateu Sbert, Vlastimil Havran, and Laszlo Szirmay-Kalos. 2018. Multiple importance sampling revisited: breaking the bounds. EURASIP Journal on Advances in Signal Processing 2018, 1 (27 Feb 2018), 15.Google ScholarCross Ref
32. Eric Veach. 1997. Robust Monte Carlo methods for light transport simulation. Ph.D. Dissertation. Stanford University. Google ScholarDigital Library
33. Eric Veach and Leonidas J. Guibas. 1995. Optimally Combining Sampling Techniques for Monte Carlo Rendering. Proc. SIGGRAPH ’95, 419–428. Google ScholarDigital Library
34. Sekhar Venkatraman and James R. Wilson. 1986. The efficiency of control variates in multiresponse simulation. Operations Research Letters 5, 1 (1986), 37–42. Google ScholarDigital Library
35. Petr Vévoda, IvoKondapaneni, and Jaroslav Křivánek. 2018. Bayesian Online Regression for Adaptive Direct Illumination Sampling. ACM Trans. Graph. (SIGGRAPH 2018) 37, 4, Article 125 (July 2018), 12 pages. Google ScholarDigital Library
36. Jiří Vorba, Ondřej Karlík, Martin Šik, Tobias Ritschel, and Jaroslav Křivánek. 2014. On-line Learning of Parametric Mixture Models for Light Transport Simulation. ACM Trans. Graph. (SIGGRAPH 2014) 33, 4, Article 101 (July 2014), 11 pages. Google ScholarDigital Library
37. Martin Šik, Hisanari Otsu, Toshiya Hachisuka, and Jaroslav Křivánek. 2016. Robust Light Transport Simulation via Metropolised Bidirectional Estimators. ACM Trans. Graph. (SIGGRAPH Asia 2016) 35, 6, Article 245 (Nov. 2016), 12 pages. Google ScholarDigital Library
