[FFmpeg-devel] [PATCH] libavcodec/zmbvenc.c: don't allow motion estimation out of range.
From: Matthew Fearnley
The maximum allowable range for ZMBV motion estimation is [-64..63], since
the dx,dy values are each stored in the upper 7 bits of a signed char.
(Previously, the range was capped in the code to 127, resulting in an
effective range of [-127..126])
Also fix a range error in the zmbv_me() for-loops ('<' instead of '<='),
which made the limit asymmetrical [-N..N-1], and also prevented it from
reaching the blocks touching the bottom/right edges.
The range is now more symmetrical [-N..N], although this requires separate
range caps of 64 and 63 for negative and positive dx,dy.
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
(Glitches are worse with higher me_range values up to 127.)
---
libavcodec/zmbvenc.c | 16 ++--
1 file changed, 10 insertions(+), 6 deletions(-)
diff --git a/libavcodec/zmbvenc.c b/libavcodec/zmbvenc.c
index 4d9147657d..300a53b08e 100644
--- a/libavcodec/zmbvenc.c
+++ b/libavcodec/zmbvenc.c
@@ -45,7 +45,7 @@
typedef struct ZmbvEncContext {
AVCodecContext *avctx;
-int range;
+int lrange, urange;
uint8_t *comp_buf, *work_buf;
uint8_t pal[768];
uint32_t pal2[256]; //for quick comparisons
@@ -101,8 +101,8 @@ static int zmbv_me(ZmbvEncContext *c, uint8_t *src, int
sstride, uint8_t *prev,
bh = FFMIN(ZMBV_BLOCK, c->avctx->height - y);
bv = block_cmp(c, src, sstride, prev, pstride, bw, bh, xored);
if(!bv) return 0;
-for(ty = FFMAX(y - c->range, 0); ty < FFMIN(y + c->range, c->avctx->height
- bh); ty++){
-for(tx = FFMAX(x - c->range, 0); tx < FFMIN(x + c->range,
c->avctx->width - bw); tx++){
+for(ty = FFMAX(y - c->lrange, 0); ty <= FFMIN(y + c->urange,
c->avctx->height - bh); ty++){
+for(tx = FFMAX(x - c->lrange, 0); tx <= FFMIN(x + c->urange,
c->avctx->width - bw); tx++){
if(tx == x && ty == y) continue; // we already tested this block
dx = tx - x;
dy = ty - y;
@@ -285,9 +285,13 @@ static av_cold int encode_init(AVCodecContext *avctx)
c->curfrm = 0;
c->keyint = avctx->keyint_min;
-c->range = 8;
-if(avctx->me_range > 0)
-c->range = FFMIN(avctx->me_range, 127);
+
+// Motion estimation range: maximum distance is -64..63
+c->lrange = c->urange = 8;
+if(avctx->me_range > 0){
+c->lrange = FFMIN(avctx->me_range, 64);
+c->urange = FFMIN(avctx->me_range, 63);
+}
if(avctx->compression_level >= 0)
lvl = avctx->compression_level;
--
2.17.1
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
Re: [FFmpeg-devel] [PATCH] libavcodec/zmbvenc.c: don't allow motion estimation out of range.
ons 2018-12-05 klockan 21:21 + skrev matthew.w.fearn...@gmail.com:
> > From: Matthew Fearnley
>
> The maximum allowable range for ZMBV motion estimation is [-64..63], since
> the dx,dy values are each stored in the upper 7 bits of a signed char.
>
> (Previously, the range was capped in the code to 127, resulting in an
> effective range of [-127..126])
>
> Also fix a range error in the zmbv_me() for-loops ('<' instead of '<='),
> which made the limit asymmetrical [-N..N-1], and also prevented it from
> reaching the blocks touching the bottom/right edges.
> The range is now more symmetrical [-N..N], although this requires separate
> range caps of 64 and 63 for negative and positive dx,dy.
>
> 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 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)..
/Tomas
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
Re: [FFmpeg-devel] [PATCH] libavcodec/zmbvenc.c: don't allow motion estimation out of range.
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..?)
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.
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...
So I guess there are at least two more fixes that need to be made:
- score_tab[] should have 257 elements (well actually, it should have
ZMBV_BLOCK*ZMBV_BLOCK+1 elements.)
- zmbv_me() should set *mx,*my and finish early, if block_cmp() (either at
the start or in the loop) sets *xored to 0.
Matthew
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
Re: [FFmpeg-devel] [PATCH] libavcodec/zmbvenc.c: don't allow motion estimation out of range.
lör 2018-12-08 klockan 00:29 + 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
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
Re: [FFmpeg-devel] [PATCH] libavcodec/zmbvenc.c: don't allow motion estimation out of range.
lör 2018-12-08 klockan 00:29 + skrev Matthew Fearnley: > 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. > > 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... Another couple of thoughts crossed my mind regarding scoring: The current scoring is entirely context-less. It might be better to at the last bring in the histogram of the previous block into the current one, to bias the encoder toward outputing similar bytes, thus making zlib's job easier. If blocks are scored primarily based on the number of zeroes, only using the entropy model for breaking ties, then some MVs can be discarded earlier if the number of non-zeroes exceeds the best MV found so far. This should speed the encoder up considerably. It would bias the output toward outputing more zeroes, which may or may not be beneficial for the zlib step. /Tomas ___ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
Re: [FFmpeg-devel] [PATCH] libavcodec/zmbvenc.c: don't allow motion estimation out of range.
On Sat, Dec 08, 2018 at 02:53:44PM +0100, Tomas Härdin wrote:
> lör 2018-12-08 klockan 00:29 + 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"
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
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
Why not whip the teacher when the pupil misbehaves? -- Diogenes of Sinope
signature.asc
Description: PGP signature
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
Re: [FFmpeg-devel] [PATCH] libavcodec/zmbvenc.c: don't allow motion estimation out of range.
On Sun, 9 Dec 2018 at 16:27, Michael Niedermayer
wrote:
> On Sat, Dec 08, 2018 at 02:53:44PM +0100, Tomas Härdin wrote:
> > lör 2018-12-08 klockan 00:29 + 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 compar
Re: [FFmpeg-devel] [PATCH] libavcodec/zmbvenc.c: don't allow motion estimation out of range.
Hi, Just to say, after further reviewing the logic in zmbv_me() and block_cmp(), I think it all tenuously holds together, with no possibilities of incorrect xored values or undefined behaviour. But it is quite fragile. I’m planning some patches to strengthen/clarify the logic, and to make it more resilient to future changes, but I think this patch is good to go, as it is now. Kind regards Matthew > On 15 Dec 2018, at 20:54, Matthew Fearnley > wrote: > ___ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
