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

6 thoughts on “Image Processing Algorithms Part 1: Finding The Nearest Colour”

  1. i have only one question, where i have de data of paletteColour, lastPaletteColour o what means this 2 vars? thanks

    1. Hi Luis,

      The paletteColour variable is used to cycle through all the available colours in the palette. It starts at the first available colour (0) and continues until the last available colour.

      You will need to know what the bit depth of the destination image is, e.g. a 4-bit image would have a maximum of 16 colours, so the For…Next loop would effectively become “For paletteColour = 0 To 15”.

      Hopefully that makes sense, but let me know if you need further clarification.

      Kind regards,

      Francis

      1. ok thanks, so de value in this function:
        rDiff = Red(actualColour) – Red(paletteColour),
        paletteColour is the same number 0 to 15?

        1. Hi Luis,

          In the example I have given then yes, paletteColour would be 0 to 15.

          What the function you mentioned is doing is comparing the red component of the current pixel and comparing it with all the colours available in the palette. Whatever colour in the palette has the smallest difference to the pixel’s colour is the nearest colour.

          Kind regards,

          Francis

Leave a Reply

Homepage of Francis G. Loch's various projects

%d bloggers like this: