HyAB k-means for color quantization
9 comments
·July 9, 2025refulgentis
Highly recommend Celebi's K-Means, weighted square means.
It feeds the results from a box cutting quantizer (Wu) into K-Means, giving you deterministic initial clusters and deterministic results. It leverages CIELAB distance to avoid a bunch of computation. I used it for Material 3's dynamic color and it was awesome as it enabled higher cluster counts.
mattdesl
Surely this would be even faster and potentially better with OKLab? Especially in the context of CIELab based distance metrics like CIEDE2000 which are a bit heavy.
My own gripe with box cutting is that perceptual color spaces tend not to have cube shaped volumes. But they are very fast algorithms.
refulgentis
I am very strongly opinionated on this, but am aware this isn't a very serious matter most of the time. Imagine my tongue in cheek, and a smile, i.e. I'm open to discussion:
Oklab is a nightmare in practice - it's not linked to any perceptual color space, but it has the sheen of such in colloquial discussion. It's a singular matmul that is supposed to emulate CAM16 as best as it can.
It reminds me of the initial state of color extraction I walked into at Google, where they were using HSL -- that is more obviously wrong, but I submit they suffer from the same exact issue: their verbiage is close enough to actual verbiage that they obfuscate discussion, and prevent people from working with the actual perceptual spaces, where all of a sudden a ton of problems just...go away.
</end rant>
In practice, quantizers are all slow enough at multimegapixel that I downscale - significantly, IIRC I used 96x96 or 112x112. IIRC you could convert all 16M of RGB to CAM16 and L* in 6 seconds, in debug mode, in Dart, transpiled to Javascript in 2021, so I try to advocate for doing things with a proper color space as much as possible, the perf just doesn't matter.
EDIT: Also, I should point out that my goal was to get a completely dynamic color system built, which required mathematically guaranteeing a given contrast ratio for two given lightness values, no matter hue and chroma, so trying to use pseudo-perceptual-lightness would have been enough to completely prevent that.
I do still think it's bad in general, i.e. if it was people doing effects on images in realtime, a couple weeks ago I finally got past what I had internally at Google, and was able to use appearance modeling (i.e. the AM in CAM-16) to do an exquisite UI whose colors change based on the lighting naturally. https://x.com/jpohhhh/status/1937698857879515450
gardaani
> Oklab is a nightmare in practice - it's not linked to any perceptual color space, but it has the sheen of such in colloquial discussion. It's a singular matmul that is supposed to emulate CAM16 as best as it can.
Oklab is perceptually uniform and addresses issues such as unexpected hue and lightness changes in blue colors present in the CIELAB color space. https://en.wikipedia.org/wiki/Oklab_color_space
Oklab is used in CSS because it creates smoother gradients and better gamut mapping of out-of-gamut colors than Lab. Here's a picture how Oklch (on the left) creates smoother gamut mapping than CIE Lch (on the right) ("Explore OKLab gamut mapping in oklch"): https://github.com/w3c/csswg-drafts/issues/9449#issuecomment...
jcelerier
> IIRC you could convert all 16M of RGB to CAM16 and L* in 6 seconds, in debug mode, in Dart, transpiled to Javascript in 2021, so I try to advocate for doing things with a proper color space as much as possible, the perf just doesn't matter.
Coming from the "real-time graphics" world, if I read that something which is going to be a minor part of your whole pipeline would take 6 seconds (or even 600 or 60 ms) it would be instantly disqualified so I don't really understand why you'd say "the perf just doesn't matter" ?
mattdesl
It does a pretty good job at emulating CAM16 with a fraction of the parameters, computational complexity, and processing; it’s no wonder it was adopted by CSS.
I don’t know what you mean by “not being linked to any perceptual color space” - it is derived from CAM16 & CIEDE2000, pretty similar in ethos to other spaces like ITP and the more recently published sUCS.
There’s also tons of discussion on w3c GitHub about OKLab, and it’s evolved in many ways since the original blog post such as improved matrices, new lightness estimate and OKHSV/OKHSL, and very useful cusp & gamut approximations.
I have a hard time seeing how it’s a nightmare in practice!
I’ve done some color quantization tests with HyAB and OKLab on this same image. A couple notes:
- what works well for this image might not work well for other images! I learned the hard way after lots of testing on this image, only to find things that did not generalize well.
- parametrizing the AB plane weight is pretty useful for color quantization; I’ve found some images will be best with more weight given to colour, and other images need more weight given to tone. OKLab creator suggests a factor of 2 in deltaEOK[1] but again this is something that should be adjustable IMHO..
- there’s another interesting and efficient color space (poorly named) sUCS and sCAM[2] that boasts impressive results in their paper for tasks like this. Although I’ve found it not much better for my needs than OKLab in my brief tests[3] (and note, both color spaces are derived using CIEDE2000)
[1] https://github.com/color-js/color.js/blob/9d812464aa318a9b47...
[2] https://opg.optica.org/oe/fulltext.cfm?uri=oe-32-3-3100&id=5...
[3] https://x.com/mattdesl/status/1902699888057446670