Abstract:
The latest video-coding standards achieve higher coding efficiency than the previous video standards, while increasing the complexity and the difficulty of encoding. In a skip macroblock prediction mode some coding parameters (such as motion vectors and residual) are not coded. Selecting skip macroblock prediction mode reduces the size of the encoded bitstream while possibly deteriorating image quality. Previously the selection of the skip prediction mode is performed after motion estimation process. This invention determines whether each macroblock should be encoded in skip macroblock prediction mode before motion estimation. This invention substantially reduces computational cost with a very small deterioration in coding efficiency.

Description:
TECHNICAL FIELD OF THE INVENTION 
     The technical field of this invention is video compression, primarily to accelerate the video encoding process of H.264 video coding standard, but applicable to the encoding process of other coding standards. 
     BACKGROUND OF THE INVENTION 
     The H.264 video standard, also as known as MPEG-4 AVC, provides compression efficiency much higher than previous video coding standards, such as MPEG-2 and MPEG-4. In most video encoding algorithms, motion estimation (ME) is the most computationally expensive module. It is generally found that ME requires more than a half of the computational operations required for the whole encoding process. The H.264 video standard uses 7 types of motion search blocks (ranging from 4 by 4 to 16 by 16) and multiple reference pictures to achieve the higher compression efficiency. The MPEG-2 video standard uses only one type (16 by 16) of motion search block and a single reference picture. It is estimated that ME encoding module of the H.264 video standard requires much more computation than previous standards. Accordingly, some technique that will reduce the computation required for ME is needed. 
     In the H.264 video standard as well as many other video standards, each picture is divided into 16 by 16 pixels square partitions, called macroblocks. If inter-block prediction is allowed in the current picture, i.e. the current picture is P-picture or B-picture, each macroblock is further divided into motion search blocks whose size range from 16 by 16 pixels to 4 by 4 pixels. Each motion search block of the current picture can be predicted from the past or future reference pictures by estimating the motion between the current motion search block and the estimated block in the reference pictures. In order to choose the optimal motion vector, the cost value between the reference and the current motion search block is computed and compared. The cost value (COST block ) is usually measured by the summation of the sum of absolute error (SAE) and the cost of motion vector (MV cos ,) defined as follows: 
                 COST   block     ⁡     (     x   ,   y   ,   p   ,   N   ,   M   ,     mv   x     ,     mv   y       )       =       SAE   ⁡     (     x   ,   y   ,   p   ,   N   ,   M   ,     mv   x     ,     mv   y       )       +       MV   cost     ⁡     (     p   ,     mv   x     ,     mv   y       )                       SAE   ⁡     (     x   ,   y   ,   p   ,   N   ,   M   ,     mv   x     ,     mv   y       )       =       ∑     j   =   0       N   -   1       ⁢       ∑     i   =   0       M   -   1       ⁢              f   c     ⁡     (       x   +   i     ,     y   +   j       )       -       f   p     ⁡     (       x   +     mv   x     +     mvp   x     +   i     ,     y   +     mv   y     +     mvp   y     +   j       )                        
where: SAE( . . . ) is the sum of absolute error between the current motion search block whose top-left corner is (x,y) in the current picture and the predicted block whose top-left corner is (x+mvp x +mv x , y+mvp y +mv y ) in the reference picture; f c (x,y) is the luminance samples (x,y) in the current picture; f p (x,y) is the luminance samples (x,y) in the reference picture; mvp x , mvp y  are the horizontal and vertical motion vector predictors which can be computed from the motion vectors of neighboring motion search blocks; mv x , mv y  are the horizontal and vertical motion vectors between the current and the predicted motion search block; N and M are the horizontal and vertical dimensions of the motion search block. The motion vector cost quantity MV cost (p,mv x ,mv y ) depends on the encoder implementation.
 
     The SAE computation is performed in ME process within a macroblock with changing motion vectors, reference pictures, and motion search block size. After testing any combination of the motion search block size, the reference pictures and the motion vectors, the optimal combination is obtained by minimizing the cost value for the macroblock with the macroblock encoder quantity ME(COST MB     —     ME ). This can be computed by summing up the cost value for all the motion search block within the macroblock as in the following equation:
 
