[FFmpeg-devel] [PATCH] Revert "avfilter/vf_palette(gen|use): support palettes with alpha"

[Soft Works]

> -----Original Message-----
> From: ffmpeg-devel <ffmpeg-devel-bounces at ffmpeg.org> On Behalf Of
> Michael Niedermayer
> Sent: Monday, October 31, 2022 10:59 PM
> To: FFmpeg development discussions and patches <ffmpeg-
> devel at ffmpeg.org>
> Subject: Re: [FFmpeg-devel] [PATCH] Revert
> "avfilter/vf_palette(gen|use): support palettes with alpha"
> 
> On Mon, Oct 31, 2022 at 11:57:16AM +0100, Clément Bœsch wrote:
> > On Mon, Oct 31, 2022 at 01:43:11AM +0000, Soft Works wrote:
> > [...]
> > > > > > The patch I had submitted doesn't change the previous
> behavior
> > > > > > without the use_alpha parameter.
> > > >
> > > > Yes I noticed, but unfortunately I'm reworking the color
> distance to
> > > > work
> > > > in perceptual color space, and the way that alpha is mixed up
> in the
> > > > equation just doesn't make any sense at all and prevents me
> from
> > > > doing
> > > > these changes.
> > >
> > > If you want to implement a new color distance algorithm, it
> should
> > > be either a new filter or a new (switchable) mode for the
> existing
> > > filter.
> >
> > Why?
> >
> > > Photoshop has these different modes as well and it would
> > > surely be useful, but I don't think it should be replacing the
> > > existing behavior.
> > >
> >
> > There is no point in keeping a ton of complexity exposed as user
> options
> > for something implementation specific. We offer no guarantee over
> how the
> > quantization is expected to run.
> >
> > > When it turns out that the use_alpha implementation doesn't fit
> > > with your new color distance calculation and you add it as
> > > an additional mode, then it would be fine IMO when the filter
> > > errors in case it would be attempted to use that mode in
> > > combination with use_alpha.
> >
> > IMO The use_alpha option shouldn't exist in the first place, it
> should be
> > the default behaviour because honoring the alpha is the correct
> thing to
> > do. That's not what the option is currently doing though.
> >
> > > > > Do you think it might make sense to put more weight on the
> > > > > alpha value by tripling it? So it would be weighted equally
> to the
> > > > > RGB value?
> > > >
> > > > You cannot mix alpha with colors at all, they are separate
> domains
> > > > and you
> > > > need to treat them as such.
> > >
> > > What's interesting is that I've followed the same (simplified)
> > > way for adding a use_alpha option to vf_elbg and it provides
> excellent
> > > results without treating alpha separately.
> >
> > I don't know how the filter works and what it's supposed to do, but
> if
> > it's indeed using the same approach as the palette ones, it cannot
> work.
> >
> > > > From paletteuse perspective what you need to do is first choose
> the
> > > > colors
> > > > in the palette that match exactly the alpha (or at least the
> closest
> > > > if
> > > > and only there is no exact match). Then within that set, and
> only
> > > > within
> > > > that one, you'd pick the closest color.
> > > >
> > > > From palettegen perspective, you need to split the colors in
> > > > different
> > > > transparency domain (a first dimensional quantization), then
> quantize
> > > > the
> > > > colors in each quantized alpha dimension. And when you have all
> your
> > > > quantized palettes for each level of alpha, you find an
> algorithm to
> > > > reduce the number of transparency dimensions or the number of
> colors
> > > > per
> > > > dimension to make it fit inside a single palette. But you can't
> just
> > > > do
> > > > the alpha and the colors at the same time, it cannot work,
> whatever
> > > > weights you choose.
> > >
> > > I would be curious to see how well that would work, especially
> > > in cases when the target palettes have just a few number of
> colors.
> > >
> >
> > You have to make a call between whether you want to preserve the
> > transparency or the color while constructing the palette, but when
> > choosing a color you must absolutely not choose a color with a
> different
> > transparency, you must pick amongst the closest alpha, with a
> particular
> > attention to extreme alphas: an opaque colors must stay opaque, and
> fully
> > transparent one as well:
> > - rounding a color with 43% alpha into 50% alpha is acceptable
> > - rounding a color with 100% alpha into a 99% alpha is not
> acceptable in
> >   any way because you're starting to make transparent areas that
> weren't
> > - rounding a color with 0% alpha into a 1% alpha is not acceptable
> because
> >   some areas of the images are not starting to blend into an area
> that was
> >   supposedly non-existent
> 
> really ?
> so if i have all shades of green available for all transparencies
> from 1% to 99%
> i "must" make my plants all use 0% trasparency even if i only have a
> single color and
> that is bright pink
> I dont think that is the best choice
> 
> There are perceptual differences between the different areas of the
> RGBA hypercube
> though. Hardly anyone would notice the difference between a 255 and
> 254 blue but
> having some slight transparency might be noticable.
> These different weights in different areas could maybe be considered
> in palette*
> and elbg, it likely would improve things. OTOH heuristics like always
> and never
> feels like that might become alot of work to tune. I think its better
> to attemt
> to achieve a similar goal with less hard and more perceptual scoring

I agree. vf_elbg+use_alpha provides excellent results without separate 
alpha handling (even though I say explain why) and pngquant doesn't 
handle alpha separately either.


The pngquant algorithm is described as follows:

pngquant uses modified version of Median Cut quantization algorithm and 
additional techniques to mitigate deficiencies of Median Cut.

Instead of splitting boxes with largest volume or number of colors, 
boxes are selected to minimize variance from their median value.

Histogram is built with addition of a basic perception model, which gives 
less weight to noisy areas of the image.

To improve color further, histogram is adjusted in a process similar to 
gradient descent (Median Cut is repeated many times with more weight on 
poorly represented colors).

Finally, colors are corrected using Voronoi iteration (K-means), which 
guarantees locally optimal palette.

pngquant works in premultiplied alpha color space to give less weight 
to transparent colors.

When remapping, error diffusion is applied only to areas where several 
neighboring pixels quantize to the same value, and which are not edges. 
This avoids adding noise to areas which have high visual quality 
without dithering.

(Reference: https://pngquant.org/#algorithm) 

softworkz