Entropy encoding and decoding scheme

• US 9,252,806 B2
• Filed: 06/09/2015
• Issued: 02/02/2016
• Est. Priority Date: 01/14/2011
• Status: Active Grant

• Current Assignee: GE Video Compression, LLC (General Electric Company)
• Original Assignee: GE Video Compression, LLC (General Electric Company)
• Inventors: Marpe, Detlev, Nguyen, Tung, Schwarz, Heiko, Wiegand, Thomas
• Primary Examiner(s): Mai, Lam T
• Application Number:
  US14/734,407
• Publication Number:
  US 20150270850A1
• Time in Patent Office: 238 Days
• Field of Search: 341 50- 71, 382/239, 382/243, 375/240.03, 375/240.02, 375/240.12, 375/240.16, 375/240.24, 375/240.18
• US Class Current: 1/1
• CPC Class Codes: H03M 7/00 Conversion of a code where information is represented by a given sequence or number of digits to a code where the same , similar or subset of information is represented by a different sequence or number of digits
• 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/4037 Prefix 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
• CPC Class Codes: H03M 7/55 Compression Theory, e.g. compression of random number, repeated compression

Abstract

Decomposing a value range of the respective syntax elements into a sequence of n partitions with coding the components of z laying within the respective partitions separately with at least one by VLC coding and with at least one by PIPE or entropy coding is used to greatly increase the compression efficiency at a moderate coding overhead since the coding scheme used may be better adapted to the syntax element statistics. Accordingly, syntax elements are decomposed into a respective number n of source symbols s_i with i=1 . . . n, the respective number n of source symbols depending on as to which of a sequence of n partitions into which a value range of the respective syntax elements is sub-divided, a value z of the respective syntax elements falls into, so that a sum of values of the respective number of source symbols s_i yields z, and, if n>1, for all i=1 . . . n−1, the value of s_i corresponds to a range of the i^th partition.

Claims

1. A method for decoding comprising:

receiving, by a VLC decoder, a first portion of a bitstream;

reconstructing, by the VLC decoder, source symbols of a first subsequence of source symbols from codewords of the first portion of a bitstream;

receiving, by an arithmetic decoder, a second portion of a bitstream;

reconstructing, by the arithmetic decoder, source symbols of a second subsequence of source symbols from codewords of the second portion of a bitstream;

retrieving, by a composer, source symbols from the first subsequence and source symbols from the second subsequence; and

composing, by the composer, a sequence of syntax elements having a value range which is sub-divided into a sequence of partitions from the first subsequence of source symbols and the second subsequence of source symbols by individually composing each syntax element from a respective number of source symbols by, for at least a subgroup of the syntax elements, determining the respective number of source symbols based on a value of the respective syntax elements and a partition of the sequence of partitions, and by summing-up the values of the respective number of source symbols, as long as the value of at least one source symbol corresponds to a range of a corresponding partition, so as to obtain the value of the syntax element;

wherein the subgroup of the syntax elements comprises absolute transform coefficient levels of absolute transform coefficients of transform blocks of a picture with the absolute transform coefficient levels of a respective transform block being arranged within the sequence of syntax elements in accordance with a scan path leading through the absolute transform coefficients of the respective transform blocks and;

wherein the composer is configured to adapt at least one limit between the partitions during composing the absolute transform coefficient levels of the absolute transform coefficients of a respective transform block.

2. The method of claim 1, wherein the values of the subgroup of the syntax elements are absolute values.

3. The method of claim 2, wherein a source symbol in the second subsequence of source symbols corresponds to the first-ordered partition in the sequence of partitions;

and

wherein the sequence of partitions is arranged such that a first partition covers higher values of the value range than a second partition.

4. The method of claim 1, wherein the source symbols from the first subsequence and the source symbols from the second subsequence correspond to different partitions.

5. The method of claim 4, wherein a source symbol in the second subsequence of source symbols corresponds to the first-ordered partition in the sequence of partitions;

and

wherein the sequence of partitions is arranged such that a first partition covers higher values of the value range than a second partition.

6. The method of claim 1, wherein the number of partitions equals three.

7. The method of claim 3, wherein a source symbol in the first subsequence of source symbols corresponds to the second-ordered partition and wherein the VLC decoder is configured to use a Golomb-Rice code to decode the source symbol in the first subsequence of source symbols.

