Context-based adaptive variable length coding for adaptive block transforms

Field of the Invention

0001The present invention is generally related to the field of video coding and compression and, more particularly, to a method and system for context-based adaptive variable length coding.

Background of the Invention

0002A typical video encoder partitions each frame of the original video sequence into contiguous rectangular regions called "blocks". These blocks are encoded in "intra mode" (I-mode), or in "inter mode" (P-mode). For P-mode, the encoder first searches for a block similar to the one being encoded in a previously transmitted "reference frame", denoted by <i>F_ref.</i> Searches are generally restricted to being no more than a certain spatial displacement from the block to be encoded. When the best match, or "prediction", has been identified, it is expressed in the form of a two-dimensional (2D) motion vector <i>(</i>Δ<i>x,</i> Δ<i>y)</i> where Δ<i>x</i> is the horizontal and Δ<i>y</i> is the vertical displacement. The motion vectors together with the reference frame are used to construct a predicted block <i>F_pred</i>: <maths id="math0001"><math display="block"><msub><mi mathvariant="italic">F</mi><mi mathvariant="italic">pred</mi></msub><mfenced><mi mathvariant="italic">x</mi><mi mathvariant="italic">y</mi></mfenced><mo mathvariant="italic">=</mo><msub><mi mathvariant="italic">F</mi><mi mathvariant="italic">ref</mi></msub><mo>⁢</mo><mfenced><mi mathvariant="italic">x</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">Δx</mi><mo mathvariant="italic">,</mo><mi mathvariant="italic">y</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">Δy</mi></mfenced></math><img file="EP1546995B1_D0001.tif" /></maths> The location of a pixel within the frame is denoted by (<i>x</i>, <i>y</i>).

0003For blocks encoded in I-mode, the predicted block is formed using spatial prediction from previously encoded neighboring blocks within the same frame. For both I-mode and P-mode, the prediction error, i.e. the difference between the block being encoded and the predicted block, is represented as a set of weighted basis functions of some discrete transform. Transforms are typically performed on an 8x8 or 4x4 block basis. The weights - transform coefficients - are subsequently quantized. Quantization introduces loss of information, thus quantized coefficients have lower precision than the original ones.

0004Quantized transform coefficients and motion vectors are examples of "syntax elements". These, plus some control information, form a complete coded representation of the video sequence. Prior to transmission from the encoder to the decoder, all syntax elements are entropy coded, thereby further reducing the number of bits needed for their representation. Entropy coding is a lossless operation aimed at minimizing the number of bits required to represent transmitted or stored symbols (in our case syntax elements) by utilizing properties of their distribution (some symbols occur more frequently than others).

0005One method of entropy coding employed by video coders is Variable Length Codes (VLC). A VLC codeword, which is a sequence of bits (0's and 1's), is assigned to each symbol. The VLC is constructed so that the codeword lengths correspond to how frequently the symbol represented by the codeword occurs, e.g. more frequently occurring symbols are represented by shorter VLC codewords. Moreover, the VLC must be constructed so that the codewords are uniquely decodable, i.e., if the decoder receives a valid sequence of bits of a finite length, there must be only one possible sequence of input symbols that, when encoded, would have produced the received sequence of bits.

0006To correctly decode the bitstream, both encoder and decoder have to use the same set of VLC codewords and the same assignment of symbols to them. As discussed earlier, to maximize the compression, the most frequently occurring symbols should be assigned the shortest VLC codewords. However, the frequency (probability) of different symbols is dependant upon the actual frame being encoded. In the case where a single set of VLC codewords, and a constant assignment of symbols to those codewords is used, it is likely that the probability distribution of symbols within a given frame will differ from the probabilities assumed by the VLC, even though the average symbol probability across the entire sequence may not. Consequently, using a single set of VLC codewords and a single assignment of symbols to those codewords reduces coding efficiency.

0007To rectify this problem different methods of adaptation are used. One approach, which offers reasonable computational complexity, and a good compression versus efficiency trade-off, and which is currently used in the state-of-the art video coders, is now described. For a set of symbols, a number of tables specifying VLC codewords (VLCs) are provided for the encoder and the decoder to use. The table selected to encode a particular symbol then depends on the information known both to the encoder and decoder, such as the type of the coded block (I- or P- type block), the component (luma or chroma) being coded, or the quantization parameter (QP) value. The performance depends on how well the parameters used to switch between the VLCs characterize the symbol statistics.

0008In the decoder, the block in the current frame is obtained by first constructing its prediction in the same manner as in the encoder, and by adding to the prediction the compressed prediction error. The compressed prediction error is found by weighting the transform basis functions using the quantized coefficients. The difference between the reconstructed frame and the original frame is called reconstruction error.

0009The compression ratio, i.e. the ratio of the number of bits used to represent original sequence and the compressed one, may be controlled by adjusting the value of the quantization parameter (QP) used when quantizing transform coefficients. The compression ratio also depends on the method of entropy coding employed.

0010Coefficients in a given block are ordered (scanned) using zigzag scanning, resulting in a one-dimensional ordered coefficient vector. An exemplary zigzag scan for a 4x4 block is shown in <figref idref="f0001">Figure 1</figref>.

0011Zigzag scanning presumes that, after applying 2 dimensional (2D) transform, the transform coefficients having most energy (i.e. higher value coefficients) correspond to low frequency transform functions and are located toward the top-left of the block as it is depicted in <figref idref="f0001">Figure 1</figref>. Thus, in a coefficient vector produced through zigzag scanning, the higher magnitude coefficients are most likely to appear toward the start of the vector. After quantization most of the low energy coefficients become equal to 0.

0012The vector of coefficients can be further processed so that each nonzero coefficient is represented by 2 values: a <i>run</i> (the number of consecutive zero coefficients proceeding a nonzero value in the vector), and a <i>level</i> (the coefficient's value).

0013CAVLC (Context-based Adaptive VLC) is the method of coding transform coefficients used in the JVT coder "Joint Final Committee Draft (JFCD) of Joint Video Specification (ITU-T Rec. H.264 |ISO/IEC 14496-10 AVC". In summary, encoding a single 4x4 block using CAVLC involves five steps: <ul id="ul0001" list-style="none" compact="compact"><li>1. Encoding the total number of nonzero coefficients in the block, combined with the number of "trailing ones".</li></ul>

0014The number of trailing ones is defined as the number of coefficients with a magnitude of one that are encountered before a coefficient with magnitude greater than one is encountered when the coefficient vector is read in reverse order (i.e. 15, 14, 13, 12, 11, ... in <figref idref="f0001">Figure 1</figref>). The VLC used to code this information is based upon a predicted number of nonzero coefficients, where the prediction is based on the number of nonzero coefficients in previously encoded neighboring blocks (upper and left blocks). <ul id="ul0002" list-style="none"><li>2. Encoding the sign of any trailing ones.</li><li>3. Encoding the <i>levels</i> (magnitudes) of nonzero coefficients other than the trailing ones.</li><li>4. Encoding the number of zero values in the coefficient vector before the last nonzero coefficient, i.e. the sum of all the "<i>runs</i>". The VLC used when coding this value depends upon the total number of nonzero coefficients in the block, since there is some relationship between these two values.</li><li>5. Encoding the <i>run</i> that occurs before each nonzero coefficient, starting from the last nonzero value in the coefficient vector.</li></ul>

0015The VLC used to encode a <i>run</i> value is selected based upon the sum of the <i>runs</i> from step (4), and the sum of the <i>runs</i> coded so far. For example, if a block has a "sum of <i>runs</i>" of 8, and the first <i>run</i> encoded is 6, then all remaining <i>runs</i> must be 0, 1, or 2. Because the possible <i>run</i> length becomes progressively shorter, more efficient VLC codes are selected to minimize the number of bits required to represent the <i>run</i>.

0016A typical block-based video encoder is shown in <figref idref="f0002">Figure 2</figref>. As shown in <figref idref="f0001">Figure 1</figref>, the video server <b>100</b> comprises a front-end unit <b>10</b>, which receives video signals <b>110</b> from a video source, and a video multiplex coder <b>40</b>. Each frame of uncompressed video provided from the video source to the input <b>110</b> is received and processed macroblock-by-macroblock in a raster-scan order. The front-end unit <b>10</b> comprises a coding control manager <b>12</b> to switch between the I-mode and P-mode and to perform timing coordination with the multiplex coder <b>40</b> via control signals <b>120</b>, a DCT (Discrete Cosine Transform) transformation module <b>16</b> and a quantizer <b>14</b> to provide quantized DCT coefficients. The quantized DCT coefficients <b>122</b> are conveyed to the multiplex coder <b>40</b>. The front-end unit <b>10</b> also comprises an inverse quantizer <b>18</b> and an inverse transformation unit <b>20</b> to perform an inverse block-based discrete cosine transform (IDCT), and a motion compensation prediction and estimation module <b>22</b> to reduce the temporal redundancy in video sequences and to provide a prediction error frame for error prediction and compensation purposes. The motion estimation module <b>22</b> also provides a motion vector <b>124</b> for each macroblock to the multiplex coder <b>40</b>. The multiplex coder <b>40</b> typically comprises a scanning module <b>42</b> to perform the zigzag scan for forming an order vector for each block of image data, an entropy coding module to designate non-zero quantized DCT coefficients with <i>run</i> and <i>level</i> parameters. The <i>run</i> and <i>level</i> values are further mapped to a sequence of bins, each of which is assigned to a so-called `context' by a context assignment module <b>46</b>. The contexts, along with the motion vector, is formatted into a bitstream <b>140</b>. A context-based encoder is known in the art. Furthermore, it is possible that the transformation module <b>16</b> is a FFT (Fast Fourier Transform) module or DFT (Discrete Fourier Transform) module, and that DCT can be an approximation of a DCT.

0017A typical decoder is shown in <figref idref="f0003">Figure 3</figref>. As shown, a client <b>200</b> comprises a video multiplex decoder <b>60</b>, which receives the encoded video bitstream <b>140</b> from the encoder <b>40.</b> The decoder <b>60</b> also decodes an I-mode frame on a macroblock-by-macroblock basis. Based on the VLC codewords contained in the bitstream <b>140</b>, <b>a</b> coefficient extractor module <b>62</b> in the decoder <b>60</b> recovers the <i>run</i> and <i>level</i> values, and then reconstructs an array of quantized DCT coefficients <b>162</b> for each block of the macroblock. The encoded motion vector information associated with the macroblock is extracted from the encoded video bitstream <b>140</b>. The extracted motion vector <b>166</b>, along with the reconstructed quantized DCT coefficients <b>162</b>, is provided to a back-end unit <b>80</b>. An inverse quantizer <b>84</b> inverse quantizes the quantized DCT coefficients <b>162</b> representing the prediction error information for each block of the macroblock provides the results to an inverse transformer <b>86</b>. With the control information provided by a coding control manager <b>82</b>, an array of reconstructed prediction error values for each block of the macroblock is yielded in order to produce video signals <b>180</b>.

0018Currently, video and still images are typically coded with help of a block-wise transformation to frequency domain. Such coding method is used in H.26L (or H.264-to-be) standard by the Joint Video Team (JVT). In such a method, the image is first subdivided into blocks of 4x4 pixels in size and the blocks are transformed into a 4x4 matrix of transform coefficients. The coefficients are then arranged by scanning them along a zigzag path, wherein the low-frequency coefficients are placed first in the scan in order to form an ordered sequence of transform coefficients - a one-dimensional vector. A 4x4 transform coefficient matrix of <figref idref="f0001">Figure 1</figref> will result in a one-dimension array or a sequence of 1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8, 12, 15, 16. This is advantageous because the following step is to code the quantized values of the DCT coefficients by <i>run</i>-length coding, whereby the more probable <i>runs</i> are represented by short codes (Huffman coding or arithmetic coding). Arranged in such a manner, many of the coefficients at the end of the scan usually end up being zero. Thus the coefficients are coded with high-efficiency. It is known that variable-length coding means that not all symbols have the same length (in bits). Huffman coding is an example of variable-length coding. Arithmetic is slightly different in that it involves a series of symbols. Thus, it is in general not possible to describe the length of ONE symbol as requiring X bits. Rather, a specific series of symbols will require Y bits. For this reason "entropy coding" is perhaps a more general term than "variable-length coding".

0019The above-described coding scheme is used for producing a block transform of 4x4 pixels. However, Context-based Adaptive VLC (CAVLC) may involve in partitioning the transform coefficients into blocks that are larger than 4x4. For example, the JVT coder contains a feature called "Adaptive Block Transforms" (ABT) which performs transforms on 4x8, 8x4, and 8x8 blocks. Thus, the coding scheme designed for 4x4 blocks can no longer be applied. A solution to the problem is to split the larger block into sub-blocks of size 4x4.

0020An existing solution has been proposed, wherein the ABT block of coefficients is divided into 4x4 blocks in the spatial domain. As an example, an 8x8 block is shown in <figref idref="f0001">Figure 4</figref> with one of the scan orders used for this block in the JVT coder. The same block partitioned into four 4x4 blocks is shown in <figref idref="f0004">Figures 5a to 5c</figref>. Subsequently each 4x4 block is zigzag scanned using 4x4 scan, yielding a plurality of vectors of length 16. These length 16 vectors are then passed to the standard 4x4 CAVLC algorithm. When 4x4 scan shown in <figref idref="f0001">Figure 1</figref> is used for the 4x4 blocks in <figref idref="f0004">Figures 5a to 5c</figref>, the resulting vectors are as given in <figref idref="f0005">Figure 6a to 6c</figref>.

0021This existing CAVLC algorithm makes certain assumptions about the content of a coefficient vector. When these assumptions are violated, the coding tables (i.e. the tables specifying which codeword is used to describe which symbol) used by CAVLC are "mismatched". This means that the length of codewords in the table no longer accurately reflects the probability of a symbol, and consequently CAVLC is less efficient.

0022As a result of this existing approach, each of the 4x4 blocks created after partitioning of the ABT block has coefficients corresponding to different frequencies in the ABT transform. For example, the 4x4 block of <figref idref="f0004">Figure 5a</figref> contains low frequency information (both horizontally and vertically) and therefore most of the high amplitude coefficients. Likewise, the 4x4 block of <figref idref="f0004">Figure 5d</figref> contains high frequency information and low amplitude coefficients. The CAVLC algorithm assumes that higher magnitudes generally occur toward the start of the vector, and critically, it assumes that longer <i>runs</i> of zeros will generally occur toward the end of a vector. The 4x4 block of <figref idref="f0004">Figure 5d</figref> is statistically unlikely to contain many values in the 4x4 block of <figref idref="f0004">Figure 5a</figref>, and the "outlying" values are likely to have long <i>runs</i> of zeros associated with them. Although the 4x4 block of <figref idref="f0004">Figure 5d</figref> may contain one or two nonzero coefficients, the locations of those coefficients are mismatched with what CAVLC expects, and consequently coding of that block requires a disproportionately large number of bits.

0023The CAVLC method also assumes that the neighboring blocks have similar number of nonzero coefficients. For the blocks, which have coefficients corresponding to different frequencies of transform functions the number of nonzero coefficients vary drastically. That can lead to the wrong choice of the VLC table used to code the number of the nonzero coefficient of a given block since this choice is based on the number of the nonzero coefficients of its neighbors.

0024Thus, the existing block partitioning scheme is not an optimal solution in terms of coding efficiency and quantization accuracy.

0025It is advantageous and desirable to provide a more efficient method and system for video and image coding, which can be applied to ABT blocks having a general size of (4<i>n</i>)x(4<i>m</i>) where <i>n</i> and <i>m</i> are positive integers equal to or greater than 1.

Summary of the Invention

0026It is a primary objective of the present invention to reduce the number of bits required to represent the quantized coefficients that result after application of a block transform larger than 4x4. More precisely, it is aimed at reducing the number of bits required to represent coefficients resulting from a 4x8, 8x4, or 8x8 transform. Moreover, in order to simplify design of the JVT encoder as well as to minimize the memory required by the code implementing JVT, it is desirable that the CAVLC method developed for 4x4 block is used to code 4x8, 8x4, or 8x8 blocks unchanged or with minimal modifications.

0027The objective can be achieved by partitioning a block larger than 4x4 by a plurality of sub-block of size 4x4 using the original vector in an interleaved fashion.

0028According to an aspect of the present invention there is provided a method of image coding, a computer program to be used an image coding, an image encodes, an image coding system and an image decodes according to claims.

Brief Description of the Drawings

0029<ul id="ul0003" list-style="none" compact="compact"><li><figref idref="f0001">Figure 1</figref> is an exemplary zigzag scan for a 4x4 block.</li><li><figref idref="f0002">Figure 2</figref> is a block diagram showing a typical video server, which employs block-based transform coding and motion-compensated prediction.</li><li><figref idref="f0003">Figure 3</figref> is a block diagram showing a typical video client corresponding to the encoder of <figref idref="f0002">Figure 2</figref>.</li><li><figref idref="f0001">Figure 4</figref> is an exemplary zigzag scan for an 8x8 block.</li><li><figref idref="f0004">Figure 5a</figref> is a 4x4 sub-block from the 8x8 block of <figref idref="f0001">Figure 4</figref>.</li><li><figref idref="f0004">Figure 5b</figref> is another 4x4 sub-block from the 8x8 block of <figref idref="f0001">Figure 4</figref>.</li><li><figref idref="f0004">Figure 5c</figref> is yet another 4x4 sub-block from the 8x8 block of <figref idref="f0001">Figure 4</figref>.</li><li><figref idref="f0004">Figure 5d</figref> is the fourth 4x4 sub-block from the 8x8 block of <figref idref="f0001">Figure 4</figref>.</li><li><figref idref="f0005">Figure 6a</figref> is a one-dimensional array representing a vector, according to the 4x4 block of <figref idref="f0004">Figure 5a</figref>, to be passed to the 4x4 CAVLC algorithm.</li><li><figref idref="f0005">Figure 6b</figref> is a one-dimensional array representing a vector, according to the 4x4 block of <figref idref="f0004">Figure 5b</figref>, to be passed to the 4x4 CAVLC algorithm.</li><li><figref idref="f0005">Figure 6c</figref> is a one-dimensional array of coefficients representing a vector, according to the 4x4 block of <figref idref="f0004">Figure 5c</figref>, to be passed to the 4x4 CAVLC algorithm.</li><li><figref idref="f0005">Figure 6d</figref> is a one-dimensional array representing a vector, according to the 4x4 block of <figref idref="f0004">Figure 5d</figref>, to be passed to the 4x4 CAVLC algorithm.</li><li><figref idref="f0006">Figure 7</figref> is a one-dimensional vector representing an ordered sequence of coefficients of a 8x8 block.</li><li><figref idref="f0006">Figure 8a</figref> is a one-dimensional array of coefficients representing the first segmented vector from the original vector, according to the present invention.</li><li><figref idref="f0006">Figure 8b</figref> is a one-dimensional array of coefficients representing the second segmented vector from the original vector, according to the present invention.</li><li><figref idref="f0006">Figure 8c</figref> is a one-dimensional array of coefficients representing the third segmented vector from the original vector, according to the present invention.</li><li><figref idref="f0006">Figure 8d</figref> is a one-dimensional array of coefficients representing the fourth segmented vector from the original vector, according to the present invention.</li><li><figref idref="f0007">Figure 9</figref> is a block diagram showing an exemplary video server, according to the present invention.</li><li><figref idref="f0008">Figure 10</figref> is a block diagram showing a video client, according to the present invention, which is corresponding to the video encoder of <figref idref="f0007">Figure 9</figref>.</li><li><figref idref="f0009">Figure 11a</figref> is a 4x4 block sub-sampled from an 8x8 block of transform coefficients.</li><li><figref idref="f0009">Figure 11b</figref> is another 4x4 block sub-sampled from an 8x8 block of transform coefficients.</li><li><figref idref="f0009">Figure 11c</figref> is yet another 4x4 block sub-sampled from an 8x8 block of transform coefficients.</li><li><figref idref="f0009">Figure 11d</figref> is the fourth 4x4 block sub-sampled from an 8x8 block of transform coefficients.</li></ul>

Best Mode to Carry Out the Invention

0030The block segmentation method, according to the present invention, partitions an ABT block (an 8x8 block, a 4x8 or 8x4 block) of transform coefficients into 4x4 blocks, which are encoded using the standard 4x4 CAVLC algorithm. The division of the coefficients among 4x4 blocks is based on the coefficients energy to ensure that the statistical distributions of coefficients in each 4x4 blocks is similar. The energy of the coefficient depends on the frequency of the transform function to which it corresponds and can be for example indicated by its position in the zigzag scan of the ABT block. As a result of such division, not all the coefficients selected to a given 4x4 block are adjacent to each other spatially in ABT block.

0031The method presented in this invention operates on blocks of coefficients produced using a 4x8, 8x4 or 8x8 transform, which have subsequently been scanned in a zigzag pattern (or any other pattern) to produce an ordered vector of coefficients.

0032As mentioned earlier, the goal of zigzag scanning is to pack nonzero coefficients toward the start of the coefficient vector. Effectively, the goal is to arrange the coefficients according to decreasing energy (variance). The actual scan used to accomplish this is of no consequence to this invention, provided the energy is generally decreasing.

0033After zigzag scanning to produce a length <i>N</i> ordered vector of coefficients (<i>N</i> being 64 for an 8x8 block, or 32 for a 4x8 or 8x4 block), the algorithm of the present invention segments this vector into <i>N</i>/16 smaller vectors, each of length 16. Each such vector is formed by taking every (<i>N</i>/16)^th coefficient from the length <i>N</i> coefficient vector in a sub-sampling process. For example, if the ordered vector contains coefficients labeled c0, c1, c2, ..., c63, then the first segmented vector of length 16 contains c0, c4, c8, c12, ..., c60. The second segmented vector of length 16 vector contains c1, c5, c9, c13, ..., c61, and so on for the third and fourth vectors. For example, if the ordered vector is represented by a one-dimensional array of 64 coefficients as shown in <figref idref="f0006">Figure 7</figref>, then the first, second, third and fourth segmented vectors of length 16 are shown, respectively, in <figref idref="f0006">Figures 8a - 8d</figref>.

0034After the sub-sampled vectors of length 16 are obtained in the described manner, they are encoded using the standard 4x4 CAVLC algorithm. As written in the CAVLC description, coding of nonzero coefficients relies on the number of nonzero coefficients of the upper and left neighboring 4x4 blocks (See <figref idref="f0006">Figures 8a to 8d</figref>). Therefore each of the vectors created by splitting ABT block is assigned the spatial locations of one of the 4x4 blocks created by dividing ABT block spatially. For example when the method of the present invention operates on 8x4 block the first vector is assigned upper 4x4 block and the second vector lower block.

0035In the method, according to the present invention, where every fourth coefficient is selected as shown in <figref idref="f0006">Figures 8a - 8d</figref>, one coefficient out of the first ("most significant") four coefficients numbered 0-4 is allocated to each 4x4 block. One coefficient out of the next group of four (numbered 4-7) is allocated to each 4x4 block. The same pattern repeats for remaining groups of four coefficients. This has the effect of "balancing" the amount of energy in each of the resulting 4x4 blocks. According to our experiments, this algorithm requires an average of 3-5% fewer bits to represent a given video sequence, when compared to the existing solution.

0036To facilitate the video coding using the vector segmentation method, according to the present invention, a video server <b>102</b> as shown in <figref idref="f0007">Figure 9</figref> and a video client <b>202</b> as shown in <figref idref="f0008">Figure 10</figref> can be used. The major difference between the encoder <b>242,</b> according to the present invention, and the typical encoder <b>40</b> (<figref idref="f0002">Figure 2</figref>) is that the multiplex encoder <b>242</b> comprises an interleaving segmentation unit <b>48</b> for segmenting an ABT block (a 4<i>nx</i>4<i>m</i> block, with <i>n</i>, <i>m</i> being positive integer equal to or greater than 1) into <i>nxm</i> blocks in an interleaved manner, as illustrated in <figref idref="f0006">Figures 8a - 8d</figref>. According to the present invention, after the scanning unit <b>42</b> produces an ordered vector of coefficients of length <i>N</i> (<i>N=</i>16<i>n</i>x<i>m</i>), a computer software in the interleaving segmentation unit <b>48</b> having an algorithm is used to segment this ordered vector into <i>n</i>x<i>m</i> smaller vectors, each of which has a length of 16. Each such vector is formed by taking every (<i>n</i>x<i>m</i>)^th coefficients from the ordered coefficient vector of length <i>N</i>. Thus, the bitstream <b>142</b> is indicative of the contexts of the <i>nxm</i> segmented vectors.

0037Likewise, in the decoder <b>262</b> of the client <b>202</b> has a vector assembling unit <b>66,</b> which has a computer program with an algorithm for regrouping the coefficients in <b>nxm</b> segmented vectors into an ordered vector of length <b>N.</b>

0038It should be noted that the algorithm as described in conjunction with <figref idref="f0006 f0007 f0008">Figures 8a to 10</figref> is a specific embodiment of a more general concept. It is possible to assign a number to each position in the length <i>N</i> vector representing its "distance" from the DC (or first) term in the vector. This value should reflect the relative importance of the coefficients in that position. For example, in <figref idref="f0001">Figure 1</figref>, the selection of whether to encode position 1 or 2 first is nearly arbitrary; therefore they might be assigned the same "distance" or "cost" value.

0039Ensuring that all blocks possess similar characteristics (i.e. are suited to the CAVLC coder) is then a minimization problem. For each possible allocation pattern, the total "cost" of coefficients in each 4x4 block can be calculated, and the variance across the 4x4 blocks taken. The allocation pattern that minimizes the variance will lead to blocks with the most similar statistical properties.

0040Mathematically, if <b>P</b> is the set of allocation patterns, then we want to calculate the value of <i>p</i> such that <maths id="math0002"><math display="block"><msup><mi>σ</mi><mn>2</mn></msup><mo>=</mo><munder><mi>min</mi><mi mathvariant="normal">P</mi></munder><mo>⁢</mo><msubsup><mi>σ</mi><mi>p</mi><mn>2</mn></msubsup></math><img file="EP1546995B1_D0002.tif" /></maths> where <maths id="math0003"><math display="inline"><msubsup><mi>σ</mi><mi>p</mi><mn>2</mn></msubsup><mo>=</mo><mi>var</mi><mfenced open="{" close="}"><mstyle displaystyle="true"><munderover><mo>∑</mo><mi>i</mi><mn>16</mn></munderover></mstyle><msub><mi>d</mi><mrow><mn>1</mn><mo>,</mo><mi>i</mi></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mi>i</mi><mn>16</mn></munderover></mstyle><msub><mi>d</mi><mrow><mi>N</mi><mo>/</mo><mn>16</mn><mo>,</mo><mi>i</mi></mrow></msub></mfenced></math><img file="EP1546995B1_D0003.tif" /></maths> and <i>d_i,j</i> is the "cost" of the <i>i</i>^th coefficient in the <i>j</i>^th segmented vector. As mentioned above, the allocation pattern described here is one example of an attempt to minimize the "cost variance" between segmented blocks. It should be understood that if the allocation patterns are selected adaptively, information on the allocation pattern that is used at the encoder needs to be transmitted to the decoder. Alternatively, the allocation pattern can be determined from other parameters used in the coding of the image. What is essential here is that both the encoder and the decoder use the same allocation pattern, since otherwise the coded image cannot be decoded properly.

0041It should be noted that the DC coefficient can be coded differently and separately. However, in order to ensure that the existing 4x4 CAVLC is unchanged, the DC coefficient is not treated any differently than the 3 lowest-frequency AC values. Treating the DC coefficient separately would mostly result in a benefit when there are very few coefficients in the block (for example, for an 8x8 block, three out of four 4x4 blocks are empty). In this case, it may be desirable to exclude the DC term from the prediction of number of non-zero values. However, the benefit may not be significant in general.

0042The distance/cost metric intrinsic to a coefficient's position in the scan can be used to determine which 4x4 block that coefficient is allocated to. For example, a cost pattern of (0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 ..." can be used for such determining. Alternatively, a cartesian distance such as "0111.42 ..." can be used. The effect of the allocation algorithm is to create blocks with an equal or approximately equal total cost. As such, the variance of the total cost for each block is taken to be a measure of the similarity. The block selected for the next coefficient in the scan is the block with the lowest accumulated cost of coefficients allocated to it so far.

0043It is also possible that, prior to zigzag scanning, a pre-determined sub-sample procedure is used to sub-sample the 8x8 block as shown in <figref idref="f0001">Figure 4</figref> into four "interleaved" sub-blocks as shown in <figref idref="f0009">Figures 11a - 11d</figref>. A zigzag scan is then applied to these sub-blocks in order to produce four ordered vectors of length 16. As such, the result is equivalent to that shown in <figref idref="f0006">Figures 8a to 8d</figref>. Accordingly, it is possible to provide an image coding method, which comprises the steps of: <ol id="ol0001" compact="compact"><li>1. forming at least a block of transform coefficients for the image data;</li><li>2. sub-sampling the transform coefficients in the block in a pre-determined manner for providing a plurality of sub-sampled blocks of transform coefficients;</li><li>3. scanning the sub-sampled blocks of transform coefficients for providing a plurality of sub-sampled sequences of transform coefficients, and</li><li>4. coding the sub-sampled sequences of transform coefficients using an entropy encoder.</li></ol>

0044The method of the present invention as described herein above divides coefficients corresponding to different frequencies of the ABT transform among 4x4 blocks more equally. Therefore the created 4x4 blocks have properties statistically similar to those expected by the CAVLC coder, which leads to increased coding efficiency.

0045Thus, although the invention has been described with respect to a preferred embodiment thereof, it will be understood by those skilled in the art that the foregoing and various other changes, omissions and deviations in the form and detail thereof may be made without departing from the scope of this invention.