Median Cut Color Quantization, Explained

## Why it matters

The naive approach, rounding every pixel to a fixed grid, wastes palette slots on colours nobody uses and merges ones that matter. Median cut adapts to the actual image: it spends splits where the colours are, so a photo of a sunset keeps its oranges instead of collapsing them into one brown.

Heckbert published it in 1982 and it still underpins most "dominant colour" tools today. It is fast, deterministic (same pixels in, same palette out every time), and produces palettes that look balanced across almost any image type.

## How it works

Start with all pixels in one box in RGB space. Repeatedly split the box with the largest population along its longest axis, at the median of that axis's values. Stop when you have the number of palette entries you want.

Here is the split rule in more detail:

1. Find the box with the most pixels.
2. Find its longest axis (largest difference between min and max values).
3. Sort the pixels along that axis.
4. Cut at the median point, creating two boxes.
5. Repeat until you have enough boxes.

Why the median and not the mean? The median guarantees that both resulting boxes have roughly equal population, which keeps them compact and representative. It also ensures that every split genuinely splits the colours, rather than wedging one outlier away.

Once you have all your boxes, compute the average colour of each box. That average is your palette entry. A 16-colour palette means 16 boxes, 16 averages.

## What does not matter

Median cut is not the only quantisation algorithm. K-means clustering and octree methods can produce good palettes too. Median cut is fast and deterministic, which makes it ideal for tools like Scalpel Color where you want instant results. Octree is simpler to implement but can miss subtle colours. K-means is flexible but slower. For most real-world use, median cut is "good enough" and much faster.

The order of splits is deterministic but depends on pixel order, so two scans of the same image at different scroll positions or zoom levels might produce slightly different palettes if the visible pixels differ. This is not a flaw; it is a feature. You get the actual palette of what you see, not a random seed-dependent result.

## Code example

// Pseudocode: the median cut algorithm
function medianCut(pixels, targetColours) {
  const boxes = [{ pixels }];
  
  while (boxes.length < targetColours) {
    // Find the box with the most pixels
    const largestBox = boxes.reduce((a, b) => 
      a.pixels.length > b.pixels.length ? a : b
    );
    
    // Find the longest axis (R, G, or B)
    const longestAxis = findLongestAxis(largestBox.pixels);
    
    // Sort by that axis and cut at the median
    const sorted = largestBox.pixels.sort((a, b) => 
      a[longestAxis] - b[longestAxis]
    );
    const mid = Math.floor(sorted.length / 2);
    
    // Split into two boxes
    const box1 = { pixels: sorted.slice(0, mid) };
    const box2 = { pixels: sorted.slice(mid) };
    
    boxes.splice(boxes.indexOf(largestBox), 1, box1, box2);
  }
  
  // Convert each box to an average colour
  return boxes.map(box => averageColour(box.pixels));
}
Copy

Real implementations handle edge cases: empty boxes, ties in axis length, pre-computed statistics for speed. But this captures the core idea.

## How Scalpel Color shows it

Open the Palette tab. The "Scan visible page" button captures the screen, then applies median cut to reduce thousands of pixels to a handful of dominant colours. The colour-count slider on the left side (typically 5, 10, or 16) controls how many boxes the algorithm splits into. Higher counts give you more variety; lower counts give you the true essentials.