Weighted Linde–Buzo–Gray Stippling


.

ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2017) 

Oliver Deussen *1,2             Marc Spicker *1            Qian Zheng 1,3

University of Konstanz 1          SIAT Shenzhen 2          Shenzhen University 3

Joint First Authors

Fig. 1. Starting from a single random point, our dynamic illustration method creates high-quality stipple drawings with a small number of iterations (left to right: 12, 14, and 18 iterations). In the example shown above we end up with 36k points of constant size.


More examples can be found in another project website. Click Here


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.


Algorithm 

Fig. 2. LBG-Stippling of a greyscale ramp (see also Figure 6) with color-coded size error in each cell: (a) initial point distribution with Voronoi cells. On the left, only some points are needed, thus cells are too small (blue) and will be merged (points will be deleted); on the right, many points are needed, thus cells are too large (red) and therefore will be split (new positions of points in green); (b) set after two iterations; (c) set after six iterations.



Results

Fig. 3. Different point diameters used to represent an input image, creating different numbers of points and levels of abstraction: (a) 56k points (size 2), (b) 14k points (size 4), and (c) 6.3k points (size 6). Input image courtesy of P. Debevec.


Fig. 4. Point sizes in relation to other constraints: (a) radial increase from the eye of the model (original image by Bùi Linh Ngan, Flickr). In (b) the beak of the duck is rendered with points enlarged depending on their distance to the viewer.


Fig. 5. Adaptive sampling of a height function and a geometric model with density defined by the color coded mean curvature: (a),(b) about 600 adaptively sampled points; (c) 5k adaptive points on the Stanford bunny; (d) remeshed result of (c).


Acknowledgments

The authors would like to thank the German Research Foundation (DFG) for financial support within project A04 of SFB/Transregio 161. We also want to thank the Guangdong Science and Technology Program (2015A030312015), Leading Talents of Guangdong Program (00201509), Shenzhen Innovation Program (JCYJ20151015151249564), and Natural Science Foundation of SZU (827-000196).


Bibtex

@article{WeightedLBG-2017,
     title = {Weighted Linde–Buzo–Gray Stippling},
     author = {Oliver Deussen and Marc Spicker and Qian Zheng},
     journal = {ACM Transactions on Graphics (Proc. SIGGRAPH Asia)},
     volume = {36},
     number = {6},
     year = {2017},
     pages = {233:1--12},   
Copyright © 2016-2018 Visual Computing Research Center