Method and system for context-based adaptive binary arithmetic coding

FIELD OF THE INVENTION

0001The present invention relates generally to the compression of still images and video sequences and, more particularly, to a method and system for context-based adaptive binary arithmetic coding.

BACKGROUND OF THE INVENTION

0002A digital image in uncompressed form comprises an array of image pixels or picture elements. For example, in a commonly used digital image format, known as the Quarter Common Interchange Format (QCIF), an image, or frame, comprises 25,344 pixels arranged in an array of 176x144 pixels. Each pixel, in turn, is represented by a certain number of bits, which carry information about the brightness (luminance) and/or color (chrominance) of the pixel. Different schemes exist for representing the luminance and/or chrominance of pixels in a digital image. Commonly, a so-called YUV color model is used. The luminance, or Y, component represents the luminance of the pixel, while the color of the pixel is represented by two chrominance or color difference components, labelled U and V. Other color models, such as RGB (Red, Green, Blue) color models, which are based on components representing the three primary colors of light, are also commonly used. However, color models based on a luminance/chrominance representation provide advantages compared with color models based on primary colors. These stem from the nature of the human visual system, which is more sensitive to intensity variations than it is to color variations. YUV color models typically exploit this property by using a lower spatial resolution for the chrominance components (U, V) than for the luminance component (Y). In this way the amount of information needed to represent the color information in an image can be reduced without a noticeable reduction in perceived image quality.

0003The lower spatial resolution of the chrominance components is usually attained by sub-sampling. Typically, a block of 16x16 image pixels is represented by four blocks of 8x8 pixels comprising luminance information and the corresponding chrominance components are each represented by one block of 8x8 pixels representing an area of the image equivalent to that of the 16x16 pixels in the luminance component. The chrominance components are thus spatially sub-sampled by a factor of 2 in the <i>x</i> and <i>y</i> directions. The resulting assembly of four 8x8 pixel luminance blocks and two spatially corresponding 8x8 pixel chrominance blocks is commonly referred to as a YUV macroblock, or macroblock, for short. A QCIF image comprises 11x9 such macroblocks. If the luminance blocks and chrominance blocks are represented with 8 bit resolution (that is by numbers in the range 0 to 255), the total number of bits required to represent the luminance and chrominance information associated with each macroblock is 6x(8x8x8) = 3072 bits. Thus, the number of bits needed to represent an image in QCIF format is 99x3072 = 304,128 bits.

0004It should be appreciated that even in the situation described above, where both chrominance components of a digital color image are sub-sampled by a factor of two, an uncompressed image of only moderate size (e.g. 176x144 pixels) requires a large number of bits for its representation. This means that the amount of memory required to store digital images in uncompressed form is excessive. Furthermore, if still images are to be transferred, for example over a data communications network having a moderate or low available bandwidth, transmission times may become lengthy, or the network may become congested. Bandwidth requirements are even more severe if it is desired to transmit a series of images as a digital video sequence in real time. For example, transmission of a digital video sequence comprising a series of images in uncompressed QCIF format, represented using a YUV color model, at a rate of 30 frames per second, requires more than 9 Mbits/s (million bits per second). Such a high data rate is generally impractical for use in video recording, transmission and display applications because of the very large storage capacity, transmission channel capacity and hardware performance required. If a video sequence is to be transmitted in real-time over a fixed line network such as an ISDN (Integrated Services Digital Network) or a PSTN (Public Service Telephone Network), the available data transmission bandwidth is typically of the order of 64kbits/s. In mobile video-telephony, where transmission takes place at least in part over a radio communications link, the available bandwidth can be as low as 20kbits/s. This means that a significant reduction in the amount of information used to represent video data must be achieved in order to enable transmission of digital images or video sequences over low bandwidth communication networks. It is nevertheless desirable that this reduction should be achieved without significantly degrading the quality of the images/video sequence.

0005Over the past years, a considerable amount of research work has been directed towards reducing the amount of data required to represent digital images and video sequences, resulting in the development of numerous different schemes and international standards for compressing digital still images and digital video. The basic approach to image compression used in almost all still image and video encoders existing today involves block-based transform coding. Typically, transform coding translates image data from a representation comprising pixel values to a form comprising a set of coefficient values, each of which is a weighting factor (multiplier) for a basis function of the transform in question. It can be shown that there is a considerable degree of spatial redundancy within a typical digital image. In practical terms, this means that in general the value of any pixel within an image is substantially the same as the value of other pixels in its immediate vicinity; that is, there is a significant degree of correlation between pixel values. It is further known that when certain mathematical transformations, such as the two-dimensional Discrete Cosine Transform (DCT), are performed on image data, this spatial redundancy is reduced significantly, thereby producing a more compact representation of the image data.

Block-based Transform Coding as Used in JPEG Still Image Coding

0006In still image compression, such as that performed according to the baseline mode of the widely-used JPEG standard, an image to be coded is first divided into an array of non-overlapping square blocks, each block comprising, for example, an 8 x 8 array of image pixels. In the case of the JPEG baseline, a two-dimensional Discrete Cosine Transform (DCT) is then applied independently to each of the image blocks. This has the effect of converting the image data from the pixel value domain to the spatial frequency domain and to produce a corresponding set of coefficient values, each of which is a weighting factor for a basis function of the two-dimensional DCT. The coefficient values thus produced are quantized and then coded in a lossless manner using entropy coding to further reduce the amount of data (i.e. number of bits) required for their representation. According to the JPEG baseline, the entropy coder employs only Huffman coding to produce a compressed bit-stream, although in other modes arithmetic coding may alternatively be used. Finally, data describing image and coding parameters (e.g. type of compression, quantization and coding tables, image size, etc.) is embedded in the bit-stream produced by the entropy encoder. As the JPEG standard comprises four alternative coding modes and places few constraints on the quantization and coding tables that can be used, this is necessary in order to enable JPEG compressed bit-streams to be interchanged among different platforms and for images to be reconstructed without any ambiguity.

0007A digital video sequence, like an ordinary motion picture recorded on film, comprises a sequence of still images (often referred to as 'frames'), the illusion of motion being created by displaying the frames one after the other at a relatively fast rate, typically 15 to 30 frames per second. As in any still image, the pixel values of an individual frame within a digital video sequence exhibit considerable spatial redundancy. Therefore, the frames of a digital video sequence are amenable to block-based transform coding, just like individual still images.

0008Images in the consecutive frames of a video sequence also tend to be quite similar and thus the overall change between one video frame and the next is rather small. This means that there is considerable temporal redundancy within a typical digital video sequence. For example, a scene may comprise some stationary elements, such as background scenery, and some moving areas, for example the face of a newsreader. In consecutive frames of the sequence, it is likely that the background will remain unaltered and the only movement in the scene will be due to changes in facial expression of the newsreader. Thus, when forming a compressed representation of a video sequence there is also a possibility to use techniques which reduce the temporal redundancy of the image data of the sequence in addition to methods that reduce spatial redundancy, thereby allowing further data compression to be achieved.

Hybrid Video Encoder/Decoder

0009State of the art video coding systems make use of a technique known as 'motion-compensated prediction', to reduce the temporal redundancy in video sequences. Using motion-compensated prediction, the image content of some (often many) frames in a digital video sequence is 'predicted' from one or more other frames in the sequence, known as 'reference frames'. Prediction of image content is achieved by tracing the motion of objects or regions of an image between a frame to be coded (compressed) and the reference frame(s) using 'motion vectors'. In general, the reference frame(s) may precede the frame to be coded or may follow it in the video sequence. However, as will become apparent from discussions later in the text, it is not appropriate (or possible) to apply motion-compensated prediction to all frames of a video sequence and thus at least two types of encoding are used in state of the art video coding systems.

0010Frames of a video sequence which are compressed using motion-compensated prediction are generally referred to as INTER-coded or P-frames. Motion-compensated prediction alone rarely provides a sufficiently precise representation of the image content of a video frame and therefore it is typically necessary to provide a so-called 'prediction error' (PE) frame with each INTER-coded frame. As will be explained in greater detail later in the text, the prediction error frame represents the difference between a decoded version of the INTER-coded frame and the image content of the frame to be coded. More specifically, the prediction error frame comprises values that represent the difference between pixel values in the frame to be coded and corresponding reconstructed pixel values formed on the basis of a predicted (INTER-coded) version of the frame in question. Consequently, the prediction error frame has characteristics similar to a still image and block-based transform coding can be applied in order to reduce the amount of data (number of bits) required to represent it.

0011Frames of a video sequence which are not compressed using motion-compensated prediction are referred to as INTRA-coded or I-frames. Generally, INTRA-coded frames are produced by applying block-based transform coding directly to the pixel values of the frame to be coded. Additionally, where possible, blocks of INTRA-coded frames are predicted from previously coded blocks within the same frame. This technique, known as INTRA-prediction, has the effect of further reducing the amount of data required to represent an INTRA-coded frame.

0012In order to illustrate principles of block-based transform coding and motion-compensated prediction in greater detail, reference will now be made to <figref idref="f0001">Figure 1</figref>, which is a schematic of a generic hybrid video encoder that employs a combination of INTRA-and INTER-coding to produce a compressed (encoded) video bit-stream. A corresponding decoder is illustrated in <figref idref="f0002">Figure 2</figref> and will be described later in the text.

0013The video encoder <b>300</b> comprises an input <b>301</b> for receiving a digital video signal from a camera or other video source (not shown). It also comprises a transformation unit <b>304</b> which is arranged to perform a block-based discrete cosine transform (DCT), a quantizer <b>306,</b> an inverse quantizer <b>308,</b> an inverse transformation unit <b>310,</b> arranged to perform an inverse block-based discrete cosine transform (IDCT), combiners <b>312</b> and <b>316,</b> and a frame store <b>320.</b> The encoder further comprises a motion estimator <b>330,</b> a motion field coder <b>340</b> and a motion compensated predictor <b>350.</b> Switches <b>302</b> and <b>314</b> are operated co-operatively by control manager <b>360</b> to switch the encoder between an INTRA-mode of video encoding and an INTER-mode of video encoding. The encoder <b>300</b> also comprises a video multiplex coder <b>370</b> which forms a single bit-stream <b>335</b> from the various types of information produced by the encoder <b>300</b> for further transmission to a remote receiving terminal or, for example, for storage on a mass storage medium, such as a computer hard drive (not shown).

0014Encoder <b>300</b> operates as follows. Each frame of uncompressed video provided from the video source to input <b>301</b> is received and processed macroblock-by-macroblock, preferably in raster-scan order. When the encoding of a new video sequence starts, the first frame of the sequence is encoded as an INTRA-coded frame. Subsequently, the encoder is programmed to code each frame in INTER-coded format, unless one of the following conditions is met: 1) it is judged that the current frame being coded is so dissimilar from the reference frame used in its prediction that excessive prediction error information is produced; 2) a predefined INTRA frame repetition interval has expired; or 3) feedback is received from a receiving terminal indicating a request for a frame to be provided in INTRA-coded format.

0015The occurrence of condition 1) is detected by monitoring the output of the combiner <b>316.</b> The combiner <b>316</b> forms a difference between the current macroblock of the frame being coded and its prediction, produced in the motion compensated prediction block <b>350.</b> If a measure of this difference (for example a sum of absolute differences of pixel values) exceeds a predetermined threshold, the combiner <b>316</b> informs the control manager <b>360</b> via a control line <b>319</b> and the control manager <b>360</b> operates the switches <b>302</b> and <b>314</b> via control line <b>313</b> so as to switch the encoder <b>300</b> into INTRA-coding mode. Occurrence of condition 2) is monitored by means of a timer or frame counter implemented in the control manager <b>360,</b> in such a way that if the timer expires, or the frame counter reaches a predetermined number of frames, the control manager <b>360</b> operates the switches <b>302</b> and <b>314</b> via control line <b>313</b> to switch the encoder into INTRA-coding mode. Condition 3) is triggered if the control manager <b>360</b> receives a feedback signal from, for example, a receiving terminal, via control line <b>321</b> indicating that an INTRA frame refresh is required by the receiving terminal. Such a condition may arise, for example, if a previously transmitted frame is badly corrupted by interference during its transmission, rendering it impossible to decode at the receiver. In this situation, the receiving decoder issues a request for the next frame to be encoded in INTRA-coded format, thus re-initialising the coding sequence.

0016Operation of the encoder <b>300</b> in INTRA-coding mode will now be described. In INTRA-coding mode, the control manager <b>360</b> operates the switch <b>302</b> to accept video input from input line <b>318.</b> The video signal input is received macroblock by macroblock from input <b>301</b> via the input line <b>318.</b> As they are received, the blocks of luminance and chrominance values which make up the macroblock are passed to the DCT transformation block <b>304,</b> which performs a 2-dimensional discrete cosine transform on each block of values, producing a 2-dimensional array of DCT coefficients for each block. In a situation such as that described earlier, where each macroblock comprises four 8x8 pixel blocks of luminance values and two spatially corresponding 8x8 pixel blocks of chrominance values, DCT transformation block <b>304</b> produces an 8x8 array of coefficient values for each block.

0017The DCT coefficients for each block are passed to the quantizer <b>306,</b> where they are quantized using a quantization parameter QP. Selection of the quantization parameter QP is controlled by the control manager <b>360</b> via control line <b>315.</b> Quantization introduces a loss of information, as the quantized coefficients have a lower numerical precision than the coefficients originally generated by the DCT transformation block <b>304.</b> This provides a further mechanism by which the amount of data required to represent each image of the video sequence can be reduced. However, unlike the DCT transformation, which is essentially lossless, the loss of information introduced by quantization causes an irreversible degradation in image quality. The greater the degree of quantization applied to the DCT coefficients, the greater the loss of image quality.

0018The quantized DCT coefficients for each block are passed from the quantizer <b>306</b> to the video multiplex coder <b>370,</b> as indicated by line <b>325</b> in <figref idref="f0001">Figure 1</figref>. The video multiplex coder <b>370</b> orders the transform coefficients for each block using a zigzag scanning procedure. This operation converts the two-dimensional array of quantized transform coefficients into a one-dimensional array. Typical zigzag scanning orders, such as that shown in <figref idref="f0003">Figure 3</figref>, order the coefficients approximately in ascending order of spatial frequency. This also tends to order the coefficients according to their values, such that coefficients positioned earlier in the one-dimensional array are more likely to have larger absolute values than coefficients positioned later in the array. This is because lower spatial frequencies tend to have higher amplitudes within the image blocks. Consequently, the last values in the one-dimensional array of quantized transform coefficients are commonly zeros.

Run-Level Coding of DCT Transform Coefficients

0019Typically, the video multiplex coder <b>370</b> 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 0-<i>level</i> value is referred to as an EOB (end-of-block) symbol.

Entropy Coding

0020The <i>run</i> and <i>level</i> values are further compressed in the video multiplex coder <b>370</b> using entropy coding. Entropy coding is a lossless operation, which exploits the fact that symbols within a data set to be coded generally have different probabilities of occurrence. Therefore, instead of using a fixed number of bits to represent each symbol, a variable number of bits is assigned such that symbols which are more likely to occur are represented by code-words having fewer bits. For this reason, entropy coding is often referred to as Variable Length Coding (VLC). Since certain values of <i>levels</i> and <i>runs</i> are more likely than other values to occur, entropy coding techniques can be used effectively to reduce the number of bits required to represent the <i>run</i> and <i>level</i> values. A number of different methods can be used to implement entropy coding. For example, entropy coding of the <i>run</i> and <i>level</i> parameters may be implemented by means of look-up tables which define the mapping between each possible symbol in the data set to be coded and its corresponding variable length code. Such look-up tables are often defined by statistical analysis of training material comprising symbols identical to those to be coded and having similar statistical properties. An alternative technique, known as arithmetic coding, can also be used to convert the <i>run</i> and <i>level</i> values into variable length code-words. In arithmetic coding a group of symbols, for example the <i>run</i> and <i>level</i> values for a block of quantized transform coefficients, are coded as a floating point decimal number.

0021Once the <i>run</i> and <i>level</i> values have been entropy coded using an appropriate method, the video multiplex coder further combines them with control information, also entropy coded using a variable length coding method appropriate for the kind of information in question, to form a single compressed bit-stream of coded image information <b>335.</b>

0022A locally decoded version of the macroblock is also formed in the encoder <b>300.</b> This is done by passing the quantized transform coefficients for each block, output by quantizer <b>306,</b> through inverse quantizer <b>308</b> and applying an inverse DCT transform in inverse transformation block <b>310.</b> In this way a reconstructed array of pixel values is constructed for each block of the macroblock. The resulting decoded image data is input to combiner <b>312.</b> In INTRA-coding mode, switch <b>314</b> is set so that the input to the combiner <b>312</b> via switch <b>314</b> is zero. In this way, the operation performed by combiner <b>312</b> is equivalent to passing the decoded image data unaltered.

0023As subsequent macroblocks of the current frame are received and undergo the previously described encoding and decoding steps in blocks <b>304, 306, 308, 310</b> and <b>312,</b> a decoded version of the INTRA-coded frame is built up in frame store <b>320.</b> When the last macroblock of the current frame has been INTRA-coded and subsequently decoded, the frame store 320 contains a completely decoded frame, available for use as a prediction reference frame in coding a subsequently received video frame in INTER-coded format.

0024Operation of the encoder <b>300</b> in INTER-coding mode will now be described. In INTER-coding mode, the control manager <b>360</b> operates switch <b>302</b> to receive its input from line <b>317,</b> which comprises the output of combiner <b>316.</b> The combiner <b>316</b> receives the video input signal macroblock by macroblock from input <b>301.</b> As combiner <b>316</b> receives the blocks of luminance and chrominance values which make up the macroblock, it forms corresponding blocks of prediction error information. The prediction error information represents the difference between the block in question and its prediction, produced in the motion compensated prediction block <b>350.</b> More specifically, the prediction error information for each block of the macroblock comprises a two-dimensional array of values, each of which represents the difference between a pixel value in the block of luminance or chrominance information being coded and a decoded pixel value obtained by forming a motion-compensated prediction for the block, according to the procedure described below. Thus, in a situation where each macroblock comprises four 8x8 pixel blocks of luminance values and two spatially corresponding 8x8 pixel blocks of chrominance values, the prediction error information for the macroblock similarly comprises four 8x8 blocks of luminance prediction error values and two spatially corresponding 8x8 blocks of chrominance prediction error values.

0025The prediction error information for each block of the macroblock is passed to DCT transformation block <b>304,</b> which performs a two-dimensional discrete cosine transform on each block of prediction error values to produce a two-dimensional array of DCT transform coefficients for each block. Thus, in a situation where the prediction error information for each macroblock comprises four 8x8 blocks of luminance prediction error values and two spatially corresponding 8x8 blocks of chrominance prediction error values, DCT transformation block <b>304</b> produces an 8x8 array of transform coefficient values for each prediction error block. The transform coefficients for each prediction error block are passed to quantizer <b>306</b> where they are quantized using a quantization parameter QP, in a manner analogous to that described above in connection with operation of the encoder in INTRA-coding mode. Again, selection of the quantization parameter QP is controlled by the control manager <b>360</b> via control line <b>315.</b>

0026The quantized DCT coefficients representing the prediction error information for each block of the macroblock are passed from quantizer <b>306</b> to video multiplex coder <b>370,</b> as indicated by line <b>325</b> in <figref idref="f0001">Figure 1</figref>. As in INTRA-coding mode, the video multiplex coder <b>370</b> orders the transform coefficients for each prediction error block using the previously described zigzag scanning procedure (see <figref idref="f0003">Figure 3</figref>) and then represents each non-zero quantized coefficient as a <i>level</i> and a <i>run</i> value. It further compresses the <i>run</i> and <i>level</i> values using entropy coding, in a manner analogous to that described above in connection with INTRA-coding mode. Video multiplex coder <b>370</b> also receives motion vector information (described in the following) from motion field coding block <b>340</b> via line <b>326</b> and control information from control manager <b>360.</b> It entropy codes the motion vector information and forms a single bit-stream of coded image information <b>335</b> comprising the entropy coded motion vector, prediction error and control information.

