Colour Quantisation
|
|
In a graphical OS environment, there will come a time when you need to represent an image on a display device. If the display device is unable to represent all the colours from the image, you will have to have a mechanism of mapping a colour from the image onto the closest displayable colour from the device palette. The general term for such a colour mapping is Colour Quantisation. The Colour Quantiser is the section of a system responsible for performing this action.
For the purposes of this article, the source image is considered to be a bitmapped image with 24 bits per pixel, eights bits for each of the red, green and blue components. This is commonly the worst case scenario (outside of 48-bit photography processing) and any other scenario can be expressed as this.
While Colour Quantisation on its own can be used to produce a reasonable representation of the image, most applications may want to consider applying Dithering to the image to produce a more accurate overall reproduction.
The term Colour Quantisation also refers to the process of calculating a low-colour palette from an image that preserves much of the colour detail, but that usage is not discussed here.
Disclaimer: This article is not intended to be the final word nor give you the best solution for this issue, but rather to introduce the concept and hopefully provide something that will work in most cases. The methods presented here should work to get your project over this hurdle in the short term to then be replaced and improved upon in future.
Non-paletted Quantisation
If your display device is a non-paletted type but it cannot display all of the required colours, for example a 15-bit display with only 5 pixels per channel, colour quantisation is straightforward, but you may still want to consider Dithering the image.
Colour Contraction
Trivially, to map a 24-bit colour onto a smaller colour space, logic and bit-shifting can be used to preserve the most significant bits in each channel from the source colour and compress them into a colour in the destimation space.
For example, given a 24-bit colour with the bits in the following form
{ R0, R1, R2, R3, R4, R5, R6, R7, G0, G1, G2, G3, G4, G5, G6, G7, B0, B1, B2, B3, B4, B5, B6, B7 }
(where R0 is the most significant bit in the eight bit Red component and R7 is the least significant bit), this can be made into a 15-bit colour by removing the least significant three bits from each channel, giving the following
{ R0, R1, R2, R3, R4, G0, G1, G2, G3, G4, B0, B1, B2, B3, B4 }.
Consideration could be given to the value of the sixth bit to be used to "round" the resultant value up or down as required, but this is unlikely to significantly affect the image quality.
Colour Extension
A low bit colour can be converted into a high bit colour in a similar manner to the above by adding in additonal low-significance bits. For example the 15-bit value
{ R0, R1, R2, R3, R4, G0, G1, G2, G3, G4, B0, B1, B2, B3, B4 }
could be converted into a 24-bit colour by inserting three zero bits into each channel, yielding
{ R0, R1, R2, R3, R4, 0, 0, 0, G0, G1, G2, G3, G4, 0, 0, 0, B0, B1, B2, B3, B4, 0, 0, 0 }.
Paletted Quantisation
Colour Quantisation for a destination palette is by far the most useful application of this technique. Any one of 16 million possible colours may have to be processed and displayed as a palette colour in order to recreate the image as accurately as possible. If only a small number of colours is available, such as the 16 colours that are available with a VGA Mode 12h screen, a good method for colour quantisation is essential. The various techniques can be extended to produce greyscale or even halftone (black and white) representations.
Euclidean Distance
The most basic method of colour quantistion is the Euclidean Distance technique. For each colour pixel in the image in turn, Euclid's formula (an extension of Pythagoras' theorem) can be applied to each colour in the palette in turn to determine which of the paletted colours is closest to the desired colour. This palette colour is then used to represent the pixel.
In pseudo code, the algorithm is as follows:
Define C as the source colour Define ND as the nearest distance so far Define NP as the nearest palette entry so far Set ND to a large value For Each Palette Entry P Calculate D as Square of ( C.R - P.R ) plus Square of ( C.G - P.G ) plus Square of ( C.B - P.B ) If D is less than ND Set ND = D Set NP = P End If Next Use NP as the result
While the implementation of this algorithm is very straightforward, the algorithm has to compare each pixel in the source image to each colour in the destination palette in turn using three squareing operators, meaning that it is very slow in operation. (Note that the square root operator called for by the Euclidean algorithm can be omitted because it will not affect the result.)
The other main problem with using the Euclidean Distance is that it considers the Red-Green-Blue colour space to be a regular cube with a linear distribution, but this isn't the case. Consider the Euclidean Distance algorithm being used to represent colours as a greyscale, a pure green and a pure blue will resolve to the same shade of grey, despite green being approximately seven times lighter than blue. A keen implementer may want to modify this algorithm to take account of the variance in brightness.
Pre-calculated map
A logical improvement of the Euclidean Distance method above is to pre-calculate a table of the nearest palette colour for a set of possible source colours. This table can be calculated whenever the display palette is set or changed, and provides a fast lookup for the colour quantiser to significantly improve performance.
Each index of the lookup table will represent a point on a regular grid within the RGB colour cube, and the corresponding value will store the index of the nearest displayable palette entry. The more points in the grid that are calculated will improve the accuracy of the quantisation, but will take more memory to store and more processing time to calculate.
The extreme case of this would be to use a grid of point that represents every possible combination of the 24-bit colourspace. Doing this would require 16 million array elements (16Mb at one byte per palette index) and would take the same time to calculate as using the Euclidean algorithm to quantise a 4096x4096 pixel image. At the other extreme, using too few elements will result in an inaccurate mapping.
The following table details the various grid size options and the resultant table size:
| Bits per channel | Mapping table entries | Calculated entries per Palette entry | Comment |
|---|---|---|---|
| 1 | 8 | 0.5 | Too few to be usable, doesn't even allowing mapping to each palette colour. |
| 2 | 64 | 4 | Minimum reasonable table size, will work as a quick procedure. |
| 3 | 512 | 32 | Reasonable table. Provides good mapping in little memory. |
| 4 | 4096 | 256 | Very accurate table. Neatly fits into one page of memory. |
| 5 | 32768 | 2048 | Unreasonably accurate table for 16 colours. Uses eight pages. |
| 8 | 16777216 | 1048576 | Excessivly accurate table for 16 colours. Uses 16Mb. |
From this table, it would seem that storing 3 bits per channel would seem to be a good starting point for the 16-colour mode 12h screen.
As each index entry in the table represents a point within the RGB colourspace, calculating the colour mapping table is straightforward:
Allocate the Colour Table Loop the number of entries in the Colour table Calculate the colour in the grid that corresponds to this array index Use the Euclidean Distance calculation to find the nearest palette entry to the colour Store the Palette entry into the corresponding array element
Once the table is calculated, it can be stored and will not need to be recalculated unless one or more palette entries is changed.
When the quantiser is needed to represent an image on the display device, the following algorithm is applied:
Loop each pixel in the source image Calculate the equivalent colour in the grid from the source colour by colour contraction (mentioned above) Access the colour table using the grid colour as the index Use the array element contents as the palette entry for that colour.