Dominant Color Extraction: k-Means, Median Cut, and ML

Upload a sunset photo, receive five hex swatches labeled dominant colors. The interface feels instantaneous. The work underneath is decades of computer graphics research compressed into a JavaScript loop or WASM module running while you wait. Dominant color extraction is not one algorithm. It is a family of strategies for summarizing a high-dimensional pixel distribution with a small palette humans find representative enough to steal for UI design.

Tooling marketed as palette from image usually implements k-means clustering, median cut popularized by Paul Heckbert’s 1982 color quantization work, or hybrids of both. Newer products may add learned embeddings from convolutional networks, though most browser-side tools still run classical clustering for latency, bundle size, and explainability. This essay explains how those approaches work, why RGB clustering biases toward muddy neutrals, when OKLCH helps, what post-processing every serious tool runs, and what machine learning changes without inventing citations that do not exist.

The problem as data reduction

A 1920 by 1080 image contains roughly two million pixels, each with RGBA channels. Many pixels are near-duplicates. Sky gradients differ by single byte steps across thousands of samples. Dominant color extraction asks a simpler question: find k representative colors, typically five to ten, such that the palette covers the image visual diversity while staying small enough for UI swatches.

Formally, you choose k cluster centers in color space and assign every pixel to the nearest center under a distance metric. Quality depends on the color space you cluster in, whether RGB cube or a perceptual space like Oklab. It depends on the distance metric, Euclidean or weighted toward chroma. It depends on initialization, random or seeded from histogram peaks. It depends on k selection, fixed or adaptive. It depends on post-processing: merge similar clusters, sort by area, clamp to sRGB gamut.

No single method wins on all images. Sunsets stress hue circularity. Product shots on white stress background dominance. Neon street photography stresses high-chroma accents against large dark regions. The algorithm you choose encodes assumptions about what dominant means, and those assumptions leak into every swatch your users copy into Figma.

k-means clustering and its RGB bias

k-means is the default workhorse. Lloyd’s algorithm alternates two steps. First, assign each pixel to the nearest of k centroids by Euclidean distance in the chosen color space. Second, update each centroid to the mean of assigned pixels. Repeat until convergence or an iteration cap, typically twenty passes.

Raw k-means on two million pixels is slow for browser main threads. Production tools downscale the image to 150 through 300 pixels on the longest edge before clustering. They subsample pixels, taking every fourth pixel or a random fifty-thousand sample. They quantize channels to five bits per channel before clustering to collapse near-duplicates. They run the heavy loop in a Web Worker or WASM for UI responsiveness.

Random centroid initialization collides on unimodal images where the entire frame is sky. k-means++ spreads initial centers probabilistically by distance from existing picks, improving convergence and reducing empty clusters. Most mature libraries use it by default.

Human vision is not Euclidean in RGB. The RGB cube stretches perceptually. Equal steps in green do not equal equal steps in perceived brightness across hues. When k-means averages many pixels, gray mixtures dominate area in typical photographs because shadows, pavement, and haze occupy enormous pixel counts. The mean of diverse hues desaturates toward brown-gray mud, the classic averaging colors is ugly demonstration. Chroma is underweighted, so a small red accent and a large gray field may yield a gray centroid that misrepresents the vibe a designer wanted.

A forest photo with green canopy, brown trunks, and a blue sky slice illustrates the failure. RGB means pull toward yellowish gray that matches neither foliage nor sky. The result is fine for average pixel statistics and poor for brand palette inspiration. Sorting clusters by pixel count surfaces backgrounds first. Designers often want saturated accent clusters ranked higher even when area is small, which requires post-rank heuristics like chroma times area score.

