“Point sampling with general noise spectrum” by Zhou, Huang, Wei and Wang

  • ©Yahan Zhou, Haibin Huang, Li-Yi Wei, and Rui Wang




    Point sampling with general noise spectrum



    Point samples with different spectral noise properties (often defined using color names such as white, blue, green, and red) are important for many science and engineering disciplines including computer graphics. While existing techniques can easily produce white and blue noise samples, relatively little is known for generating other noise patterns. In particular, no single algorithm is available to generate different noise patterns according to user-defined spectra.In this paper, we describe an algorithm for generating point samples that match a user-defined Fourier spectrum function. Such a spectrum function can be either obtained from a known sampling method, or completely constructed by the user. Our key idea is to convert the Fourier spectrum function into a differential distribution function that describes the samples’ local spatial statistics; we then use a gradient descent solver to iteratively compute a sample set that matches the target differential distribution function. Our algorithm can be easily modified to achieve adaptive sampling, and we provide a GPU-based implementation. Finally, we present a variety of different sample patterns obtained using our algorithm, and demonstrate suitable applications.


    1. Alliez, P., Meyer, M., and Desbrun, M. 2002. Interactive geometry remeshing. In SIGGRAPH ’02, 347–354. Google ScholarDigital Library
    2. Balzer, M., Schlomer, T., and Deussen, O. 2009. Capacity-constrained point distributions: A variant of Lloyd’s method. In SIGGRAPH ’09, 86:1–8. Google ScholarDigital Library
    3. Bracewell, R. 1999. The Fourier Transform and Its Applications. McGraw-Hill.Google Scholar
    4. Chang, J., Alain, B., and Ostromoukhov, V. 2009. Structure-aware error diffusion. In SIGGRAPH Asia ’09, 162:1–8. Google ScholarDigital Library
    5. Condit, R., Ashton, P. S., Baker, P., Bunyavejchewin, S., Gunatilleke, S., Gunatilleke, N., Hubbell, S. P., Foster, R. B., Itoh, A., LaFrankie, J. V., Lee, H. S., Losos, E., Manokaran11, N., Sukumar, R., and Yamakura, T. 2000. Spatial patterns in the distribution of tropical tree species. Science 288, 5470, 1414–1418.Google Scholar
    6. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1, 51–72. Google ScholarDigital Library
    7. Dale, M. R. T., Dixon, P., Fortin, M.-J., Legendre, P., Myers, D. E., and Rosenberg, M. S. 2002. Conceptual and mathematical relationships among methods for spatial analysis. ECOGRAPHY, 25, 558–577.Google ScholarCross Ref
    8. Dippé, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. In SIGGRAPH ’85, 69–78. Google ScholarDigital Library
    9. Dutre, P., Bala, K., and Bekaert, P. 2002. Advanced Global Illumination. A. K. Peters, Ltd., Natick, MA, USA. Google ScholarDigital Library
    10. Ebeida, M. S., Patney, A., Mitchell, S. A., Davidson, A., Knupp, P. M., and Owens, J. D. 2011. Efficient maximal Poisson-disk sampling. In SIGGRAPH ’11, 49:1–12. Google ScholarDigital Library
    11. Ebeida, M. S., Mitchell, S. A., Patney, A., Davidson, A., and Owens, J. D. 2012. A simple algorithm for maximal Poisson-disk sampling in high dimensions. Computer Graphics Forum 31, 2, 785–794. Google ScholarDigital Library
    12. Fattal, R. 2011. Blue-noise point sampling using kernel density model. ACM SIGGRAPH 2011 papers 28, 3, 1–10. Google ScholarDigital Library
    13. Greene, D. F., and Johnson, E. A. 1989. A model of wind dispersal of winged or plumed seeds. Ecology 70, 2, 339–347.Google ScholarCross Ref
    14. Haase, P., Pugnaire, F. I., Clark, S., and Incoll, L. 1996. Spatial patterns in a two-tiered semi-arid shrubland in southeastern spain. Journal of Vegetation Science, 7, 527–534.Google ScholarCross Ref
    15. Kalantari, N. K., and Sen, P. 2011. Efficient computation of blue noise point sets through importance sampling. Computer Graphics Forum (EGSR ’11) 30, 4, 1215–1221. Google ScholarDigital Library
    16. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive Wang tiles for real-time blue noise. In SIGGRAPH ’06, 509–518. Google ScholarDigital Library
    17. Lagae, A., and Drettakis, G. 2011. Filtering solid Gabor noise. In SIGGRAPH ’11, 51:1–6. Google ScholarDigital Library
    18. Lagae, A., and Dutré, P. 2006. An alternative for Wang tiles: colored edges versus colored corners. ACM Trans. Graph. 25, 4, 1442–1459. Google ScholarDigital Library
    19. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 21, 1, 114–129.Google ScholarCross Ref
    20. Lagae, A., Lefebvre, S., Drettakis, G., and Dutré, P. 2009. Procedural noise using sparse Gabor convolution. In SIGGRAPH ’09, 54:1–10. Google ScholarDigital Library
    21. Lau, D. L., Arce, G. R., and Gallagher, N. C. 1999. Digital halftoning by means of green-noise masks. 1575–1586.Google Scholar
    22. Lau, D., Ulichney, R., and Arce, G. 2003. Fundamental characteristics of halftone textures: blue-noise and green-noise. IEEE Signal Processing Magazine 20, 4, 28–38.Google ScholarCross Ref
    23. Li, H., and Mould, D. 2011. Structure-preserving stippling by priority-based error diffusion. In GI ’11, 127–134. Google ScholarDigital Library
    24. Li, H., Wei, L.-Y., Sander, P., and Fu, C.-W. 2010. Anisotropic blue noise sampling. In SIGGRAPH Asia ’10, 167:1–12. Google ScholarDigital Library
    25. Lloyd, S. 1983. An optimization approach to relaxation labeling algorithms. Image and Vision Computing 1, 2.Google ScholarCross Ref
    26. Martinez, V. J., Paredes, S., Borgani, S., and Coles, P. 1995. Multiscaling properties of large-scale structure in the universe. Science 269, 5228, 1245–1247.Google Scholar
    27. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In SIGGRAPH ’87, 65–72. Google ScholarDigital Library
    28. Ostling, A., Harte, J., and Green, J. 2000. Self-similarity and clustering in the spatial distribution of species. Science 290, 5492, 671.Google ScholarCross Ref
    29. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. In SIGGRAPH ’04, 488–495. Google ScholarDigital Library
    30. Ostromoukhov, V. 2001. A simple and efficient error-diffusion algorithm. In SIGGRAPH ’01, 567–572. Google ScholarDigital Library
    31. Ostromoukhov, V. 2007. Sampling with polyominoes. In SIGGRAPH ’07, 78. Google ScholarDigital Library
    32. Öztireli, A. C., Alexa, M., and Gross, M. 2010. Spectral sampling of manifolds. In SIGGRAPH ASIA ’10, 168:1–8. Google ScholarDigital Library
    33. Pang, W.-M., Qu, Y., Wong, T.-T., Cohen-Or, D., and Heng, P.-A. 2008. Structure-aware halftoning. In SIGGRAPH ’08. Google ScholarDigital Library
    34. Parker, K., Mitsa, T., and Ulichney, R. 1991. A new algorithm for manipulating the power spectrum of halftone patterns. In SPSE’s 7th Int. Congress on Non-Impact Printing, 471–475.Google Scholar
    35. Pharr, M., and Humphreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann Publishers Inc. Google ScholarDigital Library
    36. Schlömer, T., Heck, D., and Deussen, O. 2011. Farthest-point optimized point sets with maximized minimum distance. In HPG ’11, 135–142. Google ScholarDigital Library
    37. Schroeder, M. R. 1999. Computer Speech: Recognition, Compression, Synthesis. Springer. Google ScholarDigital Library
    38. Schua, K., Feger, K.-H., Wagner, S., Eisenhauer, D.-R., and Raben, G. 2009. Cause-Effect Relations with Regard to Functional and Morphological Humus Characteristics in Mixed Forest Stands. EGU General Assembly 2009 11 (Apr.), 226.Google Scholar
    39. Secord, A. 2002. Weighted Voronoi stippling. In NPAR ’02, 37–43. Google ScholarDigital Library
    40. Shirley, P. 1991. Discrepancy as a quality measure for sample distributions. In Eurographics ’91, 183–194.Google Scholar
    41. Turk, G. 1992. Re-tiling polygonal surfaces. In SIGGRAPH ’92, 55–64. Google ScholarDigital Library
    42. Tzeng, S., and Wei, L.-Y. 2008. Parallel white noise generation on a GPU via cryptographic hash. In I3D ’08: Proceedings of the 2008 symposium on Interactive 3D graphics and games, 79–87. Google ScholarDigital Library
    43. Ulichney, R. 1987. Digital Halftoning. MIT Press, Cambridge, MA. Google ScholarDigital Library
    44. Wei, L.-Y., and Wang, R. 2011. Differential domain analysis for non-uniform sampling. In SIGGRAPH ’11, 50:1–10. Google ScholarDigital Library
    45. Wei, L.-Y. 2010. Multi-class blue noise sampling. In SIGGRAPH ’10, 79:1–8. Google ScholarDigital Library
    46. Yellott, J. I. J. 1983. Spectral consequences of photoreceptor sampling in the rhesus retina. Science 221, 382–385.Google ScholarCross Ref
    47. Zhou, B., and Fang, X. 2003. Improving mid-tone quality of variable-coefficient error diffusion using threshold modulation. In SIGGRAPH ’03, 437–444. Google ScholarDigital Library

ACM Digital Library Publication: