ENTROPY CODING/DECODING OF HIERARCHICALLY ORGANIZED DATA

• US 20100046626A1
• Filed: 08/22/2008
• Published: 02/25/2010
• Est. Priority Date: 08/22/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lin, Chih-Lung, Sun, Shijun, Regunathan, Shankar, Tu, Chengjie
• Granted Patent: US 8,406,307 B2
• Time in Patent Office: Days
• US Class Current: 375/240.180
• 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 data encoded as a set that has a hierarchy of subsets with set symbols, the method comprising:

receiving encoded data; and

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

evaluating a set symbol of the set;

selectively decoding a symbol combination code that indicates respective set symbols of plural subsets of the set;

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

for each of the plural subsets considered as a new set, selectively repeating the reconstructing for the new set.

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

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

if the set symbol of the 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 selective decoding includes, when the set symbol of the set is a first symbol element, skipping the decoding the symbol combination code, and otherwise performing the decoding the symbol combination code; and

the selectively repeating includes, for each of the plural subsets, repeating the reconstructing when the subset has multiple data values.

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

5. The method of claim 4 wherein the set symbol of the 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 set is the second symbol element, and wherein the size of the codebook is five when the set symbol of the set is the third symbol element.

6. The method of claim 1 wherein the decoding the symbol combination code 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.

7. The method of claim 1 wherein the decoding the symbol combination code 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.

8. The method of claim 1 wherein the decoding the symbol combination code includes selecting one of plural different context models to adapt to which of the data values are being decoded.

9. The method of claim 1 wherein:

in a first stage, the 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; and

in a later stage for each of the luma blocks and the chroma blocks of the macroblock, the set is the block, the set symbol of the block is block type of the block, and the data values in the block are quantized transform coefficients.

10. One or more storage media storing computer software instructions for causing a computer system to perform a method of encoding data as a set that has a hierarchy of subsets with set symbols, the method comprising:

receiving data values; and

encoding the data values as a set, including;

evaluating the data values of the set;

selectively encoding a symbol combination code that indicates respective set symbols of plural subsets of the set; and

for each of the plural subsets considered as a new set, selectively repeating the evaluating, the selective encoding and the selective repeating for the new set.

11. The storage media 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 subset that includes the data value, including:

if the set symbol of the 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 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 storage media of claim 10 wherein:

the selectively encoding includes, when each of the data values in the set is zero, skipping the encoding the symbol combination code, and otherwise performing the encoding the symbol combination code; and

the selectively repeating includes, for each of the plural subsets, repeating the evaluating, the selective encoding and the selective repeating when the subset has multiple data values.

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

14. The storage media of claim 10 wherein the encoding the symbol combination code 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.

15. The storage media of claim 10 wherein the encoding the symbol combination code 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.

16. The storage media of claim 10 wherein the encoding the symbol combination code includes selecting one of plural different context models to adapt to which of the data values are being encoded.

17. The one or more storage media of claim 10 wherein the set represents a macroblock whose set symbol is for a coded block pattern of the macroblock, and wherein each of the plural subsets represents a block whose set symbol is for block type.

18. The one or more storage media of claim 10 wherein the 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.

19. 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 in plural sets, each of the plural sets having a set symbol and plural subsets with set symbols, wherein the method includes, for each of the plural sets, reconstructing the set by;

evaluating a set symbol of the set;

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

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

for each of the plural subsets considered as a new set, repeating the reconstructing for the new set when the subset has multiple data values.

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

selecting the 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.