HK1214050B - Method of coding and decoding images, coding and decoding device - Google Patents

Description

Method for encoding and decoding images, encoding and decoding devices

This application is a divisional application of the Chinese invention patent application with application number 201280021355.8, application date February 23, 2012, and titled "Method for encoding and decoding images, encoding and decoding devices, and computer programs."

Technical Field

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

The present invention can therefore be used in particular for video coding implemented in current 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-wise representation of video sequences. Images are divided into macroblocks, each macroblock itself 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-frame prediction), while other images are encoded using temporal prediction (inter-frame prediction) with respect to one or more encoding-decoding reference images, aided by motion compensation known to those skilled in the art. Furthermore, for each block, a residual block can be encoded, corresponding to the original block minus the prediction. After an optional transform, the coefficients of the block can be quantized and then encoded by an entropy encoder.

Intra-frame prediction and inter-frame prediction require the availability of certain previously coded and decoded blocks, which are then used in the decoder or encoder to predict the current block. FIG1A shows a schematic example of such predictive coding, wherein an image _IN is divided into blocks, and a current block _MBi of the image is subjected to predictive coding with respect to a predetermined number of previously coded and decoded blocks _MBr1 , _MBr2 , and _MBr3 , as indicated by the shaded arrows. The three blocks mentioned above include, in particular, block _MBr1 , located immediately to the left of the current block _MBi , and two blocks _MBr2 and _MBr3, located immediately above and immediately to the right of the current block _MBi , respectively.

Of particular interest here is the entropy encoder. The entropy encoder encodes information in the order it arrives. Typically, a "raster scan" style of block traversal is implemented, starting with the block in the upper left corner of the image, as shown in FIG1A by reference symbol PRS. For each block, the various information items required to represent the block (block type, prediction mode, residual coefficients, etc.) are sequentially distributed to the entropy encoder.

An efficient arithmetic coder of sufficient complexity is known, called “CABAC” (“Context Adaptive Binary Arithmetic Coder”), which was introduced into the AVC compression standard (also known as ISO-MPEG4 Part 10 and ITU-T H.264).

Entropy encoders implement various concepts:

Arithmetic coding: encoders such as those 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, encode symbols using the probability of occurrence of that symbol;

-Context Adaptation: This involves adapting the probability of occurrence of the symbols to be coded. On the one hand, this allows for fast learning. On the other hand, a specific context is used for coding, depending on the state of previously coded information. Each context has a corresponding inherent probability of occurrence of symbols. For example, the context corresponds to the type of coded symbol (residual coefficient, signaling of coding mode, etc.) or to the state of the neighborhood (e.g., the number of "Intra" modes selected from the neighborhood, etc.) according to a given configuration.

- Binarization: The symbol to be encoded is converted into a bit string. The individual bits are then successively distributed to a binary entropy encoder.

The entropy encoder then implements a system for quickly learning the probabilities associated with the symbols previously encoded for the context in question, for each context used. This learning is based on the order in which these symbols were encoded. Typically, the image is traversed according to a "raster scan" type of order, as described above.

When encoding a given symbol b, which may be equal to 0 or 1, the knowledge of the probability of occurrence P _i of this symbol is updated for the current block MB _i in the following way:

Wherein, α is a predetermined value, such as 0.95, and Pi _-1 is the probability of occurrence of the symbol calculated when the symbol appears last.

FIG1A shows a schematic example of such entropy coding, in which a current block _MBi of an image I _N is entropy coded. At the start of entropy coding of the current block _MBi , the symbol occurrence probabilities used are those obtained after the encoding of the previously coded and decoded block immediately preceding the current block _MBi , according to the row-by-row traversal of the blocks of the "raster scan" type described above. For clarity of illustration only, FIG1A illustrates the block-by-block dependency learning for a particular block using thin arrows.

A drawback of this type of entropy coding is that, when coding a symbol located at the beginning of a line, the probabilities used correspond mainly to the probabilities observed for the symbol located at the end of the previous line, associated with a "raster scan" traversal of the block. Due to the 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 observed in the left part, and thus the local probabilities resulting therefrom can be similar), a lack of local adaptability of the probabilities can be observed, which risks causing a loss of effectiveness during coding.

A coding method is described in the document "Annex A: CDCM Video Codec Decoder Specification" available at the internet address http://wftp3.itu.int/av-arch/jctvc-site/2010_04_A_ Dresden/JCTVC-A114-Annex A.doc (8 February 2011) which alleviates the above-mentioned drawbacks. As shown in FIG1B , the coding method described in the above document includes:

- a step of dividing the image I _N into a plurality of blocks,

a step of predictive coding of a current block MB _i of the image in conjunction with a predetermined number of three previously coded and decoded blocks MBr ₁ , MBr ₂ , MBr ₃ , indicated, for example, by hatched arrows. These three blocks include in particular the block MBr ₁ situated immediately to the left of the current block MB _i , and the two blocks MBr ₂ and MBr ₃ situated immediately above and immediately to the right of the current block MB _i ,

a step of entropy coding the blocks of the image I _N , according to which, when these blocks are available, each block uses the probability of the occurrence of symbols calculated respectively for the coded and decoded blocks immediately above the current block and for the coded and decoded blocks immediately to the left of the current block. To make the latter clearer, the use of these symbol occurrence probabilities is partially indicated in FIG1B by thin arrows.

The benefit of this entropy coding is that it utilizes the probability generated by the immediate surroundings of the current block, making it possible to obtain higher coding performance. In addition, the coding technique used makes it possible to encode a predetermined number of paired subsets of adjacent blocks in parallel. In the example shown in Figure 1B, three subsets SE1, SE2 and SE3 are encoded in parallel, each of which consists of a row of blocks represented by a dotted line. Of course, this coding requires that blocks located above and to the upper right of the current block are available.

A drawback of this parallel encoding technique is that, in order to access the symbol occurrence probabilities calculated for the blocks immediately above the current block, it is necessary to store a number of probabilities associated with a row of blocks. For example, considering the blocks of the second row SE2 in FIG1B , the first block of the row is entropy encoded using the symbol occurrence probabilities calculated for the first block of the preceding first row SE1. Upon completion of encoding the first block of the second row, the state of the occurrence probability values V1 is stored in the buffer memory MT. Subsequently, the second block of the second row SE2 is entropy encoded using the symbol occurrence probabilities calculated simultaneously for the second block of the first row SE1 and the first block of the second row SE2. Upon completion of encoding the second block of the second row SE2, the state of the occurrence probability values V2 is stored in the buffer memory MT. This process continues until the last block of the second row SE2. Since the number of probabilities is very large (there are as many probabilities as the number of syntax elements and the number of associated contexts combined), storing these probabilities for an entire row is very expensive in terms of memory resources.

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:

- Divide the image into blocks,

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

- parallel encoding of each of the subsets of blocks, the blocks of the considered subset being encoded according to a predetermined order of traversal, the encoding step comprising, for the current block of the considered subset, the following sub-steps:

predictively encoding the current block with respect to at least one previously encoded and decoded block,

Entropy coding of the current block by learning the probability of occurrence of at least one previous symbol,

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, the probability of occurrence of the symbol is the probability of occurrence of the symbol calculated for coded and decoded predetermined blocks in at least one other subset,

- In the case where the current block is a block other than the first block in the considered subset, the symbol occurrence probability is the symbol occurrence probability calculated for at least one coded and decoded block belonging to the same subset.

This arrangement makes it possible to store a smaller number of symbol occurrence probabilities in the buffer memory of the encoder, since the entropy encoding of a current block other than the first block of the subset of blocks no longer necessarily requires the use of symbol occurrence probabilities calculated with respect to a previously encoded and decoded block that is in the other subset and is located above the current block.

This arrangement also makes it possible to maintain the existing compression performance, since the entropy coding of the current block uses the probability of occurrence of symbols calculated for another previously encoded and decoded block in the subset to which the current block belongs, and learning is finally achieved by updating the probabilities so that the latter conform to the statistics of the video signal.

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

The main benefit of using the symbol occurrence probabilities calculated for blocks other than the first block (e.g. the second block) in the other subsets during the entropy encoding of the first current block of the subset of blocks under consideration is that a more precise and therefore better knowledge of the symbol occurrence probabilities is obtained, resulting in better video compression performance.

In a particular embodiment, said coded and decoded blocks belonging to the same subset as the current block to be coded except for the first block in said subset are the nearest neighboring blocks of the current block to be coded.

This arrangement thus makes it possible to store only the learned symbol occurrence probabilities during the entropy coding of the first block in the considered subset, since in this particular case only the symbol occurrence probabilities calculated for the blocks located above the first current block and belonging to another subset are considered. This leads to an optimization in terms of a reduction in the size of the encoder's memory resources.

In another particular embodiment, in the case where the predictive coding of the blocks in the considered subset is to be performed with respect to a predetermined number of previously coded and decoded blocks outside the considered subset, the parallel coding of the blocks in the considered subset is performed with an offset by a predetermined number of blocks relative to the subset of the immediately preceding blocks in the order in which the parallel coding is performed.