0027The quantized DCT coefficients representing the prediction error information for each block of the macroblock are also passed from quantizer <b>306</b> to inverse quantizer 308. Here they are inverse quantized and the resulting blocks of inverse quantized DCT coefficients are applied to inverse DCT transform block <b>310,</b> where they undergo inverse DCT transformation to produce locally decoded blocks of prediction error values. The locally decoded blocks of prediction error values are then input to combiner <b>312.</b> In INTER-coding mode, switch <b>314</b> is set so that the combiner <b>312</b> also receives predicted pixel values for each block of the macroblock, generated by motion-compensated prediction block <b>350.</b> The combiner <b>312</b> combines each of the locally decoded blocks of prediction error values with a corresponding block of predicted pixel values to produce reconstructed image blocks and stores them in frame store <b>320.</b>

0028As subsequent macroblocks of the video signal are received from the video source and undergo the previously described encoding and decoding steps in blocks <b>304, 306, 308, 310, 312,</b> a decoded version of the INTER-coded frame is built up in frame store <b>320.</b> When the last macroblock of the frame has been INTER-coded and subsequently decoded, the frame store <b>320</b> contains a completely decoded frame, available for use as a prediction reference frame in encoding a subsequently received video frame in INTER-coded format.

0029Formation of a prediction for a macroblock of the current frame will now be described. Any frame encoded in INTER-coded format requires a reference frame for motion-compensated prediction. This means, necessarily, that when encoding a video sequence, the first frame to be encoded, whether it is the first frame in the sequence, or some other frame, must be encoded in INTRA-coded format. This, in turn, means that when the video encoder <b>300</b> is switched into INTER-coding mode by control manager <b>360,</b> a complete reference frame, formed by locally decoding a previously encoded frame, is already available in the frame store <b>320</b> of the encoder. In general, the reference frame is formed by locally decoding either an INTRA-coded frame or an INTER-coded frame.

0030The first step in forming a prediction for a macroblock of the current frame is performed by motion estimation block <b>330.</b> The motion estimation block <b>330</b> receives the blocks of luminance and chrominance values which make up the current macroblock of the frame to be coded via line <b>328.</b> It then performs a block matching operation in order to identify a region in the reference frame, which corresponds substantially with the current macroblock. In order to perform the block matching operation, motion field estimation block accesses reference frame data stored in frame store <b>320</b> via line <b>327.</b> More specifically, motion estimation block <b>330</b> performs block-matching by calculating difference values (e.g. sums of absolute differences) representing the difference in pixel values between the macroblock under examination and candidate best-matching regions of pixels from a reference frame stored in the frame store <b>320.</b> A difference value is produced for candidate regions at all possible offsets within a predefined search region of the reference frame and motion estimation block <b>330</b> determines the smallest calculated difference value. The offset between the macroblock in the current frame and the candidate block of pixel values in the reference frame that yields the smallest difference value defines the motion vector for the macroblock in question.

0031Once the motion estimation block <b>330</b> has produced a motion vector for the macroblock, it outputs the motion vector to the motion field coding block <b>340.</b> The motion field coding block <b>340</b> approximates the motion vector received from motion estimation block <b>330</b> using a motion model comprising a set of basis functions and motion coefficients. More specifically, the motion field coding block <b>340</b> represents the motion vector as a set of motion coefficient values which, when multiplied by the basis functions, form an approximation of the motion vector. Typically, a translational motion model having only two motion coefficients and basis functions is used.

0032The motion coefficients are passed from motion field coding block <b>340</b> to motion compensated prediction block <b>350.</b> Motion compensated prediction block <b>350</b> also receives the best-matching candidate region of pixel values identified by motion estimation block <b>330</b> from frame store <b>320.</b> Using the approximate representation of the motion vector generated by motion field coding block <b>340</b> and the pixel values of the best-matching candidate region of pixels from the reference frame, motion compensated prediction block <b>350</b> generates an array of predicted pixel values for each block of the macroblock. Each block of predicted pixel values is passed to combiner <b>316</b> where the predicted pixel values are subtracted from the actual (input) pixel values in the corresponding block of the current macroblock. In this way a set of prediction error blocks for the macroblock is obtained.

0033Operation of the video decoder <b>400,</b> shown in <figref idref="f0002">Figure 2</figref> will now be described. The decoder <b>400</b> comprises a video multiplex decoder <b>470,</b> which receives an encoded video bit-stream <b>335</b> from the encoder <b>300</b> and demultiplexes it into its constituent parts, an inverse quantizer <b>410,</b> an inverse DCT transformer <b>420,</b> a motion compensated prediction block <b>440,</b> a frame store <b>450,</b> a combiner <b>430,</b> a control manager <b>460,</b> and an output <b>480.</b>

0034The control manager <b>460</b> controls the operation of the decoder <b>400</b> in response to whether an INTRA- or an INTER-coded frame is being decoded. An INTRA / INTER trigger control signal, which causes the decoder to switch between decoding modes is derived, for example, from picture type information provided in a header portion of each compressed video frame received from the encoder. The INTRA / INTER trigger control signal is extracted from the encoded video bit-stream by the video multiplex decoder <b>470</b> and is passed to control manager <b>460</b> via control line <b>422.</b>

0035Decoding of an INTRA-coded frame is performed on a macroblock-by-macroblock basis, each macroblock being decoded substantially as soon as encoded information relating to it is identified in the received video bit-stream <b>335.</b> The video multiplex decoder <b>470</b> first separates the encoded information for the blocks of the macroblock from possible control information relating to the macroblock in question. The encoded information for each block of an INTRA-coded macroblock comprises variable length code-words. These code-words represent the entropy coded <i>level</i> and <i>run</i> values for the non-zero quantized DCT coefficients of the block. The video multiplex decoder <b>410</b> decodes the variable length code-words using a variable length decoding method corresponding to the encoding method used in the encoder <b>300</b> and thereby recovers the <i>level</i> and <i>run</i> values. It then reconstructs the array of quantized transform coefficient values for each block of the macroblock and passes them to inverse quantizer <b>410.</b> Any control information relating to the macroblock is also decoded in the video multiplex decoder using an appropriate variable length decoding method and is passed to control manager <b>460.</b> In particular, information relating to the level of quantization applied to the transform coefficients is extracted from the encoded bit-stream by video multiplex decoder <b>470</b> and is provided to control manager <b>460</b> via control line <b>424.</b> The control manager, in turn, conveys this information to inverse quantizer <b>420</b> via control line <b>415.</b> Inverse quantizer <b>410</b> inverse quantizes the quantized DCT coefficients for each block of the macroblock according to the control information and provides the now inverse quantized DCT coefficients inverse DCT transformer <b>420.</b>

0036Inverse DCT transformer <b>420</b> performs an inverse DCT transform on the inverse quantized DCT coefficients for each block of the macroblock to form a decoded block of image information comprising reconstructed pixel values. As motion-compensated prediction is not used in the encoding/decoding of INTRA-coded macroblocks, control manager <b>460</b> controls combiner <b>430</b> in such a way as to prevent any reference information being used in the decoding of the INTRA-coded macroblock. The reconstructed pixel values for each block of the macroblock are passed to the video output <b>480</b> of the decoder where, for example, they can be provided to a display device (not shown). The reconstructed pixel values for each block of the macroblock are also stored in frame store <b>450.</b> As subsequent macroblocks of the INTRA-coded frame are decoded and stored, a decoded frame is progressively assembled in the frame store <b>450</b> and thus becomes available for use as a reference frame for motion compensated prediction in connection with the decoding of subsequently received INTER-coded frames.

0037INTER-coded frames are also decoded macroblock by macroblock, each INTER-coded macroblock being decoded substantially as soon as encoded information relating to it is identified in the received bit-stream. The video multiplex decoder <b>470</b> separates the encoded prediction error information for each block of the INTER-coded macroblock from encoded motion vector information and possible control information relating to the macroblock in question. As explained in the foregoing, the encoded prediction error information for each block of the macroblock comprises variable length codewords which represent the entropy coded <i>level</i> and <i>run</i> values for the non-zero quantized transform coefficients for the prediction error block in question. The video multiplex decoder <b>470</b> decodes the variable length code-words using a variable length decoding method corresponding to the encoding method used in the encoder <b>300</b> and thereby recovers the <i>level</i> and <i>run</i> values. It then reconstructs an array of quantized transform coefficient values for each prediction error block and passes them to inverse quantizer <b>410.</b> Control information relating to the INTER-coded macroblock is also decoded in the video multiplex decoder using an appropriate variable length decoding method and is passed to control manager <b>460.</b> Information relating to the level of quantization applied to the transform coefficients of the prediction error blocks is extracted from the encoded bit-stream and provided to control manager <b>460</b> via control line <b>424.</b> The control manager, in turn, conveys this information to inverse quantizer <b>420</b> via control line <b>415.</b> Inverse quantizer <b>410</b> inverse quantizes the quantized DCT coefficients representing the prediction error information for each block of the macroblock according to the control information and provides the now inverse quantized DCT coefficients to inverse DCT transformer <b>420.</b> The inverse quantized DCT coefficients representing the prediction error information for each block are then inverse transformed in the inverse DCT transformer <b>420</b> to yield an array of reconstructed prediction error values for each block of the macroblock.