8. The method of claim 1, further comprising a step of recombining, by a recombiner, the first subsequence of source symbols and the second subsequence of source symbols to obtain the sequence of source symbols.

9. The method of claim 1, wherein the step of reconstructing, by the VLC decoder, is performed by reconstructing the source symbols of the first subsequence of source symbols from codewords of the first portion of a bitstream.

10. The method of claim 1, wherein the composer is configured to adapt at least one limit between the partitions during composing the absolute transform coefficient levels of the absolute transform coefficients of a respective transform block depending on at least one of reconstructed absolute transform coefficient levels of absolute transform coefficients of the respective transform blocks preceding in the scan order, a position of the absolute transform coefficient level to be composed in the scan order, an evaluation of the reconstructed absolute transform coefficient levels of transform coefficients neighboring spatially the position of the absolute transform coefficient level to be composed, and an evaluation of the reconstructed absolute transform coefficient levels of transform coefficients neighboring in scan order the position of the absolute transform coefficient level to be composed.

21. A non-transitory computer readable medium including a computer program comprising program code for performing, when running on a computer, a method according to claim 1.

11. An apparatus for decoding comprising:

a VLC decoder configured to;

receive a first portion of a bitstream; and

reconstruct source symbols of a first subsequence of source symbols from codewords of the first portion of a bitstream;

an arithmetic decoder configured to;

receive a second portion of a bitstream; and

reconstruct a second subsequence of source symbols from codewords of the second portion of a bitstream;

a composer configured to;

retrieve all source symbols from the first subsequence and all source symbols from the second subsequence; and

compose a sequence of syntax elements having a value range which is sub-divided into a sequence of partitions from the first subsequence of source symbols and the second subsequence of source symbols by individually composing each syntax element from a respective number of source symbols by, for at least a subgroup of the syntax elements, determining the respective number of source symbols based on a value of the respective syntax elements and a partition of the sequence of partitions, and by summing-up the values of the respective number of source symbols, as long as the value of at least one source symbol corresponds to a range of a corresponding partition, so as to obtain the value of the syntax element;

wherein the subgroup of the syntax elements comprises absolute transform coefficient levels of absolute transform coefficients of transform blocks of a picture with the absolute transform coefficient levels of a respective transform block being arranged within the sequence of syntax elements in accordance with a scan path leading through the absolute transform coefficients of the respective transform blocks;

wherein the composer is configured to adapt at least one limit between the partitions during composing the absolute transform coefficient levels of the absolute transform coefficients of a respective transform.

12. The apparatus of claim 11, wherein the values of the subgroup of the syntax elements are absolute values.

13. The apparatus of claim 12, wherein a source symbol in the second subsequence of source symbols corresponds to the first-ordered partition in the sequence of partitions;

and

wherein the sequence of partitions is arranged such that a first partition covers higher values of the value range than a second partition.

14. The apparatus of claim 11, wherein the source symbols from the first subsequence and the source symbols from the second subsequence correspond to different partitions.

15. The apparatus of claim 14, wherein a source symbol in the second subsequence of source symbols corresponds to the first-ordered partition in the sequence of partitions;

and

wherein the sequence of partitions is arranged such that a first partition covers higher values of the value range than a second partition.

16. The apparatus of claim 11, wherein the number of partitions equals three.

17. The apparatus of claim 11, wherein a source symbol in the first subsequence of source symbols corresponds to the second-ordered partition and wherein the VLC encoder is configured to use a Golomb-Rice code to symbol-wisely encode the source symbol in the first subsequence of source symbols.

18. The apparatus of claim 11, wherein the apparatus is at least a portion of a programmable logic device, programmable gate array, microprocessor, computer or electronic circuit.

19. The apparatus of claim 11, wherein the VLC decoder is configured to reconstruct the source symbols of the first subsequence by codeword-wisely reconstructing the source symbols of the first subsequence of source symbols from codewords of the first portion of a bitstream.

20. The apparatus of claim 11, wherein the composer is configured to adapt at least one limit between the partitions during composing the absolute transform coefficient levels of the absolute transform coefficients of a respective transform block depending on at least one of reconstructed absolute transform coefficient levels of absolute transform coefficients of the respective transform blocks preceding in the scan order, a position of the absolute transform coefficient level to be composed in the scan order, an evaluation of the reconstructed absolute transform coefficient levels of transform coefficients neighboring spatially the position of the absolute transform coefficient level to be composed, and an evaluation of the reconstructed absolute transform coefficient levels of transform coefficients neighboring in scan order the position of the absolute transform coefficient level to be composed.

