Image and video decoding implementations

Patent metadata

Field	Value
Publication number	US-9706214-B2
Application number	US-97850110-A
Country	US
Kind code	B2
Filing date	Dec 24, 2010
Priority date	Dec 24, 2010
Publication date	Jul 11, 2017
Grant date	Jul 11, 2017

Abstract

Efficient operations in image or video decoding. For example, a tool such as an image or video decoder receives and decodes encoded data for a picture in a bitstream. As part of the decoding, the tool adapts a multi-symbol lookup table to use in decoding of symbols then decodes the symbols using the multi-symbol lookup table, producing exactly correct results. The tool can also perform selectively truncated inverse frequency transforms. For a given block, the tool identifies upper horizontal and vertical frequencies among non-zero coefficients for the block and, based on the upper frequency values, selectively applies a simplified inverse frequency transform to transform coefficients for the block without hurting decoding quality. Using restart markers in the bitstream, the tool can organize multiple blocks of the picture as partitions. The tool decodes at least some of the partitions in parallel on a partition-by-partition basis using multiple processing cores.

First claim

We claim:

1. In a computing device that implements an image or video decoder, a method comprising:
receiving encoded data for a picture in a bitstream, the encoded data including plural symbols, each of the plural symbols being represented in the encoded data with a variable length code (VLC) or fixed length code (FLC), wherein the plural symbols include, for each of one or more run-level pairs for a block of the picture:
a run-level pair symbol indicating a run length of zero-value coefficients and a level category of a non-zero coefficient for the run-level pair;
a sign value symbol indicating a sign for the non-zero coefficient; and
depending on value of the level category of the non-zero coefficient, an offset value symbol indicating extra bits for the non-zero coefficient; and

with the computing device that implements the image or video decoder, decoding the encoded data for the picture, including:
adapting, during the decoding the encoded data for the picture, a multi-symbol lookup table to use in decoding the plural symbols in the encoded data for the picture, wherein the multi-symbol lookup table has up to 2 x entries indexed by possible combinations of x-bit values, respectively, wherein at least one entry of the multi-symbol lookup table associates a series of VLCs leading the x-bit value for that entry with a series of multiple symbols such that the series of VLCs consumes as many bits as possible from the x-bit value but leaves as undefined any bits of the x-bit value that indicate a partial symbol, and wherein the adapting the multi-symbol lookup table includes:
after the receiving the encoded data for the picture, reconstructing a VLC table for the picture during the decoding the encoded data for the picture, wherein the VLC table is changeable on a picture-by-picture basis; and
building the multi-symbol lookup table using the VLC table for the picture reconstructed during the decoding the encoded data for the picture; and

decoding the plural symbols using the multi-symbol lookup table, including:
loading x bits of the bitstream from a buffer;
searching for the loaded x bits in the multi-symbol lookup table;
if the loaded x bits indicate one or more whole symbols for one or more of the run-level pairs:
determining y bits that represent the one or more whole symbols indicated by the loaded x bits;
flushing the y bits from the buffer; and
if the one or more whole symbols indicated by the loaded x bits only partially indicate a given one of the run-level pairs, then:
 loading z additional bits of the bitstream from the buffer to determine any remaining symbols for the given run-level pair; and
 flushing the z bits from the buffer;

otherwise, if the loaded x bits indicate a partial symbol:
loading z additional bits of the bitstream from the buffer to determine a run-level pair symbol, a sign value symbol, and, depending on the run-level pair symbol, an offset value symbol, wherein the run-level pair symbol, sign value symbol and, if present, offset value symbol consume w bits of the loaded x+z bits, and wherein x<w<=x+z; and
flushing the w bits from the buffer.

2. The method of claim 1 wherein x is 8, 10 or 12, and wherein at least one other entry of the multi-symbol lookup table indicates the x-bit value for the other entry represents a partial symbol.

3. The method of claim 1 wherein the decoding the encoded data for the picture further includes decoding plural blocks of the picture, including, for a given block of the plural blocks:
identifying an upper horizontal frequency and upper vertical frequency among non-zero coefficients in plural transform coefficients for the given block;
selecting one of plural available inverse frequency transforms having different sizes based upon the upper horizontal frequency and the upper vertical frequency among non-zero coefficients for the given block; and
applying the selected inverse frequency transform to at least some of the plural transform coefficients for the given block to reconstruct plural sample values or prediction residual values for the given block.

4. A computer-readable memory device or storage device storing computer-executable instructions for causing a computing device, when programmed thereby, to perform:
receiving encoded data for a picture in a bitstream, the encoded data including plural symbols, each of the plural symbols being represented in the encoded data with a variable length code (VLC) or fixed length code (FLC), wherein the plural symbols include, for each of one or more run-level pairs for a block of the picture:
a run-level pair symbol indicating a run length of zero-value coefficients and a level category of a non-zero coefficient for the run-level pair;
a sign value symbol indicating a sign for the non-zero coefficient; and
depending on value of the level category of the non-zero coefficient, an offset value symbol indicating extra bits for the non-zero coefficient; and

decoding the encoded data for the picture, including:
adapting, during the decoding the encoded data for the picture, a multi-symbol lookup table to use in decoding the plural symbols in the encoded data for the picture, wherein the multi-symbol lookup table has up to 2 x entries indexed by possible combinations of x-bit values, respectively, wherein at least one entry of the multi-symbol lookup table associates a series of VLCs leading the x-bit value for that entry with a series of multiple symbols such that the series of VLCs consumes as many bits as possible from the x-bit value but leaves as undefined any bits of the x-bit value that indicate a partial symbol, and wherein the adapting the multi-symbol lookup table includes:
after the receiving the encoded data for the picture, reconstructing a VLC table for the picture during the decoding the encoded data for the picture, wherein the VLC table is changeable on a picture-by-picture basis; and
building the multi-symbol lookup table using the VLC table for the picture reconstructed during the decoding the encoded data for the picture; and

decoding the plural symbols using the multi-symbol lookup table, including:
loading x bits of the bitstream from a buffer;
searching for the loaded x bits in the multi-symbol lookup table;
if the loaded x bits indicate one or more whole symbols for one or more of the run-level pairs:
determining y bits that represent the one or more whole symbols indicated by the loaded x bits;
flushing the y bits from the buffer; and
if the one or more whole symbols indicated by the loaded x bits only partially indicate a given one of the run-level pairs, then:
 loading z additional bits of the bitstream from the buffer to determine any remaining symbols for the given run-level pair; and
 flushing the z bits from the buffer;

otherwise, if the loaded x bits indicate a partial symbol:
loading z additional bits of the bitstream from the buffer to determine a run-level pair symbol, a sign value symbol, and, depending on the run-level pair symbol, an offset value symbol, wherein the run-level pair symbol, sign value symbol and, if present, offset value symbol consume w bits of the loaded x+z bits, and wherein x<w<=x+z; and
flushing the w bits from the buffer.

5. A computing device comprising a processor and memory, wherein the computing device implements an image or video decoder adapted to:
receive encoded data for a picture in a bitstream, the encoded data including plural symbols, each of the plural symbols being represented in the encoded data with a variable length code (VLC) or fixed length code (FLC), wherein the plural symbols include, for each of one or more run-level pairs for a block of the picture:
a run-level pair symbol indicating a run length of zero-value coefficients and a level category of a non-zero coefficient for

Assignees

• Wu Yongjun
• Sadhwani Shyam
• Terdina Daniele
• Microsoft Technology Licensing Llc

Inventors

• Wu Yongjun
• Sadhwani Shyam
• Terdina Daniele

Classifications

• H04N19/122

  Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type · CPC title

• H04N19/176

  the region being a block, e.g. a macroblock · CPC title

• H04N19/14

  Coding unit complexity, e.g. amount of activity or edge presence estimation (H04N19/146 takes precedence) · CPC title

• H04N19/436

  using parallelised computational arrangements · CPC title

• H04N19/127

  Prioritisation of hardware or computational resources · CPC title