Abstract:
An integrated circuit capable of video processing and a method thereof is disclosed. The integrated circuit comprises an image information generator, an adaptive motion vector (MV) candidate generator, and a block matching unit. The image information generator receives reference and current video data to determine image information. The adaptive MV candidate generator, coupled to the image information generator, receives the reference and current video data to generate spatial and temporal MV candidates, and generates an updated MV candidate based on the image information. The block matching unit, coupled to the adaptive MV candidate generator, receives the spatial and temporal MV candidates and the updated MV candidate and performs block matching to determine an output MV therefrom.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The invention relates in general to video processing, and in particular, to a motion estimation method and an integrated circuit capable of video processing. 
         [0003]    2. Description of the Related Art 
         [0004]    Block-based video coding standards such as MPEG 1/2/4 and H.26x achieve data compression by reducing temporal redundancies between video frames and spatial redundancies within a video frame. The video processing includes all processes using motion information and image information, such as video coding and frame rate conversion. 
         [0005]    Each video frame comprises an array of pixels. A macroblock (MB) is typically composed of 16×16 pixels, and a coding unit can be a complete MB or sub-partitioned blocks such as 16×8, 8×16, 8×8, 8×4, 4×8, or 4×4. It is common to estimate movement of an image between frames on a block basis, referred to as motion estimation. Motion estimation typically comprises comparing a macroblock in the current frame to a number of macroblocks from reference frames for similarity. The spatial displacement between the macroblock in the current video frame and the most similar macroblock in the reference frames is represented by a motion vector (MV). Motion vectors may be estimated to within a fraction of a pixel, by interpolating pixels from the reference frames. 
         [0006]      FIG. 1  depicts the process of motion estimation, where  1   a  is a current video frame and  1   b  is a previous (reference) video frame. Motion estimation involves searching object  10   a  of a current video frame  1   a  in a search window SW of a previous video frame  1   b  to find an object  10   b  being a best matched object. The spatial displacement from a collocated position of object  10   a  to  10   b  is the motion vector. 
         [0007]    Motion estimation is aimed to search for a block in a predetermined search range with the lowest estimation error, and obtain a motion vector. Existing methods include full search which computes all possible motion vector candidates in the search range, 3D recursive search which uses a random factor to update motion vectors, and some fixed scenario search methods. These motion estimation methods are either having a slow convergence rate for the motion vector estimation, uncontrollable motion estimation due to the random factor, or not suitable for true motion estimation. 
       BRIEF SUMMARY OF THE INVENTION 
       [0008]    A detailed description is given in the following embodiments with reference to the accompanying drawings. 
         [0009]    An integrated circuit capable of video processing comprises an image information generator, an adaptive motion vector (MV) candidate generator, and a block matching unit. The image information generator receives reference and current video data to determine image information. The adaptive MV candidate generator, coupled to the image information generator, receives the reference and current video data to generate a set of MV candidates, and generates an updated MV candidate based on the image information. The block matching unit, coupled to the adaptive MV candidate generator, receives the MV candidates regarding to the updated MV candidate to determine an output MV therefrom. 
         [0010]    According to another embodiment of the invention, an integrated circuit capable of video processing is disclosed, comprising an image information generator, an adaptive motion vector MV candidate generator, and a block matching unit. The image information generator receives reference and current video data to determine image information. The adaptive MV candidate generator, coupled to the image information generator, determines a search range size based on the image information, and receives the reference and current video data to generate MV candidates according to the search range size. The block matching unit, coupled to the adaptive MV candidate generator, receives the MV candidates and performs block matching to determine an output MV therefrom. 
         [0011]    According to yet another embodiment of the invention, a method for video processing is provided, comprising receiving reference and current video data to determine image information, receiving the reference and current video data to generate MV candidates, generating an updated MV candidate based on the image information, and receiving the spatial and temporal MV candidates with regards to the updated MV candidate to perform block matching to determine an output MV. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]    The invention can be more fully understood by reading the subsequent detailed description and examples with references made to the accompanying drawings, wherein: 
           [0013]      FIG. 1  illustrates a motion estimation process. 
           [0014]      FIG. 2  shows MV candidate selection using a 3-step search algorithm. 
           [0015]      FIG. 3  depicts MV candidate selection using a 3-D recursive search algorithm. 
           [0016]      FIG. 4  is a block diagram of an exemplary apparatus for motion estimation according to the invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0017]    The following description is of the best-contemplated mode of carrying out the invention. This description is made for the purpose of illustrating the general principles of the invention and should not be taken in a limiting sense. The scope of the invention is best determined by reference to the appended claims. 
         [0018]    Motion estimation of video encoding may be implemented by various approaches such as a full search, 3-step search, and 3-dimentional (3-D) recursive search algorithms by assuming various certain spatial-invariant motion models to maximize temporal correlation. 
         [0019]    The full search algorithm utilizes all possible MV candidates in a predetermined search range to search for the minimum spatial estimation error thereform, thus is computation-intensive and time-consuming, and not a feasible solution for true motion estimation applications. 
         [0020]    The 3-step search algorithm conducts motion estimation 3 times with 3 search windows with difference window sizes (search range size), and each search is based on the reference search result and comprises a refined resolution over a preceding resolution.  FIG. 2  shows MV candidate selection using a 3-step search algorithm, comprising a first search window SW 21 , second search window SW 22 , and third search window SW 23 . Motion vector MV out1  is computed in the first round of motion estimation based on a first search window SW 21  with coarse pixel resolution, thus a second round of motion estimation is conducted in a refined search window SW 22 , producing a second motion vector MV out2 , in turn to generate an even more precise motion vector MV out3  in a third search window SW 23 . The 3-step search algorithm is more efficient than the full search algorithm due to less MV candidate generation, requiring less data computation and rendering a faster convergent speed to produce the output motion vector. 
         [0021]    The 3-D recursive search is a block based motion estimation algorithm employing a small number of MV candidates obtained from spatio-temporal predictions. The 3-D recursive search algorithm assumes objects are smaller than block, so that the MV from a neighboring block is a good estimate for the MV candidate of the current block. The blocks are processed in a certain order, for example, from left to right and top to bottom, so that some neighboring blocks that have already been estimated for MVs can provide spatial MV candidates for the current block, while the other blocks that have not been processed take the MVs from the reference frame to provide a temporal MV candidate for the current block.  FIG. 3  depicts MV candidate selection using the 3-D recursive search algorithm, comprising spatial MV candidates S a  through S d  and temporal MV candidates Ta through Td. Along with the spatial and temporal MV candidates there are also updated MV candidates generated by random vector MV ramd  to provide non-constant motion of the objects. The values of the update vectors indicate the movement variation of the objects from frame to frame, large update vectors result in large movement, and vice versa. For each MV candidate the motion estimation error is calculated. The candidate with the lowest motion estimation error is chosen as the output motion vector for that block. The algorithm uses a normal raster scan order to go through the blocks. 
         [0022]      FIG. 4  is a block diagram of an exemplary apparatus for motion estimation according to the invention, comprising image information generator  40 , adaptive MV candidate generator  42 , and block matching unit  44 . Image information generator  40  is coupled to adaptive MV candidate generator  42 , and subsequently to block matching unit  44 . 
         [0023]    Image information generator  40  receives reference and current video data D frame  to determine image information. The image information may be a measure or may be related to one or more of the following: motion complexity, motion speed, block difference, global motion direction, texture, and image complexity. 
         [0024]    For example, the image information may be a measure of motion complexity determined by a sum of differences between motion vectors of video data D frame , and is provided in Eq(1). The value of the motion complexity indicates a variance of motion vectors in a frame, for example, this value equals to zero if all elements in the frame move in the same direction with the same speed. A large motion complexity indicates a more complicated movement within the frame. 
         [0000]        E (| MV   nm,x   −MV   (n-1)m,x |)+(| MV   nm,y   −MV   (n-1)m,y |)  Eq(1). 
         [0000]    where MV nm,x  and MV nm,y  are motion vectors of the reference video data frame at block (n, m) along x and y directions, and MV (n-1)m,x  and MV (n-1)m,y  are motion vectors of the reference video data frame at block (n−1, m) along x and y directions in a region or in a frame. 
         [0025]    The image information may indicate a motion speed of a frame, for example, an averaged motion speed can be determined by a sum of motion vectors of the current video data. The motion speed may be computed using Eq(2) and Eq(3). A larger value of N nm  indicates more objects in a frame have a fast movement. 
         [0000]    
       
         
           
             
               
                 
                   
                     N 
                     
                       n 
                        
                       
                           
                       
                        
                       m 
                     
                   
                   = 
                   
                     ∑ 
                     
                       ( 
                       
                         
                            
                           
                             MV 
                             
                               
                                 n 
                                  
                                 
                                     
                                 
                                  
                                 m 
                               
                               , 
                               x 
                             
                           
                            
                         
                         + 
                         
                            
                           
                             MV 
                             
                               
                                 n 
                                  
                                 
                                     
                                 
                                  
                                 m 
                               
                               , 
                               y 
                             
                           
                            
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Eq 
                    
                   
                       
                   
                    
                   
                     ( 
                     2 
                     ) 
                   
                 
               
             
             
               
                 
                   
                     ∑ 
                     
                       N 
                       mn 
                     
                   
                   , 
                   
                     
                       N 
                       mn 
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               1 
                               , 
                             
                           
                           
                             
                               
                                  
                                 
                                   MV 
                                   
                                     n 
                                      
                                     
                                         
                                     
                                      
                                     m 
                                   
                                 
                                  
                               
                               ≥ 
                               
                                 th 
                                 spd 
                               
                             
                           
                         
                         
                           
                             
                               0 
                               , 
                             
                           
                           
                             
                               
                                  
                                 
                                   MV 
                                   
                                     n 
                                      
                                     
                                         
                                     
                                      
                                     m 
                                   
                                 
                                  
                               
                               &lt; 
                               
                                 th 
                                 spd 
                               
                             
                           
                         
                       
                       } 
                     
                   
                 
               
               
                 
                   Eq 
                    
                   
                       
                   
                    
                   
                     ( 
                     3 
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    where MV nm,x  and MV nm,y  are motion vectors of the video data frame along x and y directions, N nm  is the motion speed, and th pd  is a motion speed threshold. 
         [0026]    In another embodiment, the image information is a block difference determined by a sum of differences between pixels of macroblocks of the reference and current video data, expressed by Eq(4). 
         [0000]    
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       
                         ( 
                         
                           x 
                           , 
                           y 
                         
                         ) 
                       
                       ∈ 
                       block 
                     
                   
                    
                   
                      
                     
                       
                         P 
                         
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                           , 
                           prev 
                         
                       
                       - 
                       
                         P 
                         
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                           , 
                           curr 
                         
                       
                     
                      
                   
                 
               
               
                 
                   Eq 
                    
                   
                       
                   
                    
                   
                     ( 
                     4 
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    where P (x,y),prev  is a pixel in the reference video frame, and P (x,y),curr  is a pixel in the current video frame. The low value of the block difference represents large similarity between the current and reference video frames. 
         [0027]    The image information may also be represented by a global motion direction, where several motion vectors are taken from a number of predetermined locations in a block of the reference video frame, say 9 locations, the motion vectors are then sorted out in a low-to-high order and a median is identified thereform as the global motion direction of the block. 
         [0028]    Some other image information examples may relate to texture or complexity of image. Examples of the image information and their derivation equations and algorithms mentioned above are only some of the possible implementations for the present invention, and should not be interpreted as a limitation to the scope of invention. 
         [0029]    Adaptive MV candidate generator  42  receives image information from image information generator  40  to generate MV candidates {MV 1 , MV 2 , . . . , MV n } using a motion estimation algorithm. In the example of 3-D recursive search, adaptive MV candidate generator  42  receives reference and/or current video data D frame  to generate spatial and temporal MV candidates, and receives the image information to generate an updated MV candidate. In other embodiments of full search and 3-step search algorithms, adaptive MV candidate generator  42  determines a search range size based on the image information, and receives reference and/or current video data D frame  to generate MV candidates according to the search range size. 
         [0030]    In the case of 3-D recursive search, adaptive MV candidate generator  42  utilizes reference and current video frames D frame  to provide spatial and temporal MV candidates, and in addition, adaptive MV candidate generator  42  may receive the image information including motion complexity, motion speed, block difference, or global motion direction information disclosed in the preceding paragraphs to generate one or more updated MV candidates. For example, adaptive MV candidate generator  42  increases the degree of predicted object motion for a simpler reference video data frame and decreases the predicted object motion for the complex reference video data frame through the updated MV candidates. In practice, adaptive MV candidate generator  42  increases the value of at least one updated MV candidate when the motion complexity is less than a motion complexity threshold, and decreases the value of at least one updated MV candidate when the motion complexity exceeds or equals to the motion complexity threshold. In an embodiment, image information carries motion speed information, adaptive MV candidate generator  42  adaptively increases the predicted object motion with feedback of a fast motion speed. An implementation of adaptive MV candidate generator  42  decreases the value of at least one updated MV candidate when the motion speed is less than motion speed threshold th spd , and increases the updated MV candidate when the motion speed exceeds or equals to motion speed threshold th spd . In other embodiments, the image information represents block differences, adaptive MV candidate generator  42  adaptively adjusts the predicted motion with the block difference between the current and reference video frames. Since a small block difference reflects the current video frame is very similar to the reference video frame, adaptive MV candidate generator  42  decreases the updated MV candidate when the block difference is less than a block difference threshold, and increases the MV updated MV candidate when the block difference exceeds or equals to the block difference threshold. When the image information indicates a global motion direction, adaptive MV candidate generator  42  decreases the updated MV candidate when the global motion speed is less than a global motion speed threshold, and increases the updated MV candidate when the global motion speed exceeds or equals to the global motion speed threshold. 
         [0031]    In some embodiments, adaptive MV candidate generator  42  adjusts the updated MV candidates with a predetermined difference or gain. For example, adaptive MV candidate generator  42  generates a random vector, and adds a predetermined difference to the random vector or subtracts the predetermined difference from the random vector to generate the updated MV candidates according to the image information. Adaptive MV candidate generator  42  may also generate a random vector, and multiply a predetermined gain with the random vector or divide the random vector by the predetermined gain according to the image information, to generate the updated MV candidates. 
         [0032]    In the cases of full search and 3-step search, adaptive MV candidate generator  42  adjusts search range size to generate MV candidates for the MVs to be searched from in accordance with the image information. When the image information carries information of motion complexity, adaptive MV candidate generator  42  conducts motion estimation in a large search range for a simpler reference video data frame and a smaller search range for more complex reference video data frame, since a large motion complexity value suggests large motion variance within a frame, and a small search range size provides smaller resolution and better motion estimation. For example, adaptive MV candidate generator  42  increases the search range size when the motion complexity is less than a motion complexity threshold, and decreases the search range size when the motion complexity exceeds or equals to the motion complexity threshold. When the image information represents the motion speed, adaptive MV candidate generator  42  adaptively increases the search range size with a fast motion speed. In an embodiment, adaptive MV candidate generator  42  decreases the search range size when the motion speed is less than motion speed threshold th spd , and increases the search range size when the motion speed exceeds or equals to motion speed threshold th spd . In other embodiments, when the image information carries information of block differences within a frame or between frames, adaptive MV candidate generator  42  adaptively adjusts the search range size with the block differences. An embodiment of the image information is an average of block differences between a current and a reference frame, and a small block difference average suggests most object motion is within a small range, adaptive MV candidate generator  42  decreases the search range size when the block difference average is less than a block difference threshold, and increases the MV search range size when the block difference average exceeds or equals to the block difference threshold. In another embodiment, the image information is an average of block differences within a frame, and a large block difference average suggests a complicated image or texture, and adaptive MV candidate generator  42  decreases the search range size when the block difference average exceeds or equal to the block difference threshold and vice versa. When the image information is a global motion direction, adaptive MV candidate generator  42  decreases the search range size when the global motion speed is less than a global motion speed threshold, and increases the search range size when the global motion speed exceeds or equals to the global motion speed threshold. 
         [0033]    In the full search algorithm, adaptive MV candidate generator  42  simply adjusts the search range size to increase or decrease an amount of the MV candidates for selecting an output motion vector MV out  through block matching. In the case of 3-step search, adaptive MV candidate generator  42  modifies the search range size by adjusting video data resolution in each search window. Adaptive MV candidate generator  42  may increase the video data resolution of each search window by 1 step unit to increase the search range size. For example, when taking search window size MV k+2 , MV k+1 , MV k  as the reference search range, the motion estimation is conducted in the increased search range size MV k+3 , MV k+2 , MV k+1  for the current video frame. Likewise, adaptive MV candidate generator  42  may decrease the video data resolution of each search window by 1 step unit to decrease the search range size, i.e., search window size MV k+1 , MV k , MV k−1 . The step unit may be a pixel data, a minimal video data base, or a predetermined data base. 
         [0034]    Some embodiments of adaptive MV candidate generator  42  add updated MV candidates to a set of MV candidates generated by a motion estimation algorithm, and some other embodiments of adaptive MV candidate generator  42  replace certain MV candidates of the set of MV candidates generated by the motion estimation algorithm by the updated MV candidates. For example, adaptive MV candidate generator  42  generates 5 MV candidates derived using 3D recursive search, and then increases to 8 MV candidates after image information feedback. In other embodiments, adaptive MV candidate generator  42  may generate 3 updated MV candidates using 3D recursive search in place of 3 out of the original 8 MV candidates. 
         [0035]    Block matching unit  44  receives the MV candidates from adaptive MV candidate generator  42 , for example, including the spatial and temporal MV candidates and updated MV candidates (e.g. 3-D recursive search example) or all MV candidates (e.g. full search and 3-step search examples). In embodiments of 3-D recursive search, block matching unit  44  receives the updated MV candidates adaptively adjusted according to the image information and the spatial and temporal MV candidates independent of the image information and it applies block matching techniques to these MV candidates, for examples, a sum-of-absolute difference (SAD), or a mean-squared-error (MSE). Block matching unit  44  then selects a matched block with a minimum difference or error or a maximum similarity, and outputs the motion vector MV out  corresponding to the matched block. In the embodiments of full search and 3-step search, block matching unit  44  receives all MV candidates computed in the search range adaptable according to the image information and performs block matching, and determines a matched block with a minimum difference or maximum similarity from the candidate blocks, and outputs its corresponding motion vector MV out . 
         [0036]    While the invention has been described by way of example and in terms of preferred embodiment, it is to be understood that the invention is not limited thereto. To the contrary, it is intended to cover various modifications and similar arrangements (as would be apparent to those skilled in the art). Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.