Entropy encoding and decoding scheme

• US 9,647,683 B2
• Filed: 06/28/2016
• Issued: 05/09/2017
• 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:
  US15/195,696
• Publication Number:
  US 20160308555A1
• Time in Patent Office: 315 Days
• Field of Search: 341 50- 75
• 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. An entropy encoding apparatus comprising:

a decomposer configured to convert a sequence of syntax elements having a value range which is sub-divided into a sequence of N partitions into a sequence of source symbols by individually decomposing at least a subgroup of the syntax elements into a respective number n of source symbols s, with i=1 . . . n, the respective number n of source symbols depending on as to which of the sequence of N partitions 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;

a subdivider configured to subdivide the sequence of source symbols into a first subsequence of source symbols and a second subsequence of source symbols such that all source symbols s_x with x being member of a first subset of {1 . . . N} are contained within the first subsequence and all source symbols s_y with y being member of a second subset of {1 . . . N} being disjoint to the first subset, are contained within the second subsequence;

a VLC encoder configured to symbol-wisely encode the source symbols of the first subsequence; and

an arithmetic encoder configured to encode the second subsequence of source symbols,

wherein the values z of the subgroup of the syntax elements are absolute values, and

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

2. An entropy decoding apparatus comprising:

a VLC decoder configured to codeword-wisely reconstruct source symbols of a first subsequence of source symbols from codewords of a first bitstream;

an arithmetic decoder configured to reconstruct a second subsequence of source symbols; and

a composer configured to compose a sequence of syntax elements having a value range which is sub-divided into a sequence of N 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 n of source symbols by, for at least a subgroup of the syntax elements, determining the respective number n of source symbols s_i with i=1 . . . n depending on as to which of the 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, by summing-up the values of the respective number of source symbols s_i from 1 to n as long as the value of s, corresponds to a range of the i^th partition so as to obtain the value of the syntax element z, wherein the composer is configured to retrieve all source symbols s_x with x being member of a first subset of {1 . . . N} from the first subsequence and all source symbols s_y with y being member of a second subset of {1 . . . N} being disjoint to the first subset, from the second subsequence,

wherein the values z of the subgroup of the syntax elements are absolute values, and

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

3. The entropy decoding apparatus according to claim 2, wherein the second subset is {1} with the sequence of N partitions being arranged such that a p^th partition covers higher values of the value range than a q^th partition for all p,qε

{1 . . . N} with p>

q.

4. The entropy decoding apparatus according to claim 3, wherein N=3.

5. The entropy decoding apparatus according to claim 2, wherein 2 is element of the first subset with the VLC decoder being configured to use a Golomb-Rice code to codeword-wisely reconstruct the source symbols s₂.

6. The entropy decoding apparatus according to claim 2 further comprising a recombiner configured to recombine the first subsequence of source symbols and the second subsequence of source symbols to obtain the sequence of source symbols.

7. An entropy encoding method comprising:

converting a sequence of syntax elements having a value range which is sub-divided into a sequence of N partitions into a sequence of source symbols by individually decomposing at least a subgroup of the syntax elements 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 the sequence of N partitions 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;

subdividing the sequence of source symbols into a first subsequence of source symbols and a second subsequence of source symbols such that all source symbols s, with x being member of a first subset of {1 . . . N} are contained within the first subsequence and all source symbols s_y with y being member of a second subset of {1 . . . N} being disjoint to the first subset, are contained within the second subsequence;

by VLC encoding, symbol-wisely encoding the source symbols of the first subsequence; and

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

wherein the values z of the subgroup of the syntax elements are absolute values,

wherein the conversion by individual decomposition comprises adapting one or more of limits between the partitions according to previously encoded source symbols.

9. A non-transitory computer readable medium storing a computer program having a program code for performing, when running on a computer, a method according to claim 7.

8. An entropy decoding method comprising:

by VLC decoding, codeword-wisely reconstructing source symbols of a first subsequence of source symbols from codewords of a first bitstream;

by arithmetic decoding, reconstructing a second subsequence of source symbols;

composing a sequence of syntax elements having a value range which is sub-divided into a sequence of N 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 n of source symbols by, for at least a subgroup of the syntax elements, determining the respective number n of source symbols s_i with i=1 . . . n depending on as to which of the 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, by summing-up the values of the respective number of source symbols s_i from 1 to n as long as the value of s_i corresponds to a range of the i^th partition so as to obtain the value of the syntax element z, wherein the composing comprises retrieving all source symbols s_x with x being member of a first subset of {1 . . . N} from the first subsequence and all source symbols s_y with y being member of a second subset of {1 . . . N} being disjoint to the first subset, from the second subsequence,

wherein the values z of the subgroup of the syntax elements are absolute values,

wherein the composing comprises adapting one or more of limits between the partitions according to previously reconstructed source symbols.

10. A non-transitory computer readable medium storing a computer program having a program code for performing, when running on a computer, a method according to claim 8.