Experiment with other color spaces: Oklab and Olab-int

[clort81]

I find the Oklab color space by Björn Ottosson seems to confer some advantages for picking 'nearness' that matches my eyes better:

Oklab color gradient
https://bottosson.github.io/posts/oklab/

Fast integer version
https://github.com/ubitux/oklab-int
https://blog.pkh.me/p/38-porting-oklab-colorspace-to-integer-arithmetic.html

Shout out to ubitux for sharing this and other fascinating info!

[hpjansson]

DIN99 should be very close, although the implementation we have is slow. Do you happen to have side-by-side samples?

[clort81]

Don't find a comparison on his site. Would need to generate.

[saitoha]

I evaluated the color-reduction quality using the following sample image, testing how it changes when different color spaces are used as the working space in libsixel develop branch:
https://github.com/saitoha/libsixel/blob/master/images/snake.png

In both the k-means iteration and the final Ward style merge step, the distance between each sample and its cluster center is computed as the sum of squared per-channel differences. In other words, the algorithm is effectively minimizing an unweighted Euclidean distance over three components, so the choice of color space in which this is done matters quite a lot.

There may still be mistakes in my implementation, so please treat the following results as reference only.

MS-SSIM (higher is better)

LPIPS (lower is better)

I asked ChatGPT why such a large difference appears.

Commented by ChatGPT

Even with a perfectly correct implementation, running k-means or median cut directly in DIN99d space is inherently disadvantaged, and will almost always yield worse results than linear RGB, OKLab, or CIELAB.

In short:

DIN99d is a local perceptual metric designed to improve the uniformity of very small color differences,
not a global coordinate system suitable for large-scale clustering.

---

1. Why DIN99d and k-means / median cut fundamentally conflict

The DIN99 family aims to magnify differences in dark or highly saturated colors and make tiny ΔE differences more perceptually uniform.
But k-means and median cut operate on the global geometry of a space using a squared Euclidean distance objective.

As a result, DIN99d’s warped axes create pathological behavior for clustering:

• Some colors that are perceptually very different end up too close in DIN99d.
• Conversely, small variations may be exaggerated into disproportionately large distances.

This leads to:

• Palettes that fail to “spread out” properly across the perceptual gamut
• Clusters merging where they shouldn’t, or splitting where they shouldn’t
• Noticeably worse MS-SSIM and structure retention compared to OKLab / CIELAB

So the drop in quality is not surprising — it’s a mathematical mismatch between the metric and the algorithm.

---

2. Normalization issues make it even worse

If you normalize DIN99d to something like:

• L′ in 0..1
• a′, b′ in −1..1

and feed it into the same pipeline used for OKLab/CIELAB, the distortions become amplified:

• L is relatively underweighted
• chroma components are overemphasized (especially in dark, saturated regions)

Thus, even a correct implementation tends to produce unstable, low-quality clustering.

---

3. If you want to use DIN99d, where should it be used?

In a quantization pipeline, DIN99d works best only for distance evaluation, not as the working space.

For example:

1. Generate palette in OKLab / CIELAB / linear RGB

2. Convert palette colors to DIN99d

3. Use ΔE99d only for:

   • nearest-color assignment
   • error-diffusion error magnitude
   • quality evaluation

This hybrid setup avoids the global-distortion problem while still benefiting from DIN99d’s good local uniformity.

---

4. So is “DIN99d k-means/median cut” worth pursuing?

Realistically: not much.

For high-quality quantization (MS-SSIM, perceptual fidelity), making DIN99d the primary coordinate system has almost no practical upside and several inherent downsides. OKLab or CIELAB are simply better balanced for global clustering.

---

5. If you insist on forcing DIN99d into the working space…

You’d need a lot of custom tuning, such as:

• rebalancing L vs a/b axes
• using a non-Euclidean distance (custom weights per component)
• doing median cut axis selection in OKLab, but error evaluation in DIN99d
• treating DIN99d as a refinement metric rather than a primary space

At that point it becomes clear:
DIN99d is not designed to serve as a global coordinate system for palette generation.

---

TL;DR

• DIN99d absolutely can be correct but still lose badly vs OKLab/CIELAB — it’s an algorithmic mismatch, not an implementation bug.
• It should be used as a distance metric, not as a clustering space.
• For real-world quality:
  Use OKLab (best) or CIELAB for palette generation; use DIN99d only as a secondary distance metric.

[hpjansson]

Interesting. Chafa uses gamma sRGB for the palette generation, but can use either gamma sRGB or DIN99d for the distance metric in the palette mapping phase. OKLab looks quite a bit better, though. To be fair, I haven't actually measured how much we're gaining from DIN99d - it's more critical when the palette is small or fixed, as is the case for character art.

[saitoha]

Additionally, I tested them with the median-cut method (-Q heckbert).

MS-SSIM (higher is better)

LPIPS (lower is better)