Motion estimation method using multilevel succesive elimination algorithm

Abstract

The present invention provides a motion estimation method using a multilevel successive elimination algorithm. The present invention includes the steps of: a) selecting an initial candidate block among a plurality of candidate blocks in an image frame for computing an initial SAD; b) selecting four vertex candidate blocks placed at vertexes of a imaginary perfect square based on the initial candidate block as the center of the imaginary perfect square; c) extracting elimination levels of the four vertex candidate blocks by performing the MSEA; d) predicting elimination levels for side candidate blocks which are located at sides of the perfect square based on a spatial correlation between elimination levels of candidate blocks and the extracted elimination levels of the four vertex candidate blocks; and e) extracting elimination levels of the side candidate blocks by performing the MSEA based on the predicted elimination level.

1 . A method for performing motion estimation of a moving image by using a multilevel successive elimination algorithm (MSEA), the method comprising: 
 a) predicting an elimination level of a candidate block using elimination levels of predetermined neighboring blocks; and    b) extracting an elimination level of the candidate block by performing the MSEA from the predicted elimination level.    
   
   
       2 . The method as recited in  claim 1 , wherein the elimination levels of predetermined neighboring blocks are extracted by performing the MSEA.  
   
   
       3 . The method as recited in  claim 2 , wherein the predetermined neighboring blocks are vertex candidate blocks of a rectangle whose center is an initial block.  
   
   
       4 . The method as recited in  claim 3 , wherein the rectangle comprises a square.  
   
   
       5 . The method as recited in  claim 3 , wherein the candidate block is one of a plurality of side candidate blocks which are located at the sides of the rectangle.  
   
   
       6 . The method as recited in  claim 5 , further comprising: 
 c) selecting vertex candidate blocks of an expanded rectangle from the rectangle;    d) computing elimination levels of the vertex candidate blocks of the expanded rectangle by performing the MSEA.    e) performing steps a) and b) for predicting elimination levels of side candidate blocks of the expanded rectangle using the computed levels of the vertex candidate blocks and extracting elimination levels of the side candidate blocks of the expanded rectangle.    
   
   
       7 . The method as recited in  claim 6 , wherein the expanded rectangle is formed by blocks located one block away from the vertex candidate blocks and corresponding side candidate blocks.  
   
   
       8 . The method as recited in  claim 5 , wherein the elimination levels of the side candidate blocks are predicted by selecting the lower elimination level between the elimination levels of two corresponding vertex candidate blocks, wherein the two corresponding vertex candidate blocks are two end points of the side including the side candidate blocks.  
   
   
       9 . The method as recited in  claim 7 , further comprising: 
 f) predicting elimination levels of remained candidate blocks in a search range of the image frame which do not have extracted elimination level using the extracted elimination levels of neighboring candidate blocks; and    g) extracting elimination levels of the remained candidate blocks by performing the MSEA from the predicted elimination levels of them.    
   
   
       10 . The method as recited in  claim 9 , wherein the elimination levels of remained candidate blocks in the step e) are predicted by selecting the lower elimination level between elimination levels of two neighboring candidate blocks in the direction of diagonal or straight lines.  
   
   
       11 . A computer readable recording medium storing instructions for executing a moving image motion estimation method of a moving image using a multilevel successive elimination algorithm (MSEA), the moving image motion estimation method comprising: 
 a) determining a preliminary elimination level of a candidate block using already computed elimination levels of neighboring blocks; and    b) obtaining an elimination level of the candidate block by performing the MSEA with use of the preliminary elimination level.    
   
   
       12 . A method of performing motion estimation of a moving image using a multilevel successive elimination algorithm (MSEA), the method comprising: 
 determining a preliminary elimination level of a candidate block using known elimination levels of neighboring blocks; and    obtaining an elimination level of the candidate block by performing the MSEA with use of the preliminary elimination level.    
   
   
       13 . The method of  claim 12 , wherein obtaining the elimination level of the candidate block comprises performing the MSEA at an elimination level which is the same as or greater than the preliminary elimination level.  
   
   
       14 . The method of  claim 12 , wherein the known elimination levels of neighboring blocks are obtained by performing the MSEA.  
   
   
       15 . The method of  claim 12 , wherein the candidate block is located between two neighboring blocks.  
   
   
       16 . The method of  claim 15 , wherein the smaller of the known elimination levels of the two neighboring blocks is determined as the preliminary elimination level of the candidate block.  
   
   
       17 . The method of  claim 12 , wherein the obtained elimination level of the candidate block is not greater than the greater of the known elimination levels of the neighboring blocks.  
   
   
       18 . The method of  claim 12 , further comprising repeating the steps of determining and obtaining with regard to another candidate block.  
   
   
       19 . The method of  claim 18 , wherein the other candidate block is chosen from a plurality of blocks, which forms boundaries of a first rectangle in the image.  
   
   
       20 . The method of  claim 19 , wherein if the elimination level is obtained for all of the plurality of blocks, the other candidate block is chosen from another plurality of blocks, which forms boundaries of a second rectangle surrounding the first rectangle.