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

research-article

Blue noise through optimal transport

Authors:

Fernando de Goes,

Katherine Breeden,

Victor Ostromoukhov,

Mathieu DesbrunAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 31, Issue 6

Article No.: 171, Pages 1 - 11

https://doi.org/10.1145/2366145.2366190

Published: 01 November 2012 Publication History

Abstract

We present a fast, scalable algorithm to generate high-quality blue noise point distributions of arbitrary density functions. At its core is a novel formulation of the recently-introduced concept of capacity-constrained Voronoi tessellation as an optimal transport problem. This insight leads to a continuous formulation able to enforce the capacity constraints exactly, unlike previous work. We exploit the variational nature of this formulation to design an efficient optimization technique of point distributions via constrained minimization in the space of power diagrams. Our mathematical, algorithmic, and practical contributions lead to high-quality blue noise point sets with improved spectral and spatial properties.

Supplementary Material

ZIP File (171-163-0030.zip)

Supplemental Materials for

Download
11.37 MB

References

[1]

Aurenhammer, F., Hoffmann, F., and Aronov, B. 1998. Minkowski-type theorems and least-squares clustering. Algorithmica 20, 1, 61--76.

[2]

Balzer, M., and Heck, D. 2008. Capacity-constrained Voronoi diagrams in finite spaces. In Int. Symp. on Voronoi Diag., 44--56.

Digital Library

[3]

Balzer, M., Deussen, O., and Lewerentz, C. 2005. Voronoi treemaps for the visualization of software metrics. In Symp. on Software Visualization, ACM, 165--172.

Digital Library

[4]

Balzer, M., Schlömer, T., and Deussen, O. 2009. Capacity-constrained point distributions: A variant of Lloyd's method. ACM Trans. Graph. (SIGGRAPH) 28, 3, 86:1--8.

Digital Library

[5]

Balzer, M. 2009. Capacity-constrained Voronoi diagrams in continuous spaces. In Int. Symp. on Voronoi Diagrams, 79--88.

Digital Library

[6]

Bonneel, N., van de Panne, M., Paris, S., and Heidrich, W. 2011. Displacement interpolation using Lagrangian mass transport. ACM Trans. Graph. (SIGGRAPH ASIA) 30, 6.

Digital Library

[7]

Bowers, J., Wang, R., Wei, L.-Y., and Maletz, D. 2010. Parallel Poisson disk sampling with spectrum analysis on surfaces. ACM Trans. Graph. 29 (Dec.), 166:1--166:10.

Digital Library

[8]

Bridson, R. 2007. Fast Poisson disk sampling in arbitrary dimensions. In ACM SIGGRAPH sketches.

Digital Library

[9]

CGAL, 2010. Computational Geometry Algorithms Library (release 3.8). http://www.cgal.org.

[10]

Chen, Z., Yuan, Z., Choi, Y.-K., Liu, L., and Wang, W. 2012. Variational blue noise sampling. IEEE Trans. Vis. Comput. Graphics 18, 10, 1784--1796.

Digital Library

[11]

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

Digital Library

[12]

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

Digital Library

[13]

Crow, F. C. 1977. The aliasing problem in computer-generated shaded images. Commun. ACM 20, 11, 799--805.

Digital Library

[14]

Davis, T. A. 2011. Algorithm 915, SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization. ACM Trans. Math. Softw. 38 (Dec.), 8:1--8:22.

Digital Library

[15]

de Goes, F., Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2011. An optimal transport approach to robust reconstruction and simplification of 2d shapes. Computer Graphics Forum 30, 5, 1593--1602.

[16]

