DITHER.DOC
Lee Daniel Crocker [73407,2030]
April 12, 1989
This paper describes some algorithms for what I will call dithering: a
process, also known as halftoning, used to display images on devices less
capable than those that created them.
Numbers in brackets (like this [0]) are references. A list of these
appears at the end of this document.
If you add to this document, please include your name below as a contributor
or as a reference. I would particularly like to see additions to the "Other
Books of Interest" section. Please keep the text in this simple format (no
margins, no pagination, no lines longer that 79 characters, and no non-ASCII
or non-printing characters other than a CR/LF pair at the end of each line)
to ensures that this paper can be read on many different machines.
Original Author:
Lee Crocker I can be reached in the CompuServe Graphics
1380 Jewett Ave Support Forum (GO PICS) with ID # 73407,2030.
Pittsburg, CA 94565 More information on CompuServe can be found
at the end of this document.
Contributors:
Paul Boulay CompuServe ID # 72117,446
Much of my information has come from electronic mail sent by many people
whom I cannot thank by name, but to whom I owe a great debt. I hope that
free and open discussion on public access networks continues to further
progress in this area.
========================================================================
What is Dithering?
Dithering, or halftoning, is the process of rendering an image on a device
capable of displaying fewer colors than are in the image. The number of
different colors in an image or on a device I will call its Color
Resolution. The word "resolution" in this context means "fineness of
detail" in a digitally sampled signal. It is used most often in referring
to Spatial Resolution, which is the sampling rate for a digitized image.
Spatial resolution describes the fineness of the "dots" used to form an
image. Color resolution describes the fineness of color detail available at
each dot. The higher the resolution of a digital sample, the better it can
reproduce high frequency detail. A compact disc, for example, has a
temporal (i.e., time) resolution of 44,000 samples per second, and a dynamic
(i.e., volume) resolution of 16 bits (0..65,535). It can reproduce sounds
with a vast dynamic range (from barely audible to ear-splitting) with great
detail, but it has problems with very high frequency sounds, such as violins
and piccolos.
It is possible to trade one kind of resolution for another. If your display
device has a higher spatial resolution than the image you are trying to
reproduce, it can show the image well even if its color resolution is less.
The method for doing this is what I will call "dithering" and is the subject
of this paper. The other tradeoff, i.e., trading color resolution for
spatial resolution, is called "anti-aliasing" and is not discussed here. It
is used frequently in the television industry because televisions have a
basically infinite color resolution but rather poor spatial resolution.
I emphasize here that dithering is a one-way operation. Once an image is
dithered, although it may look like a good reproduction of the original,
information is permanently lost. Many image processing functions fail on
dithered images. Dithering must be considered only as a way to produce an
image on hardware that would otherwise be incapable of displaying it. The
data representing an image must always be kept in full detail.
========================================================================
Classes of dithering algorithms
The classes of dithering algorithms I discuss here are Random, Pattern,
Ordered, and Error Dispersion. Each of these methods has strengths and
weaknesses; the simple ones are fast, the complex ones are accurate. For a
specific application, it is probably best to try several methods before
deciding on one.
Assume for the following discussion that we are given an image with 256
shades of gray (0=black..255=white) that we are trying to reproduce on a
black and white output device. This assumption is arbitrary, and does not
affect the algorithms--only the ease with which I can describe them. All of
these methods can be used with color images as well, usually by performing
the algorithm separately for each primary. Error Dispersion is different;
it will be described in detail later.
========================================================================
Artifacts
Many of these methods produce "artifacts" in the output. Artifacts are
visible effects produced by digital signal processing and are not part of
the source image. They are unwanted, and I will discuss how to eliminate
them for each of the dithering methods.
A common artifact that you may have seen is called the Moire pattern. If
you draw several lines close together radiating from a single point on a
computer display, you will see what appear to be flower-like patterns
running across the lines. These patterns are not part of the original idea
of lines, but are an illusion produced by the jaggedness of the display.
========================================================================
Random dither
This is the bubblesort of dithering algorithms. It is usually unacceptable
in production, but it is very simple. For each value in the image, generate
a random number 1..256; if it is greater than the image value at that point,
plot the point white, otherwise plot it black. That's it.
This generates a picture with a lot of noise, which looks like TV picture
snow. Though the image produced is very inaccurate and noisy, it is free
from artifacts, unless the algorithm you use to generate the random numbers
produces some of its own.
While random dither adds a lot of high-frequency noise to a picture, it is
useful in reproducing very low-frequency images where the absence of
artifacts is more important than the absence of noise. For example, a whole
screen containing a gradient of all levels from black to white would
actually look best with a random dither.
For efficiency, you can take the random number generator "out of the loop"
by generating a list of random numbers beforehand for use in the dither.
Make sure that the list is larger than the number of pixels in the image or
you may get artifacts from the reuse of numbers. The worst case is where
the size of your list of random numbers is a multiple or near-multiple of
the width of the image; this causes vertical or diagonal lines to appear.
========================================================================
Pattern dither
This is also a simple concept, but much more effective than random dither.
For each possible value in the image, create a pattern of dots that
approximates that value. For instance, a 3-by-3 block of dots can have one
of 512 patterns, but for our purposes, there are only 10; the number of
black dots in the pattern determines the darkness of the pattern.
Which 10 patterns do we choose? Obviously, we need the all-white and all-
black patterns. We can eliminate those patterns which would create vertical
or horizontal lines if repeated over a large area because many images have
such areas [1]. It has been shown [1] that patterns for adjacent colors
should be similar to reduce an artifact called "contouring", or visible
edges between regions of adjacent values. One easy way to assure this is to
make each pattern a superset of the previous one. Here are two good sets of
patterns for a 3-by-3 matrix:
--- --- --- -X- -XX -XX -XX -XX XXX XXX
--- -X- -XX -XX -XX -XX XXX XXX XXX XXX
--- --- --- --- --- -X- -X- XX- XX- XXX
and
--- X-- X-- X-- X-X X-X X-X XXX XXX XXX
--- --- --- --X --X X-X X-X X-X XXX XXX
--- --- -X- -X- -X- -X- XX- XX- XX- XXX
The first set of patterns above is "clustered" in that as new dots are added
to each pattern, they are added next to dots already there. The second set
is "dispersed" as the dots are spread out more. Dispersed-dot patterns
produce less grainy images, but require that the output device render each
dot distinctly. When this is not the case, as with a printing press which
smears the dots a little, clustered patterns are better.
For each pixel in the image we now print the pattern which is closest to its
value. This will triple the size of the image in each direction, so this
method can only be used where the display spatial resolution is much greater
than that of the image.
We can exploit the fact that most images have large areas of similar value
to reduce our need for extra spatial resolution. Instead of plotting a
whole pattern for each pixel, map each pixel in the image to a dot in the
pattern an only plot the corresponding dot for each pixel. This produces
exactly the same result as the Ordered Dither discussed below, although the
algorithm for the latter is simpler.
To extend this method to color images, we must use patterns of colored dots
to represent shades not directly printable by the hardware. For example, if
your hardware is capable of printing only red, green, blue, and black (the
minimal case for color dithering), other colors can be represented with
patterns of these four:
Yellow = R G Cyan = G B Magenta = R B Gray = R G
G R B G B R B K
(B here represents blue, K is black). There are a total of 31 such distinct
patterns which can be used; I will leave their enumeration "as an exercise
for the reader" (don't you hate books that do that?).
========================================================================
Ordered dither
Because each of the patterns above is a superset of the previous, we can
express the patterns in compact form as the order of dots added:
8 3 4 and 1 7 4
6 1 2 5 8 3
7 5 9 6 2 9
Then we can use the value in the array as a threshhold. If the value of the
pixel (scaled into the 0-9 range) is less than the number in the
corresponding cell of the matrix, plot that pixel black, otherwise, plot it
white. This process is called ordered dither. As before, clustered
patterns should be used for devices which blur dots. In fact, the clustered
pattern ordered dither is the process used by most newspapers, and the word
"halftoning" refers to this method if not otherwise qualified.
Bayer [2] has shown that for matrices of orders which are powers of two
there is an optimal pattern of dispersed dots which results in the pattern
noise being as high-frequency as possible. The pattern for a 2x2 and 4x4
matrices are as follows:
1 3 1 9 3 11 These patterns (and their rotations
4 2 13 5 15 7 and reflections) are optimal for a
4 12 2 10 dispersed-pattern ordered dither.
16 8 14 6
Ulichney [3] shows a recursive technique can be used to generate the larger
patterns. To fully reproduce our 256-level image, we would need to use the
16x16 pattern.
Bayer's method is in very common use and is easily identified by the cross-
hatch pattern artifacts it produces in the resulting display. These
artifacts are the major drawback of the technique which is otherwise very
fast and powerful. Ordered dithering also performs very badly on images
which have already been dithered. As stated earlier, dithering should be
the last stage in producing a physical display from a digitally stored
image. The dithered image itself should never be stored.
========================================================================
Error dispersion
This technique generates the best results of any method here, and is
naturally the slowest. In fact, there are many variants of this technique
as well, and the better they get, the slower they are.
For each point in the image, first find the closest color available.
Calculate the difference between the value in the image and the color you
have. For our monochrome image, this is a single number; for color images,
3 sets of differences will have to be kept. Divide up these errors and
distribute them over the neighboring pixels that you have not yet visited.
There are many ways to distribute the errors and many ways to scan the
image, but I will deal here with only a few. The two basic ways to scan the
image are with a normal left-to-right, top-to-bottom raster, or with an
alternating left-to-right then right-to-left raster. The latter method,
called a "serpentine" raster, generally produces fewer artifacts and can be
used with all the error diffusion patterns discussed below.
The different ways of dividing up the error can be expressed as patterns
(called filters, for reasons too boring to go into here).
X 7 This is the Floyd and Steinberg [4]
3 5 1 error diffusion filter.
In this pattern, the X represents the pixel you are currently scanning, and
the numbers (called weights, for equally boring reasons) represent the
proportion of the error distributed to the pixel in that position. Here,
the pixel immediately to the right gets 7/16 of the error (the weights add
to 16), the pixel directly below gets 5/16 of the error, and the diagonally
adjacent pixels get 3/16 and 1/16. When scanning a line right-to-left, this
pattern is reversed. This pattern was chosen carefully so that it would
produce a checkerboard pattern in areas with intensity of 1/2 (or 128 in our
image). It is also fairly easy to calculate when the division by 16 is
replaced by shifts.
Another filter in common use, but not recommended:
X 3 A simpler filter.
3 2
This is often erroneously called the Floyd-Steinberg filter, but it does not
produce equal results. An serpentine raster scan of the image is necessary
with this filter to reduce artifacts.
Many other filters are used, and each produces slightly different results.
Here are a few, in order of complexity:
X 8 4 The Burkes [5] filter.
2 4 8 4 2
X 5 3 The Sierra [10] filter.
2 4 5 4 2
2 3 2
X 7 5 The Jarvis, Judice, and Ninke [6] filter.
3 5 7 5 3
1 3 5 3 1
X 8 4 The Stucki [7] filter.
2 4 8 4 2
1 2 4 2 1
It is critical with all of these algorithms that when error values are added
to neighboring pixels, the sums must be truncated to fit within the limits
of the hardware, otherwise an area of very intense color may cause streaks
into an adjacent area of less intense color. This truncation adds noise to
the image analagous to clipping in an audio amplifier. It is mainly for
this reason that the larger filters work better--they split the errors up
more finely and produce less of this clipping noise.
With all of these filters, it is also important to ensure that the errors
you distribute add exactly to the original error value. This is easiest to
accomplish by subtracting each fraction from the whole error as it is
calculated, and using the final remainder as the last fraction.
Some of these methods (particularly the simpler ones) can be greatly
improved by skewing the weights with a little randomness [3].
Calculating the "nearest available color" is trivial with a monochrome
image; with color images it requires more work. A table of RGB values of
all available colors must be scanned sequentially for each input pixel to
find the closest. The "distance" formula most often used is a simple
Pythagorean "least squares". The difference for each primary is squared,
and the three squares added to produce the distance value. This value is
equivalent to the square of the distance between the points in RGB-space.
It is not necessary to compute the square root of this value because we are
not interested in the actual distance, only in which is smallest.
When your hardware allows you to select the available colors, very good
results can be achieved by selecting colors from the image itself [8]. At
least one color in the available set must have a lower red value than any in
the image; at least one color must have a higher red value than any in the
image, and so for green and blue as well. The easiest way to ensure this is
to reserve pure black and pure white as the first two colors. It is even
better if you can reserve 8 colors for white, black, red, green, blue, cyan,
magenta, and yellow.
If you do not know the colors in your image ahead of time, or if you are
going to use the same map to dither several different images, you will have
to fill your color map with a good range of colors. This can be done either
by assigning a certain number of bits to each primary and computing all
combinations, or by a smoother distribution as suggested by Heckbert [9].
========================================================================
Sample code
Despite my best efforts in expository writing, nothing explains an algorithm
better than real code. With that in mind, presented here is an algorithm
(in the C programming language) that dithers a 256-level monochrome image
onto a black-and-white display with Bayer's ordered dither, and a program
that dithers a color image onto an 8-color display by error dispersion with
Burkes's filter.
/* Bayer-method ordered dither. The array line[] contains the intensity
** values for the line being processed. As you can see, the ordered
** dither is much simpler than the error dispersion dither. It is also
** many times faster, but it is not as accurate and produces cross-hatch
** patterns on the output.
*/
unsigned char line[WIDTH];
int pattern[8][8] = {
{ 0, 32, 8, 40, 2, 34, 10, 42}, /* 8x8 Bayer ordered dithering */
{48, 16, 56, 24, 50, 18, 58, 26}, /* pattern. Each input pixel */
{12, 44, 4, 36, 14, 46, 6, 38}, /* is scaled to the 0..63 range */
{60, 28, 52, 20, 62, 30, 54, 22}, /* before looking in this table */
{ 3, 35, 11, 43, 1, 33, 9, 41}, /* to determine the action. */
{51, 19, 59, 27, 49, 17, 57, 25},
{15, 47, 7, 39, 13, 45, 5, 37},
{63, 31, 55, 23, 61, 29, 53, 21} };
int getline(); /* Function to read line[] from image */
/* file; must return EOF when done. */
putdot(int x, int y); /* Plot white dot at given x, y. */
dither()
{
int x, y;
while (getline() != EOF) {
for (x=0; x> 2; /* Scale value to 0..63 range */
if (c > pattern[x & 7][y & 7]) putdot(x, y);
}
++y;
}
}
/* Burkes filter error diffusion dithering algorithm in color. The array
** line[][] contains the RGB values for the current line being processed;
** line[0][x] = red, line[1][x] = green, line[2][x] = blue.
*/
unsigned char line[3][WIDTH];
unsigned char colormap[3][COLORS] = {
0, 0, 0, /* Black This color map should be replaced */
255, 0, 0, /* Red by one available on your hardware */
0, 255, 0, /* Green */
0, 0, 255, /* Blue */
255, 255, 0, /* Yellow */
255, 0, 255, /* Magenta */
0, 255, 255, /* Cyan */
255, 255, 255 }; /* White */
int getline(); /* Function to read line[][] from image */
/* file; must return EOF when done. */
putdot(int x, int y, int c); /* Plot dot of given color at given x, y. */
dither()
{
static int ed[3][WIDTH] = {0}; /* Errors distributed down, i.e., */
/* to the next line. */
int x, y, h, c, nc, v, /* Working variables */
e[4], /* Error parts (7/8,1/8,5/8,3/8). */
ef[3]; /* Error distributed forward. */
long dist, sdist; /* Used for least-squares match. */
for (x=0; x 255) v = 255; /* and clip. */
line[c][x] = v;
}
sdist = 255L * 255L * 255L + 1L; /* Compute the color */
for (c=0; c> 1; /* half of v, e[1..4] */
e[1] = (7 * h) >> 3; /* will be filled */
e[2] = h - e[1]; /* with the Floyd and */
h = v - h; /* Steinberg weights. */
e[3] = (5 * h) >> 3;
e[4] = h = e[3];
ef[c] = e[1]; /* Distribute errors. */
if (x < WIDTH-1) ed[c][x+1] = e[2];
if (x == 0) ed[c][x] = e[3]; else ed[c][x] += e[3];
if (x > 0) ed[c][x-1] += e[4];
}
}
++y;
}
}
========================================================================
References
[1] Foley, J. D. and Andries Van Dam (1982)
Fundamentals of Interactive Computer Graphics. Reading, MA: Addison
Wesley.
This is a standard reference for many graphic techniques which has not
declined with age. Highly recommended.
[2] Bayer, B. E. (1973)
"An Optimum Method for Two-Level Rendition of Continuous Tone Pictures,"
IEEE International Conference on Communications, Conference Records, pp
26-11 to 26-15.
A short article proving the optimality of Bayer's pattern in the
dispersed-dot ordered dither.
[3] Ulichney, R. (1987)
Digital Halftoning. Cambridge, MA: The MIT Press.
This is the best book I know of for describing the various black and
white dithering methods. It has clear explanations (a little higher
math may come in handy) and wonderful illustrations. It does not
contain any code, but don't let that keep you from getting this book.
Computer Literacy carries it but is often sold out.
[4] Floyd, R.W. and L. Steinberg (1975)
"An Adaptive Algorithm for Spatial Gray Scale." SID International
Symposium Digest of Technical Papers, vol 1975m, pp 36-37.
Short article in which Floyd and Steinberg introduce their filter.
[5] Daniel Burkes is unpublished, but can be reached at this address:
Daniel Burkes
TerraVision Inc.
2351 College Station Road Suite 563
Athens, GA 30305
or on CompuServe's Graphics Support Forum, ID # 72077,356.
[6] Jarvis, J. F., C. N. Judice, and W. H. Ninke (1976)
"A Survey of Techniques for the Display of Continuous Tone Pictures on
Bilevel Displays." Computer Graphics and Image Processing, vol. 5,
pp. 13-40.
[7] Stucki, P. (1981)
"MECCA - a multiple-error correcting computation algorithm for bilevel
image hardcopy reproduction." Research Report RZ1060, IBM Research
Laboratory, Zurich, Switzerland.
[8] Steven Bennett is unpublished, but can be reached through the Graphics
Support Forum on CompuServe discussed at the end of this paper.
[9] Heckbert, Paul (9182)
"Color Image Quantization for Frame Buffer Display." Computer Graphics
(SIGGRAPH 82), vol. 16, pp. 297-307.
[10] Frankie Sierra is unpublished, but can be reached through Graphics
Support Forum of CompuServe discussed at the end of this paper.
========================================================================
Other works of interest:
Knuth, Donald E. (1987)
"Digital Halftones by Dot Diffusion." ACM Transactions on Graphics, Vol. 6,
No. 4, October 1987, pp 245-273.
Surveys the various methods available for mapping grayscale images to
B&W for high-quality phototypesetting and laser printer reproduction.
Presents an algorithm for smooth dot diffusion. (With 22 references.)
Newman, William M., and Robert F. S. Sproull (1979)
Principles of Interactive Computer Graphics. 2nd edition. New York:
McGraw-Hill.
Similar to Foley and Van Dam in content and scope.
Rogers, David F. (1985)
Procedural Elements for Computer Graphics. New York: McGraw-Hill.
Rogers, David F., and J. A. Adams (1976)
Mathematical Elements for Computer Graphics. New York: McGraw-Hill.
These books are good detailed discussions of producing graphic images
on a computer. Plenty of sample code.
========================================================================
About CompuServe Graphics Support Forum:
CompuServe Information Service is a service of the H&R Block companies
providing computer users with electronic mail, teleconferencing, and many
other telecommunications services. Call 800-848-8199 for more information.
The Graphics Support Forum is dedicated to helping its users get the most out
of their computers' graphics capabilities. It has a small staff and a large
number of "Developers" who create images and software on all types of
machines from Apple IIs to Sun workstations. While on CompuServe, type GO
PICS from any "!" prompt to gain access to the forum.