Dithering
|
|
Dithering is the process of modifying the colour of various pixels in an image to provide a better reproduction of the source image. It is used commonly when displaying an image on a display that is incapable of representing all the required colours. Dithering is commonly used alongside the process of Colour Quantisation, and an understanding of that topic is recommended before continuing through this article.
The Wikipedia article on Dithering is very good and gives visual examples of each of the method of dithering. This article provides a slightly different viewpoint and focuses on elements that may be of use to OS developers.
Note that Dithering and Anti-aliasing are opposite functions. Dithering uses spatial resolution to make up for a lack of colours. Anti-aliasing uses colours to make up for a lack of spatial resolution.
Error Diffusion
The most effective Dithering techniques for use on raster (pixel-based) displays work by Error Diffusion, that is that they compute the nearest displayable colour for a pixel (by Colour Quantisation) and then calculate the difference between what that pixel should have been and what it was. This calculated difference (the "error") is then distributed to neighbouring pixels and taken into account when they are quantised. The error can accumulate across multiple pixels until becomes significant enough to alter the result of the quantisation.
For example, a dithering algorithm may be used to draw a grey line on a black and white display. In this instance, the dithering algorithm will likely draw alternating black and white pixels so that the overall effect is a grey line.
Basic Form
The basic form of error diffusion is to take the error from the first pixel and apply it to the next pixel to the right. This has the benefit of being very easy to implement, as the code only has to keep track of one pixel worth of error, but it produces a rather crude result.
In pseudo-code, this can be implemented as the following:
Define E as the carried error
For Each Source Pixel As P
Define Colour C as { P.R - E.R, P.G - E.G, P.B - E.B }
Calculate the Nearest colour to C as NC using the Colour Quantiser
Display the pixel as NC on the screen
Set E to be ( NC.R - C.R, NC.G - C.G, NC.B - C.B }
Next
Because we are taking the error from a pixel and applying it entirely to the pixel to the right, we could represent this use the following matrix kernel (no, the other kind):
| 0 | 0 | 1 |
The zero in the centre of the matrix represents the current pixel, and the one to the right indicates that the entire error (1 times the error) is applied to the pixel on the right.
This is the standard way of expressing an error diffusion dithering. All error diffusion algorithms will appear like this with the current pixel in the centre, and fractions surrounding it to indicate to which pixels the error is to be diffused. Also of note is that any pixels above or immediately to the left of the centre will be zero as all the algorithms consider that these pixels have already been drawn. This means that dithering can be applied to pixels sequentially.
Floyd–Steinberg Dithering
This is a more effective and more common dithering algorithm. It takes the error from the first pixel and divides it up between four neighbouring pixels using a the following kernel:
| 0 | 0 | 0 |
| 0 | 0 | 7/16 |
| 3/16 | 5/16 | 1/16 |
As before, the zero in the centre represents the pixel being processed, and the fractions below and to the right indicate what proportion of the error is accumulated into the corresponding pixel. As remarked above, the error is diffused only to pixels to the right or below so that the routine can be applied sequentially to an image.
This method is very effective and can render high colour images on displays with as few as 8 colours.
This algorithm is slightly more complicated to implement than the basic form, this is because the routine needs to store two rows worth of errors in order to correctly calculate the effective colour for each pixel. Depending on the application, the dithering process could modify the pixels further ahead in the source image itself to avoid having to store the diffused error data separately.
Other Dithering types
As well as Error Diffusion, there are other dithering types available, some of which are better suited to media other than a raster (pixel-based) screen. These are considered beyond the scope of this article. For more information, refer the wikipedia article.