99.9999% of Your Colors Must Go
Every photo you have ever taken holds up to 16,777,216 colors. Every Game Boy sprite ever drawn holds 4. The algorithm that negotiates between those two worlds is called color quantization — and it decides which colors survive.
The Problem: 16.7 Million Colors, 16 Slots
Your camera speaks truecolor: 8 bits each for red, green, and blue, or 224 = 16,777,216 possible colors per pixel. Pixel art speaks indexed color: each pixel is an index into a small palette — 256 colors for a GIF, 16 for a retro console sprite, 4 for the original Game Boy. Converting the first world into the second means answering two hard questions:
- Which colors? From millions of candidates, pick the N that best represent the image.
- Which pixel gets which? Map every original pixel to its nearest surviving color without making the result look broken.
Get the first question wrong and your sunset turns muddy. Get the second wrong and smooth gradients collapse into ugly contour bands. This is not a solved-and-boring problem: the best answer depends on the image, and the classic algorithms behind it are genuinely clever.
I Measured It: What 16 Colors Actually Look Like
Rather than describe quantization in the abstract, I ran it. I generated a synthetic 480x320 sunset scene in Python (sky gradient, sun, mountains, lake — 5,890 unique colors with a touch of noise to behave like a real photo), then crushed it to 16 colors with median-cut, with and without dithering. Same palette, same 16 slots — only the pixel-mapping step differs.
The same scene three ways. Middle: 16 colors, no dithering — the sky collapses into hard contour bands. Bottom: the identical 16-color palette with Floyd–Steinberg dithering — grain replaces banding and the gradient reads as smooth again. Test image generated programmatically; quantized with Pillow 10.2.0 on 2026-10-18.
3x zoom on the sky. Banding is not subtle up close: each contour step is a place where the mapping had no closer color to offer. Error diffusion smears that failure across neighboring pixels, which your eye averages back into a gradient.
The actual 16 colors median-cut chose. Notice how many slots went to the sky gradient — the algorithm spends palette entries where the pixels are, which is exactly its defining trick.
Two numbers deserve a second look. First, dithering cost 800 bytes: the grain it adds is noise, and noise compresses badly. Beauty has a file-size price. Second, the 256-color version came out at 225,922 bytes — 19% larger than the 24-bit original. Fewer colors does not automatically mean a smaller file; PNG compresses patterns, and an indexed image of a noisy gradient has worse patterns than the RGB original. Quantization is about color count, not file size — a distinction that trips up a lot of export dialogs.
How the Pickers Work: Four Ways to Choose a Palette
Choosing N colors from millions is a clustering problem in 3D: every pixel is a point in RGB space, and you want N clusters that cover them well. The classic strategies, oldest first:
Chop each channel into equal slices (the classic RGB332 keeps 3 bits of red, 3 of green, 2 of blue). No image analysis at all, so it runs instantly — and wastes slots on colors your image never uses while starving the ones it does. Gradients turn into staircases. Retro hardware loved it; nobody else should.
Build a histogram of the image's colors and keep the N most frequent. Simple and often decent — until a rare-but-critical color loses the vote. A tiny red warning light on a gray dashboard vanishes because gray had more pixels. Popularity ignores rare colors, and rare colors are frequently the point.
Invented by Paul Heckbert in 1979 and first published at SIGGRAPH 1982 in Color Image Quantization for Frame Buffer Display, median-cut is the first true color quantization algorithm and the engine behind "Adaptive" palette modes everywhere. The recipe:
- Put every pixel's color in one big RGB box.
- Find the box's longest axis (R, G, or B).
- Sort the colors along that axis and split at the median — so each half holds roughly the same number of pixels.
- Repeat until you have N boxes; each box's average color becomes one palette entry.
Splitting at the median (not the middle) is the genius move: crowded regions of color space get split again and again, earning more palette slots, while empty regions get none. That is why the sky-heavy palette in my experiment above is not a bug — it is the algorithm correctly spending its budget where the pixels are.
Octree quantization builds the palette in a single pass through a tree — great for memory-tight encoders. Anthony Dekker's NeuQuant (1994) trains a tiny neural network on the image's colors and remains the quality king in tools like pngquant. K-means clustering gives excellent results if you can afford the compute. For most work, though, median-cut plus good dithering gets you 95% of the way there.
Sources: median-cut history via the Color quantization encyclopedia entry (Heckbert, SIGGRAPH '82) and a 2026 retrospective calling it "the first true color quantization algorithm."
Banding and the Art of Lying with Dots
Even a perfect palette leaves a problem: a smooth gradient may need 200 distinct shades, and you have 16. Mapping each pixel to its nearest color produces banding — visible contour steps where the image runs out of in-between colors (see the zoom figure above). Dithering is the standard lie told to fix it: arrange the available colors in tiny spatial patterns that your eye averages into the missing shades.
The heavyweight is Floyd–Steinberg error diffusion (1976). Scan pixels left to right, top to bottom; when a pixel is forced to the nearest palette color, take the rounding error and push fractions of it onto the not-yet-processed neighbors:
X 7/16 3/16 5/16 1/16
Each pixel donates 7/16 of its error to the right neighbor, 3/16 below-left, 5/16 below, and 1/16 below-right. The magic: over any small region, the errors cancel out, so the average color is exactly right even though no single pixel is. That is why the dithered sky in my experiment reads as a smooth gradient — locally wrong, globally correct.
The older alternative is ordered dithering with a Bayer matrix (B. E. Bayer, 1973): tile a fixed threshold matrix over the image and nudge each pixel's value by its matrix entry before quantizing. The classic 4x4:
0 8 2 10 12 4 14 6 3 11 1 9 15 7 13 5
Ordered dithering is deterministic, fast, and produces a visible crosshatch texture — which is exactly why retro artists love it as an aesthetic. Error diffusion looks more photographic but can leave faint worm-like trails in flat areas. Pick your poison: photographic smoothness (Floyd–Steinberg) or honest retro texture (Bayer).
Sources: UT Austin halftoning survey ("error diffusion was introduced in 1976 by Floyd and Steinberg"); Bayer's 1973 paper "An Optimum Method for Two-Level Rendition of Continuous-Tone Pictures."
Do It Yourself: The Two Steps That Matter
In Python's Pillow, the correct incantation is two steps: build the palette with median-cut, then apply it with dithering. Watch out for a real gotcha I hit while preparing this article —
from PIL import Image
img = Image.open("sunset.png")
# Step 1: build the 16-color palette (median-cut)
palette = img.quantize(colors=16, method=Image.Quantize.MEDIANCUT)
# Step 2: map pixels to it, WITH dithering
small = img.quantize(palette=palette, dither=Image.Dither.FLOYDSTEINBERG)
small.save("sunset-16.png")img.convert("P", palette=Image.ADAPTIVE, dither=...) silently ignores the dither argument — my first two runs produced byte-identical files with and without dithering. The two-step quantize() form above is the reliable path. If your "dithered" export looks suspiciously clean, this is probably why.
From the command line, ImageMagick does it in one breath:
magick sunset.png -colors 16 -dither FloydSteinberg sunset-16.png
And in GIMP, it is Image → Mode → Indexed, where you can pick the palette size and choose None / Floyd–Steinberg / Positioned (ordered) dithering from a dropdown. Same algorithms, friendlier buttons.
A Pixel Artist's Cheat Sheet
Photo → pixel-art base: median-cut (or NeuQuant) to 16–32 colors with dithering for the preview, then hand-tune the palette. The algorithm does the grunt work; you make the artistic calls.
Sprites and UI with flat fills: dithering OFF. Dither grain on clean edges looks like dirt, and it inflates your PNG — my test showed dithering measurably growing the file.
Gradients you cannot avoid: Floyd–Steinberg for photographic smoothness, Bayer ordered dither when you want the texture to be part of the style. Old demoscene artists chose Bayer on purpose.
Never dither twice. Quantize → edit → quantize again compounds the damage. Keep a 24-bit master and quantize only at export.
Remember what the numbers mean. Fewer colors ≠ smaller file. My 256-color export was 19% larger than the truecolor original. Measure, don't assume.
Quantization used to be a hardware law — the Game Boy gave you four shades and the NES gave you 54 colors, take it or leave it. Today it is a choice, and a well-informed one: pick your palette with an algorithm that respects your image's actual color distribution, hide the seams with dithering when the style allows it, and always check the result at 1x before you ship. The 16 colors you keep are the whole artwork — choose them like it.
All measurements in this article are from the author's own experiment (Pillow 10.2.0, 2026-10-18) on a programmatically generated test image. The cover illustration is AI-generated.