Stippling with Weighted CVDs

The centroidal Voronoi diagrams in Section 2.1 incorporate the idea of a density function $\rho(x,y)$ which weights the centroid calculation. Regions with higher values of $\rho$ will pack generating points closer than regions with lower values. We can use this directly to generate high-quality stippling images by treating a greyscale image as a discrete two-dimensional function $f(x,y)$ where $x,y\in[0,1]$ and $0 \leq f(x,y) \leq 1$ is the range from a black pixel to a white pixel. Define a density function $\rho(x,y) = 1 - f(x,y)$. We can then stipple a given image by first distributing $n$ points in the image and using algorithm (1). Although any distribution of initial points will eventually converge, it is useful to start with a distribution that approximates the final form. Deussen et. al. [1] use a dithering algorithm, and we use simple rejection sampling to generate an initial distribution.

Results

We expect that at the limit of large numbers of very small stipples, the stipple drawing will approximate the greyscale image. Centroidal Voronoi diagrams produce distributions of points that approximate a blue noise distribution, that is, a random distribution with a constraint on the minimum distance between points. Blue noise distributions are useful because they do not introduce spurious patterns such as lines or grids. They can also approximate a constant tone because of the minimum distance constraint. Blue noise distributions have been used to create very high-quality dither patterns for colour reduction [10]. Figure 3 shows a grey-scale close-up image of some Peperomia leaves with a drawing of 20000 stipples. The fine stippling approximates the tones of the image very well, including the textures inside the leaves.

Figure 3: Close-up of large Peperomia leaves with 20000 stipples of radius 2

Figure 4 shows a different small Peperomia plant, lit from the side, with 20000 stipples. Although the number of stipples per square inch is less than in Figure 3, the large number of stipples still renders a faithful image. In particular, note the hard edges maintained by the stipple drawing. Figure 5 shows the full Peperomia plant from Figure 3 with 20000 stipples.

Figure 4: Small Peperomia plant, lit brightly from the right, with 20000 stipples of radius 1.0

Figure 5: Large Peperomia plant with 20000 stipples of radius 2

However, a more interesting test is to apply the method with low stipple counts. Smaller numbers of stipples mean that we cannot rely upon the eye to fuse the tiny size and spacing of the dots into a continuous tone. Figure 6 shows an image of an artist's mannequin and the stippled version with 1000 stipples. Figure 7 shows a climbing shoe in the same format. Note that both the stipple drawings are quite recognisable, especially in comparison to Figure 8, where the source images have been reduced in resolution until they contain approximately 1000 pixels each³.

Figure 6: Figure with 1000 stipples of radius 5

Figure 7: Climbing shoe with 1000 stipples of radius 5

Figure 8: Source images of Figures 6 and 7 rendered with approximately 1000 pixels instead of stipples

Finally, we note that the most striking drawings come from neither very-high nor very-low numbers of stipples, but medium ranges. Figure 9 shows the climbing shoe of Figure 7 rendered with 5000 stipples. This drawing seems to both reproduce the range of tones from the orignal and have the "feel" of a real stipple drawing. Figure 10 shows a corn plant rendered with 20000 stipples and displaying both coloration on the leaves and sharp boundaries on the edges. We feel that this image begins to live up to the quote by Hodges in [4], page 111, in which he attests to the vibrancy of stippled images: "Like a pointallist painting, the drawing will appear to vibrate slightly."

Figure 9: Climbing shoe with 5000 stipples of radius 3

Figure 10: Corn plant with 20000 stipples of radius 1.5

Parameters and Timings

We computed all the stipple drawings of Section 3 on an Intel Pentium III 1000 MHz machine with 256 Mb of RAM and a NVIDIA GeForce2 MX graphics accelerator. As discussed in Section 2.3, we require the Voronoi regions to have at least an average area of 500 pixels, which forces a virtual resolution of up to 3600 by 3600 pixels for the 20000 stipple drawings. Since we precompute the integrals $P$ and $Q$ from Section 2.2.1 at full virtual resolution, this requires upwards of 100 Mb of memory. The memory requirement could be reduced by an order of magnitude by computing the integrals in tiles in the same way that the Voronoi diagrams are computed, but this did not seem necessary.

The iterations were stopped and the stipple drawing output when the difference in the standard deviation of the area of the Voronoi regions was less than $1\times10^{-4}$. Because the background of the input images was not always pure white, stipples were only output if the input image value at that location was greater than 99% of pure white.

The stippling method is iterative and the choice of stopping criteria is not clear, so exact timings are meaningless. However, on the system used, the stipple drawings with up to 5000 stipples completed in under a minute and the drawings with 40000 stipples complete in about 20 minutes on an otherwise unloaded machine.

Footnotes

... each³

This comparison is not quite fair, as the 1000 pixels are forced to be equally spread across the image whereas the stipples have freedom to move. The point is that the stippling maintains edges and silhouettes even at very low resolutions.