Entropy encoding and decoding scheme

• US 10,404,272 B2
• Filed: 11/21/2018
• Issued: 09/03/2019
• 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:
  US16/198,338
• Publication Number:
  US 20190097649A1
• Time in Patent Office: 286 Days
• Field of Search: 341 51- 70
• 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 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 source symbol of the first sequence using arithmetic context-based entropy coding and a source symbol of the second sequence using Exp-Golomb coding; 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.

2. The apparatus of claim 1, wherein the symbol decoder comprises:

a first decoder configured to;

receive a first portion of the data stream, and

reconstruct, using the arithmetic context-based entropy coding, 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, using the Exp-Golomb coding, source symbols of the second sequence of source symbols from codewords of the second portion of the data stream.

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

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

5. The apparatus of claim 1, wherein the plurality of disjoint portions includes a maximum of three portions.

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

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

8. The apparatus 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.

9. A method for decoding comprising:

obtaining, 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 obtaining includes obtaining a source symbol of the first sequence using arithmetic context-based entropy coding and a source symbol of the second sequence using Exp-Golomb coding; and

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

10. The method of claim 9, further comprising:

receiving a first portion of the data stream;

reconstructing, using the arithmetic context-based entropy coding, source symbols of the first sequence of source symbols from codewords of the first portion of the data stream;

receiving a second portion of the data stream; and

reconstructing, using the Exp-Golomb coding, source symbols of the second sequence of source symbols from codewords of the second portion of the data stream.

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

12. The method of claim 9, wherein the source symbols from the first sequence and the source symbols from the second sequence correspond to different portions.

13. The method of claim 9, wherein the plurality of disjoint portions includes a maximum of three portions.

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

15. The method of claim 9, wherein the method is implemented using a programmable logic device, a programmable gate array, a microprocessor, a computer or an electronic circuit.

16. The method of claim 9, further comprising:

adapting 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. 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, related to level values of transform coefficients of a transform coefficient block, and

obtain a sequence of source symbols based on the sequence of syntax elements by decomposing each syntax element into a corresponding set of source symbols based on a portion of the plurality of disjoint portions associated with the syntax element, such that a combination of values of the source symbols of the set yields the value of the syntax element; and

a symbol encoder configured to;

receive the sequence of source symbols,

sub-divide the sequence of source symbols into a first sequence of source symbols and a second sequence of source symbols, and

encode a source symbol of the first sequence using arithmetic context-based entropy coding and a source symbol of the second sequence using Exp-Golomb coding.

18. The apparatus of claim 17, wherein the symbol encoder includes:

a first encoder configured to encode the source symbols of the first sequence using the arithmetic context-based entropy coding; and

a second encoder configured to encode the source symbols of the second sequence using the Exp-Golomb coding.

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

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

21. The apparatus of claim 17, 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.

22. The apparatus of claim 17, 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.

23. A non-transitory computer-readable medium for storing video data, comprising:

a data stream stored in the non-transitory computer-readable medium and comprising data associated with a first sequence of source symbols and a second sequence of source symbols, wherein the source symbols of the first and second sequences are related to level values of transform coefficients of a transform coefficient block, and are obtained based on a sequence of syntax elements having a value range which is sub-divided into a plurality of disjoint portions by executing operations using a processor, the operations including;

decomposing each syntax element into a corresponding set of source symbols based on a portion of the plurality of disjoint portions associated with the syntax element, such that a combination of values of the source symbols of the set yields the value of the syntax element,

sub-dividing the sequence of source symbols into a first sequence of source symbols and a second sequence of source symbols, and

encoding a source symbol of the first sequence using arithmetic context-based entropy coding and a source symbol of the second sequence using Exp-Golomb coding.

24. The non-transitory computer-readable medium of claim 23, the operations further comprising:

encoding the source symbols of the first sequence using a first encoder; and

encoding the source symbols of the second sequence using a second encoder.

25. The non-transitory computer-readable medium of claim 23, wherein the first encoder or the second encoder is configured to encode a scaling factor.

26. The non-transitory computer-readable medium of claim 23, wherein a source symbol in the first sequence of source symbols corresponds to a first portion in the plurality of disjoint portions, and the plurality of disjoint portions is arranged such that the first portion covers lower values of the value range than a second portion of the plurality of disjoint portions.

27. The non-transitory computer-readable medium of claim 23, 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.

28. The non-transitory computer-readable medium of claim 23, wherein the plurality of disjoint portions includes a maximum of three portions.

29. The non-transitory computer-readable medium of claim 23, wherein a third portion of the data stream represents at least one scaling factor.

30. The non-transitory computer-readable medium of claim 23, wherein the operations further include adapting 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.