Low-Discrepancy Blue Noise Sampling

Abdalla G.M. Ahmed, Hélène Perrier, David Coeurjolly, Victor Ostromoukhov, Jianwei Guo, Dong-Ming Yan, Hui HUANG, Oliver Deussen

ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia) January 2016

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.

Type

Journal article

Publication

ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia)

Caption: 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).

@article{dcoeurjo_SIGASIA16,
      author = {Ahmed, Abdalla G.M. and Perrier, Hélène and Coeurjolly, David and Ostromoukhov, Victor and Guo, Jianwei and Yan, Dong-Ming and HUANG, Hui and Deussen, Oliver},
      doi = {10.1145/2980179.2980218},
      hal_id = {hal-01372542},
      journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia)},
      keywords = {Quasi-Monte Carlo Methods QMC ; Blue Noise ; Low
Discrepancy ; Sampling ; Monte Carlo},
      number = {6},
      pages = {247:1--247:13},
      pdf = {https://hal.archives-ouvertes.fr/hal-01372542/file/final-paper.pdf},
      title = {Low-Discrepancy Blue Noise Sampling},
      volume = {35},
      year = {2016}
}

Quasi-Monte Carlo Methods QMC ; Blue Noise ; Low Discrepancy ; Sampling ; Monte Carlo