Graphics, Imaging, and Games Lab

Following up on my previous post. I am pleased to provide some stippling results from a debugged implementation.

Varying stippling parameters

Using the notation from the article, the following images were produced with parameter values of (G_-, G₊, k, D) equal to:

• (5, 3, 0, 7)
• (5, 5, 0, 7)
• (5, 5, 0, 15)
• (5, 5, 0.2, 15)

The original image is from the Qt SVG viewer example.

Of course, many more images would be necessary to illustrate the effects of each individual parameter more clearly. Instead, I will state my observations from additional experimentation not shown in the images above:

• Increasing G_- reduces the number of stipples in bright areas
• Increasing G₊ reduces the number of stipples in dark areas
• Increasing k decreases the number of stipples, primarily in areas that get processed later
• Increasing D reduces the number of stipples, presumably by improving the quality of error diffusion (Less error is lost from pixel intensity saturation)

These effects are expected based on the descriptions of the parameters in the article.

Performance

The "release build" of the application processes approximately 58000 pixels per second, as tested on a 4320 x 3240 image. This performance metric includes the time taken for converting the image to greyscale, but excludes the time taken to render the list of stipples to the output image.

Explanation for earlier results

Debugging the visibly defective results shown in the previous post proved to be extremely difficult. Eventually, I was able to identify two problems:

Incorrect error diffusion

Pixels with the maximum or minimum possible brightness values would have weights of zero, according to Equation 3 in the article. Consequently, for images with large areas of extreme white or black, normalization (Equation 5) would produce NaN values. The NaN values would then become the new pixel intensities, propagating the problem to many more pixels.

I resolved this issue by aborting the error diffusion process at a given pixel if all neighbours of the pixel have weights of zero.

Memory management

For some reason still unknown, the priority queue of pixels was overwritten by other objects. In particular, I found that a QVector object used to store the neighbours of the current pixel would overwrite the heap data for the zeroeth pixel in the image when the vector reallocated its internal storage.

I suspected that the allocator used by the Boost binomial heap may not have coordinated with that used by Qt classes. However, I could not find adequate documentation or examples to teach myself how to ensure the two systems were using a single memory manager.

Eventually, I developed my own heap implementation based on Pat Morin's BinaryHeap class from his Open Data Structures textbook. (I added increase-key and decrease-key functionality to the existing code.) I also removed all usages of QVector from the stippling algorithm implementation.

The problem is no longer evident, fortunately, but I do not know why.

As an aside, I developed a feature allowing for a visualization of the order in which pixels are processed. The following image depicts, in shades from black to white, pixels which were processed earlier and later, respectively. Note the speckled appearance of the image, which results from changes in pixel priority during error diffusion: