Entropy encoding and decoding using direct level and run-length/level context-adaptive arithmetic coding/decoding modes

• US 8,090,574 B2
• Filed: 10/19/2010
• Issued: 01/03/2012
• Est. Priority Date: 09/04/2002
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mehrotra, Sanjeev, Chen, Wei-Ge
• Primary Examiner(s): Lerner, Martin
• Application Number:
  US12/907,848
• Publication Number:
  US 20110035225A1
• Time in Patent Office: 441 Days
• Field of Search: 704/230, 704/500, 704/501, 704/201, 704/203, 704/205, 704/206, 341/56, 341/59
• US Class Current: 704/205
• CPC Class Codes: G10L 19/032 Quantisation or dequantisation of spectral components
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code
• CPC Class Codes: H03M 7/4093 Variable length to variable length coding
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

An encoder performs context-adaptive arithmetic encoding of transform coefficient data. For example, an encoder switches between coding of direct levels of quantized transform coefficient data and run-level coding of run lengths and levels of quantized transform coefficient data. The encoder can determine when to switch between coding modes based on a pre-determined switch point or by counting consecutive coefficients having a predominant value (e.g., zero). A decoder performs corresponding context-adaptive arithmetic decoding.

Claims

1. A method of encoding audio or video data in a computing device that implements an encoder, the method comprising:

performing, by the computing device, a frequency transform on a block of plural samples to produce plural transform coefficients;

quantizing, by the computing device, the plural transform coefficients; and

entropy coding, by the computing device, the plural quantized transform coefficients, wherein the entropy coding includes;

encoding one or more of the plural quantized transform coefficients using a direct level encoding mode, including performing first context-adaptive arithmetic coding of a level value of a given coefficient of the plural quantized transform coefficients, wherein the first context-adaptive arithmetic coding uses a first set of plural contexts, and wherein the first context-adaptive arithmetic coding includes selecting one of the first set of plural contexts based at least in part on level values of two previously encoded quantized transform coefficients;

switching to a run-level encoding mode for remaining coefficients of the plural quantized transform coefficients;

encoding the remaining quantized transform coefficients using the run-level encoding mode, including;

performing second context-adaptive arithmetic coding of a non-zero level value of one of the remaining quantized transform coefficients, wherein the second context-adaptive arithmetic coding uses a second set of plural contexts different than the first set of plural contexts, and wherein the second context-adaptive arithmetic coding includes selecting one of the second set of plural contexts based at least in part on a level value of a previously encoded quantized transform coefficient; and

performing third context-adaptive arithmetic coding of a run value, the run value indicating a count of consecutive zero-value remaining quantized transform coefficients adjacent the remaining quantized transform coefficient with the non-zero level value, wherein the third context-adaptive arithmetic coding uses a third set of plural contexts different than the first set of plural contexts and different than the second set of plural contexts.

2. The method of claim 1 wherein the entropy coding further includes:

selecting the first context-adaptive arithmetic coding from among multiple encoding techniques available for the direct level encoding mode, wherein the multiple encoding techniques available for the direct level encoding mode further include variable length coding of level values; and

selecting the second context-adaptive arithmetic coding and the third context-adaptive arithmetic coding from among multiple encoding techniques available for the run-level encoding mode, wherein the multiple encoding techniques available for the run-level encoding mode further include variable length coding of run values and level values.

3. The method of claim 1 wherein the switching from the direct level encoding mode to the run-level encoding mode happens at a pre-determined switch point.

4. The method of claim 1 wherein the selected context from the first set of plural contexts changes depending on (1) whether the level value of a first of the two previously encoded quantized transform coefficients is zero or non-zero and (2) whether the level value of a second of the two previously encoded quantized transform coefficients is zero or non-zero.

5. The method of claim 1 wherein the encoding the remaining ones of the plural quantized transform coefficients using the run-level encoding mode includes repeating the second context-adaptive arithmetic coding and the third context-adaptive arithmetic coding for each of one or more other pairs of non-zero level value and run value.

6. The method of claim 5 wherein:

for a first non-zero level value in the run-level encoding mode, the selection of one of the second set of plural contexts considers the level value of the given quantized transform coefficient from the direct level encoding mode; and

for a subsequent non-zero level value in the run-level encoding mode, the selection of one of the second set of plural contexts considers the first non-zero level value.

7. A method of decoding audio or video data in a computing device that implements a decoder, the method comprising:

entropy decoding, by the computing device, plural quantized transform coefficients in a block, wherein the entropy decoding the encoded information includes;

decoding one or more of the plural quantized transform coefficients using a direct level decoding mode, including performing first context-adaptive arithmetic decoding of a level value of a given coefficient of the plural quantized transform coefficients, wherein the first context-adaptive arithmetic decoding uses a first set of plural contexts, and wherein the first context-adaptive arithmetic decoding includes selecting one of the first set of plural contexts based at least in part on level values of two previously decoded quantized transform coefficients;

switching to a run-level decoding mode for remaining coefficients of the plural quantized transform coefficients in the block;

decoding the remaining quantized transform coefficients using the run-level decoding mode, including;

performing second context-adaptive arithmetic decoding of a non-zero level value of one of the remaining quantized transform coefficients, wherein the second context-adaptive arithmetic decoding uses a second set of plural contexts different than the first set of plural contexts, and wherein the second context-adaptive arithmetic decoding includes selecting one of the second set of plural contexts based at least in part on a level value of a previously decoded quantized transform coefficient; and

performing third context-adaptive arithmetic decoding of a run value, the run value indicating a count of consecutive zero-value remaining quantized transform coefficients adjacent the remaining quantized transform coefficient with the non-zero level value, wherein the third context-adaptive arithmetic decoding uses a third set of plural contexts different than the first set of plural contexts and different than the second set of plural contexts; and

inverse quantizing, by the computing device, the plural transform coefficients in the block; and

performing, by the computing device, an inverse frequency transform on the plural transform coefficients to produce a block of the plural samples.

8. The method of claim 7 wherein the entropy decoding further includes:

selecting the first context-adaptive arithmetic decoding from among multiple decoding techniques available for the direct level decoding mode, wherein the multiple decoding techniques available for the direct level decoding mode further include variable length decoding of level values; and

selecting the second context-adaptive arithmetic decoding and the third context-adaptive arithmetic decoding from among multiple decoding techniques available for the run-level decoding mode, wherein the multiple decoding techniques available for the run-level decoding mode further include variable length decoding of run values and level values.

9. The method of claim 7 wherein the switching from the direct level decoding mode to the run-level decoding mode happens at a pre-determined switch point.

10. The method of claim 7 wherein the selected context from the first set of plural contexts changes depending on (1) whether the level value of a first of the two previously decoded quantized transform coefficients is zero or non-zero and (2) whether the level value of a second of the two previously decoded quantized transform coefficients is zero or non-zero.

11. The method of claim 7 wherein the decoding the remaining ones of the plural quantized transform coefficients using the run-level decoding mode includes repeating the second context-adaptive arithmetic decoding and the third context-adaptive arithmetic decoding for each of one or more other pairs of non-zero level value and run value.

12. The method of claim 11 wherein:

for a first non-zero level value in the run-level decoding mode, the selection of one of the second set of plural contexts considers the level value of the given quantized transform coefficient from the direct level decoding mode; and

for a subsequent non-zero level value in the run-level decoding mode, the selection of one of the second set of plural contexts considers the first non-zero level value.

13. A method of decoding audio or video data in a computing device that implements a decoder, the method comprising:

entropy decoding, by the computing device, plural quantized transform coefficients in a block, wherein the entropy decoding includes;

decoding one or more of the plural quantized transform coefficients using a first decoding mode, including performing first context-adaptive arithmetic decoding of a level value of a given coefficient of the plural quantized transform coefficients, wherein the first context-adaptive arithmetic decoding uses a first set of plural contexts, and wherein the first context-adaptive arithmetic decoding includes selecting one of the first set of plural contexts based at least in part on level values of two previously decoded quantized transform coefficients;

switching to a second decoding mode for remaining coefficients of the plural quantized transform coefficients in the block; and

decoding the remaining quantized transform coefficients using the second decoding mode, including;

performing second context-adaptive arithmetic decoding of a first level value and a second level value of a first remaining coefficient and second remaining coefficient, respectively, of the remaining quantized transform coefficients, wherein the second context-adaptive arithmetic decoding uses a second set of plural contexts different than the first set of plural contexts, and wherein;

for the first level value in the second decoding mode, the selection of one of the second set of plural contexts considers the level value of the given quantized transform coefficient from the first decoding mode; and

for the second level value in the second decoding mode, the selection of one of the second set of plural contexts considers the first level value; and

inverse quantizing, by the computing device, the plural transform coefficients in the block; and

performing, by the computing device, an inverse frequency transform on the plural transform coefficients to produce on a block of the plural samples.

14. The method of claim 13 wherein the first decoding mode is a direct level decoding mode, wherein the second decoding mode is a run-level decoding mode, and wherein the decoding the remaining coefficients using the second decoding mode further includes:

performing third context-adaptive arithmetic decoding of a run value, the run value indicating a count of consecutive zero-value remaining quantized transform coefficients adjacent the first or second level value in the second decoding mode, wherein the third context-adaptive arithmetic decoding uses a third set of plural contexts different than the first set of plural contexts and different than the second set of plural contexts.

15. The method of claim 14 wherein the entropy decoding further includes:

selecting the first context-adaptive arithmetic decoding from among multiple decoding techniques available for the direct level decoding mode, wherein the multiple decoding techniques available for the direct level decoding mode further include variable length decoding of level values; and

selecting the second context-adaptive arithmetic decoding and the third context-adaptive arithmetic decoding from among multiple decoding techniques available for the run-level decoding mode, wherein the multiple decoding techniques available for the run-level decoding mode further include variable length decoding of run values and level values.

16. The method of claim 13 wherein the switching from the direct level decoding mode to the run-level decoding mode happens at a pre-determined switch point.

17. The method of claim 13 wherein the selected context from the first set of plural contexts changes depending on (1) whether the level value of a first of the two previously decoded quantized transform coefficients is zero or non-zero and (2) whether the level value of a second of the two previously decoded quantized transform coefficients is zero or non-zero.