Halftoning Methods

The most common halftoning methods in current use may be categorized as classical screening, dithering with blue noise, direct binary search, and error diffusion. Halftoning methods from all four categories may be found in modern desktop printers. Of these halftoning approaches, error diffusion is the particular focus of this research group. Error diffusion is particular interesting to analyze because it involves a non-separable infinite impulse response filter in addition to the nonlinearity introduced by the severe quantization.

Classical screening, which is the oldest halftoning method in printing, applies a periodic mask of thresholds to each color of the multi-bit image. Pixels can converted to zero (black) if they are below the threshold or one (white) otherwise. With the continuous-tone (high-resolution) images taking pixel values from 0 to 1 inclusive, a mask of M pixels has thresholds 0, 1/M, 2/M, ..., 1, which supports M + 1 intensity levels. The ordering of the thresholds in the mask has a significant effect on the visual quality of the halftone. At mid-gray, half of the pixels in the mask would be turned on, and half would be turned off. A cluster dot screen would cluster the dots in a connected way, which helps mitigate ink spread when printed. A dispersed dot screen would spread out the dots, which is well suited for low-cost displays.

To a very rough approximation as a linear spatially-invariant system, the human visual system is lowpass. With respect to noise in still images, the human visual system is in general less sensitive to uncorrelated high-frequency noise than uncorrelated low-frequency noise. Dithering with blue noise (i.e. high-frequency noise) attempts to place the quantization noise from the halftoning process into the higher frequencies. Noise shaping is a characteristic of error diffusion as described below, but large periodic masks of thresholds (e.g. 128 x 128 pixels) can be designed to produce halftones with blue noise.

Direct binary search is an iterative method to refine a halftone to improve visual quality.' Direct binary search toggles pixels and swaps pixels among neighboring pixels to minimize a distortion measure, such as a weighted mean square error, between the halftone and the original image. The weighting is generally based on a linear spatially-invariant model of the human visual system. Direct binary search may require thousands of passes over the halftone, and its convergence is dependent on the initial starting point. However, this method produces the best grayscale halftones to date. Related to direct binary search are iterative methods for designing stochastic screens.

Error diffusion was introduced in 1976 by Floyd and Steinberg. Error diffusion produces halftones of much higher quality than classical screening, with the tradeoff of requiring more computation and memory. Screening amounts to pixel-based thresholding, whereas error diffusion requires a neighborhood operation and thresholding. The neighborhood operation distributes the quantization error due to thresholding to the unhalftoned neighbors of the current pixel. The term "error diffusion" refers to the process of diffusing the quantization error along the path of the image scan. In the case of a raster scan, the quantization error diffuses across and down the image. "Qualitatively speaking, error diffusion accurately reproduces the graylevel in a local region by driving the average error to zero through the use of feedback" [Kite, Dissertation, 1998].

These halftone methods may be classified into three categories--- amplitude modulation (AM), frequency modulation (FM) and AM-FM hybrid halftoning. In AM halftoning, the dot size is varied depending on the graylevel value of the underlying grayscale image while the dot frequency is held constant, e.g. clustered-dot ordered dither. FM halftones have a fixed dot size and shape, but the frequency of the dots varies with the graylevel of the underlying grayscale image. Conventional digital FM halftones have a fixed dot size of one pixel, e.g. those produced by dispersed-dot ordered dither and error diffusion. AM-FM halftones have variable dot shape/size, and variable dot frequency that depends on the graylevel value to be reproduced. Examples of AM-FM halftones include "green-noise" halftones by Levien, halftones on space filling curves, and halftones with texture control.

Mail comments about this page to bevans@ece.utexas.edu.