RE: [AVT] Question bout motion vector

["Gary Sullivan" <garysull at windows.microsoft.com>]

Tom, Kelly, et al,

I guess now that I've been invoked by name I'll have to respond.  :-)

Below is probably more than you wanted to know about the subject:

The term UVLC just means "universal variable-length code", so it could
hypothetically be used to describe various different coding methods that
fit the description of having a high degree of structure that may be
suitable for a large variety of uses.

Lately we sometimes use the term UVLC to refer to the Exponential-Golomb
code structure used in the final standard, as specified in its subclause
9.1.

Exp-Golomb coding is about 30 years old - reference: J. Teuhola, "A
compression method for clustered bit-vectors," Information Processing
Letters, vol. 7, pp. 308-311, October 1978.

These codes have a simple structure that is pretty easy to illustrate.

The parsing process starts with the following pseudo-code:
  leadingZeroBits = -1;
  for( b = 0; !b; leadingZeroBits++ )
    b = read_bits( 1 )

where the function read_bits( n ) is defined as a function that reads n
bits from the bitstream and returns their value as an integer.

The sequence of bits read by the above pseudocode is sometimes called
the "prefix" part of the code.

The variable codeNum is then assigned as follows:

codeNum = (1 << leadingZeroBits) - 1 + read_bits( leadingZeroBits )

The value of codeNum is the decoded symbol index.

The additional bits read by the read_bits() function in the above
equation are sometimes called the "suffix" part of the code.

In other words, the code table looks like this:

    1
   01x
  001xx
 0001xxx
00001xxxx
...

where the "0" and "1" characters are the prefix bits and the "x"
characters are the suffix bits.  Since the suffix bits can have any
value, you see that the codewords are very short for small values and
gradually get longer for larger values.  It takes
  one bit to code the value 0;
  3 bits to code the value 1 or 2,
  5 bits to code the values 3, 4, 5, and 6;
  7 bits to code the values 7 through 14;
  etc.

That is how we use Exp-Golomb codes to represent unsigned integers in
the new video standard.  When representing signed numbers such as motion
vector component differences, the value of codeNum (which is an unsigned
integer) is converted to a signed number using the following formula:

outputValue = 0 if codeNum is 0;
outputValue = (-1)^(codeNum+1) * Ceil( codeNum/2 ) otherwise.

where "^" denotes exponentiation and "/" denotes division with a
real-valued (floating point) result.

A few years back, we were using a similar but somewhat different code
structure that we were calling UVLC at the time.
One place to find a description of that is the first H.26L draft (from
the Berlin meeting of August 1999), which is available as document
Q15-H-36 in the meeting document directory
http://ftp3.itu.int/av-arch/video-site/9908_Ber.  Its section 2.4
discusses what we called UVLC at the time.

That was a similar code, but in that formulation the "prefix" and
"suffix" part of the code were interleaved with each other.
We decided to change the draft video standard design because we thought
it would be easier to decode without using the interleaving.
That change happened in Feb 2002.  A document from that meeting that
discussed the topic was input document JVT-B029 from Louis Kerofsky of
Sharp Labs, and there were also some discussions of the issue in
documents two meetings earlier (specifically, VCEG-N23 and VCEG-N36 from
Minhua Zhou of Texas Instruments).

Although the change made the design less complex to decode, it
sacrificed a property known as "self-synchronization".
That property (discussed in the Kerofsky contribution VCEG-L23) may have
some usefulness, but it didn't appear to be very useful in this
particular design.

The various cited VCEG and JVT documents can be found in
http://ftp3.itu.int/av-arch.

Best Regards,

Gary Sullivan


+> -----Original Message-----
+> From: avt-bounces at ietf.org [mailto:avt-bounces at ietf.org] On 
+> Behalf Of Tom-PT Taylor
+> Sent: Friday, November 04, 2005 7:23 AM
+> To: Kelly Huang
+> Cc: avt at ietf.org
+> Subject: Re: [AVT] Question bout motion vector
+> 
+> I did some quick searching via Google.  As best I can see, the UVLC 
+> approach was part of the work on H.26L in Study Group 16.  I 
+> was going 
+> to SG 16 while they were working on this, but it wasn't in 
+> my area of 
+> interest.  I think the work migrated into an annex to 
+> MPEG-4. Hoin the 
+> ITU-T counterpart H.264.
+> 
+> Gary Sullivan (garysull at microsoft.com) may be able to help you.
+> 
+> Kelly Huang wrote:
+> > Dear experts,
+> > 
+> > When finding the best motion vector, we
+> > minimize the following equation
+> > "J(m,\lambda) = SAD(s,c(m))+\lambda R(m-p), where the rate 
+> term R(m-p) is
+> > estimated by UVLC table.
+> > 
+> > I have searched for this table for a long long time.
+> > I was wondering if anyone knows where could I find this
+> > table.
+> > 
+> > Best Regards
+> > Kelly
+> > 
+> > 
+> > 
+> > 
+> -------------------------------------------------------------
+> -----------
+> > 
+> > _______________________________________________
+> > Audio/Video Transport Working Group
+> > avt at ietf.org
+> > https://www1.ietf.org/mailman/listinfo/avt
+> 
+> 
+> _______________________________________________
+> Audio/Video Transport Working Group
+> avt at ietf.org
+> https://www1.ietf.org/mailman/listinfo/avt
+> 

_______________________________________________
Audio/Video Transport Working Group
avt at ietf.org
https://www1.ietf.org/mailman/listinfo/avt