Show HN: High End Color Quantizer

[big-nacho]

https://github.com/big-nacho/patolette

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 → ansgri]

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?

[big-nacho → qingcharles]

GIF rendering is a big use case.

pngquant was a big comparison subject during development (it's a brilliant piece of work, and a mature tool that does a few things more than just quantizing). Take it with a grain of salt of course, but in terms of raw quantization performance, patolette had the edge, particularly when dealing with images with tricky color distributions. With that said, pngquant's dithering algorithm is way more sophisticated (and animation aware, I think). In fact, one thing where it really shines is that it spots with pretty good precision where adding noise would actually hurt instead of helping.

Another thing is that patolette can quantize to both high and lower color counts (the latter particularly with CIELuv), whereas pngquant is more well suited for high color counts.

[porphyra → qingcharles]

working with GIF is valid but it is incredibly sad how it's still the only widely supported silent autoplaying video...

(I guess APNG is supported in many browsers, but uploading one often results in deleterious resizing/recompressing operations that ruins the animation. Discord uses APNG and webp for stickers afaik)

[qingcharles → porphyra]

APNG and animated WEBP are blocked and/or unsupported practically everywhere I try. And I try a lot of places to test it. Reddit supports neither, yet allows GIFs. It's sad.

[porphyra → qingcharles]

Agreed, very sad... Most tools/websites will cause APNG to silently degrade into a static image of only the first frame.

[CamperBob2 → ansgri]

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.

[hatthew → CamperBob2]

Really? Dithering is generally only useful with quantized colors, you can't dither something that's already quantized without knowledge of the original, and many/most people who want to do quantization also want to do dithering. The algorithms themselves might not be conceptually similar, but for practical purposes they seems very related.

[Lerc → ansgri]

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 → ansgri]

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 → pixelpoet]

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 → dinfinity]

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 :)

[leeoniya → big-nacho]

take a look at my demo [1]. i'd love to see the same set of images quantized with your thing.

the quant frog [2] is interesting since it has an artificial single pixel line at the top with a ton of colors to trip quantizers up.

[1] https://github.com/leeoniya/RgbQuant.js/

[2] https://github.com/leeoniya/RgbQuant.js/blob/master/demo/img...

[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 → leeoniya]

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 → w-m]

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.

[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 → vanderZwan]

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.

[vanderZwan → big-nacho]

Thanks for answering! I agree that in the one example image in the readme the output looks quite natural. In other implementations I've seen I could always notice "ghosts" of the Hilbert curve in the resulting image, as a subtle edge artifact. So that turned me off of the algorithm a bit, even though I find it a very elegant approach to dithering. Usually the other images were 1 bit though, that might have been a factor.

On the note of matrix based error diffusion and exploring other methods: maybe you'd enjoy Victor Ostromoukhov's variable coefficient dithering paper[0]. Instead of one diffusion matrix, it has different diffusion matrix depending on the value of the input pixel, and the result is a much more blue noise-like dithering.

Given that his paper is almost a quarter century old I've been wondering if we could find better matrices using modern solver algorithms on today's hardware. I've never used a solver myself so wouldn't know how to set this up though.

Also, there's Zhou-Fang dithering, which takes Ostromoukhov's algorithm and introduces a little bit of randomness to remove artifacts[1]. I have JavaScript implementations for both algorithms in an Observable notebook if you want to try them out[2]. It's limited to 1-bit output though.

[0] https://perso.liris.cnrs.fr/victor.ostromoukhov/publications...

[1] https://dl.acm.org/doi/abs/10.1145/1201775.882289

[2] https://observablehq.com/@jobleonard/variable-coefficient-di...

[Aurornis]

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

[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

[esafak]

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

[vanderZwan → esafak]

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

[esafak → vanderZwan]

Not typically. JPEG zeros out high frequency DCT coefficients, which is not the same thing. Hence my question: why go through this memory-intensive procedure?

[qingcharles → esafak]

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.