HyAB k-means for color quantization

by ibobev • 1 year ago

47 17 1 year ago

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.

mattdesl6• 1 year ago

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.

refulgentis7• 1 year ago

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

mattdesl6• 1 year ago

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

HyAB k-means for color quantization

Related Stories