Abstract:
An embodiment is directed to a method for selecting a predictive macroblock partition from a plurality of candidate macroblock partitions in motion estimation and compensation in a video encoder including determining a bit rate signal for each of the candidate macroblock partitions, generating a distortion signal for each of the candidate macroblock partitions, calculating a cost for each of the candidate macroblock partitions based on respective bit rate and distortion signals to produce a plurality of costs, and determining a motion vector from the costs. The motion vector designates the predictive macroblock partition.

Description:
BACKGROUND 
     1. Field 
     The present application relates to video encoders and cost functions employed therein. 
     2. Background 
     Video compression involves compression of digital video data. Video compression is used for efficient coding of video data in video file formats and streaming video formats. Compression is a reversible conversion of data to a format with fewer bits, usually performed so that the data can be stored or transmitted more efficiently. If the inverse of the process, decompression, produces an exact replica of the original data then the compression is lossless. Lossy compression, usually applied to image data, does not allow reproduction of an exact replica of the original image, but it is more efficient. While lossless video compression is possible, in practice it is virtually never used. Standard video data rate reduction involves discarding data. 
     Video is basically a three-dimensional array of color pixels. Two dimensions serve as spatial (horizontal and vertical) directions of the moving pictures, and one dimension represents the time domain. 
     A frame is a set of all pixels that (approximately) correspond to a single point in time. Basically, a frame is the same as a still picture. However, in interlaced video, the set of horizontal lines with even numbers and the set with odd numbers are grouped together in fields. The term “picture” can refer to a frame or a field. 
     Video data contains spatial and temporal redundancy. Similarities can thus be encoded by merely registering differences within a frame (spatial) and/or between frames (temporal). Spatial encoding is performed by taking advantage of the fact that the human eye is unable to distinguish small differences in color as easily as it can changes in brightness, and so very similar areas of color can be “averaged out.” With temporal compression, only the changes from one frame to the next are encoded because a large number of the pixels will often be the same on a series of frames. 
     Video compression typically reduces this redundancy using lossy compression. Usually this is achieved by (a) image compression techniques to reduce spatial redundancy from frames (this is known as intraframe compression or spatial compression) and (b) motion compensation and other techniques to reduce temporal redundancy (known as interframe compression or temporal compression). 
     H.264/AVC is a video compression standard resulting from joint efforts of ISO (International Standards Organization) and ITU (International Telecommunication Union.)  FIG. 1  shows a block diagram for an H.264/AVC encoder. An input video frame  102  is divided into macroblocks  104  and fed into system  100 . For each macroblock  104 , a predictor  132  is generated and subtracted (as shown by reference numeral  106  of  FIG. 1 ) from the original macroblock  104  to generate a residual  107 . This residual  107  is then transformed  108  and quantized  110 . The quantized macroblock is then entropy coded  112  to generate a compressed bitstream  113 . The quantized macroblock is also inverse-quantized  114 , inverse-transformed  116  and added back to the predictor by adder  118 . The reconstructed macroblock is filtered on the macroblock edges with a deblocking filter  120  and then stored in memory  122 . 
     Quantization, in principle, involves reducing the dynamic range of the signal. This impacts the number of bits (rate) generated by entropy coding. This also introduces loss in the residual, which causes the original and reconstructed macroblock to differ. This loss is normally referred to as quantization error (distortion). The strength of quantization is determined by a quantization factor parameter. The higher the quantization parameter, the higher the distortion and lower the rate. 
     As discussed above, the predictor can be of two types—intra  128  and inter  130 . Spatial estimation  124  looks at the neighboring macroblocks in a frame to generate the intra predictor  128  from among multiple choices. Motion estimation  126  looks at the previous/future frames to generate the inter predictor  130  from among multiple choices. Inter predictor aims to reduce temporal redundancy. Typically, reducing temporal redundancy has the biggest impact on reducing rate. 
     Motion estimation may be one of the most computationally expensive blocks in the encoder because of the huge number of potential predictors it has to choose from. Practically, motion estimation involves searching for the inter predictor in a search area comprising a subset of the previous frames. Potential predictors or candidates from the search area are examined on the basis of a cost function or metric. Once the metric is calculated for all the candidates in the search area, the candidate that minimizes the metric is chosen as the inter predictor. Hence, the main factors affecting motion estimation are: search area size, search methodology, and cost function. 
     Focusing particularly on cost function, a cost function essentially quantifies the redundancy between the original block of the current frame and a candidate block of the search area. The redundancy should ideally be quantified in terms of accurate rate and distortion. 
     The cost function employed in current motion estimators is Sum-of-Absolute-Difference (SAD).  FIG. 2  shows how SAD is calculated. Frame(t)  206  is the current frame containing a macroblock  208  which is stored in Encode MB (MACROBLOCK) RAM  212 . Frame(t−1)  202  is the previous frame containing a search area  204  which is stored in Search RAM  210 . It is appreciated that more than one previous frame can be used. 
     In the example in  FIG. 2 , the search area  204  size is M×N. Let the size of the blocks being considered be A×B, where A and B are defined in Table 1. Let the given block  208  from the current frame  206  be denoted as c  215 . Let each candidate from the search area  204  be denoted as p(x,y)  214 , where xε[0,N] and yε[0,M]. (x,y) represents a position in the search area  214 . 
     
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Notations for e(x, y) for different block shapes 
               
             
          
           
               
                 A 
                 B 
                 
                   
                     
                       
                         
                           z 
                           ⁢ 
                           ε 
                         
                         ⁡ 
                         
                           [ 
                           
                             0 
                             , 
                             
                               
                                 
                                   A 
                                   × 
                                   B 
                                 
                                 16 
                               
                               - 
                               1 
                             
                           
                           ] 
                         
                       
                     
                   
                 
                 Notation 
               
               
                   
               
               
                  4 
                  4 
                 zε[0, 0] 
                 e(x, y) = [e(x, y, 0)] 
               
               
                  8 
                  4 
                 zε[0, 1] 
                 e(x, y) = [e(x, y, 0) e(x, y, 1)] 
               
               
                   
               
               
                  4 
                  8 
                 zε[0, 1] 
                 
                   
                     
                       
                         
                           e 
                           ⁡ 
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       0 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                   
               
               
                  8 
                  8 
                 zε[0, 3] 
                 
                   
                     
                       
                         
                           e 
                           ⁡ 
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       0 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       2 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       3 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                   
               
               
                 16 
                  8 
                 zε[0, 7] 
                 
                   
                     
                       
                         
                           e 
                           ⁡ 
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       0 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       2 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       3 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       4 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       5 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       6 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       7 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                   
               
               
                  8 
                 16 
                 zε[0, 7] 
                 
                   
                     
                       
                         
                           e 
                           ⁡ 
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       0 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       2 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       3 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       4 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       5 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       6 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       7 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                   
               
               
                 16 
                 16 
                 zε[0, 15] 
                 
                   
                     
                       
                         
                           e 
                           ⁡ 
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       0 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       2 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       3 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       4 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       5 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       6 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       7 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       8 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       9 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       10 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       11 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       12 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       13 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       14 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       15 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                   
               
             
          
         
       
     
     The following steps are calculated to get a motion vector (X,Y): 
     c is motion compensated  216  for by p(x,y)  214  to get a residual error signal  218 , e(x,y)
 
 e ( x,y )= p ( x,y )− c   (1)
 
