[FFmpeg-devel] [PATCH 1/4] zmbvenc: don't sum the entropy when blocks are equal

[Matthew Fearnley]

On Sun, 20 Jan 2019 at 15:16, Tomas Härdin <tjoppen at acc.umu.se> wrote:

> > Hi.  Just to say, I tried setting up additional score_tabs for the
> > bottom/right partial blocks.  Unfortunately, after implementing it and
> > ironing out the bugs, the new score tables actually caused a slight
> > increase in file size!
> > After a little informal investigation with a couple of videos, my
> findings
> > were that increasing the divisor - '(i / (double)(ZMBV_BLOCK *
> ZMBV_BLOCK *
> > some_factor))' - would generally lead to slight compression improvements.
> > Given the score table is still "valid" for smaller blocks, and given the
> > extra complexity of adding the score tables, plus the fact that it may
> > generally hurt the compression, I'm inclined to leave it with the one
> score
> > table.  But there may be potential to improve the current compression
> > method in future, by somehow tuning the divisor for better results
> > generally.
>
> Huh, that's strange. Sounds like something that warrants a comment in
> the code. I also see we have an answer do Carl's question: you're still
> experimenting with this :) I think we can hold off on pushing anything
> until you feel happy with the result
>

Hi.
Sorry, I had missed Carl's question.  Regrettably my work on this has been
slow since my initial patch submissions, but I think I'm close to
submitting some final changes.  Thanks for your patience so far.

I have recently made two helpful realisations about the above score table
problem:

1. The entropy calculation in block_cmp() omits the score of histogram[0]
from the final sum.
It's tempting to do this to bias the scores in favour of 0-bytes, but in
reality, blocks with a majority of 0 (or any other byte) will already be
naturally favoured by the entropy score anyway, and this bias will fail to
penalise blocks with an "average" (i.e. high entropy) number of 0's in them.
The exact implications are difficult to ponder, but in practical terms this
error does tend to produce worse results in the video compression.  Not
massively so, but it's still noticeable.
(Math is a harsh mistress, and will often look unkindly on such flagrant
attempts to circumvent her laws.. :)

2. As long as the blocks being compared are the same size as each other,
the entropy-based score comparisons (without the above bias) are unaffected
by the base of the log, or the divisor used.
(Mathematically, if 'a+b=c+d', then if 'a*log(a) + b*log(b) < c*log(c) +
d*log(d)' then it is also true that 'a*log(a/N) + b*log(b/N) < c*log(c/N) +
d*log(d/N)'.
If that doesn't make sense, it helps to note that 'log(a/N) = log(a) -
log(N)', so the log(N)'s cancel out.)

This means that we can use a single score table for all block sizes!  It
only needs to be big enough for the largest block size, then it produces
optimal scores for all blocks up to that size.
It does mean that partial blocks with uniform bytes won't have a score of
0, but this property of entropy is not actually important when scoring the
blocks.
(Overall, this is a significant relief, because my attempts at multiple
score tables resulted in a lot of tricky decisions about how best to keep
the code DRY and minimise complexity, and I wasn't really happy with my
solution.)


I am planning to organise my submission into two patches.  I intend for one
to focus on problems/inefficiencies in block comparisons/score tables.  The
other will be focused on motion estimation, i.e. the range of MV's that are
compared, and to a very small extent, the order they're compared in.
This avoids the overhead of patching each individual issue separately, but
it will provide a logical split between the two main areas of change.

Kind regards,

Matthew