Introduction

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 NN, pick NN 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 NN 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 NN boxes, then average the pixels in each box to get a palette color. The algorithm is O(plog⁡N)O(p \log N) in pixels pp — 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.

Try It

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.

<!-- Color Quantization (Median Cut) — interactive demo -->
<div class="controls">
  <label for="nColors">Palette colors: <strong id="nVal">8</strong></label>
  <input type="range" id="nColors" min="2" max="16" value="8" step="1" aria-label="Palette colors:">
  <button id="btnStep" type="button">Step</button>
  <button id="btnRun" type="button">Run all</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<div class="panels">
  <div class="panel">
    <div class="panel-title">Color cloud (RGB)</div>
    <canvas id="cubeCanvas" width="280" height="180" title="Color cloud (RGB)"></canvas>
  </div>
  <div class="panel">
    <div class="panel-title">Current palette</div>
    <div id="palette"></div>
  </div>
</div>
<div id="status" class="status">Press Step or Run all to start Median Cut.</div>

/* Styles for the Median Cut demo */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Median Cut color quantization demo — vanilla JS, no external dependencies

// Generate a fixed synthetic color cloud (7 Gaussian clusters in RGB space)
const PIXELS = (function () {
  const pts = [];
  const rng = (function () {
    let s = 0x9e3779b9;
    return () => { s ^= s << 13; s ^= s >> 17; s ^= s << 5; return (s >>> 0) / 0xffffffff; };
  })();
  // 7 color clusters: red, green, blue, yellow, cyan, magenta, orange
  const clusters = [
    [200, 60, 60], [60, 160, 80], [60, 80, 200],
    [210, 190, 50], [50, 190, 190], [190, 60, 180], [240, 140, 30]
  ];
  for (const [cr, cg, cb] of clusters) {
    const n = 35 + Math.floor(rng() * 20);
    for (let i = 0; i < n; i++) {
      const r = Math.min(255, Math.max(0, cr + Math.round((rng() - 0.5) * 70)));
      const g = Math.min(255, Math.max(0, cg + Math.round((rng() - 0.5) * 70)));
      const b = Math.min(255, Math.max(0, cb + Math.round((rng() - 0.5) * 70)));
      pts.push([r, g, b]);
    }
  }
  return pts;
})();

// A bucket holds a set of pixels and their bounding box in RGB space
function makeBucket(pixels) {
  const r = pixels.map(p => p[0]), g = pixels.map(p => p[1]), b = pixels.map(p => p[2]);
  return {
    pixels,
    rMin: Math.min(...r), rMax: Math.max(...r),
    gMin: Math.min(...g), gMax: Math.max(...g),
    bMin: Math.min(...b), bMax: Math.max(...b)
  };
}

// Split a bucket along its widest axis at the median
function splitBucket(bucket) {
  const rRange = bucket.rMax - bucket.rMin;
  const gRange = bucket.gMax - bucket.gMin;
  const bRange = bucket.bMax - bucket.bMin;
  let axis = 0;
  if (gRange >= rRange && gRange >= bRange) axis = 1;
  else if (bRange >= rRange && bRange >= gRange) axis = 2;
  const sorted = bucket.pixels.slice().sort((a, b) => a[axis] - b[axis]);
  const mid = Math.floor(sorted.length / 2);
  return [makeBucket(sorted.slice(0, mid)), makeBucket(sorted.slice(mid))];
}

// Compute the representative color of a bucket (average of all pixels)
function bucketColor(bucket) {
  const n = bucket.pixels.length;
  const r = Math.round(bucket.pixels.reduce((s, p) => s + p[0], 0) / n);
  const g = Math.round(bucket.pixels.reduce((s, p) => s + p[1], 0) / n);
  const b = Math.round(bucket.pixels.reduce((s, p) => s + p[2], 0) / n);
  return [r, g, b];
}

function rgb(r, g, b) { return `rgb(${r},${g},${b})`; }

// Algorithm state: current list of buckets and target palette size
let buckets = [makeBucket(PIXELS)];
let target = 8;

// Canvas drawing — project the 3D RGB cube to 2D using an oblique projection
const canvas = document.getElementById('cubeCanvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// Oblique projection: x influenced by R and B, y influenced by G and B
function project(r, g, b) {
  const x = Math.round(0.1 * W + (r / 255) * 0.55 * W + (b / 255) * 0.25 * W);
  const y = Math.round(0.85 * H - (g / 255) * 0.65 * H - (b / 255) * 0.18 * H);
  return [x, y];
}

function draw() {
  ctx.clearRect(0, 0, W, H);
  // Draw every pixel as a small dot in its own color
  for (const [r, g, b] of PIXELS) {
    const [x, y] = project(r, g, b);
    ctx.beginPath();
    ctx.arc(x, y, 2.5, 0, 2 * Math.PI);
    ctx.fillStyle = rgb(r, g, b);
    ctx.fill();
  }
  // Draw the centroid of each current bucket as a larger outlined circle
  for (const bkt of buckets) {
    const [cr, cg, cb] = bucketColor(bkt);
    const [x, y] = project(cr, cg, cb);
    ctx.beginPath();
    ctx.arc(x, y, 7, 0, 2 * Math.PI);
    ctx.fillStyle = rgb(cr, cg, cb);
    ctx.fill();
    ctx.beginPath();
    ctx.arc(x, y, 7, 0, 2 * Math.PI);
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 2;
    ctx.stroke();
    ctx.beginPath();
    ctx.arc(x, y, 7, 0, 2 * Math.PI);
    ctx.strokeStyle = '#333';
    ctx.lineWidth = 1;
    ctx.stroke();
  }
}

function drawPalette() {
  const el = document.getElementById('palette');
  el.innerHTML = '';
  for (const bkt of buckets) {
    const [r, g, b] = bucketColor(bkt);
    const sw = document.createElement('div');
    sw.className = 'swatch';
    sw.style.background = rgb(r, g, b);
    sw.title = `rgb(${r},${g},${b})`;
    el.appendChild(sw);
  }
}

function setStatus(msg) {
  document.getElementById('status').textContent = msg;
}

// Pick the bucket with the greatest spread (widest axis) to split next
function pickWidest() {
  let best = -1, idx = 0;
  for (let i = 0; i < buckets.length; i++) {
    const bkt = buckets[i];
    const spread = Math.max(bkt.rMax - bkt.rMin, bkt.gMax - bkt.gMin, bkt.bMax - bkt.bMin);
    if (spread > best) { best = spread; idx = i; }
  }
  return idx;
}

function canStep() { return buckets.length < target && buckets.length < PIXELS.length; }

function step() {
  if (!canStep()) return;
  const idx = pickWidest();
  const [a, b] = splitBucket(buckets[idx]);
  buckets.splice(idx, 1, a, b);
  draw();
  drawPalette();
  if (!canStep()) {
    setStatus(i18nFmt('Done! Palette has %n% colors.', { n: buckets.length }));
    document.getElementById('btnStep').disabled = true;
    document.getElementById('btnRun').disabled = true;
  } else {
    setStatus(i18nFmt('Split %cur% of %total% buckets — keep going!', { cur: buckets.length, total: target }));
  }
}

function reset() {
  buckets = [makeBucket(PIXELS)];
  draw();
  drawPalette();
  setStatus('Press Step or Run all to start Median Cut.');
  document.getElementById('btnStep').disabled = false;
  document.getElementById('btnRun').disabled = false;
}

document.getElementById('nColors').addEventListener('input', function () {
  target = +this.value;
  document.getElementById('nVal').textContent = target;
  reset();
});

document.getElementById('btnStep').addEventListener('click', step);

document.getElementById('btnRun').addEventListener('click', function () {
  while (canStep()) step();
});

document.getElementById('btnReset').addEventListener('click', reset);

// Initial render
draw();
drawPalette();
setStatus('Press Step or Run all to start Median Cut.');
Result
Console

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 NN, 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.

The Real Complexity

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

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

  • kk-means in 1D is solvable exactly in O(p⋅N2)O(p \cdot N^{2}) time (dynamic programming on a sorted array).
  • kk-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 224≈16 million2^{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 kk-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(plog⁡N)O(p \log N) and uses O(N)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.

Where It Matters

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≈4–8N \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.

Conclusion

Median Cut is a small masterpiece of algorithm design: a problem that sounds hard — choose NN 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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/color-quantization-median-cut/Content licensed under CC BY-NC 4.0.