Image Processing Algorithms Part 1: Finding The Nearest Colour

This article was originally published in issue 52 of The Crypt Mag

This is a series of articles on some basic algorithms for image processing. Part one in the series will look at how to reduce the number of colours of an image by finding the closest match from an available palette. For reasons of simplicity this article assumes that we will be working with a predefined palette limited to eight colours of black, red, green, yellow, blue, magenta, cyan and white.

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’ and ‘Mandrill’ images

(click images to enlarge)

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 negative values) 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’ and ‘Mandrill’ images reduced to 8 colours
(click images to enlarge)

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

Article copyright © 2007, 2010 Francis G. Loch

One thought on “Image Processing Algorithms Part 1: Finding The Nearest Colour”

Leave a Reply

Homepage of Francis G. Loch's various projects

%d bloggers like this: