[FFmpeg-devel] Rework color quantization in palette{gen,use}

[Clément Bœsch]

On Mon, Jan 02, 2023 at 10:57:33PM +0100, Michael Niedermayer wrote:
[...]
> > So I did a lot of experiments, and the explanation for the desaturated
> > output at low number of colors can be found at the end of this article:
> > http://blog.pkh.me/p/39-improving-color-quantization-heuristics.html
> 
> interresting and its impressive how much reseacrh you did here
> i hope this will get applied

Thanks. I was actually planning to push in the next 12 hours or so, unless
there is an objection.

> also i hape a bit that it will get
> extended to include clustering as in ELBG cuz it seems a bit odd
> to have this sort of alternative filters neither does all ....

Yeah at some point we probably want to group the clustering and vector
quantization logics in a common module. But there are lot of questions API
wise wrt its relationship with perceptual and other color systems.

> > I still think it's acceptable to lean toward desaturated colors when
> > reducing the number of colors, but you may disagree.
> 
> I think a key aspect of desaturation has not been mentioned.
> That is mixing, i mean dithering is some sort of mixing, in the sense of
> an artist mixing several pigment/dyes/colors.
> If you have black and white a 50% mixture gives 50% gray. other ratios
> would give us all values between white and black though with dithering
> some ratios work better like 50% looks good while ratios very close to
> 0 and 100% but not exacty 0 and 100 look bad with few highly vissible
> black or white pixels in a see of the opposing color.
> 
> Now this results in 2 things at least.
> 1. We should be able to improve color quantization by this.
>  If we have colors A and B the (A+B)/2 point is basically free, its dither
>  pattern looks good on any high resolution display and if we consider such
>  points there are more of course like maybe (A+B+C+D)/4 we can cover more
>  output colors with a smaller palette.

That's interesting. Basically you'd free certain slots of the palette if
you detect that this particular color is at the mid point of two others in
the palette? And so you could use that slot for another tint…

Yeah I don't know what to do with this information, it looks not trivial
to implement.

> 2. desaturation happens in dithered images because colors are simply not
>  representable, the same way a artist cant paint 100% white if the brightest
>  color she has is 80% white. She cant mix that with anything to make it
>  brighter. An algorithm which would ensure that the colors from the palette
>  form a convex hull around all the colors of the input would ensure all
>  colors are representable and no desaturation should happen. it of course
>  may look bad, i dont know, A convex hull likely is not the global optimum
>  from a perceptual POV. But one only needs 8 colors to gurantee all colors
>  are representable with dithering

I feel like a cheap hack would be to create a filter such as
"palettesource" which generates a palette using OkLCh (same as OkLab but
circular space, the hue is an angle) to design such palette. That's easy
to do and you could immediately test it by feeding it to paletteuse.

>  Another way to maybe see this is that if you have 1 color the best place
>  is teh one where it minimizes the distance to all. But as more points are
>  added average points between them become usable in a dithered image so
>  the thing starts filling up while the perimeter and outside is harder
>  to represent
>  One could also say that with 2 colors all points on the line joining
>  them can be represented and so distance to that line could be minimized
>  but as not really all points on that line form pleasing dither patterns
>  iam hesitant about this representation but it can be extended to a triangle
>  and so forth with more points
>  
> Now i hope i have not given any ideas that make you spend more months on
> this if you dont enjoy it :) But i find the whole myself a bit interresting

Heh, yeah I'm already onto another crazy topic currently so you'll have to
do it on your own :)

BTW it was rightfully pointed out to me that in addition to the box and
the axis selections, there is a 3rd aspect to study: the median cut
itself.

There is likely something better to do here that would use the values
themselves instead of just a cut at the median of the set, specifically if
there are large gaps in the values. For example [1,2,3,6,7,8,231,255]
(assuming weights of 1) would be cut [1,2,3,6] [7,8,231,255] when
[1,2,3,6,7,8] [231,255] would probably be much more appropriate.

It might help addressing the bias toward L* for low number of colors
where these irregularities are particularly common (and tend to smooth out
over cuts because typically [7,8,231,255] is likely to be cut again soon
due to its variance).

I feel like it might not be that hard to actually improve the low color
count by trying out some alternatives. But there are many cut solutions
approaches which need to be measured.

I'm happy to provide guidance in how to try them out in my research
repository. It should be pretty easy to hack.

Regards,

-- 
Clément B.