Show HN: High End Color Quantizer

[big-nacho]

This is a personal project I've been working on for a long time now.

I stumbled upon the color quantization problem while doing something related for work. I then found an interesting paper for which I could find no implementations online, and the thing went from "let's implement this paper" to getting pretty obsessed with the whole thing.

It's at an early, eaaaarly stage. There's a lot of work to be done, and it's a memory hog, but generally speaking works quite well, and the output is for the most part very high quality, so I'm happy to share it as beta.

[bmn__]

> eaaaarly stage […] beta

If your goal is for users to adopt the use of the software, then you can easily increase acceptance by going the proverbial extra mile:

1. Make it installable via `uv tool install patolette` with the optimisations taken care of automatically. 2. Compare its results in the documentation/on the project Web site against the incumbents. https://news.ycombinator.com/item?id=26646035 Find standard test images https://ddg.gg/?q=color+quantization+test+corpus , copy the split-image/slider technique from https://uprootlabs.github.io/poly-flif/

The rationale for this is that each interested user should not have to replicate this work on his own.

[ansgri]

What's the primary use case you had in mind here? In the example I see it generating a palette of 256 colors and then using them, but it doesn't seem to correspond to any modern use case. AFAIU one currently needs dithering either as part of print/display process (but then you have a fixed palette), or for compression, but I think this makes sense nowadays only with very low color count, like 16 max?

[qingcharles]

I'm always interested in ways to increase the quality of GIF rendering. There are absolutely tons of places that still need GIF support, either because they don't allow video uploads, or because the videos don't auto-play.

Gifski uses the png-quant library, and I wonder how this compares?

[CamperBob2]

Also, dithering and color quantization are two vastly different operations on two different data types in two different domains that don't belong in the same topic at all.

Still, color quantization is a really interesting rabbit hole to go down if you're new to graphics programming, or at least it was for me. It's a mixed blessing that almost nobody has to confront the problem anymore.

[Lerc]

For just about any obsolete desktop computing solution there's almost always an embedded application somewhere doing the same thing today.

Colour quantisation is still one of the best lossy image compression formats for when you have almost no memory or CPU.

[pk-protect-ai]

Oh, there are still several use cases to consider. It is still related to compression pretty much and there some niche non-obvious use cases for this quantization.

[pixelpoet]

This doesn't seem to be gamma correct, I just see / 255 and * 255.

sRGB is a nonlinear colour space and so you can't do linear operations in that space (because a^2 + b^2 isn't (a+b)^2 in general).

[big-nacho]

Gamma aware operations happen in the C code. The python code you're referencing is just changing the scale of color intensities. What you shouldn't do is liberally add up sRGB colors, take averages and generally do any math on them unless you're aware of the non-linearity of the space.

[dinfinity]

The example image only shows the differences between parts of the image that are deemed as salient, but does not show the effects of the tradeoff on the non-salient parts nor does it show an entire quantized image.

I'd say that showing full example results are the most important part of showcasing a "high end" color quantizer.

[big-nacho]

Yeah, good point. I'll definitely add an image showing the saliency map tradeoff.

Regarding full examples, because some other projects seem to have cherry picked cases where they perform very well, I wanted to go for a "try it out yourself" approach, at least for now. Maybe in the future I'll add a proper showcase. Thanks for the feedback :)

[SillyUsername]

Can this also do quantizations like median cut?

Does it also support colour spaces other than RGB, CIEDE (I think I saw that in the source), i.e CMYK for paint mixing, and similar ilk?

I have a few personal projects that would benefit from a library that is wide ranging in the colour space, dither algorithms (I only saw riezsma) and quantizations.

Typically these are all usually implemented in different libraries :(

Thanks!

[leeoniya]

Wu v2 is really good. i said it in 2015 :)

https://news.ycombinator.com/item?id=9213955

see that whole thread, too

[big-nacho]

Will take a look, thanks for sharing! This does not implement Wu v2 but a different method he published a year later though.

[w-m]

What specifically about this paper caught your eye that you wanted to implement that, what does it do better than other methods? Can you give a quick primer on what it does, and what the optional kmeans refinement does?

[big-nacho]

Something that caught my eye is that it seemed to be a kind of "controlled" K-Means. One problem with K-means is that it's too sensitive to the initial state. You can run it multiple times with different initial states or use fancy initialization techniques (or both) but even then nothing really guarantees you won't be stuck with a bad local optimum. Another thing was that the guy that wrote the paper also authored an insanely high quality method the year before and claimed this one was better. Not seeing any available implementations I wondered how good it actually was.

The optional K-Means step just grabs whatever palette the original method yielded and uses it as initial state for a final refinement step. This gives you (or gets you closer) to a local optimum. In a lot of cases it makes little difference, but it can bump up quality sometimes.

[sebastianmestre]

Very cool!

Something that always bugged me about palette generators I've used is how they end up not picking any colors intense enough for the deepest highlights/shadows, because they use colors close to the average of various sets of pixels.

The result is that the most eye-catching parts of an image end up washed out, reducing the appeal.

My hack to address this has always been making a larger image with big white/black bars around the original image to push the palette generator to include a few really bright or dark colors.

From the look of your examples, your project addresses this too, right?

Btw, I opened an issue about the graphs in your readme because, as a programmer, they don't tell me if your program is fast or not. From a user's perspective that thinks in terms of the side length of an image, the numbers presented are very useful, but they might be even more useful in table format.

[ValdikSS]

Please consider adding this and possibly other algorithms to CUPS printing system. Easiest is to add it into ghostscript.

https://github.com/OpenPrinting/libcupsfilters/pull/92

[vanderZwan]

There so many interesting papers out there without a publicly accessible implementation, very cool that you made this. Question out of curiousity: what made you pick Riemersma dithering?

[big-nacho]

Two things: 1. I like the natural feel it gives to images. 2. Easy to control. As much as it's super easy to cook up a matrix based error diffusion dither (like Floyd), there are a lot of things to take care of to reduce artifacts and bad side effects.

I also generally want to take a bit more time with the dithering topic and explore other methods too, which hopefully I'll add in the future.

[Aurornis]

Fantastic project and documentation. Thanks for putting it up there.

[esafak]

What is color quantization used for in this lossy compression age?

[vanderZwan]

I don't get the question. Lossy compression uses color quantization all the time, doesn't it?

[qingcharles]

GIFs

[JKCalhoun]

Would this be a good candidate for use in image posterization? That was what I assumed it was for.

[pk-protect-ai]

I looked for pytorch native implementation for Xiaolin Wu's quantizer like 3 month ago, and found none. Would not it be much easier and more productive to integrate with pytorch? Some of the functionality which you have there is already provided by kornia, torch_kmeans. You'll end up with much less code to worry about.

[leeoniya]

i wonder how something like this would perform if adapted to oklab or oklch. these should give good eucledian color distances.