Raster Algorithms - Computer Graphics and Geometric Modeling - page 47

2.7 Halftoning, Thresholding, and Dithering

In contrast to antialiasing where we use multiple intensity levels to increase the
resolution, halftoning (or patterning ) is a technique for obtaining increased visual
resolution with a minimum number of intensity levels. Basically, rectangular grids of
pixels are treated as single pixels. This is how photographs are usually reproduced for
magazines and topics. For example, using a 2 ¥ 2 grid we can get five different inten-
sities. See Figure 2.15(a). Not all of the possible combinations are used (basically sym-
metric patterns are to be avoided) in order not to introduce unwanted patterns into
the picture. Using the patterns in Figure 2.15(b) could easily introduce unwanted hor-
izontal or vertical lines in a picture. Normally 2 ¥ 2 or 3 ¥ 3 grids are used.
Halftoning reduces the overall spatial resolution of a system. For example, the
resolution of a 1024 ¥ 1024 monitor would be reduced to 512 ¥ 512 with 2 ¥ 2 grids.
This means that such a technique is best applied when the resolution of the original
scene is less than that of the output device.
Another technique called thresholding deals with the problem where we have a
digital image with the same resolution as our monochrome display device but with
more intensity levels. The simplest form of thresholding is to use a fixed threshold for
each pixel. If the intensity exceeds that value, the pixel is drawn white, otherwise it
is drawn black. Such a simple scheme can lose a lot of detail. A more refined algo-
rithm of this type is due to Floyd and Steinberg. See [Roge98].
Finally, dithering is a technique applying to monochrome displays that is used with
halftoning or thresholding methods to smooth edges of objects by introducing random
noise into the picture. It increases the visual resolution without reducing the spatial
resolution. One adds a random error to each pixel value before comparing to the
threshold value (if any has been selected). Good error patterns have to be chosen care-
fully. Ordered dithering is where a square dither matrix is added to the picture. Alter-
natively, rather than adding noise using the same threshold for each pixel one can
vary the threshold. With this approach, an optimum 2 ¥ 2 matrix has been shown to
be

02
31

Ê
Ë

ˆ
¯ .

The entries of the matrix are used as the threshold for the corresponding pixel. There
are recursive formulas for higher dimensional dither matrices. See [Roge98].

Figure 2.15. Halftone patterns.