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

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