Frame header encoding in VP8 Reg

[Rajesh Pamula]

Dear experts,

I have a generic query regarding the frame header encoding in VP8. Almost all the syntax elements in the frame header are encoded in a such a way that the bools 0 and 1 are equi probable. This results is exactly the same  number of bits to be output as the input.  So, what is the reason behind encoding the frame header using bool coder, when fixed length coding also would do the same job in compression efficiency sense.

Thanks and regards

--
Rajesh Pamula
Post Graduate Student
Analogue and Digital Integrated Circuit Design
Imperial College London.
Residence Phone: +44-20-78522056

[Rajesh Pamula]

Dear Experts,

Could you please answer my query below?

Thanks and regards,
Rajesh

[Mike Melanson]

On 01/27/2011 01:28 AM, Rajesh Pamula wrote:
> Dear experts,
>
> I have a generic query regarding the frame header encoding in VP8.
> Almost all the syntax elements in the frame header are encoded in a such
> a way that the bools 0 and 1 are equi probable. This results is exactly
> the same number of bits to be output as the input. So, what is the
> reason behind encoding the frame header using bool coder, when fixed
> length coding also would do the same job in compression efficiency sense.

Sure, you could use a simple bit encoder and then switch the a Boolean
coder as demanded. That might be a little more coding work than just
emitting the equiprobable bit using a Boolean encoder. Whatever suits you.

When I wrote my VP8 encoder, I just went the pure Boolean coding route.

--
-Mike Melanson

[Rajesh Pamula]

Hi Mike,

Thank you for the reply. As per my understanding, even when the bool coder is bypassed, the context of the bool coder needs to be tracked (updated), so as to facilitate its usage when bool coder is required.

Best regards,
Rajesh

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

[Paul Wilkins]

Actually I do not believe it is the case that you can choose to simply
encode these bits "raw"...or switch in and out of the bool coder on
demand.

For equi-probably bits it looks at first sight as if it should make no
difference, but a detailed analysis of the way the bool coder works
and is initialized has shown that there are some situations where it
is possible that the output of a simple bit encoder and the bool coder
using 128 probability will not be identical.

If and when we progress to a next generation codec (VP9 if you like) I
suspect that we will correct this and code most/all the equi-probable
header bits outside the arithmetic encoder. However, WebM was based on
VP8 with only very minor tweaks and modifications possible in the
timescales before release, so for now it is necessary to use the
boolcoder to decode these bits.

[Rajesh Pamula]

Dear Paul Wilkins,

I agree with your observation, that it is possible to get a stream other than "raw bits" even while encoding equi probable bits. But the actual implementation of the bool coder presented in VP8 seems to be slightly different from what is described in the paper by Witten et al titled "ARITHMETIC CODING FOR DATA COMPRESSION". The method described in the above mentioned paper probably gives "raw bits" when encoding equiprobable bits provided encoding of equiprobable bits start immediately after initialization of bool coder. 

On a related note, I would like to know if it is possible to modify the bool coder such that it outputs one bit at a time instead of byte at a time as implemented currently. If so, can someone suggest the steps that are to be followed.

Thanks and regards,

Rajesh

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

[Mehul Tikekar]

Rajesh,
  Something like this should work -

void write_bool( bool_encoder *e, Prob prob, int bool_value)
{
    uint32 split = 1 + ( ((e->range - 1) * prob) >> 8);
    if( bool_value)
    {
        e->bottom += split; /* move up bottom of interval */
        e->range -= split; /* with corresponding decrease in range */
    }
    else
    e->range = split;
    while( e->range < 128)
    {
        e->range <<= 1;
        if( e->bottom & (1 << 8))
        {
            add_one_to_output( e->output);
        }
       
        e->bottom &= 0xff;
        uint8 temp = (uint8) (e->bottom >> 7);
        *e->output++ = temp;
         e->bottom &= 127;
         e->bottom <<=1;
     }
}

You also have to change add_one_to_output
void add_one_to_output( uint8 *q)
{
    while( *--q == 1)
    *q = 0;
    ++*q;
}

Regards,
 Mehul

[Rajesh Pamula]

Hi Mehul,

Thanks for the information. I will try this and let you know.

Best regards,
Rajesh

[Rajesh Pamula]

Hi Mehul,

I think there is a change needed in the code provided.

        e->bottom &= 0xff;
        uint8 temp = (uint8) (e->bottom >> 7);
        *e->output++ = temp;

needs to be changed to

        uint8 temp = (uint8) (e->bottom >> 7);

        e->bottom &= 0xff;
        *e->output++ = temp;

Also I am not sure in the left shifting of the bottom by 1 is in the right place.

Thanks and regards,
Rajesh