MV bounds patch

[Timothy B. Terriberry]

I'm not suggesting that the attached patch be applied upstream, but this
addresses the issue in
https://bugzilla.mozilla.org/show_bug.cgi?id=566987, providing clamping
without breaking existing streams.

That is, for SPLITMV it allows MVs up to 7 1/8th pel units farther
outside the frame bounds than any of the other MB modes. The other modes
can't use the same bound, because the encoder actually does use NEARMV
and NEARESTMV with clamping when RDO is enabled (and actually uses the
same clamping as done in the decoder).

Using the extra +7 requires 17 pixels of padding on the right/bottom for
unchecked access when using bilinear interpolation, instead of 16 pixels
without it. When using the anti-aliasing filters, those numbers are 19
and 18, which was already inconvenient.

I think the proper thing to do is to fix the encoder to use a consistent
set of MV bounds throughout, and commit a version of this without the
+7. I'm preparing such an encoder patch, and will post it once I've
tested it.

[Paul Wilkins]

I think that we all felt that this patch basically made sense and it
was initially
put in. Unfortunately it turns out that it DOES break some existing
streams.

This was discovered < 48 hours before the launch and whilst there is a
case
to make that it is the encoder that should be changed (or fixed) this
was
not a practical option with such a short time to go before the launch
as there
were already in the order of 1 million clips encoded that might
exhibit the
problem and insufficient time to recode them.

At some point (hopefully soon) we may be able to revisit this and if
necessary
initiate a recode on affected content, but we did not feel comfortable
launching
in the knowledge that some unknown proportion of the clips would
exhibit
serious corruption.


On May 20, 2:26 am, "Timothy B. Terriberry" <tterribe...@mozilla.com>
wrote:

> I'm not suggesting that the attached patch be applied upstream, but this

> addresses the issue inhttps://bugzilla.mozilla.org/show_bug.cgi?id=566987, providing clamping

> --
> You received this message because you are subscribed to the WebM "Codec Developers" group.
> To post to this group, send email to codec-de...@webmproject.org
> To unsubscribe from this group, send email to
> codec-devel+unsubscr...@webmproject.org
> For more options, visit this group athttp://groups.google.com/a/webmproject.org/group/codec-devel?hl=en
>
>  0001-Test-commit-for-a-version-of-the-SPLITMV-bounds-patc.patch
> 1KViewDownload

--
You received this message because you are subscribed to the WebM "Codec Developers" group.
To post to this group, send email to codec...@webmproject.org
To unsubscribe from this group, send email to
codec-devel...@webmproject.org
For more options, visit this group at
http://groups.google.com/a/webmproject.org/group/codec-devel?hl=en

[Timothy B. Terriberry]

Paul Wilkins wrote:
> I think that we all felt that this patch basically made sense and it

This is not the same as the first patch I sent. This one was designed to
ensure to still work with streams generated from the encoder as it
exists today, as proof-of-concept that the issue I raised with doing
1/8th pel clamping in the decoder, but fullpel clamping in the encoder
was actually the source of the problems.

Unfortunately, this patch means having a different bounds check for the
SPLITMV case, and potentially requiring a larger padding buffer than
would have been required if the same bounds check as used for the other
MB modes was used for SPLITMV.

> At some point (hopefully soon) we may be able to revisit this and if
> necessary
> initiate a recode on affected content, but we did not feel comfortable
> launching
> in the knowledge that some unknown proportion of the clips would
> exhibit
> serious corruption.

I understand the decisions you had to make. I'm trying to start the
conversation that "revisits" this, now that everything's public.

[Paul Wilkins]

OK. I confess I hadn't realized that this was a revised patch. In the last couple of days there just haven't been enough hours in the day!

Clearly this aught to be resolved one way or the other though as the lack of clamping for SPLITMV at the moment is an issue in itself.

[John Koleszar]

On Thu, May 20, 2010 at 10:39 AM, Timothy B. Terriberry
<tterr...@mozilla.com> wrote:
> Paul Wilkins wrote:
>> I think that we all felt that this patch basically made sense and it
>
> This is not the same as the first patch I sent. This one was designed to
> ensure to still work with streams generated from the encoder as it
> exists today, as proof-of-concept that the issue I raised with doing
> 1/8th pel clamping in the decoder, but fullpel clamping in the encoder
> was actually the source of the problems.
>
> Unfortunately, this patch means having a different bounds check for the
> SPLITMV case, and potentially requiring a larger padding buffer than
> would have been required if the same bounds check as used for the other
> MB modes was used for SPLITMV.
>

Agree.. I fixed this bug on Tuesday the same way you did, we just
wanted to take time to address the issue properly rather than throwing
a hack in at the 11th hour.

>> At some point (hopefully soon) we may be able to revisit this and if
>> necessary
>> initiate a recode on affected content, but we did not feel comfortable
>> launching
>> in the knowledge that some unknown proportion of the clips would
>> exhibit
>> serious corruption.
>
> I understand the decisions you had to make. I'm trying to start the
> conversation that "revisits" this, now that everything's public.
>

The way I see this: The clamping behavior is undefined by the spec at
the moment, but the spec does define a 32 pixel border. The motion
search is bounded on the encoder to 16 pixels, but it doesn't clamp
except on the near/nearest mvs. I think this means we only ever use a
couple pixels past 16 for subpixel interpolation, which seems wasteful
to me, knowing how expensive the border fill is in the embedded world.

To me, the ideal thing to do depending on the current state of
hardware implementations is probably relax the clamping to allow the
whole 32 pixel border for current bitstreams, then rev the bitstream
version with one that requires only a 16 pixel border. Doing it this
way, older decoders that use the 32 pixel border could play files that
respect the 16 pixel border (if they don't choke on the different
version number anyway). I don't have the background to know whether
this is detrimental or how much so -- I know it would require that
filtering non-split mbs overlap the frame at least for a naive
implementation, but I'm starting to get out of my depth here.

If we did end up revving the bitstream or otherwise break backwards
compatibility to clean up/formalize MV clamping, I'll also put in
another plug for looking at the clamping in find_near_mv.. I really
wish that we didn't clamp both before and after adding the delta to
the best mv, and we end up clamping a bunch of times without actually
referencing the clamped mv.

[Timothy B. Terriberry]

John Koleszar wrote:
> The way I see this: The clamping behavior is undefined by the spec at
> the moment, but the spec does define a 32 pixel border. The motion

Right. The spec says "you need to do it" but doesn't specify where or
how, and the code as shipped doesn't do it at all for SPLITMV.

> couple pixels past 16 for subpixel interpolation, which seems wasteful
> to me, knowing how expensive the border fill is in the embedded world.

I completely agree.

> To me, the ideal thing to do depending on the current state of
> hardware implementations is probably relax the clamping to allow the
> whole 32 pixel border for current bitstreams, then rev the bitstream

The problem is that the clamping for the other MB modes happens inside
the MV prediction loop. Relaxing that clamp will also break existing
streams (at least those encoded with RDO enabled, as then the encoder
actually applies this clamping to NEARMV and NEARESTMV modes).

> version number anyway). I don't have the background to know whether
> this is detrimental or how much so -- I know it would require that
> filtering non-split mbs overlap the frame at least for a naive
> implementation, but I'm starting to get out of my depth here.

Well, this would be pretty easy to evaluate (change the clamping and
test), but I'm pretty sure the answer is "not much". Not allowing MVs to
point outside the frame at _all_ is bad (you get lots of INTRA blocks on
the edges), but the difference between 16 pixels and 14 pixels of
padding is not large; MVs that large are relatively rare anyway, even at
HD resolutions.

> If we did end up revving the bitstream or otherwise break backwards
> compatibility to clean up/formalize MV clamping, I'll also put in
> another plug for looking at the clamping in find_near_mv.. I really

Or just move clamping outside of the prediction loop entirely, and do it
right before reconstruction. I'm not sure I would formally rev the
bitstream just for this, but if we do, there's a lot of other easy
things it would be nice to address, like the loop filter ordering. This
is a conversation we need to have with your hardware partners, however.

