An Optimal 256 colour palette

This article describes an optimal palette for 8 bit displays, with a palette of 256 colours. What I mean by "optimal" here, is general optimality, as it is very good for general colour reproduction, and fast, i.e. it is computationally easy and fast to match a given colour to the closest colour in the palette.

It is possible to make marginally better general palettes, but they are very slow to use. It is possible to adapt the palette to the picture, but again, slow, and not general. My palette is practically perfect, and it is easy to find the colours. Without further ado, here it is:

PNG
PNG
GIF
GIF

Palette256.h

Hardware Palette

If you want to define a good 8 bit palette in hardware, but not quite as good as the palette above, just do the following, which will give a nice palette with 8 levels of Red, Green, and Blue:

Red_Bit_0 = Bit_2 XOR Bit_5
Red_Bit_1 = Bit_0
Red_Bit_2 = Bit_1
Green_Bit_0 = Bit_2
Green_Bit_1 = Bit_3
Green_Bit_2 = Bit_4
Blue_Bit_0 = Bit_5
Blue_Bit_1 = Bit_6
Blue_Bit_2 = Bit_7

Matching colours

To match a colour to the closest colour in the palette, use the following simple subroutine. It is based on the algorithm for finding nearest sphere in 3 dimensions, from Conways book on sphere packings.

Sorry, but it is not finished yet. It will be here later. (In 2003, i have still not received any emails about this, so I suppose no one are interested.)

Some facts

How good is it? Signal to noise ratio is as if it were a palette of 512 colours, with 8 levels of Red, Green, and Blue. This means that you get 1 bit extra, sort of, 6 dB less noise, as compared to a palette of 216 colours with 6 levels of Red, Green, and Blue.

This is accomplished with 2 methods:

3D Sphere packing
By packing the colours as spheres instead of as cubes, the maximum distance between 2 close colours gets lower. (This also means that you must use Floyd Steinberg dithering, since ordered dithering is impossible.)
Gamma correction informatics
The colour white on a monitor consists typically of 28% Red, 55% Green, and 17% blue. However, this does not mean that they should have proportionally numbers of colour levels. F.ex. Red should not have half as many levels as Green, even though its level of light is half.
The reason for this, is that the optimal gamma correction is 1.5, from a signal/noise perspective, as shown below. The colours will thus be closer toghether for dark values. (The palette assumes that all colours are represented with gamma of 1.5. If they are not, fix that! Most monitors and screencards already have a gamma of nearly 1.5, so in most cases, do nothing at all!)
Corrected thusly, the relative number of colour levels are: 30% Red, 48% for Green, and 22% for Blue.
NEW(Sep2005:

The speed is accomplished by finding closest colour with the 3D closest sphere algorithm from Conways book on sphere packings. (More on that later)

There are 6 colours for a black to white pure grey-scale as well.

A little warning: The colours Black, White, Red, and Cyan are represented exacly, while the colours Green, Blue, Yellow and Magenta are all each represented by 2 equally close slightly off colours. This means that you have to watch out for overflow if you dither these last 4 pure colours with Floyd Steinberg dithering. This is almost never a significant problem in practice. In other cases, just use the colour that is given by the colour matching program, as they are plenty pure enough for practical purposes.

Optimal Gamma is 1.5

An eye receives photons. Since photons are energetic particles, they arrive as discrete quanta. In ordinary light, and ordinary photodetectors, the number of received photons is proportional to the amount of light, but because of the randomness, the random variation of the number of received photons will vary, proportionally with the square root of the amount of light.

F.ex: If a sensor registers an average of 100 photons each second, the actual number of photons received in a particular second will be something like 89, 107, or 96. If the receiver only receives for 1 second, the uncertainty will thus be 10%.

In order to maximize the amount of information in a pixel about the level of light, the discrete values should be placed so that the uncertainty of a light level is proportional to the distance between light levels. This is accomplished with a gamma correction of 1.5.