Method and system for context-based adaptive binary arithmetic coding

FIELD OF THE INVENTION

0001The present invention relates to context-based adaptive binary arithmetic coding and decoding.

BACKGROUND OF THE INVENTION

Run-Level

Coding of DCT Transform Coefficients

0002Typically, a hybrid video coder represents each non-zero quantized coefficient in the one dimensional array by two values, referred to as <i>level</i> and <i>run. Level</i> is the value of the quantized coefficient and <i>run</i> is the number of consecutive zero-valued coefficients preceding the coefficient in question. The <i>run</i> and <i>level</i> values for a given coefficient are ordered such that the <i>level</i> value precedes the associated <i>run</i> value. A <i>level</i> value equal to zero is used to indicate that there are no more non-zero coefficient values in the block. This o<i>-level</i> value is referred to as an EOB (end-of-block) symbol.

0003The latest version of the H.26L recommendation, known as Test Model 8 (TML8) and described in "H.26L Test Model Long Term Number 8 (TML-8) drafto" (ITU-T Telecommunications Standardization Section, Study Group 16, Video Coding Experts Group), specifies two alternative entropy coding modes. One entropy coding method, specified for use in the so-called 'high complexity profile' of H.26L, is a technique known as Context-based Adaptive Binary Arithmetic Coding (CABAC). This is a form of binary arithmetic coding which continually adapts to the statistical properties of the information being coded and is known in the art to be one of the most efficient forms of entropy coding (see <nplcit id="ncit0001" npl-type="s"><text>H. Witten, R. M. Neal, and J. G. Cleary, "Arithmetic coding for data compression," Commun. ACM, vol. 30, pp. 520-540, June 1987</text></nplcit>).

0004More details are described in <patcit id="pcit0001" dnum="WO03027940A"><text>WO03/027940</text></patcit>.

0005The invention is defined by the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

0006<ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">Figure 1a</figref> is a table showing a way in which contexts are assigned to bins based on level values.</li><li><figref idref="f0002">Figure 1b</figref> is a table showing the way in which contexts are assigned to level values according to a first embodiment.</li><li><figref idref="f0003">Figure 2a</figref> is a table showing a way in which contexts are assigned to bins based on run values.</li><li><figref idref="f0004">Figure 2b</figref> is a table showing the way in which contexts are assigned to run values according to a second embodiment, which is an embodiment of the invention.</li><li><figref idref="f0005">Figure 3</figref> is a block diagram illustrating an encoder in a context-based arithmetic coding scheme, according to the present invention.</li><li><figref idref="f0006">Figure 4</figref> is a block diagram illustrating a decoder, according to the present invention.</li><li><figref idref="f0007">Figure 5</figref> is a flowchart illustrating a method of image coding, according to an embodiment.</li><li><figref idref="f0008">Figure 6</figref> is a flowchart illustrating a method of image coding, according to another embodiment.</li></ul>

BEST MODE TO CARRY OUT THE INVENTION

0007Embodiments will now be discussed in detail. This disclosure provides a number of related mechanisms by which an improvement in the coding efficiency (data compression) of a context-based arithmetic coder, can be attained. This improvement is achieved by using context models, which take into account the contexts to which other data symbols are assigned.

0008A first embodiment, described in detail in section 1.1 below, relates to a context-based binary arithmetic coder suitable for use in an image coding system such as that defined by ITU-T recommendation H.26L. In this embodiment, level values generated by <i>run-level</i> coding the quantized transform coefficients of a transform coded block of image pixels are assigned to contexts taking into account the level of another transform coefficient belonging to the same block.

0009A second embodiment, which is an embodiment of the invention, described in detail in section 1.2, also relates to a context-based binary arithmetic coder for an image coding system such as that defined by ITU-T recommendation H.26L. In the second embodiment, run values produced by <i>run-level</i> coding the quantized DCT transform coefficients of a transform coded block of image pixels are assigned to contexts taking into account the <i>level</i> value of the <i>run-level</i> pair to which the <i>run</i> value belongs.

0010A third embodiment is described in section 1.3 and also relates to a context-based arithmetic coder for an image coding system such as that defined by ITU-T recommendation H.26L. According to the third embodiment, the number of non-zero transform coefficients N_c for a transform coded image block is determined and assigned to a context taking into account the context assigned to the N_c value for at least one other transform coded image block.

0011A preferred embodiment of the invention combines the functionality of the three above-mentioned embodiments.

0012The high complexity profile of ITU-T recommendation H.26L TML8 employs a form of context-based arithmetic coding known as CABAC. In a video encoder implemented according to H.26L, the CABAC method is used to encode a variety of different types of information produced by the encoder, including the transform coefficients generated by transform coding blocks of image pixels (in INTRA-coding mode) or prediction error values (in INTER-coding mode). The two-dimensional array of transform coefficients produced by transform coding a block of image pixels is scanned according to a particular scanning mode to produce a one-dimensional array. Two such scanning modes are defined in H.26L. The first is known as 'single-scanning mode' while the other is referred to as 'double-scanning mode'. Whichever scanning mode is used, scanning of the transform coefficients converts the two-dimensional array of coefficient values into a one-dimensional array in which the coefficients are ordered in a predetermined manner. The ordered transform coefficient values in the one-dimensional array are converted to <i>run</i> and <i>level</i> values. The last entry in the ordered one-dimensional array is an end-of-block symbol, which according to H.26L TML8, takes the form of a <i>level</i> value equal to zero. This indicates that the last non-zero coefficient value in the ordered array has been converted into a <i>run-level</i> pair.

0013The <i>run</i> and <i>level</i> values are converted to binary numbers (binarized), by mapping them to a series of bins, each of which can be assigned the value 0 or 1. The binarized <i>run</i> and <i>level</i> values are then assigned to contexts, a separate set of contexts being defined for the <i>runs</i> and the <i>levels.</i> According to H.26L TML8, for a given block type, the set of contexts defined for <i>levels</i> depends only on the bin number to which the <i>levels</i> are assigned. More specifically, according to H.26L TML8 four contexts are defined for <i>level</i> encoding. The first one is for the first bin, the second is for the second bin, while the third context is for the rest of the bins representing the magnitude of the <i>level.</i> The remaining context is used for the sign of the <i>level.</i> For <i>runs</i> there are three contexts, the first one for the first bin, the second for the second bin and the third for all remaining bins. As <i>run</i> values are always equal to or greater than zero, there is no need for an additional context to represent sign information.

1.1. Context Model for

Levels

0014According to a first embodiment, when assigning a binarized <i>level</i> value to a context, in addition to considering the bin to which the <i>level</i> value itself is mapped, the <i>level</i> value of the preceding <i>run-level</i> pair is also taken into account. In this context, the term 'preceding <i>run-level</i> pair' means the <i>run-level</i> pair corresponding to the preceding coefficient in the ordered one-dimensional array of coefficient values. The following pseudo code presents an exemplary procedure for assigning a context to a <i>level</i> value of a <i>run-level</i> pair, taking into account both the bin to which the <i>level</i> itself is mapped and the <i>level</i> value of the preceding <i>run-level</i> pair: <img file="EP2007147B1_D0001.tif" />

0015In expression (2) <i>prev_level</i> is the magnitude of the <i>level</i> value of the previous <i>run-level</i> pair. <i>prev</i>_<i>level</i> is initialized to zero at the beginning of each block. In double scanning mode, <i>prev</i>_<i>level</i> is initialized at the beginning of each scan, twice per block. Parameter MAX_BIN_LEVEL provides a means of controlling the way in which the bin number to which the <i>level</i> value is mapped affects the assignment of a context. More specifically, and in a manner similar to the present assignment of contexts according to H. 26L TML8, MAX_BIN_LEVEL effectively defines a context to which all bin numbers greater than or equal to MAX_BIN_LEVEL are assigned. In a similar fashion parameter MAX_LEVEL provides a means of controlling the way in which the <i>level</i> value of the previous <i>run-level</i> pair affects the assignment of a context. <figref idref="f0001">Figures 1a</figref> and <figref idref="f0002">1b</figref> illustrate the way in which contexts are assigned to <i>level</i> values according to the first embodiment by applying the pseudo code of expression (2) with MAX_BIN_LEVEL = 3 and MAX_LEVEL = 5. In principle, any combination of MAX_BIN_LEVEL and MAX_LEVEL can be used to define a set of contexts appropriate for the statistical characteristics of the <i>level</i> values to be coded.

1.2. Context Model for

Runs

0016According to a second embodiment, which is an embodiment of the claimed invention, an approach similar to that described in section 1.1 is used to assign <i>run</i> values to contexts. More specifically, when assigning a binarized <i>run</i> value to a context, in addition to considering the bin to which the <i>run</i> value itself is mapped, the <i>level</i> of the <i>run-level</i> pair to which the <i>run</i> value belongs is also taken into account. The following pseudo code presents an exemplary procedure for assigning a context to a <i>run</i> value of a <i>run-level</i> pair, taking into account both the bin to which the <i>run</i> itself is mapped and the <i>level</i> value of the <i>run-level</i> pair to which the <i>run</i> value belongs: <img file="EP2007147B1_D0002.tif" />

0017In expression (3) <i>level</i> is the magnitude of the <i>level</i> value of the <i>run-level</i> pair. Parameter MAX_BIN_RUN provides a means of controlling the way in which the bin number to which the <i>run</i> value is mapped affects the assignment of a context. More specifically, and in a manner similar to the present assignment of contexts according to H. 26L TML8, MAX_BIN_RUN effectively defines a context to which all bin numbers greater than or equal to MAX_BIN_RUN are assigned. In a similar fashion parameter MAX_RUNL provides a means of controlling the way in which the <i>level</i> value of <i>run-level</i> pair affects the assignment of a context. <figref idref="f0003">Figures 2a</figref> and <figref idref="f0004">2b</figref> illustrate the way in which contexts are assigned to <i>level</i> values according to the second embodiment, which is an embodiment of the invention, by applying the pseudo code of expression (3) with MAX_BIN_RUN = 3 and MAX_RUNL = 4. In principle, any combination of MAX_BIN_RUN and MAX_RUNL can be used to define a set of contexts appropriate for the statistical characteristics of the <i>run</i> values to be coded.

1. 3 Contexts for Number of Non-Zero Coefficients

0018A third embodiment relates in particular to the way in which an ordered array of transform coefficient values is converted into <i>run</i> and <i>level</i> values and the way in which the number of <i>run-level</i> pairs corresponding to an array of quantized transform coefficient values is signaled. More specifically, after a block of image pixels or prediction error values has been transform coded to form a two-dimensional array of transform coefficient values and each of the coefficient values has been quantized, the number of non-zero quantized coefficient values in the array is determined. A value, referred to as N_c, is assigned to that number and is used to signal explicitly the number of non-zero coefficient values in the array. Thus, according to this embodiment, an EOB symbol, for example a <i>level</i> value equal to zero, is no longer required.

0019The quantized transform coefficients are further scanned according to a predetermined scanning order to produce an ordered one-dimensional array. Alternatively, N_c may be determined after ordering the quantized coefficient values. Each of the non-zero quantized coefficients in the ordered array is then converted into a <i>run-level</i> pair. According to this embodiment, the <i>level</i> value of the <i>run-level</i> pair denotes the magnitude of the value of the quantized coefficient minus 1 and the <i>run</i> value corresponds to the number of consecutive zero-valued quantized coefficients preceding the coefficient in question. The <i>level</i> values are assigned to the magnitude of the value of the quantized coefficient minus 1 because a <i>level</i> value equal to zero is no longer used as an end-of-block indicator. This gives rise to a saving in the amount of data (e. g. number of bits) required to represent the <i>level</i> information.

0020The <i>level</i> and <i>run</i> values are then encoded using entropy coding, as is the N_c value. In a situation where a context-based arithmetic coding method such as the CABAC technique implemented in H. 26L TML8 is used, the <i>run</i> and <i>level</i> values may be encoded according to the first and/or second embodiments of the invention, as described above. Alternatively any other appropriate context models may be used for the <i>run</i> and <i>level</i> values. Additionally a separate context model is defined for N_c. According to this embodiment, the N_c value representing the number of non-zero quantized transform coefficients in a given block is first binarized by mapping it to a series of bins, each of which has a corresponding bin number. The context for N_c is then determined on the basis of the bin number to which N_c is mapped and the N_c of at least one other image block or macroblock which has already been assigned an N_c value. The following pseudo code presents an exemplary procedure for assigning a context to an N_c value, taking into account both the bin to which the N_c itself is mapped and the preceding N_c value: <img file="EP2007147B1_D0003.tif" />

0021In expression (4) <i>prev_nc</i> is the previous N_c value. When encoded <i>level</i> and <i>run</i> values for a given block of quantized transform coefficents are transmitted from an encoder to a decoder, the entropy coded N_c value is transmitted before the encoded <i>run</i> and <i>level</i> values. At the decoder, the N_c value is decoded, followed by the <i>run-level</i> pairs corresponding to the quantized transform coefficient values for the block in question. The value of +1 is added to each of the magnitude of the <i>level</i> values as they are decoded in order to compensate for the corresponding subtraction made at the encoder.

0022To demonstrate the improvement in coding efficiency using the method of image coding, according to the present invention, the average bitrate difference is calculated using results for QP=28, 24, 20, 16. Table 2 shows the bitrate reduction in percentage, as compared to TML8, where MAX_LEVEL=5 and MAX_RUN=4. All frames are encoded as I-frames in CABAC mode. As shown in Table 2, the reduction in bitrate ranges from 0.95 to 4.74%. The improvement is more pronounced when the QP values are small. <tables id="tabl0001" num="0001"><table frame="all"><title><b>Table 2</b></title><tgroup cols="8"><colspec colnum="1" colname="col1" colwidth="34mm" /><colspec colnum="2" colname="col2" colwidth="20mm" /><colspec colnum="3" colname="col3" colwidth="18mm" /><colspec colnum="4" colname="col4" colwidth="14mm" /><colspec colnum="5" colname="col5" colwidth="14mm" /><colspec colnum="6" colname="col6" colwidth="18mm" /><colspec colnum="7" colname="col7" colwidth="15mm" /><colspec colnum="8" colname="col8" colwidth="13mm" /><thead><row><entry valign="top">QP</entry><entry valign="top">Container</entry><entry valign="top">Foreman</entry><entry valign="top">News</entry><entry valign="top">Silent</entry><entry valign="top">Tempete</entry><entry valign="top">Mobile</entry><entry valign="top">Paris</entry></row></thead><tbody><row><entry>5</entry><entry>3.19</entry><entry>3.92</entry><entry>3.11</entry><entry>4.74</entry><entry>4.01</entry><entry>3.63</entry><entry>3.34</entry></row><row><entry>10</entry><entry>3.10</entry><entry>3.39</entry><entry>2.85</entry><entry>4.32</entry><entry>3.88</entry><entry>3.73</entry><entry>3.04</entry></row><row><entry>16</entry><entry>2.64</entry><entry>2.67</entry><entry>2.26</entry><entry>3.17</entry><entry>3.37</entry><entry>3.37</entry><entry>2.55</entry></row><row><entry>20</entry><entry>2.20</entry><entry>2.14</entry><entry>1.76</entry><entry>2.38</entry><entry>2.79</entry><entry>2.90</entry><entry>2.20</entry></row><row><entry>24</entry><entry>1.30</entry><entry>1.51</entry><entry>1.35</entry><entry>2.28</entry><entry>1.89</entry><entry>2.01</entry><entry>1.54</entry></row><row><entry>28</entry><entry>1.16</entry><entry>0.95</entry><entry>0.99</entry><entry>1.76</entry><entry>1.55</entry><entry>1.57</entry><entry>1.18</entry></row><row><entry>Ave.Bitrate Diff.* (%)</entry><entry>1.79</entry><entry>1.83</entry><entry>1.58</entry><entry>2.37</entry><entry>2.49</entry><entry>2.40</entry><entry>1.87</entry></row></tbody></tgroup></table></tables>

0023In Table 2, the names appearing on the first row of the table are pictures used in <nplcit id="ncit0002" npl-type="b"><text>Gisle Bjontegaard "Recommended Simulation Conditions for H. 26L" (VCG-M75, ITU-T Video Coding Experts Group, Austin, Texas, USA, 2-4 April, 2001</text></nplcit>).

