[FFmpeg-devel] [PATCH] libavcodec/zmbvenc.c: don't allow motion estimation out of range.

[Matthew Fearnley]

On Sun, 9 Dec 2018 at 16:27, Michael Niedermayer <michael at niedermayer.cc>
wrote:

> On Sat, Dec 08, 2018 at 02:53:44PM +0100, Tomas Härdin wrote:
> > lör 2018-12-08 klockan 00:29 +0000 skrev Matthew Fearnley:
> > > Hi Tomas, thanks for looking through my patch.
> > >
> > > > > Practically, this patch fixes graphical glitches e.g. when
> reencoding
> > >
> > > the
> > > > > Commander Keen sample video with me_range 65 or higher:
> > > > >
> > > > >     ffmpeg -i keen4e_000.avi -c:v zmbv -me_range 65 keen4e_me65.avi
> > > > I'd expect this problem to pop up with -me_range 64 too, no?
> > >
> > > I initially thought this would be the case, but taking the tx loop and
> > > removing the edge constraints:
> > >
> > >     for(tx = x - c->range; tx < x + c->range; tx++){
> > >         ...
> > >         dx = tx - x;
> > >
> > > The effective range is (-c->range) <= dx < (c->range), meaning when
> > > c->range = me_range = 64, the dx value ranges from -64 to 63, which
> happens
> > > to be exactly in bounds.
> > > So I could have just capped me_range to 64, and that would have fixed
> the
> > > bug...
> > >
> > > But more generally, I've concluded the '<' sign is a mistake, not just
> > > because of the general asymmetry, but because of the way it prevents
> tx,ty
> > > reaching the bottom/right edges.
> > > In practice it means, for example, that if the screen pans left to
> right,
> > > the bottom edge will have to match against blocks elsewhere in the
> image.
> > >
> > > > I went over the patch, and it looks fine. But what's up with the
> xored
> > > > logic? It seems like it would compute xored always from the bottom-
> > > > right-most MV. The loop in zmbv_me() should probably have a temporary
> > > > xored and only output to *xored in if(tv < bv)..
> > >
> > > Hmm, you're right.  In most cases, the code actually works anyway -
> because
> > > when *xored==0, the block entropy returned by block_cmp() is supposed
> to be
> > > 0 anyway, so it still finishes then.
> > > But... I've realised there are some exceptions to this:
> > > - the entropy calculations in block_cmp() use a lookup table
> > > (score_tab[256]), which assumes each block has 16*16 pixels.  This will
> > > only be valid when the dimensions are a multiple of 16, otherwise the
> > > bottom/right edge blocks may be smaller.
> > > - I've just realised the lookup table only goes up to 255.  If all
> 16*16
> > > xored pixels are the same value, it will hit the 256th entry!  (I'm
> > > surprised valgrind hasn't found this..?)
> >
> > Static analysis would've caught this, which is something I've harped on
> > previously on this list (http://ffmpeg.org/pipermail/ffmpeg-devel/2018-
> > June/231598.html)
> >
> > > All that said, *xored==0 is actually the most desirable outcome
> because it
> > > means the block doesn't need to be output.
> > > So if *xored is 0, the best thing to do is probably to finish
> immediately
> > > (making sure *mx,*my are set), without processing any more MVs.
> > > And then it doesn't matter (from a correctness point of view, at
> least) if
> > > block_cmp() gives bad entropy results, as long as *xored is set
> correctly.
> >
> > Oh yeah, that's right. It might also be a good idea to try the MV of
> > the previous block first for the next block, since consecutive blocks
> > are likely to have the same MV. Even fancier would be to gather
> > statistics from the previous frame, and try MVs in order of decreasing
> > popularity. A threshold might also be useful, like "accept any MV that
> > results in no more than N bits entropy"
>
I have a feeling that this isn't a strategy that helps much in the worst
case.  If the upper half of a block contains random data, there's still
potential for compression, but you wouldn't get a good enough sense of the
entropy until you've run block_cmp more than half-way for every MV.

Could still be worth it though.  You could probably presume blocks like
that would be infrequent in the kind of videos ZMBV is designed for, and
just write them off with a suboptimal MV.
(This is presuming we don't go along the path suggested by Michael below.)

looking at existing fancy motion estimation methods, for example variants of
> predictive zonal searches. Might safe some time from redesigning a ME
> method
> from scratch
> also maybe something from libavcodec/motion_est.c can be reused

If the contents of zmbv_me (and block_cmp) can be replaced with a call to a
purpose-built function, that would be great.
I might be willing to help with that, but I don't understand how the
motion_est code works.

My feeling is that ZMBV's specific strengths lie with identical areas of
pixels between frames (e.g. 2D games with scrolling backgrounds/large
sprites).
With that in mind, possibly the easiest way to search is to hash every
possible block in the last frame using a rolling algorithm, and then do a
lookup on that.
The problem is the worst case - when there's no match (or no "0-entropy"
blocks), currently it would still a full search and compare, even if it
tries the likely best blocks first.
In this case, an efficient, preexisting ME function would be very helpful,
because it could find a "good enough" match much quicker than a "lowest
entropy" match, which might not even compress better.


In the short term, I think these two additional fixes should be made to the
current code (along with my first patch), which don't improve things much,
but stabilise what is already there:
- score_tab[] should be declared (and initialised) with
(ZMBV_BLOCK*ZMBV_BLOCK+1) elements
- `!*xored` should be explicitly checked rather than relying on the entropy
calculation: so `!bv` should be `!*xored || !bv`, and `tv < bv` should be
`!*xored || tv < bv`.

(I wonder if we were getting away with the score_tab issue because
score_tab[256] should be 0, and it was at the end of the ZmbvEncContext
structure that's implicitly zeroed anyway..)

I can submit an additional patch (or patches) for the two bugfixes, if that
would be helpful.  I'm not sure the best way to submit them though..
(Would they warrant separate patches?  Should I start new threads?)


I've been planning some additional patches for this codec:
- out-of-bounds ME (by padding the image with a 64-pixel border)
- trying the MV for the previous block (as also suggested above)
- support for RGB pixel formats

I wanted to get this bug fixed first though.  Partially to test the waters
with a simple first patch, but also to just prioritise correctness over
speed/features.

Matthew


> [...]
> --
> Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
>
> Why not whip the teacher when the pupil misbehaves? -- Diogenes of Sinope
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel at ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>