Entropy encoding and decoding scheme

• US 10,224,953 B2
• Filed: 09/27/2017
• Issued: 03/05/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:
  US15/717,579
• Publication Number:
  US 20180019762A1
• Time in Patent Office: 524 Days
• Field of Search: 341 50- 95
• 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 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 obtained based on a sequence of syntax elements having a value range which is sub-divided into a sequence of N disjoint portions by executing operations using a processor, the operations including;

converting the sequence of syntax elements 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 disjoint portions a value z of a respective syntax element of the subgroup falls into, such that a sum of values of the respective number of source symbols s_i yields the value z, and, if n>

1, for all i=1 . . . n−

1, a value of s_i corresponds to a range of the i^th portion of the sequence of N disjoint portions;

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

encoding, using Variable Length Coding (VLC), each of the source symbols of the first sequence; and

encoding, using arithmetic encoding, each of the source symbols of the second sequence,

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

wherein x=2 is an element of the first subset and the VLC coding includes using a Golomb-Rice code to codeword-wisely reconstruct the source symbols s₂, and

wherein the converting of the sequence of syntax elements comprises adapting one or more of limits between the disjoint portions according to previously encoded source symbols.

2. The non-transitory computer-readable medium according to claim 1, wherein the second subset is {1} with the sequence of N disjoint portions being arranged such that a p^th portion covers higher values of the value range than a q^th portion for all p, q ∈

{1 . . N} with p>

q.

3. The non-transitory computer-readable medium according to claim 2, wherein N=3.

4. The non-transitory computer-readable medium according to claim 1, wherein the source symbols from the first sequence and the source symbols from the second sequence correspond to different disjoint portions.

5. The non-transitory computer-readable medium according to claim 1, wherein a source symbol in the second sequence of source symbols corresponds to a first-ordered portion in the sequence of N disjoint portions, and wherein the sequence of N disjoint portions is arranged such that a first portion covers higher values of the value range than a second portion.

6. The non-transitory computer-readable medium according to claim 1, wherein the adapting comprises adapting one or more of limits between the disjoint portions according to source symbols that were previously encoded according to a scan order.