0038The encoded motion vector information associated with the macroblock is extracted from the encoded video bit-stream <b>335</b> by video multiplex decoder <b>470</b> and is decoded using an appropriate variable length decoding method. The decoded motion vector information thus obtained is passed via data line <b>426</b> to motion compensated prediction block <b>440,</b> which reconstructs a motion vector for the macroblock using the same motion model as that used to encode the INTER-coded macroblock in encoder <b>300.</b> The reconstructed motion vector approximates the motion vector originally determined by motion estimation block <b>330</b> of the encoder. The motion compensated prediction block <b>440</b> of the decoder uses the reconstructed motion vector to identify the location of a region of reconstructed pixels in a prediction reference frame stored in frame store <b>450.</b> The reference frame may be, for example, a previously decoded INTRA-coded frame, or a previously decoded INTER-coded frame. In either case, the region of pixels indicated by the reconstructed motion vector is used to form a prediction for the macroblock in question. More specifically, the motion compensated prediction block <b>440</b> forms an array of pixel values for each block of the macroblock by copying corresponding pixel values from the region of pixels identified in the reference frame. The prediction, that is the blocks of pixel values derived from the reference frame, are passed from motion compensated prediction block <b>440</b> to combiner <b>430</b> where they are combined with the decoded prediction error information. In practice, the pixel values of each predicted block are added to corresponding reconstructed prediction error values output by inverse DCT transformer <b>420.</b> In this way an array of reconstructed pixel values for each block of the macroblock is obtained. The reconstructed pixel values are passed to the video output <b>480</b> of the decoder and are also stored in frame store <b>450.</b> As subsequent macroblocks of the INTER-coded frame are decoded and stored, a decoded frame is progressively assembled in the frame store <b>450</b> and thus becomes available for use as a reference frame for motion-compensated prediction of other INTER-coded frames.

H.26L Video Coding Standard

0039ITU-T recommendation H.26L is the latest in a family of video coding standards developed by the International Telecommunications Union. It is intended in particular for video coding at very low bit rates, typically below 64kbits/s, which makes it especially suitable for the coding of digital video for transmission via radio communication networks or any fixed line communication network in which optimal use of available bandwidth is a priority. The video encoding system defined by ITU-T H.26L is a hybrid video coding system, which operates according to the general principles described above in connection with the generic video encoder <b>300</b> and decoder <b>400</b> illustrated in <figref idref="f0001">Figures 1</figref> and <figref idref="f0002">2</figref>. In particular, a video encoding system implemented according to H.26L employs a combination of block-based transform coding and motion-compensated prediction to reduce the spatial and temporal redundancy within video sequences.

0040The 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) draft0" (ITU-T Telecommunications Standardization Section, Study Group 16, Video Coding Experts Group), specifies two alternative entropy coding modes. In the first (default) mode a so-called Universal Variable Length Coding (UVLC) method is used to encode all syntax elements. The UVLC coding mode is a look-up table method in which the same set of variable length code-words is used to represent all the different kinds of information produced by the video encoder, regardless of the type of information in question. The alternative 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>).

0041Because UVLC entropy coding uses the same set of variable length code-words to represent all types of information produced by the video encoder, in general the statistical properties of the code-words do not match optimally with the characteristics of the information to be encoded. For example, the frequency of occurrence of particular <i>run</i> and <i>level</i> values used to represent the quantized DCT coefficients for an INTRA-coded image block is likely to be different from the occurrence of values in control information relating to quantization parameter values. The CABAC entropy coding method was introduced into the H.26L recommendation in order to overcome the inherently sub-optimal nature of the UVLC entropy coding method. As explained earlier in the text, arithmetic coding represents a group of symbols to be coded with a single variable length code (a floating-point number). This provides particular advantages compared with entropy coding methods, which encode each symbol independently. Specifically, entropy coding methods which encode each symbol independently require at least one bit to represent each symbol. Because arithmetic coding represents groups of symbols with a single code-word, it is possible to achieve data compression rates of less than one bit per symbol. Thus the CABAC method provided in H.26L also provides the possibility of improved data compression. Furthermore, because it is an adaptive method, it is also able to take into account changes in the statistical characteristics of the information being coded, ensuring that data compression performance is maintained even if the nature of the data being encoded changes to some extent.

Context-Based Arithmetic Coding

0042As explained above, CABAC arithmetic coding is an entropy coding method, which is able to adapt to changing statistics of the information to be encoded. In this way it is capable of providing improved compression efficiency compared with entropy coding techniques which assume fixed statistical properties. <figref idref="f0004">Figure 4</figref> illustrates an exemplary context-based binary arithmetic encoder <b>700.</b> CABAC is a binary arithmetic coding method and thus data symbols to be coded which have non-binary values are first converted to binary values ('binarized') in binary mapping block <b>710.</b> The binarization process involves mapping a symbol to be coded to a sequence of bins, each of which has a corresponding bin number and can be assigned a value of either 0 or 1. An example of such a mapping is given below in Table 1. In principle other binarization schemes can be envisaged. <tables id="tabl0001" num="0001"><table frame="all"><title><b>Table 1</b></title><tgroup cols="9"><colspec colnum="1" colname="col1" colwidth="15mm" /><colspec colnum="2" colname="col2" colwidth="10mm" /><colspec colnum="3" colname="col3" colwidth="10mm" /><colspec colnum="4" colname="col4" colwidth="10mm" /><colspec colnum="5" colname="col5" colwidth="10mm" /><colspec colnum="6" colname="col6" colwidth="10mm" /><colspec colnum="7" colname="col7" colwidth="10mm" /><colspec colnum="8" colname="col8" colwidth="10mm" /><colspec colnum="9" colname="col9" colwidth="10mm" /><thead><row><entry align="center" valign="top"><b>value</b></entry><entry namest="col2" nameend="col9" align="center" valign="top"><b>Bin Sequence</b></entry></row></thead><tbody><row><entry align="center">0</entry><entry align="center">1</entry><entry align="center" /><entry align="center" /><entry align="center" /><entry align="center" /><entry align="center" /><entry align="center" /><entry align="center" /></row><row><entry align="center">1</entry><entry align="center">0</entry><entry align="center">1</entry><entry align="center" /><entry align="center" /><entry align="center" /><entry align="center" /><entry align="center" /><entry align="center" /></row><row><entry align="center">2</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">1</entry><entry align="center" /><entry align="center" /><entry align="center" /><entry align="center" /><entry align="center" /></row><row><entry align="center">3</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">1</entry><entry align="center" /><entry align="center" /><entry align="center" /><entry align="center" /></row><row><entry align="center">4</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">1</entry><entry align="center" /><entry align="center" /><entry align="center" /></row><row><entry align="center">5</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">1</entry><entry align="center" /><entry align="center" /></row><row><entry align="center">6</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">1</entry><entry align="center" /></row><row><entry align="center">...</entry><entry align="center">.</entry><entry align="center">.</entry><entry align="center">.</entry><entry align="center">.</entry><entry align="center">.</entry><entry align="center">.</entry><entry align="center">.</entry><entry align="center">.</entry></row><row><entry align="center">bin_nr.</entry><entry align="center">1</entry><entry align="center">2</entry><entry align="center">3</entry><entry align="center">4</entry><entry align="center">5</entry><entry align="center">6</entry><entry align="center">7</entry><entry align="center">:</entry></row></tbody></tgroup></table></tables>

0043In the CABAC method each of the bins is assigned to a so-called 'context' (hence the name <i>context-based</i> arithmetic coding). A context can be thought of as grouping together bins, which have similar statistical characteristics. In other words, each bin assigned to a particular context is assumed to have a similar probability of containing the value 1 or 0 as the other bins belonging to that context. In this way, the probability estimates used to generate code-words in the arithmetic coder are defined for each context rather than for each possible bin to be encoded. Each context is defined according to a 'context model', established in advance and based on information about the statistical characteristics of the data symbols (and thus the bins) to be encoded. Generally, the data compression ratio achieved by a binary arithmetic encoder is enhanced if the difference between the probability of occurrence of a 0 and probability of occurrence of a 1 is maximised. In a similar way, the performance of a context-based arithmetic coding also depends on the choice of context model. This means that, in general, context models should be chosen so as to maximise the difference between the probability of occurrence of 0's and 1's for the bins assigned to each context.

0044In the exemplary context-based arithmetic coder illustrated in <figref idref="f0004">Figure 4</figref>, once a symbol to be coded has been binarized in binary mapping block <b>710</b> it is assigned to a corresponding context in context assignment block <b>720.</b> The value assigned to the corresponding bin (i.e., 1 or 0) is then passed to the arithmetic coder <b>730.</b> The coding engine <b>750</b> of arithmetic coder <b>730</b> then encodes the bin value using a probability estimate for the context to which the bin is assigned. The performance, that is the data compression ratio achieved by the arithmetic encoder, depends on the accuracy of the probability estimates. In principle, the estimates may be fixed or adaptive. If fixed probability estimates are used, the probability estimates for each context are assigned to predefined values and remain unchanged during the encoding process. Fixed probability estimates are typically obtained in advance by analysing training material having statistical properties similar to those of the actual data to be encoded. If adaptive probability estimates are used, fixed values are used to initialise the probability estimates for each context and the probabilities are then updated throughout the encoding process based on the actual statistical properties of the data (bins) encoded so far. Adaptive probability estimates generally perform better since they can adjust to the material being encoded.

0045The exemplary context-based arithmetic coder illustrated in <figref idref="f0004">Figure 4</figref> employs adaptive probability estimates and comprises a probability estimation block <b>740</b> where updated probability estimates are calculated. The probability estimates for each context are updated by keeping a record of the number of occurrences of 1 and 0 for each of the bins assigned to each context. For example, if the bins assigned to an arbitrary context <i>k</i> have been assigned the value <i>0 m</i> times and the value <i>1 n</i> times, then the probability estimate for <i>1</i> in context k is <i>n</i>/<i>(n(m</i>+<i>1))</i> and the probability estimate for <i>0</i> is <i>(m</i>+<i>1)</i>/<i>(n(m</i>+<i>1))</i>.

0046<figref idref="f0005">Figure 5</figref> illustrates a context-based arithmetic decoder <b>800</b> corresponding to the encoder described in connection with <figref idref="f0004">Figure 4</figref>. A bit-stream representing arithmetic coded data symbols is received by the context-based arithmetic decoder at input <b>810.</b> Initially, based on the previously decoded symbols, a context is calculated in a context assignment block <b>850</b> and the probability estimates of the bin values are updated. Context assignment, as carried out in the context assignment block <b>850,</b> and calculation of probability estimates, as carried out in the probability estimation block <b>830,</b> are done in the same manner as the encoder. The received bits are then fed into an arithmetic decoding engine <b>840</b> of the arithmetic decoder <b>820,</b> where they are converted to decoded bin values, using the calculated context and the current probability estimates of the bin values. Decoded bins are mapped to the values of the <i>runs</i> and <i>levels</i> in a bin-to-value mapping block <b>860.</b>

CABAC Method as Used in H.26L

0047The details of the CABAC arithmetic coding method adopted for use in the high complexity profile of ITU-T recommendation H.26L will now be described in detail. According to H.26L TML8, the contexts for <i>run</i> and <i>level</i> values depend on the type of block being encoded and the bin number of the binarized <i>level</i> or <i>run</i> value. Different block types are defined according to the scanning mode (single/double) used to order the coefficient values, the component type (luminance/chrominance, AC/DC), or the coding mode (INTER/INTRA). However, for a given block type, the context depends only on the bin number. 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> A similar approach is used to assign <i>run</i> values to contexts. 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. Thus, for a block of a given type, the assignment of bins to contexts for transform coefficient bins (for both <i>level</i> and <i>run</i> encoding) can be summarised as follows: <maths id="math0001" num="1"><math display="block"><mtable><mtr><mtd><mtable><mtr><mtd><mtable><mtr><mtd><mi mathvariant="italic">if</mi><mfenced separators=""><mi mathvariant="italic">bin_nr</mi><mo mathvariant="italic">></mo><mi mathvariant="italic">MAX_BIN_VAL</mi></mfenced></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mi mathvariant="italic">bin_nr</mi><mo mathvariant="italic">=</mo><mi mathvariant="italic">MAX_BIN_VAL</mi></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mtable><mtr><mtd><mi mathvariant="italic">end</mi></mtd></mtr><mtr><mtd><mi mathvariant="italic">context</mi><mo mathvariant="italic">=</mo><mi mathvariant="italic">bin_nr</mi></mtd></mtr></mtable></mtd></mtr></mtable></math><img file="EP2007147A2_D0001.tif" /></maths> where <i>bin_nr</i> is the bin number and <i>context</i> is the context number. According to H.26L TML8, the value of <i>MAX_BIN_VAL</i> is set equal to 3, but in principle another <i>MAX_BIN_VAL</i> could be used instead.

0048A <i>run-level</i> pair is encoded as follows: The <i>runs</i> and <i>levels</i> are first classified according to block / coefficient type: scanning mode, coefficient type (DC/AC), and coding mode (INTER/INTRA or 16x16 INTRA). The <i>levels</i> and <i>runs</i> are then binarized by mapping them onto a sequence of bins and each bin is assigned to a context based on its bin number.

0049<figref idref="f0006 f0007 f0008">Figures 6a-6d</figref> illustrate this process in detail with reference to an exemplary 4x4 array of quantized DCT coefficients. It also demonstrates the adaptive nature of the CABAC method, by illustrating the way in which the statistical properties of <i>run</i> and <i>level</i> values for quantized DCT coefficients are tracked. The two-dimensional array of quantized DCT coefficient values is first zigzag scanned to produce a one-dimensional array of values, as indicated in <figref idref="f0006">Figure 6a</figref>. The non-zero coefficient values in the one-dimensional array are then represented as pairs of <i>run</i> and <i>level</i> values. As previously explained, each <i>level</i> value represents the value of a non-zero quantized DCT coefficient, while the associated <i>run</i> value corresponds to the number of zero-valued coefficients preceding the coefficient in question. The <i>run- level</i> pairs derived from the exemplary array of quantized DCT coefficients are presented in <figref idref="f0006">Figure 6b</figref>. In each pair the <i>level</i> value precedes the associated <i>run</i> value and a <i>level</i> value equal to zero is used as an end-of-block symbol to indicate that there are no more non-zero coefficient values in the block.

0050Next, each <i>run</i> and <i>level</i> value is converted into a binary value. According to H.26L TML8, the binarization scheme used to convert the <i>run</i> and <i>level</i> values for quantized DCT transform coefficient values is identical to that shown above in Table 1. <figref idref="f0007">Figure 6c</figref> shows the result of applying the binarization scheme presented in Table 1 to the <i>run</i> and <i>level</i> values in the exemplary array. <figref idref="f0007">Figure 6c</figref> also shows the assignment of bins to contexts according to H.26L. As described above, only three contexts are used to describe the magnitudes of the <i>run</i> and <i>level</i> values. The first context corresponds to bin 1, the second to bin 2, while the third context comprises all the remaining bins. In <figref idref="f0007">Figure 6c</figref>, the contexts are delineated by bold horizontal lines. By examining <figref idref="f0007">Figure 6c</figref> it can be seen that the majority of <i>level</i> values are mapped to bins which are assigned to context 3, while the majority of <i>run</i> values are mapped to bins which are assigned to context 1.

0051The probability estimates for each assigned context are updated after the encoding of the bins. Probability estimates for the <i>run</i> and <i>level</i> contexts are updated independently. As previously described, the probability estimate for a given context represents the statistical characteristics of the bins assigned to the context in question. More specifically, the probability estimate describes the likelihood of a bin assigned to the context containing a 1 or a 0. <figref idref="f0008">Figure 6d</figref> describes, in an exemplary manner, the way in which the probability estimates are updated for <i>runs</i> and <i>levels.</i> The figure illustrates the probability of a bin assigned to a given <i>run</i> or <i>level</i> context containing a 1 or a 0 before and after the <i>runs</i> and <i>levels</i> representing the 4x4 block of quantized DCT coefficients shown in <figref idref="f0006">Figure 6a</figref> are binarized and assigned to contexts and encoded in the arithmetic encoder. <figref idref="f0008">Figure 6d</figref> takes the form of a table, which records the occurrence of 1's and 0's in the bins assigned to each context. Thus, the probability estimate for a given context is given by: <ul id="ul0001" list-style="none" compact="compact"><li>probability of 0 = no.of0's / (no. of 0's + no. of 1's)</li><li>probability of 1 = no.of1's / (no. of 0 1's no. of 1's)</li></ul> In the figure it is assumed that the 4x4 block of quantized DCT coefficients shown in <figref idref="f0006">Figure 6a</figref> is the first such block to be processed. This means that there are no previous occurrences of 1's and 0's to record in the table. To overcome this problem it is assumed that before the block is processed, each context has an equal probability of containing a 1 or a 0. This is indicated by entering identical values in the columns that record the occurrence of 0's and 1's. In <figref idref="f0008">Figure 6d</figref>, 1's are used to initialize the probability estimate. Alternatively, a probability estimate derived from analysis of training data could be used to intialize the probability estimates for each context. The probability estimates are then updated by counting the number of 1's and 0's which occur in the bins of each context as the <i>run</i> and <i>level</i> values for the block of quantized DCT transform coefficients are binarized and assigned to contexts. The right-hand column of <figref idref="f0008">Figure 6d</figref> shows the situation after processing the 4x4 block of quantized DCT shown in <figref idref="f0006">Figure 6a</figref>.

0052Although the CABAC arithmetic encoding method adopted in the high complexity profile of ITU-T recommendation H.26L TML8 provides an improvement in data compression compared with the UVLC entropy coding method, it is still not optimal with regard to coding efficiency. It is therefore an object of the invention to provide a method and system for context-based arithmetic coding, wherein coding efficiency is further improved.

SUMMARY OF THE INVENTION

0053The present invention is based on the realization that when coding a given data symbol using context-based arithmetic coding, an improvement in coding efficiency can be achieved by using context models which take into account the contexts to which other data symbols are assigned. With specific reference to the CABAC method used in the high complexity profile of H.26L TML8, the inventors of the present invention have determined that certain relationships exist between the <i>run</i> and <i>level</i> values associated with DCT transform coefficients. They have further determined that these relationships can be used to construct improved context models which enable the CABAC method to operate with improved coding efficiency when applied to the <i>run</i> and <i>level</i> values. In particular, the inventors have determined that consecutive <i>level</i> values exhibit a significant similarity. More specifically, within a given block of transform coefficients, the <i>level</i> of a coefficient to be encoded has, in general, a magnitude substantially similar to the <i>level</i> of the previously encoded coefficient. The inventors have also determined an inverse relationship between the <i>level</i> and <i>run</i> values. In particular, larger <i>level</i> values are more likely to be preceded by smaller <i>run</i> values. The converse is also true, namely smaller <i>level</i> values are likely to be preceded by larger <i>runs.</i> Consequently, the present invention proposes the creation of new context models for the coding of DCT transform coefficients, which take into account these relationships between <i>level</i> and <i>run</i> values.

0054In a first such context model, intended for implementation in a context-based arithmetic encoder, the context assigned to the bins of a binarized coefficient <i>level</i> value depends on the previously encoded coefficient <i>level.</i> In a second such context model, intended for implementation in a context-based arithmetic decoder, the context assigned to the bins of a binarized coefficient <i>level</i> value depends on the previously decoded coefficient <i>level.</i> In a third context model, implemented in either a context-based arithmetic encoder or a context-based arithmetic decoder, the context assigned to the bins of a binarized coefficient <i>run</i> value depends on the coefficient's <i>level</i> value.

0055The inventors have also determined that certain similarities exist between the transform coefficient values associated with different image blocks. These similarities are greater between image blocks which reside close to each other and tend to be strongest between immediately neighbouring image blocks. More specifically, the number N_c of non-zero transform coefficient values representing a particular image block tends to be similar to the number of non-zero transform coefficient values in an image block close to, or neighbouring, the image block in question. Thus, the present invention further introduces the concept of providing an indication of the number of non-zero transform coefficients for a transform coded image block and encoding this value using entropy coding. Furthermore, if context-based arithmetic coding is used to encode the N_c value, the inventors have determined that it is advantageous to assign the N_c value of a block to a context by taking into account the context assigned to the N_c value for at least one other transform coded image block. In this way the similarity between N_c values between image blocks which reside close to each other can be taken advantage of in the context-based arithmetic coding procedure. According to ITU-T recommendation H.26L TML8, the number of non-zero transform coefficients in an image block is not encoded. Instead, and as previously explained, an end-of-block (EOB) indication is provided. The EOB indication signals that the last <i>run-level</i> pair corresponding to a non-zero coefficient has been encoded. The inventors have determined that the proposed method, in which an explicit indication of the number of non-zero coefficients in a block is provided and coded using context-based arithmetic coding leads to an increase in the coding efficiency compared with the method of providing an EOB indication as currently employed in H.26L TML8.

0056Although the motivation behind the present invention and its basic concepts have been presented in the context of video encoding/decoding and more specifically with respect to H.26L TML8, it should be appreciated that invention may be applied in other video coding systems and also to still image coding. In principle the invention can be applied in any image coding system in which block-based transform coding and context-based arithmetic coding are used.

0057According to a first aspect of the present invention, there is provided a method of image coding in which an image is divided into a plurality of blocks having a plurality of pixels, each pixel having a pixel value, and a transform coding operation is performed on a block of pixel values to produce a corresponding block of transform coefficient values. The block of transform coefficient values is scanned in a given scanning order to produce a scanned array of coefficient values, and the coefficient values in the scanned array are represented by a plurality of number pairs, the number pairs having a first number and a second number. The first number and the second number are assigned to one of a plurality of contexts representative of the number pairs. According to the first aspect of the invention, the first value of a number pair is assigned to a context based on a first number of another number pair.

0058Preferably, the step of assigning the first number of a number pair to a context based on the first number of another number pair takes into account the context to which the first number of the other number pair is assigned.

0059Advantageously, the first number of a number pair is indicative of a non-zero coefficient value. Preferably, the first number of a number pair is equal to the magnitude of a non-zero coefficient value.

0060Advantageously, the second number of a number pair is indicative of a number of consecutive zero coefficient values preceding a non-zero coefficient value.

0061Preferably, the contexts are contexts of a context-based arithmetic coder.

0062More preferably, the contexts are contexts of a context-based binary arithmetic coder.

0063Advantageously, the first and second numbers are mapped to a set of bins, each of the bins having an associated bin number and each capable of taking one of either a first value or a second value.

0064Preferably, each of the first and second numbers is mapped to one of the set of bins, mapping of a number to a given one of the set of bins being indicated by assigning the value of the bin to the first value.

0065Preferably, the first value is 1 and the second value is 0.

0066Preferably, each of the set of bins is assigned to a context.

0067Advantageously, the step of assigning the first number of a number pair to a context based on the first number of another number pair, taking into account the context to which the first number in the other number pair is assigned, is implemented by examining the bin number of the bin to which the first number of the other number pair is mapped.

0068Advantageously, the method further comprises maintaining a probability estimate describing the statistical properties of each context.

0069Preferably, for each context, the probability estimate is indicative of the statistical likelihood of a number having a predetermined value being assigned to the context.

0070Preferably, for each context, the probability estimate is maintained by keeping a record of occurrences of the first value and the second value in the bins assigned to the context in question.

0071According to a second aspect of the present invention, there is provided a method of image coding in which an image is divided into a plurality of blocks having a plurality of pixels, each pixel having a pixel value, and a transform coding operation is performed on a block of pixel values to produce a corresponding block of transform coefficient values. The block of transform coefficient values is scanned in a given scanning order to produce a scanned array of coefficient values, and the coefficient values in the scanned array are represented by a plurality of number pairs, the number pairs having a first number and a second number. The first number and the second number are assigned to one of a plurality of contexts representative of the number pairs. According to the second aspect of the invention, the second number of a number pair is assigned to a context based on the first number of the number pair.

0072Preferably, the step of assigning the second number of a number pair to a context based on the first number of the number pair takes into account the context to which the second number of the number pair is assigned.

0073Advantageously, the first number of a number pair is indicative of a non-zero coefficient value. Preferably, the first number of a number pair is equal to the magnitude of a non-zero coefficient value.

0074Advantageously, the second number of a number pair is indicative of a number of consecutive zero coefficient values preceding a non-zero coefficient value.

0075Preferably, the contexts are contexts of a context-based arithmetic coder.

0076More preferably, the contexts are contexts of a context-based binary arithmetic coder.

0077Advantageously, the first and second numbers are mapped to a set of bins, each of the bins having an associated bin number and being capable of taking one of either a first value or a second value.

0078Preferably, each of the first and second numbers is mapped to one of the set of bins, mapping of a number to a given one of the set of bins being indicated by assigning the value of the bin to the first value.

0079Preferably the first value is 1 and the second value is 0.

0080Preferably each of the set of bins is assigned to a context.

0081Advantageously, the step of assigning the second number of a number pair to a context based on the first number of the number pair, taking into account the context to which the second number in the one of the number pairs is assigned, is implemented by examining the bin number of the bin to which the second number is mapped.

0082Advantageously, the method further comprises maintaining a probability estimate describing the statistical properties of each context.

0083Preferably, for each context, the probability estimate is indicative of the statistical likelihood of a number having a predetermined value being assigned to the context.

0084Preferably, for each context, the probability estimate is maintained by keeping a record of occurrences of the first value and the second value in the bins assigned to the context in question.

0085Preferably, the methods, according to the first and the second aspect of the invention, are both applied to a block of transform coefficient values.

0086According to a third aspect of the present invention there is provided an encoder comprising means for dividing an image into a plurality of blocks having a plurality of pixels, each pixel having a pixel value and means for performing a transform coding operation on a block of pixels to produce a corresponding block of transform coefficient values. The encoder further comprises means for scanning the block of transform coefficient values in a given scanning order to produce a scanned array of coefficient values, means for representing the coefficient values in the scanned array are represented by a plurality of number pairs, the number pairs having a first number and a second number, and means for assigning the first and the second numbers to one of a plurality of contexts representative of the number pairs. According to the third aspect of the invention, the encoder comprises means for assigning the first number of a number pair to a context based on a first number of another number pair.

0087According to a fourth aspect of the present invention, there is provided an encoder comprising means for dividing an image into a plurality of blocks having a plurality of pixels, each pixel having a pixel value, and means for performing a transform coding operation on a block of pixels to produce a corresponding block of transform coefficient values. The encoder further comprises means for scanning a block of transform coefficient values in a given scanning order to produce a scanned array of coefficient values means for representing the coefficient values in the scanned array by a plurality of number pairs, the number pairs having a first number and a second number, and means for assigning the first and the second numbers to one of a plurality of contexts representative of the number pairs. According to the fourth aspect of the invention, the encoder comprises means for assigning the second number of a number pair to a context based on the first number of the number pair.

0088According to a fifth aspect of the present invention, there is provided a method of image coding in which an image is divided into a plurality of blocks having a plurality of pixels, each pixel having a pixel value, and a transform coding operation is performed on a block of pixels to produce a corresponding block of transform coefficient values. According to the fifth aspect of the invention, the method comprises the step of providing a number indicative of a number of non-zero coefficient values in the block of transform coefficient values and assigning the number to a context representative of the number.

0089Advantageously, the step of assigning the number indicative of the number of non-zero transform coefficient values in the block of transform coefficient values to a context takes into account the context to which another such number indicative of the number of non-zero coefficient values in another block of transform coefficients is assigned.

0090Advantageously, the block of transform values is scanned in a given scanning order to produce a scanned array of coefficient values and the coefficient values in the scanned array are represented by a plurality of number pairs having a first number and a second number.

0091Advantageously, the first number of a number pair is indicative of a non-zero coefficient value.

0092Preferably, the first number of a number pair is equal to the magnitude of a non-zero coefficient value.

0093More preferably, the first number of a number pair is equal to the magnitude of a non-zero coefficient value minus 1.

0094Advantageously, the second number of a number pair is indicative of a number of consecutive zero coefficient values preceding a non-zero coefficient value.

0095Preferably, an end-of-block indication, indicative of the last non-zero coefficient value in the scanned array of coefficient values, is not provided.

0096Preferably, the methods according to the first, second and fifth aspects of the invention are each applied to a block of transform coefficient values.

0097According to a sixth aspect of the present invention there is provided an encoder comprising means for dividing an image into a plurality of blocks having a plurality of pixels, each pixel having a pixel value, and means for performing a transform coding operation on a block of pixels to produce a corresponding block of transform coefficient values. The encoder comprises means for providing a number indicative of the number of non-zero coefficient values in the block of transform coefficient values and means for assigning the number to a context representative of the number.

0098Advantageously, the encoder further comprises means for assigning the number indicative of the number of non-zero transform coefficient values in the block of transform coefficient values, taking into account the context to which another such number indicative of the number of non-zero transform coefficient values in another block of transform coefficient is assigned.

0099According to a seventh aspect of the present invention there is provided a computer program comprising a code for dividing an image into a plurality of blocks having a plurality of pixels, each pixel having a pixel value, and a code for performing a transform coding operation on a block of pixel values to produce a corresponding block of transform coefficient values. The computer program further comprises a code for scanning the block of transform coefficient values in a given scanning order to produce a scanned array of coefficient values, a code for representing the coefficient values in the scanned array by a plurality of number pairs, the number pairs having a first number and a second number, and a code for assigning the first and the second numbers to one of a plurality of contexts representative of the number pairs. According to the seventh aspect of the invention, the computer program also comprises a code for assigning the first number in one of the number pairs to a context based on a first number of another number pair.

