Multi-level representation of reordered transform coefficients

• US 20090273706A1
• Filed: 05/02/2008
• Published: 11/05/2009
• Est. Priority Date: 05/02/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sun, Shijun, Lin, Chih-Lung, Regunathan, Shankar, Tu, Chengjie
• Granted Patent: US 8,179,974 B2
• Time in Patent Office: Days
• US Class Current: 348/420.100
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• 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/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/136 Incoming video signal characteristics or properties
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/162 User input
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/174 the region being a slice, e.g. a line of blocks or a group of blocks
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream
• CPC Class Codes: H04N 19/44 Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

Techniques and tools for encoding and decoding a block of frequency coefficients are presented. An encoder selects a scan order from multiple available scan orders and then applies the selected scan order to a two-dimensional matrix of transform coefficients, grouping non-zero values of the frequency coefficients together in a one-dimensional string. The encoder entropy encodes the one-dimensional string of coefficient values according to a multi-level nested set representation. In decoding, a decoder entropy decodes the one-dimensional string of coefficient values from the multi-level nested set representation. The decoder selects the scan order from among multiple available scan orders and then reorders the coefficients back into a two-dimensional matrix using the selected scan order.

Claims

1. One or more storage media storing instructions which, when executed on a computer, cause the computer to perform a method of encoding video, the method comprising:

selecting one of a plurality of scan orders;

outputting information indicating the selected scan order in a bit stream;

applying the selected scan order to reorder plural frequency coefficients of a block;

entropy coding the reordered plural frequency coefficients using a multi-level nested-set representation of the reordered frequency coefficients, including;

representing a first set of one or more of the reordered plural frequency coefficients as a summary representation with a first symbol at a first level of the multi-level nested-set representation; and

entropy coding the first symbol and a second symbol at the first level of the multi-level nested-set representation; and

outputting the entropy coded frequency coefficients in the bit stream.

2. The one or more storage media of claim 1 wherein the first symbol indicates the presence or absence of non-zero coefficient values among the first set of reordered frequency coefficients.

3. The one or more storage media of claim 1 wherein the second symbol represents one of the reordered plural frequency coefficients outside of the first set.

4. The one or more storage media of claim 3 wherein the entropy coding the first symbol and the second symbol includes jointly coding the first symbol and the second symbol using Huffman coding.

5. The one or more storage media of claim 1 wherein the entropy coding the first symbol and the second symbol includes run length coding the first symbol and the second symbol along with one or more other symbols.

6. The one or more storage media of claim 1 wherein the entropy coding further comprises:

representing a second set of one or more of the reordered plural frequency coefficients as a summary representation with the second symbol at the first level of the multi-level nested-set representation, wherein the entropy coding the first symbol and the second symbol includes jointly coding the first symbol and the second symbol using Huffman coding.

7. The one or more storage media of claim 1 wherein the first set includes at least one non-zero coefficient value, and wherein the entropy coding further comprises, at a second level of the multi-level nested-set representation lower than the first level, entropy coding coefficient values for the respective coefficients of the first set.

8. The one or more storage media of claim 1 wherein the first set includes at least one non-zero coefficient value, and wherein the entropy coding further comprises:

representing a first subset of one or more of the frequency coefficients of the first set as a summary representation with a first sub-symbol at a second level of the multi-level nested-set representation lower than the first level.

9. The one or more storage media of claim 8 further comprising entropy coding, at a third level of the multi-level nested-set representation lower than the second level, coefficient values for the respective coefficients of the first subset.

10. The one or more storage media of claim 1 wherein the selecting comprises:

evaluating plural pre-determined scan orders among the plurality of scan orders; and

if none of the plural pre-determined scan orders produces suitably reordered frequency coefficients for entropy encoding, creating a new scan order of the plurality of scan orders.

11. A method of reconstructing video, the method comprising:

receiving in a bit stream entropy encoded video information for plural frequency coefficients;

entropy decoding the entropy encoded video information, including;

entropy decoding a first symbol and a second symbol at a first level of a multi-level nested-set representation of the plural frequency coefficients, wherein the first symbol represents a first set of one or more of the plural frequency coefficients; and

entropy decoding a first sub-symbol at a second level lower than the first level of the multi-level nested-set representation of the plural frequency coefficients, wherein the first sub-symbol represents a first subset of one or more of the frequency coefficients of the first set;

determining a scan order for the plural frequency coefficients;

reordering the plural frequency coefficients according to the determined scan order; and

using the reordered frequency coefficients to reconstruct the video.

12. The method of claim 11 wherein the first symbol indicates the presence or absence of non-zero coefficient values in the first set.

13. The method of claim 12 wherein the second symbol at the first level of the multi-level nested-set representation of the plural frequency coefficients indicates the presence or absence of non-zero coefficient values in a second set of one or more of the plural frequency coefficients outside of the first set.

14. The method of claim 11 wherein the first sub-symbol indicates the presence or absence of non-zero coefficient values in the first subset.

15. The method of claim 11 wherein the determining the scan order comprises:

receiving scan order information in the bit stream, the scan order information indicating the determined scan order.

16. The method of claim 15 wherein the scan order is one of a plurality of pre-determined scan orders.

17. An encoder system comprising:

a block scan order selector adapted to select a scan order from a plurality of scan orders;

a block scanner adapted to reorder a plurality of frequency coefficients in a block using the selected scan order;

one or more entropy coding modules adapted to encode the reordered frequency coefficients in a multi-level nested-set representation by;

encoding plural symbols at a given level of the multi-level nested-set representation, each of the plural symbols at the given level representing a set of one or more of the reordered frequency coefficients; and

for each of the plural symbols at the given level, determining whether to split the set for the symbol into plural subsets and, if so, encoding plural sub-symbols at a lower level of the multi-level nested-set representation, each of the plural sub-symbols at the lower level representing one of the plural subsets.

18. The encoder system of claim 17 wherein the block scan order selector is adapted to select the scan order based upon the results of a closed-loop application of each of the plurality of scan orders to the block.

19. The encoder system of claim 17 wherein the block scan order selector is adapted to select the scan order based upon the results of an open-loop evaluation of application of one or more of the plurality of scan orders to the block.

20. The encoder system of claim 17 wherein the plurality of scan orders are pre-determined.