CN100403801C - A context-based adaptive entropy encoding/decoding method - Google Patents

Abstract

A context-based adaptive entropy encoding/decoding method, when encoding: scan the quantized DCT coefficients in the current transform block, thereby forming a (level, run) pair sequence; and then log the pair sequence in the reverse order of scanning Entropy encoding is performed on each pair of numbers in the coded block. In the encoding process, the value of the encoded number pair in the encoded block is used to dynamically and adaptively construct the context statistical model. At the same time, a context model weighted fusion technology is also proposed to further improve the model. Compression performance; entropy coding is driven by the context statistical model obtained in the previous step. The context-based adaptive entropy decoding method is the inverse of the encoding method. The invention realizes the description of the long-memory Markov model with a small number of context states, and has higher compression performance.

Description

A context-based adaptive entropy encoding/decoding method

technical field

The technical field that the present invention relates to is multimedia (image, video, audio frequency) compression and transmission, especially a kind of DCT coefficient self-adaptive entropy encoding/decoding method for signal compression based on context modeling. The object of the present invention is to improve the quality of the statistical context model in adaptive entropy coding of DCT coefficients. In all data compression techniques and systems, adaptive entropy coding plays a crucial role, and adaptive entropy coding must be driven by statistical context models. The quality of the statistical context model will ultimately determine the compression performance of the entire system.

Background technique

Discrete Cosine Transform (DCT for short) is widely used in the compression of video/image/audio signals. After DCT transformation, the statistical and subjective redundancy of the signal can be better understood, utilized and removed. Therefore, the transformed signal is also more suitable for compression. Most of the current international and domestic signal compression standards (such as JPEG, MPEG, H.264, China Audio/Video Standard (AVS for short)) adopt the method of encoding in the DCT transform domain, which fully reflects the The effectiveness of the DCT transformation. However, the DCT transformation itself does not produce any reduction in the amount of data, because the number of transformed coefficients is the same as the original number of samples of the signal. What really achieves the compression effect is the entropy coding process of the DCT coefficients. Any entropy coding method of DCT coefficients, such as Huffman (Huffman) codes, arithmetic codes, must utilize the estimation of the probability distribution of DCT coefficients.

In a practical DCT-based signal compression system, the DCT coefficients will be entropy-encoded sequentially according to a certain agreed scanning order. One of the most popular scan sequences is the zigzag scan employed in the JPEG and MPEG standards. The method in the present invention is universal and can be applied to any scanning order of DCT coefficients.

If x ₁ , x ₂ ,..., x _N represent the scanned DCT coefficient sequence, where N reflects the size of the block used for DCT transformation, then the minimum code length required to encode the sequence is:

${\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; log</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; .</span>$

下，算术编码可以实现编码长度 ${-\log }_2\underset{i=1}{\overset{N}{\mathrm{\&Pi;}}}\hat{P}\left(x_i\right|{\tilde{x}}^{i-1})$ 。问题的关键在于如何进行概率估计以使

成为条件概率P(x_i|x^i-1)的良好估计。表示序列x^i-1中对当前系数x_i的统计特性有重要意义的某个子序列，称为模型上下文(Context)。所估计的条件概率

用作信源的统计模型。Wherein, x ^i-1 represents a sequence {xi _-1 , x _i-1 , . . . x ₁ } formed by all coefficients before the current coefficient x _i . If the conditional probability P( _xi |xi ^-1 ) is known, adaptive arithmetic coding can approach the ideal minimum code length L _min . In conditional probability estimation

Under, arithmetic coding can realize code length ${-\mathrm{<figure-callout\; id="2"\; label="log"\; filenames="C20051010485300152.png,C20051010485300161.png"\; state="\{\{state\}\}">log</figure-callout>}}_2\underset{i=1}{\overset{N}{\mathrm{\&Pi;}}}\hat{P}\left(x_i\right|{\tilde{x}}^{i-1})$ . The key to the problem is how to estimate the probability so that

becomes a good estimate of the conditional probability P( _xi |xi ^-1 ). Represents a certain subsequence in the sequence xi ^-1 that is significant to the statistical properties of the current coefficient _xi , called the model context (Context). Estimated conditional probability

Statistical models used as sources.

Statistical context models in the form of probability estimates are at the heart of all signal compression systems. The quality of the model, i.e. the accuracy of the probability estimates, will ultimately determine the compression performance.

Nokia (Nokia) proposed a (run, level) for the DCT coefficient block in 2001 for the H264 standard reference model TML85 (level is a non-zero residual coefficient, run represents the zero between the current non-zero coefficient and the previous non-zero coefficient The number of coefficients) is a method for adaptive binary arithmetic coding of sequences. This method encodes each number pair sequentially in the "same" order as when the number pair is scanned and generated, and only uses the nearest level value in the coefficient block to construct the context (first-order Markov model) during encoding. The patent publication No. US2004112683 for this method discloses a method for encoding transform coefficients. The encoding of the DCT coefficient block is completed through two forward and reverse scans. In the first forward scan, the context is constructed according to the physical frequency position of the coefficient to encode the first bit plane (ie Significant Map) of the coefficient. The encoding of other bit-planes with non-zero coefficients is completed in the second inverse scan. However, this method does not describe the long-memory Markov model, and the compression performance is relatively low.

Contents of the invention

The purpose of the present invention is to address the shortcomings of the above-mentioned existing coding technology, provide a DCT coefficient adaptive entropy coding/decoding method for signal compression based on context modeling, improve the existing DCT coefficient entropy coding/decoding technology, Provide a high-performance entropy coding module for China AVS, making the overall performance of China AVS system reach or even exceed the level of the most advanced video compression technology in the world.

In order to achieve the above object, the present invention adopts a DCT coefficient adaptive entropy encoding/decoding method for signal compression based on context modeling, wherein, during encoding, the following steps are performed:

Step 1. Scan the current DCT-transformed and quantized coefficient block to form a sequence of (level, run) pairs to obtain the number of non-zero coefficients; initialize the context model of the coefficient block;

Step 2, if the value of the non-zero coefficient is zero, then obtain the EOB information (EOB is the block end mark End of Block), i.e. a (0, 0) number pair; if the value of the non-zero coefficient is not is zero, then search the (level, run) number pairs on the position of the number of non-zero coefficients in the scan result;

Step 3. If the first coefficient is coded, construct the first context according to the empty sequence; otherwise, construct the first context according to all pairs of numbers that have been coded in the coefficient block, and use the context weighting method to calculate the current level The absolute value is entropy encoded;

Step 4. If the number of non-zero coefficients is zero, then the encoding ends; otherwise, according to the absolute value of all the encoded numbers in the coefficient block and the encoded level in step 3, the level The sign bit is encoded;

Step 5. Constructing a second context according to all pairs of numbers that have been coded in the coefficient block and the absolute value and sign bit of the coded current level in steps 3 and 4, and performing entropy coding on run;

Step 6. Subtract 1 from the value of the non-zero coefficient, and execute step 2.

When decoding, perform the following steps:

Step 1. Initialize the first and second context models;

Step 2. Scan the Level amplitude in the first (Level, Run) number pair in reverse order, and obtain the first Level amplitude by decoding according to the first context model;

Step 3, if the obtained Level amplitude is zero, then get the EOB information, that is, a (0,0) number pair, and execute step 7; otherwise, execute step 4;

Step 4, decode to obtain the sign bit of level;

Step 5. Construct a second context based on all the pairs of numbers that have been decoded and the value of the current level just decoded in steps 2 and 3, and decode to obtain Run;

Step 6. Construct the first context according to all the pairs of numbers that have been decoded, and use context weighting technology to decode and obtain the absolute value of level in the next (Level, Run) number pair; perform step 3;

Step 7: Restoring the coefficient block according to the sequence of (Level, Run) pairs obtained through the decoding.

Considering the practicability and compatibility, the technical details of the present invention have been carefully adjusted to the direction suitable for the Chinese AVS benchmark version, making a natural and significant improvement and extension to the current Chinese AVS system.

(1) The present invention encodes each number pair sequentially according to the "reverse" order of the number pair scan generation, and the encoding order of this reverse scanning order obviously improves the effectiveness of the context model.

(2) At the same time, when encoding, use all the coded (level, run) pairs in this coefficient block to construct the context (higher-order Markov model), and innovatively use the context weighting technology. This method can combine multiple contexts The models are fused together to improve compression performance.

(3) The present invention adopts an innovative context quantification method to realize the use of a small number of context states to describe the long-memory Markov model, thereby avoiding the adverse effects of the context dilution problem when describing the high-order Markov model .

Compared with the prior art, the present invention does not increase the computational complexity when realizing the above object, is suitable for real-time application, and has compatibility with the Chinese AVS benchmark video codec framework.

The technical solutions of the present invention will be described in further detail below in conjunction with the accompanying drawings and embodiments.

Description of drawings

Fig. 1 is the encoding flowchart of the present invention;

Fig. 2 is the decoding flowchart of the present invention;

Figure 3 is an example of zig-zag scanning;

Fig. 4 is the encoding order of block coefficients in the present invention.

Detailed ways

As shown in Figures 1 and 2, it is Embodiment 1 of the present invention, and the specific encoding steps are:

Step 101, scan the current DCT-transformed and quantized coefficient block to form a sequence of (level, run) pairs to obtain the number of non-zero coefficients; initialize the context model of the coefficient block;

Step 102, if the value of the non-zero coefficient is zero, then obtain EOB information, that is, a (0,0) number pair; if the value of the non-zero coefficient is not zero, then search for the value of the non-zero coefficient in the scan result (level, run) number pairs at the position of the number of non-zero coefficients;

Step 103, if the first coefficient is coded, construct the first context according to the empty sequence; otherwise, construct the first context according to all pairs of numbers that have been coded in the coefficient block, and use the context weighting method to calculate the current level The absolute value is entropy encoded; constructing the first context includes: defining two random variables, the first random variable is used to record the amplitude change information of the level in all pairs of numbers that have been coded in this coefficient block, and the second random variable Recording the position of the current to-be-encoded level in the reverse scanning order; according to the two random variables, constructing the first context through context weighting, and using a small number of context states to describe the long memory Markov model;

Step 104, if the number of non-zero coefficients is zero, then the encoding ends; otherwise, according to the absolute value of all the number pairs that have been encoded in the coefficient block and the level just encoded in step 3, the sign bit of the level to encode;

Step 105: Construct a second context according to all the pairs of numbers that have been encoded in the coefficient block and the value of the current level just encoded in steps 3 and 4, and entropy encode the run; constructing the second context includes: defining two random Variables, the first random variable is used to record the amplitude change information of the level in all pairs of numbers that have been coded in this coefficient block, and the other records the absolute value of the current level that has been coded in step 3. Through these two The variable construction context encodes the run;

Step 106: Subtract 1 from the value of the non-zero coefficient, and execute step 2.

When decoding, perform the following steps:

Step 201, initialize the context model;

Step 202, the Level amplitude in the first (Level, Run) number pair scanned in reverse order, and decoded according to the context model to obtain the first Level amplitude;

Step 203, if the obtained Level amplitude is zero, then get the EOB information, that is, a (0,0) number pair, and execute step 7; otherwise, execute step 4;

Step 204, decoding to obtain the sign bit of level;

Step 205, construct a context according to all the pairs of numbers that have been decoded in this coefficient block and the value of the current level just decoded in steps 2 and 3, and decode to obtain Run;

Step 206, construct context according to all the number pairs that have been decoded in this coefficient block, and use context weighting technology to decode to obtain the absolute value of level in the next (Level, Run) number pair; perform step 3;

Step 207: Restore the coefficient block according to the sequence of (Level, Run) pairs obtained through the decoding.

The following is embodiment two of the present invention, and embodiment 2 is the implementation of the present invention in Chinese AVS:

Description of the key technologies of this embodiment:

1. Scanning order and encoding order of DCT coefficient blocks:

Scanning of DCT coefficients is a process of arranging two-dimensional or multi-dimensional DCT coefficients into a one-dimensional sequence. The principle followed is to make the probability of the coefficients being zero after the arrangement show an increasing law. The classic zigzag scanning in JPEG and MPEG, the scanning of AVS coefficient blocks in China, and the scanning methods for different coefficient block sizes and different field/frame modes in H264 all follow this rule.

The scanned one-dimensional coefficient random sequence approximately satisfies the law of increasing probability of zero. After converting into (level, run) pairs, we encode each pair in the reverse order of scanning and in increasing order of coefficient "non-zero" probability.

2. Binarization of elements to be encoded:

Before performing binary arithmetic coding, it is first necessary to convert the values of the elements to be coded: level and run into a series of binary decisions (Binary Decision).

level is a signed integer. Firstly, the sign bit is separated, and 1 bit "0/1" is used to represent "+/-"; the remaining absolute value part is a non-negative integer, and the binarization is realized through Unary representation. For example: the binarization of -2 is (1)001, and the binarization of +1 is (0)01.

run is an unsigned integer. Binarization is realized directly through Unary representation.

Table 1: Binarization implementation

Table 1 shows the structure of binarizing non-negative integers through Unary representation. It can be seen that the result of binarization is composed of a prefix and a suffix: the prefix code is a string composed of several 0s, and the suffix is a 1 at the end; the binarized string is called a bin stfing, in which 0 in each position Or 1 is called a bin;

3. Definition and quantification of context:

A non-negative integer variable Lmax is used to record the maximum level amplitude of each (level, run) number pair to be coded that has been coded in the previous coefficient block. Lmax is initialized to 0 before coding each coefficient block. As shown in Table 2, Lmax is quantized into 5 levels to select the Primary context number.

Lmax 0 1 2 [3, 4] [5, +∞) Primary Context 0 1 2 3 4

Table 2: Quantification of Primary Context

Lmax has the effect of recording the encoding history of the coefficient block and classifying the current (level, run) number pairs according to different statistical characteristics. When encoding the specific binarization results of the current level and run, different bins will further select the Secondary context number according to Table 3.

model number Context model encoding content 0 Encode the first bin of absLevel (e.g., EOB) with this context model 1 If there is a second bin for absLevel, encode that bin with the context model 2 If there is a third or more bins for absLevel, encode those bins with this context model 3 If absLevel=1, encode the first bin of the run with this context model. 4 If absLevel=1 and the run has a second bin or more, use the context model to encode these bins 5 If absLevel>1, use the context model to encode the first bin of the run 6 If absLevel>1, and there is a second bin in the run, the latter is more, use the context model to encode these bins

Table 3: Secondary context structure

When encoding each binary decision, select the corresponding context from a total of 35 contexts according to the primary context number (0 to 4) and the secondary context number (0 to 6), and use the probability estimation under the context to drive the arithmetic coder.

4. Context weighting method:

In order to further improve the coding efficiency of EOB information, ReverseP indicates the position of the level to be coded in the coefficient reverse scanning order. Lmax is initialized to 0 before coding each coefficient block. For 8×8 DCT coefficient blocks, ReverseP is limited to [0, 63], and uniformly quantized to 32 levels as the accompanying context sequence number.

When encoding the first bin of absLevel, select a context according to the Primary context number and the Secondary upper and lower numbers (value 0), and set the probability estimate under this context as p1; select another from 32 accompanying contexts according to ReverseP context, let the probability estimate under this context be p2. A binary arithmetic encoder is driven with a simple weighting of p1 and p2: (p1+p2)/2.

The following is the process of Embodiment 2, and the specific encoding process is:

Step 1. Scan the encoded DCT coefficient block to form a sequence of (level, run) pairs to obtain the number of non-zero coefficients. The variable icoef represents the number of non-zero coefficients. For each block containing non-zero DCT coefficients, zigzag is used to scan first, and (level, run) pairs are formed according to the scanning order from upper left to lower right, and the value of icoeff is 7. When encoding, the level and run of each number pair will be encoded in reverse order formed by the number pair sequence, and the last (0, 0) number pair represents the end information EOB of the data block encoding;

Fig. 3 is an example of zigzag scanning, and Fig. 4 is an encoding sequence of block coefficients in the present invention.

Step 2. Determine whether the value of the variable icoef is zero, if so, assign (0, 0) to the variable (level, run); if the value of the variable icoef is not zero, then search for the ( level, run) value; initialize the context variable Lmax=0, ReverseP=0. The (0,0) pair inserted when the value of icoeff is reduced to 0 represents the coefficient block end information EOB.

Step 3. Construct a context according to all (level, run) pairs that have been coded in this coefficient block, and use the context weighting technique to code the absolute value of the level. Obtain the binary representation of its absolute value absLevel according to the value of the current level. The binarization process of absLevel is detailed in Table 1: the coefficient amplitude represented by absLevel is binarized using Unary representation, that is: several "0"s as a prefix and a "1" as a suffix, and the number of 0s is equal to absLevel.

Encoding the context model of the first bin of absLevel: select the Primary context number according to the value of Lmax (Table 2), and the Secondary context number is 0; at the same time, select the accompanying context number according to the value of ReverseP; apply context weighting technology to encode the first bin.

The context model for encoding other bins of absLevel: select the Primary context number according to the value of Lmax, and then select the Secondary context number (see Table 3) for encoding according to the position of the bin after the binarization of the current absLevel.

Step 4. If the value of the variable icoef is zero, the encoding ends.

Step 5. If the value of the variable icoef is not zero, encode the sign bit of level according to the (level, run) value; the sign bit of level is encoded with equal probability, if it is a negative number, encode with a binary arithmetic coder "1", otherwise the binary arithmetic coder encodes "0".

Step 6: Construct a context according to all the coded pairs in this coefficient block and the value of the current level just coded in step 104, and code the run. The binarization process of run is shown in Table 1; the Primary context sequence number is selected according to the value of Lmax, and the Secondary context sequence number is selected by the magnitude of the level in the current coded (level, run) number pair and the bin position of the currently coded run (see Table 3) is encoded;

Step 7. Subtract 1 from the value of the variable icoef; execute step 2.

Table 4: An example of context model number selection

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention without limitation, although the present invention has been described in detail with reference to the preferred embodiments, those of ordinary skill in the art should understand that: the technology of the present invention can still be The schemes are modified or equivalently replaced without departing from the spirit and scope of the technical solutions of the present invention, and all of them shall be included in the scope of the technical solutions claimed in the present invention.

Claims (5)

1. A context-based adaptive entropy coding method, wherein the following steps are performed: Step 1. Scan the current DCT-transformed and quantized coefficient block to form a "level, run" pair sequence to obtain the number of non-zero coefficients; initialize the context model of the coefficient block; Step 2. If the value of the non-zero coefficient is zero, then obtain the EOB information; if the value of the non-zero coefficient is not zero, then search for the " level, run" pairs; Step 3. If the first coefficient is coded, construct the first context according to the empty sequence; otherwise, construct the first context according to all pairs of numbers that have been coded in the coefficient block, and use the context weighting method to calculate the current level The absolute value is entropy encoded; Step 4. If the number of non-zero coefficients is zero, then the encoding ends; otherwise, according to the absolute value of all the encoded numbers in the coefficient block and the encoded level in step 3, the level The sign bit is encoded; Step 5. Constructing a second context according to all pairs of numbers that have been encoded in the coefficient block and the absolute value and sign bit of the encoded current level in steps 3 and 4, and performing entropy encoding on run; Step 6. Subtract 1 from the value of the non-zero coefficient, and execute step 2. 2. The adaptive entropy coding method according to claim 1, characterized in that: said scanning in step 1 is carried out according to the reverse order of the coding "level, run" number pairs. 3. The adaptive entropy coding method according to claim 1 or 2, characterized in that: the construction of the first context in the step 3 includes: defining two random variables, the first random variable is used to record the coefficient block For the amplitude change information of levels in all pairs of numbers that have been coded, the second random variable is recorded at the position of the current level to be coded in the reverse scanning order; according to the two random variables, the first context is constructed by context weighting. 4. The adaptive entropy coding method according to claim 1 or 2, characterized in that: the construction of the second context in the step 5 includes: defining two random variables, the first random variable is used to record the coefficient block The amplitude change information of the levels in all pairs of numbers that have been encoded in , and the other records the absolute value of the encoded current level described in step 3, and encodes the run by constructing a context with these two variables. 5. A context-based adaptive entropy decoding method, wherein the following steps are performed: Step 1. Initialize the first and second context models; Step 2. Scan the Level amplitude in the first "level, run" pair in reverse order, and decode the first Level amplitude according to the first context model; Step 3. If the obtained Level amplitude is zero, then get the EOB information, and go to step 7; otherwise, go to step 4; Step 4, decode to obtain the sign bit of level; Step 5. Construct a second context based on all the pairs of numbers that have been decoded and the value of the current level just decoded in steps 2 and 3, and decode to obtain Run; Step 6. Construct the first context according to all the pairs of numbers that have been decoded, and use the context weighting method to decode to obtain the absolute value of level in the next "level, run" number pair; perform step 3; Step 7. Restore the coefficient block according to the sequence of "level, run" pairs obtained from the decoding.

Images