[John Koleszar]

On Thu, May 20, 2010 at 6:16 PM, Timothy B. Terriberry
<tterr...@mozilla.com> wrote:
> John Koleszar wrote:
>> The way I see this: The clamping behavior is undefined by the spec at
>> the moment, but the spec does define a 32 pixel border. The motion
>
> Right. The spec says "you need to do it" but doesn't specify where or
> how, and the code as shipped doesn't do it at all for SPLITMV.
>
>> couple pixels past 16 for subpixel interpolation, which seems wasteful
>> to me, knowing how expensive the border fill is in the embedded world.
>
> I completely agree.
>
>> To me, the ideal thing to do depending on the current state of
>> hardware implementations is probably relax the clamping to allow the
>> whole 32 pixel border for current bitstreams, then rev the bitstream
>
> The problem is that the clamping for the other MB modes happens inside
> the MV prediction loop. Relaxing that clamp will also break existing
> streams (at least those encoded with RDO enabled, as then the encoder
> actually applies this clamping to NEARMV and NEARESTMV modes).
>

I didn't mean relaxing the clamp on the bestmv that new mvs are coded
relative to (from find_near_mv), I meant the second clamping that
happens after the decoded mv is added back to the clamped bestmv. Our
current encoder does not rely on this behavior, it was added recently
as a protection against crashing when decoding bad data. You could do
the SPLITMV and NEWMV clamping at the 32 pixel border, but that's
still inconsistent with the near/nearest modes.

In any case I'd prefer that we handle all the clamping consistently
similar to what I described, I was just pointing out a way we could
manage compatibility. Still need to figure out exactly how much
flexibility we have at this point.

[Paul Wilkins]

re

> Well, this would be pretty easy to evaluate (change the clamping and
> test), but I'm pretty sure the answer is "not much". Not allowing MVs to
> point outside the frame at _all_ is bad (you get lots of INTRA blocks on
> the edges), but the difference between 16 pixels and 14 pixels of
> padding is not large; MVs that large are relatively rare anyway, even at
> HD resolutions.

With 16 pels the MB is wholly (at least from a full pel perspective)
inside the border (though the sup-pel filter will still be drawing
data from some points inside the image for a couple of the pixel rows
or columns). Moving further into the border does not therefore change
the prediction much and once the filter is also fully inside the
border not at all. Reducing to 14 does have a more significant impact
because it forces the macroblock to overlap into the real image by at
least a couple of pixels, though I don't have any very reliable feel
for how much difference this would make.

[John Koleszar]

I was thinking that the splitmv case wouldn't be a problem for the
smaller border, since the partitions could be clamped individually and
the smaller blocks could be filtered in the border, so we're only
talking about the 16x16 modes, right? If so, maybe the decoder could
turn the 16x16 MBs along the border into splits with two partitions
(obviously without updating the entropy context) to get the two
different MV's you'd need. Or maybe only do that if the predictor is
wholly within the border. Doesn't really solve the issue
mathematically, but would allow you to only use 16 pixels in memory.

[Yaowu Xu]

From the bit stream perspective, we can simply specifying how pixel
values are extrapolated, buffer border extension and mv clamping are
not necessary. Still those can be done for convenience/ robustness of
implementations.

One possible implementation can be not doing any mv clamping at at in
either encoder and decoder, and not doing any buffer border extension.
Pixel values are extrapolated only when needed. We probably should do
experiments to see if this way actually helps performance, especially
when buffer copy cost is high on so mentioned embedded platforms.

[Timothy B. Terriberry]

Paul Wilkins wrote:
> border not at all. Reducing to 14 does have a more significant impact
> because it forces the macroblock to overlap into the real image by at
> least a couple of pixels, though I don't have any very reliable feel

Actually only by one pixel, because the edge of the image is the same as
the border, too. Though if you don't want any of the real imagery for
prediction, you might do as well with one of the INTRA modes than as
with whatever junk happens to be on the border.

[Timothy B. Terriberry]

John Koleszar wrote:
> I was thinking that the splitmv case wouldn't be a problem for the
> smaller border, since the partitions could be clamped individually and
> the smaller blocks could be filtered in the border, so we're only

Keeping in mind that the average MV used for chroma can point farther
outside the bounds than any of the blocks that contributed to that
average. This is doable, but tricky to get right, and the less tricky it
is the more likely people are going to get it right. This is one of the
reasons I'm arguing for a consistent treatment of all of the MB modes.

[Timothy B. Terriberry]

Yaowu Xu wrote:
> From the bit stream perspective, we can simply specifying how pixel
> values are extrapolated, buffer border extension and mv clamping are
> not necessary. Still those can be done for convenience/ robustness of
> implementations.

This is the approach Theora took, though it was much less complicated as
we only had 15.5-pel long MVs to begin with. I believe a number of the
ffmpeg decoders allow you to simulate border extension in this way,
rather than use the extra padding.

The problem with this is that because MVs in VP8 are offsets from a
predictor, and that offset must be less than 64 pixels, you can actually
get in a situation where you can't code a MV that points back in the
image at all, except for in ZEROMV mode. At least doing the clamping
before coding the BESTMV residual ensures you have a useful set of
predictors you can point to with it.

[Timothy B. Terriberry]

John Koleszar wrote:
> manage compatibility. Still need to figure out exactly how much
> flexibility we have at this point.

This is still the million-dollar question. Has there been any progress
on this front? I'm afraid the longer we wait, the less flexibility we
will have.

[Silvia Pfeiffer]

Oh my - I think the largest content owner moving to WebM is YouTube,
so I would chat with those guys if they can stop the transcoding and
apply a new format (aren't there Google people here who would have the
relationship to the right YouTube guys?). That new format would need
to be released asap though.

Just my 2c.

Silvia.

[Timothy B. Terriberry]

A number of projects integrating webm support have been contacting me
about this issue, and with nothing better to suggest, I have been forced
to recommend they apply the patch in this thread, due to the security
concerns. Unless a decision is made soon on the correct way to handle
this, this is likely to become the de-facto standard. Refusing to choose
is also a choice.

[Yaowu Xu]

I agree.  Since the patch does not break current bit stream in any way but addresses security concerns, I think we should get your patch in rather quickly. 

[John Koleszar]

Yeah, I think a change like this needs to go into the stable branch
now, we have to address the security issue. Making the whole of the MV
clamping more consistent and maybe changing the border size is a good
thing to look at for the bitstream changes branch.

To be pedantic, this change does change the bitstream, though it does
not break any existing streams. I'm fine with accepting this patch
as-is to fix the issue today, but I think that a better approach is to
remove this "secondary" clamping for both the split and non-split
cases and do it at the prediction stage instead, which would make the
bounds checking implementation defined, which seems cleaner to me.
Both of these options need buy-in on the hardware side. The only other
option is to leave the mv-decoding as-is and do the bounds checking at
the prediction stage for split-mvs.

Based on the history of this code, I'm not sure that this secondary
clamping was communicated well to the hardware folks, so there's a
risk that there are multiple inconsistent implementations. The
hw-devel@ list has been created to provide a forum to discuss these
sorts of things, and we should bring this up there as the first order
of business once people have a chance to sign up.

[Timothy B. Terriberry]

John Koleszar wrote:
> as-is to fix the issue today, but I think that a better approach is to
> remove this "secondary" clamping for both the split and non-split
> cases and do it at the prediction stage instead, which would make the

For those following this thread, John's proposal has been committed in
the following two commmits:
http://review.webmproject.org/gitweb?p=libvpx.git;a=commit;h=3085025fa1392e99bc95a519657374f2e9a4249b
http://review.webmproject.org/gitweb?p=libvpx.git;a=commit;h=05c6eca4db7f2abec32c9ce0fc325d9a0b933fb7

These should supersede the patch I posted at the beginning of this thread.