Motion estimation technique for digital video encoding applications

Abstract

The present invention provides an improved motion estimation encoder for digital video encoding applications. In one example embodiment, the improved encoder receives a raw image in the form of a current frame and estimates the macroblock motion vector with respect to a reference frame. The encoder then performs an initial local search around an initial motion vector candidate derived from spatio-temporal neighboring macroblock parameters. The encoder then compares the user-defined complexity scalable sum of absolute difference between the original and the associated reference macroblock against an adaptive threshold value for motion estimation convergence. The encoder introduces a global full search around a candidate from a coarser level, in case an initial local search fails. The encoder then selects an inter encoding mode for coding the current macroblock, when the first local search is successful, otherwise the encoder selects the inter or intra encoding mode for encoding the current macroblock by comparing variances of the original and difference macroblocks.

The invention claimed is: 
     
       1. A computer system for performing a frame-to-frame digital video encoding, comprising:
 a processor; 
 an output device; and 
 a storage device to store instructions that are executable by the processor to perform the frame-to-frame digital video encoding, comprising:
 partitioning a current frame into non-overlapping macroblocks; 
 computing a motion estimation termination threshold for a current macroblock using macroblock parameters; 
 selecting an initial motion vector for the current macroblock using spatio-temporal neighboring macroblock parameters; 
 determining an initial distortion for the current macroblock by computing a sum of absolute difference using the selected initial motion vector and the associated reference macroblocks; 
 comparing the computed initial distortion to the computed motion estimation termination threshold; and 
 encoding the current macroblock based on the outcome of the comparison. 
 
 
     
     
       2. The system of  claim 1 , wherein encoding the current macroblock based on the outcome of the comparison, comprises:
 if the computed initial distortion is less than the computed motion estimation termination threshold, then selecting the inter coding mode for encoding the current macroblock and choosing the selected initial motion vector as the representative motion vector for the current macroblock; 
 if the computed initial distortion is greater than or equal to the computed motion estimation termination threshold, then computing the sum of absolute difference values at each of the equidistant motion vector positions from the initial motion vector; 
 determining a minimum sum of absolute difference value from the computed sum of absolute difference values; and 
 comparing the determined minimum sum of absolute difference value to the motion estimation termination threshold and encoding the current macroblock based on the outcome of the comparison. 
 
     
     
       3. The system of  claim 2 , wherein comparing the determined minimum sum of absolute difference value to the motion estimation termination threshold further comprises:
 if the determined minimum sum of absolute difference value is less than the motion estimation termination threshold, then selecting the inter coding mode for encoding the current macroblock and choosing the motion vector associated with the minimum sum of absolute difference as the representative motion vector; 
 if the determined minimum sum of absolute difference value is greater than or equal to the motion estimation termination threshold, then repeating the above steps for a predetermined number of times using the motion vector associated with the minimum sum of absolute difference as the initial motion vector; 
 if after repeating the above steps for the predetermined number of times, the determined minimum sum of absolute difference value does not yield a value less than the motion estimation termination threshold, then doing a global full search to determine the motion vector based on the lowest sum of absolute difference value obtained; 
 computing a block variance of the current macroblock and a block variance of the difference macroblock; 
 comparing the computed variance of the current macroblock value with the variance of the difference macroblock value; and 
 selecting inter or intra coding for encoding the current macroblock and choosing the motion vector associated with the minimum sum of absolute difference from full search as the representative motion vector based on the outcome of the comparison. 
 
     
     
       4. The system of  claim 3 , wherein computing an initial motion vector for the current macroblock using spatio-temporal neighboring macroblock parameters further comprises:
 adopting a predefined voting technique to select the initial motion vector from spatio-temporal neighboring macroblock's motion vectors. 
 
     
     
       5. The system of  claim 3 , wherein computing the motion estimation termination threshold for the current macroblock in a current frame using macroblock parameters comprises:
 computing the motion estimation termination threshold for the current macroblock using the equation: 
 
       
         
           
             
               sqrt 
               ⁡ 
               
                 ( 
                 
                   
                     
                       ∑ 
                       
                         I 
                         = 
                         0 
                       
                       255 
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           
                             x 
                             I 
                           
                           - 
                           μ 
                         
                         ) 
                       
                       2 
                     
                   
                   + 
                   
                     2 
                     * 
                     255 
                     * 
                     128 
                     * 
                     
                       
                         ( 
                         
                           x 
                           avg 
                         
                         ) 
                       
                       2 
                     
                   
                 
                 ) 
               
             
           
         
         wherein x I 's are luminance components of the current macroblock, x avg  is the allowed average absolute pixel-difference for an optimal prediction, and μ is the mean of x I  where I=0 to 255. 
       
     
     
       6. The system of  claim 3 , wherein computing the sum of absolute difference between the current and reference macroblocks is based on using the equation: 
       
         
           
             
               
                 ∑ 
                 
                   I 
                   = 
                   0 
                 
                 255 
               
               ⁢ 
               
                  
                 
                   
                     x 
                     I 
                   
                   - 
                   
                     y 
                     I 
                   
                 
                  
               
             
           
         
         wherein x I 's are luminance components of the current macroblock and y I 's are luminance components of the reference macroblock. 
       
     
     
       7. The system of  claim 3 , wherein comparing the block variance of current macroblock with the block variance of difference macroblock is based on using the equations: 
       
         
           
             
               
                 
                   ∑ 
                   
                     I 
                     = 
                     0 
                   
                   255 
                 
                 ⁢ 
                 
                   
                     ( 
                     
                       
                         x 
                         I 
                       
                       - 
                       
                         y 
                         I 
                       
                     
                     ) 
                   
                   2 
                 
               
               < 
               
                 
                   ∑ 
                   
                     I 
                     = 
                     0 
                   
                   255 
                 
                 ⁢ 
                 
                   
                     
                       ( 
                       
                         
                           x 
                           I 
                         
                         - 
                         μ 
                       
                       ) 
                     
                     2 
                   
                   .