CS 791: Assignment 1 - Weighted Voronoi Stippling

Overview

For this assignment, we were to implement the first three sections of Adrian Secord's Weighted Voronoi Stippling paper, including an extra extention of our choosing. My report is organized as follows:

  • Implementation
  • Extensions
    • Asymmetric stipples
    • Coloured stipples - two variants
  • Results

Implementation

My implementation for this assignment was developed under Windows XP using C++. I used openGL for rendering and the Gtkmm libraries for the user interface. The Cairo graphics library is used to generate PDF files.

The Gtk application framework was based on donated code for CS 488 - specifically for assignment 3.

Interface

A simple user interface was created for the stippling program:

The menus are shown below:

The File menu allows for opening images and. writing results as PDFs.

The Stippling menu sets stippling options:

  • Generate Stipples creates a new stipple distribution.
  • Number of Stipples allows the user to set the number of stipples.
  • Single time step runs a single step of Lloyd's method.
  • Run runs Lloyd's method until it converges or is terminated by the user.
  • Stop manually terminates the stipple algorithm.
  • Stipple by Colour switches to the second variant of the colour stipple extension.
The Rendering menu sets rendering options:
  • Rendering of stipples and voronoi regions can be toggled.
  • Different versions of the image can be displayed or hidden altogether.
  • Stipples can be rendered in different styles.
  • The asymmetric stipple extension can be toggled.
When running Lloyd's algorithm, the screen is rendered after each step, showing the results of the algorithm as it progresses.

Algorithm

When an image is loaded, it is first converted into greyscale. The Gdk Pixbuf object is used to load and store images. RGB values are converted into a grey value using the formula: 0.299R + 0.587G + 0.114B

Stipple Placement

I use a simple variation on rejection sampling to generate the initial stipple placement. First, I scan through each row of pixels in the greyscale version of the image. In each row, I identify every contiguous sequence of pixels with a grey value that is less than about 95% of white. Once all of the non-white portion of the image are found, I generate random samples from within these non-white segments. If a sample falls within 3 pixels of an already existing sample, it is rejected and a new sample is generated in its place. If a sample is rejected 25 times, the last one that is generated is used.

Below are two examples of initial stipple distributions. By identifying white-space in the greyscale image, an initial stipple distribution can be created which avoids putting stipples in those locations, thus better approximating the image.

Lloyd's Method

For each step of Lloyd's method, the voronoi diagram of the stipple points is calculated using openGL. For each point, we draw a cone (generated by glutSolidCone and stored in a display list) with its apex positioned at the stipple location, into the back buffer. Each cone is drawn with a solid colour which is derived from the index of the stipple within the stipple list.

The region of the back buffer that is covered by the source image is read back into memory. This is used to move the stipples to the weighted centroid of their voronoi region, using the greyscale image as the weight function, much as described in Adrian's paper. I don't use any of the calculation speed-up tricks that Adrian uses and my implementation of the algorithm seems to run suitably fast as-is.

Adrian discusses splitting an image into tiles to obtain a higher virtual resulation than that of the video hardware in order to decrease discretization errors in generating the voronoi diagram. I do not implement this as I seem to get reasonable results with a buffer size of up to 800x600 (the resolution of the openGL drawing area in my application) using as many as 20 000 stipples.

Below is an example of the voronoi diagram generated for an image with 1000 stipples after convergence of the algorithm. Note that I render the cones with a height of 64 units so that images with large regions of white-space may not be completely covered by cones. Stipples are also drawn in the image.

Convergence

Adrian terminates his alogirhtm when the standard deviation between the size of the voronoi regions was less than 1x10^-4. I took this to mean the difference in standard deviation on successive iterations of the algorithm. For my implementation, I have used a similar termination criteria: I stop the algorithm when the difference in the standard deviation of the size of the voronoi regions on successive iterations is less than 1/10000 of the larger of the image's width or height.

Rendering

Stipples can be rendered using a fixed size and a gradient colouring (going from green at the top of the image to cyan at the bottom) or black stipples of varying sizes. The gradient stipples were intended for debugging purposes and won't be discussed further.

When rendering black stipples of varying size, the radius of the stipple is determined by the "density" of the image. First, an initial radius is estimated by calculating the radius of a circle that has the same area as the stipple's voronoi region and then taking 90% of this radius. Then, we take the density function of the image, as used in Lloyd's method, summed over the voronoi region and divide this by the total area of the region.

Since the density at each point in the image is 1.0-I(x,y) (where I(x,y) is in the range [0, 1] and represents the greyscale value of the image at pixel (x,y) ) the sum of the density over a region will be in the range [0, area of the region]. When we divide the summed density by the region area we then get a value in the range [0, 1].

This value is then multiplied with the estimated radius to produce the final stipple size which has the result of producing smaller stipples in light areas and larger stipples in dark areas.

Extensions

Two extensions were implemented: asymmetric, oriented stipples and coloured stipples. The extensions are discussed in detail on the extensions page.

Results

The results are viewable on the results page.