Median-Cut Color Quantizer

Math essence

Median-cut: repeatedly take the bucket with the largest (max - min) along any RGB axis, sort that bucket along that axis, split at the median into two sub-buckets. After `log2(num_colors)` recursive splits, each leaf bucket's mean is a palette color. Mapping each pixel to its nearest palette entry (Euclidean in RGB or Lab) gives a posterized, banded image. The CIE Lab branch uses sRGB->linear->XYZ->Lab gamma correction so perceptual banding (more even luminance steps) is achievable.

Parameters

Reference

First 60 lines of reference.py. Full source: library_external/toxi_openframeworks/ColorQuantizer/reference.py

from __future__ import annotations

from typing import ClassVar

import numpy as np


def _median_cut(pixels: np.ndarray, num_colors: int) -> np.ndarray:
    """Recursive median-cut palette extraction (Heckbert 1982).

    `pixels` is an (N, 3) float array of RGB values in [0, 1]. The
    algorithm repeatedly splits the pixel bucket with the longest
    channel range at its median, producing `num_colors` buckets whose
    per-bucket mean becomes the palette entry.

    This is the same approach Karsten Schmidt uses in the early
    `toxiclibs.color` median-cut demos and now codified in
    @thi.ng/color. Reference: Heckbert, "Color Image Quantization for
    Frame Buffer Display", SIGGRAPH 1982.
    """
    buckets: list[np.ndarray] = [pixels]
    while len(buckets) < num_colors:
        ranges = np.array([b.max(axis=0) - b.min(axis=0) for b in buckets])
        idx = int(np.argmax(ranges.max(axis=1)))
        if ranges[idx].max() <= 1e-6:
            break
        bucket = buckets.pop(idx)
        channel = int(np.argmax(ranges[idx]))
        order = np.argsort(bucket[:, channel])
        bucket = bucket[order]
        mid = len(bucket) // 2
        left = bucket[:mid]
        right = bucket[mid:]
        if left.size == 0 or right.size == 0:
            buckets.append(bucket)
            continue
        buckets.append(left)
        buckets.append(right)
    palette = np.stack([b.mean(axis=0) for b in buckets], axis=0)
    return np.clip(palette, 0.0, 1.0)


class ColorQuantizer:
    """Median-cut color quantizer (Heckbert / toxiclibs).

    A palette is extracted from an evolving procedural image (a
    multi-octave gradient + Perlin-ish noise wash) using the
    Heckbert 1982 median-cut algorithm. The full image is then
    remapped to the closest palette color in CIE Lab space, yielding
    the posterized, banded look that Karsten Schmidt pioneered in his
    early openFrameworks demos and that the `toxiclibs.color` library
    (now `@thi.ng/color`) carries forward. On each `step` the source
    image is regenerated with a slightly different seed so the
    quantized output drifts through palette space over time.
    """

    family: ClassVar[str] = "toxi_openframeworks"
    sketch: ClassVar[str] = "colorquantizer"

    def __init__(