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

[Tomas Härdin]

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"

> Note: the code currently exits on bv==0.  It's a very good result, but it
> does not always imply the most desirable case, because it will happen if
> the xored block contains all 42's (etc), not just all 0's.
> It's obviously highly compressible, but it would still be better if the
> block could be omitted entirely.  Maybe it's an acceptable time/space
> tradeoff though.  I don't know...

You could always add !!*xored to the score. That way all 42's -> 1, all
0's -> 0.

/Tomas