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

• US 9,390,720 B2
• Filed: 03/31/2014
• Issued: 07/12/2016
• Est. Priority Date: 09/04/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Mehrotra, Sanjeev, Chen, Wei-Ge
• Primary Examiner(s): Lerner, Martin
• Application Number:
  US14/231,415
• Publication Number:
  US 20140229186A1
• Time in Patent Office: 834 Days
• Field of Search: 704/203, 704/205, 704/206, 704/500, 704/501, 341/56, 341/59
• US Class Current: 1/1
• 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 computing device that implements an encoder, the computing device comprising:

one or more processors;

memory; and

one or more storage media storing instructions for causing the computing device to perform a method of encoding audio or video data, the method comprising;

performing a frequency transform on a block of plural samples to produce plural transform coefficients;

quantizing the plural transform coefficients; and

entropy coding 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 computing device 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 computing device 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 computing device 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 computing device 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 computing device 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. The computing device of claim 1 wherein the computing device includes a display and a wireless communication connection, and wherein the method further comprises transmitting, over the wireless communication connection, a bit stream comprising the encoded audio or video data.

8. A computing device that implements a decoder, the computing device comprising:

one or more processors;

memory; and

one or more storage media storing instructions for causing the computing device to perform a method of decoding audio or video data, the method comprising;

entropy decoding 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 the plural transform coefficients in the block; and

performing an inverse frequency transform on the plural transform coefficients to produce the block of the plural samples.

9. The computing device of claim 8 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.

10. The computing device of claim 8 wherein the switching from the direct level decoding mode to the run-level decoding mode happens at a pre-determined switch point.

11. The computing device of claim 8 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.

12. The computing device of claim 8 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.

13. The computing device of claim 12 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.

14. The computing device of claim 8 wherein the computing device includes a display and a wireless communication connection, and wherein the method further comprises receiving, over the wireless communication connection, a bit stream comprising the audio or video data.

15. One or more computer-readable storage media, comprising one or more of volatile memory, non-volatile memory, optical storage media, and magnetic storage media storing computer-executable instructions for causing a computing device that implements a decoder to perform a method of decoding audio or video data, the method comprising:

entropy decoding 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 the plural transform coefficients in the block; and

performing an inverse frequency transform on the plural transform coefficients to produce the block of the plural samples.

16. The one or more computer-readable storage media of claim 15 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.

17. The one or more computer-readable storage media of claim 16 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.

18. The one or more computer-readable storage media of claim 15 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 switching from the direct level decoding mode to the run-level decoding mode happens at a pre-determined switch point.

19. The one or more computer-readable storage media of claim 15 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.

20. The one or more computer-readable storage media of claim 15 wherein the switching from the first decoding mode to the second decoding mode happens based on a run count threshold that depends on a size of a current block being decoded.