256 Colours are all you need

Introduction

During World War II mechanical computers were used to calculate bomb trajectory and navigation, engineers noticed that these computers (boxes filled with hundreds of gears) performed more accurately on planes than on the ground. The vibration of the plane reduced the error of the gears, which instead of sticking, moved more smoothly! That’s why small vibrating motors were built into computers of that epoch, their vibration was called dither.

Shouldn’t this be a post about digital images?
Well, dithering is the name of an actual technique used in digital image processing to increase the quality of images after quantization, let’s dive into the problem.

Quantization and its problem

True-colour images use 24bit per pixel, which means that each pixel has three channels of 8bit, one for red, one for green and one for blue. The possible colours that can be displayed are 256³ = 16.777.216, wow… do we need all these colours in each image? The short answer is no.

We can put all the colours that our image needs inside an indexed table (palette), and each pixel will save the index of the corresponding colour instead of the 24bit for the colour. If we consider that an average image has between 10.000 and 100.000 colours we need 17bit per pixel.

We can do even better, with quantization techniques we can decrease the number of colours to 256 (8bit per pixel). There are several algorithms for doing this, the simplest is selecting the 256 most-common colours, the problem is that the details are in smaller quantities and therefore will be lost in the process. A better approach is given by the Median-Cut algorithm or K-means.

The problem with quantization is that it tends to create uniform areas of colour that our eyes see as a big problem, whereas in the real world, there is no such problem and therefore our visual system immediately recognizes it as something artificial or wrong.

Dithering with Error Diffusion

We have introduced errors in our image, the original picture of this parrot has 134.178 colours! We want a technique that can create the illusion of colour depth using much fewer colours.

The technique that we are looking for is dithering.
There are different types of dithering, the version we are going to use today was introduced in 1976 by Robert W. Floyd and Louis Steinberg.
The concept is simple if we consider p being the original colour and q being the colour after quantization we can calculate the error and propagate it to neighbours. In this way, the average intensity over regions in the output image is approximately the same as the average over the same region in the original image.

Doing so creates another problem, now we are using more than 256 colours because the error that is accumulating on the neighbours changes their value that would not be in the palette anymore. Solving this problem is actually easy, for each pixel we first look in the palette for the closest colour, then we calculate the error and propagate it to the neighbours.

# let image be the original image
# let out be the output image
out := image
for each (x,y) in size(image) do
  out[x][y] = find_closest_palette_color(out[x][y])
  err := image[x][y] - out[x][y]
    out[x+1][y] += err * 7/16
  out[x-1][y+1] += err * 3/16
  out[x][y+1] += err * 5/16
  out[x+1][y+1] += err * 1/16

Remember, the original image has 134.178 colours and with only 256 we achieve a result that tricks our visual system. This is not a particular image, I challenge you to find an image that looks terrible or suspicious after applying this technique, you will not find it. Humans are not particularly good with colours, that’s why we can’t find too many differences between these two images.

Conclusion

Indexed-colour images (and therefore quantization and dithering) are used in many places, think of GIF for example. The title of this post is deliberately provocative, in many situations we need much more detail and much more colours than 256, but I enjoyed studying this technique because in the past, hardware limited the user experience and having 24-bit images was often out of bounds, which is why so many clever techniques came about, trying to optimize the optimizable should be a mantra for us as well.