This arrangement allows, for a subset of blocks currently being encoded, synchronization of the processing of blocks in the subset of blocks preceding the current subset in the order in which parallel encoding is performed, thereby making it possible to ensure the availability of one or more blocks in the preceding subset for encoding the current block. In this way, the step of verifying the availability of the blocks in the preceding subset (such as is performed in prior art parallel encoders) can be advantageously omitted, thereby allowing the processing time required for processing blocks in the encoder according to the present invention to be accelerated.

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

- a component for dividing the image into blocks,

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

- for each parallel encoding means of a subset of blocks, the blocks of the subset considered are encoded according to a predetermined order of traversal, said encoding means comprising, for a current block of the subset considered,

a subcomponent for predictively encoding the current block with respect to at least one previously encoded and decoded block,

a subcomponent for entropy coding the current block based on at least one symbol occurrence probability,

The coding device is noteworthy in that:

- in the case where the current block is the first block to be coded in the subset under consideration, the entropy coding sub-means take into account, for the entropy coding of the first current block, the probabilities of occurrence of symbols calculated for coded and decoded predetermined blocks in at least one other subset,

- in the case where the current block is a block other than the first block of the subset considered, the entropy coding subcomponent takes into account, for the entropy coding of the current block, the symbol occurrence probabilities calculated for at least one coded and decoded block belonging to the same subset.

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 the image a subset of a predetermined number of blocks to be decoded,

- parallel decoding of the portions of the stream associated with each of the subsets of blocks, the blocks of the considered subset being decoded according to a predetermined order of traversal, said decoding step comprising, for a current block of the considered subset, the following sub-steps:

Entropy decoding of the current block based on at least one symbol occurrence probability,

predictively decoding the current block with respect to at least one previously decoded block,

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, the symbol occurrence probabilities are calculated for already decoded predetermined blocks of at least one other subset,

- In the case where the current block is a block of the considered subset other than the first block in the subset, the symbol occurrence probability is calculated for at least one decoded block belonging to the same subset.

In a particular embodiment, the decoded blocks belonging to the same subset as the current block to be decoded other than the first block in the subset are nearest neighboring blocks of the current block to be decoded.

In another specific embodiment, in a case where predictive decoding of blocks in the considered subset is intended to be performed for a predetermined number of previously encoded and decoded blocks other than the considered subset, parallel decoding of the blocks in the considered subset is performed offset by the predetermined number of blocks relative to the subset of the immediately preceding blocks in the order in which the parallel decoding is performed.

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

- means for identifying in the image a subset of a predetermined number of blocks to be decoded,

- means for partially parallel decoding of the stream associated with each of the subsets of blocks, the blocks of the subset considered being decoded according to a predetermined order of traversal, said decoding means comprising, for a current block of the subset considered:

a subcomponent for entropy decoding the current block based on at least one symbol occurrence probability,

a subcomponent for predictive decoding of the current block with respect to at least one previously decoded block,

The decoding device is noteworthy in that:

- in the case where the current block is the first block to be decoded in the subset under consideration, the sub-means for performing entropy decoding take into account, for the entropy decoding of the first current block, the probabilities of occurrence of symbols calculated for already decoded predetermined blocks of at least one other subset,

- in the case where the current block is a block other than the first block of said considered subset, the sub-means for performing entropy decoding take into account, for entropy decoding of the current block, the probabilities of occurrence of symbols calculated for at least one decoded block belonging to the same subset.

The invention also relates to a computer program comprising instructions for executing the steps of the above encoding or decoding method when this program is executed on a computer.

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

Yet another object of the present invention is a computer-readable recording medium containing the computer program instructions described above.

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

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

Alternatively, the recording medium may be an integrated circuit in which the program is incorporated, the circuit being suitable for executing the method in question or being usable for the execution of the latter.

The above-described encoding device, decoding method, decoding device, and computer program have at least the same advantages as those exhibited by the encoding method according to the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

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

- FIG. 1A shows a prior art picture coding diagram according to a first example,

- FIG. 1B shows a prior art picture coding diagram according to a second example,

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

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

- FIG. 3A shows an embodiment of a coding device according to the invention,

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

- 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,

- FIG5B shows in detail the parallel encoding implemented in the decoding method of FIG5A,

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

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

DETAILED DESCRIPTION

An embodiment of the present invention will now be described in which the encoding method according to the present invention is used to encode a series of images based on a binary stream that approximates a binary stream obtained by encoding in accordance with the H.264/MPEG-4 AVC standard. 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 complies with the H.264/MPEG-4 AVC standard. The encoding method according to the present invention is illustrated 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 the encoding device CO shown in FIG. 3A .

