HK1244375B - Method for encoding and decoding images, encoding and decoding device, and computer program - Google Patents

Description

Image encoding and decoding method, encoding and decoding device, and computer program

This application is a divisional application of the Chinese invention patent application with application number 201280031335.9, application date June 20, 2012, and entitled "Method for encoding and decoding images, encoding and decoding devices and corresponding computer programs".

Technical Field

The present invention generally belongs to the field of image processing, and more precisely to the encoding and decoding of digital images and digital image sequences.

The invention is thus particularly applicable to video coding implemented in current digital video encoders (MPEG, H.264, etc.) or future video encoders (ITU-T/VCEG (H.265) or ISO/MPEG (HVC)).

Background Art

Current video encoders (MPEG, H264, etc.) use a block-by-block representation of video sequences. Images are divided into macroblocks, each macroblock itself can be divided into blocks, and each block or macroblock is encoded using intra-image or inter-image prediction. Thus, certain images are encoded using spatial prediction (intra-prediction), while other images are encoded using temporal prediction (inter-prediction) relative to one or more coded-decoded reference images, with the aid of motion compensation known to those skilled in the art. Furthermore, for each block, a residual block corresponding to the original block minus the prediction can be encoded. The coefficients of this block can be quantized after transformation and then encoded by an entropy encoder.

Intra-prediction and inter-prediction require the availability of certain previously coded and decoded blocks, which are then used to predict the current block at the decoder or encoder. FIG1 shows an exemplary embodiment of such predictive coding, wherein an image _IN is divided into blocks, and a current block _MBi of the image is predictively coded with respect to a predetermined number of previously coded and decoded blocks _MBr1 , _MBr2 , and _MBr3 , as indicated by the shaded arrows. These three blocks specifically include block _MBr1 , which is located immediately to the left of the current block _MBi , and two blocks _MBr2 and _MBr3, which are located immediately above and immediately to the right of the current block _MBi , respectively.

The entropy encoder is of greater interest here. It encodes information in the order in which it arrives. This is typically done by a "raster scan" style of block traversal, starting with the block in the upper left corner of the image, as shown in Figure 1, using the PRS. For each block, the various pieces of information necessary to represent the block (block type, prediction mode, residual coefficients, etc.) are sequentially distributed to the entropy encoder.

A sufficiently complex and efficient arithmetic coder called "CABAC" (Context-Adaptive Binary Arithmetic Coder) is known which was introduced in the AVC compression standard (also known as ISO-MPEG4 Part 10 and ITU-T H.264).

The entropy encoder implements various concepts:

Arithmetic coding: an encoder such as that originally described in the document J. Rissanen and G. G. Langdon Jr, “Universal modeling and coding,” IEEE Trans. Inform. Theory, vol. IT-27, pp. 12-23, Jan. 1981, encodes a symbol using the probability of its occurrence;

Context Adaptation: This involves adapting the probability of occurrence of the symbols to be encoded. This allows for rapid learning. Furthermore, the specific context used for encoding depends on the state of the previously encoded information. Each context has an inherent probability of occurrence associated with it. For example, the context corresponds to the type of symbol to be encoded according to a given configuration (representation of residual coefficients, signaling a coding mode, etc.) or the state of the neighborhood (e.g., the number of "inner" modes selected within the neighborhood).

- Binarization: This is the shaping of the bit sequence of the symbol to be coded. These individual bits are then successively distributed to a binary entropy coder.

Thus, for each context used, the entropy encoder implements a system that quickly learns the probabilities of previously encoded symbols for the context under consideration. This learning is based on the order in which these symbols are encoded. Typically, the image is traversed according to a "raster scan" type of order as described above.

During the coding of a given symbol b, which can be 0 or 1, the learning of the probability of occurrence _pi of this symbol for the current block MB _i is updated in the following way:

Here, α is a predetermined value such as 0.95, and p _i-1 is the probability of occurrence of the symbol calculated when the symbol appears last.

FIG1 shows an exemplary embodiment of such entropy coding, in which a current block MB _i of an image I _N is entropy coded. At the start of entropy coding of block MB _i , the symbol occurrence probabilities used are those obtained after coding the previously coded and decoded block that immediately precedes the current block MB _i , according to the aforementioned "raster scan" type of block traversal. For the sake of clarity of the figure only, such block-by-block dependency learning is indicated in FIG1 by thin arrows for specific blocks.

A disadvantage of this type of entropy coding is that, taking into account the "raster scan" traversal of the blocks, when coding a symbol located at the beginning of a line, the probabilities used mainly correspond to those seen for the symbol at the end of the previous line. Now, taking into account possible spatial variations in the symbol probabilities (for example, for a symbol associated with a motion information item, the motion located in the right part of the image can be different from that seen in the left part, and therefore similar for the subsequent local probabilities), a lack of local consistency in the probabilities can be observed, which can increase the efficiency losses during coding.

To limit this phenomenon, adjustments to the order in which blocks are traversed have been proposed, with the goal of ensuring better local consistency but still preserving sequential encoding and decoding.

This type of entropy coder has another drawback. Indeed, since the encoding and decoding of symbols depends on probabilities learned in this way, the decoding of symbols can only be performed in the same order as used during encoding. Typically, decoding can then only be sequential, thus preventing the parallel decoding of several symbols (which would benefit from multi-core architectures, for example).

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, further states that the CABAC entropy encoder has the special feature of allocating a non-integer number of bits to each symbol of the current alphabet to be encoded, which is advantageous for symbol occurrence probabilities greater than 0.5. Specifically, the CABAC encoder waits until it has read a number of symbols before allocating a predetermined number of bits to the set of symbols read, which the encoder writes into the compressed stream to be sent to the decoder. This provision makes it possible to "interact" the bits on several symbols and encode a symbol on a fractional number of bits that reflects information that is closer to the information actually transmitted by the symbol. The other bits associated with the symbol read are not sent in the compressed stream, but remain waiting, waiting to be assigned to one or more new symbols to be read by the CABAC encoder, making it possible to interact with these other bits again. In a known manner, the entropy encoder "clears" these unsent bits at a given moment. Unless otherwise specified, at this given moment, the encoder extracts the bits that have not yet been sent and writes them to the compressed stream going to the decoder. This clearing is performed, for example, at the moment when the last symbol to be encoded has been read, to ensure that the compressed stream does contain all the bits that will allow the decoder to decode all the symbols in the alphabet. In a more general way, the moment when the clearing is performed is determined as a function of the performance and functionality specific to a given encoder/decoder.

A document available on the internet at http://research.microsoft.com/en-us/um/people/jinl/paper_2002/msri_jpeg.htm, dated April 15, 2011, describes a method for encoding a still image in accordance with the JPEG 2000 compression standard. The still image undergoes a discrete wavelet transform and is then quantized, thereby obtaining quantized wavelet coefficients, each associated with a quantization index. The obtained quantization indexes are encoded with the aid of an entropy encoder. The quantized coefficients are previously grouped into rectangular blocks, typically 64x64 or 32x32 in size, called code blocks. Each code block is then independently entropy-encoded. Consequently, when encoding the current code block, the entropy encoder does not use the symbol occurrence probabilities calculated during the encoding of the previous code block. The entropy encoder is thus initialized at the start of each code block encoding. This method demonstrates the advantage of decoding the data of a code block without having to decode adjacent code blocks. Thus, for example, client software can request server software to provide only the compressed code blocks required by the client to decode an identified subsection of an image. This method also exhibits the advantage of allowing parallel encoding and/or decoding of code blocks. Thus, the smaller the code block size, the higher the level of parallelism. For example, with a fixed parallelization level of 2, two code blocks will be encoded and/or decoded in parallel. In theory, the value of the parallelization level is equal to the number of code blocks to be encoded in the image. However, given that this encoding does not exploit the probability of intermediate contexts emerging from the current code block, the compression performance achieved by this method is suboptimal.

Summary of the Invention

An object of the present invention is to remedy the above-mentioned drawbacks of the prior art.

To this end, the subject matter of the invention is a method for encoding at least one image, comprising the following steps:

- segmenting the image into a number of blocks that may contain symbols belonging to a predetermined set of symbols,

- grouping said blocks into a predetermined number of block subsets,

- encoding each of said subsets of blocks by an entropy coding module by associating digital information with the sign of each block in the subset considered, this coding step comprising a substep of initializing the state variables of the entropy coding module for the first block of the image,

- generating at least one data substream representing at least one of the subset of blocks to be coded,

The method according to the present invention is noteworthy in that:

- in the case where the current block is the first block to be coded in the subset under consideration, determining for this first current block the probabilities of occurrence of symbols which are those already determined for predetermined blocks of coding and decoding of at least one other subset,

- In case the current block is the last coded block in the considered subset:

writing all the digital information associated with said symbols during the encoding of the blocks in said subset under consideration into a substream representing the subset under consideration,

●Implement the initialization sub-step.

The above-mentioned writing step amounts to clearing out the digital information (bits) that have not yet been sent once the last block in the block subset has been encoded, as explained in the above description.

The coupling of the aforementioned writing step and the step of reinitializing the entropy coding module makes it possible to generate a coded data stream comprising individual data substreams corresponding to the at least one coded block subset, said stream being suitable for coding according to various levels of parallelism, independent of the type of coding applied to the block subset, whether sequential or parallel. Thus, a great deal of freedom can be exercised in the choice of the level of parallelism during encoding, as a function of the desired encoding/decoding performance. The level of parallelism during decoding can be varied and can even differ from the level of parallelism during encoding, since the decoder is always in an initialized state when starting decoding of the block subset.

According to a first example, the state variables of the entropy coding module are two boundaries of an interval representing the probability of occurrence of a symbol among the symbols of a predetermined set of symbols.

According to a second example, the state variable of the entropy coding module is a string of symbols contained in the conversion table of the LZW (Lempel-Ziv-Welch) entropy encoder which is well known to those skilled in the art and described on June 21, 2011 at the following Internet address http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch.

The main benefit of using the symbol occurrence probabilities determined for the first block of the other subset during the entropy coding of the first current block of the block subset under consideration is that the encoder's buffer memory is saved by storing in the latter only the updates of the symbol occurrence probabilities without taking into account the symbol occurrence probabilities learned by other consecutive blocks in the other subset.

The benefit of using symbol occurrence probabilities determined for blocks other than the first block in the subset of blocks under consideration, such as the second block, during entropy encoding of the first current block in the subset of blocks is to obtain more accurate and thus better learned symbol occurrence probabilities, thereby promoting better video compression performance.

In certain embodiments, subsets of blocks are encoded sequentially or in parallel.

The fact that the subset blocks are coded sequentially has the advantage of demonstrating that the coding method according to the invention complies with the H.264/MPEG-4 AVC standard.

The fact that subset blocks are encoded in parallel has the benefit of speeding up encoder processing time and benefiting from a multi-platform architecture for image coding.

In another particular embodiment, when at least two block subsets are encoded in parallel with at least one other block subset, the at least two encoded block subsets are contained in the same data substream.

This provision makes it particularly possible to save signaling for data substreams. Indeed, in order to enable the decoding unit to decode the substream as early as possible, it is necessary to indicate in the compressed file where the substream in question begins. When several block subsets are contained in the same data substream, a single indicator is required, thereby reducing the size of the compressed file.

In yet another particular embodiment, when said coded block subsets are intended to be coded in parallel in a predetermined order, the data substreams presented after each respective coding of the block subsets are pre-ordered according to the predetermined order before being sent for decoding.

This provision makes it possible to adapt a coded data substream to a specific type of decoding, without requiring the picture to be decoded and then encoded again.

Relatedly, the present invention also relates to a device for encoding at least one image, comprising:

- means for dividing the image into a plurality of blocks, each of which may contain symbols belonging to a predetermined set of symbols,

- means for grouping said blocks into a predetermined number of block subsets,

means for encoding each of the subset of blocks, said encoding means comprising an entropy coding module capable of associating digital information with the sign of each block in the considered subset, said encoding means comprising sub-means for initializing, for a first block in the image, the state variables of the entropy coding module,

- means for generating at least one data substream of data, the data substream representing at least one of the subset of blocks to be coded.

The encoding device is noteworthy in that it comprises:

means for determining the probabilities of occurrence of symbols of the current block, which, in the case where the current block is the first block to be coded in the subset under consideration, determine the probabilities of occurrence of symbols of the first block to be those already determined for predetermined blocks of the coding and decoding of at least one other subset,

- writing means which, in the event that the current block is the last coded block in the subset under consideration, are activated to write all the digital information that has been associated with said symbol during the coding of the blocks in the subset under consideration, into a substream representing at least the subset under consideration,

The initialization sub-device is also activated to reinitialize the state variables of the entropy coding module.

In a corresponding manner, the invention also relates to a method for decoding a stream representing at least one coded image, comprising the following steps:

- identifying in said stream a predetermined number of data substreams corresponding respectively to at least a subset of blocks to be decoded, said blocks being capable of containing symbols belonging to a predetermined set of symbols,

- decoding, by an entropy decoding module, the identified subset of blocks by reading, in at least one identified substream, digital information associated with a symbol corresponding to each block of the subset of at least one said identified substream, this decoding step comprising a substep of initializing state variables of said entropy decoding module for a first block to be decoded in the image,

The decoding method is noteworthy in that:

- in the case where the current block is the first block to be decoded in the subset under consideration, determining the probabilities of occurrence of symbols of the first block in the subset under consideration, these probabilities being those already determined for predetermined blocks to be decoded of at least one other subset,

- said initialization sub-step is implemented in the case where the current block is the last decoded block in the subset considered.

In certain embodiments, the subsets of blocks are decoded sequentially or in parallel.

In another specific embodiment, one of the identified data substreams represents the at least two block subsets when the at least two block subsets are decoded in parallel with at least one other block subset.

In yet another specific embodiment, when the coded block subsets are intended to be decoded in parallel in a predetermined order, the data substreams respectively corresponding to the coded block subsets are previously sorted in the predetermined order in the stream to be decoded.

Relatedly, the invention also relates to a device for decoding a stream representing at least one coded image, comprising:

- means for identifying in said stream a predetermined number of data substreams corresponding respectively to at least a subset of blocks to be decoded, said blocks being capable of containing symbols belonging to a predetermined set of symbols,

means for decoding the identified subset of blocks, the decoding means comprising an entropy decoding module capable of reading, in at least one of said identified substreams, digital information associated with a symbol corresponding to each block of the subset of at least one identified substream, the decoding means comprising submeans for initializing, for a first block to be decoded in the image, state variables of the entropy decoding module,

The decoding device is noteworthy in that it comprises means for determining the probabilities of occurrence of symbols of the current block, in the case where the current block is the first block to be decoded in the subset considered, these means determine the probabilities of occurrence of symbols of this first block as those already determined for predetermined blocks to be decoded of at least one other subset,

And it is that, in the case that the current block is the last decoded block in the subset considered, the initialization sub-means is activated to reinitialize the state variables of the entropy decoding module.

The invention also relates to a computer program comprising instructions for carrying out the steps of the encoding or decoding method described above, when the program is executed by a computer.

The program may use any programming language and may be in the form of source code, object code or an intermediate code between source code and object code, such as a partially compiled form or any other desired form.

Yet another subject of the present invention is a recording medium that is readable by a computer and contains the computer program instructions described above.

The recording medium may be an entity or device capable of storing a program. For example, the medium may include a storage device such as a ROM such as a CD ROM or a microelectronic circuit ROM, or a magnetic storage device such as a magnetic disk (floppy disk) or a hard disk.

Furthermore, the recording medium may be a transmissible medium such as an electrical or optical signal, which may be transferred via electrical or optical cables, by radio or other means.The program according to the invention may in particular be downloaded from a network of the Internet type.

Alternatively, the recording medium may be an integrated circuit in which the program is embodied, the circuit being adapted to execute the method in question or to be used when the latter is executed.

The above-mentioned encoding device, decoding method, decoding device and computer program exhibit the same advantages as those possessed by the encoding method according to the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

Other features and advantages will become apparent from a reading of the two preferred embodiments described with reference to the accompanying drawings, in which:

- FIG1 shows a prior art image coding diagram,

- FIG2A shows the main steps of the encoding method according to the invention,

- FIG. 2B shows in detail the encoding implemented in the encoding method of FIG. 2A ,

- FIG3A shows a first embodiment of a coding device according to the invention,

- FIG. 3B shows a coding unit of the coding device in FIG. 3A ,

- FIG3C shows a second embodiment of a coding device according to the invention,

- FIG. 4A shows an image encoding/decoding diagram according to a first preferred embodiment,

- FIG. 4B shows an image encoding/decoding diagram according to a second preferred embodiment,

- FIG5A shows the main steps of the decoding method according to the invention,

- FIG. 5B shows in detail the decoding implemented in the decoding method of FIG. 5A ,

- FIG. 6A shows an embodiment of a decoding device according to the invention,

- FIG. 6B shows a decoding unit of the decoding device in FIG. 6A ,

- FIG. 7A shows an image encoding/decoding diagram that implements sequential type encoding and parallel type decoding,

- FIG. 7B shows an image encoding/decoding diagram for implementing parallel types of encoding/decoding at different levels of parallelism.

DETAILED DESCRIPTION

An embodiment of the present invention will now be described in which a binary stream obtained by encoding, for example, in accordance with the H.264/MPEG-4 AVC standard, is used to encode a sequence of images according to the encoding method according to the present invention. In this embodiment, the encoding method according to the present invention is implemented, for example, in software or hardware, by modifying an encoder that originally conforms to the H.264/MPEG-4 AVC standard. The encoding method according to the present invention is represented in the form of an algorithm comprising steps C1 to C5, as shown in FIG2A .

According to an embodiment of the present invention, the encoding method according to the present invention is implemented in an encoding device CO, two embodiments of which are respectively represented in Figures 3A and 3C.

With reference to FIG2A , the first encoding step C1 consists in dividing an image IE in the sequence of images to be encoded into a plurality of blocks or macroblocks MB, as shown in FIG4A or 4B . The macroblocks may contain one or more symbols, which form part of a predetermined set of symbols. In the example shown, the blocks MB are square and all have the same size. As a function of the image size, the image does not need to be a multiple of the block size; the last block on the left and the last block at the bottom may not be square. In alternative embodiments, the blocks may, for example, be rectangular in size and/or may not be aligned with one another.

Each block or macroblock may itself be further divided into sub-blocks, which may themselves be further subdivided.

This partitioning is performed by the partitioning module PCO shown in FIG3A , which uses a well-known partitioning algorithm.

Referring to FIG2A , the second encoding step C2 involves grouping the aforementioned blocks into a predetermined number P of consecutive block subsets SE1, SE2, ..., SEk, ..., SEP, to be encoded sequentially or in parallel. In the example shown in FIG4A and FIG4B , only four subsets SE1, SE2, SE3, and SE4 are shown for clarity. These four block subsets are each indicated by a dashed line and contain blocks from the first four rows of image IE.

This grouping is performed by the calculation module GRCO shown in FIG. 3A , with the aid of algorithms known per se.

With reference to FIG2A , the third encoding step C3 consists in encoding each of the block subsets SE1 to SE6, encoding the blocks of the considered subset according to a predetermined traversal order PS, for example of the sequential type. In the example shown in FIG4A and 4B , the blocks of the current block SEk (1≤k≤P) are encoded successively from left to right, as indicated by the arrows PS.

According to a first variant, the coding is of sequential type and is implemented by a single coding unit UC as shown in Figure 3A. In a manner known per se, the coder CO comprises a buffer memory MT adapted to contain the probabilities of the occurrence of symbols that are gradually and repeatedly updated when the current block is coded.

As shown in more detail in FIG3B , the coding unit UC comprises:

* A module that predictively encodes a current block with respect to at least one previously coded and decoded block, denoted as MCP;

* A module for entropy encoding the current block using the probability of occurrence of at least one symbol calculated for the previously coded and decoded blocks, denoted MCE.

The predictive coding module MCP is a software module capable of predictively coding the current block according to conventional prediction techniques, for example in intra and/or inter mode.

The entropy coding module MCE is itself of CABAC type, but is adapted according to the invention, as will be described further in the description.

As a variant, the entropy coding module MCE may be a Huffman coder known per se.

In the example shown in Figures 4A and 4B, the unit UC encodes the blocks in the first row SE1 from left to right. When it reaches the last block of the first row SE1, it passes to the first block of the second row SE2. When it reaches the last block of the second row SE2, it passes to the first block of the third row SE3. When it reaches the last block of the third row SE3, it passes to the first block of the fourth row SE4, and so on, until the last block of the image IE is encoded.

Other types of traversal than those just described are of course possible. Thus, the image IE can be divided into several sub-images and this type of division applied independently to each sub-image. The encoding unit can also process the columns sequentially instead of the rows as explained above. It is also possible to traverse the rows or columns in any direction.

According to the second variant, the encoding is of the parallel type and is distinguished from the first variant of sequential encoding only by the fact that it is implemented by a predetermined number R of encoding units UCk (1≤k≤R) (R=2 in the example shown in FIG3C ). It is known that this parallel encoding brings a significant acceleration to the encoding method.

Each of the coding units UCk is equivalent to the coding unit UC shown in Figure 3B. In a corresponding manner, the coding unit UCk includes a prediction coding module MCPk and an entropy coding module MCEk.

Referring again to Figures 4A and 4B, the first unit UC1 encodes blocks in odd-numbered rows, while the second unit UC2 encodes blocks in even-numbered rows. More precisely, the first unit UC1 encodes the blocks in the first row SE1 from left to right. When it reaches the last block of the first row SE1, it passes on the first block of the (2n+1)th row, which is the third row SE3, and so on. In parallel with the processing performed by the first unit UC1, the second unit UC2 encodes the blocks in the second row SE2 from left to right. When it reaches the last block of the second row SE2, it passes on to the first block of the (2n)th row, which is the fourth row SE4, and so on. The above two traversals are repeated until the last block of the image IE is encoded.

With reference to FIG2A , the fourth encoding step C4 generates L substreams of bits F1, F2, ..., Fm, ..., FL (1≤m≤L≤P) representing the processed blocks compressed by each of the above-mentioned coding units UC or UCk, as well as decoded versions of the processed blocks in each subset SEk. According to a synchronization mechanism that will be further detailed in the description, the decoded processed blocks represented by SED1, SED2, ..., SEDk, ..., SEDP in the considered subset can be multiplexed by each of the coding units UC shown in FIG3A or UCk shown in FIG3C .

3B , the step of generating L sub-streams is implemented by a stream generation software module MGSF or MSGFk, which is adapted to generate a data stream, eg bits.

With reference to FIG2A , the fifth encoding step C5 comprises constructing a global stream F based on the L substreams F1, F2, ..., Fm, ..., FL described above. According to one embodiment, the substreams F1, F2, ..., Fm, ..., FL are simply concatenated, with an additional information item indicating to the decoder the position of each substream Fm within the global stream F. The latter is then transmitted via a communication network (not shown) to a remote terminal. The latter includes a decoder DO shown in FIG5A . According to another embodiment, this is particularly advantageous because, without having to decode the image and then re-encode it, the decoder DO sorts the L substreams F1, F2, ..., Fm, ..., FL in a predetermined order before transmitting the stream F to the decoder DO, which corresponds to the order in which the substreams can be decoded by the decoder DO.

Thus, as described in more detail in the description, the decoder according to the present invention is able to separate the substreams F1, F2, ..., Fm, ..., FL in the global stream F and distribute them to one or more decoding units constituting the decoder. It should be noted that this decomposition of the substreams in the global stream is independent of the choice of using a single coding unit or several coding units operating in parallel, and that with this method, only the encoder or only the decoder can be provided, which includes units operating in parallel.

This construction of the global flow F is implemented in the flow construction module CF shown in, for example, Figures 3A and 3C.

Various specific sub-steps of the invention will now be described with reference to FIG. 2B , for example sub-steps implemented in the coding unit UC or UCk during the above-described coding step C3 .

During step C31 , the coding unit UC or UCk selects the current block SEk shown in FIG. 4A or 4B , for example, the first block to be coded in the first row SE1 , as the current block.

During a step C32 , the unit UC or UCk tests whether the current block is the first block (at the top and on the left) of the image IE which has been divided into blocks in the above-described step C1 .

If this is the case, during step C33, the entropy coding module MCE or MCEk initializes its state variables. According to the example shown, arithmetic coding, as described above, is used. This involves initializing an interval representing the probability of occurrence of symbols contained in the predetermined symbol set. In a manner known per se, this interval is initialized with two boundaries, L and H, respectively, a lower boundary and an upper boundary. The value of the lower boundary, L, is fixed to 0, while the value of the upper boundary is fixed to 1, thus corresponding to the probability of occurrence of the first symbol among all symbols of the predetermined symbol set. The size R of this interval is therefore now defined by R = H - L = 1. The initialized interval is conventionally further divided into a number of predetermined subintervals, each representing the probability of occurrence of a symbol from the predetermined symbol set.

As a variant, if the entropy coding used is LZW coding, the conversion table of strings of symbols is initialized so that it contains all possible symbols once and only once.

If the current block is not the first block of the image IE after the above-mentioned step C32 , the availability of necessary previously encoded and decoded blocks is determined during step C40 to be described later in the subsequent description.

During step C34, the first current block MB1 in the first row SE1 shown in Figure 4A or 4B is encoded. This step C34 comprises a number of sub-steps C341 to C348 which will be described below.

During a first sub-step C341 shown in FIG. 2B , the current block MB1 is predictively coded by known techniques of intra and/or inter prediction, during which the block MB1 is predicted with respect to at least one previously coded and decoded block.

Of course, other modes of intra prediction, such as those proposed in the H.264 standard, are also possible.

The current block MB1 can also be predictively coded in intra mode, in which the current block is predicted with respect to blocks that appeared in previously coded and decoded images. Other types of prediction are of course also possible. Among the possible predictions for the current block, the optimal prediction is selected according to a bit rate distortion criterion well known to those skilled in the art.

The predictive coding step described above makes it possible to construct a predicted block MBp ₁ , which is an approximation of the current block MB ₁ . The information relating to the predictive coding is subsequently written into a stream F, which is sent to the decoder DO. This information includes in particular the prediction type (inter or intra) and, if applicable, the type of intra prediction, the type of partitioning of the block or macroblock (if the latter has been subdivided), the reference image index used in the inter prediction mode, and the displacement vector. This information is compressed by the encoder CO.

During the subsequent sub-step C342 , the prediction block MBp ₁ is subtracted from the current block MB ₁ to generate a residual block MBr ₁ .

During a subsequent sub-step C343 , the residual block MBr ₁ is transformed according to a conventional direct transformation operation, for example a discrete cosine transformation of the DCT type, in order to generate a transformed block MBt ₁ .

In the subsequent sub-step C344 , the transformed block MBt ₁ is quantized according to a conventional quantization operation, such as scalar quantization, to obtain a block MBq ₁ with quantized coefficients.

During the subsequent sub-step C345, the block MBq ₁ with quantized coefficients is entropy coded. In a preferred embodiment, this involves CABAC entropy coding. This step comprises:

a) reading a symbol associated with said current block or a symbol from a predetermined set of symbols,

b) Associating digital information, such as bits, with the read symbols.

In the variant described above, according to which the encoding used is the LZW encoding, an item of digital information corresponding to the code of the symbol currently in the conversion table is associated with the symbol to be encoded, and the conversion table is updated according to a procedure known per se.

During the subsequent sub-step C346 , the block MBq ₁ is dequantized according to a conventional dequantization operation, ie, an operation opposite to the quantization performed in step C344 , thereby obtaining a block MBDq ₁ with dequantized coefficients.

In the subsequent sub-step C347 , the block MBDq ₁ with inversely quantized coefficients is subjected to an inverse transform, which is the opposite operation to the direct transform performed in the above step C343 , and the decoded residual block MBDr ₁ is then obtained.

During the subsequent sub-step C348, the decoded block MBD 1 is constructed by adding the decoded residual block MBDr ₁ to the prediction block MBp _1. It should be noted _that this latter block is identical to the decoded block obtained after the method for decoding the image IE described further in the description is completed. The decoded block MBD ₁ is thus rendered available for use by the coding unit UCk forming part of the predetermined number R of coding units or any other coding unit.

After the encoding step C34, the entropy encoding module MCE or MCEk, for example as shown in FIG3B , contains all the probabilities that were updated repeatedly during the encoding of the first block. These probabilities correspond to the various elements of the possible syntax or the various associated coding contexts.

After the above-mentioned encoding step C34 , a test is performed during a step C35 to determine whether the current block is the j-th block of the same row, where j is a predetermined value known to the coder CO and which is at least equal to 1.

If this is the case, during step C36 shown in Figure 2B, the set of probabilities calculated for the jth block is stored in a buffer memory MT of the encoder CO shown, for example, in Figure 3A or 3B and Figures 4A and 4B, the size of which is adapted to store the calculated number of probabilities.

2B , the coding unit UC or UCk tests whether the current block of the line SEk just coded is the last block in the image IE. This step is also performed if, during step C35 , the current block is not the jth block of the line SE1 .

When the current block is the last block of the image IE, the coding method ends during a step C38 .

If this is not the case, during a step C39 , the next block MB _i to be coded is selected according to the traversal order indicated by the arrow PS in FIG. 4A or 4B .

During step C40 shown in FIG. 2B , the availability of previously coded and decoded blocks necessary for the coding of the current block MB _i is determined.

If this is the first row SE1, this step involves verifying the availability of at least one block located to the left of the MB _i to be coded. However, for the traversal order PS selected in the embodiment shown in FIG4A or 4B, the blocks in the row SEk under consideration are coded sequentially. As a result, a block to the left is always available (except for the first block of a row) to be coded and decoded. In the example shown in FIG4A or 4B, this is the block directly to the left of the current block to be coded.

If this is a row SEk different from the first row, the determining step further comprises verifying whether a predetermined number N' of blocks located in the previous row SEk-1, e.g. two blocks located above and above the right of the current block respectively, can be used for the encoding of the current block, i.e. whether they have already been encoded by the coding unit UC or UCk-1 and then decoded.

Since this test step tends to slow down the encoding method, an alternative approach according to the invention is to adapt the clock CLK shown in FIG3C to synchronize the progress of block encoding, in the case where the encoding of the lines is of the parallel type, to ensure the availability of two blocks located above and to the right of the current block, respectively, without having to verify the availability of these two blocks. Thus, the encoding unit UCk always starts the encoding of the first block with an offset of a predetermined number N' (e.g., N'=2) of coded and decoded blocks from the previous line SEk-1 used for the encoding of the current block. From a software perspective, the implementation of such a clock makes it possible to significantly speed up the processing time of the blocks in the image IE in the encoder CO.

During step C41 shown in FIG. 2B , a test is performed to determine whether the current block is the first block in the row SEk considered.

If this is the case, during a step C42 , only the probabilities of the occurrence of the symbols calculated during the coding of the j-th block of the previous row SEk-1 are read in the buffer memory MT.

According to a first variant shown in FIG4A , the jth block is the first block of the previous row SE k-1 (j=1). This reading involves replacing the probabilities of the CABAC coder with the probabilities present in the buffer memory MT. This reading step is illustrated in FIG4A as a thin arrow, so that it processes the first blocks of the second, third, and fourth rows SE2, SE3, and SE4, respectively.

According to a second variant of the above-described step C43, shown in FIG4B , the jth block is the second block (j=2) of the previous row SEk-1. This reading involves replacing the probabilities of the CABAC coder with the probabilities present in the buffer memory MT. This reading step is illustrated in FIG4B as a thin dashed arrow, so that it processes the first blocks of the second, third, and fourth rows SE2, SE3, and SE4, respectively.

After step C42, the current block is encoded and then decoded by repeating the above steps C34 to C38.

If, after the above-mentioned step C41, the current block is not the first block of the row SEk considered, it is advantageous not to read the probabilities of occurrence in the previously coded and decoded block located in the same row SEk, i.e., in the example shown, the coded and decoded block located immediately to the left of the current block. Indeed, given the traversal order PS for reading blocks located in the same row, as shown in FIG4A or 4B , the probabilities of occurrence of the symbols present in the CABAC coder at the start of the coding of the current block are exactly the same as those that existed after the coding/decoding of the previous block in the same row.

As a result, during step C43 shown in Figure 2B, the probabilities of the occurrence of symbols are learned for the entropy coding of the current block, which (probabilities) correspond only to those probabilities calculated for the previous block in the same row as shown by the double solid arrows in Figure 4A or 4B.

After step C43, the above steps C34 to C38 are repeated to encode and then decode the current block.

After the process of step C44 , a test is performed to determine whether the current block is the last block in the row SEk considered.

If this is not the case, after step C44 , step C39 of selecting the next block MB _i to be coded is implemented again.

If the current block is the last block of the row SEk under consideration, during a step C45, the coding device CO of FIG3A or 3C performs the flushing mentioned above. To this end, the coding unit UCk sends all the bits associated with the symbols read during the coding of each block of the row under consideration to the corresponding substream generation module MGSFk, in such a way that the module MGSFk writes all the bits into a substream Fm containing a binary string representing the block being coded in the row SEk under consideration. This situation is represented in FIG4A and 4B by the triangle at the end of each row SEk.

During step C46 shown in FIG2B , the coding unit UC or UCk performs the same steps as in step C33 above, namely reinitializing the intervals representing the probability of occurrence of the symbols contained in the predetermined symbol set. This reinitialization is indicated in FIG4A and 4B by the black dots at the beginning of each row SEk.

The benefit of performing steps C45 and C46 at this coding level is that during the coding of the next block processed by coding unit UC or coding unit UCk, the encoder CO is in an initialized state. Thus, as will be described further below, the decoding units operating in parallel may start decoding the compressed stream F directly from this point on, since it satisfies the initialized state.

Detailed description of an embodiment of the decoding part

An embodiment of a decoding method according to the invention will now be described, wherein the decoding method according to the invention is implemented, for example, in software or hardware by adapting an encoder originally compliant with the H.264/MPEG-4 AVC standard.

The encoding method according to the present invention is represented in the form of an algorithm comprising steps D1 to D4, as shown in FIG5A.

According to an embodiment of the present invention, the decoding method according to the present invention is implemented in a decoding device DO shown in FIG. 6A .

With reference to FIG5A , the first decoding step consists in identifying, in the stream F, L substreams F1, F2, ..., Fm, ..., FL, each containing P subsets SE1, SE2, ..., SEk, ..., SEP of previously coded blocks or macroblocks MB, as shown in FIG4A or 4B . To this end, each substream in the stream F is associated with an indicator intended to allow the decoder DO to determine the position of each substream Fm in the stream F. As a variant, upon completion of the encoding step C3 described above, the decoder CO sorts the substreams F1, F2, ..., Fm, ..., FL of the stream F in the order desired by the decoder DO, thereby avoiding the need to insert substream identifiers in the stream F. This provision thus makes it possible to reduce the costs associated with the bit rate of the data stream F.

In the examples shown in FIG4A or 4B , the blocks MB are square and all have the same size. Depending on the image size, the image does not have to be a multiple of the block size; the last block on the left and the last block at the bottom may not be square. In alternative embodiments, the blocks may be rectangular in size and/or may not be aligned with each other.

Each block or macroblock may itself be further divided into sub-blocks, which may themselves be further subdivided.

This identification is performed by, for example, the flow extraction module EXDO shown in FIG. 6A .

In the example shown in FIG. 4A or 4B , the predetermined number P is equal to 6, and for clarity of the drawing, only four subsets SE1 , SE2 , SE3 , SE4 are shown with dotted lines.

Referring to FIG5A , the second decoding step D2 decodes each of the block subsets SE1, SE2, SE3, and SE4, where the blocks in the considered subset are encoded according to a predetermined traversal order PS. In the example shown in FIG4A or 4B , the blocks in the current subset SEk (1≤k≤P) are decoded sequentially from left to right as indicated by the arrow PS. Upon completion of step D2, decoded block subsets SED1, SED2, SED3, ..., SEDk, ..., SEDP are obtained.

Such decoding may be of sequential type and therefore performed with the aid of a single decoding unit.

However, in order to be able to benefit from a multi-platform decoding architecture, the decoding of the block subset is of a parallel type and is carried out by a number R of decoding units UDk (1≤k≤R), for example, R=4 as shown in FIG6A . This provision thus allows a significant acceleration of the decoding method. In a manner known per se, the decoder DO includes a buffer memory MT adapted to contain the probability of the occurrence of symbols, which is gradually and repeatedly updated during the decoding of the current block.

As shown in more detail in FIG. 6B , each decoding unit UDk comprises:

a module for entropy decoding the current block by learning the probability of occurrence of at least one symbol calculated for at least one previously decoded block, denoted MDEk,

The module that performs predictive decoding on the current block with respect to the previously decoded block is denoted by MDPk.

The predictive decoding module SUDPk is capable of decoding the current block according to conventional prediction techniques such as intra and/or inter modes.

The entropy decoding module MDEk is itself of CABAC type, but adapted according to the invention, as will be further described below in the description.

As a variant, the entropy decoding module MDEk may be a Huffman decoder known per se.

In the example shown in FIG4A or 4B, the first unit UD1 decodes the blocks in the first row SE1 from left to right. When it reaches the last block of the first row SE1, it passes on to the first block of the (n+1)th row, here, row 5, and so on. The second unit UC decodes the blocks in the second row SE2 from left to right. When it reaches the last block of the second row SE2, it passes on to the first block of the (n+2)th row, here, row 6, and so on. This process repeats until the unit UD4 decodes the fourth row from left to right. When it reaches the last block of the first row, it passes on to the first block of the (n+4)th row, here, row 8, and so on until the last block of the last identified substream is decoded.

Different traversal types than those just described are of course possible. For example, each decoding unit may process not the embedded rows as explained above but the embedded columns. It is also possible to traverse the rows or columns in any direction.

Referring to FIG5A , the third decoding step D3 reconstructs the decoded picture ID based on each decoded subset SED1, SED2, ..., SEDk, ..., SEDP obtained in decoding step D2. More specifically, the decoded blocks in each decoded subset SED1, SED2, ..., SEDk, ..., SEDP are sent to a picture reconstruction unit URI, such as that shown in FIG6A . During step D3 , the unit URI writes the decoded blocks to the decoded picture when it becomes available.

During the fourth decoding step D4 shown in FIG. 5A , the unit URI shown in FIG. 6A gives the fully decoded image ID.

Various specific sub-steps of the invention will now be described with reference to FIG. 5B , for example sub-steps implemented in a decoding unit UDk during the above-mentioned step D2 of parallel decoding.

During step D21 , the decoding unit UDk selects the first block to be decoded among the current blocks SEk shown in FIG. 4A or 4B as the current block.

During a step D22 , the decoding unit UDk tests whether the current block is the first block of the image to be decoded, in this case the first block of the sub-stream F1 .

If this is the case, during a step D23 , the entropy decoding module MDE or MDEk initializes its state variables. According to the example shown, this entails initializing the intervals representing the probabilities of the occurrence of the symbols contained in the predetermined set of symbols.

As a variant, if the entropy decoding used is LZW decoding, the conversion table of strings of symbols is initialized so that it contains all possible symbols once and only once. Step D23 is identical to the encoding step C33 described above and will not be described again.

If the current block is not the first block in the decoded picture ID after the above-mentioned step D22, the availability of a necessary previously decoded block is determined during step D30 to be described later in the subsequent description.

During step D24, the first current block MB1 in the first row SE1 shown in Figure 4A or 4B is decoded. This step D24 includes a plurality of sub-steps D241 to D246 which will be described below.

In the first sub-step D241, entropy decoding is performed on the syntax elements related to the current block. This step mainly includes:

a) reading the bits contained in the substream associated with said first row SE1,

b) Reconstruct the symbol based on the read bits.

In the variant described above, according to which the decoding used is LZW decoding, the digital information item corresponding to the symbol code currently in the conversion table is read, the symbol is reconstructed based on the code read and the conversion table is updated according to a procedure known per se.

More precisely, the symbol elements associated with the current block are decoded by a CABAC entropy decoding module MDE1, such as that shown in FIG6B . The latter decodes the bit substream F1 of the compressed file to generate the symbol elements and simultaneously re-updates their probabilities in such a way that, when the latter decodes a symbol, the probability of its occurrence is equal to the probabilities obtained when encoding the same symbol during the aforementioned entropy decoding step C345.

During the subsequent sub-step D242 , the current block MB1 is predictively decoded by known techniques of intra and/or inter prediction, during which the block MB1 is predicted with respect to at least one previously decoded block.

Of course, other intra prediction modes, such as those proposed in the H.264 standard, are also possible.

During this step, predictive decoding is performed with the help of syntax elements decoded in the previous step, which include in particular the type of (inter or intra) prediction and, if applicable, the mode of intra prediction, the partitioning type of the block or macroblock (if the latter has been subdivided), the reference image index used in the inter prediction mode and the displacement vector.

The predictive decoding step described above makes it possible to reconstruct the predicted block MBp ₁ .

During the subsequent sub-step D243 , the quantized residual block MBq ₁ is reconstructed with the help of previously decoded syntax elements.

During the subsequent sub-step D244 , the quantized residual block MBq ₁ is dequantized according to a conventional dequantization operation, ie an operation opposite to the quantization performed in the above-mentioned step C344 , to generate a decoded dequantized block MBDt ₁ .

In the subsequent sub-step D245 , the inverse transform is performed on the dequantized block MBDt _{1 ,} which is an operation opposite to the direct transform performed in the above step C343 , thereby obtaining the decoded residual block MBDr ₁ .

During a subsequent sub-step D246 , the decoded block MBD _{1 is constructed by adding the decoded residual block MBDr 1 to} the prediction block MBp _1. The decoded block MBD ₁ is thus rendered available for use by the decoding unit UD1 or any other decoding unit forming part of the predetermined number N of decoding units.

Upon completion of the above decoding step D246 , the entropy decoding module MDE1 , for example as shown in FIG6B , contains all the probabilities that are gradually and repeatedly updated while decoding the first block. These probabilities correspond to the various elements of the possible syntax and to the various associated decoding contexts.

After the above-mentioned decoding step D24 , a test is performed during a step D25 to determine whether the current block is the jth block of the same row, where j is a predetermined value known to the decoder DO and at least equal to 1.

If this is the case, during step D26 , the set of probabilities calculated for the jth block is stored in a buffer memory MT, for example as shown in FIG. 6A and in the decoder DO in FIG. 4A or 4B , the size of said memory being adapted to store the number of calculated probabilities.

During a step D27 , the unit UDk tests whether the current block that has just been decoded is the last block of the last sub-stream.

If this is the case, the decoding method ends during a step D28 .

If this is not the case, the next block MB _i to be decoded is selected during a step D29 according to the traversal order indicated by the arrows PS in FIG. 4A or 4B .

If, during the above step D25 , the current block is not the j-th block of the row SEDk considered, the above step D27 is executed.

During step D30, following step D29, the availability of previously decoded blocks necessary for decoding the current block MB _i is determined. Given the fact that this requires parallel decoding of blocks by different decoding units UDk, it may happen that these blocks have not yet been decoded by the decoding units designated to decode them and are therefore not yet available. This determination step involves verifying whether a predetermined number N' of blocks located in the previous row SEk-1, for example, two blocks located above and to the right of the current block, are available for decoding the current block, i.e., whether they have already been decoded by the decoding unit UDk-1 designated to decode it. This determination step also includes determining the availability of at least one block located to the left of the current block MB _i to be encoded. However, given the selected traversal order PS in the embodiment shown in FIG. 4A or 4B , the blocks in the row SEk considered are decoded sequentially. As a result, the blocks decoded to the left are always available (except for the first block in a row). In the example shown in FIG. 4A or 4B , this requires decoding the block directly to the left of the current block. To this end, only the availability of the two blocks located above and to the right of the current block, respectively, is tested.

Since this test step tends to slow down the decoding method, an alternative approach according to the invention is to adapt the clock CLK shown in FIG6A to synchronize the progress of block decoding to ensure the availability of two blocks located above and to the right of the current block, respectively, without verifying the availability of these two blocks. Thus, as shown in FIG4A or 4B , the decoding unit UDk always starts decoding the first block with an offset of a predetermined number N′ (where N′=2) of decoded blocks in the previous row SEk-1 used for decoding the current block. From a software perspective, such a clock implementation makes it possible to significantly speed up the processing time of each block in the decoder DO for each subset SEk.

During a step D31 , a test is performed to determine whether the current block is the first block in the row SEk considered.

If this is the case, during a step D32 , only the probabilities of the occurrence of the symbols calculated during the decoding of the j-th block of the previous row SEk-1 are read in the buffer memory MT.

According to a first variant shown in FIG4A , the jth block is the first block of the previous row SE k-1 (j=1). This reading involves replacing the probabilities of the CABAC decoder with the probabilities present in the buffer memory MT. This reading step is illustrated in FIG4A as a thin arrow so that it processes the first blocks of the second, third, and fourth rows SE2, SE3, and SE4, respectively.

According to a second variant of the above-described step D32, shown in FIG4B , the jth block is the second block (j=2) of the previous row SEk-1. This reading involves replacing the probabilities of the CABAC decoder with the probabilities present in the buffer memory MT. This reading step is illustrated in FIG4B as a thin dashed arrow, so that it processes the first blocks of the second, third, and fourth rows SE2, SE3, and SE4, respectively.

After step D32, the current block is decoded by repeating the above steps D24 to D28.

If, after the above-mentioned step D31, the current block is not the first block of the row SEk considered, it is advantageous not to read the probabilities present in the previously decoded block located in the same row SEk, i.e., in the example shown, the block immediately to the left of the current block. Indeed, given the traversal order PS for reading blocks located in the same row, as shown in FIG4A or 4B , the probabilities of the symbols present in the CABAC decoder at the start of decoding the current block are exactly the same as those present after the decoding of the previous block in the same row.

As a result, during step D33 , the probabilities of symbol occurrence are learned for entropy decoding of the current block, which probabilities correspond only to those calculated for the previous block in the same row as indicated by the double solid arrows in FIG. 4A or 4B .

After step D33, the above steps D24 to D28 are repeated to decode the current block.

After the process of step D34 a test is performed to determine whether the current block is the last block in the row SEk considered.

If this is not the case, after step D34 , step D29 of selecting the next block MB _i to be decoded is implemented again.

If the current block is the last block of the row SEk considered, during a step D35 the decoding means UDk perform the same steps as those of the above-described step D23, namely reinitializing the intervals representing the probabilities of occurrence of the symbols contained in the predetermined set of symbols. This reinitialization is represented in Figures 4A and 4B by the black dots at the beginning of each row SEk.

The decoder DO is then in an initialized state at the beginning of each line, thereby allowing greater flexibility from the point of view of choosing the level of parallelism of the decoding and optimizing the processing time of the decoding.

In the exemplary encoding/decoding diagram shown in FIG. 7A , the encoder CO includes a single encoding unit UC, as shown in FIG. 3A , while the decoder DO includes six decoding units.

The decoding unit sequentially encodes lines SE1, SE2, SE3, SE4, SE5, and SE6. In the example shown, lines SE1 through SE4 are fully encoded, line SE5 is in the process of being encoded, and line SE6 has not yet been encoded. To account for the sequential nature of encoding, the encoding unit UC is adapted to provide a stream F containing sequentially ordered substreams F1, F2, F3, and F4 to encode lines SE1, SE2, SE3, and SE4. To this end, substreams F1, F2, F3, and F4 are represented using the same shading as the encoded lines SE1, SE2, SE3, and SE4, respectively. By clearing the substreams at the end of encoding each encoded line and reinitializing the probability interval at the start of encoding or decoding the next line to be encoded/decoded, the decoder DO is in an initialized state each time it reads a substream for decoding. The four substreams F1, F2, F3, and F4 can be decoded in parallel in an optimized manner using decoding units UD1, UD2, UD3, and UD4, which can be installed on, for example, four different platforms.

In the exemplary encoding/decoding diagram shown in FIG. 7B , the encoder CO includes two encoding units UC1 and UC2 as shown in FIG. 3C , while the decoder DO includes six decoding units.

Coding unit UC1 sequentially encodes the odd-ranked lines SE1, SE3, and SE5, while coding unit UC2 sequentially encodes the even-ranked lines SE2, SE4, and SE6. To this end, lines SE1, SE3, and SE5 appear with a white background, while lines SE2, SE4, and SE6 appear with a dotted background. In the example shown, lines SE1 through SE4 are fully encoded, line SE5 is in the process of being encoded, and line SE6 has not yet been encoded. Taking into account the fact that the level of parallelism performed is 2, coding unit UC1 is adapted to provide a substream F _2n , which can be decomposed into two parts, F2 and F4, obtained after decoding lines SE2 and SE4, respectively. Decoder CO is therefore adapted to send a stream F to decoder DO, which contains the concatenation of the two substreams F _2n+1 and F _2n , and thus a substream ordering F1, F3, F2, F4 that is different from that shown in FIG. 7A . To this end, substreams F1, F2, F3 and F4 are represented with the same shading as the coded lines SE1, SE2, SE3, SE4 respectively, substreams F1 and F3 appearing with a white background (coding of odd-numbered lines) and substreams F2 and F4 appearing with a dotted background (coding of even-numbered lines).

As for the advantages described in connection with FIG. 7A , this encoding/decoding diagram also demonstrates the advantage of being able to flush out a decoder whose decoding parallelism level is completely independent of the encoding parallelism level, thereby making it possible to further optimize the operation of the encoder/decoder.

Claims (13)

1. A method for encoding at least one image, the method comprising: Segment the image into multiple blocks. Group the blocks into a predetermined number of subsets. Quantize the block to obtain a quantized block. Entropy coding is performed on the current quantized block in the block subset using an entropy coding module, wherein the entropy coding includes: The subset is not the first subset in the encoding order of the image when the current quantization block is the first quantization block in the encoding order of the following subset: The probability of symbol occurrence in the current quantization block is determined by entropy encoding a predetermined quantization block of at least one other subset, wherein the predetermined quantization block is the second quantization block in the encoding order of the other subsets. Initialize the state variables of the entropy coding module, and Entropy encoding is performed on the current quantized block; and At least one data substream is generated for the at least one image. 2. The method as claimed in claim 1, wherein the subset of blocks is encoded sequentially or in parallel. 3. The method as claimed in claim 2, wherein when at least two block subsets are encoded in parallel with at least one other block subset, the at least two encoded block subsets are contained in the same data substream. 4. The method as claimed in any one of claims 1 to 3, wherein the entropy encoding further comprises: Perform arithmetic encoding on the symbols of the current quantized block; and The intervals used in arithmetic encoding will be initialized to known values. 5. A method for decoding a stream representing at least one encoded image, the method comprising: Identify a predetermined subset of blocks to be decoded within the stream. By using an entropy decoding module, the current block in the block subset is entropy decoded to obtain the entropy-decoded current block, wherein the entropy decoding includes: When the current block is the first block to be decoded in the following subset, said subset is not the first subset in the decoding order of the encoded image: The probabilities of symbol occurrence in the current block are read. These probabilities are determined by decoding predetermined blocks in at least one other subset, wherein the predetermined block is the second block to be decoded in the decoding order of the other subset. Initialize the state variables of the entropy decoding module, and Perform entropy decoding on the current block; and Dequantize the current block after entropy decoding to obtain the dequantized block. 6. The method as claimed in claim 5, wherein the subset of blocks is decoded sequentially or in parallel. 7. The method as claimed in claim 6, wherein, when at least two subsets of blocks are decoded in parallel with at least one other subset of blocks, one of the identified data substreams represents the at least two subsets of blocks. 8. The method as claimed in any one of claims 5 to 7, wherein the entropy decoding further comprises: Perform arithmetic decoding on the symbols of the current block; and The intervals used in arithmetic decoding will be initialized to known values. 9. An apparatus for encoding at least one image, comprising: A component used to segment an image into multiple blocks. A component used to group blocks into a predetermined number of block subsets. A component used to quantize blocks to obtain quantized blocks. A component for entropy encoding the current quantized block in a subset of blocks using an entropy encoding module, wherein the entropy encoding includes: The subset is not the first subset in the encoding order of the image when the current quantization block is the first quantization block in the encoding order of the following subset: The probability of symbol occurrence in the current quantization block is determined by entropy encoding a predetermined quantization block of at least one other subset, wherein the predetermined quantization block is the second quantization block in the encoding order of the other subsets. Initialize the state variables of the entropy coding module, and Entropy encoding is performed on the current quantized block; and A component for generating at least one data substream for the at least one image. 10. An apparatus for decoding a stream representing at least one encoded image, comprising: A component for identifying a predetermined subset of blocks to be decoded in the stream. A component for obtaining the entropy-decoded current block by performing entropy decoding on the current block in a subset of blocks using an entropy decoding module, wherein the entropy decoding includes: When the current block is the first block to be decoded in the following subset, said subset is not the first subset in the decoding order of the encoded image: The probabilities of symbol occurrence in the current block are read. These probabilities are determined by decoding predetermined blocks in at least one other subset, wherein the predetermined block is the second block to be decoded in the decoding order of the other subset. Initialize the state variables of the entropy decoding module, and Perform entropy decoding on the current block; and A component used to dequantize the current block after entropy decoding to obtain a dequantized block. 11. A computer-readable storage medium having stored thereon program instructions that, when executed by a processor, cause the processor to perform the method according to any one of claims 1-8. 12. An apparatus for encoding at least one image, comprising: The memory is configured to store program instructions, and A processor coupled to memory is configured to execute program instructions. The program instructions, when executed by the processor, cause the processor to perform the method according to any one of claims 1-4. 13. An apparatus for decoding a stream representing at least one encoded image, comprising: The memory is configured to store program instructions, and A processor coupled to memory is configured to execute program instructions. The program instructions, when executed by the processor, cause the processor to perform the method according to any one of claims 5-8.