0100Advantageously, the first number of a number pair is indicative of a non-zero coefficient value.

0101Preferably, the first number of a number pair is equal to the magnitude of a non-zero coefficient value.

0102Advantageously, the second number of a number pair is indicative of a number of consecutive zero coefficient values preceding a non-zero coefficient value.

0103According to an eighth aspect of the present invention, there is provided a computer program comprising a code for dividing an image into a plurality of blocks having a plurality of pixels, each pixel having a pixel value, and a code for performing a transform coding operation on a block of pixel values to produce a corresponding block of transform coefficient values. The computer program further comprises a code for scanning the block of transform coefficient values in a given scanning order to produce a scanned array of coefficient values, a code for representing the coefficient values in the scanned array by a plurality of number pairs, the number pairs having a first number and a second number, and a code for assigning the first and the second numbers to one of a plurality of contexts indicative of the number pairs. According to the eighth aspect of the invention, the computer program also comprises a code for assigning the second number of a number pair to a context based on the first number of the number pair.

0104Advantageously, the first number of a number pair is indicative of a non-zero coefficient value.

0105Preferably, the first number of a number pair is equal to the magnitude of a non-zero coefficient value.

0106Advantageously, the second number of a number pair is indicative of a number of consecutive zero coefficient values preceding a non-zero coefficient value.

0107According to a ninth aspect of the present invention there is provided a computer program comprising a code for dividing an image into a plurality of blocks having a plurality of pixels, each pixel having a pixel value, and a code for performing a transform coding operation on a block of pixels to produce a corresponding block of transform coefficient values. According to the ninth aspect of the invention, the computer program further comprises a code for providing a number indicative of the number of non-zero coefficient values in the block of transform coefficient values and a code for assigning the number to a context representative of the number.

0108Advantageously, the computer program further comprises a code for assigning the number indicative of the number of non-zero transform coefficient values in the block of transform coefficient values to a context, taking into account the context to which another such number indicative of the number of non-zero transform coefficient values in another block of transform coefficient is assigned.

0109According to a tenth aspect of the invention, there is provided a computer program according to the seventh, eighth and ninth aspects of the invention.

0110According to an eleventh aspect of the invention, there is provided a method of context-based arithmetic encoding in which an array of data symbols is represented with a code-word. The data symbols in said array are number pairs comprising a first number and a second number. The first number of a number pair is assigned to a context selected from a plurality of contexts representative of the first numbers, and the second number of a number pair is assigned to a context selected from a plurality of contexts representative of the second numbers. According to the eleventh aspect of the invention, the first number of a number pair is assigned to a context based on a first number of another of said number pairs.

0111According to a twelfth aspect of the invention, there is provided a method of context-based arithmetic decoding in which an array of data symbols is decoded from a code-word representative of the array. The data symbols in said array are number pairs comprising a first number and a second number. The first number of a number pair is assigned to a context selected from a plurality of contexts representative of the first numbers, and the second number of a number pair is assigned to a context selected from a plurality of contexts representative of the second numbers. According to the twelfth aspect of the invention, the first number of a number pair is assigned to a context based on a first number of another of said number pairs.

0112According to a thirteenth aspect of the invention, there is provided a method of context-based arithmetic encoding in which an array of data symbols is represented with a code-word. The data symbols in the array are number pairs comprising a first number and a second number. The first number of a number pair is assigned to a context selected from a plurality of contexts representative of the first numbers, and the second number of a number pair is assigned to a context selected from a plurality of contexts representative of the second numbers. According to the thirteenth aspect of the invention, the second number of a number pair is assigned to a context based on the first number of the number pair.

0113According to a fourteenth aspect of the invention, there is provided a method of context-based arithmetic decoding in which an array of data symbols is decoded from a code-word representative of the array. The data symbols in the array are number pairs comprising a first number and a second number. The first number of a number pair is assigned to a context selected from a plurality of contexts representative of the first numbers, and the second number of a number pair is assigned to a context selected from a plurality of contexts representative of the second numbers. According to the fourteenth aspect of the invention, the second number of a number pair is assigned to a context based on the first number of the number pair.

0114According to a fifteenth aspect of the invention, there is provided a method of context-based arithmetic encoding in which an array of data symbols is represented with a code-word, and a number indicative of a number of non-zero data symbols in the array is provided and assigned to a context representative of the number.

0115According to a sixteenth aspect of the invention, there is provided a context-based arithmetic encoder comprising means for representing an array of data symbols with a code-word. The data symbols in said array are number pairs comprising a first number and a second number, and the encoder further comprises means for assigning the first number of a number pair to a context selected from a plurality of contexts representative of the first numbers and means for assigning the second number of a number pair to a context selected from a plurality of contexts representative of the second numbers. According to the sixteenth aspect of the invention, the encoder comprises means for assigning the first number of a number pair to a context based on a first number of another of said number pairs.

0116According to a seventeenth aspect of the invention, there is provided a context-based arithmetic decoder comprising means for decoding an array of data symbols from a code-word representative of the array. The data symbols in the array are number pairs comprising a first number and a second number, and the decoder further comprises means for assigning the first number of a number pair to a context selected from a plurality of contexts representative of the first numbers and means for assigning the second number of a number pair to a context selected from a plurality of contexts representative of the second numbers. According to the seventeenth aspect of the invention, the decoder comprises means for assigning the first number of a number pair to a context based on a first number of another of said number pairs.

0117According to an eighteenth aspect of the invention, there is provided a context-based arithmetic encoder comprising means for representing an array of data symbols with a code-word. The data symbols in said array are number pairs comprising a first number and a second number, and the encoder further comprises means for assigning the first number of a number pair to a context selected from a plurality of contexts representative of the first numbers and means for assigning the second number of a number pair to a context selected from a plurality of contexts representative of the second numbers. According to the eighteenth aspect of the invention, the encoder comprises means for assigning the second number of a number pair to a context based on the first number of the number pair.

0118According to a nineteenth aspect of the invention, there is provided a context-based arithmetic decoder comprising means for decoding an array of data symbols from a code-word representative of the array. The data symbols in the array are number pairs comprising a first number and a second number, and the decoder further comprises means for assigning the first number of a number pair to a context selected from a plurality of contexts representative of the first numbers and means for assigning the second number of a number pair to a context selected from a plurality of contexts representative of the second numbers. According to the nineteenth aspect of the invention, the decoder comprises means for assigning the second number of a number pair to a context based on the first number of the number pair.

0119According to a twentieth aspect of the invention, there is provided a context-based arithmetic encoder comprising means for representing an array of data symbols with a code-word, further comprising means for providing a number indicative of a number of non-zero data symbols in the array and means for assigning said number to a context representative of the number.

0120The present invention will become apparent upon reading the description taken in conjunction with <figref idref="f0009 f0010 f0011 f0012 f0013 f0014 f0015 f0016">Figures 7a to 12</figref>.

BRIEF DESCRIPTION OF THE DRAWINGS

0121<ul id="ul0002" list-style="none" compact="compact"><li><figref idref="f0001">Figure 1</figref> is a block diagram illustrating the structure of an exemplary video encoder, which employs block-based transform coding and motion-compensated prediction.</li><li><figref idref="f0002">Figure 2</figref> is a block diagram of an exemplary video decoder corresponding to the encoder of <figref idref="f0001">Figure 1</figref>.</li><li><figref idref="f0003">Figure 3</figref> is a diagrammatic representation showing an exemplary zigzag scan.</li><li><figref idref="f0004">Figure 4</figref> is a block diagram showing an encoder in a prior art context-based arithmetic coding scheme.</li><li><figref idref="f0005">Figure 5</figref> is a block diagram showing a decoder in a prior art context-based arithmetic coding scheme.</li><li><figref idref="f0006">Figure 6a</figref> is a diagrammatic representation showing an exemplary two-dimensional array of quantized DCT coefficient values scanned in a zigzag manner.</li><li><figref idref="f0006">Figure 6b</figref> is a table showing the <i>level</i> and <i>run</i> values derived from the array of <figref idref="f0006">Figure 6a</figref>.</li><li><figref idref="f0007">Figure 6c</figref> is a table showing the binarized <i>level</i> and <i>run</i> values resulting from the application of the binarization scheme of Table 1 to the <i>level</i> and <i>run</i> values of <figref idref="f0006">Figure 6b</figref>.</li><li><figref idref="f0008">Figure 6d</figref> is a table showing a way in which the probability estimates are updated from <i>runs</i> and <i>levels.</i></li><li><figref idref="f0009">Figure 7a</figref> is a table showing a way in which contexts are assigned to bins based on <i>level</i> values.</li><li><figref idref="f0010">Figure 7b</figref> is a table showing the way in which contexts are assigned to <i>level</i> values according to a first embodiment of the present invention.</li><li><figref idref="f0011">Figure 8a</figref> is a table showing a way in which contexts are assigned to bins based on <i>run</i> values.</li><li><figref idref="f0012">Figure 8b</figref> is a table showing the way in which contexts are assigned to <i>run</i> values according to a second embodiment of the present invention.</li><li><figref idref="f0013">Figure 9</figref> is a block diagram illustrating an encoder in a context-based arithmetic coding scheme, according to the present invention.</li><li><figref idref="f0014">Figure 10</figref> is a block diagram illustrating a decoder, according to the present invention.</li><li><figref idref="f0015">Figure 11</figref> is a flowchart illustrating a method of image coding, according to a preferred embodiment of the present invention.</li><li><figref idref="f0016">Figure 12</figref> is a flowchart illustrating a method of image coding, according to another embodiment of the present invention.</li></ul>

BEST MODE TO CARRY OUT THE INVENTION

0122Embodiments of the invention will now be discussed in detail. As described above, the present invention 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.

0123A first embodiment of the invention, 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, <i>level</i> 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 <i>level</i> of another transform coefficient belonging to the same block.

0124A second 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, <i>run</i> 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.

