More Web Proxy on the site http://driver.im/

research-article

Multi-class blue noise sampling

Author:

Li-Yi WeiAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 29, Issue 4

Article No.: 79, Pages 1 - 8

https://doi.org/10.1145/1778765.1778816

Published: 26 July 2010 Publication History

Abstract

Sampling is a core process for a variety of graphics applications. Among existing sampling methods, blue noise sampling remains popular thanks to its spatial uniformity and absence of aliasing artifacts. However, research so far has been mainly focused on blue noise sampling with a single class of samples. This could be insufficient for common natural as well as man-made phenomena requiring multiple classes of samples, such as object placement, imaging sensors, and stippling patterns.

We extend blue noise sampling to multiple classes where each individual class as well as their unions exhibit blue noise characteristics. We propose two flavors of algorithms to generate such multi-class blue noise samples, one extended from traditional Poisson hard disk sampling for explicit control of sample spacing, and another based on our soft disk sampling for explicit control of sample count. Our algorithms support uniform and adaptive sampling, and are applicable to both discrete and continuous sample space in arbitrary dimensions. We study characteristics of samples generated by our methods, and demonstrate applications in object placement, sensor layout, and color stippling.

Supplementary Material

JPG File (tp061-10.jpg)

Download
11.81 KB

Supplemental material. (079.zip)

The zip file contains the extended paper draft with appendices for extra information.

Download
62.65 MB

MP4 File (tp061-10.mp4)

Download
25.38 MB

References

[1]

Alliez, P., de Verdière, É. C., Devillers, O., and Isenburg, M. 2003. Isotropic surface remeshing. In Shape Modeling International, 49--58.

Digital Library

[2]

Balzer, M., Schlömer, T., and Deussen, O. 2009. Capacity-constrained point distributions: A variant of Lloyd's method. In SIGGRAPH '09, 86:1--8.

Digital Library

[3]

Baqai, F., Lee, J.-H., Agar, A., and Allebach, J. 2005. Digital color halftoning. Signal Processing Magazine, IEEE 22, 1 (Jan.), 87--96.

[4]

Ben Ezra, M., Lin, Z., and Wilburn, B. 2007. Penrose pixels super-resolution in the detector layout domain. In ICCV '07, 1--8.

[5]

Bridson, R. 2007. Fast Poisson disk sampling in arbitrary dimensions. In SIGGRAPH '07 Sketches & Applications.

Digital Library

[6]

Cline, D., Jeschke, S., Razdan, A., White, K., and Wonka, P. 2009. Dart throwing on surfaces. In EGSR '09, 1217--1226.

Digital Library

[7]

Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. In SIGGRAPH '03, 287--294.

Digital Library

[8]

Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1, 51--72.

Digital Library

[9]

Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast Poisson-disk sample generation. In SIGGRAPH '06, 503--508.

Digital Library

[10]

Fu, Y., and Zhou, B. 2008. Direct sampling on surfaces for high quality remeshing. In SPM '08, 115--124.

Digital Library

[11]

Jones, T. R. 2006. Efficient generation of Poisson-disk sampling patterns. journal of graphics tools 11, 2, 27--36.

[12]

Kim, D., Son, M., Lee, Y., Kang, H., and Lee, S. 2008. Feature-guided image stippling. Computer Graphics Forum 27, 4, 1209--1216.

Digital Library

[13]

Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive Wang tiles for real-time blue noise. In SIGGRAPH '06, 509--518.

Digital Library

[14]

Lagae, A., and Dutré, P. 2005. A procedural object distribution function. ACM Trans. Graph. 24, 4, 1442--1461.

Digital Library

[15]

Lagae, A., and Dutré, P. 2006. An alternative for Wang tiles: colored edges versus colored corners. ACM Trans. Graph. 25, 4, 1442--1459.

Digital Library

[16]

Lagae, A., and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 21, 1, 114--129.

[17]

Lloyd, S. 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 2, 129--137.

Digital Library

[18]

McClure, M. 2002. A stochastic cellular automaton for three-coloring penrose tiles. Computers & Graphics 26, 3, 519--524.

[19]

McCool, M., and Fiume, E. 1992. Hierarchical Poisson disk sampling distributions. In Graphics Interface '92, 94--105.

Digital Library

[20]

Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In SIGGRAPH '87, 65--72.

Digital Library

[21]

Mitchell, D. P. 1991. Spectrally optimal sampling for distribution ray tracing. SIGGRAPH Comput. Graph. 25, 4, 157--164.

Digital Library

[22]

Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. In SIGGRAPH '04, 488--495.

Digital Library

[23]

Ostromoukhov, V. 2007. Sampling with polyominoes. In SIGGRAPH '07, 78:1--6.

Digital Library

[24]

