Entropy encoding and decoding scheme

• US 9,473,169 B2
• Filed: 12/28/2015
• Issued: 10/18/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/980,671
• Publication Number:
  US 20160149588A1
• Time in Patent Office: 295 Days
• Field of Search: 341 50- 75, 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 first decoder, a first portion of a bitstream;

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

receiving, by a second decoder, a second portion of the bitstream;

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

retrieving, by a composer, source symbols from the first sequence and source symbols from the second sequence; 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 sequence of source symbols and the second sequence of source symbols by 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 so as to obtain the value of the syntax element,

wherein the composer is configured to adapt one or more of limits between the partitions according to previously reconstructed source symbols.

2. The method of claim 1, wherein a source symbol in the second sequence of source symbols corresponds to a 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.

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

4. The method of claim 3, wherein a source symbol in the second sequence of source symbols corresponds to a 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.

5. The method of claim 1, wherein a third portion of the bitstream represents at least one scaling factor.

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

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

8. The method of claim 1, wherein said reconstructing, by the first decoder, is performed by reconstructing the source symbols of the first sequence of source symbols from codewords of the first portion of the bitstream.

9. The method of claim 1, wherein the composer is configured to adapt at least one limit between the partitions during composing absolute transform coefficient levels of 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 a 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 spatially neighboring 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 the scan order the position of the absolute transform coefficient level to be composed.

19. 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.

10. An apparatus for decoding comprising:

a first decoder configured to;

receive a first portion of a bitstream, and

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

a second decoder configured to;

receive a second portion of the bitstream, and

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

a composer configured to;

retrieve source symbols from the first sequence and source symbols from the second sequence, and

compose a sequence of syntax elements having a value range which is sub-divided into a sequence of partitions from the first sequence of source symbols and the second sequence of source symbols by 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, so as to obtain the value of the syntax element,

wherein the composer is configured to adapt one or more of limits between the partitions according to previously reconstructed source symbols.

11. The apparatus of claim 10, wherein a source symbol in the second sequence of source symbols corresponds to a 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.

12. The apparatus of claim 10, wherein the source symbols from the first sequence and the source symbols from the second sequence correspond to different partitions.

13. The apparatus of claim 12, wherein a source symbol in the second sequence of source symbols corresponds to a 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 10, wherein the number of partitions equals one, two or three.

15. The apparatus of claim 10, wherein a third portion of the bitstream represents at least one scaling factor.

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

17. The apparatus of claim 10, wherein the first decoder is configured to reconstruct the source symbols of the first sequence by reconstructing the source symbols of the first sequence of source symbols from codewords of the first portion of the bitstream.

18. The apparatus of claim 10, wherein the composer is configured to adapt at least one limit between the partitions during composing absolute transform coefficient levels of 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 a 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 spatially neighboring 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.

20. 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 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;

a subdivider configured to;

receive the sequence of source symbols, and

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

a first encoder configured to;

receive the source symbols of the first sequence, and

encode the source symbols of the first sequence; and

a second encoder configured to;

receive the source symbols of the second sequence, and

encode the source symbols of the second sequence,

wherein the decomposer is configured to adapt one or more of limits between the partitions according to previously encoded source symbols.

21. The apparatus of claim 20, wherein a source symbol in the second sequence of source symbols corresponds to a 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.

22. The apparatus of claim 20, wherein the first or second encoder is further configured to encode a scaling factor.

23. The apparatus of claim 20, wherein the source symbols from the first sequence and the source symbols from the second sequence correspond to different partitions.

24. The apparatus of claim 23, wherein a source symbol in the second sequence of source symbols corresponds to a 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.

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

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