With reference to FIG2A , the first encoding step C1 involves dividing an image IE from the series of images to be encoded into a plurality of blocks or macroblocks MB, as shown in FIG4A or 4B . In the example shown, the blocks MB are square and all of the same size. As a function of the image size, which need not 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 not aligned with one another.

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

This segmentation is achieved by the segmentation module PCO shown in FIG3A , which uses, for example, a well-known segmentation algorithm.

With reference to FIG2A , the second encoding step C2 consists of grouping the blocks into a predetermined number P of consecutive block subsets SE1, SE2, ..., SEk, ..., SEP, which are encoded in parallel. In the example shown in FIG4A and FIG4B , the predetermined number P is equal to 4, and the four subsets SE1, SE2, SE3, and SE4, indicated by dashed lines, each consist of the first four rows of blocks of the image IE.

The grouping operation is implemented by the calculation module GRCO shown in FIG3A using a well-known algorithm.

With reference to FIG2A , the third encoding step C3 comprises encoding each of the subsets SE1, SE2, SE3, and SE4 of blocks in parallel, the blocks of the considered subset being encoded according to a predetermined order PS of traversal. In the example shown in FIG4A and FIG4B , the blocks of the current subset SEk (1≤k≤4) are encoded sequentially from left to right as indicated by the arrows PS.

This parallel coding is achieved by a number R of coding units UCk (1≤k≤R) (R=4) as shown in FIG3A and allows a significant acceleration of the coding method. In a known manner, the coder CO comprises a buffer memory MT suitable for containing, for example, gradually updated symbol occurrence probabilities in conjunction with the coding of the current block.

As shown in more detail in FIG3B , each coding unit UCk includes:

The sub-unit for predictive coding of the current block with respect to at least one previously coded and decoded block, denoted by SUCPk;

• A sub-unit of entropy coding of said current block by using at least one symbol occurrence probability calculated for said previously coded and decoded block, denoted SUCEk.

The prediction coding sub-unit SUCPk is capable of performing prediction coding of the current block according to conventional prediction techniques, for example in intra and/or inter modes.

The entropy coding sub-unit SUCEk itself is of CABAC type, but is adapted according to the present invention, which will be further described in the specification.

As a variant, the entropy coding sub-unit SUCEk may be a known Huffman coder.

In the example shown in Figures 4A and 4B, the first unit UC1 encodes the blocks of the first row SE1 from left to right. When the last block of the first row SE1 is reached, the first block of the (N+1)th row, which is row 5, is passed to. The second unit UC2 encodes the blocks of the second row SE2 from left to right. When the last block of the second row SE2 is reached, the first block of the (N+2)th row, which is row 6, is passed to, and so on. This process is repeated until the unit UC4 encodes the blocks of the fourth row SE4 from left to right. When the last block of the first row is reached, the first block of the (N+4)th row, which is row 8, is passed to, 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 split into several sub-images, and this type of segmentation applied independently to each sub-image. Each coding unit can also process nested columns instead of rows as explained above. It is also possible to traverse rows or columns in any direction.

With reference to FIG2A , the fourth encoding step C4 generates N sub-bitstreams Fk (1≤k≤N), representing the processed blocks compressed by each coding unit, as well as decoded versions of the processed blocks in each subset SEk. According to a synchronization mechanism described in further detail later in this specification, the decoded processed blocks in the considered subset, denoted by SED1, SED2, ..., SEDk, ..., SEDP, can be reused by certain coding units UC1, UC2, ..., UCk, ..., UCP, as shown in FIG3A .

With reference to FIG2A , the fifth encoding step C5 comprises constructing a global stream F based on the substreams Fk described above. According to one embodiment, the substreams Fk are simply arranged in parallel, with additional information indicating to the decoder the position of each substream Fk within the global stream F. The global stream F is transmitted via a communication network (not shown) to a remote terminal. The latter includes a decoder DO shown in FIG6A .

Thus, as will be described in more detail later in the description, the decoder according to the invention is able to isolate the substreams Fk of the global stream F and assign them to each constituent decoding unit of the decoder. It should be noted that the decomposition of the substreams into the global stream is independent of the choice of using several decoding units operating in parallel, and that this approach makes it possible to use only encoders or decoders that include units operating in parallel.

This construction of the global flow F is implemented in the flow construction module CF as shown in FIG3A .

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

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

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

If this is the case, during a step C33, the coding probabilities are initialized to the values Pinit previously defined in the coder CO of FIG. 3A .

If this is not the case, in a step C40 , which will be described in detail in the subsequent description, the availability of the necessary previously encoded and decoded blocks is determined.

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

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

Needless to say, other modes of intra-frame prediction proposed in the H.264 standard, for example, are also possible.

The current block MB1 can also be subjected to inter-mode predictive coding, during which the current block is predicted with respect to blocks generated from previously coded and decoded images. Of course, other types of prediction are conceivable. Among the possible predictions for the current block, the optimal prediction is selected according to a rate-distortion criterion well known to those skilled in the art.

The predictive coding step described above makes it possible to construct a prediction block MBp ₁ , which is an approximation of the current block MB ₁ . The information relating to this predictive coding is then written to a stream F which is sent to the decoder DO. This information contains in particular the type of prediction (inter or intra) and, if applicable, the mode of intra prediction, the type of partitioning of the block or macroblock (if the macroblock is subdivided), the reference image index, and the offset vector used in the inter prediction mode. 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 the 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), generating a transformed block MBt ₁ .

During the subsequent sub-step C344 , the transformed block MBt ₁ is quantized according to a conventional quantization operation (for example scalar quantization), and a block MBq ₁ of quantized coefficients is then obtained.

During a subsequent sub-step C345 , the block MBq ₁ of quantized coefficients is entropy coded. In a preferred embodiment, this requires CABAC entropy coding.

During a subsequent sub-step C346 , the block MBq ₁ is dequantized according to a conventional dequantization operation, which is the inverse of the quantization performed in step C344 . A block MBDq ₁ is then obtained whose coefficients are dequantized.

During the subsequent sub-step C347 , the block MBDq ₁ whose coefficients are inversely quantized is subjected to an inverse transformation, which is the inverse operation of the direct transformation performed in the above step C343 . The decoded residual block MBDr ₁ is then obtained.

During a subsequent sub-step C348, a decoded block MBD _{1 is constructed by adding the decoded residual block MBDr 1} to _the prediction block MBp _1. It should be noted that the latter is identical to the decoded block obtained upon completion of the method for decoding the image IE described further in this description. The decoded block MBD ₁ can then be used by the coding unit UC1 or any other coding unit constituting the predetermined number R of coding units.

Upon completion of the encoding step C34, the entropy encoding subunit SUCEk, as shown in FIG3B , contains all probabilities that have been updated gradually, for example, in conjunction with the encoding of the first block. These probabilities correspond to various possible syntax elements and to various relevant encoding contexts.

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

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

During a step C37 , the unit UCk tests whether the current block in the line SEk that has just been coded is the last block of the image IE.

If this is the case, the encoding method ends during a step C38 .

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

If, during step C35 , the current block is not the j-th block in the considered row SEk, the above step C37 is not performed.

During step C40, the availability of previously coded and decoded blocks necessary for encoding the current block _MBi is determined. Given the fact that this requires parallel coding of blocks of the image IE by different coding units UCk, the coding units used to encode these blocks may not have already coded and decoded 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 encoding the current block, i.e., whether they have already been coded and subsequently decoded by the coding unit UCk-1 that coded it. This determination step also includes verifying the availability of at least one block located to the left of the current block _MBi to be encoded. However, given the traversal order PS selected in the embodiment shown in FIG. 4A or 4B , the blocks in the row SEk under consideration are encoded sequentially. Therefore, the coded and decoded blocks 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 blocks located immediately to the left of the current block to be encoded. To this end, only the two blocks located above and to the right of the current block are tested for availability.

This test step tends to slow down the encoding method. By using an alternative method according to the present invention, the clock CLK shown in FIG. 3A is adapted to synchronize the block encoding process, thereby ensuring the availability of two blocks located above and to the right of the current block, respectively, without requiring verification of their availability. Thus, as shown in FIG. 4A or 4B , the encoding unit UCk always begins encoding the first block with a predetermined number N′ (where N′=2) of coded and decoded blocks from the previous row SEk-1 used for the encoding of the current block as an offset. Implementing such a clock makes it possible, from a software perspective, to significantly accelerate the processing time required for processing blocks in an image IE in the encoder CO.

During a step C41 , 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 symbol occurrence probabilities 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 (j=1) 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. The first blocks of the second row SE2, the third row SE32, and the fourth row SE4 are processed, and this reading step is depicted in FIG4A by the thin arrows.

According to a second variant of the above-described step C42, 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 encoder with the probabilities present in the buffer memory MT. This is done for the first blocks of the second row SE2, the third row SE32, and the fourth row SE4, respectively. This reading step is depicted in FIG4B by the dashed arrows.

After step C42 , through iterations of steps C34 to C38 described above, the current block is encoded and then decoded.