0024Referring now to <figref idref="f0005">Figure 3</figref>, an encoder 10 in the transmit side, according to the present invention, includes a unit 16 for storing previous <i>levels</i> and <i>runs.</i> As shown in <figref idref="f0005">Figure 3</figref>, the <i>run-level</i> pairs 102 for a given block are provided to a mapping unit 12, which maps the pairs to a sequence of bins, each bin having a value of 0 or 1. The location of the bin in the sequence representing a <i>run-level</i> pair is called a bin number. The bin numbers are represented by signals 104. Based on the signals 104 and a previously encoded <i>level</i> value 108 provided by unit 16, an assignment unit 14 assigns a context to a bin number. The contexts, denoted by signals 106, are provided to an adaptive arithmetic coder 20. The probability of occurrence of 1 and the probability of occurrence of 0 are estimated by a probability estimation module 22. Based on the probability estimates 120, an arithmetic encoding unit 24 encodes the bins. A feedback signal 124 is provided from the encoder 24 to the probability estimation module 22 to update the probability estimation. The encoded information is made into a bit-stream 122 to be conveyed to a decoder or stored in a storage device for later use.

0025Preferably, the encoder 10 also includes a unit 18, which is capable of providing the number, N_c, of non-zero coefficients in the block to the arithmetic encoder 20 before the <i>run-level</i> pairs are provided to the arithmetic encoder 20, so that N_c is also encoded and included into the bit-stream 122. N_c is represented by signals 110. By using N_c, there is no need to send an End-of-Block (EOB) symbol to the decoder. In prior art, the <i>level</i> value of 0 is used for the EOB symbol. More specifically, N_c is found after transform and quantization and it is encoded using entropy encoding. It should be noted that with the number of non-zero coefficients known, it is no longer necessary to use the 0<i>-levee</i> value to signal the end of the block. Thus, it is possible to modify the <i>level</i> value by subtracting 1 from the value of the quantized coefficient.

0026On the receive side, as shown in <figref idref="f0006">Figure 4</figref>, a decoder 50 is used to receive the bitstream 122 provided by the encoder 10. The received bit-stream, which represents arithmetic coded data symbols, is denoted by reference numeral 202. Initially, based on the previously decoded symbols, a context is calculated in a context assignment block 66 and the probability estimates of the bin values are updated in a probability estimation block 62. The previously decoded symbols based on which the probability estimates are updated are denoted by reference numeral 205. Context assignment, as carried out in the context assignment block 66, and calculation of probability estimates, as carried out in the probability estimation block 62, are similar to those in the encoder 10. The received bits 202 are then fed into an arithmetic decoding engine 64 in an arithmetic coder 60, where they are converted into decoded bin values 206, using the calculated context and the current probability estimates of the bin values 204. Decoded bins 208 are mapped to the values of the <i>runs</i> and <i>levels</i> in block 68. If the number, N_c, of non-zero coefficients in the block is encoded in the encoder 10 and provided in the received bit-stream 202, then a signal 214 is provided to the bin-to-value mapping module 68 whereby the quantized coefficient is restored by adding to the <i>level</i> value by 1.

0027<figref idref="f0007">Figure 5</figref> is a flowchart illustrating a method of image coding, according to the preferred embodiment of the present invention. As shown, the method 500 starts at step 510 where an image is received by an encoder. The received image is divided into a plurality of blocks at step 520. Each block is scanned at step 530 and the <i>levels</i> and <i>runs</i> of the quantized coefficients in the block are obtained at step 540. In contrast to prior art coding schemes, the present invention also uses the previous <i>levels</i> in the assignment of contexts at step 550. In particular, the assignment of contexts to the bins representing the <i>level</i> values of the quantized coefficients takes into account the value of the previously encoded <i>level,</i> as described in section 1.1. Likewise, the assignment of contexts to the bins representing the <i>run</i> values of the quantized coefficients takes into account the <i>level</i> value, as described in section 1.2. The assigned contexts are conveyed to an arithmetic coder for encoding at step 560. Additionally, N_c, or the number of non-zero quantized coefficients, is determined during or after the block is scanned at step 530 and N_c is encoded at step 560 prior to N_c and the contexts being provided to a decoder, as described in section 1.3.

0028Alternatively, the image coding method can be improved solely by conveying signals indicative of N_c, to the receive side, without considering the value of the previously encoded <i>level</i> or <i>run</i> when the contexts are assigned, as shown in <figref idref="f0007">Figure 5</figref>. As shown in <figref idref="f0008">Figure 6</figref>, instead of obtaining the previously encoded <i>levels</i> and <i>runs</i> at step 540 for assigning the contexts at step 550, N_c is obtained and provided at step 542. N_c is conveyed, before the contexts assigned at step 550 are sent, to an arithmetic coder for encoding at step 560. By sending N_c, there is no need to send the EOB symbol to the decoder.