There are a number of reasons for wanting to reduce the number of colours in an image. It may be that the intended display device has a limited palette or you may just want to reduce the amount of memory that the image occupies.

The first step in this process is obviously to load in an image. For this example I will be using the Lena and mandrill images which are standard images for testing various image processing techniques.

Original 'Lena' image	Original 'Mandrill' image

Step two is to go through each pixel of the image in turn and replace them with the nearest colour from the available palette. The algorithm for this is essentially as follows:

   1. Start at the first pixel in the image.
   2. Get the actual colour of the pixel.
   3. Find the nearest colour of this pixel from the available palette.
   4. Replace the pixel with the nearest colour.
   5. Have we reached the end of the image? If so stop here.
   6. Move on to the next pixel.
   7. Go back to step 2.

Or in pseudo-code:

   For y = 0 To ImageHeight - 1
      For x = 0 To ImageWidth - 1
         actualColour = GetPixelColour(x, y)
         nearestColour = FindNearestColour(actualColour)
         PutPixelColour(x, y, nearestColour)
      Next
   Next

There are a few methods for finding the nearest colour. The one that I am going to explain here is called the Euclidean distance method.

The Euclidean distance method works by first calculating the difference between the separate RGB values of the actual colour and each of the colours available from the palette. These differences are then squared (a convenient way of ensuring that there are no negatives) and added together to produce the distance. The palette colour that has the smallest distance from the actual colour will be the nearest.

The algorithm for this is as follows:

   1. Set minimum distance to a value higher than the highest possible.
   2. Start at the first colour in the palette.
   3. Find the difference between each RGB value of the actual colour and
      the current palette colour.
   4. Calculate the Euclidean distance.
   5. If the distance is smaller than the minimum distance set minimum distance
      to the smaller value and note the current palette colour.
   6. Have we reached the end of the palette? If so stop here.
   7. Move on to the next colour in the palette.
   8. Go back to step 3.

Or in pseudo-code:

   minimumDistance = 255*255 + 255*255 + 255*255 + 1
   For paletteColour = 0 To lastPaletteColour
      rDiff = Red(actualColour) - Red(paletteColour)
      gDiff = Green(actualColour) - Green(paletteColour)
      bDiff = Blue(actualColour) - Blue(paletteColour)
      distance = rDiff*rDiff + gDiff*gDiff + bDiff*bDiff
      If distance < minimumDistance
         minimumDistance = distance
         nearestColour = paletteColour
      EndIf
   Next

Performing this colour reduction method on our example images will produce the following results:

'Lena' image reduced to 8 colours	'Mandrill' image reduced to 8 colours

And there we have it. Our original images have now been reduced from millions of colours to only 8.

Programs written to accompany this series demonstrating the techniques discussed are available from here. There are versions of the programs available for Linux, Mac OS X and Windows platforms. Please be sure to read the 'readme.txt' files for more information.