1. Colour quantisation

The process of reducing the number of colours used in an image is called colour quantisation. It is a very old and common computer graphics problem. Many methods exist to do the task, and their efficiency depends on several parameters:

  • the input image: is it a photograph? a vector drawing? a composition of both?
  • the target media: is it a computer screen? if so, what are the size and the position of the pixels? is it a printed document? if so, what kind of paper? what kind of ink? or maybe the conversion should be optimised for both targets?
  • the quality requirements: for instance, can contrast be raised for a more appealing result at the expense of accuracy?
  • the allowed computation time: do we need 50fps or can we afford to wait 10 seconds for a better result?

1.1. Black and white thresholding

Since a greyscale pixel has a value between 0 and 1, a fast method to convert the image to black and white is to set all pixels below 0.5 to black and all pixels above 0.5 to white. This method is called thresholding and, in our case, results in the following image:

50% threshold 50% threshold gradient

Not that bad, but we were pretty lucky: the original image’s brightness was rather well balanced. A lot of detail is lost, though. Different results can be obtained by choosing “threshold values” other than 0.5, for instance 0.4 or 0.6, resulting in a much brighter or darker image:

40% threshold 40% threshold gradient 60% threshold 60% threshold gradient

Choosing the best thresholding value for a given image is called average dithering. But even with the best value, the results will not improve tremendously.

1.2. Greyscale thresholding

Better results can be achieved with a slightly bigger palette. Here is thresholding applied to a 3-colour and to a 5-colour palette:

3-colour threshold 3-colour threshold gradient 5-colour threshold 5-colour threshold gradient

Using this method, shades of grey are evenly used. However, the global error is far from optimal, as the following graphs show:

mean error 0.138 mean error 0.075

The following thresholding method minimises the error, at the cost of underusage of pure black and white colours:

3-colour threshold, minimal error 3-colour threshold gradient, minimal error 5-colour threshold, minimal error 5-colour threshold gradient, minimal error

mean error 0.125 mean error 0.0625

This is a perfect example of a situation where colour accuracy does not help achieve a better result.

1.3. Dynamic thresholding

Dynamic thresholding consists in studying the image before selecting the threshold values. One strategy, for instance, is to choose the median pixel value. This is done simply by computing a histogram of the image.

2-colour dynamic threshold 2-colour dynamic threshold gradient 5-colour dynamic threshold 5-colour dynamic threshold gradient

1.4. Random dithering

Instead of constantly using the same threshold value, one can use a different random value for each pixel in the image. This technique is simply called random dithering.

Here are two simple examples. On the left, threshold values are uniformly chosen between 0 and 1. On the right, random dithering with threshold values chosen with a gaussian distribution (mean 0.5, standard deviation 0.15):

random dithering random dithering gradient gaussian (0.5, 0.15) random dithering gaussian (0.5, 0.15) random dithering gradient

The images look very noisy, but they are arguably an improvement over standard constant thresholding.

Finally, this is dynamic thresholding with 4 colours where threshold values at every pixel are computed as usual, but then perturbated using a gaussian distribution (mean 0, standard deviation 0.08):

4-colour dynamic thresholding, gaussian (0, 0.08) 4-colour dynamic thresholding, gaussian (0, 0.08) gradient

Last modified 15 years ago Last modified on 12/22/2009 09:10:05 PM