How color extraction turns an image into a color palette

Color extraction reduces an image to a small set of representative colors, called a color palette. Computer graphics calls the same process color quantization, the process of reducing an image to a small set of colors. Each palette color stands for a cluster of similar pixels.

Color quantization began as a display problem. At SIGGRAPH '82 in Boston, Paul S. Heckbert showed that images needing a 15-bit-per-pixel frame buffer can be quantized to 8 or fewer bits per pixel with little perceived loss. His method has four phases:

1. Sample the color statistics of the image.
2. Choose a colormap, the set of output colors.
3. Map each color to its nearest colormap entry.
4. Quantize the image, optionally with dithering.

A palette extractor runs the first two phases, and the chosen colormap is the color palette. Median cut, k-means and octree differ in how they choose that colormap.

Median cut splits color space into boxes that hold roughly equal numbers of pixels, and each box yields one palette color. In Heckbert's original method, the box with the most pixels is split along its largest axis, leaving half of its pixels on each side. Heckbert suggests choosing the split axis by side length or by pixel variance along that axis.

Median cut has one known weakness: low-density regions of color space end up in very large boxes, which produces large color errors there.

What does modified median cut (MMCQ) change?

Modified median cut quantization (MMCQ) is Dan Bloomberg's variant of median cut in the Leptonica image library. MMCQ chooses the first 85% of box splits by pixel population alone and the remaining splits by population multiplied by box volume. Bloomberg's report states that this gives visually significant colors a representative even when their population is small.

MMCQ samples about 100,000 pixels and keeps 5 significant bits per RGB channel, so its histogram has 2^15 (32,768) cells and each cell covers 512 original colors.

How does Color Thief use MMCQ?

Color Thief, an MIT-licensed JavaScript library by Lokesh Dhakar, extracts colors with a TypeScript port of MMCQ that uses a population fraction of 0.75 instead of Leptonica's 0.85. Its colorCount option defaults to 10 colors (range 2 to 20), and its quality option samples every 10th pixel by default.

K-means clustering places k cluster centers in color space and moves each cluster center to the mean of the pixels closest to it. The standard procedure is Lloyd's algorithm, published by Stuart P. Lloyd in IEEE Transactions on Information Theory in 1982:

1. Choose k starting cluster centers, typically at random from the data points.
2. Assign every pixel to its nearest cluster center.
3. Move each cluster center to the center of mass of its assigned pixels.
4. Repeat steps 2 and 3 until the result stabilizes.

The algorithm lowers the k-means objective φ, the sum of squared distances from each pixel to its nearest cluster center:

φ = Σ over all pixels x of min over centers c of ‖x − c‖²

Finding the exact minimum of φ is NP-hard, even with two clusters, so Lloyd's algorithm settles in a local minimum. A cluster center is a mean, so the extracted color can match no pixel in the image.

How does k-means++ choose starting centers?

K-means++ picks each new starting center with probability proportional to D(x)², the squared distance from point x to the nearest cluster center already chosen. David Arthur and Sergei Vassilvitskii of Stanford call this rule "D² weighting".

P(x) = D(x)² / Σ D(x′)²

Their paper proves that the expected φ is at most 8(ln k + 2) times the optimal φ for any data set, and it reports that the seeding improves both the speed and the accuracy of k-means. The scikit-learn KMeans class uses k-means++ as its default init.

Octree quantization adds pixels to an octree one at a time and merges its leaves once the color table reaches its limit. M. Gervautz and W. Purgathofer designed the method, and Glassner's Graphics Gems I (1990) summarizes it. Leptonica groups practical adaptive quantizers into three families (popularity, median cut and octree) and notes that octree merges regions of color space as well as splitting them.

The color space defines the distance between two colors, and every color quantization algorithm groups pixels by that distance. A color space that does not track perception merges colors that look different and separates colors that look alike.

Why are RGB and HSL distances misleading?

RGB spaces are not perceptually uniform: CSS Color 4 notes that a ray of constant hue and constant lightness is a curved path in RGB space. HSL, a cylindrical form of sRGB, carries the same problem.

How do CIELAB and ΔE measure color difference?

CIELAB, created by the CIE in 1976, is intended to be perceptually uniform, and the Euclidean distance between two CIELAB colors is ΔE*ab. A ΔE*ab of about 2.3 equals one just-noticeable difference (JND), according to Sharma and Trussell (1997). CIELAB is only approximately uniform, so CIEDE2000 (ISO/CIE 11664-6:2014) corrects the difference for lightness, chroma, hue and chroma-hue interaction. CSS Color 5 states that a ΔE2000 of 1 or more is just visible, and 5 or more is a different color.

Why does OKLab suit color extraction?

OKLab is a perceptual color space for image processing that Björn Ottosson published on 23 December 2020. Ottosson names hue prediction, especially of blue hues, as the largest weakness of CIELAB. OKLab is optimized to predict lightness and chroma closer to the CAM16-UCS model.

Ottosson notes that this comparison does not show which model matches human perception. CSS Color 4 credits OKLab with better hue linearity, hue uniformity and chroma uniformity than CIE LCH, and it defines ΔE_OK as plain Euclidean distance in OKLab:

ΔE_OK = √((L₁ − L₂)² + (a₁ − a₂)² + (b₁ − b₂)²)

K-means minimizes squared Euclidean distance, so k-means in OKLab groups pixels by ΔE_OK without extra correction terms.

Tools return different palettes from the same image because each tool samples, bins, clusters and reports colors in its own way.

Color Palette Extractor extracts colors with weighted k-means++ clustering in OKLab, entirely in the browser. The image is decoded on the device and never uploaded.

1. 01

   Sample the image

   The image is sampled at up to 1024 px on the longest side with nearest-neighbor sampling, so every sampled pixel is a real pixel. Pixels under 50% alpha are ignored.

2. 02

   Build a histogram

   Pixels go into a 5-bit-per-channel histogram with 32,768 bins, and each bin keeps its mean color in OKLab.

3. 03

   Cluster in OKLab

   Weighted k-means++ clusters the bins in OKLab with a fixed seed, so the same image always returns the same color palette. Clustering stops after 20 iterations or when no cluster center moves more than 0.001.

4. 04

   Merge near-duplicates

   Clusters closer than ΔE_OK 0.03 merge.

5. 05

   Pick the final colors

   One of three modes (Dominant, Balanced or Vibrant) chooses the final colors.

6. 06

   Assign every pixel

   Every pixel is assigned to its nearest final color, so the pixel shares add up to 100%.

7. 07

   Report the swatch value

   The swatch value is the real pixel color nearest the cluster center (exact) or the cluster mean (average).

Several images are weighted equally, so one large photo does not drown out a small one.

How do Dominant, Balanced and Vibrant modes differ?

• Dominant picks the clusters with the largest pixel share.
• Balanced, the default mode, picks each next color by the score below, so small accents survive.
• Vibrant weights the same score by OKLCH chroma, so saturated colors rank higher.

score = √(pixel share) × ΔE_OK to the nearest color already picked

The square root reduces the lead of very large clusters, and the distance term rewards colors that differ from the ones already in the color palette.

How does logo mode handle flat colors?

Logo mode in the Logo Color Extractor counts exact colors instead of clustering them. It removes a background that covers at least 60% of the image border. It also drops anti-aliasing blends: edge-only colors whose RGB values lie on the mixing line between two major colors.