function kMeansRGB(pixels, k, maxIter = 20) {
  let centroids = initCentroids(pixels, k);

  for (let iter = 0; iter < maxIter; iter++) {
    const clusters = Array.from({ length: k }, () => []);

    for (const px of pixels) {
      let best = 0;
      let bestDist = Infinity;
      for (let i = 0; i < k; i++) {
        const d = distRGB(px, centroids[i]);
        if (d < bestDist) { bestDist = d; best = i; }
      }
      clusters[best].push(px);
    }

    let moved = false;
    for (let i = 0; i < k; i++) {
      if (clusters[i].length === 0) continue;
      const next = meanRGB(clusters[i]);
      if (distRGB(next, centroids[i]) > 1) moved = true;
      centroids[i] = next;
    }
    if (!moved) break;
  }
  return centroids;
}

Median cut and perceptual color spaces

Median cut, described in Paul Heckbert’s foundational work on color quantization for frame buffer display at SIGGRAPH 1982, recursively splits color space along the channel with widest range. Place all pixels in one box representing the RGB volume. While you have fewer than k boxes, split the box with largest channel span at the median along that channel. Each final box’s representative is typically the mean or median color of contained pixels.

Median cut respects histogram structure better than random k-means initialization on some images. It finds distinct color masses like a sky band and a skin tone band without iterative optimization. Trade-offs are structural. k-means produces roughly spherical clusters in its distance metric and requires iteration. Median cut uses greedy axis-aligned splits in RGB and runs in predictable time. k-means may merge thin accent colors. Median cut may split them across boxes awkwardly. Axis-aligned boxes in RGB do not correspond to warm versus cool in human terms. Still, median cut remains common in image processing toolchains because it is deterministic and fast.

Perceptually uniform spaces improve clustering for design palettes. Convert pixels from sRGB through linear light to OKLab or OKLCH, following Björn Ottosson’s Oklab model now available in CSS as oklch() per CSS Color Module Level 4. Run k-means on L, a, b coordinates or on L, C, h with care for hue wraparound.

Distance correlates better with looks similar. Lightness averaging separates shadows from highlights more cleanly. Chroma can be weighted in the distance metric to favor vivid accents. Conversion cost per pixel is modest at fifty-thousand subsample scale. Hue is circular. Clustering on raw hue angle without handling wrap splits reds at 350 degrees versus 10 degrees incorrectly. Use the a,b plane or sin-cos hue encoding. Out-of-gamut OKLCH centers must clamp on export to sRGB hex.

function distOklab(a, b) {
  const dL = a.L - b.L;
  const da = a.a - b.a;
  const db = a.b - b.b;
  return dL * dL + 1.5 * (da * da + db * db);
}

For UI token inspiration, OKLCH k-means typically produces more usable neutrals and accents than RGB k-means on the same photo. Less mud lands in the sixty percent area cluster. That improvement is not magic. It is geometry. You stopped averaging in the wrong cube.

Machine learning and honest limits

Machine learning does not replace clustering everywhere. It changes what is being clustered. Convolutional networks trained on image classification produce feature vectors per image region or per patch. Clustering runs in embedding space where dimensions encode semantic texture and object type, not raw wavelength. Two blue pixels from sky and painted wall may separate because embeddings capture context.

Browser palette tools rarely ship full ResNets client-side. Latency and bundle size push ML to server APIs that return palette labels, tiny models via ONNX Runtime Web, which remains uncommon for palette-only features, or hybrid pipelines where ML predicts salient regions and classical clustering runs only on those pixels. Some research and product pipelines train models to predict harmonious palettes directly from images. These can outperform k-means on aesthetic ratings in user studies, but models are proprietary, training data defines bias, and WCAG contrast is not guaranteed unless explicitly optimized afterward.

Do not cite fake papers. The honest statement is that ML palettes exist in commercial tools and academic colorization literature. Exact architectures vary. Failures are less explainable than centroid math. ML helps most on busy scenes where saliency should ignore background parking lots, on fashion and product photography where brand color is the object not the backdrop, and on style transfer workflows suggesting coordinated accents. ML hurts when users need reproducibility, offline tooling, or audit trails. k-means with a fixed seed wins those cases.

Post-processing and from palette to tokens

