Abstract:
A weighting function (WF) is previously provided to model the number of search points of a pattern search. However, WF fails to properly describe the behavior of the genetic pattern search algorithms due to some over-simplifications in their models. Therefore, a refined weighting function (RWF) is provided to more accurately describe both genetic and non-genetic pattern searches. Moreover, based on the understanding to RWF, two momentum-directed genetic search algorithms are further provided. These new algorithms check the possible mutations according to their likelihood to the preceding successful mutations and further accelerate the previous genetic pattern searches.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of U.S. Provisional Application No. 61/101,155, filed on Sep. 30, 2008 and entitled “On Modeling Genetic Pattern Searches for Block Motion Estimation” the contents of which are incorporated herein. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to processing of digital image data, and more particularly, to compression techniques such as Block Motion Estimation (BME) and related features which are useful in coding video signal sequences. 
         [0004]    2. Description of the Prior Art 
         [0005]    Motion Estimation (ME) is a tool used frequently in the art of image processing to find a motion vector that best describes an object in one domain and its corresponding object in another domain. Most modern video coding circuits, such as employed in H.26x and MPEG compatible systems, typically adopt a branch of ME, namely so called BME to help eliminate the inter-frame dependencies. For contemporary examples of this type of technique, please see the following, all of which are incorporated by reference herein: [1] Kim et al. “Fast motion estimation apparatus and method using block matching algorithm”, US patent, Pub. No.: US 2006/0280248 A1, Dec. 14, 2006. [2] Thomas Wiegand, et al. “Overview of the H.264/AVC video coding standard”, IEEE Trans. Circuits Systm. Video Technolog, vol. 13, no. 7, July 2003. 
         [0006]    Please refer to  FIG. 1 .  FIG. 1  is a diagram illustrating a conventional method for BME process. As shown in  FIG. 1 , a motion vector can be found that best describes a current block in one current image frame and its corresponding reference block within the search area in the other frame(s). The location differences of the reference block within the prior frame and co-located block within the current frame are described as the motion vectors. Typically a 16×16, 16×8, 8×16, 8×8, 8×4, 4×8, or 4×4 block is used for the BME procedure. BME is conventionally used in a number of block-matching video compression systems, such as H.261/263/264 as well as MPEG-1/2/4. In a BME approach, reference frames typically consist of the temporal previous coded frame. In some instances, it may consist of both the temporal previous coded frames and the temporal successive coded frames. 
         [0007]    For example:
   Presentation Sequence: I 1 , P 2 , B 3 , P 4 , B 5 , P 6 , B 7 , B 8 , P 9 , B 10 , P 11 , B 12 , P 13 , I 14  . . .   Coding Sequence: I 1 , P 2 , P 4 , B 3 , P 6 , B 5 , P 9 , B 7 , B 8 , P 11 , B 10 , P 13 , B 12 , I 14 .   
 
         [0010]    In deciding which reference block most resembles a current selected block, one usually calculates the corresponding block-matching discrepancy. Any of a number of different techniques may be employed to measure such discrepancy. 
         [0011]    One of the most commonly used block-matching discrepancy measures is the Sum of Absolute Differences (SAD). The SAD of a current block having a size N×M compared to a reference block with a displacement of (v x , v y ) relative to the current block in the reference frame is defined as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       SAD 
                        
                       
                         ( 
                         
                           
                             v 
                             x 
                           
                           , 
                           
                             v 
                             y 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         N 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             1 
                           
                           M 
                         
                          
                         
                            
                           
                             
                               
                                 
                                   
                                     
                                       I 
                                       n 
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           x 
                                           + 
                                           i 
                                         
                                         , 
                                         
                                           y 
                                           + 
                                           j 
                                         
                                       
                                       ) 
                                     
                                   
                                   - 
                                 
                               
                             
                             
                               
                                 
                                   
                                     I 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         x 
                                         + 
                                         i 
                                         + 
                                         
                                           V 
                                           x 
                                         
                                       
                                       , 
                                       
                                         y 
                                         + 
                                         j 
                                         + 
                                         
                                           V 
                                           y 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                            
                         
                       
                     
                   
                   ; 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0012]    Where I n  is the current frame and I n−1  is the reference frame, (x, y) is the location of the current block. 
         [0013]    As noted above, in a block-matching algorithm, a current frame of video image data is divided into a plurality of individual current blocks of a particular size. BME finds a corresponding reference block in the search window of the reference frames for each of the blocks. The displacements of the reference blocks from the previous frame to the current frame are determined as respective corresponding motion vectors. 
         [0014]    One type of BME algorithms employs what is referred to as a full search (FS) algorithm. In the FS algorithm, each reference block within a current frame is compared with all of a plurality of blocks within a predetermined search region of a reference frame. The FS algorithm is a useful technique in that it provides block matching with high precision and a simple data flow. In addition, the structure of a control circuit used for executing the FS algorithm is relatively simple. However, it can be seen quite easily that the FS algorithm requires a considerable amount of computation, especially when the search region becomes large. 
         [0015]    In order to reduce the time/computation requirements associated with FS algorithms, various fast pattern search methods have been suggested. Using a search pattern instead of each block in an entire frame is advantageous as it reduces the number of points to be searched. These search patterns are devised therefore by taking advantage of the characteristics of a distribution of motion vectors, thereby enhancing the speed of the motion estimation process. 
         [0016]    While it is known to use different kinds of search patterns for a BME process, the process for determining what kind of search patterns to be used and when to use them is still very much an unpredictable art. Therefore there is a very pronounced and long-felt need for both improved BME search patterns as well as tools for evaluating the performance of potential search patterns, and adaptively identifying which of such patterns may be most appropriate for particular image sequences. 
       SUMMARY OF THE INVENTION 
       [0017]    The present invention provides an adaptive method of performing block motion estimation. The method comprises (a) calculating a motion vector variance for a first frame according to a first search pattern, (b) determining a relationship between the motion vector variance and a predetermined threshold for the first frame, and (c) selecting a first or a second search pattern algorithms for identifying one or more search blocks in a second frame according to the determined relationship between the motion vector variance and the predetermined threshold for the first frame, wherein the predetermined threshold is determined by refined weighting functions of the first and the second search pattern algorithms, the refined weighting functions of the first and the second pattern algorithms are numbers of average search points for the first and the second pattern algorithms searching in the first frame, and block motion estimation is performed adaptively for the second frame. 
         [0018]    The present invention further provides a momentum-directed genetic pattern search method of performing block motion estimation for a frame. The method comprises (a) selecting a child point proximate to a parent point according to likelihood to previous successful mutations, (b) comparing block matching cost of the parent point and block matching cost of the child point, and (c) setting either the parent point or the child point as a surviving parent point for a successful mutation according to the compared result of the step (b). 
         [0019]    The present invention further provides a momentum-directed genetic rhombus pattern search method of performing block motion estimation for a frame. The method comprises (a) selecting a child point from a perimeter portion of a rhombus centered about a parent point according to likelihood to previous successful mutations, (b) comparing block matching cost of the parent point and block matching cost of the child point, and (c) setting either the parent point or the child point as a surviving parent point for a successful mutation according to the compared result of the step (b). 
         [0020]    The present invention further provides a momentum-directed genetic hexagonal pattern search method of performing block motion estimation for a frame. The method comprises (a) selecting a child point from a perimeter portion of a hexagon centered about a parent point according to likelihood of the parent point according to previous successful mutations, (b) comparing block matching cost of the parent point and block matching cost of the child point, and (c) setting either the parent point or the child point as a surviving parent point for a successful mutation according to the compared result of the step (b). 
         [0021]    These and other objectives of the present invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment that is illustrated in the various figures and drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0022]      FIG. 1  is a diagram illustrating the idea of BME process. 
           [0023]      FIG. 2  is a diagram illustrating all possible search order for a parent point with four possible mutation points and only one of them is feasible. 
           [0024]      FIG. 3  is a diagram illustrating all possible search order for a parent point with four possible mutation points and only two of them is feasible. 
           [0025]      FIG. 4  is a flowchart of the GRPS. 
           [0026]      FIG. 5  is a diagram illustrating the search patterns of GRPS. 
           [0027]      FIG. 6  is a diagram illustrating the contour plot of the feasible number of mutation points for each point in the search area. 
           [0028]      FIG. 7  is a diagram illustrating two cases of starting search points and two cases of intermediate search points. 
           [0029]      FIG. 8  is a diagram illustrating the construction of RWF of the present invention. 
           [0030]      FIG. 9  is a diagram illustrating the contour plot of RWF of GRPS of the present invention. 
           [0031]      FIG. 10  is a flowchart of GPHS. 
           [0032]      FIG. 11  is a diagram illustrating the search pattern of GPHS. 
           [0033]      FIG. 12  is a diagram illustrating the feasible number of mutations of GPHS. 
           [0034]      FIG. 13  is a diagram illustrating the contour plot of RWF of GPHS of the present invention. 
           [0035]      FIG. 14  is a diagram illustrating the contour plot of RWF of MD-GRPS of the present invention. 
           [0036]      FIG. 15  is a flowchart illustrating the MD-GRPS algorithm of the present invention. 
           [0037]      FIG. 16  is a diagram illustrating the search order of possible mutation points of MD-GRPS algorithm of the present invention. 
           [0038]      FIG. 17  is a diagram illustrating the contour plot of RWF of MD-GPHS algorithm of the present invention. 
           [0039]      FIG. 18  is a flowchart of MD-GPHS of the present invention. 
           [0040]      FIG. 19  is a diagram illustrating the search order of possible mutation points in MD-GPHS algorithm of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0041]    The present invention provides method for evaluating the performance of search pattern and further provides momentum-directed genetic search pattern algorithms. Therefore users can utilize the most suitable search pattern by the evaluation result. Furthermore, users can utilize the momentum-directed genetic search pattern of the present invention so that the computational requirement for searching the motion vector of the inter-frame can be reduced. 
         [0042]    Basic Assumption: the present invention assumes the matching error (distortion) surface is uni-modal, and furthermore, a Strong Quadrant Monotonic (SQM) function. 
         [0043]    The present invention provides a mathematical model (as expressed by the equation (2)˜(4)) to evaluate the computational requirement of a search pattern utilized in a video sequence: 
         [0000]    
       
         
           
             
               
                 
                   
                     ASP 
                     = 
                     
                       
                         
                           C 
                           1 
                         
                         × 
                         
                           
                             ∑ 
                             
                               x 
                               , 
                               
                                 y 
                                 ∈ 
                                 A 
                               
                             
                           
                            
                           
                             
                               
                                 S 
                                 
                                   SP 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                               
                                
                               
                                 ( 
                                 
                                   x 
                                   , 
                                   y 
                                 
                                 ) 
                               
                             
                             × 
                             
                               
                                 WF 
                                 
                                   SP 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                               
                                
                               
                                 ( 
                                 
                                   x 
                                   , 
                                   y 
                                 
                                 ) 
                               
                             
                           
                         
                       
                       + 
                       
                         C 
                         2 
                       
                     
                   
                   ; 
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         S 
                         
                           SP 
                            
                           
                               
                           
                            
                           1 
                         
                       
                        
                       
                         ( 
                         
                           x 
                           , 
                           y 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           1 
                           
                             
                               
                                  
                                 x 
                                  
                               
                               
                                 5 
                                 / 
                                 3 
                               
                             
                             + 
                             
                               ζ 
                               x 
                             
                           
                         
                          
                         
                           1 
                           
                             
                               
                                  
                                 y 
                                  
                               
                               
                                 5 
                                 / 
                                 3 
                               
                             
                             + 
                             
                               ζ 
                               y 
                             
                           
                         
                       
                       
                         
                           ∑ 
                           
                             
                               ( 
                               
                                 
                                   x 
                                   ′ 
                                 
                                 , 
                                 
                                   y 
                                   ′ 
                                 
                               
                               ) 
                             
                             ∈ 
                             A 
                           
                         
                          
                         
                           
                             1 
                             
                               
                                 
                                    
                                   
                                     x 
                                     ′ 
                                   
                                    
                                 
                                 
                                   5 
                                   / 
                                   3 
                                 
                               
                               + 
                               
                                 ζ 
                                 x 
                               
                             
                           
                            
                           
                             1 
                             
                               
                                 
                                    
                                   
                                     y 
                                     ′ 
                                   
                                    
                                 
                                 
                                   5 
                                   / 
                                   3 
                                 
                               
                               + 
                               
                                 ζ 
                                 y 
                               
                             
                           
                         
                       
                     
                   
                   ; 
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
             
               
                 
                   
                     PMV 
                     = 
                     
                       median 
                        
                       
                         ( 
                         
                           
                             MV 
                             L 
                           
                           , 
                           
                             MV 
                             U 
                           
                           , 
                           
                             MV 
                             UR 
                           
                         
                         ) 
                       
                     
                   
                   ; 
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0044]    where ASP represents the average number of search points produced by a PBME, SP 1  represents a first search pattern, SP 2  represents a second search pattern, S SP1  represents the Motion Vector (MV) probability distribution function of the search pattern SP 1 , WF SP2  (Weight Function) represents the minimal search points for a motion vector located at the coordinates (x,y) by utilizing the search pattern SP 2 , C 1  and C 2  are two constant parameters, and MV L , MV U , and MV UR  are the MVs of the left, up, and up-right block neighbors to current block. 
         [0045]    In the present invention, SP 1  can be realized with the full search, and SP 2  can be realized with any search pattern. 
         [0046]    This model consists of two components: a statistical probability distribution function S SP1 (x,y) of MVs (expressed by the equation (3)), and the minimal search points for a MV located at the coordinates (x,y), WF SP2 (x,y). In the equation (2), (x,y) are the relative coordinates of which the origin is “PMV” expressed by the equation (4). The parameters C 1  and C 2  are obtained experimentally by training methods. Note that C 1  is always positive because ASP (equation (2)) and the sum of products of S SP1 (x,y) and WF SP2 (x,y) are always positively correlated. 
         [0047]    The equation (3) is derived based on the experimental data. In the equation (3), (x,y) and (x′,y′) are relative coordinates with respect to (w.r.t.) “PMV”, and “A” represents the search area. The parameters (ζ x , ζ y ) are obtained b numerical methods such that the variances of S SP1 (x,y) match those of the MVs acquired by the first search pattern on a specific sequence. 
         [0048]    There are two methods to obtain the values of parameters C 1  and C 2 . In the first method, the parameters C 1  and C 2  are obtained from a set of training sequences with one specific search algorithm. In the second method, the parameters C 1  and C 2  are obtained by applying a set of search algorithms (training algorithms) to a specific sequence. Then the “ASP” value of a new algorithm can be predicted by using the mathematical model of the present invention. The first and the second methods are designed for different scenarios. The first method is used to predict the ASP of a new sequence (for a given specific search algorithm), while the second method is used to predict the ASP of a new search algorithm (for a given specific sequence). 
         [0049]    Therefore, if one search pattern algorithm has lower ASP than any other search pattern algorithm does, it meant that this search pattern algorithm is more suitable than any other search pattern algorithm for this video sequence. 
         [0050]    However, if the search pattern SP 2  is a genetic search pattern, since the nature of the genetic search pattern is randomly selecting one child point neighboring the parent point, thus the probability of each possible child point neighboring the parent point has to be considered. In this way, the weighting function WF is not suitable to describe the number of the search points of a genetic search pattern. Therefore, the present invention provides a Refined Weighting Function (RWF) to describe the number of a genetic search pattern with higher accuracy. Consequently, the WF in the equation (2) is replaced with the RWF as the following equation expresses: 
         [0000]    
       
         
           
             
               
                 
                   ASP 
                   = 
                   
                     
                       
                         C 
                         1 
                       
                       × 
                       
                         
                           ∑ 
                           
                             x 
                             , 
                             
                               y 
                               ∈ 
                               A 
                             
                           
                         
                          
                         
                           
                             
                               S 
                               
                                 SP 
                                  
                                 
                                     
                                 
                                  
                                 1 
                               
                             
                              
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                           × 
                           
                             
                               RWF 
                               
                                 SP 
                                  
                                 
                                     
                                 
                                  
                                 2 
                               
                             
                              
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                         
                       
                     
                     + 
                     
                       C 
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0051]    where the search pattern SP 2  can be a genetic search pattern. Therefore, the equation (5) is utilized in the present invention as the refined model to characterize the behavior of a genetic pattern search. 
         [0052]    In one embodiment of the present invention, the genetic search pattern can be Genetic Rhombus Pattern Search (GRPS) or Genetic Point oriented Hexagonal Search (GPHS). The present invention provides a method for determining which of the GRPS and the GPHS is more suitable for a video sequence. According to the equation (5), the ASPs of the GRPS and GPHS respectively are: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         ASP 
                         GRPS 
                       
                       = 
                       
                         
                           
                             C 
                             1 
                           
                           × 
                           
                             
                               ∑ 
                               
                                 x 
                                 , 
                                 
                                   y 
                                   ∈ 
                                   A 
                                 
                               
                             
                              
                             
                               
                                 
                                   S 
                                   
                                     SP 
                                      
                                     
                                         
                                     
                                      
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     x 
                                     , 
                                     y 
                                   
                                   ) 
                                 
                               
                               × 
                               
                                 
                                   RWF 
                                   GRPS 
                                 
                                  
                                 
                                   ( 
                                   
                                     x 
                                     , 
                                     y 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         + 
                         
                           C 
                           2 
                         
                       
                     
                     ; 
                   
                    
                   
                     
 
                   
                    
                   and 
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
             
               
                 
                   
                     ASP 
                     GRHS 
                   
                   = 
                   
                     
                       
                         C 
                         1 
                       
                       × 
                       
                         
                           ∑ 
                           
                             x 
                             , 
                             
                               y 
                               ∈ 
                               A 
                             
                           
                         
                          
                         
                           
                             
                               S 
                               
                                 SP 
                                  
                                 
                                     
                                 
                                  
                                 1 
                               
                             
                              
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                           × 
                           
                             
                               RWF 
                               GPHS 
                             
                              
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                         
                       
                     
                     + 
                     
                       
                         C 
                         2 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0053]    Comparatively, when we use the first method to predict the ASP of a new sequence, the prediction differences between adopting WF and RWF in the model are similar. It is because statistical regressions effectively compensate the difference in parameter C 1  and C 2 . 
         [0054]    According to the equations (6) and (7), if the ASP GRPS  is higher than the ASP GPHS , it means the GPHS has better performance than the GRPS for the video sequence, and vice versa. Therefore, an average search point difference D ASP  can be derived according to the equations (6) and (7): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       D 
                       ASP 
                     
                     = 
                     
                       
                         C 
                         1 
                       
                       × 
                       
                         
                           ∑ 
                           
                             x 
                             , 
                             
                               y 
                               ∈ 
                               A 
                             
                           
                         
                          
                         
                           
                             
                               S 
                               
                                 SP 
                                  
                                 
                                     
                                 
                                  
                                 1 
                               
                             
                              
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                           × 
                           
                             ( 
                             
                               
                                 
                                   
                                     
                                       
                                         RWF 
                                         GRPS 
                                       
                                        
                                       
                                         ( 
                                         
                                           x 
                                           , 
                                           y 
                                         
                                         ) 
                                       
                                     
                                     - 
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       RWF 
                                       GPHS 
                                     
                                      
                                     
                                       ( 
                                       
                                         x 
                                         , 
                                         y 
                                       
                                       ) 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   ; 
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0000]    and a performance difference index I ASP  between the GRPS and the GPHS can be derived from the equation (8) by dividing the equation (8) with the constant parameter C 1 : 
         [0000]    
       
         
           
             
               
                 
                   
                     I 
                     ASP 
                   
                   = 
                   
                     
                       ∑ 
                       
                         x 
                         , 
                         
                           y 
                           ∈ 
                           A 
                         
                       
                     
                      
                     
                       
                         
                           S 
                           
                             SP 
                              
                             
                                 
                             
                              
                             1 
                           
                         
                          
                         
                           ( 
                           
                             x 
                             , 
                             y 
                           
                           ) 
                         
                       
                       × 
                       
                         
                           ( 
                           
                             
                               
                                 RWF 
                                 GRPS 
                               
                                
                               
                                 ( 
                                 
                                   x 
                                   , 
                                   y 
                                 
                                 ) 
                               
                             
                             - 
                             
                               
                                 RWF 
                                 GPHS 
                               
                                
                               
                                 ( 
                                 
                                   x 
                                   , 
                                   y 
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0055]    When the performance difference index I ASP &gt;0, the GPHS is significantly superior to GRPS, and when the performance difference index I ASP &lt;0, the GRPS is significantly superior to GPHS. Thus, users can utilize the performance difference index I ASP  to determine which genetic search pattern algorithm to be used. 
         [0056]    Consequently, for simplicity, the equation (9) can be approximated by a linear function which is expressed as follows: 
         [0000]        P ×VAR x   +Q ×VAR y   −TH =0   (10); 
         [0057]    where P and Q represent constants, TH represents a predetermined threshold, VAR x  represents the horizontal motion vector variance, and VAR y  represents the vertical motion vector variance. The value of the predetermined threshold can be estimated by the RWF of the GRPS and the RWF of the GPHS. Therefore, it is quite obvious that the refined model adopting RWF shows better accuracy than the original model adopting WF. 
         [0058]    The details of the refined weighting function (RWF) of the present invention will be explained in the following description. 
         [0059]    It is assmed that the matching error surface is a strong Quadrant Monotonic function. Let O=(x o , y o ) be the optimum search point, and A=(x A , y A ) and X=(x x , y x ) are any two points in the search range, and (|A−X|&lt;R nbd , (Say, R nbd =3)). If |A−O|&gt;|X−O| implies D(X)&lt;D(A), then this D(X) is a strong quadrant monotonic function. 
         [0060]    The RWF, or RWF(x,y), is defined to be the average number of search points needed by a search algorithm on a SQM matching error surface when the best matching point is located at (0,0) and the starting point is (x,y). 
         [0061]    For a genetic search algorithm, when a parent point is with N possible mutation points and m out of the N points have smaller matching error, the expected number of search points to move from the parent point to one feasible mutation point is E m   N , as shown in the equation (11): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           E 
                           m 
                           N 
                         
                         = 
                           
                          
                         
                           
                             m 
                             N 
                           
                           + 
                           
                             
                               m 
                               N 
                             
                              
                             
                               
                                 ∑ 
                                 
                                   j 
                                   = 
                                   1 
                                 
                                 
                                   N 
                                   - 
                                   m 
                                 
                               
                                
                               
                                 ( 
                                 
                                   
                                     ( 
                                     
                                       j 
                                       + 
                                       1 
                                     
                                     ) 
                                   
                                   × 
                                   
                                     
                                       ∏ 
                                       
                                         i 
                                         = 
                                         1 
                                       
                                       j 
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           
                                             ( 
                                             
                                               N 
                                               - 
                                               m 
                                             
                                             ) 
                                           
                                           - 
                                           
                                             ( 
                                             
                                               i 
                                               - 
                                               1 
                                             
                                             ) 
                                           
                                         
                                         
                                           N 
                                           - 
                                           i 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           = 
                             
                            
                           
                             
                               N 
                               + 
                               1 
                             
                             
                               m 
                               + 
                               1 
                             
                           
                         
                         ; 
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
             
               
                 
                   
                     Where 
                      
                     
                         
                     
                      
                     N 
                   
                   &gt; 
                   
                     m 
                     . 
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
         [0062]    In the present invention, it is assumed that the probability for selecting any of the mutation points is equal. On a SQM matching error surface, the number of the feasible mutation points, m, is decided by the relative locations between the current parent point and the global optimal point. N is decided by the search point and the parent point type (a starting parent point or an intermediate parent point). 
         [0063]    Please refer to  FIG. 2  and  FIG. 3 .  FIG. 2  is a diagram illustrating all possible search order for a parent point with four possible mutation points, denoted by A, B, C, and D, respectively, and only one of them, denoted by D, is with smaller matching distortion.  FIG. 3  is a diagram illustrating all possible search order for a parent point with four possible mutation points, denoted by A, B, C, and D, respectively, and two of them, denoted by C and D, are with smaller matching distortion. The equations (12) and (13) show the calculations of their expected value to move from the parent point to a feasible mutation point of  FIG. 2  and  FIG. 3 , respectively: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       E 
                       1 
                       4 
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               
                                 
                                   
                                     [ 
                                     
                                       
                                         
                                           
                                             
                                               
                                                 [ 
                                                 
                                                   
                                                     
                                                       
                                                         
                                                           
                                                             1 
                                                             4 
                                                           
                                                           × 
                                                           
                                                             1 
                                                             3 
                                                           
                                                           × 
                                                           
                                                             1 
                                                             2 
                                                           
                                                           × 
                                                           1 
                                                           × 
                                                           4 
                                                         
                                                         + 
                                                       
                                                     
                                                   
                                                   
                                                     
                                                       
                                                         
                                                           1 
                                                           4 
                                                         
                                                         × 
                                                         
                                                           1 
                                                           3 
                                                         
                                                         × 
                                                         
                                                           1 
                                                           2 
                                                         
                                                         × 
                                                         3 
                                                       
                                                     
                                                   
                                                 
                                                 ] 
                                               
                                               × 
                                               2 
                                             
                                             + 
                                           
                                         
                                       
                                       
                                         
                                           
                                             
                                               1 
                                               4 
                                             
                                             × 
                                             
                                               1 
                                               3 
                                             
                                             × 
                                             2 
                                           
                                         
                                       
                                     
                                     ] 
                                   
                                   × 
                                   3 
                                 
                                 + 
                               
                             
                           
                           
                             
                               
                                 1 
                                 4 
                               
                             
                           
                         
                         ] 
                       
                       = 
                       
                         5 
                         2 
                       
                     
                   
                   ; 
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       E 
                       2 
                       4 
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               
                                 
                                   
                                     [ 
                                     
                                       
                                         
                                           
                                             
                                               
                                                 1 
                                                 4 
                                               
                                               × 
                                               
                                                 1 
                                                 3 
                                               
                                               × 
                                               
                                                 1 
                                                 2 
                                               
                                               × 
                                               3 
                                               × 
                                               2 
                                             
                                             + 
                                           
                                         
                                       
                                       
                                         
                                           
                                             
                                               1 
                                               4 
                                             
                                             × 
                                             
                                               1 
                                               3 
                                             
                                             × 
                                             2 
                                             × 
                                             2 
                                           
                                         
                                       
                                     
                                     ] 
                                   
                                   × 
                                   2 
                                 
                                 + 
                               
                             
                           
                           
                             
                               
                                 
                                   1 
                                   4 
                                 
                                 × 
                                 1 
                                 × 
                                 2 
                               
                             
                           
                         
                         ] 
                       
                       = 
                       
                         5 
                         3 
                       
                     
                   
                   ; 
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
         [0064]    Similarly, by observing the search order of a parent point, it can be obtained with the expected value to move from the parent point to a feasible mutation point as shown in Table 1. 
         [0000]    
       
         
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 The values of E m   N   
               
             
          
           
               
                   
                 M 
                   
               
             
          
           
               
                 E m   N   
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
               
               
                   
               
             
          
           
               
                 N 
                 3 
                 2.00 
                 1.33 
                 1.00 
                   
                   
                   
               
               
                   
                 4 
                 2.50 
                 1.67 
                 1.25 
                 1.00 
               
               
                   
                 5 
                 3.00 
                 2.00 
                 1.50 
                 1.20 
                 1.00 
               
               
                   
                 6 
                 3.50 
                 2.33 
                 1.75 
                 1.40 
                 1.17 
                 1.00 
               
               
                   
               
               
                 Where N = 3~6, and m = 1~N. 
               
             
          
         
       
     
       GRPS: 
       [0065]    As one example, the RWF for the Genetic Rhombus Pattern Search (GRPS) is constructed. Please refer to  FIG. 4  and  FIG. 5  together.  FIG. 4  is a flowchart of the GRPS.  FIG. 5  is a diagram illustrating the search patterns of GRPS. In the search process (S2, Mutation), only one (black dot, for example) out of the four (grey and black) points in  FIG. 5(   a ) is randomly chosen as the next check point. And the search ends when all four (black) points in  FIG. 5(   b ) have been checked and all of them have larger matching errors than that of the center (white) point. 
         [0066]    Please refer to  FIG. 6 .  FIG. 6  is a diagram illustrating the contour plot of the feasible number of mutation points for each point in the search area. On a SQM matching error surface, it is assumed that the optimal point be the origin (0,0), and u=(x 1 , y 1 ) and v=(x 2 , y 2 ) be two points in the domain. The distortion at u, D(u), is smaller than D(v), if |x 1 |&lt;|x 2 | and |y 1 |≦|y 2 |, or if |x 1 |≦|x 2 | and |y 1 |&lt;|y 2 |. 
         [0067]    Please refer to  FIG. 7 .  FIG. 7  is a diagram illustrating two cases of starting search points and two cases of intermediate search points. Specifically, as shown in  FIG. 7 , there are two types of starting search point cases (S 1   GRPS  and S 2   GRPS ) and two types of intermediate search point cases (M 1   GRPS  and M 2   GRPS ) for the GRPS. Herein, the points “A”, “B”, “C” and “D” are the search candidate points (mutation points), and the point “E” denotes the best matching point. In  FIG. 7(   a ), only one out of the four points centered at S 1   GRPS  may have a smaller matching error than S 1   GRPS  when the point “E” has the same X or Y coordinate as S 1   GRPS . Otherwise, it is the case as shown in  FIG. 7(   b ), which illustrates two out of the four points centered at S 2   GRPS  may have smaller errors. Similarly, as shown in  FIG. 7(   c ), only one out of the three points centered at M 1   GRPS  may have smaller matching error when the point “E” has the same X or Y coordinate as M 1   GRPS . Otherwise, it is the case as shown in  FIG. 7(   d ), which illustrates two out of the three points centered at M 2   GRPS  may have smaller errors. And the expected numbers of the search points to move rom S 1   GRPS , S 2   GRPS , M 1   GRPS  and M 2   GRPS  to a feasible point respectively are E 1   4 (5/2), E 2   4 (5/3), E 1   3 (4/2) and E 2   3 (4/3) by looking up in Table 1. 
         [0068]    It is assumed that the coordinate of the starting point is (x,y) and the best matching point is (0,0). The number of the average search points moving from (x,y) to (0,0) is RWFGRPS(x,y).  FIG. 8  shows the algorithm of calculating RWF for the GRPS according to the above analysis.  FIG. 9  shows the contour plot of RWFGRPS(x,y). 
       GPHS: 
       [0069]    Please refer to  FIG. 10  and  FIG. 11  together.  FIG. 10  is a flowchart of Genetic Point oriented Hexagonal Search (GPHS).  FIG. 11  is a diagram illustrating the search pattern of the GPHS. In  FIG. 10 , Steps  2  and  3  are similar to those of GRPS but with a different large search pattern. In Step  4  (S 4 , Refinement), the so-called normalized group distortion (NGD) for all the grey points in  FIG. 11(   b ) is defined by the following equation (14): 
         [0000]    
       
         
           
             
               
                 
                   
                     NGD 
                     = 
                     
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           N 
                         
                          
                         
                           
                             SAD 
                             i 
                           
                           
                             d 
                             i 
                           
                         
                       
                       = 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           N 
                         
                          
                         
                           
                             SAD 
                             i 
                           
                           
                             
                               
                                 
                                   ( 
                                   
                                     
                                       x 
                                       i 
                                     
                                     - 
                                     x 
                                   
                                   ) 
                                 
                                 2 
                               
                               + 
                               
                                 
                                   ( 
                                   
                                     
                                       y 
                                       i 
                                     
                                     - 
                                     y 
                                   
                                   ) 
                                 
                                 2 
                               
                             
                           
                         
                       
                     
                   
                   ; 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0070]    where SADi denotes the SAD of neighbor i in the corresponding group, “A”˜“H”, di denotes the distance to the center, (xi, yi) and (x,y) are the coordinates of neighbor i and the center, respectively, and N is the total point number of each group in  FIG. 11(   c ) and  FIG. 11(   d ). 
         [0071]    Then, the point having smallest NGD from points “a” to “f” in  FIG. 11(   d ) is selected and one smaller NGD point from points “g” and “h” in  FIG. 11(   c ). These two points constitute the small search pattern. Herein, the NGD of points “a” to “h” is calculated from the SADs in the groups “A” to “H”, respectively, as shown by  FIG. 11(   d ) and  FIG. 11(   c ). This last step is biased to the horizontal direction because most data in nature image sequences show that the horizontal movement has a higher probability.  FIG. 12  shows the feasible number of mutations of GPHS. Similarly, using above information to simulate the search process of a GPHS on a SQM matching error surface, the contour plot of RWFGPHS(x,y) can be obtained in  FIG. 13 . 
       MD-GPS: 
       [0072]    The present invention provides two Momentum-Directed Genetic Pattern Search (MD-GPS) algorithms. The MD-GPS algorithms of the present invention are the momentum-directed version of the GRPS and the GPHS, respectively. 
         [0073]    It is assumed that a doable search method moves at most one unit distance horizontally or vertically per step, as shown in  FIG. 5(   a ). Then, the smallest average number of search points for reaching the point (x,y) can be expressed by the following equation: 
         [0000]        SP   M =abs( x )+abs( y )+1   (15); 
         [0074]    where SP M  represents the smallest average number of the search points for reaching the point (x,y), abs(x) represents the horizontal distance between the point (x,y) and the starting point, and abs(y) represents the vertical distance between the point (x,y) and the starting point. At the ending stage, deciding the best motion vector generally requires examining at least the center point and its four neighboring points as shown in  FIG. 5(   b ). Consequently, the smallest number of search points for motion vector (x,y) can be expressed by the equation (16) and its contour plot is shown by  FIG. 14 . The equation (16) is expressed as follows: 
         [0000]      RWF GRPS ( x,y )=Max(5,4+abs( x )+abs( y ))   (16). 
         [0075]    Comparing  FIG. 14  to  FIG. 9 , it is obvious that the RWF of GRPS does not match the ideal RWF. However, by observing the ideal RWF carefully, it can be understood that the algorithm should proceed straightly towards the best matching point. Statistically, the successful direction of the previous search likely reappears at the current point. Therefore, instead of randomly select one mutation point from the candidate child point set, the mutation point is selected according to its likelihood to be a successful mutation. That is, it tends to move along the same direction of the prior successful search. On the other hand, it can still change the search directions when the assumption of monotonic matching error surface is not totally valid. 
         [0076]    Please refer to  FIG. 15 .  FIG. 15  is a flowchart illustrating the MD-GRPS algorithm of the present invention. Please refer to  FIG. 16 .  FIG. 16  is a diagram illustrating the search order of possible mutation points of MD-GRPS algorithm of the present invention. As shown in  FIG. 16 , “P” represents the previous successful mutation direction, and “C” represents the current parent point. “PP” represents the previously previous successful mutation direction. The search order of possible mutation points in MD-GRPS is:
   (1) st  the mutation point with the same direction as the previous successful mutation point;   (2) nd  the mutation point with the same direction as the previously previous successful mutation point;   (3) rd  the mutation point with the opposite direction as the previously previous successful mutation point; and   (4) th  the mutation point with the opposite direction as the previous successful mutation point.   
 
         [0081]    Likewise, by adopting the momentum-directed search order in the genetic pattern search, the GPHS algorithm can be converted into a momentum-directed one.  FIG. 17  shows the contour plot of RWF of the momentum-directed GPHS algorithm of the present invention. Please refer to  FIG. 18 .  FIG. 18  is a flowchart of the momentum-directed GPHS (MD-GPHS) algorithm of the present invention. The search order of possible mutation points in MD-GPHS algorithm is shown in  FIG. 19 . 
         [0082]    Additionally, the motion vector variance mentioned in the present invention is only illustrated for better understanding. However, any other motion vector related index can be utilized instead, e.g. motion vector standard deviations, or other mathematically equivalent or approximate index. 
         [0083]    To sum up, the present invention provides a mathematical model of pattern search algorithms, and more particularly, a refined mathematical model for genetic pattern search algorithms. In the refined model of the present invention, refined weighting function (RWF) is defined as the average number of search points required by a search algorithm on a SQM matching error surface and is proposed as a better replacement for the weighting function (WF). When the behavior of a genetic pattern search algorithm is described more precisely, it is understood better on how a genetic pattern search works. Based on such insights, a general way to further improve the performance of genetic pattern searches is given by the present invention. Two momentum-directed genetic pattern search algorithms are devised as well. Moreover, when the RWF is adopted in the model to predict the performance of a new genetic search algorithm, the prediction accuracy is increased. 
         [0084]    Those skilled in the art will readily observe that numerous modifications and alterations of the device and method may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.