If, after the above-mentioned step C41, the current block is not the first block of the row SEk considered, the probabilities resulting from the previously coded and decoded blocks located in the same row SEk (i.e., the coded and decoded blocks located immediately to the left of the current block in the example shown) are advantageously not read in. Indeed, considering a sequential traversal reading PS of blocks located in the same row, as shown in FIG4A or 4B , the probability of occurrence of the symbols present in the CABAC encoder at the start of the coding of the current block is exactly the probability of occurrence of the symbols present after the coding/decoding of the previous block in the same row.

Therefore, during step C43, the entropy-coded symbol occurrence probability of the current block is learned, which only corresponds to the symbol occurrence probability calculated for the previous block in the same row as indicated by the double solid arrows in FIG. 4A or 4B.

After step C43 , through iterations of steps C34 to C38 described above, the current block is encoded and then decoded.

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 is implemented in software or hardware by adapting a decoder originally compliant with the H.264/MPEG-4 AVC standard.

The decoding method according to the present invention is presented in the form of an algorithm comprising steps D1 to D4 as shown in FIG. 5A .

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

With reference to FIG5A , the first decoding step D1 consists in identifying N substreams F1, F2, ..., Fk, ..., FP in the stream F, each containing N subsets SE1, SE2, ..., SEk, ..., SEP of a previously encoded block or macroblock MB, as shown in FIG4A or 4B . To this end, each substream Fk in the stream F is associated with an indicator that allows the decoder DO to determine the position of each substream in the stream F. In the example shown, the blocks MB are square and all have the same size. As a function of the image size, which does not necessarily 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, for example, be rectangular in size and/or misaligned.

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

Such identification is performed by the stream extraction module EXDO as represented in FIG. 6A .

In the example shown in FIG. 4A or 4B , the predetermined number is equal to 4, and the four subsets SE1 , SE2 , SE3 , SE4 are indicated by dotted lines.

Referring to FIG5A , the second decoding step D2 involves decoding each of the block subsets SE1, SE2, SE3, and SE4 in parallel, with the blocks in the considered subset being encoded according to the traversal order PS. In the example shown in FIG4A or 4B , the blocks in the current subset SEk (1≤k≤4) 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.

This parallel decoding is realized by a number R (R=4) of decoding units UDk (1≤k≤R) as shown in FIG6A and allows a significant acceleration of the decoding method. In a known manner, the decoder DO comprises a buffer memory MT suitable for containing symbol occurrence probabilities that are gradually updated, for example, in conjunction with the decoding of the current block.

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

a subunit, denoted SUDEk, for entropy decoding the current block by knowing at least one symbol occurrence probability calculated for at least one previously decoded block,

The sub-unit for predictive decoding of the current block with respect to the previously decoded block is denoted by SUDPk.

The predictive decoding sub-unit SUDPk is capable of performing predictive decoding of the current block according to conventional prediction techniques, for example in intra and/or inter modes.

The entropy decoding sub-unit SUDEk is itself of CABAC type, but adapted according to the present invention, as will be described further in the description.

As a variant, the entropy decoding sub-unit SUDEk may be a known Huffman decoder.

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 the last block of the first row SE1 is reached, the block is passed to the first block of the (N+1)th row (here, the 5th row), and so on. The second unit UC2 decodes the blocks in the second row SE2 from left to right. When the last block of the second row SE2 is reached, the block is passed to the first block of the (N+2)th row (here, the 6th row), and so on. This process is repeated until the unit UD4 decodes the blocks in the fourth row SE4 from left to right. When the last block of the first row is reached, the block is passed to the first block of the (N+4)th row (here, the 8th row), and so on until the last block in the last identified substream is decoded.

Other types of traversal than those just described are of course also possible. For example, each decoding unit may process nested columns instead of rows as explained above. Rows or columns may also be traversed in any direction.

Referring to FIG5A , the third decoding step D3 reconstructs a decoded image 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 an image reconstruction unit URI, such as that shown in FIG6A . During step D3 , the unit URI writes the decoded blocks into the decoded image as they become 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 as implemented in a decoding unit UDk, for example during the above-described parallel decoding step D2, will now be described with reference to FIG. 5B .

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 unit UDk tests whether the current block is the first block of the image being decoded, in this example the first block of the sub-stream F1 .

If this is the case, during a step D23, the decoding probability is initialized to the value Pinit previously defined in the decoder DO of Figure 6A.

If this is not the case, the availability of the necessary previously decoded blocks will be determined during step D30 described 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.

