Why CIELAB doesn’t improve median cut

Color quantization is a process that compresses an image into a color table, or a palette, and an index image that references the palette. The process can be divided into a palette design phase that analyzes an image, followed by a pixel mapping phase that assigns a palette color to each original image pixel.

A classic algorithm for palette design is the median cut algorithm that recursively partitions image colors into two via axis-aligned splits. It can be viewed as a top-down hierarchical clustering algorithm. The algorithm terminates when the requested number of colors have been found; the mean color in each cluster becomes a color in the palette. This result can be further refined with k-means.

Median cut rarely works perfectly without further tweaking, and it’s only natural to consider alternative color spaces in such a situation. CIELAB is the standard choice, in which Euclidean distances are closer to perceptual color differences. Instead of RGB channels, it consists of a lightness channel L^* (nonlinear aka gamma-corrected) and two opponent color channels: the green-red a^* and blue-yellow b^*. And yes, the channels have stars in their names.

(L^*,\,a^*,\,b^*) = \begin{aligned} L^* & : \textcolor{gray}{\text{lightness}} \\ a^* & : \textcolor{green}{\text{green}}-\textcolor{red}{\text{red}} \\ b^* & : \textcolor{blue}{\text{blue}}-\textcolor{orange}{{\text{yellow}}} \end{aligned}

Using it sounds simple: convert each color from sRGB to CIELAB, run your median cut, receive a palette in CIELAB, and map each pixel to a palette color. Too bad it doesn’t help.

Consider the PhotoDemon image editor, of which I learned through its developer’s excellent 1-bit dithering article. The program is open source and I like to dig into code like this in search of clever new palette tricks. The file Palettes.bas has a promisingly named GetOptimizedPaletteIncAlpha_LAB function. But reading its comment, we see the code goes unused. Emphasis mine:

[–] Analysis is done in LAB color space, for slower but potentially better results. That said, internal testing shows that this produces results that don’t “look as good” as traditional methods.

Huh. The comment continues with a hint, emphasis still mine:

[–] I’m not sure why - it’s possibly caused, in part, by not weighting L more aggressively than A/B [–] As such, PD doesn’t use this function at present, but it may be useful in the future if I have more time to refine it.

Alright. Perhaps we need to weight the lightness channel L^* more, but how much more? And why would that help, exactly?

The GIMP goes LAB

In February 2024, GIMP’s palette builder feature got upgraded. In the relevant source file, we can see how they turned to the babl library for sRGB to CIELAB conversion:

gfloat rgb[3] = { r / 255.0, g / 255.0, b / 255.0 };
gfloat lab[3];

babl_process (rgb_to_lab_fish, rgb, lab, 1);

The resulting floating point CIELAB color is converted into what they call the “box-space” 8-bit integer coordinates. It’s done by biasing and scaling with per-channel constants:

or = RINT(lab[0] * LRAT);
og = RINT((lab[1] - LOWA) * ARAT);
ob = RINT((lab[2] - LOWB) * BRAT);

Confusingly, they kept the “RGB” variable names even though the contents are now actually (L^*, a^*, b^*). The floating point CIELAB values are centered, scaled, and rounded to integers. The offset and scaling factors are defined in the same file:

#define LOWA   (-86.181F)
#define LOWB  (-107.858F)
#define HIGHA   (98.237F)
#define HIGHB   (94.480F)

#define LRAT (2.55F)
#define ARAT (255.0F / (HIGHA - LOWA))
#define BRAT (255.0F / (HIGHB - LOWB))

I believe these numbers were chosen just to use the full 8-bit range of all components. However, if we normalize the opponent-color channels’ respective factors ARAT and BRAT with the lightness component’s LRAT, we get about ½ in both:

LRAT = 2.55
ARAT = 1.3827283670791355
BRAT = 1.2602674732378494
ARAT/LRAT = 0.5422464184624061  <-- both roughly 0.5
BRAT/LRAT = 0.49422253852464687 <--

We could say that in GIMP’s color quantizer, the L^* channel is multiplied by two, relatively speaking. (It can go temporarily even higher when the color count is 16 or less.) Why not try this ourselves?

Scaling lightness

The test image today is the venerable “hats” by Don Cochran:

I quantized the image to 16 colors via median cut in different color spaces. I’m interested only in the resulting palette, so I used Oklab for the final pixel mapping step. Traditionally, median cut always splits the cluster with the most colors in it, but this variant picks the cluster with the largest per-axis variance. It’s also how the split axis is chosen.

Converting this photo to 16 colors will look rough, no matter the method. Dithering would, of course, improve the quality but I think it’s easier to see differences in palettes without it. (I also haven’t added it to my color quantizer application.)

Okay so below we have the image quantized in CIELAB without (left) and with (right) lightness channel scaling. The difference is quite small but at least the clouds no longer have a yellow blotch on the right. Scaling lightness by two does seem to help.

