HyAB k-means for color quantization

(30fps.net)

40 points | by ibobev 18 hours ago ago

13 comments

  • mattdesl 17 hours 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

  • refulgentis 17 hours 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.

    • mattdesl 17 hours 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.

      • refulgentis 17 hours 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

        • jcelerier 16 hours ago

          > 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" ?

          • refulgentis 15 hours ago

            > I don't understand how "the perf just doesn't matter"

            Ah, apologies, I don't mean to imply color perf never matters :)

            The paragraph is discussing a color quantization algorithm to extract colors from an image, not color conversion in general. It's very hard in that situation

            > "a minor part of your whole pipeline would take 6 seconds (or even 600 or 60 ms"

            Ah, apologies for the lack of clarity: you don't need to ever convert the entirety of RGB to CAM16 and L*. :) That's just a rough instructive benchmark I can remember.

            If I'm worried about realtime, say, I know I want to convert an 6K* wallpaper with realtime appearance modelling, at 120 fps on 2022 Android, I use a shader. 0 perf issues so far. (knock on wood)

            * now that I think about it...it's probably at display res, not the original 6K. Maybe 2 megapixel? shrugs

        • gardaani 10 hours ago

          > 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...

          • yorwba 8 hours ago

            Oklab is not perceptually uniform. It's better than other color spaces with equally simple conversion functions, but in the end, it was created as a simple approximation to more complex color spaces, so compared to the best you could do, it's merely OK (hence the name).

            • mattdesl 3 hours ago

              > Oklab is not perceptually uniform

              By what metric? If the target is parity with CAM16-UCS, OKLab comes closer than many color spaces also designed to be perceptually uniform.

              • yorwba 3 hours ago

                If the target is parity with CAM16-UCS, CAM16-UCS is best, tautologically. Sure, if you need a fast approximation, by all means fall back to Oklab, but that optimization isn't going to be necessary in all cases.

                • mattdesl 2 hours ago

                  Obviously; but this doesn’t suggest that OKLab is not a perceptually uniform color space.

                  There is no “one true” UCS model - all of these are just approximations of various perception and color matching studies, and at some point CAM16-UCS will probably be made obsolete as well.

        • mattdesl 16 hours ago

          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!

          • refulgentis 16 hours ago

            Because it is a matmul best-effort approximation of a perceptual color space, not a perceptual one, and in my experience that's a significant difference when deployed and for design. YMMV. :)

            I cringe myself, it sounds like a nitpick, but it's an extremely significant upgrade in every case.

            Most concretely, if I use actual L*, design can use palettes linked to L* and vary hue / colorfulness while meeting any contrast standard.