An illustration of dithering. Red and blue are the only colors used, but as the pixels become smaller, the patch appears magenta.

Dithering is a technique used in computer graphics to create the illusion of color depth in images with a limited color palette (quantization). In a dithered image, colors not available in the palette are approximated by a diffusion of colored pixels from within the available palette. The human eye perceives the diffusion as a mixture of the colors within it. Dithering is analogous to the halftone technique used in printing. Dithered images, particularly those with relatively few colors, can often be distinguished by a characteristic graininess, or speckled appearance.

Dithering examples

Figure 1. Original photo; note the smoothness in the detail.

Figure 2. Original image using the web-safe color palette with no dithering applied. Note the large flat areas and loss of detail.

Figure 3. Original image using the web-safe color palette with Floyd-Steinberg dithering. Note that even though the same palette is used, the application of dithering gives a better representation of the original.

Figure 4. Here, the original has been reduced to a 256-color optimized palette with Floyd-Steinberg dithering applied. The use of an optimized palette, rather than a fixed palette, allows the result to better represent the colors in the original image.

Figure 5. Depth is reduced to a 16-color optimized palette in this image, with no dithering. Colors appear muted, and color banding is pronounced.

Figure 6. This image also uses the 16-color optimized palette, but the use of dithering helps to reduce banding.

Reducing the color depth of an image can often have significant visual side-effects. If the original image is a photograph, it is likely to have thousands, or even millions of distinct colors. The process of constraining the available colors to a specific color palette effectively throws away a certain amount of color information.

A number of factors can affect the resulting quality of a color-reduced image. Perhaps most significant is the color palette that will be used in the reduced image. For example, an original image (Figure 1) may be reduced to the 216-color "web-safe" color palette. If the original pixel colors are simply translated into the closest available color from the palette, no dithering occurs (Figure 2). Typically, this approach results in flat areas and a loss of detail, and may produce patches of color that are significantly different from the original. Shaded or gradient areas may appear as color bands, which may be distracting. The application of dithering can help to minimize such visual artifacts, and usually results in a better representation of the original (Figure 3). Dithering helps to reduce color banding and flatness.

One of the problems associated with using a fixed color palette is that many of the needed colors may not be available in the palette, and many of the available colors may not be needed; a fixed palette containing mostly shades of green would not be well-suited for images that do not contain many shades of green, for instance. The use of an optimized color palette can be of benefit in such cases. An optimized color palette is one in which the available colors are chosen based on how frequently they are used in the original source image. If the image is reduced based on an optimized palette, the result is often much closer to the original (Figure 4).

The number of colors available in the palette is also a contributing factor. If, for example, the palette is limited to only 16 colors, the resulting image could suffer from additional loss of detail, and even more pronounced problems with flatness and color banding (Figure 5). Once again, dithering can help to minimize such artifacts (Figure 6).

Applications

Display hardware, including early computer video adapters and many modern LCDs used in mobile phones and inexpensive digital cameras, are capable of showing a smaller color range than more advanced displays. One common application of dithering is to more accurately display graphics containing a greater range of colors than the hardware is capable of showing. For example, dithering might be used in order to display a photographic image containing millions of colors on video hardware that is only capable of showing 256 colors at a time. The 256 available colors would be used to generate a dithered approximation of the original image. Without dithering, the colors in the original image might be simply be "rounded off" to the closest available color, resulting in a new image that is a poor representation of the original. Dithering takes advantage of the human eye's tendency to "mix" two colors in close proximity to one another.

Dithering such as this, in which the computer's display hardware is the primary limitation on color depth, is commonly employed in software such as web browsers. Since a web browser may be retrieving graphical elements from an external source, it may be necessary for the browser to perform dithering on images with too many colors for the available display. It was due to problems with dithering that a color palette known as the "web-safe color palette" was identified, for use in choosing colors that would not be dithered on displays with only 256 colors available.

Another useful application of dithering is for situations in which the graphic file format is the limiting factor. In particular, the commonly-used GIF format is restricted to the use of 256 or fewer colors. Images in other file formats, such as PNG, may also have such a restriction imposed on them for the sake of a reduction in file size. Images such as these have a fixed color palette defining all the colors that the image may use. For such situations, graphical editing software may be responsible for dithering images prior to saving them in such restrictive formats.

Dithering algorithms

There are several algorithms designed to perform dithering. One of the earliest, and still one of the most popular, is the Floyd-Steinberg algorithm, developed in 1975. One of the strengths of this algorithm is that it minimizes visual artifacts through an error-diffusion process; the Floyd-Steinberg algorithm typically produces images that more closely represent the original than simpler dithering algorithms.

Other dithering methods include:

• Average dithering: one of the simplest dithering techniques, based on selecting an average tone and choosing pixel colors based on how close they are to the average
• Ordered dithering: produces a cross-hatch dithering pattern similar to the halftones used by print newspapers
• Random dithering: introduces a random element to each pixel, resulting in a staticky image