While normal ordered dither output can present images with a rectangular-lattice pattern across uniform input pixel value areas, this clustered dot strategy builds patterns that represent uniform intensity areas as various sized diamonds. Modern cultures usually consider this more appealing because they are less sensitive to the natural 45 degree patterns that clustered dot approaches generate. Thus, magazines and newspapers frequently use clustered dot algorithms for their pictures but must use different angles for each colorant. These angles require different shaped cells for each color separation and greatly complicate the processing. Hence, this book only provides a printing example for error diffusion which produces excellent output but is difficult to reproduce.

The VIDEO.C sample program illustrates several clustered dot algorithms as well as several ordered dot algorithms. The cluster patterns build horizontal, vertical, slanted, and diamond patterns. The horizontal pattern is particularly suited to facsimile applications because facsimile compression favors the long runs of zeros and binary ones horizontal clustered dot algorithms produce.

Printer Lines Per Inch

Ordered dither algorithms process groups of scan lines together. Suppose a printer has a 300 dpi resolution. If an algorithm processes four scan lines together to produce tiled ordered dither output, then its corresponding output is 300/4, or 75 lines per inch. Similarly, processing six lines together produces 50 lines per inch.

Processing more lines together provides more intensity levels since more input pixels are included in each tile. However, output images begin to present unappealing-appearing textures—coarse and grainy—if too many lines are processed together. Hence, to minimize such visual distractions, collectively called artifacts, ordered dither algorithms provide tradeoffs between output resolution and intensity levels.

While ordered dot dithers compute output values based on thresholds and ignore errors that occur when input values do not equal output values, error diffusion algorithms incorporate error considerations in subsequent calculations.

Error Diffusion Dither

To understand error diffusion, first consider images produced by threshold algorithms. With threshold algorithms, every pixel output value is determined by comparing the pixel’s input value to some constant value. If the input value is above the threshold, the pixel output value is set to the maximum value; otherwise it is set to zero. Resulting errors are ignored. The VIDEO.C sample program illustrates two images produced from the same input image using two different respective threshold values. The images are unattractive because they provide draconian contrast and massive contouring as a consequence of the pixel rendering algorithm generating and ignoring significant assignment errors.

Like threshold algorithms, error diffusion dithering also uses a constant threshold to compute pixel-by-pixel output values and generates rendering errors during its assignment operations. Sometimes error diffusion algorithms assign zero output values to input pixels with values greater than zero. Other times the algorithms assign maximum output values to input pixels having less than the maximum input value. However, unlike threshold algorithms, error diffusion algorithms calculate the generated error and distribute varying fractions of it to surrounding image pixels whose output values have not yet been calculated. The particular way the error is distributed determines the particular error diffusion algorithm.

In 1975, Robert W. Floyd and Louis Steinberg published their milestone paper titled An Adaptive Algorithm for Spatial Gray Scale in the Society for Information Display 1975 Symposium Digest of Technical Papers. This landmark paper introduced the first error diffusion algorithm, referred to in the literature as Floyd Steinberg error diffusion. To understand the Floyd Steinberg algorithm, consider the following 8-bit image sample fragment:

For the algorithm, select a constant value such as a mid-intensity value of 127. In this image fragment, each intensity value will now be raised to a maximum 255 value or reduced to a minimum zero value depending on whether the pixel’s value plus its accumulated error is greater than or less than the constant selected.