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

[Michael Niedermayer]

On Tue, Jan 03, 2023 at 12:05:22AM +0100, Clément Bœsch wrote:
> 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.

If we simplify the problem a bit and instead of considering 3d we just look at 1d
then for example to represent all colors between 0 and 128 either as a
solid color or by 2 colors 50:50% then we need only 19 colors of these values
{0,2,6,8,10,16,28,40,52,64,76,88,100,112,118,120,122,126,128}

if we have fewer colors in 1d we can cover these

Full n= 4 cover=9 avg=2.666667 {0,2,6,8}
Full n= 5 cover=13 avg=3.769231 {0,2,6,10,12}
Full n= 6 cover=17 avg=4.823529 {0,2,6,10,14,16}
Full n= 7 cover=21 avg=5.857143 {0,2,4,10,16,18,20}
Full n= 8 cover=27 avg=6.888889 {0,2,6,8,18,20,24,26}
Full n= 9 cover=33 avg= 9.969697 {0,2,4,10,16,22,28,30,32}
Full n=10 cover=41 avg=10.878049 {0,2,6,8,18,22,32,34,38,40}
Full n=11 cover=45 avg=10.644444 {0,2,6,8,18,22,26,36,38,42,44}
Full n=12 cover=55 avg=14.727273 {0,2,6,8,18,22,32,36,46,48,52,54}
Full n=13 cover=65 avg=18.415385 {0,2,6,8,18,22,32,42,46,56,58,62,64}
Full n=14 cover=73 avg=18.931507 {0,2,6,8,18,22,32,40,50,54,64,66,70,72}
Full n=15 cover=81 avg=25.172840 {0,2,6,8,10,16,28,40,52,64,70,72,74,78,80}
Full n=16 cover=93 avg=30.193548 {0,2,6,8,10,16,28,40,52,64,76,82,84,86,90,92}
Full n=17 cover=105 avg=35.209524 {0,2,6,8,10,16,28,40,52,64,76,88,94,96,98,102,104}
Full n=18 cover=111 avg=33.261261 {0,2,6,10,14,18,20,42,44,66,68,90,92,96,100,104,108,110}

so what about 3d ?
if we have a 3d cube and we create a palette with the 1d list from above for
6 colors we end up with a 6x6x6 palette of 216 colors where with the 50:50 mixes
we cover the full 17x17x17=4913 cube, all points of it that is. same for the 6x6x7
 (17x17x21=6069) cases. this might be an interresting alternative to the 332 palette
or maybe it could be used as start point for some optimized palette, remocing unused
colors and adding new by some clustering

I didnt try any of this on an actual image. Its not as simple as using that palette
as the dither algorithm also needs to be redesigned to actually use the right
color pairs. Dither would generally use the closest color and thats not true here
for many pairs

also gamma needs to be handled correctly for all this because mixing white and
black pixels will only look like 50% gray when gamma is handled correctly
As i didnt try it, i have 0 idea how bad it would look. I was primarly interrested
in the nummeric/math aspect behind this which is why i played a bit with these
numbers

thx

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The day soldiers stop bringing you their problems is the day you have stopped 
leading them. They have either lost confidence that you can help or concluded 
you do not care. Either case is a failure of leadership. - Colin Powell
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 195 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20230103/354df9bb/attachment.sig>