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

[Michael Niedermayer]

Hi

On Sat, Dec 31, 2022 at 01:11:54PM +0100, Clément Bœsch wrote:
> On Sun, Nov 06, 2022 at 06:30:22PM +0100, Michael Niedermayer wrote:
> > On Sun, Nov 06, 2022 at 06:09:41PM +0100, Michael Niedermayer wrote:
> > > On Sat, Nov 05, 2022 at 04:26:02PM +0100, Clément Bœsch wrote:
> > > > Hi,
> > > > 
> > > > This patchset essentially fixes a few core problems in these filters and
> > > > switches to a perceptual model.
> > > > 
> > > > I've generated a report for each key commit on this (temporary) page:
> > > > http://big.pkh.me/pal/ (warning: heavy page, ~500M; I did try to add some lazy
> > > > loading of the images but I'm not sure it's actually working as expected).
> > > 
> > > i just looked at file00 and 16 and 64 colors with dither for it and they look
> > > different, some areas look better before and some better afterwards
> > 
> > looked at more of the 16 color cases with dither 
> > (16 colors as i asumed fewer would magnify any issues )
> > file 01, IMHO current looks better than last (variance per axis)
> > file 02, IMHO current looks better than last (variance per axis)
> > file 03, IMHO VPA looks better but both really are quite off in terms of color,
> >          thats not the color of the original image.
> > file 04, VPA is not good thats not the correct color
> > 
> > It seems th last (variance per axis) is more pale and looses color
> 
> 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 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 ....


> 
> 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.
 
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
 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
 
[...]

thx
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Any man who breaks a law that conscience tells him is unjust and willingly 
accepts the penalty by staying in jail in order to arouse the conscience of 
the community on the injustice of the law is at that moment expressing the 
very highest respect for law. - Martin Luther King Jr
-------------- 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/20230102/14c7a70b/attachment.sig>