vp3-format.txt

mediastreamer2是开源的网络传输媒体流的库

VP3 Bitstream Format and Decoding Process
by Mike Melanson (mike at multimedia.cx)
v0.5: December 8, 2004


[December 8, 2004: Note that this document is not complete and likely
will never be completed. However, it helped form the basis of Theora I 
specification available at
  http://www.theora.org/doc/Theora_I_spec.pdf ]


Contents
--------
 * Introduction
 * Underlying Coding Concepts
 * VP3 Coding Overview
 * VP3 Chunk Format
 * Decoding The Frame Header
 * Initializing The Quantization Matrices
 * Hilbert Coding Pattern
 * Unpacking The Block Coding Information
 * Unpacking The Macroblock Coding Mode Information
 * Unpacking The Macroblock Motion Vectors
 * Unpacking The DCT Coefficients
 * Reversing The DC Prediction
 * Reconstructing The Frame
 * Theora Specification
 * Appendix A: Quantization Matrices And Scale Factors
 * Appendix B: Macroblock Coding Mode Alphabets
 * Appendix C: DCT Coefficient VLC Tables
 * Appendix D: The VP3 IDCT
 * Acknowledgements
 * References
 * Changelog


Introduction
------------
A company named On2 (http://www.on2.com) created a video codec named
VP3. Eventually, they decided to open source it. Like any body of code
that was produced on a deadline, the source code was not particularly
clean or well-documented. This makes it difficult to understand the
fundamental operation of the codec.

This document describes the VP3 bitstream format and decoding process at
a higher level than source code.


Underlying Coding Concepts
-------------------------- 
In order to understand the VP3 coding method it is necessary to
understand the individual steps in the process. Like many multimedia
compression algorithms VP3 does not consist of a single coding method.
Rather, it uses a chain of methods to achieve compression.

If you are acquainted with the MPEG video clique then many of VP3's
coding concepts should look familiar as well. What follows is a list of
the coding methods used in VP3 and a brief description of each.

* Discrete Cosine Transform (DCT): This is a magical mathematical
function that takes a group of numbers and turns it into another group
of numbers. The transformed group of numbers exhibits some curious
properties. Notably, larger numbers are concentrated in certain areas of
the transformed group. 

A video codec like VP3 often operates on 8x8 blocks of numbers. When
these 8x8 blocks are transformed using a DCT the larger numbers occur
mostly in the up and left areas of the block with the largest number
occurring as the first in the block (up-left corner). This number is
called the DC coefficient. The other 63 numbers are called the AC
coefficients.

The DCT and its opposite operation, the inverse DCT, require a lot of
multiplications. Much research and experimentation is focused of
optimizing this phase of the coding/decoding process.

* Quantization: This coding step tosses out information by essentially
dividing a number to be coded by a factor and throwing away the
remainder. The inverse process (dequantization) involves multiplying by
the same factor to obtain a number that is close enough to the original.

* Run Length Encoding (RLE): The concept behind RLE is to shorten runs
of numbers that are the same. For example, the string "88888" is encoded
as (5, 8), indicating a run of 5 '8' numbers. In VP3 (and MPEG/JPEG),
RLE is used to record the number of zero-value coefficients that occur
before a non-zero coefficient. For example:

  0 0 0 0 5 0 2 0 0 0 9

is encoded as:

  (4, 5), (1, 2), (3, 9)

This indicates that a run of 4 zeroes is followed by a coefficient of 5;
then a run of 1 zero is followed by 2; then a run of 3 zeroes is
followed by 9.

* Zigzag Ordering: After transforming and quantizing a block of samples,
the samples are not in an optimal order for run length encoding. Zigzag
ordering rearranges the samples to put more zeros between non-zero
samples.

* Differential (or Delta) Pulse Code Modulation (DPCM): 1 + 1 = 2. Got
that? Seriously, that is what DPCM means. Rather than encoding absolute
values, encode the differences between successive values. For example:

  82 84 81 80 86 88 85

Can be delta-encoded as:

  82 +2 -3 -1 +6 +2 -3

Most of the numbers turn into smaller numbers which require less
information to encode.

* Motion Compensation: Simply, this coding method specifies that a block
from a certain position in the previous frame is to be copied into a new
position in the current frame. This technique is often combined with DCT
and DPCM coding, as well as fractional pixel motion.

* Entropy Coding (a.k.a. Huffman Coding): This is the process of coding
frequently occurring symbols with fewer bits than symbols that are not
likely to occur as frequently.

* Variable Length Run Length Booleans: An initial Boolean bit is
extracted from the bitstream. A variable length code (VLC) is extracted
from the bitstream and converted to a count. This count indicates that
the next (count) elements are to be set to the Boolean value.
Afterwards, the Boolean value is toggled, the next VLC is extracted and
converted to a count, and the process continues until all elements are
set to either 0 or 1.

* YUV Colorspace: Like many modern video codecs, VP3 operates on a YUV
colorspace rather than a RGB colorspace. Specifically, VP3 uses YUV
4:2:0, alias YUV420P, YV12. Note: Throughout the course of this
document, the U and V planes (a.k.a., Cb and Cr planes) will be
collectively referred to as C planes (color or chrominance planes).

* Frame Types: VP3 has intra-coded frames, a.k.a. intraframes, I-frames,
or keyframes. VP3 happens to call these golden frames. VP3 has
interframes, a.k.a. predicted frames or P-frames. These frames can use
information from either the previous interframe or from the previous
golden frame.


VP3 Overview
------------
The first thing to understand about the VP3 coding method is that it
encodes all 3 planes upside down. That is, the data is encoded from
bottom-to-top rather than top-to-bottom as is done with many video
codecs.

VP3 codes a video frame by first breaking each of the 3 planes (Y, U,
and V) into a series of 8x8 blocks called fragments. VP3 also has a
notion of superblocks. Superblocks encapsulate 16 fragments arranged in
a 4x4 matrix. Each plane has its own set of superblocks. Further, VP3
also uses the notion of macroblocks which is the same as that found in
JPEG/MPEG. One macroblock encompasses 4 blocks from the Y plane arranged
in a 2x2 matrix, 1 block from the U plane, and 1 block from the V plane.
While a fragment or a superblock applies to 1 and only 1 plane, a
macroblock extends over all 3 planes.

VP3 compresses golden frames by transforming each fragment with a
discrete cosine transform. Each transformed sample is then quantized and
the DC coefficient is reduced via DPCM using a combination of DC
coefficients from surrounding fragments as predictors. Then, each
fragment's DC coefficient is entropy-coded in the output bitstream,
followed by each fragment's first AC coefficient, then each second AC
coefficient, and so on.

An interframe, naturally, is more complicated. While there is only one
coding mode available for a golden frame (intra coding), there are 8
coding modes that the VP3 coder can choose from for interframe
macroblocks. Intra coding as seen in the keyframe is still available.
The rest of the modes involve encoding a fragment diff, either from the
previous frame or the golden frame, from the same coordinate or from the
same coordinate plus a motion vector. All of the macroblock coding modes
and motion vectors are encoded in an interframe bitstream.


VP3 Chunk Format
----------------
The high-level format of a compressed VP3 frame is laid out as:

 * chunk header
 * block coding information
 * macroblock coding mode information
 * motion vectors
 * DC coefficients
 * 1st AC coefficients
 * 2nd AC coefficients
 * ...
 * 63rd AC coefficients


Decoding The Frame Header
-------------------------
The chunk header always contains at least 1 byte which has the following
format:

  bit 7: 0 = golden frame, 1 = interframe
  bit 6: unused
  bits 5-0: Quality index (0..63)

Further, if the frame is a golden frame, there are 2 more bytes in the
header:

  byte 0: version byte 0
  byte 1:
    bits 7-3: VP3 version number (stored)
    bit 2:    key frame coding method (0 = DCT key frame, only type
              supported)
    bits 1-0: unused, spare bits

All frame headers are encoded with a quality index. This 6-bit value is
used to index into 2 dequantizer scaling tables, 1 for DC values and 1
for AC values. Each of the 3 dequantization tables is modified per these
scaling values.


Initializing The Quantization Matrices
--------------------------------------
VP3 has three static matrices for quantizing and dequantizing fragments.
One matrix is for quantizing golden frame Y fragments, one matrix is for 
quantizing golden frame C fragments, and one matrix is for quantizing both
golden frame and interframe Y or C fragments. While these matrices are
static, they are adjusted according to quality index coded in the header.

The quality index is an index into 2 64-element tables:
dc_scale_factor[] and ac_scale_factor[]. Each quantization factor from
each of the three quantization matrices is adjusted by the appropriate
scale factor according to this formula:

                base quantizer * scale factor
  quantizer  =  -----------------------------
                            100
     
    where scale factor =
        dc_scale_factor[quality_index] for DC dequantizer
        ac_scale_factor[quality_index] for AC dequantizer

The quantization matrices need to be recalculated at the beginning of a
frame decode if the current frame's quality index is different from the
previous frame's quality index.

See Appendix A for the complete VP3 quantization matrices and scale factor
tables.

As an example, this is the base quantization matrix for golden frame Y
fragments:

    16  11  10  16  24  40  51  61
    12  12  14  19  26  58  60  55
    14  13  16  24  40  57  69  56
    14  17  22  29  51  87  80  62
    18  22  37  58  68 109 103  77
    24  35  55  64  81 104 113  92
    49  64  78  87 103 121 120 101
    72  92  95  98 112 100 103  99

If a particular coded frame specifies a quality index of 54. Element 54
of the dc_scale_factor table is 20, thus:

                               16 * 20
  DC coefficient quantizer  =  -------  =  3
                                 100

Element 54 of the ac_scale_factor table is 24. The AC coefficient
quantizers are each scaled using this factor, e.g.:

    11 * 24
    -------   =  2
      100

    100 * 24
    --------  =  24
      100

[not complete; still need to explain how these quantizers are saturated
and scaled with respect to the DCT process]


Hilbert Coding Pattern
----------------------
VP3 uses a Hilbert pattern to code fragments within a superblock. A
Hilbert pattern is a recursive pattern that can grow quite complicated.
The coding pattern that VP3 uses is restricted to this pattern subset,
where each fragment in a superblock is represented by a 'X':

      X -> X    X -> X
           |    ^
           v    |
      X <- X    X <- X
      |              ^
      v              |
      X    X -> X    X
      |    ^    |    ^
      v    |    v    |
      X -> X    X -> X

As an example of this pattern, consider a plane that is 256 samples wide
and 64 samples high. Each fragment row will be 32 fragments wide. The
first superblock in the plane will be comprised of these 16 fragments:

   0   1   2   3  ...  31
  32  33  34  35  ...  63
  64  65  66  67  ...  95
  96  97  98  99  ... 127

The order in which these 16 fragments are coded is:

   0 |  0  1  14 15
  32 |  3  2  13 12
  64 |  4  7   8 11
  96 |  5  6   9 10

All of the image coding information, including the block coding status
and modes, the motion vectors, and the DCT coefficients, are all coded
and decoded using this pattern. Thus, it is rather critical to have the
pattern and all of its corner cases handled correctly. In the above
example, if the bottom row and left column were not present due to the
superblock being in a corner, the pattern proceeds as if the missing
fragments were present, but the missing fragments are omitted in the
final coding list. The coding order would be:

  0, 1, 2, 3, 4, 7, 8, 13, 14