“Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration” by Subr and Kautz
Conference:
Type(s):
Title:
- Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration
Session/Category Title: Sampling
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Each pixel in a photorealistic, computer generated picture is calculated by approximately integrating all the light arriving at the pixel, from the virtual scene. A common strategy to calculate these high-dimensional integrals is to average the estimates at stochastically sampled locations. The strategy with which the sampled locations are chosen is of utmost importance in deciding the quality of the approximation, and hence rendered image.We derive connections between the spectral properties of stochastic sampling patterns and the first and second order statistics of estimates of integration using the samples. Our equations provide insight into the assessment of stochastic sampling strategies for integration. We show that the amplitude of the expected Fourier spectrum of sampling patterns is a useful indicator of the bias when used in numerical integration. We deduce that estimator variance is directly dependent on the variance of the sampling spectrum over multiple realizations of the sampling pattern. We then analyse Gaussian jittered sampling, a simple variant of jittered sampling, that allows a smooth trade-off of bias for variance in uniform (regular grid) sampling. We verify our predictions using spectral measurement, quantitative integration experiments and qualitative comparisons of rendered images.
References:
1. Amidror, I., Hersch, R. D., and Ostromoukhov, V. 1994. Spectral analysis and minimization of moiré patterns in color separation. J. Electron. Imaging 3, 295–317.Google ScholarCross Ref
2. Arvo, J. 2001. Stratified sampling of 2-manifolds. SIGGRAPH 2001 Course Notes 29, 2.Google Scholar
3. Balakrishnan, A. 1962. On the problem of time jitter in sampling. Information Theory, IRE Transactions on 8, 3 (april), 226–236.Google ScholarCross Ref
4. Bartlett, M. S. 1964. The spectral analysis of two-dimensional point processes. Biometrika 51, 299–311.Google ScholarCross Ref
5. Belcour, L., Soler, C., Subr, K., Holzschuch, N., and Durand, F. 2012. 5d covariance tracing for efficient defocus and motion blur. Tech. Rep. MIT-CSAIL-TR-2012-034, MIT, MA, November 2012.Google Scholar
6. Bowers, J., Wang, R., Wei, L.-Y., and Maletz, D. 2010. Parallel poisson disk sampling with spectrum analysis on surfaces. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 29, 6, 166:1–166:10. Google ScholarDigital Library
7. Brémaud, P., Massoulié, L., and Ridolfi, A. 2003. Power spectra of random spike fields & related processes. Journal of Applied Probability 2002, 1116–1146.Google Scholar
8. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Transactions on Graphics 5, 1 (Jan.), 51–72. Google ScholarDigital Library
9. Dippe, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. In ACM SIGGRAPH ’85), B. A. Barsky, Ed., 69–78. Google ScholarDigital Library
10. Durand, F., Holzschuch, N., Soler, C., Chan, E., and Sillion, F. X. 2005. A frequency analysis of light transport. ACM Trans. Graph. (Proc. SIGGRAPH) 24, 3 (July), 1115–1126. Google ScholarDigital Library
11. Durand, F. 2011. A frequency analysis of Monte-Carlo and other numerical integration schemes. Tech. Rep. MIT-CSAIL-TR-2011-052, CSAIL, MIT, MA.Google Scholar
12. Egan, K., Tseng, Y.-T., Holzschuch, N., Durand, F., and Ramamoorthi, R. 2009. Frequency analysis and sheared reconstruction for rendering motion blur. ACM Trans. Graph. 28, 3 (July), 93:1–93:13. Google ScholarDigital Library
13. Fienup, J. R. 1997. Invariant error metrics for image reconstruction. Appl. Opt. 36, 32 (Nov), 8352–8357.Google ScholarCross Ref
14. Gallaher, L. J. 1973. A multidimensional Monte Carlo quadrature with adaptive stratified sampling. Commun. ACM 16, 1 (Jan.), 49–50. Google ScholarDigital Library
15. Gamito, M. N., and Maddock, S. C. 2009. Accurate multidimensional Poisson-disk sampling. ACM Transactions on Graphics 29, 1 (Dec.), 8:1–8:19. Google ScholarDigital Library
16. Hachisuka, T., Jarosz, W., Weistroffer, R. P., Dale, K., Humphreys, G., Zwicker, M., and Jensen, H. W. 2008. Multidimensional adaptive sampling and reconstruction for ray tracing. ACM Trans. Graph. (Proc. SIGGRAPH) 27, 3 (Aug.), 33:1–33:10. Google ScholarDigital Library
17. Keller, A., and Heidrich, W. 2001. Interleaved sampling. In Rendering Techniques, 269–276. Google ScholarDigital Library
18. Keller, A., Heinrich, S., and Niederreiter, H. 2006. Monte Carlo and Quasi-Monte Carlo methods. Springer. Google ScholarDigital Library
19. Keller, A. 2002. Stratification by Rank-1-Lattices. Interner Bericht. Universität Kaiserslautern, Fachbereich Informatik.Google Scholar
20. Kollig, T., and Keller, A. 2002. Efficient multidimensional sampling. Comput. Graph. Forum (Proc. Eurographics) 21, 3, 557–557.Google ScholarCross Ref
21. Křivánek, J., and Colbert, M. 2008. Real-time shading with filtered importance sampling. Computer Graphics Forum (Proc. Eurographics Symposium on Rendering) 27, 4, 1147–1154. Google ScholarDigital Library
22. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating poisson disk distributions. Comput. Graph. Forum 27, 1, 114–129.Google ScholarCross Ref
23. Larcher, G., and Pillichshammer, F. 2001. Walsh series analysis of the L2-discrepancy of symmetrisized point sets. Monatshefte für Mathematik 132, 1, 1–18.Google ScholarCross Ref
24. Lehtinen, J., Aila, T., Laine, S., and Durand, F. 2012. Reconstructing the indirect light field for global illumination. ACM Trans. Graph. (Proc. SIGGRAPH) 31, 4 (July), 51:1–51:10. Google ScholarDigital Library
25. Leneman, O. A. 1966. Random sampling of random processes: Impulse processes. Information and Control 9, 4, 347–363.Google ScholarCross Ref
26. Luchini, P. 1994. Fourier analysis of numerical integration formulae. Computer Physics Communications 83, 23, 227–235.Google ScholarCross Ref
27. Machiraju, R., Swan, E., and Yagel, R. 1995. Spatial domain characterization and control of reconstruction errors. In Proceedings of the 6th Eurographics Workshop on Rendering, 33–44.Google Scholar
28. Matérn, B. 1960. Spatial variation. Meddelanden fran Statens Skogsforskningsinstitut 49, 1–144.Google Scholar
29. Matérn, B. 1986. Spatial Variation, 2nd ed. Springer Verlag.Google Scholar
30. Mitchell, D. P., and Netravali, A. N. 1988. Reconstruction filters in computer-graphics. SIGGRAPH Comput. Graph. 22 (June), 221–228. Google ScholarDigital Library
31. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. M. C. Stone, Ed., vol. 21, 65–72. Google ScholarDigital Library
32. Mitchell, D. P. 1991. Spectrally optimal sampling for distribution ray tracing. T. W. Sederberg, Ed., vol. 25, 157–164. Google ScholarDigital Library
33. Mitchell, D. P. 1992. Ray Tracing and Irregularities of Distribution. In Third Eurographics Workshop on Rendering, 61–69.Google Scholar
34. Mitchell, D. 1996. Consequences of stratified sampling in graphics. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, ACM, 277–280. Google ScholarDigital Library
35. Neyman, J. 1934. On the two different aspects of the representative method: the method of stratified sampling and the method of purposive selection. Journal of the Royal Statistical Society 97, 4, 558–625.Google ScholarCross Ref
36. Niederreiter, H. 1992. Quasi-Monte Carlo Methods. John Wiley & Sons, Ltd.Google Scholar
37. Ostromoukhov, V. 2007. Sampling with polyominoes. ACM Trans. Graph. (Proc. SIGGRAPH) 26, 3 (July), 78:1–78:6. Google ScholarDigital Library
38. Ouellette, M. J., and Fiume, E. 2001. On numerical solutions to one-dimensional integration problems with applications to linear light sources. ACM Trans. Graph. 20, 4 (Oct.), 232–279. Google ScholarDigital Library
39. Öztireli, A. C., and Gross, M. 2012. Analysis and synthesis of point distributions based on pair correlation. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 31, 6 (Nov.), 170:1–170:10. Google ScholarDigital Library
40. Pharr, M., and Humphreys, G. 2010. Physically Based Rendering, Second Edition: From Theory To Implementation, 2nd ed. Morgan Kaufmann Publishers Inc. Google ScholarDigital Library
41. Ramamoorthi, R., and Hanrahan, P. 2004. A signal-processing framework for reflection. ACM Trans. Graph. 23, 4 (Oct.), 1004–1042. Google ScholarDigital Library
42. Ramamoorthi, R., Anderson, J., Meyer, M., and Nowrouzezahrai, D. 2012. A theory of monte carlo visibility sampling. ACM Trans. Graph. 31, 5 (Sept.), 121:1–121:16. Google ScholarDigital Library
43. Ripley, B. 1977. Modelling spatial patterns. J. Roy. Statist. Soc. B 39, 172–212.Google Scholar
44. Schlömer, T., and Deussen, O. 2011. Accurate spectral analysis of two-dimensional point sets. Journal of Graphics, GPU, and Game Tools 15, 3, 152–160.Google ScholarCross Ref
45. Shirley, P. 1991. Discrepancy as a quality measure for sampling distributions. In Proc. Eurographics ’91, 183–194.Google Scholar
46. Soler, C., Subr, K., Durand, F., Holzschuch, N., and Sillion, F. 2009. Fourier depth of field. ACM Trans. Graph. 28, 2 (May), 18:1–18:12. Google ScholarDigital Library
47. Subr, K., and Arvo, J. 2007. Statistical hypothesis testing for assessing Monte Carlo estimators: Applications to image synthesis. In Pacific Graphics 2007, 106–115. Google ScholarDigital Library
48. Wei, L.-Y., and Wang, R. 2011. Differential domain analysis for non-uniform sampling. ACM Trans. Graph. (Proc. SIGGRAPH) 30, 4, 50:1–50:10. Google ScholarDigital Library
49. Zhou, Y., Huang, H., Wei, L.-Y., and Wang, R. 2012. Point sampling with general noise spectrum. ACM Trans. Graph. (Proc. SIGGRAPH) 31, 4 (July), 76:1–76:11. Google ScholarDigital Library
