A Balanced Dithering Technique
Thiadmer Riemersma
Dithering with just one neighbor doesn't sound very helpful — unless you're clever about how you visit the neighbors.
Dithering is a technique for displaying a color or gray scale that is not available in the display system's palette. A dithering algorithm selects colors from the palette and assigns them to the pixels in a given region such that their average value is close to the desired color or gray scale. Human observers who are far enough from the image will not see the individual pixels, but will perceive their average color. Thus, through dithering, an image can display realistic colors, even with a restricted palette. The biggest costs of dithering are loss of image resolution and extra computation required to do the dithering. In this article, I will present a new algorithm that provides a good balance between the benefits and costs of dithering.
The two most common types of dithering algorithms are ordered dither and error diffusion dither. These are described in more detail in the sidebar, "Ordered Dither and Error Diffusion Dither." You may also wish to consult reference [1]. These algorithms both have their advantages and disadvantages. The advantage of error diffusion dither over ordered dither is that it can choose colors from any color palette. When you reduce a full color image to palette color (e.g., with 256 colors), you will want to create an optimal palette for the image for best quality. The error diffusion dither algorithm can use such a palette, but the ordered dither algorithm can dither only to colors from a special "uniform" palette (see "Ordered Dither and Error Diffusion Dither" sidebar). Ordered dither has the advantage that the dithering of one pixel does not influence the dithering of surrounding pixels; that is, the dither is "localized." This is especially useful when the dithered image is used in an animation sequence.
I will present a novel dithering algorithm, which I call Riemersma dither, that can reduce a gray-scale or color image to any color palette, and that restricts the influence of a dithered pixel to a small surrounding area. Riemersma dither thereby combines the advantages of ordered dither and error diffusion dither. Applications for the new algorithm include image-processing systems using quadtrees and animation file formats that support palette files (especially if those animation file formats use some kind of delta-frame encoding).
Dithering along a Hilbert Curve
The first step towards a dither procedure that combines localized dither and optimized color mapping is to reduce the error diffusion algorithm to its bare essentials. Error diffusion works by compensating for the difference between a source pixel's color (the desired color) and its palette-mapped color as it appears in an output pixel. This compensation is accomplished by distributing the difference among a set of neighboring pixels.
I have reduced this set of neighboring pixels to a single pixel. Normally, the error diffusion algorithm spreads the error (the difference between the source pixel and the mapped pixel) both horizontally and vertically, but if you only have one pixel in which to carry the error, the algorithm implicitly becomes one-dimensional. This one-dimensional nature is relevant because the next step is to align the algorithm to a Hilbert curve. A Hilbert curve is a "space-filling curve." It is a kind of fractal that runs through a square grid and visits every grid point exactly once without intersecting itself. A Hilbert curve that fills a 4x4 grid is shown below.
By applying this unidimensional algorithm to a Hilbert curve, I have obtained a very simple, but effective way to dither a two-dimensional picture. See the sidebar, "The Hilbert Curve," for more information on Hilbert curves. The forwarded error mentioned previously holds the accumulated total of all quantization errors. This accumulated error is added to the value of a pixel prior to quantizing it. For example, when dithering a gray-level image to black and white, every pixel is mapped to either black (level 0) or white (level 255), and the error introduced by this mapping is in the range -127 to +128 for every pixel (this is the quantization error). The single error accumulator is the sum of the quantization errors of all pixels that were quantized so far.
The image in Figure 1 is the well-known "Lena" picture dithered with the Hilbert curve and the error propagation as described above. Although I have simplified the error diffusion algorithm, a change in a pixel near the start of the image may still affect, through the error accumulator, the quantized values of a large number of subsequent pixels.
Limiting Error Propagation
Conventional error diffusion dithering algorithms accumulate the quantization error continuously throughout the entire image. While continuous accumulation simplifies the algorithms, it provides no clear benefit in terms of image quality. It would make more sense to restrict the accumulation of error to a region surrounding the pixel in question. This localization of accumulated error is simple in concept to accomplish. Instead of adding the accumulated error of all previous pixels to the current pixel before quantizing it, you just add the accumulated error of the last, say, 16 pixels. In other words, you keep a list of the quantization errors of a number of recent pixels. At every new pixel to quantize, you add to the pixel value all the quantization errors in the list. Then you quantize the pixel. This creates a new quantization error (for the pixel just quantized). This error is added to the list, while removing the oldest error entry from the list.
There is a pitfall in this scheme. When removing an entry from the quantization error list, you are effectively adding a bias of the negative value of the removed entry to the list. An example will make this clearer. Assume that you keep a list of the four most recent quantization errors. When dithering a gray surface (gray value 128) to black and white, the progression would be as shown in Table 1.
The following will help in interpreting the table:
- The "adjusted pixel" value is the source pixel, plus all values in the "quantization error list."
- The adjusted pixel is mapped to either 0 or 255, whichever is closest. This becomes the "quantized pixel" result.
- The difference between the source pixel and the quantized pixel becomes the new (rightmost) entry in the quantization error list on the next row.
- Gray-level 128 is slightly above the mid-level between 0 and 255. That is why the adjusted pixel is slowly incrementing in the first five rows.
On the sixth line, the leftmost value was dropped from the list. The accumulated error of the list is suddenly 127 higher than what it should have been. Dropping the oldest entry from the root creates a severe error in the dithered result.
In the quantization error list of the above example, all entries have the same weight. The solution to the problem of the "bias" introduced by dropping a value from the list is to give the old entries in the quantization error list a (much) smaller weight than the new entries. As an entry moves down from the top of the list towards the bottom, its weight gradually lowers. In my experience, an exponentially decaying curve works well.
The weight of every list item is:
where i is the position of the item in the list (starting at 0 and ending at list length -1), r is the ratio of the highest weight to the lowest weight, and b is the base value for the exponential curve. b is computed as:
where q represents the length of the list.
The results in Table 2 apply to the same example, but now the four values have a weight attached to them. The oldest entry has the weight of 1/4th of the newest entry.
The resulting dither pattern in Table 2 is what we would expect for the dither pattern for mid-level gray. Note that the quantization error list is much too short to achieve a decent dither quality. I regard an error list of 16 as a minimum. In my own implementation, I have also set the weight ratio of the oldest entry versus the newest entry to 1:16 (instead of to 1:4 as in Table 2).
Example Program
A simple example program in C (Listing 1), which created the dithered "Lena" picture in Figure 1, implements the concepts of this article. It was tested with Borland C++ for DOS in large memory model, but I have tried to avoid non-portable constructs. The bulk of the code deals with the Hilbert curve generation. The implementation of the error propagation is straightforward.
Conclusion
Although this article focuses on dithering to black and white, the same principles apply to the case where intermediate gray levels are available. In a similar vein, the algorithm can be adapted to color images (and restricted color palettes) by keeping three quantization error lists for each of the red, green, and blue channels.
Dithering along a space-filling curve is a relatively new subject of study. I expect that the results of this simple dither can be adjusted and improved, for example:
- by using a different space-filling curve, like Peano or Sierpinsky
- by adjusting the decay speed and the length of the quantization error list
- by substituting the exponential decaying weights by a different curve
Related to dithering are the topics of computing the best color map (creating an optimal palette) and of performing quantization as accurately as possible.
Bibliography
[1] Robert Ulichney. Digital Halftoning (MIT Press, 1987). This book presents an overview and discussion of various dithering and halftoning algorithms. It is becoming somewhat outdated: new error diffusion matrices like Burkes and Sierra are absent from the book, and the research on dithering using space-filling curves is also missing.
[2] Pieter Gosselink. "Gosselink Dither." Dr. Dobb's Journal, December 1994. Gosselink dither combines ordered dither and error diffusion by creating a large set of square tiles, one for each possible color in an RGB cube. Each tile is then dithered using a simplified error diffusion algorithm. The dithered tiles are used as ordered dither matrices, where the RGB indices of each pixel in the original picture select the tile to use. The memory requirements of Gosselink dither are steep.
[3] Douglas Voorhies. "Space-Filling Curves and a Measure Of Coherence." Graphic Gems II, edited by James Arvo (Academic Press, 1991), pp 26-30. This article discusses the coherence level of the Peano and the Hilbert curves. The coherence level is a measure of the compactness of the area occupied by pixels at sequential positions on a space-filling curve. The smaller and more circular shaped that this area is, the higher the coherence between the pixels on the curve.
Thiadmer Riemersma writes software toolkits for computer graphics and animation for his company, CompuPhase, in the Netherlands. Taking an engineering approach to software development, he tries to balance performance, visual quality, and feasibility of the implementation. You may contact Thiadmer via the company homepage at www.compuphase.com.
