Color palette

Instead of storing the color of every pixel, you can store a short list of colors, the palette, and give each pixel only an index into that list. That is how GIF and palette PNG work. The image takes less space, but it can have at most as many colors as the palette.

Indexed color

palette: 0 → (200, 80, 40) #c85028 1 → (255, 255, 255) white 2 → (0, 0, 0) black 3 → (27, 152, 224) blue pixels: 0 0 1 1 0 3 3 1 each pixel is 2 bits instead of 24

Bits per pixel follow from the palette size: 1 bit is 2 colors, 4 bits 16, 8 bits 256. In GIF the palette always has 2, 4, 8, ... 256 entries (see the logical screen descriptor); in PNG any number from 1 to 256.

Choosing a palette

A photo usually has tens of thousands of distinct colors. Reducing it to 256 is quantization. The most common methods:

a fixed palette, e.g. "web-safe" 6 × 6 × 6 = 216 colors with components 0, 51, 102, 153, 204, 255. Simple, but poor for photos.
median cut (Heckbert, 1982): the RGB cube holding the image's colors is split in half along its longest side again and again until there are 256 boxes. The palette color is the average of each box.
octree: a tree that divides the RGB cube into octants, pruned from the leaves until as many nodes remain as there should be colors.
k-means: iteratively fitting 256 centers to the image's colors. The best results, the slowest.

The nearest palette color

Once the palette is fixed, each pixel gets the index of the nearest color. "Nearest" is simplest to measure in RGB, but distance in CIELAB gives better results because it matches what the eye sees. An example with the web-safe palette:

#c85028 = (200, 80, 40) nearest components from {0, 51, 102, 153, 204, 255}: 204, 102, 51 → #cc6633 Lab: (49.71, 45.77, 46.31) → (54.64, 36.91, 46.12) ΔE = 10.1 (a clearly visible difference)

Dithering

When there are too few colors, gradients turn into bands. Dithering hides that by mixing neighboring palette colors in a fine pattern the eye averages out (see averaging mixture).

The most popular is Floyd-Steinberg dithering (1976): the error between a pixel's color and its palette color is spread to neighbors not yet processed:

pixel 7/16 3/16 5/16 1/16 error = original color - palette color right neighbor += error · 7/16 lower-left neighbor += error · 3/16 lower neighbor += error · 5/16 lower-right neighbor += error · 1/16

In our example the red error is 200 - 204 = -4, green 80 - 102 = -22, blue 40 - 51 = -11. The pixel to the right therefore gets (-1.75, -9.6, -4.8), which pushes it toward a darker palette color and on average gives a color closer to the original.

The alternative is ordered dithering with a Bayer matrix: a fixed threshold pattern, faster and stable in animation (it does not "flicker" between frames), but with a visible regular texture.

The dithering error is best computed in linear light, not on gamma-encoded values. Otherwise light and dark areas come out slightly shifted (see gamma correction).