ACM Trans. Graph. (Proceedings of SIGGRAPH Asia 2016)

Low-Discrepancy Blue Noise Sampling

Abdalla G. M. Ahmed¹       Hélène Perrier²       David Coeurjolly²       Victor Ostromoukhov²
Jianwei Guo³       Dongming Yan³       Hui Huang^4,5       Oliver Deussen^1,5

¹University of Konstanz, Germany
²Université de Lyon, CNRS/LIRIS, France
³NLPR, Institute of Automation, CAS, China
⁴Shenzhen University, China
⁵SIAT, China

Starting from a template low-discrepancy (LD) point set (a), we use a segmented table of permutations to rearrange the LD set to match a reference set with the desired target spectrum (b). The permutations are localized and carefully constructed in such a way that they have minimal impact on the discrepancy of the underlying template set. The resulting set (c) inherits the spectral profile of the target set, while still retaining the discrepancy profile of the template set (d).

Abstract

We present a novel technique that produces two-dimensional low-discrepancy (LD) blue noise point sets for sampling. Using one-dimensional binary van der Corput sequences, we construct two-dimensional LD point sets, and rearrange them to match a target spectral profile without loosing their low discrepancy. We store the rearrangement information in a compact lookup table that can be used to produce arbitrarily large point sets. We evaluate our technique and compare it to the state-of-the-art sampling approaches.

Interactive Demo

You can draw samples right from this page, scaled to unit area. Drag to move around, use the mouse wheel or pinch to zoom. What You See Is What You Get!

Results

This html bundle contains all the data that was collected while performing tests and comparisons between the LDBN sampler and various other samplers from the state of the art. You can click on any sampler to see all its associated data, discrepancy results, integration variance results, point distribution, behaviour relatively to aliasing (zoneplate tests), and spectral behaviour.

Video

Downloads

	Get for free at ACM digital library
	Supplementary PDF (2.3 MB)
	Source Code ZIP (37 KB)

Bibtex

@article{Ahmed2016LDBN,
    author = {Ahmed, Abdalla G. M. and Perrier, H\'{e}l\`{e}ne and Coeurjolly,
              David and Ostromoukhov, Victor and Guo, Jianwei and Yan,
              Dong-Ming and Huang, Hui and Deussen, Oliver},
    title = {Low-Discrepancy Blue Noise Sampling},
    year = {2016},
    issue_date = {November 2016},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    volume = {35},
    number = {6},
    issn = {0730-0301},
    url = {https://doi.org/10.1145/2980179.2980218},
    doi = {10.1145/2980179.2980218},
    journal = {ACM Trans. Graph.},
    month = nov,
    articleno = {247},
    numpages = {13},
    keywords = {sampling, monte carlo, quasi-monte carlo, blue noise, low discrepancy}
}
        

Acknowledgments

We thank the anonymous reviewers for their detailed feedback to improve the paper. Thanks to Jean-Yves Franceschi and Jonathan Dupuy for reviewing an earlier version of the paper. This project was supported in part by Deutsche Forschungsgemeinschaft Grant (DE-620/22-1), French ANR Excellence Chair (ANR-10-CEXC-002-01) and CoMeDiC (ANR-15-CE40-0006), 973 Program (2015CB352501), National Foreign 1000 Plan (WQ201344000169), National Natural Science Foundation of China (61372168, 61620106003, 61331018), GD Leading Talents Plan (00201509), GD Science and Technology Program (2014B050502009, 2014TX01X033, 2015A030312015, 2016A050503036), and SZ Innovation Program (JCYJ20151015151249564).

Other

Web pages for this project are also maintained at Universit of Konstanz and LIRIS