“Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration” by Subr and Kautz

  • ©Kartic Subr and Jan Kautz




    Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration

Session/Category Title: Sampling




    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.


    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

ACM Digital Library Publication:

Overview Page: