Entropy coding/decoding of hierarchically organized data

• US 8,406,307 B2
• Filed: 08/22/2008
• Issued: 03/26/2013
• Est. Priority Date: 08/22/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tu, Chengjie, Regunathan, Shankar, Sun, Shijun, Lin, Chih-Lung
• Primary Examiner(s): Sefcheck, Gregory
• Assistant Examiner(s): SMITH, JOSHUA Y
• Application Number:
  US12/197,124
• Publication Number:
  US 20100046626A1
• Time in Patent Office: 1,677 Days
• Field of Search: None
• US Class Current: 375/240.23
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

Techniques and tools for encoding and decoding data values that are hierarchically organized are presented. For example, an encoder encodes data as a set that has a hierarchy of subsets with set symbols. In the encoding, the encoder evaluates the data values of the set and selectively encodes a symbol combination code that indicates the set symbols of multiple subsets of the set. Then, for each of the multiple subsets considered as a new set, the encoder selectively repeats the evaluating, selective encoding and selective repetition for the new set. In corresponding decoding, a decoder decodes data encoded as a set that has a hierarchy of subsets with set symbols. In some implementations, the encoding and decoding are adaptive and use a symbol alphabet with nested elements.

Claims

1. A method of decoding video data hierarchically encoded as a set that has subsets with set symbols, the method comprising:

receiving encoded data; and

using the encoded data, reconstructing data values hierarchically encoded as a given set, including;

evaluating a set symbol of the given set;

selectively decoding a symbol combination code that indicates respective set symbols of plural subsets of the given set, including, when the set symbol of the given set is a first symbol element, skipping the decoding the symbol combination code, and otherwise performing the decoding the symbol combination code;

assigning the respective set symbols of the plural subsets to the plural subsets of the given set; and

for each of the plural subsets, selectively repeating the reconstructing when the subset has multiple data values, including, for a given subset of the plural subsets, evaluating the set symbol of the given subset, selectively decoding a symbol combination code that indicates respective set symbols of further subsets of the given subset, assigning the respective set symbols of the further subsets to the further subsets of the given subset, and, for each of the further subsets, selectively repeating the reconstructing for that further subset.

2. The method of claim 1 further comprising setting each of the data values depending on the set symbol of a lowest level subset that includes the data value, including:

if the set symbol of the lowest level subset that includes the data value is a first symbol element, setting the data value to zero;

if the set symbol of the lowest level subset that includes the data value is a second symbol element, decoding a sign bit and setting the data value to be 1 or −

1; and

otherwise, decoding a value code and sign bit and setting the data value depending on the value code and sign bit.

3. The method of claim 1 wherein the symbol combination code that indicates the respective set symbols of the plural subsets of the given set is a single variable length code that jointly indicates the respective set symbols of the plural subsets of the given set, and wherein the decoding the symbol combination code uses a codebook whose size depends on symbol element of the set symbol of the given set.

4. The method of claim 2 wherein the set symbol of the given set is selected from among first, second and third symbol elements, wherein the size of the codebook is three when the set symbol of the given set is the second symbol element, and wherein the size of the codebook is five when the set symbol of the given set is the third symbol element.

5. The method of claim 1 wherein the decoding the symbol combination code that indicates the respective set symbols of the plural subsets of the given set uses a codebook, and wherein the method further comprises, based upon history of occurrences of symbol combination codes in the encoded data, selecting the codebook from among plural available codebooks.

6. The method of claim 1 wherein the decoding the symbol combination code that indicates the respective set symbols of the plural subsets of the given set uses a codebook, and wherein the method further comprises, based upon history of occurrences of symbol combination codes in the encoded data, shuffling associations between variable length code entries and set symbol combinations represented in the codebook.

7. The method of claim 1 wherein the decoding the symbol combination code that indicates the respective set symbols of the plural subsets of the given set includes selecting one of plural different context models to adapt to which of the data values are being decoded.

8. The method of claim 1 wherein the given set is a macroblock, the set symbol of the macroblock is for a coded block pattern of the macroblock, and the symbol combination code indicates a luma block type and chroma block type for luma blocks and chroma blocks of the macroblock.

9. The method of claim 1 wherein the given set is a block of a macroblock, the data values in the block are quantized transform coefficients, and each of the plural subsets represents a group of one or more of the quantized transform coefficients.

10. A video encoder comprising a processor and one or more storage media storing computer software instructions for causing a computer system to perform a method of hierarchically encoding data as a set that has subsets with set symbols, the method comprising:

receiving data values; and

hierarchically encoding the data values as a given set, including;

evaluating the data values of the given set;

selectively encoding a symbol combination code that indicates respective set symbols of plural subsets of the given set, including, when each of the data values in the given set is zero, skipping the encoding the symbol combination code, and otherwise performing the encoding the symbol combination code; and

for each of the plural subsets, selectively repeating the evaluating, the selectively encoding and the selectively repeating when the subset has multiple data values, including, for a given subset of the plural subsets, evaluating the data values of the given subset, selectively encoding a symbol combination code that indicates respective set symbols of further subsets of the given subset, and, for each of the further subsets, selectively repeating the encoding for that further subset.

11. The video encoder of claim 10 wherein the method further comprises signaling one or more value codes for each of the data values to the extent the data value is not already implied by the set symbol of the lowest level subset that includes the data value, including:

if the set symbol of the lowest level subset that includes the data value is a first symbol element, signaling no value codes for the data value;