Raw centroids are not shipped directly to users. Serious tools merge clusters within a delta-E threshold in Lab to eliminate near-duplicate swatches. They drop clusters below an area threshold to remove noise speckles. They boost chroma slightly for UI preview because designers want punchier output than literal mean colors provide. They sort by area, luminance, or chroma depending on UX goals. They name colors via nearest CSS keyword or a color naming API, which is cosmetic but helps communication.

Contrast-checking suggested text-on-swatch pairs is often omitted in fun palette generators. Professional handoff tools should flag pairs that fail WCAG 2.2 contrast minimum. Fixed k equals five is arbitrary. Adaptive methods include elbow method on within-cluster variance, which is heavy for browsers, Heckbert-style target box count from unique color estimates, or a user slider from three to twelve clusters.

Alpha channels require deliberate handling. Composite transparent PNGs onto white or a user-picked backdrop before clustering. Clustering raw transparent pixels pollutes results with premultiplied fringe colors from anti-aliased edges.

Dominant colors are candidates, not tokens. Photography palettes need role assignment, OKLCH ramps, neutral derivation, and contrast matrices before production. Extraction answers what hues appear. Semantics answer what is accent-subtle. If you implement extraction yourself, start with k-means++ on OKLab, fifty-thousand sample, k equals six, merge clusters within delta-E below two, downscale longest edge to 256 pixels, document color space in API responses, and expose a seed for reproducibility. If you evaluate tools, ask which algorithm and space they use, test the same photo across vendors because variance reveals hidden heuristics, and check whether output is literal dominant or enhanced for design.

JPEG artifacts deserve explicit mention because they create fake clusters. Quantization noise along block boundaries produces micro-clusters of near-identical gray-beige values that steal a k slot from a meaningful accent. Pre-filtering with a mild blur before clustering, or merging clusters with centroids within a tight distance threshold after clustering, mitigates the problem. Some tools run median cut first to establish coarse regions, then k-means within each region for refinement. Hybrids exploit the strengths of both families without requiring users to understand either algorithm name.

Choosing between building and buying extraction depends on your product surface. A design tool adding palette suggestions needs reproducibility, documented color space, and sub-second latency on mid-tier laptops. A marketing microsite that calls a server API once per hero image can afford heavier pipelines. Document the algorithm in API responses. Designers comparing output across sessions notice when Tuesday’s upload returns different swatches than Monday’s for the same file because initialization was random and no seed was exposed.

The path from extracted palette to production tokens mirrors any other color sourcing workflow. Take the fifth-ranked OKLCH swatch, assign it as accent candidate, generate a chroma ramp by holding hue and stepping lightness, derive neutrals by desaturating and aligning hue to your brand anchor, then run the contrast matrix before committing --accent in your token file. Extraction accelerates inspiration. It does not replace judgment. A sunset orange belongs in a travel app hero, not necessarily in error state red, even if it ranked second by pixel area.

Comparative testing across tools reveals hidden heuristics quickly. Run the same product photograph through three palette generators. If one returns muted literal means and another returns boosted chroma previews, you know post-processing differs even when both claim k-means. If one ignores the white studio background and another includes it as the dominant swatch, you know saliency or masking differs. Transparency in marketing copy about enhancement versus literal extraction builds trust with professional users who paste swatches into client deliverables.

k-means in RGB is the fast naive baseline. Median cut is the deterministic cousin from quantization literature. OKLCH clustering is the designer-aligned upgrade. ML adds semantic attention when classical math averages the parking lot with the product. Know which pipeline you are using. Muddy neutrals are usually a space and weighting problem, not a mystery. Fixing them starts with stopping Euclidean averaging in the wrong cube and remembering that the palette your tool returns is a compression of two million opinions, not a brand guideline until you run it through the same token discipline you would apply to any other color decision. The algorithms are teachable. The failure modes are predictable. The gap between a fun swatch row and a shippable token file is everything your design system already knows how to do. Teach your team which pipeline powers your product feature and the muddy swatch complaints become actionable bug reports instead of mystical disappointment about the algorithm being wrong.