Entropy encoding and decoding scheme

Patent metadata

Field	Value
Publication number	US-9647683-B2
Application number	US-201615195696-A
Country	US
Kind code	B2
Filing date	Jun 28, 2016
Priority date	Jan 14, 2011
Publication date	May 9, 2017
Grant date	May 9, 2017

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.

First claim

What is claimed is:

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

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.

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.

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 .

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 .

Assignees

• Ge Video Compression Llc

Inventors

• Marpe Detlev
• Nguyen Tung
• Schwarz Heiko
• Wiegand Thomas

Classifications

• H03M7/4037

  Prefix coding · CPC title

• H03M7/55

  Compression Theory, e.g. compression of random number, repeated compression · CPC title

• H04N19/91

  Entropy coding, e.g. variable length coding [VLC] or arithmetic coding · CPC title

• H03M7/40 Primary

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title

• H03M7/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 title