COST MB     —     ME ( x,y )=ΣCOST block ( . . . )
 
     Meanwhile, the cost value of the macroblock with skip prediction mode (COST MB_SKIP) can be computed in a similar way as follows: 
                     ⁢         COST     MB   ⁢           ⁢   _   ⁢           ⁢   SKIP       ⁡     (     x   ,   y     )       =       SAE   SKIP     ⁡     (     x   ,   y     )                         SAE   SKIP     ⁡     (     x   ,   y     )       =       ∑     j   =   0     15     ⁢       ∑     i   =   0     15     ⁢              f   c     ⁡     (       x   +   i     ,     y   +   j       )       -       f     skip   ⁢           ⁢   _   ⁢           ⁢   p       ⁡     (       x   +     mvp     skip   ⁢           ⁢   _   ⁢           ⁢   x       +   i     ,     y   +     mvp     skip   ⁢           ⁢   _   ⁢           ⁢   y       +   j       )                        
where: SAE skip (x,y) is the sum of the absolute error between the current macroblock whose top-left corner is (x,y) in the current picture and the predicted macroblock whose top-left corner is labeled x+mvp skip     —     x , y+mvp skip     —     y  in the reference picture; f skip     —     p (x,y) is the luminance samples (x,y) in the reference picture; mvp skip     —     x , and mvp skip     —     y  are the horizontal and vertical motion vector predictors which can be computed from the motion vectors of temporally or spatially neighboring macroblocks depending on the coding environment.
 
       FIG. 1  through  FIG. 3  illustrate the typical flowchart of the optimal inter-block prediction mode (ordinary ME mode or skip prediction mode) selection of macroblock encoding in the H.264 video standard.  FIG. 1  illustrates the prior art flowchart of the inter-block prediction process beginning at block  101 . In block  102  the optimal ME cost value COST MB     —     ME  is computed from ME block size and motion vector selection. In block  103  the optimal SKIP cost value COST MB     —     SKIP  is computed for the skip prediction mode. The optimal inter-block prediction mode is selected by comparing in test block  104  the optimal cost value for macroblock encoding COST MB     —     ME  to that with skip prediction mode macroblock encoding COST MB     —     SKIP . If COST MB     —     ME  is lower than COST MB     —     SKIP  then block  108  chooses the optimal set of ME block combination, reference pictures and motion vectors as the best prediction from the inter prediction of the macroblock. If COST MB     —     ME  is higher than COST MB     —     SKIP , then test block  105  is selected to determine if there is a threshold of COST MB     —     SKIP  compared to cost T. If a threshold exists test block  106  compares COST MB     —     SKIP  to cost T. If COST MB     —     SKIP  is more than threshold cost T in test block  106 , then the flow proceeds to block  108 , which chooses the optimal set of ME block combination, reference pictures and motion vectors as the best prediction from the inter prediction of the macroblock. If COST MB     —     SKIP  is less than threshold cost T in test block  106 , then block  107  chooses the skip prediction mode as the best prediction from the inter prediction of the macroblock. If no threshold T was found in test block  105 , then test block  106  is bypassed to block  107 . Block  107  selects the skip prediction mode as the best prediction from inter-prediction of the macroblock. The end block  109  completes the inter prediction mode selection for the macroblock. 
       FIG. 2  illustrates a flowchart of the method to obtain the COST MB     —     ME  from the ME block size and motion vector selection process.  FIG. 2  begins at block  200 .  FIG. 2  illustrates the process to compute the COST MB     —     ME  with the changing combinations of ME block size within a macroblock, reference pictures, and motion vectors. This process requires a large amount of computation and returns the optimal COST MB     —     ME  along with the optimal combination of ME block size, reference pictures, and motion vectors. In  FIG. 2 , the four processes are initiated, each of which involve potential multiple iterations as evidenced by re-circulate paths  216  through  219 . The initial four processes are: 
     (A) select a combination of ME block size in block  201 ; 
     (B) select one of the divided ME blocks in block  202 ; 
     (C) select a reference picture for the block Ref(Pic) and compute the motion vector predictor in block  203 ; and 
     (D) select a motion vector MV in block  204 . 
     From the four selections in blocks  201  to  204 , the data is available for step  205  to compute the cost value of COST block . 
     Test block  206  determines whether COST block  is smaller than the candidate cost. If the result is Yes, then MV, Ref(Pic) and COST block  are saved as the new candidate cost in block  207 . If the result is NO, then MV, Ref(Pic) are tested further according to the prescriptions illustrated in test blocks  208 ,  209 , and  210 . A No result in any test block  208 ,  209 , or  210  results in re-circulate via respective paths  216 ,  217 , and  218  respectively. YES results in all test blocks  208 ,  209 , and  210  allow the process to proceed without re-circulation to block  211 . Block  211  computes the MB cost value COST MB     —     ME . If COST MB     —     ME  it is smaller than the currently optional one, then block  211  qualifies it as the currently optimal MB cost value. Finally test block  212  determines if all combinations of ME block size are tested. A YES result in test block  212 , ends the algorithm steps with the completion of ME block size and motion vector selection in end block  213 . A NO result in test block  212 , initiates a major re-circulation via path  219 . From  FIG. 2 , it can be seen that the conventional process flow for ME block size and motion vector selection is a most complex algorithm. 
     In contrast to the process of  FIG. 2 , COST MB     —     SKIP  can be obtained from the skip prediction process described in  FIG. 3 . The skip prediction process initiates in block  300 . The reference picture for the macroblock RefPic skip  and MVP skip  are computed in block  301 . From the information computed in block  301 , block  302  computes the MB cost value COST MB     —     SKIP . The skip prediction computation concludes at end block  303 . 
     In some implementations, the skip prediction mode will be selected (see  107  of  FIG. 1 ) as the best inter-block prediction simply because the cost value with the skip prediction mode is the lowest. However, if the skip prediction mode is selected, it will skip coding not only the motion vector information but also the residual information. Accordingly, selecting skip prediction mode will reduce the output bit stream size, but will tend to deteriorate the image quality when compared to selecting other inter-block prediction modes if the cost values are equivalent. In order to minimize the image quality deterioration by selecting skip prediction mode, many implementations set the threshold value T to COST MB     —     SKIP  as described in test block  105  of  FIG. 1 . If T exists in the encoder and COST MB     —     SKIP  is larger than T, the optimal inter-block prediction with ME will be selected. 
     The fundamental concern here is that ME block size and motion vector selection, accomplished by the algorithm of  FIG. 2 , is a critical and time-consuming process. This makes it impractical to realize real-time encoding in most applications. Therefore, the computational reduction of ME block size and motion vector selection methodology providing high image quality and coding efficiency is desired. 
     SUMMARY OF THE INVENTION 
     The present invention describes a method for reducing the computation required for macroblock encoding (ME) in video compression by skipping redundant ME processes. 
     a) If previously encoded picture is available, obtain the prediction mode MODE ref  and the cost value COST ref  of locally the same macroblock in the previously encoded picture (i.e. spatially identical, but temporally adjacent macroblock). 
     b) Compute the cost value of the macroblock with skip prediction mode COST MB     —     SKIP  at first as described in  FIG. 3 . 
     c) If MODE ref  from step a, is not skip prediction mode, go to step f). 
     d) Compute the threshold value T EARLY     —     SKIP , defined as T EARLY     —     SKIP =K*COST ref , where K is the constant set by the encoder implementation. 
     e) Early determination: if COST MB     —     SKIP ≦T EARLY     —SKIP   , qualify skip prediction mode as the best inter-prediction mode MODE current , and go to step h). 
     f) Perform ordinary motion estimation for the macroblock and compute the optimal cost value of the macroblock COST MB     —     ME  as described in  FIG. 2 . 
     g) Ordinarily determine the best inter-prediction mode MODE current  by comparing COST MB     —     ME  with COST MB     —     SKIP  as described in  FIG. 1 . Use the threshold value for the skip prediction mode T if applicable. 
     h) Store the current optimal prediction mode MODE current  and the optimal cost value either COST MB     —     ME  or COST MB     —     SKIP  as MODE ref  and COST ref  respectively for next early qualification. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       These and other aspects of this invention are illustrated in the drawings, in which: 
         FIG. 1  illustrates the flowchart of a typical inter-prediction mode selection for a macroblock (Prior Art); 
         FIG. 2  illustrates the flowchart of motion estimation (ME) block size and motion vector selection (Prior Art); 
         FIG. 3  illustrates the flowchart for skip prediction (Prior Art); 
         FIG. 4  illustrates the flowchart of inter-prediction mode selection for a macroblock with the EarlySkip method of this invention; 
         FIG. 5  illustrates a table of statistical data used to estimate the effect of EarlySkip method; 
         FIG. 6  illustrates a table of encoding options to collect the statistical data relating to EarlySkip; 
         FIG. 7  illustrates in table form the contrasts of image quality and bit-rate data in both encoding methods, with or without EarlySkip; and 
         FIG. 8  illustrates in table form taken from encoded data files the relative image quality and bit rate effects of the EarlySkip method of encoding. 
     
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
       FIG. 4  illustrates the essential features of this invention. To clarify the descriptive text that follows it is useful to label the invented methodology as EarlySkip. This represents early qualification of skip prediction mode using its temporal coherence. The invention uses the coherence in prediction mode between the temporally neighboring macroblocks. In most video sequences, the spatially identical macroblocks in consecutive pictures tend to have the similar motion vectors. Meanwhile, the skip prediction mode tends to be selected when the macroblock has no motion or similar motion with the spatially neighboring macro-blocks. 
     If a temporary neighboring macroblock is coded with skip prediction mode, the current macroblock is also likely to be coded with skip prediction mode. Accordingly, the EarlySkip method will not be applied if the coding mode of the temporary neighboring macroblock is not skip prediction mode coding. An exception occurs when the object in the current macroblock starts to move suddenly and irregularly at the current picture. In this case, the cost value of the current macroblock with skip prediction mode COST MB     —     SKIP  should be much larger than that of the temporally neighboring macroblock COST ref . Hence, it is necessary to proceed as follows: 
     1. Compute the threshold value T EARLY     —     SKIP , defined as T EARLY     —     SKIP =K*COST ref , where K is the constant set by the encoder implementation; 
     2. Perform early determination: if COST MB     —     SKIP ≦T EARLY     —     SKIP , qualify skip prediction mode as the best inter-prediction mode MODE current , and then proceed to step 3; and 
     3. Store the current optimal prediction mode MODE current  and the optimal cost value either COST MB     —     ME  or COST MB     —     SKIP  as MODE ref  and COST ref  respectively for next early qualification. 
     Step 1 computes the threshold value for EarlySkip T EARLY     —     SKIP . Step 2 compares T EARLY     —     SKIP  to the cost value of the current macroblock with the skip prediction mode COST MB     —     SKIP . Consider the two possible results of the comparison: 
     Case A: If the cost value is larger, i.e. COST MB     —     SKIP &gt;T EARLY     —     SKIP , there will be less possibility that the skip prediction mode is selected as the best inter-block prediction mode. In case A, the ordinary ME should be performed to retain the coding efficiency. 
     Case B: If the cost value is smaller than or equal to the threshold value for EarlySkip, i.e. COST MB     —     SKIP ≦T EARLY     —     SKIP , there will be high probability that the skip prediction mode is selected as the best inter-block prediction mode at last. 
       FIG. 4  illustrates the flow chart for inter-prediction mode for a macroblock using the EarlySkip method of this invention. Block  400  begins the method. Block  401  accesses MODE ref  and COST ref  of a similar local macroblock in previously encoded picture for comparison. Block  402  computes the optimal SKIP cost value COST MB     —     SKIP . The test in test block  403  determines if MODE ref  is a skip prediction mode result. A Yes result in test block  403  begins the skip mode processing. 
     Block  404  computes the threshold value for EarlySkip T EARLY     —     SKIP . Block  405  compares this threshold value T EARLY     —     SKIP  with the cost value of the current macroblock with the skip prediction mode, i.e. is COST MB     —     SKIP &gt;T EARLY     —     SKIP ? If the cost value is smaller than or equal to the threshold (No in test block  405 ), then the process proceeds to select the skip prediction mode via path  421 . In this case there will be high probability that the skip prediction mode is the best inter-block prediction mode. In this case, the method bypasses the most computationally expensive block  406  of  FIG. 4 , which corresponds to the process  102  of  FIG. 1  and entire  FIG. 2 . This achieves significant computational reduction. 
     If the cost value is greater than the threshold COST MB     —     SKIP &gt;T EARLY     —     SKIP  (Yes at test block  405 ), then this method enters the lower portion of the flow chart of  FIG. 4 . This corresponds to blocks  102  and  104  through  109  of  FIG. 1 . 
     Block  406  computes COST MB     —     ME , which corresponds to block  102  of  FIG. 1 . Test block  414  determines the relative cost COST MB     —     ME &lt;COST MB     —     SKIP . If COST MB     —     ME ≧COST MB     —     SKIP  (No at test block  414 ), then test block  415  evaluates if there is a threshold of COST MB     —     SKIP  compared to cost T. If a threshold exists (YES at test block  415 ), then test block  416  evaluates COST ME     —     ME &lt;T? If no threshold T was found in test block  415  (NO at test block  415 ), then test block  416  is bypassed to block  417 . 
     If COST MB     —     SKIP ≧T (NO in test block  416 ), then selection routes to block  418 . Block  418  chooses the optimal set of ME block combination with reference pictures and motion vectors as the best prediction from the inter prediction of the macroblock. If COST MB     —     SKIP &lt;T (YES in test block  416 ), then block  417  chooses the skip prediction mode as the best prediction from the inter-prediction of the macroblock. Block  419  stores for purposes of later processing (block  401 ) the optimal prediction mode and cost values MODE ref  and COST ref  of the current block. End block  420  completes the inter prediction mode selection for the macroblock. 
       FIG. 5  illustrates statistical evidence of the effectiveness of the EarlySkip method.  FIG. 6  illustrates the coding options used in the various video sequences according to the ordinary inter-prediction process described in  FIG. 1  (i.e. EarlySkip method is not applied) for the data presented in  FIG. 5 . For 21 images listed by file name,  FIG. 5  illustrates the number of skipped macroblocks satisfying the condition COST MB     —     SKIP ≦T EARLY     —     SKIP , the number of total P-macroblocks satisfying the condition COST MB     —     SKIP ≦T EARLY     —     SKIP  and the total number of P-macroblocks where the parameter K=1 that is, T EARLY     —     SKIP =COST ref , were counted. The number of P-macroblocks satisfying the condition equals to the number of P-macroblocks for which EarlySkip method is applied. Hence, the accuracy of EarlySkip method can be computed by dividing the number of skipped macroblocks satisfying the condition by the number of P-macroblocks satisfying the condition as shown in  FIG. 5 . Meanwhile, the rate that EarlySkip method is applied for a P-macroblock is computed by dividing the number of P-macroblocks satisfying the condition by the number of total P-macroblocks as also shown in  FIG. 5 . 
     The EarlySkip method has an accuracy over 80% in most cases. The only exception is bicycle.yuv. This image has an accuracy of 67.3%. For this image, the EarlySkip applicable rate is only 0.8%. This means that the EarlySkip method will not help much to reduce the required computation for ME in that case, but neither it will appreciably deteriorate the image quality. It is expected that the deterioration of image quality will be the primary disadvantage of the EarlySkip method. This will be considered further below. The EarlySkip method of this invention will reduce the computation required for ME of a macroblock with the possibility of an EarlySkip applicable rate ranging from 0.8% to 56.6% as shown in  FIG. 5  for the example images. The accuracy of EarlySkip method is over 97% when the EarlySkip applicable rate is over 15%. 
     This invention will reduce the computation required for ME with a certain probability as described earlier in the text. This invention has possible negative effects, which may result from application of the methodology. 
       FIG. 7  illustrates a list of encoded image quality and bit-rate resulting in two cases: with or without EarlySkip method. Various video sequences were encoded with the coding options presented in  FIG. 6  with or without applying the EarlySkip method.  FIG. 8  illustrates the effect of EarlySkip method as the difference of image quality and bit-rate with and without the method is described in the table. According to  FIG. 8 , the worst case for EarlySkip method is when football.yuv is encoded because image quality of the luma component deteriorates by 0.21 (dB). However, the image quality deterioration due to the EarlySkip method is around 0.2 (dB) even in the worst case and 0.05 (dB) on average. This is quite small when compared to the benefit received. In some cases such as akiyo_qcif.yuv, the image quality even improves. The EarlySkip method reduces the bit-rate of encoded bit-stream by about 0.72% on average because some macroblocks are skipped extra due to the inaccuracy of the method. 
     In conclusion, both the positive and the negative effects of the invention are listed as follows: 
     (A) The amount of computation required for ME is reduced by 0.8% to 56.6% (about 17.0% on average); 
     (B) The image quality (luma component) deteriorates by 0.05 dB on average and 0.21 dB at worst for these examples; and 
     C) The bit-rate of encoded stream is reduced by 0.72% on average.