“Wasserstein Blue Noise Sampling” by Qin, Chen, He and Chen

  • ©Hongxing Qin, Yi Chen, Jinlong He, and Baoquan Chen




    Wasserstein Blue Noise Sampling

Session/Category Title: Random Sampling




    In this article, we present a multi-class blue noise sampling algorithm by throwing samples as the constrained Wasserstein barycenter of multiple density distributions. Using an entropic regularization term, a constrained transport plan in the optimal transport problem is provided to break the partition required by the previous Capacity-Constrained Voronoi Tessellation method. The entropic regularization term cannot only control spatial regularity of blue noise sampling, but it also reduces conflicts between the desired centroids of Vornoi cells for multi-class sampling. Moreover, the adaptive blue noise property is guaranteed for each individual class, as well as their combined class. Our method can be easily extended to multi-class sampling on a point set surface. We also demonstrate applications in object distribution and color stippling.


    1. Martial Agueh and Guillaume Carlier. 2011. Barycenters in the Wasserstein space. SIAM J. Math. Anal. 43, 2 (2011), 904–924. Google ScholarCross Ref
    2. Marc Alexa, Johannes Behr, Daniel Cohen-Or, Shachar Fleishman, David Levin, and Claudio T. Silva. 2001. Point set surfaces. In Proceedings of the Conference on IEEE Visualization. 21–28. Google ScholarCross Ref
    3. Michael Balzer, Thomas Schlömer, and Oliver Deussen. 2009. Capacity-constrained point distributions: A variant of Lloyd’s method. ACM Trans. Graph. (TOG) 28, 3 (2009), 86:1–86:8.Google ScholarDigital Library
    4. Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. 2015. Iterative Bregman projections for regularized transportation problems. SIAM J. Sci. Comput. 37, 2 (2015), A1111–A1138. Google ScholarCross Ref
    5. Nicolas Bonneel, Gabriel Peyré, and Marco Cuturi. 2016. Wasserstein barycentric coordinates: Histogram regression using optimal transport. ACM Trans. Graph. (TOG) 35, 4 (2016), 71:1–71:10.Google ScholarDigital Library
    6. Haidong Chen, Wei Chen, Honghui Mei, Zhiqi Liu, Kun Zhou, Weifeng Chen, Wentao Gu, and Kwan-Liu Ma. 2014. Visual abstraction and exploration of multi-class scatterplots. IEEE Trans. Visual. Comput. Graph. 20, 12 (2014), 1683–1692. Google ScholarCross Ref
    7. Zhonggui Chen, Zhan Yuan, Yi-King Choi, Ligang Liu, and Wenping Wang. 2012. Variational blue noise sampling. IEEE Trans. Visual. Comput. Graph. 18, 10 (2012), 1784–1796. Google ScholarDigital Library
    8. Robert L. Cook. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. (TOG) 5, 1 (1986), 51–72. Google ScholarDigital Library
    9. Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Adv. Neural Info. Process. Syst. 2292–2300.Google Scholar
    10. Marco Cuturi and Arnaud Doucet. 2014. Fast computation of Wasserstein barycenters. Proceedings of The 31st International Conference on Machine Learning (2014), 685–693.Google ScholarDigital Library
    11. Fernando de Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue noise through optimal transport. ACM Trans. Graph. (TOG) 31, 6 (2012), 171:1–171:11.Google ScholarDigital Library
    12. Mark A. Z. Dippé and Erling Henry Wold. 1985. Antialiasing through stochastic sampling. ACM Siggraph Comput. Graph. (TOG) 19, 3 (1985), 69–78. Google ScholarDigital Library
    13. Daniel Dunbar and Greg Humphreys. 2006. A spatial data structure for fast Poisson-disk sample generation. ACM Trans. Graph. (TOG) 25, 3 (2006), 503–508. Google ScholarDigital Library
    14. Mohamed S. Ebeida, Andrew A. Davidson, Anjul Patney, Patrick M. Knupp, Scott A. Mitchell, and John D. Owens. 2011. Efficient maximal Poisson-disk sampling. ACM Trans. Graph. (TOG) 30, 4 (2011), 49:1–49:12.Google ScholarDigital Library
    15. Mohamed S. Ebeida, Scott A. Mitchell, Anjul Patney, Andrew A. Davidson, and John D. Owens. 2012. A simple algorithm for maximal poisson-Disk sampling in high dimensions. Computer Graphics Forum 31, 24 (2012), 785–794. Google ScholarDigital Library
    16. Raanan Fattal. 2011. Blue-noise point sampling using kernel density model. 30, 4 (2011), 48:1–48:10.Google Scholar
    17. Manuel N. Gamito and Steve C. Maddock. 2009. Accurate multidimensional Poisson-Disk sampling. ACM Trans. Graph. (TOG) 29, 1 (2009), 81–8:19.Google ScholarDigital Library
    18. Min Jiang, Yahan Zhou, Rui Wang, Richard Southern, and Jian Jun Zhang. 2015. Blue noise sampling using an SPH-based method. ACM Trans. Graph. (TOG) 34, 6 (2015), 211:1–211:11.Google ScholarDigital Library
    19. Thouis R. Jones. 2006. Efficient generation of Poisson-Disk sampling patterns. J. Graph. GPU Game Tools 11, 2 (2006), 27–36. Google ScholarCross Ref
    20. Anuraag R. Kansal, Thomas M. Truskett, and Salvatore Torquato. 2000. Nonequilibrium hard-disk packings with controlled orientational order. J. Chem. Phys. 113, 12 (2000), 4844–4851. Google ScholarCross Ref
    21. A. Lagae and P. Dutré. 2008. A comparison of methods for generating Poisson disk distributions. Comput. Graph. Forum 27, 1 (2008), 114–129. Google ScholarCross Ref
    22. Stuart P. Lloyd. 1982. Least squares quantization in PCM. IEEE Trans. Info. Theory 28, 2 (1982), 129–137. Google ScholarDigital Library
    23. Michael McCool and Eugene Fiume. 1992. Hierarchical Poisson disk sampling distributions. In Proceedings of the Conference on Graphics Interface, Vol. 92. 94–105.Google Scholar
    24. D. P. Mitchell. 1987. Generating antialiased images at low sampling densities. In Proceedings of the the 14th ACM SIGGRAPH. ACM, 65–72. Google ScholarDigital Library
    25. A. Cengiz Öztireli, Marc Alexa, and Markus Gross. 2010. Spectral sampling of manifolds. ACM Trans. Graph. (TOG) 29, 6 (2010), 168:1–168:8.Google ScholarDigital Library
    26. Hossein Rahmani, Arif Mahmood, Du Q. Huynh, and Ajmal Mian. 2014. HOPC: Histogram of oriented principal components of 3D pointclouds for action recognition. In Proceedings of the European Conference on Computer Vision. 742–757. Google ScholarCross Ref
    27. Thomas Schlömer and Oliver Deussen. 2011. Accurate spectral analysis of two-dimensional point sets. J. Graph. GPU. Game Tools 15, 3 (2011), 152–160. Google ScholarCross Ref
    28. Thomas Schlömer, Daniel Heck, and Oliver Deussen. 2011. Farthest-point optimized point sets with maximized minimum distance. In Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics. ACM, 135–142. Google ScholarDigital Library
    29. Christian Schmaltz, Pascal Gwosdek, and Joachim Weickert. 2012. Multi-class anisotropic electrostatic halftoning. Comput. Graph. Forum 31, 6 (2012), 1924–1935. Google ScholarDigital Library
    30. Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. 2015. Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. ACM Trans. Graph. (TOG) 34, 4 (2015), 66.Google ScholarDigital Library
    31. Robert A. Ulichney. 1988. Dithering with blue noise. In Proceedings of the IEEE 76, 1, 56–79. Google ScholarCross Ref
    32. Cédric Villani. 2008. Optimal Transport: Old and New. Vol. 338. Springer Science 8 Business Media.Google Scholar
    33. Muge Wang and Kevin J. Parker. 1999. Properties of combined blue noise patterns. In Proceedings of the International Conference on Image Processing. 328–332.Google Scholar
    34. Li-Yi Wei. 2008. Parallel Poisson disk sampling. ACM Trans. Grap. (TOG) 27, 3 (2008), 20.Google Scholar
    35. Li-Yi Wei. 2010. Multi-class blue noise sampling. ACM Trans. Graph. (TOG) 29, 4 (2010), 79:1–79:8.Google ScholarDigital Library
    36. Li-Yi Wei and Rui Wang. 2011. Differential domain analysis for non-uniform sampling. ACM Trans. Graph. (TOG) 30, 4 (2011), 50:1–50:10.Google ScholarDigital Library
    37. Kenric B. White, David Cline, and Parris K. Egbert. 2007. Poisson disk point sets by hierarchical dart throwing. In Proceedings of the IEEE Symposium on Interactive Ray Tracing, 2007. 129–132. Google ScholarDigital Library
    38. Shi-Qing Xin, Bruno Lévy, Zhonggui Chen, Lei Chu, Yaohui Yu, Changhe Tu, and Wenping Wang. 2016. Centroidal power diagrams with capacity constraints: Computation, applications, and extension. ACM Trans. Graph. (TOG) 35, 6 (2016), 244:1–244:12.Google ScholarDigital Library
    39. Yin Xu, Ruizhen Hu, Craig Gotsman, and Ligang Liu. 2012. Blue noise sampling of surfaces. Comput. Graph. 36, 4 (2012), 232–240. Google ScholarDigital Library
    40. Yin Xu, Ligang Liu, Craig Gotsman, and Steven J. Gortler. 2011. Capacity-constrained Delaunay triangulation for point distributions. Comput. Graph. 35, 3 (2011), 510–516. Google ScholarDigital Library
    41. Cem Yuksel. 2015. Sample elimination for generating poisson disk sample sets. Comput. Graph. Forum 34, 2 (May 2015), 25–32. DOI:http://dx.doi.org/10.1111/cgf.12538 Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: