Current video coders (MPEG, H264, etc.) use a block-wise representation of the video sequence. The images are segmented into macro-blocks, each macro-block is itself segmented into blocks and each block, or macro-block, is coded by intra-image or inter-image prediction. Thus, certain images are coded by spatial prediction (intra prediction), while other images are coded by temporal prediction (inter prediction) with respect to one or more coded-decoded reference images, with the aid of a motion compensation known by the person skilled in the art. Moreover, for each block can be coded a residual block corresponding to the original block minus a prediction. The coefficients of this block are quantized, possibly after a transformation, and then coded by an entropy coder.
Intra prediction and inter prediction require that certain blocks which have been previously coded and decoded be available, so as to be used, either at the decoder or at the coder, to predict the current block. A schematic example of a predictive coding such as this is represented in FIG. 1, in which an image IN is divided into blocks, a current block MBi of this image being subjected to a predictive coding with respect to a predetermined number of three previously coded and decoded blocks MBr1, MBr2 and MBr3, such as designated by the hatched arrows. The aforementioned three blocks specifically comprise the block MBr1 situated immediately to the left of the current block MBi, and the two blocks MBr2 and MBr3 situated respectively immediately above and above and to the right of the current block MBi.
The entropy coder is of more particular interest here. The entropy coder encodes the information in its order of arrival. Typically a row by row traversal of the blocks is carried out, of “raster-scan” type, as illustrated in FIG. 1 by the reference PRS, starting from the block at the top left of the image. For each block, the various items of information necessary for the representation of the block (type of block, mode of prediction, residual coefficients, etc.) are dispatched sequentially to the entropy coder.
An efficient arithmetic coder of reasonable complexity, called “CABAC” (“Context Adaptive Binary Arithmetic Coder”), introduced into the AVC compression standard (also known by the name ISO-MPEG4 part 10 and ITU-T H.264) is already known.
This entropy coder implements various concepts:                arithmetic coding: the coder, such as described initially in the document J. Rissanen and G. G. Langdon Jr, “Universal modeling and coding,” IEEE Trans. Inform. Theory, vol. IT-27, pp. 12-23, January 1981, uses, to code a symbol, a probability of occurrence of this symbol;        adaptation to context: here this entails adapting the probability of occurrence of the symbols to be coded. On the one hand, learning is carried out on the fly. On the other hand, depending on the state of the previously coded information, a specific context is used for the coding. To each context there corresponds an inherent probability of occurrence of the symbol. For example a context corresponds to a type of symbol coded (the representation of a coefficient of a residual, signaling of coding mode, etc.) according to a given configuration, or a state of the neighborhood (for example the number of “intra” modes selected in the neighborhood, etc.);        binarization: a shaping of a series of bits of the symbols to be coded is carried out. Subsequently, these various bits are dispatched successively to the binary entropy coder.        
Thus, this entropy coder implements, for each context used, a system for learning the probabilities on the fly with respect to the symbols coded previously for the context under consideration. This learning is based on the order of coding of these symbols. Typically, the image is traversed according to an order of “raster-scan” type, described hereinabove.
During the coding of a given symbol b that may equal 0 or 1, the learning of the probability pi of occurrence of this symbol is updated for a current block MBi in the following manner:
            p      i        ⁡          (              b        =        0            )        =            α      ·                        p                      i            -            1                          ⁡                  (                      b            =            0                    )                      +          {                                                  (                              1                -                α                            )                                                          if              ⁢                                                          ⁢              coded              ⁢                                                          ⁢              bit              ⁢                                                          ⁢              is              ⁢                                                          ⁢              0                                                            0                                otherwise                              
where α is a predetermined value, for example 0.95 and pi-1 is the symbol occurrence probability calculated upon the last occurrence of this symbol.
A schematic example of such an entropy coding is represented in FIG. 1, in which a current block MBi of the image IN is subjected to an entropy coding. When the entropy coding of the block MBi begins, the symbol occurrence probabilities used are those obtained after coding of a previously coded and decoded block, which is the one which immediately precedes the current block MBi in accordance with the aforementioned row by row traversal of the blocks of “raster scan” type. Such a learning based on block to block dependency is represented in FIG. 1 for certain blocks only for the sake of clarity of the figure, by the slender arrows.
A drawback of such a type of entropy coding resides in the fact that, when coding a symbol situated at the start of a row, the probabilities used correspond mainly to those observed for the symbols situated at the end of the previous row, having regard to the “raster scan” traversal of the blocks. Now, on account of the possible spatial variation of the symbol probabilities (for example for a symbol related to an item of motion information, the motion situated on the right part of an image may be different from that observed on the left part and therefore likewise for the ensuing local probabilities), a lack of local conformity of the probabilities may be observed, thereby possibly giving rise to a loss of efficiency during coding.
To limit this phenomenon, proposals for modifications of the order of traversal of the blocks have been made, with the aim of ensuring better local consistency, but the coding and the decoding remain sequential.
Therein lies another drawback of this type of entropy coder. Indeed, the coding and the decoding of a symbol being dependent on the state of the probability learned thereto, the decoding of the symbols can only be done in the same order as that used during coding. Typically, the decoding can then only be sequential, thus preventing parallel decoding of several symbols (for example to profit from multi-core architectures).
The document: Thomas Wiegand, Gary J. Sullivan, Gisle Bjontegaard, and Ajay Luthra, “Overview of the H.264/AVC Video Coding Standard”, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 13, No. 7, pp. 560-576, July 2003, point out moreover that the CABAC entropy coder has the particular feature of assigning a non-integer number of bits to each symbol of a current alphabet to be coded, this being advantageous for symbol occurrence probabilities of greater than 0.5. Specifically, the CABAC coder waits until it has read several symbols, and then assigns to this set of symbols read a predetermined number of bits that the coder writes to the compressed stream to be transmitted to the decoder. Such a provision thus makes it possible to “mutualize” the bits on several symbols and to code a symbol on a fractional number of bits, this number reflecting information which is closer to the information actually transported by a symbol. Other bits associated with the symbols read are not transmitted in the compressed stream but are kept on standby while waiting to be assigned to one or more new symbols read by the CABAC coder making it possible again to mutualize these other bits. In a known manner, the entropy coder undertakes, at a given instant, an “emptying” of these untransmitted bits. Stated otherwise, at said given instant, the coder extracts the bits not yet transmitted and writes them to the compressed stream destined for the decoder. Such emptying takes place for example at the instant at which the last symbol to be coded has been read, so as to ensure that the compressed stream does indeed contain all the bits which will allow the decoder to decode all the symbols of the alphabet. In a more general manner, the instant at which the emptying is performed is determined as a function of the performance and functionalities specific to a given coder/decoder.
The document, which is available at the Internet address http://research.microsoft.com/en-us/um/people/jinl/paper_2002/msri_jpeg.htm on the date of 15 Apr. 2011, describes a method for coding still images compliant with the JPEG2000 compression standard. According to this method, the still image data undergo a discrete wavelet transform followed by a quantization, thereby making it possible to obtain quantized wavelet coefficients with which are respectively associated quantization indices. The quantization indices obtained are coded with the aid of an entropy coder. The quantized coefficients are previously grouped into rectangular blocks called code-blocks, typically 64×64 or 32×32 in size. Each code-block is thereafter coded independently by entropy coding. Thus, the entropy coder, when it undertakes the coding of a current code-block, does not use the symbol occurrence probabilities calculated during the coding of previous code-blocks. The entropy coder is therefore in an initialized state at each start of coding of a code-block. Such a method exhibits the advantage of decoding the data of a code-block without having to decode the neighboring code-blocks. Thus for example, a piece of client software may request a piece of server software to provide the compressed code-blocks needed solely by the client to decode an identified sub-part of an image. Such a method also presents the advantage of permitting the parallel encoding and/or decoding of the code-blocks. Thus, the smaller the size of the code-blocks, the higher the level of parallelism. For example, for a level of parallelism fixed at two, two code-blocks will be coded and/or decoded in parallel. In theory, the value of the level of parallelism is equal to the number of code-blocks to be coded of the image. However, the compression performance obtained with this method is not optimal having regard to the fact that such coding does not exploit the probabilities arising from the immediate environment of the current code-block.
USPTO Backgrounds
USPTO Backgrounds