0125A third embodiment of the invention 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.

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

0127As explained earlier in the text, the 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.

0128The <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 (see Table 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

0129According to a first embodiment of the present invention, 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: <maths id="math0002" num="2"><math display="block"><mstyle mathvariant="italic" displaystyle="true"><mtable><mtr><mtd><mtable><mtr><mtd><mtable><mtr><mtd><mi>if</mi><mfenced separators=""><mi>bin_nr</mi><mo>></mo><mi>MAX_BIN_LEVEL</mi></mfenced></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mi>bin_nr</mi><mo>=</mo><mi>MAX_BIN_LEVEL</mi><mo>;</mo></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mtable><mtr><mtd><mi>end</mi></mtd></mtr><mtr><mtd><mi>if</mi><mo>⁢</mo><mfenced separators=""><msub><mi>prev</mi><mo>-</mo></msub><mo>⁢</mo><mi>level</mi><mo>></mo><mi>MAX_LEVEL</mi></mfenced></mtd></mtr><mtr><mtd><msub><mi>prev</mi><mo>-</mo></msub><mo>⁢</mo><mi>level</mi><mo>=</mo><mi>MAX_LEVEL</mi><mo>;</mo></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mtable><mtr><mtd><mi>end</mi></mtd></mtr><mtr><mtd><mi>context</mi><mo>=</mo><mrow><mo>(</mo><mi>bin_nr</mi><mo>-</mo><mn>1</mn><mo>)</mo><mo>*</mo><mi>MAX_LEVEL</mi><mo>+</mo><msub><mi>prev</mi><mo>-</mo></msub><mo>⁢</mo><mi>level</mi></mrow></mtd></mtr></mtable></mtd></mtr></mtable></mstyle></math><img file="EP2007147A2_D0002.tif" /></maths> In expression (2) p<i>rev_level</i> is the magnitude of the <i>level</i> value of the previous <i>run-level</i> pair. <i>prev_level</i> is initialized to zero at the beginning of each block. In double scanning mode, <i>prev_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 an 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="f0009">Figures 7a</figref> and <figref idref="f0010">7b</figref> illustrate the way in which contexts are assigned to <i>level</i> values according to the first embodiment of the invention 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

0130According to a second embodiment of the invention an approach is 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: <maths id="math0003" num="3"><math display="block"><mstyle mathvariant="italic" displaystyle="true"><mtable><mtr><mtd><mtable><mtr><mtd><mtable><mtr><mtd><mi>if</mi><mfenced separators=""><mi>bin_nr</mi><mo>></mo><mi>MAX_BIN_RUN</mi></mfenced></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mi>bin_nr</mi><mo>=</mo><mi>MAX_BIN_RUN</mi><mo>;</mo></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mtable><mtr><mtd><mi>end</mi></mtd></mtr><mtr><mtd><mi>if</mi><mfenced separators=""><mi>level</mi><mo>></mo><mi>MAX_RUNL</mi></mfenced></mtd></mtr><mtr><mtd><mi>Level</mi><mo>=</mo><mi>MAX_RUNL</mi><mo>;</mo></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mtable><mtr><mtd><mi>end</mi></mtd></mtr><mtr><mtd><mi>context</mi><mo>=</mo><mrow><mo>(</mo><mi>bin_nr</mi><mo>-</mo><mn>1</mn><mo>)</mo><mo>*</mo><mi>MAX_RUNL</mi><mo>+</mo><mi>level</mi></mrow></mtd></mtr></mtable></mtd></mtr></mtable></mstyle></math><img file="EP2007147A2_D0003.tif" /></maths> In 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 an 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="f0011">Figures 8a</figref> and <figref idref="f0012">8b</figref> illustrates the way in which contexts are assigned to <i>level</i> values according to the second 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

0131A third embodiment of the invention 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 of the invention, an EOB symbol, for example a <i>level</i> value equal to zero, is no longer required.

0132The 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 of the invention, 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.

0133The <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 of the invention, 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: <maths id="math0004" num=""><math display="block"><mstyle mathvariant="italic" displaystyle="true"><mtable><mtr><mtd><mtable><mtr><mtd><mtable><mtr><mtd><mi>if</mi><mfenced separators=""><mi>bin_nr</mi><mo>></mo><mi>MAX_BIN_Nc</mi></mfenced></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mi>bin_nr</mi><mo>=</mo><mi>MAX_BIN_Nc</mi><mo>;</mo></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mtable><mtr><mtd><mi>end</mi></mtd></mtr><mtr><mtd><mi>if</mi><mo>⁢</mo><mfenced separators=""><msub><mi>prev</mi><mo>-</mo></msub><mo>⁢</mo><mi>nc</mi><mo>></mo><mi>MAX_Nc</mi></mfenced></mtd></mtr><mtr><mtd><mi>prev_nc</mi><mo>=</mo><mi>MAX_Nc</mi><mo>;</mo></mtd></mtr></mtable></mtd></mtr><mtr><mtd><mtable><mtr><mtd><mi>end</mi></mtd></mtr><mtr><mtd><mi>context</mi><mo>=</mo><mrow><mo>(</mo><mi>bin_nr</mi><mo>-</mo><mn>1</mn><mo>)</mo><mo>*</mo><mi>MAX_nc</mi><mo>+</mo><mi>prev_</mi></mrow><mi>nc</mi></mtd></mtr></mtable></mtd></mtr></mtable></mstyle></math><img file="EP2007147A2_D0004.tif" /></maths>

0134When 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.

0135To 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 1-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="tabl0002" num="0002"><table frame="all"><title><b>Table 2</b></title><tgroup cols="8"><colspec colnum="1" colname="col1" colwidth="33mm" /><colspec colnum="2" colname="col2" colwidth="19mm" /><colspec colnum="3" colname="col3" colwidth="18mm" /><colspec colnum="4" colname="col4" colwidth="13mm" /><colspec colnum="5" colname="col5" colwidth="13mm" /><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 align="char" char="." charoff="15">3.04</entry></row><row><entry>16</entry><entry align="char" char="." charoff="10">2.64</entry><entry align="char" char="." charoff="11">2.67</entry><entry align="char" char="." charoff="14">2.26</entry><entry align="char" char="." charoff="14">3.17</entry><entry align="char" char="." charoff="11">3.37</entry><entry align="char" char="." charoff="13">3.37</entry><entry align="char" char="." charoff="15">2.55</entry></row><row><entry>20</entry><entry align="char" char="." charoff="10">2.20</entry><entry align="char" char="." charoff="11">2.14</entry><entry align="char" char="." charoff="14">1.76</entry><entry align="char" char="." charoff="14">2.38</entry><entry align="char" char="." charoff="11">2.79</entry><entry align="char" char="." charoff="13">2.90</entry><entry align="char" char="." charoff="15">2.20</entry></row><row><entry>24</entry><entry align="char" char="." charoff="10">1.30</entry><entry align="char" char="." charoff="11">1.51</entry><entry align="char" char="." charoff="14">1.35</entry><entry align="char" char="." charoff="14">2.28</entry><entry align="char" char="." charoff="11">1.89</entry><entry align="char" char="." charoff="13">2.01</entry><entry align="char" char="." charoff="15">1.54</entry></row><row><entry>28</entry><entry align="char" char="." charoff="10">1.16</entry><entry align="char" char="." charoff="11">0.95</entry><entry align="char" char="." charoff="14">0.99</entry><entry align="char" char="." charoff="14">1.76</entry><entry align="char" char="." charoff="11">1.55</entry><entry align="char" char="." charoff="13">1.57</entry><entry align="char" char="." charoff="15">1.18</entry></row><row><entry>Ave.Bitrate Diff.* (%)</entry><entry align="char" char="." charoff="10">1.79</entry><entry align="char" char="." charoff="11">1.83</entry><entry align="char" char="." charoff="14">1.58</entry><entry align="char" char="." charoff="14">2.37</entry><entry align="char" char="." charoff="11">2.49</entry><entry align="char" char="." charoff="13">2.40</entry><entry align="char" char="." charoff="15">1.87</entry></row></tbody></tgroup></table></tables>

0136In Tables 2, the names appearing on the first row of the table are pictures used in <nplcit id="ncit0002" npl-type="s"><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>).

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

0138Preferably, the encoder <b>10</b> also includes a unit <b>18,</b> which is capable of providing the number, N_c, of non-zero coefficients in the block to the arithmetic encoder <b>20</b> before the <i>run-level</i> pairs are provided to the arithmetic encoder <b>20,</b> so that N_c is also encoded and included into the bit-stream <b>122.</b> N_c is represented by signals <b>110.</b> 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>level</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.

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

0140<figref idref="f0015">Figure 11</figref> is a flowchart illustrating a method of image coding, according to the preferred embodiment of the present invention. As shown, the method <b>500</b> starts at step <b>510</b> where an image is received by an encoder. The received image is divided into a plurality of blocks at step <b>520.</b> Each block is scanned at step <b>530</b> and the <i>levels</i> and <i>runs</i> of the quantized coefficients in the block are obtained at step <b>540.</b> In contrast to prior art coding schemes, the present invention also uses the previous <i>levels</i> in the assignment of contexts at step <b>550.</b> 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 <b>560.</b> Additionally, N_c, or the number of non-zero quantized coefficients, is determined during or after the block is scanned at step <b>530</b> and N_c is encoded at step <b>560</b> prior to N_c and the contexts being provided to a decoder, as described in section 1.3.

0141Alternatively, 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="f0015">Figure 11</figref>. As shown in <figref idref="f0016">Figure 12</figref>, instead of obtaining the previously encoded <i>levels</i> and <i>runs</i> at step <b>540</b> for assigning the contexts at step <b>550,</b> N_c is obtained and provided at step 542. N_c is conveyed, before the contexts assigned at step <b>550</b> are sent, to an arithmetic coder for encoding at step <b>560.</b> By sending N_c, there is no need to send the EOB symbol to the decoder.

0142Although 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.