SAD  222  is then calculated  220  from e(x,y).
 
                     SAD   ⁡     (     x   ,   y     )       =         ∑     i   ,   j       ⁢            e   ⁡     (     x   ,   y     )            ⁢           ⁢   where   ⁢           ⁢   i       ∈       [     0   ,   A     ]     ⁢           ⁢   and   ⁢           ⁢   j     ∈     [     0   ,   B     ]               (   2   )               
The motion vector (X,Y) is then calculated from SAD(x,y).
 
( X,Y )=( x,y )|min SAD( x,y )  (3)
 
     Ideally, the predictor macroblock partition should be the macroblock partition that most closely resembles the macroblock. One of the drawbacks of SAD is that it does not specifically and accurately account for Rate and Distortion. Hence the redundancy is not quantified accurately, and therefore it is possible that the predictive macroblock partition chosen is not the most efficient choice. Thus, in some cases utilizing a SAD approach may actually result in less than optimal performance. 
     SUMMARY 
     One embodiment relates to a method for selecting a predictive macroblock partition in motion estimation and compensation in a video encoder including determining a bit rate signal, generating a distortion signal, calculating a cost based on the bit rate signal and the distortion signal, and determining a motion vector from the cost. The motion vector designates the predictive macroblock partition. The method may be implemented in a mobile device such as a mobile phone, digital organizer or lap top computer. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a block diagram of an H.264/AVC video encoder. 
         FIG. 2  shows a block diagram of the sum of absolute difference cost function as employed in a standard video encoder. 
         FIG. 3  shows a block diagram of the theoretically optimal solution Rate-Distortion-optimized cost function for a video encoder. 
         FIG. 4  shows a block diagram of a Rate-Distortion-optimized cost function for a video encoder. 
         FIG. 5  shows a first graphical illustration of the performance of a video encoder using the sum of absolute difference cost function as compared to a video encoder using a cost function. 
         FIG. 6  shows a second graphical illustration of the performance of a video encoder using the sum of absolute difference cost function as compared to a video encoder using a cost function 
     
    
    
     DETAILED DESCRIPTION 
     Reference will now be made in detail to some embodiments, examples of which are illustrated in the accompanying drawings. It will be understood that the embodiments are not intended to limit the description. On the contrary, the description is intended to cover alternatives, modifications and equivalents, which may be included within the spirit and scope of the description as defined by the claims. Furthermore, in the detailed description, numerous specific details are set forth in order to provide a thorough understanding. However, it may be obvious to one of ordinary skill in the art that the present description may be practiced without these specific details. In other instances, well known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the present description. 
     Some portions of the detailed descriptions that follow are presented in terms of procedures, logic blocks, processing, and other symbolic representations of operations on data bits within a computer or digital system memory. These descriptions and representations are means used by those skilled in the data processing arts to effectively convey the substance of their work to others skilled in the art. A procedure, logic block, process, etc., is herein, and generally, conceived to be a sequence of steps or instructions leading to a desired result. 
     Unless specifically stated otherwise as apparent from the discussion herein, it is understood that throughout discussions of the embodiments, discussions utilizing terms such as “determining” or “outputting” or “transmitting” or “recording” or “locating” or “storing” or “displaying” or “receiving” or “recognizing” or “utilizing” or “generating” or “providing” or “accessing” or “checking” or “notifying” or “delivering” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data. The data is represented as physical (electronic) quantities within the computer system&#39;s registers and memories and is transformed into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission, or display devices. 
     In general, embodiments of the description below subject candidate macroblock partitions to a series of processes that approximate the processes the macroblock partition would undergo were it actually selected as the predictive macroblock partition (see generally  FIG. 1 ). Doing so allows for accurate approximation of the rate and distortion for each candidate macroblock partition. Embodiments then employ a Lagrangian-based cost function, rather than SAD, to select the candidate macroblock partition that best minimizes costs associated with rate and distortion that occur during the encoding process. 
     An optimal solution to predictive macroblock partition selection needs to be established to understand where SAD stands and the scope of the gains possible. The optimal solution will guarantee minimum distortion (D) under a rate (R) constraint. Such a solution is found using Lagrangian-based optimization, which combines Rate and Distortion as D+λR. λ is the Lagrangian multiplier that represents the tradeoff between rate and distortion.  FIG. 3  shows a block diagram  300  of the optimal solution for an RD-optimized cost function. In order to calculate rate  332  and distortion  334  accurately, the entire encoding process should be carried out for each of the candidate blocks  304 , as shown in  FIG. 3  and described below. 
     The current frame  308  is motion compensated  310  for by the candidate macroblock partitions  304  to get a residual error signal e(x,y) as shown in (1). The current frame  308  and the candidate macroblock partitions  304  are provided from encoded MB random access memory (RAM)  306  and search RAM  302 , respectively. 
     e(x,y) is divided into an integral number of 4×4 blocks e(x,y,z)  312  where 
             z   ∈       ⌊     0   ,         A   ×   B     16     -   1       ⌋     .           
The size of e(x,y) is A×B. The values that A and B can take are shown in Table 1. Let e(x,y,z) be denoted by E.
 
     
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Notations for e(x, y) for different block shapes 
               
             
          
           
               
                 A 
                 B 
                 
                   
                     
                       
                         
                           z 
                           ⁢ 
                           ε 
                         
                         ⁡ 
                         
                           [ 
                           
                             0 
                             , 
                             
                               
                                 
                                   A 
                                   × 
                                   B 
                                 
                                 16 
                               
                               - 
                               1 
                             
                           
                           ] 
                         
                       
                     
                   
                 
                 Notation 
               
               
                   
               
               
                  4 
                  4 
                 zε[0, 0] 
                 e(x, y) = [e(x, y, 0)] 
               
               
                  8 
                  4 
                 zε[0, 1] 
                 e(x, y) = [e(x, y, 0) e(x, y, 1)] 
               
               
                   
               
               
                  4 
                  8 
                 zε[0, 1] 
                 
                   
                     
                       
                         
                           e 
                           ⁡ 
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       0 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                   
               
               
                  8 
                  8 
                 zε[0, 3] 
                 
                   
                     
                       
                         
                           e 
                           ⁡ 
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       0 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       2 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       3 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                   
               
               
                 16 
                  8 
                 zε[0, 7] 
                 
                   
                     
                       
                         
                           e 
                           ⁡ 
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       0 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       2 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       3 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       4 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       5 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       6 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       7 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                   
               
               
                  8 
                 16 
                 zε[0, 7] 
                 
                   
                     
                       
                         
                           e 
                           ⁡ 
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       0 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       2 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       3 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       4 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       5 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       6 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       7 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                   
               
               
                 16 
                 16 
                 zε[0, 15] 
                 
                   
                     
                       
                         
                           e 
                           ⁡ 
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       0 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       2 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       3 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       4 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       5 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       6 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       7 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       8 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       9 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       10 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       11 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       12 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       13 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       14 
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   e 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                       , 
                                       15 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                   
               
             
          
         
       
     
     E  312  is transformed  314  into the frequency domain from the spatial domain. Let the transformed block be denoted as t(x,y,z) or T  316 . Since the transform is separable, it is applied in two stages, horizontal (4) and vertical (5) on E  312 . E′ represents the intermediate output. D represents the transform matrix shown in (6). 
     
       
         
           
             
               
                 
                   
                     
                       
                         E 
                         ′ 
                       
                       ⁡ 
                       
                         ( 
                         
                           i 
                           , 
                           j 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           0 
                         
                         3 
                       
                       ⁢ 
                       
                         
                           E 
                           ⁡ 
                           
                             ( 
                             
                               i 
                               , 
                               k 
                             
                             ) 
                           
                         
                         × 
                         
                           D 
                           ⁡ 
                           
                             ( 
                             
                               k 
                               , 
                               j 
                             
                             ) 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         where 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         i 
                       
                     
                   
                   , 
                   
                     j 
                     ∈ 
                     
                       [ 
                       
                         0 
                         , 
                         3 
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       T 
                       ⁡ 
                       
                         ( 
                         
                           i 
                           , 
                           j 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           0 
                         
                         3 
                       
                       ⁢ 
                       
                         
                           
                             E 
                             ′ 
                           
                           ⁡ 
                           
                             ( 
                             
                               k 
                               , 
                               j 
                             
                             ) 
                           
                         
                         × 
                         
                           D 
                           ⁡ 
                           
                             ( 
                             
                               i 
                               , 
                               k 
                             
                             ) 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         where 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         i 
                       
                     
                   
                   , 
                   
                     j 
                     ∈ 
                     
                       [ 
                       
                         0 
                         , 
                         3 
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
             
               
                 
                   D 
                   = 
                   
                     ⌊ 
                     
                       
                         
                           1 
                         
                         
                           1 
                         
                         
                           1 
                         
                         
                           1 
                         
                       
                       
                         
                           2 
                         
                         
                           1 
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           
                             - 
                             2 
                           
                         
                       
                       
                         
                           1 
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           1 
                         
                       
                       
                         
                           1 
                         
                         
                           
                             - 
                             2 
                           
                         
                         
                           2 
                         
                         
                           
                             - 
                             1 
                           
                         
                       
                     
                     ⌋ 
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     T  316  is quantized  318  with a quantization parameter Q, which is predetermined. Let the quantization block be denoted by l(x,y,z) or L  320 . 
                         L   ⁡     (     i   ,   j     )       =     (         T   ⁡     (     i   ,   j     )       ×     M   ⁡     (     i   ,   j     )         +   R     )       &gt;&gt;     S   ⁢           ⁢   where   ⁢           ⁢   i       ,     j   ∈     [     0   ,   3     ]               (   7   )               M   =     ⌊         f       g       f       g           g       h       g       h           f       g       f       g           g       h       g       h         ⌋             (   8   )               S   =     15   +     Q   6               (   9   )               R   =       2   s     3             (   10   )               
The values for the elements of M are derived from a table known in the art. A sample of the table is shown in Table 2.
 
     
       
         
               
             
               
               
               
               
               
             
               
               
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 Values for Multiplication Factor (M) for H.264 Quantization 
               
             
          
           
               
                   
                 Q %6 
                 f 
                 g 
                 h 
               
               
                   
                   
               
             
          
           
               
                   
                 0 
                 13107 
                 8066 
                 5243 
               
               
                   
                 1 
                 11916 
                 7490 
                 4660 
               
               
                   
                 2 
                 10082 
                 6554 
                 4194 
               
               
                   
                 3 
                 9362 
                 5825 
                 3647 
               
               
                   
                 4 
                 8192 
                 5243 
                 3355 
               
               
                   
                 5 
                 7282 
                 4559 
                 2893 
               
               
                   
                   
               
             
          
         
       
     
     Next, L  320  is entropy coded  328  using a context-adaptive variable length coding (CAVLC) scheme. This generates the number of bits taken to represent l(x,y,z), which is denoted as Rate(x,y,z,Q) or Rate(Q)  332 .
 
Rate( x,y,z,Q )=CAVLC( l ( x,y,z,Q ))  (11)
 
It should be appreciated by one skilled in the art that CAVLC is known in the art and that another entropy coding algorithm may be used in its place.
 
     L  320  is inverse quantized  322  with quantization parameter Q. Let the inverse quantized block be denoted by {circumflex over (l)}(x,y,z) or {circumflex over (L)}  324 . 
                         L   ^     ⁡     (     i   ,   j     )       =       (       L   ⁡     (     i   ,   j     )       ×       M   ^     ⁡     (     i   ,   j     )         )     ⁢     &lt;&lt;   S     ⁢           ⁢   where   ⁢           ⁢   i       ,     j   ∈     [     0   ,   3     ]               (   12   )                 M   ^     =     ⌊           f   ^           g   ^           f   ^           g   ^               g   ^           h   ^           g   ^           h   ^               f   ^           g   ^           f   ^           g   ^               g   ^           h   ^           g   ^           h   ^           ⌋             (   13   )               
The values for the elements of {circumflex over (M)} are derived from a table known in the art. A sample of the table is shown in Table 3.
 
     
       
         
               
             
               
               
               
               
               
             
           
               
                 TABLE 3 
               
             
             
               
                   
               
               
                 Values for Multiplication Factor ({circumflex over (M)}) for H.264 Inverse Quantization 
               
             
          
           
               
                   
                 Q %6 
                 {circumflex over (f)} 
                 ĝ 
                 ĥ 
               
               
                   
                   
               
               
                   
                 0 
                 10 
                 13 
                 16 
               
               
                   
                 1 
                 11 
                 14 
                 18 
               
               
                   
                 2 
                 13 
                 16 
                 20 
               
               
                   
                 3 
                 14 
                 18 
                 23 
               
               
                   
                 4 
                 16 
                 20 
                 25 
               
               
                   
                 5 
                 18 
                 23 
                 29 
               
               
                   
                   
               
             
          
         
       
     
     {circumflex over (L)} is transformed from the frequency domain to the spatial domain  326 . Let the transformed block be denoted by ê(x,y,z,Q) or Ê  329 . Since the transform is separable, it is applied in two stages, horizontal (14) and vertical (15), on {circumflex over (L)}. L′ represented the intermediate output. {circumflex over (D)} represents the transform matrix shown in (16). 
     
       
         
           
             
               
                 
                   
                     
                       
                         L 
                         ′ 
                       
                       ⁡ 
                       
                         ( 
                         
                           i 
                           , 
                           j 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           0 
                         
                         3 
                       
                       ⁢ 
                       
                         
                           
                             L 
                             ^ 
                           
                           ⁡ 
                           
                             ( 
                             
                               i 
                               , 
                               k 
                             
                             ) 
                           
                         
                         × 
                         
                           
                             D 
                             ^ 
                           
                           ⁡ 
                           
                             ( 
                             
                               k 
                               , 
                               j 
                             
                             ) 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         where 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         i 
                       
                     
                   
                   , 
                   
                     j 
                     ∈ 
                     
                       [ 
                       
                         0 
                         , 
                         3 
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         E 
                         ^ 
                       
                       ⁡ 
                       
                         ( 
                         
                           i 
                           , 
                           j 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           0 
                         
                         3 
                       
                       ⁢ 
                       
                         
                           
                             L 
                             ′ 
                           
                           ⁡ 
                           
                             ( 
                             
                               k 
                               , 
                               j 
                             
                             ) 
                           
                         
                         × 
                         
                           
                             D 
                             ^ 
                           
                           ⁡ 
                           
                             ( 
                             
                               i 
                               , 
                               k 
                             
                             ) 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         where 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         i 
                       
                     
                   
                   , 
                   
                     j 
                     ∈ 
                     
                       [ 
                       
                         0 
                         , 
                         3 
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
             
               
                 
                   
                     D 
                     ^ 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           1 
                         
                         
                           1 
                         
                         
                           1 
                         
                         
                           1 
                         
                       
                       
                         
                           1 
                         
                         
                           
                             1 
                             / 
                             2 
                           
                         
                         
                           
                             
                               - 
                               1 
                             
                             / 
                             2 
                           
                         
                         
                           
                             - 
                             1 
                           
                         
                       
                       
                         
                           1 
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           1 
                         
                       
                       
                         
                           
                             1 
                             / 
                             2 
                           
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           1 
                         
                         
                           
                             
                               - 
                               1 
                             
                             / 
                             2 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
     The squared-error between Ê and E (as shown by sum of squared difference  330 ) represents the Distortion  334 , Distortion(x,y,z,Q) or Distortion(Q). 
     
       
         
           
             
               
                 
                   
                     
                       Distortion 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         
                           x 
                           , 
                           y 
                           , 
                           z 
                           , 
                           Q 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           , 
                           j 
                         
                       
                       ⁢ 
                       
                         
                           ( 
                           
                             
                               E 
                               ⁡ 
                               
                                 ( 
                                 
                                   i 
                                   , 
                                   j 
                                 
                                 ) 
                               
                             
                             - 
                             
                               E 
                               ⁡ 
                               
                                 ( 
                                 
                                   i 
                                   , 
                                   j 
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                         2 
                       
                     
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       where 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       i 
                     
                     , 
                     
                       j 
                       ∈ 
                       
                         [ 
                         
                           0 
                           , 
                           3 
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
     The Lagrangian cost Cost4×4(x,y,z,Q,λ) is calculated for a predefined λ.
 
Cost4×4( x,y,z,Q ,λ)=Distortion( x,y,z,Q )+λ×Rate( x,y,z,Q )  (18)
 
     The total cost for p(x,y) is given by: 
     
       
         
           
             
               
                 
                   
                     
                       Cost 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         
                           x 
                           , 
                           y 
                           , 
                           Q 
                           , 
                           λ 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         z 
                       
                       ⁢ 
                       
                         Cost 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         4 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         x 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         4 
                         ⁢ 
                         
                           ( 
                           
                             x 
                             , 
                             y 
                             , 
                             z 
                             , 
                             Q 
                             , 
                             λ 
                           
                           ) 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       where 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       z 
                     
                     ∈ 
                     
                       ⌊ 
                       
                         0 
                         , 
                         
                           
                             
                               A 
                               × 
                               B 
                             
                             16 
                           
                           - 
                           1 
                         
                       
                       ⌋ 
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
     The motion vector (X,Y) is then calculated as follows.
 
( X,Y )=( x,y )|min Cost( x,y,Q ,λ)  (20)
 
     The optimal solution just described maybe too complex to be practical even though it provides the best solution possible. Embodiments of the present description introduce a new cost function that represents a computational approximation of the optimal solution. This computational approximation may have an insignificant impact on the results of the optimal solution while significantly reducing the complexity of the same. 
       FIG. 4  shows a block diagram  400  of an embodiment. Just as with the optimal solution, the current frame  408  is motion compensated  410  for by the candidate macroblock partitions  406  to get the residual error signal, e(x,y). The cunnent fram  404  and the candidate macroblock partitions  406  are provided from encoded MB RAM  408  and search RAM  402 , respectively. e(x,y) is then divided into an integral number of four by four blocks, e(x,y,z) or E  412 , as shown in Table 1. E  412  is then transformed  414  into the frequency domain from the spatial domain as shown in (4), (5), and (6) to get t(x,y,z) or T  416 . 
     According to the optimal solution, T would now be quantized. However, the quantization process is computationally complex because it involves multiplication and other complex binary functions. Thus in one embodiment, the multiplication of T and M from (7) is approximated through a series of shifts and adds as follows:
 
 M ( i,j )× T ( i,j )=( T ( i,j )&lt;&lt; a +Sign( T ( i,j )&lt;&lt; b,  b   )+Sign( T ( i,j )&lt;&lt; c,  c   ))&gt;&gt; d   (21)
 
Thus, (7) can be rewritten as the quantization approximation  418 :
 
 L ( i,j )=(( T ( i,j )&lt;&lt; a +Sign( T ( i,j )&lt;&lt; b,  b   )+Sign( T ( i,j )&lt;&lt; c,  c   ))&gt;&gt; d+R )&gt;&gt; S   (22)
         where i,jε[0,3], and where Sign(x) is 1 when x is negative and 0 when positive
 
S and R can be determined from (9) and (10). The multiplication factor M is approximated with {tilde over (M)}. The values of a, b, c, d,  b , and  c  are found in Table 4 and Table 5 for a corresponding first quantization approximation parameter and corresponding elements of the approximate multiplication factor {tilde over (M)}.
       

     
       
         
               
             
               
               
             
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 4 
               
             
             
               
                   
               
               
                 (a, b, c, d) shift values for a given value of the Multiplication 
               
               
                 Approximation Factor ({circumflex over (M)}) for quantization approximation 
               
             
          
           
               
                   
                 (23) 
               
               
                 
                   
                     
                       
                         
                           M 
                           ~ 
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   f 
                                   ~ 
                                 
                               
                               
                                 
                                   g 
                                   ~ 
                                 
                               
                               
                                 
                                   f 
                                   ~ 
                                 
                               
                               
                                 
                                   g 
                                   ~ 
                                 
                               
                             
                             
                               
                                 
                                   g 
                                   ~ 
                                 
                               
                               
                                 
                                   h 
                                   ~ 
                                 
                               
                               
                                 
                                   g 
                                   ~ 
                                 
                               
                               
                                 
                                   h 
                                   ~ 
                                 
                               
                             
                             
                               
                                 
                                   f 
                                   ~ 
                                 
                               
                               
                                 
                                   g 
                                   ~ 
                                 
                               
                               
                                 
                                   f 
                                   ~ 
                                 
                               
                               
                                 
                                   g 
                                   ~ 
                                 
                               
                             
                             
                               
                                 
                                   g 
                                   ~ 
                                 
                               
                               
                                 
                                   h 
                                   ~ 
                                 
                               
                               
                                 
                                   g 
                                   ~ 
                                 
                               
                               
                                 
                                   h 
                                   ~ 
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                   
               
             
          
           
               
                   
                 {tilde over (f)} 
                   
                 ĝ 
                   
                 ĥ 
                   
               
             
          
           
               
                 QP %6 
                 a 
                 b 
                 c 
                 d 
                 a 
                 b 
                 c 
                 d 
                 a 
                 b 
                 c 
                 d 
               
               
                   
               
             
          
           
               
                 0 
                 11 
                 13 
                 14 
                 1 
                 13 
                 0 
                 7 
                 0 
                 12 
                 10 
                 7 
                 0 
               
               
                 1 
                 13 
                 14 
                 10 
                 1 
                 14 
                 10 
                 9 
                 1 
                 12 
                 9 
                 0 
                 0 
               
               
                 2 
                 13 
                 11 
                 0 
                 0 
                 12 
                 11 
                 9 
                 0 
                 12 
                 7 
                 0 
                 0 
               
               
                 3 
                 13 
                 10 
                 0 
                 0 
                 14 
                 13 
                 10 
                 2 
                 12 
                 0 
                 9 
                 0 
               
               
                 4 
                 13 
                 0 
                 0 
                 0 
                 14 
                 12 
                 9 
                 2 
                 11 
                 10 
                 8 
                 0 
               
               
                 5 
                 13 
                 7 
                 10 
                 0 
                 12 
                 9 
                 0 
                 0 
                 11 
                 9 
                 8 
                 0 
               
               
                   
               
             
          
         
       
     
     
       
         
               
             
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
             
           
               
                 TABLE 5 
               
             
             
               
                   
               
               
                 (  b ,  c ) sign values for a given value of the Multiplication 
               
               
                 Approximation Factor ({tilde over (M)}) for quantization approximation 
               
             
          
           
               
                   
                 {tilde over (f)} 
                   
                 ĝ 
                   
                 ĥ 
                   
               
             
          
           
               
                 QP %6 
                 
                   b 
                 
                 
                   c 
                 
                 
                   b 
                 
                 
                   c 
                 
                 
                   b 
                 
                 
                   c 
                 
               
               
                   
               
               
                 0 
                 0 
                 0 
                 0 
                 1 
                 0 
                 0 
               
               
                 1 
                 0 
                 1 
                 1 
                 1 
                 0 
                 0 
               
               
                 2 
                 0 
                 0 
                 0 
                 0 
                 0 
                 0 
               
               
                 3 
                 0 
                 0 
                 0 
                 1 
                 0 
                 1 
               
               
                 4 
                 0 
                 0 
                 0 
                 0 
                 0 
                 0 
               
               
                 5 
                 0 
                 1 
                 0 
                 0 
                 0 
                 0 
               
               
                   
               
             
          
         
       
     
     According to the optimal solution, the quantization approximation block  420  would then be entropy coded to produce the rate signal  428 . However, entropy coding algorithms such as CAVLC are highly computationally demanding operations. Entropy coding of a 4×4 quantized block involves encoding a Token (indicates the number of non-zero coefficients and the number of trailing 1&#39;s), signs or the trailing 1&#39;s, Levels of the non-zero coefficients, and Runs of zeros between non-zero coefficients. In one embodiment, the entropy coding is eliminated by using the Fast Bits Estimation Method (FBEM) to estimate the rate. According to FBEM, the number of bits taken by the different elements can be derived from the number of non-zero coefficients (N C ), the number of zeros (N Z ), and the sum of absolute levels (SAL). 
     
       
         
           
             
               
                 
                   
                     Rate 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ( 
                       
                         x 
                         , 
                         y 
                         , 
                         z 
                         , 
                         Q 
                       
                       ) 
                     
                   
                   = 
                   
                     Token_Bits 
                     + 
                     Sign_Bits 
                     + 
                     Level_Bits 
                     + 
                     Run_Bits 
                   
                 
               
               
                 
                   ( 
                   24 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     Token_Bits 
                     = 
                     
                       N 
                       c 
                     
                   
                 
               
               
                 
                   ( 
                   25 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     Sign_Bits 
                     = 
                     
                       N 
                       c 
                     
                   
                 
               
               
                 
                   ( 
                   26 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     Level_Bits 
                     = 
                     SAL 
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     Run_Bits 
                     = 
                     
                       
                         N 
                         c 
                       
                       + 
                       
                         N 
                         z 
                       
                     
                   
                 
               
               
                 
                   ( 
                   28 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     
                       N 
                       c 
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         n 
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             Scan 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               ( 
                               
                                 l 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     x 
                                     , 
                                     y 
                                     , 
                                     z 
                                     , 
                                     Q 
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                           != 
                           0 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   29 
                   ) 
                 
               
             
           
         
       
     
     where Scan( ) represents the zig-zag scan 
     
       
         
           
             
               
                 
                   
                     N 
                     z 
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       n 
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           Scan 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             ( 
                             
                               l 
                               ⁡ 
                               
                                 ( 
                                 
                                   x 
                                   , 
                                   y 
                                   , 
                                   z 
                                   , 
                                   Q 
                                 
                                 ) 
                               
                             
                             ) 
                           
                         
                         == 
                         0 
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   30 
                   ) 
                 
               
             
           
         
       
     
     where Scan( ) represents the zig-zag scan 
                   SAL   =       ∑     i   =   0     16     ⁢          l   ⁡     (     x   ,   y   ,   z   ,   Q     )                      (   31   )               
Thus, a Rate  428  can be determined for each candidate macroblock partition  406  through an entropy coding approximation  424 .
 
     According to the optimal solution, L would also need to be inverse-quantized  322  and inverse-transformed  326 . Similar to quantization, inverse quantization is also computationally complex. In one embodiment, these processes are simplified through an inverse quantization approximation. The inverse quantization approximation is achieved by performing the same steps as the quantization approximation, but with a second quantization parameter.
 
 L ′( i,j )=(( T ( i,j )&lt;&lt; a +Sign( T ( i,j )&lt;&lt; b,  b   )+Sign( T ( i,j )&lt;&lt; c,  c   ))&gt;&gt; d+R )&gt;&gt; S   (32)
 
In one embodiment, the second quantization parameter is chosen such that S=15, which approximates the equivalent to calculating the zero-distortion value.
 
     By doing the above steps, inverse quantization  322  has been significantly simplified and inverse transformation  326  is no longer necessary. It is appreciated that because embodiments achieve the inverse quantization approximation through quantization approximation with a second quantization parameter, both L and L′ can be generated from the same circuitry, module, etc. 
     In one embodiment, once the inverse quantization approximation block L′  422  has been generated, the Distortion  430 , Distortion(x,y,z,Q) or Distortion(Q), can be represented by the squared-error between L′ and L (as shown by sum of squared difference  426 ). (L′-L) represents the quantization error and has a small dynamic range. Hence embodiments can store the squared values in a lookup-table to avoid the squaring operation. 
     
       
         
           
             
               
                 
                   
                     Distortion 
                     ⁡ 
                     
                       ( 
                       
                         x 
                         , 
                         y 
                         , 
                         z 
                         , 
                         Q 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         , 
                         j 
                       
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           
                             
                               L 
                               ′ 
                             
                             ⁡ 
                             
                               ( 
                               
                                 i 
                                 , 
                                 j 
                               
                               ) 
                             
                           
                           - 
                           
                             L 
                             ⁡ 
                             
                               ( 
                               
                                 i 
                                 , 
                                 j 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   33 
                   ) 
                 
               
             
           
         
       
     
     In one embodiment, the Lagrangian cost for each of the integral number of four by four blocks Cost4×4(x,y,z,Q,λ) is calculated for a predefined λ.
 
Cost4×4( x,y,z,Q ,λ)=Distortion( x,y,z,Q )+λ×Rate( x,y,z,Q )  (34)
 
     In one embodiment, the total cost for p(x,y) is given by: 
     
       
         
           
             
               
                 
                   
                     Cos 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       t 
                       ⁡ 
                       
                         ( 
                         
                           x 
                           , 
                           y 
                           , 
                           Q 
                           , 
                           λ 
                         
                         ) 
                       
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         z 
                       
                       ⁢ 
                       
                         Cos 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         t 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         4 
                         ⁢ 
                         x 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         4 
                         ⁢ 
                         
                           ( 
                           
                             x 
                             , 
                             y 
                             , 
                             z 
                             , 
                             Q 
                             , 
                             λ 
                           
                           ) 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         where 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         z 
                       
                     
                     ∈ 
                     
                       [ 
                       
                         0 
                         , 
                         
                           
                             A 
                             × 
                             B 
                           
                           16 
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   35 
                   ) 
                 
               
             
           
         
       
     
     Finally, the motion vector (X,Y) is then selected as follows:
 
( X,Y )=( x,y )|min Cost( x,y,Q,λ )  (36)
 
     Thus, the above embodiments are able to accurately approximate the rate and distortion for each candidate macroblock partition. The embodiments may select the best possible predictive macroblock partition with more certainty than the SAD cost function because the selection process specifically account for Rate and Distortion. Therefore, the embodiments are able to achieve a higher signal to noise ratio than SAD for a given bitrate, as illustrated in  FIG. 5  and  FIG. 6 . 
     The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present description. Various modifications to these embodiments may be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the description. Thus, the present description is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.