Deussen, O., Hiller, S., Overveld, C., and Strothotte, T. 2000. Floating points: A method for computing stipple drawings. Computer Graphics Forum (EG'00) 19, 3, 40--51.

[17]

Dippé, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. In ACM SIGGRAPH, 69--78.

Digital Library

[18]

Du, Q., Faber, V., and Gunzburger, M. 1999. Centroidal Voronoi Tessellations: Applications and algorithms. SIAM Rev. 41 (Dec.), 637--676.

Digital Library

[19]

Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast Poisson-disk sample generation. ACM Trans. Graph. 25, 3 (July), 503--508.

Digital Library

[20]

Ebeida, M. S., Davidson, A. A., Patney, A., Knupp, P. M., Mitchell, S. A., and Owens, J. D. 2011. Efficient maximal Poisson-disk sampling. ACM Trans. Graph. 30 (Aug.), 49:1--49:12.

Digital Library

[21]

Fattal, R. 2011. Blue-noise point sampling using kernel density model. ACM Trans. Graph. (SIGGRAPH) 30, 3, 48:1--48:12.

Digital Library

[22]

Floyd, R. W., and Steinberg, L. 1976. An adaptive algorithm for spatial grey scale. Proc. Soc. Inf. Display 17, 75--77.

[23]

Gamito, M. N., and Maddock, S. C. 2009. Accurate multidimensional Poisson-disk sampling. ACM Trans. Graph. 29, 8:1--8:19.

Digital Library

[24]

Jones, T. R. 2006. Efficient generation of Poisson-disk sampling patterns. Journal of Graphics, GPU, & Game Tools 11, 2, 27--36.

[25]

Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive Wang tiles for real-time blue noise. ACM Trans. Graph. 25, 3, 509--518.

Digital Library

[26]

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

[27]

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

[28]

Lecot, G., and Lévy, B. 2006. ARDECO: Automatic Region DEtection and COnversion. In EG Symp. on Rendering, 349--360.

Digital Library

[29]

Lemieux, C. 2009. Monte Carlo and Quasi Monte Carlo Sampling. Springer.

[30]

Li, H., Nehab, D., Wei, L.-Y., Sander, P., and Fu, C.-W. 2010. Fast capacity constrained Voronoi tessellation. In Symp. on Interactive 3D Graphics & Games, 13:1--13:4.

Digital Library

[31]

Li, H., Wei, L.-Y., Sander, P. V., and Fu, C.-W. 2010. Anisotropic blue noise sampling. ACM Trans. Graph. (SIGGRAPH Asia) 29 (Dec.), 167:1--167:12.

Digital Library

[32]

Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D., Lu, L., and Yang, C. 2009. On Centroidal Voronoi Tessellation - energy smoothness and fast computation. ACM Trans. Graph. 28, 4.

Digital Library

[33]

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

Digital Library

[34]

Lucarini, V. 2009. Symmetry-break in Voronoi tessellations. Symmetry 1, 1, 21--54.

[35]

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

Digital Library

[36]

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

Digital Library

[37]

Mullen, P., Memari, P., de Goes, F., and Desbrun, M. 2011. HOT: Hodge Optimized Triangulations. ACM Trans. Graph. (SIGGRAPH) 30, 3.

Digital Library

[38]

Niederreiter, H. 1992. Random Number Generation and Quasi-Monte-Carlo Methods. SIAM.

Digital Library

[39]

Nocedal, J., and Wright, S. J. 1999. Numerical optimization. Springer Verlag.

[40]

Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Trans. Graph. 23, 3, 488--495.

Digital Library

[41]

Ostromoukhov, V. 2007. Sampling with polyominoes. ACM Trans. Graph. 26, 3, 78:1--78:6.

Digital Library

[42]

Schlömer, T., and Deussen, O. 2011. Accurate spectral analysis of two-dimensional point sets. Journal of Graphics, GPU, and Game Tools 15, 3, 152--160.

[43]

Schlömer, T., Heck, D., and Deussen, O. 2011. Farthest-point optimized point sets with maximized minimum distance. In Symp. on High Performance Graphics, 135--142.

Digital Library

[44]

Schmaltz, C., Gwosdek, P., Bruhn, A., and Weickert, J. 2010. Electrostatic halftoning. Comput. Graph. Forum 29, 8, 2313--2327.

[45]

Secord, A. 2002. Weighted Voronoi stippling. In Symp. on Non-Photorealistic Animation and Rendering, 37--43.

Digital Library

[46]

Ulichney, R. 1987. Digital Halftoning. MIT Press.

Digital Library

[47]

Villani, C. 2009. Optimal Transport: Old and New. Fundamental Principles of Mathematical Sciences, 338. Springer-Verlag.

[48]

Wei, L.-Y., and Wang, R. 2011. Differential domain analysis for non-uniform sampling. ACM Trans. Graph. 30 (Aug.), 50:1--50:10.

Digital Library

[49]

Wei, L.-Y. 2008. Parallel Poisson disk sampling. ACM Trans. Graph. (SIGGRAPH) 27 (August), 20:1--20:9.

Digital Library

[50]

Wei, L.-Y. 2010. Multi-class blue noise sampling. ACM Trans. Graph. (SIGGRAPH) 29 (July), 79:1--79:8.

Digital Library

[51]

Xiang, Y., Xin, S.-Q., Sun, Q., and He, Y. 2011. Parallel and accurate Poisson disk sampling on arbitrary surfaces. In SIGGRAPH Asia Sketches, 18:1--18:2.

Digital Library

[52]

Xu, Y., Liu, L., Gotsman, C., and Gortler, S. J. 2011. Capacity-constrained Delaunay triangulation for point distributions. Comput. Graph. 35, 510--516.

Digital Library

[53]

Xu, Y., Hu, R., Gotsman, C., and Liu, L. 2012. Blue noise sampling of surfaces. Comput. Graph. 36, 232--240.

Digital Library

[54]

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

[55]

Zhou, Y., Huang, H., Wei, L.-Y., and Wang, R. 2012. Point sampling with general noise spectrum. ACM Trans. Graph. (SIGGRAPH) 31, 4, 76:1--76:11.

Digital Library

Cited By

Sadhu RGoldfeld ZKato K(2024)Stability and statistical inference for semidiscrete optimal transport mapsThe Annals of Applied Probability10.1214/24-AAP210434:6Online publication date: 1-Dec-2024
https://doi.org/10.1214/24-AAP2104
Doignies BCoeurjolly DBonneel NDigne JIehl JOstromoukhov V(2024)Differentiable Owen ScramblingACM Transactions on Graphics10.1145/368776443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687764
Xu RLiu LWang NChen SXin SGuo XZhong ZKomura TWang WTu C(2024)CWF: Consolidating Weak Features in High-quality Mesh SimplificationACM Transactions on Graphics10.1145/365815943:4(1-14)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658159
Show More Cited By

Index Terms

Blue noise through optimal transport
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition

Recommendations

Multi-class blue noise sampling

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 ...
Capacity constrained blue-noise sampling on surfaces

We present a novel method for high-quality blue-noise sampling on mesh surfaces with prescribed cell-sizes for the underlying tessellation (capacity constraint). Unlike the previous surface sampling approach that only uses capacity constraints as a ...
Color filter array design using random patterns with blue noise chromatic spectra

We propose two new types of random patterns with R, G, B colors, which allow to design color filter arrays (CFAs) with good spectral properties. Indeed, the chrominance channels have blue noise characteristics, a property which maximizes the robustness ...

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 31, Issue 6

November 2012

794 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2366145

Issue’s Table of Contents

Copyright © 2012 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: 01 November 2012

Published in TOG Volume 31, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

169
Total Citations
View Citations
1,192
Total Downloads

Downloads (Last 12 months)85
Downloads (Last 6 weeks)10

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sadhu RGoldfeld ZKato K(2024)Stability and statistical inference for semidiscrete optimal transport mapsThe Annals of Applied Probability10.1214/24-AAP210434:6Online publication date: 1-Dec-2024
https://doi.org/10.1214/24-AAP2104
Doignies BCoeurjolly DBonneel NDigne JIehl JOstromoukhov V(2024)Differentiable Owen ScramblingACM Transactions on Graphics10.1145/368776443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687764
Xu RLiu LWang NChen SXin SGuo XZhong ZKomura TWang WTu C(2024)CWF: Consolidating Weak Features in High-quality Mesh SimplificationACM Transactions on Graphics10.1145/365815943:4(1-14)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658159
Ostromoukhov VBonneel NCoeurjolly DIehl J(2024)Quad-Optimized Low-Discrepancy SequencesACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657431(1-9)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657431
Xiong ZLi LZhu YZhang X(2024)On the Convergence of Continuous and Discrete Unbalanced Optimal Transport Models for 1-Wasserstein DistanceSIAM Journal on Numerical Analysis10.1137/22M152074862:2(749-774)Online publication date: 5-Mar-2024
https://doi.org/10.1137/22M1520748
Genest BCourty NCoeurjolly D(2024)Non‐Euclidean Sliced Optimal Transport SamplingComputer Graphics Forum10.1111/cgf.1502043:2Online publication date: 30-Apr-2024
https://doi.org/10.1111/cgf.15020
Cammarasana SPatané G(2024)Adaptive Membership Functions and F-TransformIEEE Transactions on Fuzzy Systems10.1109/TFUZZ.2024.336063332:5(2786-2796)Online publication date: May-2024
https://doi.org/10.1109/TFUZZ.2024.3360633
Shih ACasiulis MMartiniani S(2024)Fast generation of spectrally shaped disorderPhysical Review E10.1103/PhysRevE.110.034122110:3Online publication date: 13-Sep-2024
https://doi.org/10.1103/PhysRevE.110.034122
Cui NChen HGuo XZeng YHua ZXiong GYue RLiu J(2024)Self-prompting semantic segmentation of bridge point cloud data using a large computer vision modelAutomation in Construction10.1016/j.autcon.2024.105729167(105729)Online publication date: Nov-2024
https://doi.org/10.1016/j.autcon.2024.105729
Gong WFan X(2024)Image adaptive sampling using reinforcement learningMultimedia Tools and Applications10.1007/s11042-023-15558-983:2(5511-5530)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s11042-023-15558-9
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