Dithering is one of those things, a crucial algorithm used in a vast variety of technologies used in our daily lives without most people evening knowing it. It’s up there with algorithms such as Fourier transformations, Gaussian blurs and Dijkstra’s algorithm.
What is dithering?
Dithering in the terms of image processing is an algorithm used to reduce the bit depth of an image while trying to closely approximate the original image and minimise the number of errors this process may cause. An example would be taking an image which uses 24-bits per pixel (which can store 16,777,216 different colours) down to 8-bits per pixel (256 colours)
Dithering can also be applied to audio waveforms which are beyond the scope of this article.
Uses of dithering
Older hardware such as computer monitors which may only be able to display 256 colours, would use this technique to better approximate the original image which might contain millions of colours. Dithering tries to take into account the errors that rounding a pixels value up or down to quantize it into the lower bit depth will create and attempt to even this error out. A key aspect of this algorithm is to rely on the human brains’ ability to average out and interpolate the missing information.
As GIF and animated GIFs are ever more common than before with their use in social media and the growing popularity of photography and videos, GIFs uses dithering to store the information with only 8 bits (256 colours).
Inkjet printers! Also used in everyday life and work by depositing small dots of ink on the page, the printer itself may not be able to recreate exactly every single colour within an image but will use dithering to closely approximate the image.
There are significantly more uses of dithering ranging from computer vision and audio analysis. Various algorithms exist in dithering to achieve different effects. Below are two examples, the first of Michelangelo’s David taken to an extreme of dithering and second on a colour image. These both were generated using the Floyd-Steinburg algorithm, one of the most commonly used today.
Sample Code and Java Library
If you are looking to use dithering in your own project I’ve created a java library which has implemented some of the most common dithering algorithms.