Floyd-Stucci Colour Reduction Methods and Gray Scaling

Reduce a true-colour image to a specified palette using dithering, and convert images to gray scale.

Before and after - converting to Black and White

This article describes the Floyd-Stucci method to dither an image to a specified palette and also how to Gray Scale an Image, as demonstrated in the vbAccelerator Image Processor.

This article covers two concepts:

  1. How to decrease colour depth to a specified palette
  2. Gray-Scaling an Image

1. Decreasing Colour Depth

There are two forms of colour depth reduction:

  1. Converting an image so it uses a specific palette of colours; for example, to a black and white image (a two colour palette) or to only use the WebSafe colours (a 216 colour palette).
  2. Reducing colours to a specified number by choosing an optimal palette.

The second method is achieved using Octree Colour Quantisation and isn't covered here.

To create an image using a fixed palette which resembles the original, you cannot simply match colours onto the new palette using a closest match. You can see this particularly if your destination palette is black and white, i.e. two colours. Just matching the closest colour often produces an all black or all white image, and certainly the detail is lost.

To reduce colour depth like this correctly, you need to somehow dither the output pixels so that different shades are still represented even with the lower colour resolution. It turns out there is a very simple way of doing this, as described by Floyd and Stucci involving error diffusion.

Floyd-Stucci Method

This is performed as follows:

  1. Starting at the top left pixel, determine the closest matching colour in the palette.
  2. Determine the difference between this colour and the actual colour.
  3. Add this error amount to the surrounding pixels and then continue.

The exact error diffusion is probably not 100% critical, but these are the amounts of error added to each pixel in the Floyd-Stucci method:

- Current 7/16
3/16 5/16 1/16

In the Image Processing sample, colour reduction is implemented in the cImageProcessDIB class. An optimised black and white method is supplied as well as a method which decreases to an arbitrary palette. An Internet Explorer 216 colour palette is supplied as a sample, and it creates the same results as some of the GIF images here on the vbAccelerator site (which were actually colour reduced using Paint Shop Pro using the Error Diffusion-Reduce Colour Bleeding method). The only problem is of course there is no way to save the resulting 256 colour image out as a GIF in VB! (Even if it was, it would contravene the unpleasant GIF/LZW patent licensing agreements - don't even think of acquiring a GIF license - it is prohibitively expensive.) If anyone has code to save a bitmap to PNG I would be very interested to hear. Unfortunately JPG is not a suitable format for saving 256 colour images: JPG only works with True Colour and Grey Scale images, and does not preserve colour fidelity, so what appears to be a flat area of colour in fact can vary quite a bit depending on the JPG compression level chosen.

Gray Scaling Images

Reducing images to a gray scale is a common image processing task which is also very simple to implement. The simplest method to do this is simply to take the green value and use apply the same value to Red and Blue pixels. This works well because the eye responds to green light in RGB colours much more strongly that the Red and Blue values. Obviously completely saturated Reds and Blues will not be represented this way. A more accurate conversion can be performed using the ITU standard, which is:

    (222 * Red + 707 * Green + 71 * Blue) / 1000 

Using this calculation results in a gray value between 0 and 255 which should be applied to each of the Red, Green and Blue pixels.