Color Quantization (Median Cut)

A photograph fresh from a camera can contain millions of distinct colors. A GIF file allows at most 256. Somewhere between those two numbers lies one of the most satisfying algorithmic ideas in computer graphics: color quantization.

The task is simple to state: given an image and a target palette size $N$, pick $N$ colors and remap every pixel to whichever palette entry looks closest. Done badly, a sunset becomes a sickly neon smear. Done well, the result is almost indistinguishable from the original — at least to human eyes.

Median Cut, published by Paul Heckbert in 1982, was the first practical algorithm to crack this problem elegantly. Its key insight: think of every pixel as a point in a three-dimensional space where the axes are red, green, and blue. Quantization then becomes a geometry problem — partition that cloud of points into $N$ tight clusters and use each cluster's average color as a palette entry.

Heckbert's trick is a recursive divide-and-conquer. Find the axis (R, G, or B) along which the current set of pixels spreads most. Cut that box exactly at the median value so that half the pixels fall on each side. Repeat until you have $N$ boxes, then average the pixels in each box to get a palette color. The algorithm is $O(p \log N)$ in pixels $p$ — fast enough to run inside early 1980s hardware.

Like bin packing, color quantization is easy to approximate but provably hard to solve optimally. The gap between "good enough" and "perfect" is where algorithm design lives.

The demo below runs Median Cut on a synthetic color cloud. Pick how many palette colors you want, then watch the algorithm slice the color cube step by step.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label for="nColors">{{label_n_colors}} <strong id="nVal">8</strong></label>
  <input type="range" id="nColors" min="2" max="16" value="8" step="1" aria-label="{{label_n_colors}}">
  <button id="btnStep" type="button">{{btn_step}}</button>
  <button id="btnRun" type="button">{{btn_run}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="panels">
  <div class="panel">
    <div class="panel-title">{{label_color_cube}}</div>
    <canvas id="cubeCanvas" width="280" height="180" title="{{label_color_cube}}"></canvas>
  </div>
  <div class="panel">
    <div class="panel-title">{{label_palette}}</div>
    <div id="palette"></div>
  </div>
</div>
<div id="status" class="status">{{status_ready}}</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem; margin-bottom: .6rem; }
label { font-size: .9rem; color: #444; }
input[type=range] { width: 110px; cursor: pointer; }
button { font: 600 13px system-ui; padding: .38rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.panels { display: flex; flex-wrap: wrap; gap: .8rem; }
.panel { flex: 1 1 200px; }
.panel-title { font-size: .8rem; font-weight: 600; color: #555; text-transform: uppercase;
               letter-spacing: .04em; margin-bottom: .35rem; }
canvas { border: 1px solid #d0d7df; border-radius: 6px; display: block;
         width: 100%; max-width: 280px; }
#palette { display: flex; flex-wrap: wrap; gap: 4px; min-height: 40px; }
.swatch { width: 28px; height: 28px; border-radius: 5px; border: 1px solid rgba(0,0,0,.15);
          transition: transform .15s; cursor: default; }
.swatch:hover { transform: scale(1.25); }
.status { font-size: .88rem; font-weight: 600; color: #444; margin-top: .5rem; min-height: 1.3em; }

// Code not found

Each colored rectangle represents one bucket of pixels — a region of the RGB cube that has not yet been split. On every step the widest bucket gets cut at its median. When the number of buckets equals your target $N$, the center color of each bucket becomes a palette entry. Notice how early cuts carve out the most dominant hue ranges, while later cuts refine finer distinctions.

Median Cut is fast and produces visually good results — but it is a heuristic, not an optimal solution.

The true problem is: given $p$ pixels and a budget of $N$ colors, find the palette that minimizes the total squared error between each pixel and its nearest palette entry. This is equivalent to $k$-means clustering in three dimensions with $k = N$:

• $k$-means in 1D is solvable exactly in $O(p \cdot N^{2})$ time (dynamic programming on a sorted array).
• $k$-means in 2D and above — the version that color quantization actually needs — is NP-hard in the worst case (proven by Mahajan, Nimbhorkar and Varadarajan, 2009).
• The number of distinct color values in a 24-bit image is up to $2^{24} \approx 16\,\text{million}$, so even ignoring pixels, the search space is vast.

Practically, the gap matters whenever colors are adversarially distributed — for example, an image with equal masses of red, green, blue, yellow, cyan, and magenta will fool Median Cut into wasting palette slots. In those cases practitioners use $k$-means++ (better initialization), Wu's algorithm (exact 3D histogram quantization), or neural network palette fitting — all of which trade speed for quality.

Median Cut itself is $O(p \log N)$ and uses $O(N)$ extra memory. The fact that it is nowhere near optimal is hidden by the limits of human color perception: the eye is far more sensitive to luminance differences than to hue shifts, so a palette that is "wrong" by machine metrics often looks fine to us.

This is the pattern we see across bin packing and scheduling: the optimal version of a practical problem is NP-hard, so we reach for a clever polynomial-time approximation and call it good enough.

Color quantization is not a historical curiosity — it is active in every device that renders images under a color budget:

• GIF and PNG-8: both formats store at most 256 colors in a palette; every GIF encoder runs some form of color quantization before writing the file.
• E-ink displays: e-readers and electronic shelf labels often support only 2–16 colors; quantization maps grayscale or full-color content to that fixed set.
• Retro game sprites and pixel art: early consoles (NES, SNES, Game Boy) imposed strict per-sprite palette limits; artists and tools still use quantization to convert modern art to those constraints.
• Embedded systems and microcontrollers: devices with small framebuffers or limited RAM use palette-based color to cut memory usage by a factor of 3–4×.
• Video thumbnails and UI color extraction: extracting the "dominant colors" from a photo for a UI palette is color quantization with $N \approx 4\text{–}8$.
• Neural style transfer and image generation: modern pipelines use quantization as a post-processing step when the output must conform to a brand palette.

The same "partition a high-dimensional space into tight clusters" idea also powers dimensionality reduction and vector quantization in audio codecs — median-cut-style bisection appears whenever you need a compact discrete representation of a continuous space.

Median Cut is a small masterpiece of algorithm design: a problem that sounds hard — choose $N$ colors to best represent millions — is tamed by a single geometric observation. Sort the pixels along the axis of greatest spread, cut at the median, and recurse. The result is not perfect, but it is fast, predictable, and good enough that humans rarely notice the difference.

What Heckbert's algorithm cannot escape is the fundamental hardness underneath: optimal color quantization is NP-hard. Every image editor, GIF encoder, and e-ink driver is quietly living with that fact, choosing a fast approximation over an exact but intractable answer.

That trade-off — polynomial speed for near-optimal quality — is the beating heart of algorithm design. Median Cut makes it visible in the most literal way possible: you can see the approximation error in the image, and you can see that it barely matters.