Abstract:
Several attempts have been tried to improve the performance of intra-prediction in video encoding and decoding, which are targeting at pixel level parallelization. A solution for implementing an improved intra-prediction method on a parallel processing platform uses estimated predictors instead of reconstructed exact predictors. This enables faster estimation of predictors, and allows an encoder to perform intra-prediction for all blocks of at least a portion of an image simultaneously.

Description:
This application is a 371 of PCT/CN2010/000901 filed on Jun. 21, 2010. 
     This application claims the benefit, under 35 U.S.C. §365 of International Application PCT/CN2010/000901, filed Jun. 21, 2010, which was published in accordance with PCT Article 21(2) on Dec. 29, 2011 in English. 
     FIELD OF THE INVENTION 
     This invention relates to a method and an apparatus for encoding image data, and a method and an apparatus for decoding image data. 
     BACKGROUND 
     This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that the statements in this section are to be read in this light, and not as admissions of prior art. 
     Various video coding standards, e.g. MPEG-4 Part 10/AVC, apply a spatial based intra prediction algorithm for taking advantage of spatial redundancy within images. The intra prediction is done for various block sizes (e.g. 4×4, 8×8 and 16×16). Taking 4×4 block intra prediction as an example, there are in AVC nine pre-defined spatial predictors and the prediction directions for predicting. One of the biggest issues of intra prediction schemes employed in AVC is its complexity. In order to make a correct prediction of the current block, the blocks that are located on the left and upper side of a current block are reconstructed first, after their own encoding and before serving as predictors. Therefore, image encoding can only be performed sequentially, in left-to-right and up-down directions. 
     Nowadays, the processing architectures are evolving from high performance sequential processor architecture to parallel processor architectures (e.g. IBM&#39;s cell processor, Intel&#39;s Larabee processor, and nVidia or AMD&#39;s GPUs etc.) The introduction of these processors is changing the way computation is done with computers. The more parallelism an application has, the better the application will perform on the processors. However, in AVC encoding, intra prediction cannot be efficiently be performed using these processors, due to the fact that intra prediction is a natural born sequential processing problem. 
     Several attempts have been tried to improve the performance of intra prediction in video encoding and decoding, which are targeted at pixel level parallelization. This approach can make prediction for a line of pixels according to the prediction mode. These methods are efficient on DSP or FPGA implementations, but the above-mentioned parallel processor architectures cannot take advantage of those proposed schemes. 
     SUMMARY OF THE INVENTION 
     In light of the above, a solution for implementing an improved intra prediction method on a parallel processing platform remains a problem to be solved. The present invention provides such solution, and is suitable for improving the efficiency of intra prediction at least on the encoder side. In various embodiments, also an improvement on the decoder side is achieved. 
     The present invention is based on the recognition of the fact that image prediction can be based on estimated predictors instead of exactly reconstructed predictors, while yielding good prediction results and therefore high compression efficiency. 
     In principle, a method for encoding image data where the image data are structured in blocks comprises for each block in (at least a portion of) the image a first prediction step of predicting the pixels of two edges of a block, based on original pixels of neighbouring blocks, wherein estimated predictor pixels are obtained, and a second prediction step of predicting remaining pixels of the block from the predicted predictor pixels of at least neighbouring blocks. 
     According to one embodiment of the invention, a method for encoding image data, the image data being structured in blocks, comprises for each block in (at least a portion of) the image steps of predicting the pixels of two edges of a block in a first prediction step, wherein the prediction is based on pixels of neighbouring blocks from the original image, and wherein estimated predictor pixels are obtained, determining residual data for the estimated predictor pixels, performing quantization and inverse quantization on the determined residual data for the estimated predictor pixels, wherein reconstructed residual data for estimated predictor pixels are obtained, reconstructing predictor pixels, wherein the difference between original pixels and reconstructed residual data for estimated predictor pixels is obtained, in a second prediction step, predicting remaining pixels of the block from the predicted predictor pixels of at least neighbouring blocks, determining residual data for each predicted pixel resulting from the first or second prediction step, the residual data being the difference between the predicted pixel and its corresponding original pixel, and entropy encoding the residual data. 
     Further, according to another embodiment of the invention, a device for encoding image data, which are structured in blocks, comprises first and second prediction means, first and second residual determining means, quantizer and inverse quantizer means, reconstruction means, and entropy coding means. The apparatus performs for each block in at least a portion of the image the steps of 
     in the first prediction means, predicting the pixels of two edges of a block in a first prediction step, wherein the prediction is based on pixels of neighbouring blocks from the original image, and wherein estimated predictor pixels are obtained; 
     in the residual determining means, determining residual data for the estimated predictor pixels; 
     in the quantizer and inverse quantizer, performing quantization and inverse quantization on the determined residual data for the estimated predictor pixels, wherein reconstructed residual data for estimated predictor pixels are obtained; 
     in the reconstruction means, reconstructing predictor pixels, wherein the difference between original pixels and reconstructed residual data for estimated predictor pixels is obtained; 
     in the second prediction means, in a second prediction step, predicting remaining pixels of the block from the predicted predictor pixels of at least neighbouring blocks; 
     in the second residual determining means, determining residual data for each predicted pixel resulting from the first or second prediction step, the residual data being the difference between the predicted pixel and its corresponding original pixel; and 
     in the entropy coding means, entropy encoding the residual data. 
     One advantage of the invention is that it enables faster estimation of reconstructed predictors. Another advantage is that that the encoder can perform intra prediction for all blocks of at least a portion of an image simultaneously, based on the estimated predictors, instead of relying on the reconstructed exact predictors from the conventional sequential encoding process. Thus, encoding is accelerated. 
     Advantageous embodiments of the invention are disclosed in the dependent claims, the following description and the figures. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Exemplary embodiments of the invention are described with reference to the accompanying drawings, which show in 
         FIG. 1  predictors for all 4×4 blocks in a current frame; 
         FIG. 2  predictors for neighbouring blocks in an exemplary 4×4 block; 
         FIG. 3  a 4×4 block with its boundary pixels and nine intra prediction modes (9 th  mode is DC mode, not shown); 
         FIG. 4  pixels in the first phase of the encoding procedure; 
         FIG. 5  pixels in the second phase of the encoding procedure; 
         FIG. 6  a frame that is divided into N×M portions, each of which being predicted independently; 
         FIG. 7  a flow-diagram of the encoding procedure; 
         FIG. 8  an overview of an encoder structure; and 
         FIG. 9  an overview of a decoder structure. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       FIG. 1  shows a video frame or image  100 , which is structured into blocks of 4×4 pixels each, and the predictors  110 , 120  for all 4×4 blocks in the current frame. The frame is intra-predicted, i.e. all prediction is done from other pixel data of the same frame. The predictors  110 , 120  for all 4×4 blocks in the current coding frame are the lower and right edges of each 4×4 block (only if the edge has a neighbour block), and are shown shaded. 
     In more detail, four 4×4 blocks B 0 -B 3  and B 0 &#39;s neighbouring pixels X,A-L in the original frame are shown in  FIG. 2 . To make conventional intra prediction to all 4×4 blocks in the current coding frame, reconstructed predictors are required. That is, in a conventional encoder right edge pixels d,h,l,p of a current block B 0  are predicted, reconstructed and then used to predict pixels of a horizontally adjacent block B 1 . Lower edge pixels m,n,o,p of a current block B 0  in a conventional encoder are predicted, reconstructed and then used to predict pixels of a vertically adjacent block B 2 . In the AVC coding standard, the predictors are reconstructed and usable not before the macroblocks (MBs) located in the top and left have been reconstructed. According to the present invention, the reconstructed predictors are generated by estimation before actually coding the MBs, i.e. fast approximation of the reconstructed predictors is possible as a separate step. This has the advantage that all predictors are available simultaneously before actually encoding the image. Therefore the actual intra-prediction, which also takes a long time, can be made for some or all blocks of at least a portion of the image, or the complete image, simultaneously. 
     Instead of using the reconstructed predictors to perform intra prediction, the invention uses the neighbouring pixels in the original frame to make the prediction directly. Then, e.g. for block B 0  in  FIG. 2 , the prediction is directly done using original pixels X, A, . . . , L and using a spatial prediction mode (e.g. one of the nine spatial prediction modes of AVC). This generates a predicted block per spatial prediction mode. For the AVC example, there are nine candidate predicted blocks B 01 , B 02 , . . . , B 09  possible, according to the nine prediction modes shown in  FIG. 3 . In one embodiment, more than one prediction mode is checked, and the best mode to perform the prediction is determined by selecting the one with optimal rate-distortion.
 
mode= i ,( i =min(error_func( B   0 - B   0i )))  (Eq. 1)
 
     error_func is an error measuring method. It can in principle be any known error measuring method (sum-of-absolute-differences SAD, sum-of-absolute-transformed-differences SATD, mean-square-error MSE, etc.). 
     For the predictor pixels m,n,o,p,d,h,l in a current block B 0 , its reconstruction can be estimated according to the best prediction mode and selected or given quantization parameters (QP). Taking a pixel m as an example, the estimation reconstruction m′ is calculated as follows:
 
 m′=m−Q   −1 ( Q ( m - m   p ), QP ), QP )  (Eq. 2)
 
     where Q(A, QP) means the quantization of a value A using a quantization parameter QP, and Q −1 (A, QP) means the inverse quantization of a value A using the quantization parameter QP, and m p  means the prediction value of m using the best prediction mode. 
     In this way, in one embodiment, all the predictors for the blocks are estimated. The predictors are the edge pixels of two edges of each block. Note that this need not necessarily be the lower and right edges of a block: it depends on the possible prediction direction. Using lower and right edge pixels of a block is suitable for left-to-right and up-to-down prediction directions, e.g. line-wise or column-wise. 
     In the next step, all chosen best prediction modes for each block and the estimated predictors are used to perform intra prediction for all 4×4 blocks (of at least a portion of the image) simultaneously. That is, the intra prediction within the encoding process is based not on reconstructed pixels, but on estimated reconstructed pixels that are obtained from the original pixels. This simplifies the encoding process and encoder, and accelerates it. 
     In one embodiment, all possible prediction modes are checked in order to decide the best prediction mode. 
     However, the complexity of this approach can be reduced. In block B 0 , the pixels m,n,o,p,d,h and l that shall be used as estimated predictors are relatively far away from their own predictor pixels X, A, B, . . . , L. Therefore, the mode selection can be simplified by using only major prediction directions to perform a prediction specifically for m,n,o,p,d,h and l to make the below-described estimation. In the simplified mode selection, only the DC mode, vertical intra-prediction mode and horizontal intra-prediction mode are used to estimate m,n,o,p,d,h and l. Then, the prediction error ERROR DC , ERROR ver  and ERROR hor  between these pixels and the estimated pixels is calculated. The ERROR function can be any known error measurement function (SAD, SATD, MSE, etc.) Choose the smallest ERROR from all major directions to estimate the reconstructed predictors, using equation (2). 
     For the intra-prediction of remaining pixels of a block, the estimated predictors are used to perform intra prediction based on all allowed prediction modes. For example, the nine above-shown intra-prediction modes of AVC can be used. Note that the intra prediction modes, and corresponding mode selection, for estimating the predictors are in principle independent from the intra prediction modes, and corresponding mode selection, for the actual intra-prediction of all the pixels. Then, all 4×4 blocks can be predicted simultaneously, using the estimated predictors. 
     In the following, the encoding process is described in more detail. The encoding is a process that has two phases. 
     The first phase of the encoding procedure is shown in  FIG. 4 . In a first step, lower-edge pixels m 0 ,n 0 ,o 0 ,p 0  and right-edge pixels d 0 ,h 0 ,l 0 ,p 0  of each block are predicted from pixels of neighbouring blocks of the original image A-L. Edge pixels of the leftmost or uppermost blocks can be predicted using the same modes as for conventional intra-coding, e.g. DC mode, since these blocks have no left or upper neighbours. At the end of the first phase, as shown in  FIG. 4   b ), all predictors of all blocks (of at least that portion of the image to which accelerated intra-prediction is applied) are estimated. Thus, each block has estimated predictors in neighbouring blocks in two directions available (left and upper direction in  FIG. 4 ), before any block is actually encoded. This is possible because the estimated predictors are predicted from pixels of the original image. 
     In a second step, which may be considered as part of the first phase or the second phase or as separate intermediate phase, the residuals between the estimated predictors and their original pixels are determined, e.g. m-m p , n-n p  etc. These residuals are then quantized and inverse quantized, in order to make them more similar to the predictors that will be available at the decoder. This results in reconstructed predictor residuals for all blocks (in the concerned portion of the image), according to 
     Q −1 (Q(m-m p ),QP)/QP), Q −1 (Q(n-n p ), QP) QP) etc. 
     The actual estimated predictors m′, n′, . . . for each of these blocks are then calculated according to eq. 2. 
     At the end of the first phase and after the quantization and inverse quantization, all predictors of all blocks (of at least that portion of the image to which accelerated intra-prediction is applied) are estimated. Thus, each block has estimated predictors in two neighbouring blocks, as shown in  FIG. 4   b ). Accelerated intra-prediction can be applied to one or more portions of an image simultaneously. Other portions may use other, e.g. conventional, intra prediction. For example, conventional intra prediction may be applied in a region-of-interest (ROI), while accelerated intra prediction according to the invention is used in remaining portions of the image. 
     The second phase of the encoding process is shown in  FIG. 5 . It comprises prediction and reconstruction of remaining pixels, i.e. other than predictor pixels, based on the predictor pixels that result from the first phase. In step  3 , pixels a 3 , b 3 , . . . , k 3  of a block B 3  are predicted using intra-prediction, which uses the actual estimated predictor pixels of neighbouring blocks B 0 , B 1  and B 2 . In detail, the following estimated predictors are used: p′ 0  from upper left adjacent (i.e. neighbouring) block B 0 , lower edge pixels m′ 1 -p′ 1  from upper adjacent block B 1 , and right-edge pixels d′ 2 ,h′ 2 ,l′ 2 ,p′ 2  from left adjacent block B 2 . In another embodiment, any combination of upper edge, lower edge, left edge and right edge pixels of adjacent blocks can be used as predictors, depending on the prediction direction. 
     In step  4 , shown in  FIG. 5 , the predicted remaining pixels a 3 , b 3 , . . . , k 3  of a block B 3  and the original pixels A 3 , B 3 , . . . , K 3  of said block are used to determine prediction residuals A 3,res , B 3,res , . . . , K 3,res  of said block. The prediction residuals are then entropy-encoded, as usual. 
     Since the estimated predictors are slightly different from the exact predictors that would be used by conventional sequential intra-prediction, the encoded image data resulting from the two methods are slightly different. In other words, encoder and decoder do not use exactly the same predictors, since an encoder uses the estimated predictors and a decoder uses conventionally reconstructed predictors. However, the different predictors of encoder and decoder are so similar that the difference is not visible in the image. It has been found that the simplified prediction based on estimated predictors, as employed by the invention, is not only faster and less computational expensive, but also in terms of quality yields much better results than could be expected. 
     Embodiments of the present invention comprise at least the following: 
     In one embodiment, a method for encoding image data, the image data being structured in blocks, comprises for each block in at least a portion of the image the steps of predicting the pixels of two edges of a block in a first prediction step, wherein the prediction is based on pixels of neighbouring blocks from the original image, and wherein estimated predictor pixels are obtained; 
     determining residual data for the estimated predictor pixels; 
     performing quantization and inverse quantization on the determined residual data for the estimated predictor pixels, wherein reconstructed residual data for estimated predictor pixels are obtained, according to Q −1 (Q(m-m p ),QP),QP); 
     reconstructing predictor pixels, wherein the difference between original pixels and reconstructed residual data for estimated predictor pixels is obtained, according to m′=m−Q −1 (Q(m-m p ),QP),QP); 
     in a second prediction step, predicting remaining pixels of the block from the predicted predictor pixels of at least neighbouring blocks; 
     determining residual data for each predicted pixel resulting from the first or second prediction step, the residual data being the difference between the predicted pixel and its corresponding original pixel; and entropy encoding the residual data. 
     In one embodiment of the method for encoding, the second prediction step is executed in parallel for at least two blocks of the image simultaneously, and the step of determining residual data is executed in parallel for at least two blocks of the image simultaneously. This is possible because there are no dependency issues among blocks, since the original pixel values are used. 
     In one embodiment of the method for encoding, the first prediction step is executed in parallel for at least two blocks of the image simultaneously. This is possible because there are no dependency issues among blocks, since the original pixel values are used in the first prediction step. 
     In one embodiment of the method for encoding, the first prediction step further comprises determining for each of the estimated predictor pixels a best prediction mode from a given group of spatial intra prediction modes. 
     In one embodiment of the method for encoding, the given group of spatial intra prediction modes comprises DC mode, horizontal prediction mode and vertical prediction mode. In one embodiment of the method for encoding, the given group of spatial intra prediction modes consists of only DC mode, horizontal prediction and vertical prediction. 
     In one embodiment of the method for encoding, the image is structured into at least two portions, wherein the method is executed in parallel for at least two portions of the image simultaneously and independently. 
     In one embodiment of the method for encoding, the at least one portion of the image is not square, wherein if there is more than one portion, all portions have the same shape and same amount of blocks. 
     In one embodiment a method for decoding image data, the image data being structured in blocks and having at least two portions, comprises, in all portions of the image independently and simultaneously, the steps of reconstructing pixels of the blocks from received pixel data; 
     predicting pixels in the blocks from said reconstructed pixels of the block or from reconstructed pixels of neighboring blocks; and 
     reconstructing the predicted pixels based on received residual data. 
     In one embodiment, a device for encoding image data, the image data being structured in blocks, comprises first and second prediction means; first and second residual determining means; quantizer and inverse quantizer; 
     reconstruction means; and entropy coding means; 
     wherein the apparatus performs for each block in at least a portion of the image the steps of 
     in the first prediction means, predicting the pixels of two edges of a block in a first prediction step, wherein the prediction is based on pixels of neighbouring blocks from the original image, and wherein estimated predictor pixels are obtained; 
     in the residual determining means, determining residual data for the estimated predictor pixels; 
     in the quantizer and inverse quantizer, performing quantization and inverse quantization on the determined residual data for the estimated predictor pixels, wherein reconstructed residual data for estimated predictor pixels are obtained, according to Q −1 (Q(m-m p ), QP), QP), Q −1 (Q(n-n p ), . . . ; 
     in the reconstruction means, reconstructing predictor pixels m′, wherein the difference between original pixels and reconstructed residual data for estimated predictor pixels is obtained, according to m′=m−Q −1 (Q(m-m p ), QP), QP), n′= . . . ; 
     in the second prediction means, in a second prediction step, predicting remaining pixels of the block from the predicted predictor pixels of at least neighbouring blocks; 
     in the second residual determining means, determining residual data for each predicted pixel resulting from the first or second prediction step, the residual data being the difference between the predicted pixel and its corresponding original pixel; and in the entropy coding means, entropy encoding the residual data. 
     In one embodiment, the encoding device further comprises at least a second set of second prediction means and residual determining means, wherein the second prediction step is executed in parallel in the at least two second prediction means for at least two blocks of the image simultaneously, and the step of determining residual data is executed in parallel in the at least two residual prediction means for at least two blocks of the image simultaneously. 
     In one embodiment, the encoding device further comprises at least two of the first prediction means, wherein the first prediction step is executed in the at least two first prediction means in parallel for at least two blocks of the image simultaneously. 
     In one embodiment of the encoding device, the first prediction means comprises a prediction mode selector for determining for each of the estimated predictor pixels a best prediction mode from a given group of spatial intra prediction modes. 
     In one embodiment of the encoding device, the image is structured into at least two portions, and the device operates in parallel for at least two portions of the image simultaneously and independently. 
     For most of the above embodiments, the resulting data stream can be decoded conventionally. However, where the image is split into portions, it is also possible to decode each portion independently, and thus in parallel simultaneously. In one embodiment, as shown in  FIG. 9 , a device for decoding image data is concerned: The device for decoding image data, the image data being structured in blocks and having at least two independent portions, comprises decoder data receiving means DDR, decoder pixel reconstruction means DPR, and decoder pixel prediction means DPP. After receiving pixel data, prediction mode data and residual data in the decoder data receiving means DDR, the device performs in all portions of the image independently and simultaneously the following steps: in the decoder pixel reconstruction means DPR, reconstructing pixels based on received pixel data; in the decoder pixel prediction means DPP, predicting pixels in the blocks from said reconstructed pixels of the block or from reconstructed pixels of neighbouring blocks; and further in the decoder pixel reconstruction means DPR, reconstructing the predicted pixels based on reconstructed predictors and received residual data. For parallel decoding two or more sets of decoder pixel reconstruction means DPR and decoder pixel prediction means DPP may be employed in the decoder. 
     In the above illustrative embodiments, intra 4×4 prediction is used as an example. It is clear that the same mechanism can seamlessly be applied to other intra predictions, e.g. intra 16×16 prediction. Usually, the processing of a block is independent from its relative position in a MB. 
     In one embodiment of the encoding device or the decoding device, the at least one portion of the image is not square, and if there is more than one portion, all portions have the same shape and same amount of blocks. 
     Different embodiments described above can be used in combination. For example, the dividing images into more than one portion and processing the portions simultaneously has the lowest measurable impact on prediction quality. The usage of estimated predictors with limited set of prediction directions yields the highest performance improvement. Thus, it is possible to choose among different combinations of the disclosed features, depending on different requirements and conditions. 
     Further, the spirit of the idea can be extended to design an efficient loop filter implementation, where the pixel values to be filtered can be predicted using the methods described above. Also any product that uses parallel intra prediction mode decisions may use features described above. 
     It will be understood that the present invention has been described purely by way of example, and modifications of detail can be made without departing from the scope of the invention. While there has been shown, described, and pointed out fundamental novel features of the present invention as applied to preferred embodiments thereof, it will be understood that various omissions and substitutions and changes in the apparatus and method described, in the form and details of the devices disclosed, and in their operation, may be made by those skilled in the art without departing from the spirit of the present invention. Although the present invention has been disclosed with regard to AVC, one skilled in the art would recognize that the method and devices described herein may be applied to any coding standard that uses intra-prediction. It is expressly intended that all combinations of those elements that perform substantially the same function in substantially the same way to achieve the same results are within the scope of the invention. Substitutions of elements from one described embodiment to another are also intended and contemplated. 
     Each feature disclosed in the description and (where appropriate) the claims and drawings may be provided independently or in any appropriate combination. Features may, where appropriate be implemented in hardware, software, or a combination of the two. Reference numerals appearing in the claims are by way of illustration only and shall have no limiting effect on the scope of the claims.