22. A method for encoding comprising:

receiving, by a decomposer, a sequence of syntax elements having a value range which is sub-divided into a sequence of partitions;

converting, by the decomposer, the sequence of syntax elements into a sequence of source symbols by individually decomposing at least a subgroup of the syntax elements into a corresponding number of source symbols, based on a value of the respective syntax elements and a partition of the sequence of partitions, so that a sum of values of the source symbols yields the value of the respective syntax element, wherein, if the number of source symbols is greater than one, a value of at least one source symbol corresponds to a range of a corresponding partition;

receiving, by a subdivider, the sequence of source symbols;

subdivide, by the subdivider, the sequence of source symbols into a first subsequence of source symbols and a second subsequence of source symbols;

receiving, by a VLC encoder, the source symbols of the first subsequence;

encoding, by the VLC encoder, the source symbols of the first subsequence;

receiving, by an arithmetic encoder, the source symbols of the second subsequence; and

encoding, by the arithmetic encoder, the second subsequence of source symbols;

wherein the subgroup of the syntax elements comprises absolute transform coefficient levels of absolute transform coefficients of transform blocks of a picture with the absolute transform coefficient levels of a respective transform block being arranged within the sequence of syntax elements in accordance with a scan path leading through the absolute transform coefficients of the respective transform blocks;

wherein the decomposer is configured to adapt at least one limit between the partitions during decomposing the absolute transform coefficient levels of the absolute transform coefficients of a respective transform block based on at least one of already encoded absolute transform coefficient levels of absolute transform coefficients of the respective transform blocks preceding in a scan order, a position of the absolute transform coefficient level to be decomposed in the scan order, an evaluation of the already reconstructed absolute transform coefficient levels of transform coefficients neighboring spatially the position of the absolute transform coefficient level to be decomposed, and an evaluation of the already reconstructed absolute transform coefficient levels of transform coefficients neighboring in scan order the position of the absolute transform coefficient level to be decomposed.

23. The method of claim 22, wherein the values of the syntax elements of the subgroup are absolute values.

24. The method of claim 22, wherein a source symbol in the second subsequence of source symbols corresponds to the first-ordered partition in the sequence of partitions;

and

wherein the sequence of partitions is arranged such that a first partition corresponds to higher values of the value range than a second partition.

25. The method of claim 24, wherein the number of partitions equals three.

26. The method of claim 22, wherein the step of encoding, by the VLC encoder, the source symbols of the first subsequence is performed by encoding the source symbols of the first subsequence.

27. An apparatus for encoding comprising:

a decomposer configured to;

receive a sequence of syntax elements having a value range which is sub-divided into a sequence of partitions; and

convert the sequence of syntax elements into a sequence of source symbols by individually decomposing at least a subgroup of the syntax elements into a corresponding number of source symbols, based on a value of the respective syntax elements and a partition of the sequence of partitions, so that a sum of values of the source symbols yields the value of the respective syntax element, wherein, if the number of source symbols is greater than one, a value of at least one source symbol corresponds to a range of a corresponding partition;

a subdivider configured to;

receive the sequence of source symbols; and

subdivide the sequence of source symbols into a first subsequence of source symbols and a second subsequence of source symbols;

a VLC encoder configured to;

receive the source symbols of the first subsequence; and

encode the source symbols of the first subsequence; and

an arithmetic encoder configured to;

receive the source symbols of the second subsequence; and

encode the second subsequence of source symbols;

wherein the subgroup of the syntax elements comprises absolute transform coefficient levels of absolute transform coefficients of transform blocks of a picture with the absolute transform coefficient levels of a respective transform block being arranged within the sequence of syntax elements in accordance with a scan path leading through the absolute transform coefficients of the respective transform blocks;

wherein the decomposer is configured to adapt at least one limit between the partitions during decomposing the absolute transform coefficient levels of the absolute transform coefficients of a respective.

28. The apparatus of claim 27, wherein the values of the subgroup of the syntax elements are absolute values.

29. The apparatus of claim 27, wherein a source symbol in the second subsequence of source symbols corresponds to the first-ordered partition in the sequence of partitions;

and

wherein the sequence of partitions is arranged such that a first partition covers higher values of the value range than a second partition.

30. The apparatus of claim 28, wherein the number of partitions equals three.