Weighted linde-buzo-gray stippling

Abstract

We propose an adaptive version of Lloyd's optimization method that distributes points based on Voronoi diagrams. Our inspiration is the Linde-Buzo-Gray-Algorithm in vector quantization, which dynamically splits Voronoi cells until a desired number of representative vectors is reached. We reformulate this algorithm by splitting and merging Voronoi cells based on their size, greyscale level, or variance of an underlying input image. The proposed method automatically adapts to various constraints and, in contrast to previous work, requires no good initial point distribution or prior knowledge about the final number of points. Compared to weighted Voronoi stippling the convergence rate is much higher and the spectral and spatial properties are superior. Further, because points are created based on local operations, coherent stipple animations can be produced. Our method is also able to produce good quality point sets in other fields, such as remeshing of geometry, based on local geometric features such as curvature.

References

1. B. Adams, M. Pauly, R. Keiser, and L. Guibas. 2007. Adaptively Sampled Particle Fluids. In ACM SIGGRAPH 2007 Papers (SIGGRAPH '07). ACM, New York, NY, USA, Article 48.
2. A. G. M. Ahmed, J. Guo, D. M. Yan, J. Y. Franceschi, X. Zhang, and O. Deussen. 2016. A Simple Push-Pull Algorithm for Blue-Noise Sampling. IEEE Transactions on Visualization and Computer Graphics PP, 99 (2016), 1--1.
3. P. Alliez, E. de Verdière, O. Devillers, and M. Isenburg. 2005. Centroidal Voronoi diagrams for isotropic surface remeshing. Graphical Models 67, 3 (2005), 204 -- 231.
4. R. Ando, N. Thürey, and C. Wojtan. 2013. Highly Adaptive Liquid Simulations on Tetrahedral Meshes. ACM Trans. Graph. 32, 4, Article 103 (July 2013), 10 pages.
5. M. Balzer, T. Schlömer, and O. Deussen. 2009. Capacity-constrained Point Distributions: A Variant of Lloyd's Method. ACM Trans. Graph. 28, 3, Article 86 (July 2009), 8 pages.
6. M. Berg, O. Cheong, M. Kreveld, and M. Overmars. 2008. Computational Geometry: Algorithms and Applications (3rd ed.). Springer-Verlag TELOS.
7. Z. Chen, Z. Yuan, Y. K. Choi, L. Liu, and W. Wang. 2012. Variational Blue Noise Sampling. IEEE Transactions on Visualization and Computer Graphics 18, 10 (Oct 2012), 1784--1796.
8. M. Cohen, J. Wallace, and P. Hanrahan. 1993. Radiosity and Realistic Image Synthesis. Academic Press Professional, Inc., San Diego, CA, USA.
9. F. de Goes, K. Breeden, V. Ostromoukhov, and M. Desbrun. 2012. Blue Noise Through Optimal Transport. ACM Trans. Graph. 31, 6, Article 171 (Nov. 2012), 11 pages.
10. O. Deussen, S. Hiller, C. Van Overveld, and T. Strothotte. 2000. Floating Points: A Method for Computing Stipple Drawings. Computer Graphics Forum 19, 3 (2000), 41--50.
11. R. Fattal. 2011. Blue-noise Point Sampling Using Kernel Density Model. ACM Trans. Graph. 30, 4, Article 48 (July 2011), 12 pages.
12. R. W. Floyd and L. Steinberg. 1976. An adaptive algorithm for spatial grey scale. In Proceedings of the Society of Information Display. 75--77.
13. S Fortune. 1986. A Sweepline Algorithm for Voronoi Diagrams. In Proceedings of the Second Annual Symposium on Computational Geometry (SCG '86). ACM, New York, NY, USA, 313--322.
14. A. Hausner. 2001. Simulating Decorative Mosaics. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '01). ACM, New York, NY, USA, 573--580.
15. S. Hiller, H. Hellwig, and O. Deussen. 2003. Beyond Stippling - Methods for Distributing Objects on the Plane. Computer Graphics Forum 22, 3 (2003), 515--522.
16. M. A. Joshi, M. S. Raval, Y. H. Dandawate, K. R. Joshi, and S. P. Metkar. 2014. Image and Video Compression: Fundamentals, Techniques, and Applications. Chapman and Hall/CRC.
17. M. Kass and D. Pesare. 2011. Coherent Noise for Non-photorealistic Rendering. ACM Trans. Graph. 30, 4, Article 30 (July 2011), 6 pages.
18. D. Kim, M. Son, Y. Lee, H. Kang, and S. Lee. 2008. Feature-guided Image Stippling. Computer Graphics Forum 27, 4 (2008), 1209--1216.
19. S. Kim, R. Maciejewski, T. Isenberg, W. Andrews, W. Chen, M. Sousa, and D. Ebert. 2009. Stippling by Example. In Proceedings of the 7th International Symposium on Non-Photorealistic Animation and Rendering (NPAR '09). ACM, New York, NY, USA, 41--50.
20. B. Klingner and J. Shewchuk. 2008. Aggressive tetrahedral mesh improvement. In Proceedings of the 16th international meshing roundtable. Springer, 3--23.
21. H. Li and D. Mould. 2011. Structure-preserving Stippling by Priority-based Error Diffusion. In Proceedings of Graphics Interface 2011 (GI '11). Canadian Human-Computer Communications Society, 127--134. http://dl.acm.org/citation.cfm?id=1992917.1992938
22. Y. Linde, A. Buzo, and R. Gray. 1980. An Algorithm for Vector Quantizer Design. IEEE Transactions on Communications 28, 1 (Jan 1980), 84--95.
23. Y. J. Liu, Z. Chen, and K. Tang. 2011. Construction of Iso-Contours, Bisectors, and Voronoi Diagrams on Triangulated Surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 8 (Aug 2011), 1502--1517.
24. S. Lloyd. 1982. Least Squares Quantization in PCM. IEEE Trans. Inf. Theor. 28, 2 (1982), 129--137.
25. L. Luo, Z. Jiang, H. Lu, D. Wei, K. Linghu, X Zhao, and D. Wu. 2014. Optimisation of Size-controllable Centroidal Voronoi Tessellation for FEM Simulation of Micro Forming Processes. Procedia Engineering 81 (2014), 2409 -- 2414.
26. D. Martín, G. Arroyo, M. Luzón, and T. Isenberg. 2010. Example-based Stippling Using a Scale-dependent Grayscale Process. In Proceedings of the 8th International Symposium on Non-Photorealistic Animation and Rendering (NPAR '10). ACM, New York, NY, USA, 51--61.
27. M. McCool and E. Fiume. 1992. Hierarchical Poisson Disk Sampling Distributions. In Proceedings of the Conference on Graphics Interface '92. Morgan Kaufmann Publishers Inc., 94--105.
28. E. Melvær and M. Reimers. 2012. Geodesic Polar Coordinates on Polygonal Meshes. Computer Graphics Forum 31, 8 (2012), 2423--2435.
29. M. Meyer. 2008. Dynamic Particles for Adaptive Sampling of Implicit Surfaces. Ph.D. Dissertation. University of Utah.
30. D. Mould. 2007. Stipple Placement Using Distance in a Weighted Graph. In Proceedings of the Third Eurographics Conference on Computational Aesthetics in Graphics, Visualization and Imaging (Computational Aesthetics'07). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 45--52.
31. A. Okabe, B. Boots, and K. Sugihara. 1992. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley & Sons.
32. D. Pelleg and A. Moore. 2000. X-means: Extending K-means with Efficient Estimation of the Number of Clusters. In Proceedings of the 17th International Conference on Machine Learning (ICML '00). Morgan Kaufmann Publishers Inc., 727--734.
33. G. Rong and T. Tan. 2006. Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform. In Proceedings of the 2006 Symposium on Interactive 3D Graphics and Games (I3D '06). ACM, New York, NY, USA, 109--116.
34. A. Secord. 2002. Weighted Voronoi Stippling. In Proceedings of the 2nd International Symposium on Non-photorealistic Animation and Rendering (NPAR '02). ACM, New York, NY, USA, 37--43.
35. P. Sloan, J. Hall, J. Hart, and J. Snyder. 2003. Clustered Principal Components for Precomputed Radiance Transfer. ACM Trans. Graph. 22, 3 (July 2003), 382--391.
36. V. Springel. 2010. E pur si muove: Galilean-invariant cosmological hydrodynamical simulations on a moving mesh. Monthly Notices of the Royal Astronomical Society 401, 2 (2010), 791.
37. V. Surazhsky, P. Alliez, and G. Gotsman. 2003. Isotropic Remeshing of Surfaces: a Local Parameterization Approach. Research Report RR-4967. INRIA. https://hal.inria.fr/inria-00071612
38. J. Tournois, C. Wormser, P. Alliez, and M. Desbrun. 2009. Interleaving Delaunay Refinement and Optimization for Practical Isotropic Tetrahedron Mesh Generation. In ACM SIGGRAPH 2009 Papers (SIGGRAPH '09). ACM, New York, NY, USA, Article 75, 9 pages.
39. T. Tsai and Z. Shih. 2006. All-frequency Precomputed Radiance Transfer Using Spherical Radial Basis Functions and Clustered Tensor Approximation. ACM Trans. Graph. 25, 3 (July 2006), 967--976.
40. S. Valette, J. M. Chassery, and R. Prost. 2008. Generic Remeshing of 3D Triangular Meshes with Metric-Dependent Discrete Voronoi Diagrams. IEEE Transactions on Visualization and Computer Graphics 14, 2 (March 2008), 369--381.
41. D. Vanderhaeghe, P. Barla, J. Thollot, and F. Sillion. 2007. Dynamic Point Distribution for Stroke-based Rendering. In Proceedings of the 18th Eurographics Conference on Rendering Techniques (EGSR'07). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 139--146.
42. X. Wang, X. Ying, Y. Liu, S. Xin, W. Wang, X. Gu, W. Mueller-Wittig, and Y. He. 2015. Intrinsic computation of centroidal Voronoi tessellation (CVT) on meshes. Computer-Aided Design 58 (2015), 51 -- 61. Solid and Physical Modeling 2014.
43. S. Xin, B. Lévy, Z. Chen, L. Chu, Y. Yu, C. Tu, and W. Wang. 2016. Centroidal Power Diagrams with Capacity Constraints: Computation, Applications, and Extension. ACM Trans. Graph. 35, 6, Article 244 (Nov. 2016), 12 pages.
44. Y. Xu, L. Liu, C. Gotsman, and S. Gortler. 2011. Capacity-Constrained Delaunay Triangulation for point distributions. Computers & Graphics 35, 3 (2011), 510 -- 516. Shape Modeling International (SMI) Conference 2011.
45. D. Yan, J. Guo, X. Jia, X. Zhang, and P. Wonka. 2014. Blue-Noise Remeshing with Farthest Point Optimization. Computer Graphics Forum 33, 5 (2014), 167--176.
46. D. Yan, B. Lévy, Y. Liu, F. Sun, and W. Wang. 2009. Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram. Computer Graphics Forum 28, 5 (2009), 1445--1454.

Index Terms

• Computing methodologies

  • Computer graphics

    • Image manipulation

      • Image processing

    • Rendering

      • Non-photorealistic rendering