Archive

Some color reduction related historical sources.

Usenet discussion on comp.graphics

A thread on color reduction found in nic.funet.fi’s archive:

palletmapping1.txt (1988)

David P. Cook (Truevision Inc.) responds to Bob Clark (HP) on mapping 32,768 colors from a Targa 16 board to 256 VGA colors. Describes an RGB-to-palette index lookup table, popularity reduction by histogram, and color cube compression (median cut).

palletmapping2.txt (1988)

Patrick Naughton (Sun Microsystems) recommends to run Floyd-Steinberg dithering after the median-cut algorithm.

palletmapping3.txt (1988)

David Jevans (University of Calgary) describes an octree-based color quantizer for his Sun3/60 computer.

palletmapping4.txt (1988)

Paul Raveling (USC-ISI) describes a tree-based color selection algorithm that classifies colors into a tree and prunes upward from the leaves. I believe this method is what ImageMagick’s color quantizer was inspired by.

palletmapping5.txt (1988)

Paul Heckbert (UC Berkeley) explains bit-replication of low-bit color values to 8-bit (approximates multiplication by 255/7). References his median cut paper and an improved 1988 algorithm by Wan, Wong, and Prusinkiewicz.

Tutorials

DITHER.TXT (1989)

Lee Crocker (later co-authoring the PNG format specification) describes four classes of dithering algorithms: random, pattern, ordered (Bayer matrix), and error diffusion (Floyd-Steinberg, Jarvis-Judice-Ninke, Stucki, Burkes). Includes sample C code and a bibliography.

DHALF.TXT (1991)

Paul Boulay’s and Mike Morra’s revision of DITHER.TXT. Adds new error-diffusion filters (Sierra family) and additional explanations.

Collected by Pekka Väänänen. Last update: 28 May 2026.