Dithering

Dithering is a method for achieving the illusion for an indexed image of having greater colour depth than its maximum 8bit value of 256 colours. This technique also allows smoother colour transitions than would usually occur after colour quantization as a result of changing colour depth.

Indexed images have a restricted colour palette of two or more colours. To achieve the illusion of another colour outside this palette the size and shape of a pixel pattern is varied. The quality of the mixed colour greatly depends on the resolution of the media, the image is viewed in. Low resolution monitors usually still show the underlying pattern or even single pixels, while high resolution media, like print, usually will not show any pattern anymore. Actually this is how the huge variety of colours is achieved in printing, where the initial palette is restricted to four colours, cyan, magenta, yellow, and black (CMYK).

The following illustration shows how different shapes and sizes of a pixel pattern gradually influence and increase the quality of a resulting colour. Supplementary you may have a look at how the illusion of 136 colours is achieved using the 16 VGA-colours and how a bug in older versions of the Opera browsers lead to actually mixing each two dithered colours to result in a single intermediate colour.

Rasterisation of Purple and Yellow

16 x 16 pixel	8 x 8 pixel	4 x 4 pixel	2 x 2 pixel
1 x 1 pixel	straight plus (+) pattern	shifted plus (+) pattern	filled squares pattern
plain intermediate colour

Two different techniques may be used in dithering. The first one, ordered dithering splits the colour value of each single pixel into its RGB channels and sets each channel value according to a predefined matrix. This matrix consists of two or more boundary values and one or more threshold values, e.g. 0 and 255 as boundaries and 127 as threshold value. The resulting RGB color values form a palette of at most 256 colours. The second technique, error diffusion, does not only calculate colour values for each single pixel but also takes the colour value of the surrounding pixels into account when calculating the indexed colour value of each pixel. The most prominent error diffusion technique is the Floyd-Steinberg Error Diffusion.

Floyd-Steinberg Error Diffusion

The Floyd-Steinberg error diffusion distributes the difference between the initial and the calculated value of each pixel among surrounding pixels. In this algorithm the surrounding pixels are weighted according to a predefined scheme.

Floyd-Steinberg error diffusion distributes 7/16 of the calculated error to the adjacent right pixel, 1/16 to the lower right pixel, 5/16 to the pixel below and 3/16 to the lower left pixel.

Scanning the pixels of the image line by line only from left to right may lead to the impression of a certain directionality of the resulting image or to undesirable patterns. To avoid this, an advanced method is to change the scanning direction each line.

normal scanning
The direction does not change, possibly leading to unwanted patterns.

advanced scanning
The scanning direction alternates from left to right to left, improving the quality of the image.

When applying dithering, any colour palette may be used instead of a generated one. though the generated palette usually is an optimized palette in nowadays graphics software. Yet a couple of years ago, when VGA monitors, only capable of displaying 16 or 256 colours, were in wider use, it was best practise only to use websafe colours.

Predefined colour palettes come with a fixed number of possible colour values. Quite often, not all values are used for the image. To reduce the filesize of the resulting image it is now best to delete unneeded colours from the predefined colour palette.

Comparison of Colour Palettes

Full Palette	Reduced Palette
Colours: 104 of 216 FileSize: 20,671	Colours: 104 of 104 FileSize: 20,317

Both images above use exactly the same colours, in fact they are identical despite the number of colour values entered in their corresponding colour palettes. Where the first image stores all 216 websafe colours, the second image stores only those colours, which are actually needed, thus reducing the file size by 354 bytes. At first, this might not seem to be much, but considering e.g. an average number of 100 requests per day this amounts to around 13MB over one year. Assuming one has more than one image on her site, traffic reduction increases considerably.

To sum up, dithering improves the quality of indexed images but on the negative side it increases file sizes. For best results, optimized and reduced colour palettes should be used. A comparison of different dithering techniques and colour palettes applied to an image can be found on the following pages:

• Dithered 8bit Images
• Dithered 4bit Images