Color Quantization: From Millions to Dozens of Colors

The Core Challenge

A 24-bit RGB image can contain up to 16,777,216 unique colors. But many artistic and technical contexts demand far fewer: 256 for GIF, 16 for classic pixel art, sometimes as few as 2 for monochrome prints. Color quantization is the science — and art — of choosing which handful of colors best represents all 16.7 million possibilities.

The naive approach of evenly dividing the RGB cube into bins produces terrible results. Most images use only a small region of the full color space, so uniform division wastes palette slots on colors that don't appear in the image at all.

Median Cut: Divide and Conquer

Paul Heckbert's Median Cut algorithm (1982) takes a spatial approach. It treats every pixel as a point in 3D RGB space, then repeatedly splits the point cloud along its longest axis at the median. After n splits, you have 2ⁿ clusters. The average color of each cluster becomes a palette entry.

Median Cut is elegant because it naturally adapts to the image. A sunset photograph, dominated by reds and oranges, will allocate most palette entries to warm hues — exactly where the detail matters. The blue sky gets fewer entries because it's more uniform.

K-Means Clustering

K-Means approaches the problem iteratively. Start with k random "centroids" in RGB space. Assign each pixel to its nearest centroid (using Euclidean distance). Recalculate each centroid as the average of its assigned pixels. Repeat until convergence.

K-Means often finds better palettes than Median Cut because it optimizes globally, but it's slower and sensitive to initialization. In practice, combining Median Cut initialization with K-Means refinement gives the best results — the speed of divide-and-conquer with the polish of iterative optimization.

The Distance Problem

Every quantization algorithm relies on measuring distance between colors. The naive Euclidean distance in RGB space treats red, green, and blue as equally important, but human vision doesn't. We're far more sensitive to changes in green (luminance) than in blue.