[HN Gopher] Show HN: High End Color Quantizer
___________________________________________________________________
Show HN: High End Color Quantizer
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.
Author : big-nacho
Score : 102 points
Date : 2025-06-10 11:50 UTC (11 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| leeoniya wrote:
| Wu v2 is really good. i said it in 2015 :)
|
| https://news.ycombinator.com/item?id=9213955
|
| see that whole thread, too
| big-nacho wrote:
| Will take a look, thanks for sharing! This does not implement
| Wu v2 but a different method he published a year later though.
| ansgri wrote:
| 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?
| pk-protect-ai wrote:
| 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.
| CamperBob2 wrote:
| 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 wrote:
| 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.
| qingcharles wrote:
| 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?
| porphyra wrote:
| 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)
| Lerc wrote:
| 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.
| dinfinity wrote:
| 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 wrote:
| 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 :)
| pk-protect-ai wrote:
| 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.
| sebastianmestre wrote:
| 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 wrote:
| 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 wrote:
| What is color quantization used for in this lossy compression
| age?
| vanderZwan wrote:
| I don't get the question. Lossy compression uses color
| quantization all the time, doesn't it?
| esafak wrote:
| 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 wrote:
| GIFs
| w-m wrote:
| 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 wrote:
| 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.
| vanderZwan wrote:
| 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?
| JKCalhoun wrote:
| Would this be a good candidate for use in image posterization?
| That was what I assumed it was for.
| Aurornis wrote:
| Fantastic project and documentation. Thanks for putting it up
| there.
| pixelpoet wrote:
| 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 wrote:
| 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.
| SillyUsername wrote:
| 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!
| bmn__ wrote:
| > 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.
___________________________________________________________________
(page generated 2025-06-10 23:00 UTC)