if the set symbol of the lowest level subset that includes the data value is a second symbol element, signaling a sign bit that indicates whether the data value is 1 or −

1; and

otherwise, signaling a value code and sign bit that indicate the data value.

12. The video encoder of claim 10 wherein the symbol combination code that indicates the respective set symbols of the plural subsets of the given set is a single variable length code that jointly indicates the respective set symbols of the plural subsets of the given set, and wherein the encoding the symbol combination code uses a codebook whose size depends on symbol element of the set symbol of the given set.

13. The video encoder of claim 10 wherein the encoding the symbol combination code that indicates the respective set symbols of the plural subsets of the given set uses a codebook, and wherein the encoding the data values further comprises, based upon history of occurrences of symbol combination codes, selecting the codebook from among plural available codebooks.

14. The video encoder of claim 10 wherein the encoding the symbol combination code that indicates the respective set symbols of the plural subsets of the given set uses a codebook, and wherein the encoding the data values further comprises, based upon history of occurrences of symbol combination codes, shuffling associations between variable length code entries and set symbol combinations represented in the codebook.

15. The video encoder of claim 10 wherein the encoding the symbol combination code that indicates the respective set symbols of the plural subsets of the given set includes selecting one of plural different context models to adapt to which of the data values are being encoded.

16. The video encoder of claim 10 wherein the given set represents a macroblock whose set symbol is for a coded block pattern of the macroblock.

17. The video encoder of claim 10 wherein the given set represents a block whose set symbol is for block type, and wherein each of the plural subsets represents a single quantized transform coefficient or group of plural quantized transform coefficients.

18. A video decoder comprising:

a processor; and

one or more storage media storing computer software instructions for causing a computer system to perform a method of decoding quantized transform coefficients hierarchically encoded in plural sets, each of the plural sets having a set symbol and plural subsets with set symbols, wherein the method includes, for each given set of the plural sets, reconstructing the given set by;

evaluating a set symbol of the given set;

selectively variable length decoding a symbol combination code that indicates respective set symbols of the plural subsets of the given set, including skipping the variable length decoding when the set symbol of the given set is a first symbol element and otherwise performing the variable length decoding;

assigning the respective set symbols of the plural subsets to the plural subsets of the given set; and

for each of the plural subsets of the given set, repeating the reconstructing when the subset has multiple data values, including for a given subset of the plural subsets of the given set, evaluating the set symbol of the given subset, selectively decoding a symbol combination code that indicates respective set symbols of further subsets of the given subset, assigning the respective set symbols of the further subsets to the further subsets of the given subset, and, for each of the further subsets, repeating the reconstructing for that further subset when the further subset has multiple data values.

19. The video decoder of claim 18 wherein the method further comprises adapting the variable length decoding by one or more of:

selecting a codebook from among plural available codebooks;

shuffling associations between variable length code entries and set symbol combinations represented in the codebook; and

selecting one of plural different context models to adapt to which of the quantized transform coefficients are being decoded.

20. A method of hierarchically encoding video data as a set that has subsets with set symbols, the method comprising:

receiving data values; and

hierarchically encoding the data values as a given set, including;

evaluating the data values of the given set;

selectively encoding a symbol combination code that indicates respective set symbols of plural subsets of the given set, including, when each of the data values in the given set is zero, skipping the encoding the symbol combination code, and otherwise performing the encoding the symbol combination code; and

for each of the plural subsets, selectively repeating the evaluating, the selectively encoding and the selectively repeating when the subset has multiple data values, including, for a given subset of the plural subsets, evaluating the data values of the given subset, selectively encoding a symbol combination code that indicates respective set symbols of further subsets of the given subset, and, for each of the further subsets, selectively repeating the encoding for that further subset.

21. The method of claim 20 wherein the method further comprises signaling one or more value codes for each of the data values to the extent the data value is not already implied by the set symbol of the lowest level subset that includes the data value, including:

if the set symbol of the lowest level subset that includes the data value is a first symbol element, signaling no value codes for the data value;

if the set symbol of the lowest level subset that includes the data value is a second symbol element, signaling a sign bit that indicates whether the data value is 1 or −

1; and

otherwise, signaling a value code and sign bit that indicate the data value.

22. The method of claim 20 wherein the symbol combination code that indicates the respective set symbols of the plural subsets of the given set is a single variable length code that jointly indicates the respective set symbols of the plural subsets of the given set, and wherein the encoding the symbol combination code uses a codebook whose size depends on symbol element of the set symbol of the given set.

23. The method of claim 20 wherein the encoding the symbol combination code that indicates the respective set symbols of the plural subsets of the given set uses a codebook, and wherein the encoding the data values further comprises, based upon history of occurrences of symbol combination codes, selecting the codebook from among plural available codebooks.

24. The method of claim 20 wherein the encoding the symbol combination code that indicates the respective set symbols of the plural subsets of the given set uses a codebook, and wherein the encoding the data values further comprises, based upon history of occurrences of symbol combination codes, shuffling associations between variable length code entries and set symbol combinations represented in the codebook.

25. The method of claim 20 wherein the encoding the symbol combination code that indicates the respective set symbols of the plural subsets of the given set includes selecting one of plural different context models to adapt to which of the data values are being encoded.

26. The method of claim 20 wherein the given set represents a macroblock whose set symbol is for a coded block pattern of the macroblock.

27. The method of claim 20 wherein the given set represents a block whose set symbol is for block type, and wherein each of the plural subsets represents a single quantized transform coefficient or group of plural quantized transform coefficients.