User:Orlando/XINTRA8 Decoding

From MultimediaWiki
Revision as of 15:02, 7 November 2009 by Orlando (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Decoding

Estimating Chroma QP

To obtain the Chroma QP from known Luma QP, perform the following operation:

chroma_qp = (9 * luma_qp + 3) / 8

Compute Inverse QP

Given Luma and Chroma QP, compute their respective inverse using the following operation:

iqp = (65536 + (qp / 2)) / qp

Overall Decoding Process

 for(y = 0; y < blocks_height; y++) {
   for(x = 0; x < blocks_width; x++) {
     decode_block(luma, x, y);
     if ((x & 1) && (y & 1)){
       decode_block(chroma_u, x/2, y/2);
       decode_block(chroma_v, x/2, y/2);
     }
   }
 }

Decoding a Block

Perform the following operations in order to decode a block:

  • Read Coefficients

If no residuals have been found:

  • Extrapolate Pixels, this is the resulting decoded block

Otherwise:

  • Perform IDCT on the Residuals
  • Extrapolate Pixels
  • Add with saturation the values from the IDCT to the Extrapolated Pixels

Reading Residual Coefficients

In order to read residual coefficients from the bitstream, you need to perform the following steps:

  • Fill Top/Left vectors
  • Predict the meta-direction
  • Predict the extrapolation mode and differential rank order
  • Predict the minimum number of AC coefficients before table switch
  • Read DC level
  • Read AC levels
  • Update prediction tables (Luma blocks only)
  • Perform dequantization of the DC
  • Eventually, perform inverse lifting

Fill Top/Left Vectors

The spatial extroplation begins filling the Top and Left vectors, estimating the pixel value range and the FLAT DC value to be used in FLAT extrapolation mode.

If at block (0, 0), then top and left vectors are filled with value 128, pixel range is 0 and FLAT DC value is 128, the function ends; otherwise the neighbors' pixels are analyzed.

Neighbors' pixels used in spatial extrapolation:

+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  | |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  | |16|17|18|19|20|21|22|23| |24|25|26|27|28|29|30|31| 
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ 
|  |  |  |  |  |  |  | 0| | 0| 1| 2| 3| 4| 5| 6| 7| | 8| 9|10|11|12|13|14|15| <- Top Vector
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  | 9| 1| |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |10| 2| |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ <- Predicted Block
|  |  |  |  |  |  |11| 3| |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |12| 4| |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |13| 5| |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |14| 6| |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |15| 7| |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |16| 8| |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
                       ^
                       +- Left Vector
  • Init sum to zero, this will be used to compute the average to pad missing pixels.
  • If x > 0, fill the left vector elements 1..16, and if y > 0 fill element 0.
    • Add the elements 1..8 to the sum, if y > 0 add element 0.
  • If y > 0, fill the top vector elements 0..7 - 16..23.
    Also, if not at the rightmost column, fill elements 8..15 - 24..31, otherwise pad them with last element of the respective row from the top block.
    • Add the elements 0..7 to the sum.
  • If x or y are zero, compute the average for padding missing neighbor pixels as follow and pad the missing vector elements:
    • Add 9 * avg to the sum, this compensates the missing pixels.
 avg = (sum + 4) / 8
  • Add to the sum the 8th and 9th elements of the top vector and compute the FLAT DC value as follow:
 flat_dc_value = (sum + 9) / 19
  • Last, compute the pixel value range, take the minimum and maximum pixel values from the elements 1..8 of the left vector and 0..7 of the top vector, subtract the minimum from the maximum to obtain the range.

Predict Meta Direction

There are three meta-directions:

 0 - NULL 
 1 - VERTICAL
 2 - HORIZONTAL

If the block is at the top or left edge, the predicted meta-direction is known a priori.

  • If block is at (0,0), meta-direction is NULL.
  • If block is at (0,y), meta-direction is VERTICAL.
  • If block is at (x,0), meta-direction is HORIZONTAL.

Now the prediction continues depending on the block plane.

  • For Chroma blocks:
    • Get the predicted meta-direction for the Luma block at the position (x * 2, y * 2), the prediction ends.
  • For Luma blocks:
    • Get the previously predicted meta-direction from top and left blocks.
    • If the left and top meta-directions are the same, then that's the predicted meta-direction.
    • If the left meta-direction is HORIZONTAL and the top is NULL, then it's HORIZONTAL.
    • If the left meta-direction is NULL and the top is VERTICAL, then it's VERTICAL.
    • In case of horizontal continuity, where left is HORIZONTAL and top is VERTICAL, the returned prediction is HORIZONTAL which overrides VERTICAL.
    • If the left meta-direction is VERTICAL and top is HORIZONTAL:
      • For low bitrate (QP > 12), use always the top block meta-direction.
      • For high bitrate, get the previously predicted top-left block meta-direction.
        • If the top-left meta-direction is equal to the top meta-direction, then predict from left.
        • If, instead, the meta-direction is equal to the left meta-direction, then predict from top.
        • In any other case, predict from top-left.
    • In any other case, the predicted meta-direction is NULL.

Predict Extrapolation Mode and Differential Rank Order

There are 13 different extrapolation modes (or orientations if you prefer), the known ones are:

 0 - NULL
 4 - VERTICAL
 8 - HORIZONTAL
10 - BLENDED HORIZONTALLY
11 - BLENDED VERTICALLY
   - FLAT

Modes 1-3,5-7,9 are diagonals of ~22.5 degrees, while FLAT mode has no mode index associated, and is signalled when certain conditions are met.

Algorithm:

  • Initially, the predicted extrapolation mode is set to NULL, likewise the differential rank order.
  • If the pixel range is less than the QP or less than 3, consider the predicted meta-direction as NULL and if range is less than 3, the FLAT mode is signalled.
  • For Chroma blocks:
    • The meta-direction needs to be mapped to its extrapolation mode counter part.
  • For Luma blocks:
    • If the aforementioned range is smaller than 2QP:
      • If block is at the top or left edge for non-FLAT mode, extrapolation mode is predicted to NULL.
      • If the block is not at top or left edge of the picture, then HORIZONTAL meta-direction maps into BLENDED HORIZONTALLY, while for VERTICAL meta-direction maps into BLENDED VERTICALLY.
      • In any other case the meta-direction is the predicted extrapolation mode.
    • Otherwise:
      • Read the differential rank order, which happens to be also the rank order index.
      • The predicted extrapolation mode is taken from the Rank Order table for the known meta-direction.

Reading Differential Rank Order/Rank Order Index

There are two different set of orientation tables, depending if Low bitrate or High bitrate is selected.

There are two VLC tables for low bitrate and four VLC tables for high bitrate, the encoder will transmit just once the table index for the current mode.

  • For Low bitrate, read 1 bit for table index.
  • For High bitrate, read 2 bits for table index.

Read the differential rank order/rank order index using the selected VLC table.

Predict minimum number of AC Coefficients

For Chroma blocks the predicted value is always 16.

For Luma blocks:

  • If block is at (0,0) the predicted minimum number of AC coefficients is always 16.
  • If block is at (0,y) predict from the left neighbor block.
  • If block is at (x,0) predict from the top neighbor block.

Otherwise the prediction is computed taking the minimum of the values between the top, left and top-left neighbor blocks in a sierpinski pattern.

Exemplary prediction pattern:

  1 2 3 4 5 6 7 8 9 A B C D E F 
1 X - X - X - X - X - X - X - X
2 - X X - - X X - - X X - - X X
3 X X X - X X X - X X X - X X X
4 - - - X X X X - - - - X X X X
5 X - X X X X X - X - X X X X X
6 - X X X X X X - - X X X X X X
7 X X X X X X X - X X X X X X X
8 - - - - - - - X X X X X X X X
9 X - X - X - X X X X X X X X X
A - X X - - X X X X X X X X X X
B X X X - X X X X X X X X X X X
C - - - X X X X X X X X X X X X
D X - X X X X X X X X X X X X X
E - X X X X X X X X X X X X X X
F X X X X X X X X X X X X X X X

X means the minimum of the three neighbor's values is taken.

- means the minimum of only the top and left neighbors is taken.

Reading DC Level

Once finished all the required predictions, you can perform the selection of the DC mode based on the number of the predicted AC coefficients, there are 3 DC modes:

 0 - INTRAZ  - Luma, predicted AC coefficients == 0
 1 - INTRANZ - Luma, predicted AC coefficients > 0
 2 - INTRAC0 - Chroma

Depending on the QP value, there are two more submodes, one for Low bitrate and the other for High bitrate. There are in total six different modes and each one has eight VLC tables used to read the DC level.

The encoder will transmit just once the VLC table index for the current mode. The table index is 3 bits long.

  • The DC value is read from the VLC reader.
  • Values greater than 16 signals that there are no AC coefficients encoded, subtract 17 to obtain the correct index.
  • If index is 0 then the level is zero and the function ends.
  • Get the number of DC level extra bits for the given index.
  • Set DC level to zero.
  • If there are extra bits, read them as the DC level.
  • Add the DC level bias for the given index to the DC level.
  • Read sign bit.

Reading AC Levels

If DC level did signal the presence of the AC coefficients, perform the following steps:

  • Select the Scan Table for the predicted Extrapolation Mode
  • Determine the AC mode, read below to know how.
  • Chroma blocks and Luma blocks where the AC mode is INTER0 or INTRAY0, do not perform table switch, so reset the predicted minimum AC coefficient count to 64.
  • By other means, the XINTRA8 decoder get to know if reconstruction levels are to be used (for example through the QUANTIZATION MATRIX bit in WMV), however for Luma blocks there are two extra conditions to use them:
    • The Extrapolation Mode is not FLAT.
    • The Differential Rank Order is not a Meta Direction (ie. >= 3)
  • Read the AC coefficients.

Determining AC Mode

Like the case for DC level, there are four different modes to read AC coefficients, and there are two submodes, one for Low bitrate and one for High bitrate. There are in total eight modes, and in turn each of this mode use 8 different VLC tables.

The mode selection depends on the Differential Rank Order and the predicted minimum number of AC coefficients.

The modes are:

0 - INTER0  - Luma, differential rank order > 4
1 - INTRAY  - Luma, differential rank order <= 4, predicted AC coefficient count > 1
              The symbol count is LESS than the predicted AC coefficient count.
2 - INTRAY0 - Luma, differential rank order <= 4, predicted AC coefficient count <= 1
              The symbol count is GREATER or EQUAL to the predicted AC coefficient count.
3 - INTER   - Chroma

Although there are four modes, only two tables are used, INTER0 and INTER share the same tables, so INTRAY and INTRAY0.

Reading AC Level

Having determinated the AC mode, select the right VLC table, the encoder will transmit just once the VLC table index for the current mode.

The VLC table index is 3 bits long, like in the DC level case.

Read code from the VLC reader, there are four different modes to read the AC level, the code itself determines the mode:

  • Mode 0 (Code Range: 0 - 45)
    If code > 22, signals there are no more AC coefficients following, subtract 23 to obtain the correct index.
   index < 16  | run= index    level=0
   index < 20  | run= index-16 level=1
   index < 22  | run= index-20 level=2
   index == 22 | run= index-22 level=3
  • Mode 1 (Code Range: 46 - 72)
    If code > 58, signals there are no more AC coefficients following, subtract 59 to obtain the correct index.
    • Use the index in a specific run/level table. TBD
  • Mode 2 (Code Range: 73 - 74)
    Code 74 signals there are no more AC coefficients.
    • Read 5 bits index from the bitstream.
    • Use the read index in another specific run/level table. TBD
  • Mode 3 (Code >= 75)
    If the code is odd, there are 4 bits per level, otherwise 7 bits are used.
    • Read 4 or 7 level bits.
    • Read 6 run bits.
    • Read 1 bit which signals if there are no more AC coefficients.

After reading the run/level, read 1 bit from the bitstream for the sign.

Perform dequantization of the AC level as follow:

  ac_level = quant_offset + (ac_level + 1) * 2 * luma_qp;
  if (sign) ac_level = -ac_level;

Reading AC Coefficients

  • Init count and pos to zero, count will be used to count coefficients to update prediction, while pos will be used for the zig-zag output.
  • Init last to false, this tells if there are no more AC coefficients.

Perform the following until there are no more AC coefficients:

  • If current AC mode isn't INTRAY0, and count + 1 is the predicted minimum AC coefficient, then switch AC mode to INTRAY0.
  • Read the AC run/level/last using the method described above.
  • Increment pos by run + 1.
  • If reconstruction levels are to be used perform the following operation:
 ac_level = (ac_level * reconstruction_levels[pos]) / 256
  • Write ac_level to the corrisponding output 8x8 block position using the selected scan table ordering.
  • Increment count by one.

Updating Prediction Tables

As mentionated above, there are two prediction tables, one for the Meta Direction and one for the AC coefficient count.

Updating Meta-Direction Prediction

Only Extrapolation Modes that are mappable to their Meta Direction counterparts are recorded, otherwise the Meta Direction to record is NULL.

Updating AC Coefficient Count Prediction

The number of AC coefficient present in this Luma block has to be recorded.

Dequantizing DC level

If there are no AC coefficients, check the DC level read, if it is zero, there are no residuals.

If there are no AC coefficients in FLAT extrapolation mode and DC value is in range -1..1 then the spatial extrapolated pixels will contain the final resulting block, that means no residuals. In this case quantize the FLAT DC value and dequantize it back:

 idc = quantize_dc (flat_dc_value * 8, iqp) + dc_level
 flat_dc_level = clamp ((idc * qp + 4) / 8);

where quantize_dc is:

 qdc = (dc * iqp + 32768) / 65536

and clamp is:

 x = (x < 0) ? 0 : (x > 255) ? 255 : x

Otherwise, dequantize the DC level read with 'qp' and write it to the output block. In this case, if not at top or left edge and DC level is not in the range -1..1, perform inverse lifting of the AC coefficients.

The 'qp' and 'iqp' parameters are different for Luma and Chroma blocks.

Inverse Lifting

There are four different types of lifting modes:

0 - The DCT levels are left untouched
1 - Horizontal Lifting
2 - Vertical Lifting
3 - Bidirectional Lifting

The correct lifting mode is determined by the Extrapolation Mode.

Horizontal lifting:

block[0][1] -= (6269 * dc_level + 32768) / 65536
block[0][3] -= (708  * dc_level + 32768) / 65536
block[0][5] -= (172  * dc_level + 32768) / 65536
block[0][7] -= (73   * dc_level + 32768) / 65536

Vertical lifting is a transposition of Horizontal lifting.

Bidirectional lifting is performed across all the levels in the DCT block using the following formula:

block[y][x] -= (bidi_lifting_weights[y][x] * dc_level + 32768) / 65536

Pixels Extrapolation

There are thirteen extrapolation mode defined, one being FLAT.

Mode 0

Also known as NULL mode.

Mode 1

block[i][j] = ((2 * i + 2 + j) > 15) ? 15 : (2 * i + 2 + j)

Mode 2

block[i][j] = top[i + j + 1]

Mode 3

block[i][j] = top[((i + 1) >> 1) + j]

Mode 4

Also known as VERTICAL mode.

block[i][j] = (top[j] + top[j + 16] + 1) >> 1

Mode 5

if (j > ((i - 1) >> 1))
  block[i][j] = top[j - ((i + 1) >> 1)];
else
  block[i][j] = left[i - 1 - 2 * j]

Mode 6

block[i][j] = (j > i) ? top[j - i - 1] : left[i - j]

Mode 7

if (j > 2 * i + 1)
  block[i][j] = (top[j - 2 * i - 2] + top[j - 2 * i - 1] + 1) >> 1
else if (j == 2 * i + 1)
  block[i][j] = (left[0] + top[0] + 1) >> 1
else
  block[i][j] =  left[i - (j >> 1)]

Mode 8

Also known as HORIZONTAL mode.

block[i][j] = (left[i + 1] + left[i + 9] + 1) >> 1

Mode 9

block[i][j] = (i + j < 6) ? left[i + j + 2] : left[8]

Mode 10

Also known as BLENDED HORIZONTALLY mode.

block[i][j] = (left[i + 1] * (8 - j) + top[j] * j + 4) >> 3

Mode 11

Also known as BLENDED VERTICALLY mode.

block[i][j] = (left[i + 1] * i + top[j] * (8 - i) + 4) >> 3

Flat Mode

The extrapolated block is filled with the computed flat_dc_level.

Constants

Scan Tables

Order by Extrapolation Mode

0, 2, 0, 1,
1, 1, 0, 2,
2, 0, 1, 2

NULL (0)

This corresponds to WMV Inter Scan Table.

0x00, 0x08, 0x01, 0x02, 0x09, 0x10, 0x18, 0x11,
0x0a, 0x03, 0x04, 0x0b, 0x12, 0x19, 0x20, 0x28,
0x30, 0x38, 0x29, 0x21, 0x1a, 0x13, 0x0c, 0x05,
0x06, 0x0d, 0x14, 0x1b, 0x22, 0x31, 0x39, 0x3a,
0x32, 0x2a, 0x23, 0x1c, 0x15, 0x0e, 0x07, 0x0f,
0x16, 0x1d, 0x24, 0x2b, 0x33, 0x3b, 0x3c, 0x34,
0x2c, 0x25, 0x1e, 0x17, 0x1f, 0x26, 0x2d, 0x35,
0x3d, 0x3e, 0x36, 0x2e, 0x27, 0x2f, 0x37, 0x3f

VERTICAL (1)

This corresponds to WMV IntraV Scan Table.

0x00, 0x01, 0x08, 0x02, 0x03, 0x09, 0x10, 0x18,
0x11, 0x0a, 0x04, 0x05, 0x0b, 0x12, 0x19, 0x20,
0x28, 0x30, 0x21, 0x1a, 0x13, 0x0c, 0x06, 0x07,
0x0d, 0x14, 0x1b, 0x22, 0x29, 0x38, 0x31, 0x39,
0x2a, 0x23, 0x1c, 0x15, 0x0e, 0x0f, 0x16, 0x1d,
0x24, 0x2b, 0x32, 0x3a, 0x33, 0x2c, 0x25, 0x1e,
0x17, 0x1f, 0x26, 0x2d, 0x34, 0x3b, 0x3c, 0x35,
0x2e, 0x27, 0x2f, 0x36, 0x3d, 0x3e, 0x37, 0x3f

HORIZONTAL (2)

This corresponds to WMV IntraH Scan Table.

0x00, 0x08, 0x10, 0x01, 0x18, 0x20, 0x28, 0x09,
0x02, 0x03, 0x0a, 0x11, 0x19, 0x30, 0x38, 0x29,
0x21, 0x1a, 0x12, 0x0b, 0x04, 0x05, 0x0c, 0x13,
0x1b, 0x22, 0x31, 0x39, 0x32, 0x2a, 0x23, 0x1c,
0x14, 0x0d, 0x06, 0x07, 0x0e, 0x15, 0x1d, 0x24,
0x2b, 0x33, 0x3a, 0x3b, 0x34, 0x2c, 0x25, 0x1e,
0x16, 0x0f, 0x17, 0x1f, 0x26, 0x2d, 0x3c, 0x35,
0x2e, 0x27, 0x2f, 0x36, 0x3d, 0x3e, 0x37, 0x3f

Reconstruction Levels

256, 256, 256, 256, 256, 256, 259, 262,
265, 269, 272, 275, 278, 282, 285, 288,
292, 295, 299, 303, 306, 310, 314, 317,
321, 325, 329, 333, 337, 341, 345, 349,
353, 358, 362, 366, 371, 375, 379, 384,
389, 393, 398, 403, 408, 413, 417, 422,
428, 433, 438, 443, 448, 454, 459, 465,
470, 476, 482, 488, 493, 499, 505, 511

Mode 0 Weights

TOP

640, 669, 708, 748, 792, 760, 808, 772,
480, 537, 598, 661, 719, 707, 768, 745,
354, 416, 488, 564, 634, 642, 716, 706,
257, 316, 388, 469, 543, 571, 655, 660,
198, 250, 317, 395, 469, 507, 597, 616,
161, 206, 266, 340, 411, 455, 548, 576,
122, 159, 211, 276, 341, 389, 483, 520,
110, 144, 193, 254, 317, 366, 458, 499

LEFT

 640,  480,  354,  257,  198,  143,  101,   72,
 669,  537,  416,  316,  250,  185,  134,   97,
 708,  598,  488,  388,  317,  241,  179,  132,
 748,  661,  564,  469,  395,  311,  238,  180,
 792,  719,  634,  543,  469,  380,  299,  231,
 855,  788,  710,  623,  548,  455,  366,  288,
 972,  914,  842,  758,  682,  584,  483,  390,
1172, 1107, 1028,  932,  846,  731,  611,  499

Inverse Lifting

Type by Extrapolation Mode

3, 0, 0, 1,
1, 3, 3, 3,
2, 2, 2, 1

Bidirectional Weights

   0,  3811,   487,   506,   135,   173,   61,   42,
3811, -1084,  -135,  -135,   -42,   -61,    0,    0,
 487,  -135,     0,     0,     0,     0,    0,    0,
 506,  -135,     0,     0,     0,     0,    0,    0,
 135,   -42,     0,     0,   -42,     0,    0,    0,
 173,   -61,     0,     0,     0,     0,    0,    0,
  61,     0,     0,     0,     0,     0,    0,    0,
  42,     0,     0,     0,     0,     0,    0,    0