But CIELAB was supposed to be superior to sRGB, remember? Looking at the good old sRGB’s result below, it’s hard to make a case for CIELAB, scaled L^* or not:

So far it looks like CIELAB doesn’t improve the palette median cut generates, but I did the pixel mapping step in Oklab; admittedly an unorthodox choice. Usually median cut and pixel mapping are done in the same space.

Perhaps it’s only pixel mapping that should be done in a perceptual space? I mean, it’s literally about comparing color distances, unlike the median cut that involves per-axis sorting and color averaging.

Below is some evidence to support this point. The image on the left is again processed in sRGB but now also with sRGB pixel mapping. I suppose this is the baseline to which most people compare their alternatives to, and while not a failure, the green hat appears way too dim. On the right, processing is sRGB but pixel mapping is done in lightness-scaled CIELAB instead. To me this looks good, on-par with Oklab pixel mapping above.

My theory is that developers switching to CIELAB in their median cut implementations see an improvement because a perceptual color space makes pixel mapping more accurate. The hierarchical splitting itself works just as well in sRGB. In fact, in the axis-aligned splits that median cut does, a perceptual space can even be a hindrance.

What happens in an axis-aligned cut

Recall that the median cut chooses a cluster to split, finds the axis that has most variation, and finally splits the cluster in the middle into two new smaller clusters. This always reduces error because the cluster colors are now represented with two values (new cluster means) instead of one (the old mean).

Think about an axis-aligned cut in sRGB. The RGB channels are correlated with each other, but also with the color’s lightness (CIELAB’s L* channel) approximately with per-channel weights of (0.299, 0.518, 0.183). As a consequence, each time a cluster is split on the R, G, or B axis, lightness error also goes down.

Even in an uncorrelated color space like CIELAB, a cut on the a^* or b^* axis often reduces error in lightness. For example, if a cluster contains dark greens and bright reds, a median cut on the green-red a^* axis will also happen to reduce lightness variance in both new clusters. I suspect this is why even a tiny lightness scale of 0.05 works surprisingly well, see the result:

You could even argue that with only 16 colors, this is the best result for such a colorful source image. (I wouldn’t agree since the magenta cap turned red). Still, it’s useful to be able to adjust the lightness scale separately from color. I think the lightness-vs-colorfulness tradeoff is a big factor in how “high quality” the results look, and that’s why I did some measurements.

The graph below characterizes how eager each color space is to minimize lightness error. The X-axis represents median cut’s splits as it works its way through clusters until all palette colors have been found. The Y-axis shows the sum of squared lightness errors of the whole image, measured as CIELAB’s L^*.

The lines go down as expected, but see how the blue sRGB line remains lower than the dashed green CIELAB line. This tells us sRGB prioritizes lightness error much more than a stock CIELAB. When CIELAB’s L* channel is multiplied by two (the dashed red line), the error finally goes down faster than in sRGB. I believe the low lightness weight is the main reason why median cut doesn’t work better in unscaled CIELAB than in sRGB.

The orange “Weighted sRGB” line is a commonly taken shortcut: sRGB multiplied by weights (w_R, w_G, w_B), where w_G > w_R > w_B. Here I used ExoQuant’s (1, 1.2, 0.8). It’s clear from the graph that this approach works but it’s harder to control for an exact lightness-vs-colorfulness tradeoff.

The case of Oklab

I also included Oklab in the above graph, and it pulls the lightness error lowest of them all. Like CIELAB, it consists of a lightness and two opposite-color channels, this time mercifully called just L, a, and b. It also makes median cut weight lightness so much the result looks like a 70’s Polaroid:

Oklab’s behavior is easy to explain: its L channel’s relative value range is big when compared to those of a and b. Based on the below histogram, I’d say Oklab’s L-vs-ab-range ratio is about 3x greater than CIELAB’s. (In sRGB, all channels span the [0..255] range, of course.)

In summary, a perceptual color space works best for median cut’s axis-aligned splits if its lightness component range is greater than the ranges of its “a” and “b” components. But the difference shouldn’t be as large as in Oklab. It also seems more important to do pixel mapping in a perceptual space than to change the space in which the median cut is done in.

In the end I did end up learning some neat tricks from my encounter with PhotoDemon:

• Make sure a palette always has pure black and pure white present.
• Pixel mapping can be accelerated by reusing a color index in areas of solid color.
• Most popular palette colors should come early in the palette (PCX format) or appear at power-of-two indices (PNG) for better compressibility.
• It uses RGBA weights of (0.33, 0.42, 0.25, 0.75) :)

I’m writing a book on color quantization. Sign up here if you’re interested.

---

Mastodon Bluesky YouTube Feed

30fps.net