ALGORITHM ALLEY
The Gosselink Ditherer
Pieter Gosselink
Pieter is a programmer located in The Netherlands. He can be reached by fax at +31-73-443635.
Introduction
by Bruce Schneier
Dithering is a trick. It's a way to make video output look better than its data. It relies on your eye not being able to see certain things as well as certain other things. Dithering techniques are used with halftoning methods to smooth the edges of a displayed object. Basically, you add some kind of dither intensity to the calculated intensity of various pixels. Sometimes this dither intensity is calculated randomly; sometimes the calculation is based on the coordinate position of the point. Adding dither tends to break up the contours of objects, which improves the overall appearance of a scene.
In this article, Pieter reviews the two basic approaches to dithering--error distribution and ordered dither--then presents a new technique he's developed. For additional information on both techniques, see "Converting Dithered Images Back to Gray Scale," by Allen Stenger (DDJ, November 1992), and "Differential Image Compression," by John Bridges (DDJ, February 1991). Dithering is a cool subject, one not likely to be overcome by technology anytime soon.
With the introduction of full-color pictures and full-motion video on present-day computer displays, it is obvious that video hardware isn't keeping pace with requirements. At least for the time being, there remains a need for fast, high-quality color-dithering algorithms.
Most currently available monitors display 256 colors at a fairly high resolution. To display pictures with a few million colors with these relatively limited resources, some clever algorithms have been suggested, two of which have proven to be very popular.
The first algorithm is "error distribution" (ED), which is almost always implemented in the Floyd-Steinberg variant; see "An Adaptive Algorithm for Spatial Gray Scale," by R. Floyd and L. Steinberg, Proceedings of the International Symposium on Digital Technology, 1975. The second is "ordered dither" (OD), or "Bayer;" see "An Optimum Method for Two-Level Rendition of Continous-Tone Pictures," by B.E. Bayer, Proceedings of the International Conference on Communication, 1973. In this article, I present a new algorithm that is a combinatorial variant of these two algorithms.
Error Distribution versus Ordered Dither
Table 1 compares the ED and OD algorithms on a number of key factors. Colorset, for instance, is a collection of colors which can be displayed simultaneously. Most of the time it is constructed by selecting 256 colors from a larger set. This colorset is used to approximate the colors in the picture. For ED, this set can be chosen arbitrarily from the larger set. This means that the choice of one color has no implications for the choice of the other colors. For OD, the situation is somewhat more complicated. The available bits for a palette entry (eight bits are needed for 256 colors) have to be divided between the three primary colors (red, green, and blue) because the algorithm has to be applied to these colors independently. A common division is three bits for red, three bits for green, and two bits for blue. This takes into account the fact that the eye is more sensitive to changes in red and green than in blue. I call a colorset constructed in this way a "linear colorset."
Most of the time, the output quality of the ED algorithm is higher because it preserves the information better than OD. The error which is made when approximating an RGB value in ED is distributed to the neighboring pixels, whereas with OD this error is preprogrammed in a matrix. The Floyd-Steinberg variant of ED reduces the noise further by distributing the error to several pixels instead of one.
OD is much faster because it makes approximately 1/5 to 1/10 as many calculations per pixel as ED.
ED distributes errors to neighboring pixels, which leads to a picture that is somewhat more blurred. OD instead takes an approximation that is independent of the color of a pixel's neighbors. This may be a less accurate approximation than is possible with ED, but it preserves the contrast better.
Finally, if the RGB value of a pixel changes, the color of that pixel (chosen as an approximation of the RGB value) has to be changed. In ED, this results in recalculating the whole picture, because all the pixels are dependent on each other. In OD, only the color of the matching pixel has to be changed. This presents a great advantage for applications in which pixels locally change color, for example, in full-color bitmap editors and full-motion video. The algorithm presented here, which I call the "Gosselink Dither," combines the positive characteristics of both the ED and OD algorithms.
The Gosselink Dither
To illustrate the Gosselink Dither, I'll use a 4X4 OD matrix (although the algorithm is applicable to matrixes independent of size). For clarity, I've implemented the algorithm in Basic (see Listing One). For speed, however, I've coded the algorithm in assembly. The matrix used for approximating an RGB value consists of 16 colors, the mean value of which more or less corresponds to the original RGB value. The key is that the colors in the matrix are in order of brightness. The darkest color has an index of 0, and the brightest has an index of 15.
A combination of 16 colors approximating an RGB value does not have to be based on a linear colorset. Any combination corresponding to the RGB value that has to be approximated will do.
As soon as a set of 16 colors for a particular RGB value is created, it is sorted on brightness and arranged in a table; this table is used when dithering a picture. With the RGB value used as an address, a combination of 16 colors is selected from the table. The x- and y-coordinates (modulo 4) are used to select 1 of the 16 colors from this combination.
The difference with the original OD is that the palette entry can no longer be calculated from the RGB value, but is looked up in a table.
Because the 16 RGB values are all equal, the calculation of the combination can be of a special form of error distribution. The simple form of error distribution adds the error to the neighboring pixel, but because the RGB values are all equal, there is no blurring. Consequently, the error can be distributed to more RGB values. The logical way to do this is to distribute the error made with the first approximation evenly among the remaining 15 RGB values so they each get 1/15 of the error. This is repeated for the second RGB value but now the error is divided by 14 and distributed to the remaining 14 RGB values, and so on. The error made on the last RGB value is lost, but this would also be the case for ED or Floyd-Steinberg.
Conclusion
One disadvantage of the Gosselink Dither is that the table size can become large. This size depends on the number of bits (c) per primary color, and the size (s) of the OD matrix (equal to 2n for a 2n*2n matrix). There is a functional relationship between these parameters and the number of bits used for creating the palette (p): c<=p+s. By experimenting with different values, I determined the following:
- For large (full screen) pictures, five bits per primary color is necessary; the size of the matrix may vary, but 2X2 should be satisfactory in most cases. For pictures requiring a smooth grading of colors, a 4X4 matrix should be used.
- For small pictures, four bits per primary color should be used. A matrix of 2X2 again is sufficient in most cases. In special cases, the number of bits for red, green, and blue may not be equal.
The calculation of a table of 128 Kbytes is comparable to dithering 128,000 pixels with ED (not counting the sorting of the four colors). An implementation coded in assembly language running on a 36-MHz, ARM3-powered Acorn Archimedes reached 200,000 pixels per second, so the calculation of the table should not really be a problem, considering that this has to be done only once. The quality of the result is almost as good as that of ED, except for pictures with very smooth grades of color, in which the limited number of bits per primary color becomes clear.
In summary, ED compromises on speed, OD compromises on quality, and the Gosselink Dither compromises on memory usage.
Ordered Dither and Error Distribution
With ordered dither, combinations of black and white are used to suggest 16 levels of grey. A matrix containing the numbers 0-15 in a specific order is used to tile the image; see Figure 1. If the greyvalue of a pixel is greater than the value in the matrix, the color white is used; otherwise the color black is used. An image consisting of only half grey is represented by a pattern with an equal number of black and white pixels. The values in the matrix are placed in such an order that annoying, nonrandom patterns are avoided. The size of the matrix can also be 2X2; see Figure 2.
With error distribution, the image is scanned from top-left to bottom-right while dithering a picture. When a color is chosen from the colorset to represent an RGB value, an error is made. The amount of red, green, and blue will not be the requested amount. This error can be added to the RGB value of the next pixel. The color combination of the pixels is a better approximation of the RGB value than the first approximation.
The error can be divided among more neighboring pixels (which have not been scanned yet). This will result in a better image because the noise of the error is more evenly spread. This is what Floyd and Steinberg suggested. They added 3/8 of the error to the right pixel, 3/8 to the below pixel, and 1/4 to the right-below pixel; see Figure 3.
--P.G.
Figure 1 A matrix used to tile an image. Figure 2 A 2X2 matrix. Figure 3 Floyd-Steinberg matrix.
Table 1: Error distribution versus ordered dither.
ED OD
Colorset arbitrary (+) linear (--)
Quality high (+) medium (--)
Speed slow (--) fast (+)
Contrast medium (--) high (+)
Update global (--) local (+)
Listing One
REM Number of bits per primary color
rbits%=5
gbits%=5
bbits%=5
REM The size of the ordered dither matrix
accurate%=4
REM The number of colors in the palette ( <=256)
num_of_colors = 256-1
tot% = (1<<accurate%)-1
tr% = (1<<rbits%)-1
tg% = (1<<gbits%)-1
tb% = (1<<bbits%)-1
max = 4*(tot%+1)
REM Reserve the necessary memory
DIM bytes%(tot%)
DIM red(num_of_colors),green(num_of_colors),blue(num_of_colors)
DIM grey(num_of_colors)
DIM grid%(tot%)
DIM table%(tr%,tb%,tg%,tot%)
REM The indeces in the ordered dither matrix
CASE accurate% OF
WHEN 2:grid%()=0,3,2,1
WHEN 4:grid%()=0,12,3,15,8,4,11,7,2,14,1,13,10,6,9,5
OTHERWISE : PRINT "Invalid size":END
ENDCASE
REM Palette specification
REM The file consist records with the RGB value and the grey value
REM of each palette entry
f%=OPENIN("Palette")
IF f%=0 THEN PRINT "Couldn't open palette file for reading":END
FOR i%=0 TO num_of_colors
INPUT#f%,red(i%),green(i%),blue(i%),grey(i%)
NEXT
CLOSE#f%
FOR ir%=0 TO tr%
fr=ir%/tr%
FOR ig%=0 TO tg%
fg=ig%/tg%
FOR ib%=0 TO tb%
fb=ib%/tb%
sr = fr
sg = fg
sb = fb
FOR i%=0 TO tot%
a=max
FOR j%=0 TO num_of_colors
d = (red(j%)-sr)*(red(j%)-sr)
d += (green(j%)-sg)*(green(j%)-sg)
d += (blue(j%)-sb)*(blue(j%)-sb)
IF d<a THEN a=d:c%=j%
NEXT
bytes%(i%)=c%
IF i%<tot% THEN
f=tot%-i%
sr+=(sr-red(c%))/f
sg+=(sg-green(c%))/f
sb+=(sb-blue(c%))/f
ENDIF
NEXT
FOR i%=0 TO tot%-1
FOR j%=i%+1 TO tot%
IF grey(bytes%(i%))>grey(bytes%(j%)) THEN SWAP bytes%(i%),bytes%(j%)
NEXT
NEXT
FOR i%=0 TO tot%
table%(ir%,ig%,ib%,i%)=bytes%(grid%(i%))
NEXT
NEXT
NEXT
NEXT
a$="RGB"+STR$(rbits%)+STR$(gbits%)+STR$(bbits%)+STR$(accurat e%)
F%= OPENOUT(a$)
IF F%=0 THEN PRINT "Couldn't open table file for writing":END
FOR r%=0 TO tr%
FOR g%=0 TO tg%
FOR b%=0 TO tb%
FOR c% = 0 TO tot%
BPUT#F%,table%(r%,g%,b%,c%)
NEXT
NEXT
NEXT
NEXT
CLOSE#F%
END
Copyright © 1994, Dr. Dobb's Journal
