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.
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.
Gifski uses the png-quant library, and I wonder how this compares?
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.
(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)
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.
Colour quantisation is still one of the best lossy image compression formats for when you have almost no memory or CPU.
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).
I'd say that showing full example results are the most important part of showcasing a "high end" color quantizer.
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 :)
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...
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!
https://news.ycombinator.com/item?id=9213955
see that whole thread, too
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.
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.
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.
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...