During a first sub-step D241, the syntax elements associated with the current block are entropy decoded. More precisely, the syntax elements associated with the current block are decoded by a CABAC entropy decoding sub-unit SUDE1, for example as shown in FIG6B . The CABAC entropy decoding sub-unit SUDE1 decodes the sub-bitstream F1 of the compressed file to generate syntax elements and simultaneously updates their probabilities in such a way that, at the moment a symbol is decoded by this sub-unit, the probability of the occurrence of this symbol is equal to the probability of the occurrence of the symbol obtained when encoding the same symbol in the above-mentioned entropy encoding step C345.

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

Needless to say, other modes of intra-frame prediction proposed in the H.264 standard, for example, are also possible.

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

The above-described predictive decoding step makes it possible to construct the prediction block MBp ₁ .

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

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

During the subsequent sub-step D245 , the inverse transformation is performed on the dequantized block MBDt ₁ , which is the inverse operation of the direct transformation performed in the above step C343 . The decoded residual block MBDr ₁ is then obtained.

During a subsequent sub-step D246 _, a decoding block MBD ₁ is constructed by adding the prediction block MBp 1 to the decoded residual block MBDr _1. Said decoding block MBD ₁ can then be used 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 subunit SUDE1, for example as shown in FIG6B, contains all probabilities that are gradually updated, for example in cooperation with the decoding of the first block. These probabilities correspond to various possible syntax elements and 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 j-th block of this same row, where j is a predetermined value known to the decoder DO and is at least equal to 1.

If this is the case, during a step D26 , the set of probabilities calculated for the jth block is stored in a buffer memory MT of the decoder DO, for example as shown in FIG. 6A and FIG. 4A or 4B , the size of which is suitable for storing 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, step D29 is executed, during which the next block MB _i to be decoded is selected according to the traversal order indicated by the arrow PS in FIG. 4A or 4B .

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

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 encoding of blocks by different decoding units UDk, these blocks may not have been decoded by the decoding units used 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 (e.g., two blocks located above and to the right of the current block, respectively) are available for decoding the current block, i.e., whether they have already been decoded by the decoding unit UDk-1 that decoded it. This determination step also involves verifying the availability of at least one block located to the left of the current block MB _i to be decoded. However, given the traversal order PS selected in the embodiment shown in FIG. 4A or 4B , the blocks in the row SEk under consideration are decoded sequentially. Therefore, the decoded blocks 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 that the blocks be located immediately to the left of the current block to be decoded. To this end, only the two blocks located above and to the right of the current block, respectively, are tested for availability.

This test step tends to slow down the decoding method. By using an alternative method according to the invention, the clock CLK shown in FIG6A is adapted to synchronize the block decoding process, thereby ensuring 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, as shown in FIG4A or 4B , the decoding unit UDk always starts decoding the first block with a predetermined number N′ (where N′=2) of decoded blocks from the row SEk-1 preceding the current block as an offset. Implementing such a clock makes it possible, from a software perspective, to significantly accelerate the processing time required to process the blocks in each subset SEk in the decoder DO.

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 symbol occurrence probabilities 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 (j=1) 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. The same process is performed for the first blocks of the second row SE2, the third row SE3, and the fourth row SE4, respectively. This reading step is depicted in FIG4A by the thin arrows.

According to a second variant of step D32 described above, 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 is done for each of the first blocks in the second row SE2, the third row SE3, and the fourth row SE4, a reading step depicted by the dashed arrows in FIG4B .

After step D32, the current block is decoded through iterations of steps D24 to D28 described above.

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 resulting from the previously decoded block located in the same row SEk (i.e., the decoded block located immediately to the left of the current block in the example shown). Indeed, considering a sequential traversal reading PS of blocks located in the same row, as shown in FIG4A or 4B , the probability of the occurrence of the symbols present in the CABAC decoder at the start of the decoding of the current block is exactly the probability of the occurrence of the symbols present after the decoding of the previous block in the same row.

Therefore, during step D33, the symbol occurrence probabilities for entropy decoding of the current block are learned, which only correspond to the symbol occurrence probabilities 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 current block is decoded through iterations of steps D24 to D28 described above.

Claims (12)

1. A computer-implemented method, comprising: Receive a stream representing at least one encoded image; Identify groups of multiple predefined blocks from the stream; Provide each block group to the first decoding unit; and The first block in a given block set is processed by the first decoding unit, wherein the processing of the first block includes: Determine that the first block is the first in the order of blocks within the given group of blocks; In response to determining that the first block is the first in the order of blocks in the given group of blocks, a first set of probability data is retrieved from the buffer, wherein the first set of probability data includes a first set of symbol occurrence probabilities associated with a block that is located immediately adjacent to the first block and belongs to a group of another block that is different from the group of the given group of blocks in the predetermined plurality of blocks. Entropy decoding of the first block is performed based on the first set of probability data; and The first decoding unit processes the second block in the given block set, wherein the processing of the second block includes: Determine that the second block is not the first in the order of the given group of blocks; In response to determining that the second block is not the first in the order of blocks in the given group of blocks, a second set of probability data is retrieved from the memory cell, wherein the second set of probability data includes a second set of symbol occurrence probabilities associated with at least one other decoded block, which belongs to the given group of blocks in the predetermined plurality of groups of blocks. The probability of the second group of symbols appearing is not associated with blocks that do not belong to the group of the given block; and Entropy decoding of the second block is performed based on the second set of probability data. 2. The method of claim 1, further comprising: A third set of probability data is generated based on the second set of probability data and the data about the second block; and Replace the second set of probability data in the memory cell with the third set of probability data. 3. The method of claim 1, wherein: Entropy decoding of the first block based on the first set of probability data includes: using the context-adapted binary arithmetic coding (CABAC) algorithm to entropy decode the first block based on the first set of probability data; and Entropy decoding of the second block based on the second set of probability data includes: using the CABAC algorithm to perform entropy decoding of the second block based on the second set of probability data. 4. The method of claim 1, further comprising: Generate the third set of probability data based on the first set of probability data and the data about the first block; Store the third set of probability data into the memory unit; and Use at least a third set of probability data to generate the second set of probability data. 5. The method of claim 1, further comprising: Predictive decoding is performed on each block in the group of the given blocks, relative to at least one previously decoded block. 6. The method of claim 1, further comprising: The first decoding unit processes the third block in the given block group, wherein the processing of the third block includes: Retrieve a third set of probability data from the memory cell, wherein the third set of probability data includes a third set of symbol occurrence probabilities associated with the at least one other decoded block, and wherein the third set of probability data is based at least on the second set of probability data; and Entropy decoding of the third block is performed based on the third set of probability data. 7. A computer-implemented system, comprising: One or more computers and one or more storage devices storing instructions, the instructions being operable to cause the one or more computers to perform operations including: Receive a stream representing at least one encoded image; Identify groups of multiple predefined blocks from the stream; Provide each block group to the first decoding unit; and The first block in a given block set is processed by the first decoding unit, wherein the processing of the first block includes: Determine that the first block is the first in the order of blocks within the given group of blocks; In response to determining that the first block is the first in the order of blocks in the given group of blocks, a first set of probability data is retrieved from the buffer, wherein the first set of probability data includes a first set of symbol occurrence probabilities associated with a block that is located immediately adjacent to the first block and belongs to a group of another block that is different from the group of the given group of blocks in the predetermined plurality of blocks. Entropy decoding of the first block is performed based on the first set of probability data; and The first decoding unit processes the second block in the given block set, wherein the processing of the second block includes: Determine that the second block is not the first in the order of the given group of blocks; In response to determining that the second block is not the first in the order of blocks in the given group of blocks, a second set of probability data is retrieved from the memory cell, wherein the second set of probability data includes a second set of symbol occurrence probabilities associated with at least one other decoded block, which belongs to the given group of blocks in the predetermined plurality of groups of blocks. The probability of the second group of symbols appearing is not associated with blocks that do not belong to the group of the given block; and Entropy decoding of the second block is performed based on the second set of probability data. 8. The system of claim 7, wherein the operation further comprises: A third set of probability data is generated based on the second set of probability data and the data about the second block; and Replace the second set of probability data in the memory cell with the third set of probability data. 9. The system of claim 7, wherein: Entropy decoding of the first block based on the first set of probability data includes: using the context-adapted binary arithmetic coding (CABAC) algorithm to entropy decode the first block based on the first set of probability data; and Entropy decoding of the second block based on the second set of probability data includes: using the CABAC algorithm to perform entropy decoding of the second block based on the second set of probability data. 10. The system of claim 7, wherein the operation further comprises: Generate the third set of probability data based on the first set of probability data and the data about the first block; Store the third set of probability data into the memory unit; and Use at least a third set of probability data to generate the second set of probability data. 11. The system of claim 7, wherein the operation further comprises: Predictive decoding is performed on each block in the group of the given blocks, relative to at least one previously decoded block. 12. The system of claim 7, wherein the operation further comprises: The first decoding unit processes the third block in the given block group, wherein the processing of the third block includes: Retrieve a third set of probability data from the memory cell, wherein the third set of probability data includes a third set of symbol occurrence probabilities associated with the at least one other decoded block, and wherein the third set of probability data is based at least on the second set of probability data; and Entropy decoding of the third block is performed based on the third set of probability data.