Pang, W.-M., Qu, Y., Wong, T.-T., Cohen-Or, D., and Heng, P.-A. 2008. Structure-aware halftoning. In SIGGRAPH '08, 89:1--8.

Digital Library

[25]

Turk, G. 1992. Re-tiling polygonal surfaces. In SIGGRAPH '92, 55--64.

Digital Library

[26]

Wang, M., and Parker, K. 1999. Properties of combined blue noise patterns. ICIP 4, 328--332.

[27]

Wei, L.-Y. 2008. Parallel Poisson disk sampling. In SIGGRAPH '08, 20:1--9.

Digital Library

[28]

White, K., Cline, D., and Egbert, P. 2007. Poisson disk point sets by hierarchical dart throwing. In Symposium on Interactive Ray Tracing, 129--132.

Digital Library

[29]

Yellott, J. I. J. 1983. Spectral consequences of photoreceptor sampling in the rhesus retina. Science 221, 382--385.

Cited By

Giovannangeli LLalanne FGiot RBourqui R(2024)Guaranteed Visibility in Scatterplots with ToleranceIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.332659630:1(792-802)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3326596
Huang XRitschel TSeidel HMemari PSingh G(2023)Patternshop: Editing Point Patterns by Image ManipulationACM Transactions on Graphics10.1145/359241842:4(1-14)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592418
Salaün CGeorgiev ISeidel HSingh G(2022)Scalable Multi-Class Sampling via Filtered Sliced Optimal TransportACM Transactions on Graphics10.1145/3550454.355548441:6(1-14)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555484
Show More Cited By

Index Terms

Multi-class blue noise sampling
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition

Recommendations

Blue-noise dithered sampling
SIGGRAPH '16: ACM SIGGRAPH 2016 Talks

The visual fidelity of a Monte Carlo rendered image depends not only on the magnitude of the pixel estimation error but also on its distribution over the image. To this end, state-of-the-art methods use high-quality stratified sampling patterns, which ...
Multi-class blue noise sampling
SIGGRAPH '10: ACM SIGGRAPH 2010 papers

Sampling is a core process for a variety of graphics applications. Among existing sampling methods, blue noise sampling remains popular thanks to its spatial uniformity and absence of aliasing artifacts. However, research so far has been mainly focused ...
Line segment sampling with blue-noise properties

Line segment sampling has recently been adopted in many rendering algorithms for better handling of a wide range of effects such as motion blur, defocus blur and scattering media. A question naturally raised is how to generate line segment samples with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 29, Issue 4

July 2010

942 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1778765

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 July 2010

Published in TOG Volume 29, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
1,926
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)7

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Giovannangeli LLalanne FGiot RBourqui R(2024)Guaranteed Visibility in Scatterplots with ToleranceIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.332659630:1(792-802)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3326596
Huang XRitschel TSeidel HMemari PSingh G(2023)Patternshop: Editing Point Patterns by Image ManipulationACM Transactions on Graphics10.1145/359241842:4(1-14)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592418
Salaün CGeorgiev ISeidel HSingh G(2022)Scalable Multi-Class Sampling via Filtered Sliced Optimal TransportACM Transactions on Graphics10.1145/3550454.355548441:6(1-14)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555484
Tu PWei LZwicker M(2022)Clustered vector texturesACM Transactions on Graphics10.1145/3528223.353006241:4(1-23)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530062
Li ZShi RLiu YLong SGuo ZJia SZhang J(2022)Dual Space Coupling Model Guided Overlap-Free ScatterplotIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.3209459(1-11)Online publication date: 2022
https://doi.org/10.1109/TVCG.2022.3209459
Quadri GNieves JWiernik BRosen P(2022)Automatic Scatterplot Design Optimization for Clustering IdentificationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.318988329:10(4312-4327)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1109/TVCG.2022.3189883
Nguyen CMartel JWetzstein G(2022)Learning Spatially Varying Pixel Exposures for Motion Deblurring2022 IEEE International Conference on Computational Photography (ICCP)10.1109/ICCP54855.2022.9887786(1-11)Online publication date: 1-Aug-2022
https://doi.org/10.1109/ICCP54855.2022.9887786
Peng YFan XChen RYu ZLiu SChen YZhao YZhou F(2022)Visual abstraction of dynamic network via improved multi-class blue noise samplingFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-021-0609-017:1Online publication date: 8-Aug-2022
https://dl.acm.org/doi/10.1007/s11704-021-0609-0
Ahmed AWonka P(2021)Optimizing dyadic netsACM Transactions on Graphics10.1145/3450626.345988040:4(1-17)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459880
van Onzenoodt CSingh GRopinski TRitschel T(2021)Blue Noise PlotsComputer Graphics Forum10.1111/cgf.14264440:2(425-433)Online publication date: 4-Jun-2021
https://doi.org/10.1111/cgf.142644
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents