Median Cut Color Quantization (MMCQ)

Overview

Median Cut Color Quantization is an algorithm used to reduce the number of colors in an image while preserving visual similarity. It is widely used in image processing and color palette extraction.

Modern Colorthief implements a highly optimized version of this algorithm in Rust.

How It Works

The algorithm works by recursively dividing the RGB color space into smaller “boxes” and selecting representative colors.

Algorithm Steps

  1. Collect Pixels – Gather all pixels from the image.

  2. Initial Box – Place all pixels into a single 3D RGB box.

  3. Find Longest Channel – Identify the color channel (R, G, or B) with the largest range within the current box.

  4. Sort – Sort pixels along that channel.

  5. Split – Divide the box at the median point into two sub-boxes.

  6. Recurse – Repeat steps 3-5 until the desired number of color boxes is reached.

  7. Compute Averages – Calculate the average color of each box to form the final palette.

Advantages

  • Simple and Efficient – O(n log k) complexity where n is the number of pixels and k is the target palette size.

  • Visually Good Palettes – Produces colors that well represent the image’s dominant hues.

  • Widely Used – Industry-standard algorithm for color quantization.

Parameters

The quality parameter controls the sampling rate. A higher quality value means fewer pixels are analyzed, resulting in faster execution but slightly less accurate results.

Quality Guide

Quality

Effect

1

Every pixel analyzed (slowest, most accurate)

10

Every 10th pixel (default, balanced)

100

Every 100th pixel (fastest, least accurate)

Reference

Detailed PDF explanation

See also

Benchmarks – Performance benchmarks of the Rust implementation.

API Reference – API reference for get_color and get_palette.