Entropy encoding and decoding scheme

Patent metadata

Field	Value
Publication number	US-9806738-B2
Application number	US-201715479787-A
Country	US
Kind code	B2
Filing date	Apr 5, 2017
Priority date	Jan 14, 2011
Publication date	Oct 31, 2017
Grant date	Oct 31, 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:

1. A method for decoding comprising:
obtaining, by a symbol decoder, based on codewords from a data stream, a first sequence of source symbols and a second sequence of source symbols, wherein source symbols of the first and second sequences are related to level values of transform coefficients of a transform coefficient block; and
composing, by a composer, a sequence of syntax elements having a value range which is sub-divided into a plurality of disjoint portions, by, for each syntax element:
obtaining a set of source symbols from the first and second sequences based on a portion of the plurality of disjoint portions associated with the syntax element, and
combining values of the source symbols of the set to determine the value of the syntax element,

wherein one or more limits between the plurality of disjoint portions are adapted according to one or more previously obtained source symbols, and
wherein the symbol decoder is configured to obtain a first source symbol of the first sequence using a Rice code and a second source symbol of the first sequence using an Exp-Golomb code.

2. The method of claim 1 , further comprising:
receiving, by a first decoder, a first portion of the data stream;
reconstructing, by the first decoder, source symbols of the first sequence of source symbols from codewords of the first portion of the data stream;
receiving, by a second decoder, a second portion of the data stream; and
reconstructing, by the second decoder, source symbols of the second sequence of source symbols from codewords of the second portion of the data stream.

3. The method of claim 1 , wherein a source symbol in the second sequence of source symbols corresponds to a first-ordered portion in the plurality of disjoint portions, and the plurality of disjoint portions is arranged such that a first portion covers higher values of the value range than a second portion.

4. The method of claim 1 , wherein the source symbols from the first sequence and the source symbols from the second sequence correspond to different portions of the plurality of disjoint portions.

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

6. The method of claim 2 , wherein one of the first decoder and the second decoder is configured to use arithmetic coding to reconstruct the source symbols, and the other of the first decoder and the second decoder is configured to use Golomb-Rice coding to reconstruct the source symbols.

7. The method of claim 1 , wherein the composer is configured to adapt at least one limit between the disjoint portions during composing absolute transform coefficient levels of the transform coefficients of the transform coefficient block based on at least one of:
a previously reconstructed absolute transform coefficient level of a transform coefficient preceding in a scan order,
a position of a current absolute transform coefficient level to be composed in the scan order,
an evaluation of previously reconstructed absolute transform coefficient levels of transform coefficients spatially neighboring the position of the current absolute transform coefficient level to be composed, and
an evaluation of previously reconstructed absolute transform coefficient levels of transform coefficients neighboring according to the scan order the position of the current absolute transform coefficient level to be composed.

8. An apparatus for decoding comprising:
a symbol decoder configured to:
obtain, based on codewords from a data stream, a first sequence of source symbols and a second sequence of source symbols, wherein source symbols of the first and second sequences are related to level values of transform coefficients of a transform coefficient block, wherein the symbol decoder is configured to obtain a first source symbol of the first sequence using a Rice code and a second source symbol of the first sequence using an Exp-Golomb code; and
a composer configured to:
compose a sequence of syntax elements having a value range which is sub-divided into a plurality of disjoint portions by, for each syntax element:
obtaining a set of source symbols from the first and second sequences based on a portion of the plurality of disjoint portions associated with the syntax element, and
combining values of the source symbols of the set to determine the value of the syntax element; and

adapt one or more limits between the plurality of disjoint portions according to previously obtained source symbols.

9. The apparatus of claim 8 , wherein the symbol decoder comprises:
a first decoder configured to:
receive a first portion of the data stream, and
reconstruct source symbols of the first sequence of source symbols from codewords of the first portion of the data stream; and
a second decoder configured to:
receive a second portion of the data stream, and
reconstruct source symbols of the second sequence of source symbols from codewords of the second portion of the data stream.

10. The apparatus of claim 8 , wherein a source symbol in the second sequence of source symbols corresponds to a first-ordered portion in the plurality of disjoint portions, and the plurality of disjoint portions is arranged such that a first portion covers higher values of the value range than a second portion.

11. The apparatus of claim 8 , wherein the source symbols from the first sequence and the source symbols from the second sequence correspond to different portions.

12. The apparatus of claim 8 , wherein the plurality of disjoint portions includes a maximum of three portions.

13. The apparatus of claim 8 , wherein a third portion of the data stream represents at least one scaling factor.

14. The apparatus of claim 8 , 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.

15. The apparatus of claim 9 , wherein one of the first decoder and the second decoder is configured to use arithmetic coding to reconstruct the source symbols, and the other of the first decoder and the second decoder is configured to use Golomb-Rice coding to reconstruct the source symbols.

16. The apparatus of claim 8 , the composer is configured to adapt at least one limit between the disjoint portions during composing absolute transform coefficient levels of the transform coefficients of the transform coefficient block based on at least one of:
a previously reconstructed absolute transform coefficient level of a transform coefficient preceding in a scan order,
a position of a current absolute transform coefficient level to be composed in the scan order,
an evaluation of previously reconstructed absolute transform coefficient levels of transform coefficients spatially neighboring the position of the current absolute transform coefficient level to be composed, and
an evaluation of previously reconstructed absolute transform coefficient levels of transform coefficients neighboring according to the scan order the position of the current absolute transform coefficient level to be composed.

17. A non-transitory computer readable medium including a computer program comprising program code for performing, when executing on a computing device, a method according to claim 1 .

18. 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 plurality of disjoint portions, wherein the sequence of syntax elements are related to level values of transform co

Assignees

• Ge Video Compression Llc

Inventors

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

Classifications

• H03M7/4037

  Prefix coding · CPC title

• H03M7/55

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

• H03M7/4006

  Conversion to or from arithmetic code · 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