Device and method for performing half-pixel accuracy fast search in video coding

Abstract

A half-pixel accuracy fast search algorithm in video coding performs a hierarchical search method for motion, which initially searches integer accuracy motion vector and then continues its search sub-pixel accuracy over surrounding reconstructed sub-pixels of the integer motion vector. The term hierarchical connotes that the algorithm first calculates a minimum integer pixel location and then performs a sub-integer pixel search. The present invention obtains the integer pixel value with the lowest MAD value and then interpolates conjugate half-pixel values in a first direction. The algorithm determines which half-pixel value yields the lowest MAD value and then interpolates conjugate half-pixel values in a second direction from the previously calculated minimum MAD half-pixel location from the first direction.

What is claimed is:  
     
         1 . A method of obtaining a motion vector between a first macroblock contained in a first frame and a second macroblock contained in a second frame of video image data comprising: 
 at an integer pixel location having a lowest mean of absolute difference (“MAD”) value in the second frame relative to the first frame,    identifying a first conjugate sub-pixel value in a first direction having a lowest first direction MAD value;    identifying a second conjugate sub-pixel value in a second direction having a lowest second direction MAD value; and    determining a motion vector representing the distance between the first macroblock and the second macroblock using the integer pixel location and a sub-integer pixel location, wherein the sub-pixel location is obtained from the first conjugate sub-pixel value and the second conjugate sub-pixel value having the lowest MAD value.    
     
     
         2 . The method according to  claim 1 , wherein identifying a first conjugate sub-pixel value further comprises: 
 performing bi-linear interpolation to determine a first and a second half-pixel value in the first direction centered on the integer pixel location, the first and the second half-pixel values being conjugally related;    determining a MAD value at each of the first and second half-pixel locations; and    comparing the MAD values to determine the half-pixel location having the lowest MAD value in the first direction.    
     
     
         3 . The method according to  claim 1  wherein identifying a second conjugate sub-pixel value further comprises: 
 performing bi-linear interpolation to determine a first and a second half-pixel value in the second direction centered on the integer pixel location, the first and the second half-pixel values being conjugally related;  
 determining a MAD value at each of the first and the second half-pixel locations; and  
 comparing the MAD values to determine the half-pixel location having the lowest MAD value in the second direction.  
 
     
     
         4 . The method according to  claim 1  further comprising: 
 performing bi-linear interpolation to determine a first and a second half-pixel value in the second direction centered on the first conjugate sub-pixel value in the first direction having the lowest first direction MAD value, the first and the second half-pixel values in the second direction being conjugally related;  
 determining a MAD value at each of the first and the second half-pixel locations in the second direction; and  
 comparing the MAD values to determine the half-pixel location having the lowest MAD value in the second direction.  
 
     
     
         5 . The method according to  claim 1  wherein determining the motion vector further comprises: 
 generating an integer motion vector using the integer pixel location;  
 generating a sub-pixel motion vector using the sub-pixel location; and  
 generating a final motion vector by adding the integer motion vector to the sub-pixel motion vector.  
 
     
     
         6 . The method according to  claim 2  further comprising: 
 performing bi-linear interpolation to determine a first and a second half-pixel value in the second direction centered on the half-pixel location having the lowest MAD value in the first direction, the first and the second half-pixel values in the second direction being conjugally related;  
 determining a MAD value at each of the first and the second half-pixel locations in the second direction; and  
 comparing the MAD values to determine the half-pixel location having the lowest MAD value in the second direction.  
 
     
     
         7 . The method according to  claim 1  wherein the first direction is horizontal and parallel to an x axis and the second direction is vertical and parallel to a y-axis.  
     
     
         8 . The method according to  claim 1  wherein the first direction is perpendicular to the second direction.  
     
     
         9 . An apparatus for obtaining a motion vector between a first and a second frame of video image data having sub-pixel accuracy comprising: 
 a memory having a program and a processor, the program configured, when executed, to perform: 
 identifying a first conjugate sub-pixel value in a first direction having a lowest first direction MAD value;  
 identifying a second conjugate sub-pixel value in a second direction having a lowest second direction MAD value; and  
 determining a motion vector representing the distance between the first macroblock and the second macroblock using the integer pixel location and a sub-integer pixel location, wherein the sub-pixel location is obtained from the first conjugate sub-pixel value and the second conjugate sub-pixel value having the lowest MAD value.  
   
     
     
         10 . The apparatus according to  claim 9  wherein program is further configured to perform: 
 performing bi-linear interpolation to determine a first and a second half-pixel value in the first direction centered on the integer pixel location, the first and the second half-pixel values being conjugally related;  
 determining the MAD value at each of the first and second half-pixel locations; and  
 comparing the MAD values to determine the half-pixel location having the lowest MAD value in the first direction.  
 
     
     
         11 . The apparatus according to  claim 10  wherein program is further configured to perform: 
 performing bi-linear interpolation to determine a first and a second half-pixel value in the second direction centered on the half-pixel location having the lowest MAD value in the first direction, the first and the second half-pixel values in the second direction being conjugally related;  
 determining a MAD value at each of the first and the second half-pixel locations in the second direction; and  
 comparing the MAD values to determine the half-pixel location having the lowest MAD value in the second direction.  
 
     
     
         12 . A computer program comprising: 
 a computer-usable medium having program components embodied therein, when executed by a processor, for obtaining a motion vector having half-pixel accuracy between a first and a second frame of video image data, the computer usable medium comprising: 
 at an integer pixel location having a lowest mean of absolute difference (“MAD”) value in the second frame relative to the first frame,  
 a component of the program configured to identify a first conjugate sub-pixel value in a first direction having a lowest first direction MAD value;  
 a component of the program configured to identify a second conjugate sub-pixel value in a second direction having a lowest second direction MAD value; and  
 a component of the program configured to determine a motion vector representing the distance between the first macroblock and the second macroblock using the integer pixel location and a sub-integer pixel location, wherein the sub-pixel location is obtained from the first conjugate sub-pixel value and the second conjugate sub-pixel value having the lowest MAD value.  
   
     
     
         13 . The computer program according to  claim 12 , wherein the component of the program configured to identify the first conjugate sub pixel value further comprises: 
 a component of the program configured to perform bi-linear interpolation to determine a first and a second half-pixel value in the first direction centered on the integer pixel location, the first and the second half-pixel values being conjugally related;    a component of the program configured to determine a MAD value at each of the first and second half-pixel locations; and    a component of the program configured to compare the MAD values to determine the half-pixel location having the lowest MAD value in the first direction.    
     
     
         14 . The computer program according to  claim 13 , wherein the component of the program configured to identify the second conjugate sub pixel value further comprises: 
 a component of the program configured to perform bi-linear interpolation to determine a first and a second half-pixel value in the second direction centered on the half-pixel location having the lowest MAD value in the first direction, the first and the second half-pixel values in the second direction being conjugally related;    a component of the program configured to determine a MAD value at each of the first and the second half-pixel locations in the second direction; and    a component of the program configured to compare the MAD values to determine the half-pixel location having the lowest MAD value in the second direction.    
     
     
         15 . A device for obtaining a motion vector between a first macroblock contained in a first frame and a second macroblock contained in a second frame of video image data comprising: 
 a memory device that stores executable program codes;    a processor that accesses the memory device and executes the instructions contained therein, the processor comprising: 
 a component configured to identify a first conjugate sub-pixel value in a first direction having a lowest first direction MAD value;  
 a component configured to identify a second conjugate sub-pixel value in a second direction having a lowest second direction MAD value; and  
 a component configured to determine a motion vector representing the distance between the first macroblock and the second macroblock using the integer pixel location and a sub-integer pixel location, wherein the sub-pixel location is obtained from the first conjugate sub-pixel value and the second conjugate sub-pixel value having the lowest MAD value.  
   
     
     
         16 . The device according to  claim 15  wherein the component configured to identify the first conjugate sub pixel value further comprises: 
 a component configured to perform bi-linear interpolation to determine a first and a second half-pixel value in the first direction centered on the integer pixel location, the first and the second half-pixel values being conjugally related;  
 a component configured to determine a MAD value at each of the first and second half-pixel locations; and  
 a component configured to compare the MAD values to determine the half-pixel location having the lowest MAD value in the first direction.  
 
     
     
         17 . The device according to  claim 16  wherein the component configured to identify the second conjugate sub-pixel value further comprises: 
 a component configured to perform bi-linear interpolation to determine a first and a second half-pixel value in the second direction centered on the half-pixel location having the lowest MAD value in the first direction, the first and the second half-pixel values in the second direction being conjugally related;  
 a component configured to determine a MAD value at each of the first and the second half-pixel locations in the second direction; and  
 a component configured to compare the MAD values to determine the half-pixel location having the lowest MAD value in the second direction.  
 
     
     
         18 . A fast search sub-pixel accuracy method for obtaining a motion vector between successive frames of video image data, the method comprising the steps of: 
 determining a first macroblock of a first frame comprising a plurality of pixels arranged in a two-dimensional array;    selecting a second macroblock of a second frame comprising a plurality of pixels arranged in a two-dimensional array having the lowest mean of absolute differences (MAD) value between the first and the second macroblocks;    determining a minimum pixel location having the lowest MAD value in the second macroblock;    calculating conjugate sub-pixel values in a first direction centered on the minimum pixel location;    determining the conjugate sub-pixel value in the first direction having the lowest MAD value;    calculating conjugate sub-pixel values in a second direction centered on the sub-pixel having the lowest MAD value in the first direction;    determining the conjugate sub-pixel value in the second direction having the lowest MAD value; and    determining a motion vector for the macroblock representing the distance between the first macroblock and the second macroblock using the integer pixel location and the sub integer pixel location having the lowest MAD values.    
     
     
         19 . The fast search sub-pixel method according to  claim 18 , wherein the step of determining the motion vector further comprises the steps of: 
 generating an integer motion vector using the integer pixel location;    generating a sub-pixel motion vector using the sub-pixel location; and    generating a motion vector by adding the integer motion vector to the sub-pixel motion vector.    
     
     
         20 . The fast search sub-pixel method according to  claim 18 , wherein the first direction is in a horizontal direction parallel to an x axis and the second direction is in a vertical direction parallel to a y axis of a grid.  
     
     
         21 . The fast search sub-pixel method according to  claim 18 , wherein the step of calculating conjugate sub-pixel values further comprises the step of performing bilinear interpolation to determine a half-pixel value.  
     
     
         22 . The fast search sub-pixel method according to  claim 18 , wherein the step of determining the motion vector for the macroblock further comprises the step of: 
 determining an integer pixel motion vector for the minimum pixel location;    determining a sub-pixel motion vector for the conjugate sub-pixel in the second direction having the lowest MAD value; and    adding the integer pixel motion vector together with the sub-pixel motion vector.    
     
     
         23 . The fast search sub-pixel method according to  claim 18 , wherein the steps of determining the conjugate sub-pixel value having the lowest MAD value further comprises the step of comparing the conjugate sub-pixel values with the integer pixel value to determine the lowest MAD value.  
     
     
         24 . A method of obtaining a motion vector between a first macroblock contained in a first frame and a second macroblock contained in a second frame of video image data comprising: 
 at an integer pixel location having a lowest mean of absolute difference (“MAD”) value in the second frame relative to the first frame, determining a first sub-pixel value in a first direction having a lowest first direction MAD value;    determining a second sub-pixel value in a second direction centered on the first sub-pixel value, the second sub-pixel value having a lowest second direction MAD value; and    determining a motion vector representing the distance between the first macroblock and the second macroblock using the integer pixel location and the second sub-integer pixel location.    
     
     
         25 . A method of obtaining a motion vector between a first macroblock contained in a first frame and a second macroblock contained in a second frame of video image data comprising: 
 at an integer pixel location having a lowest mean of absolute difference (“MAD”) value in the second frame relative to the first frame, determining a first sub-pixel value in a first diagonal direction having a lowest first direction MAD value;    determining a second sub-pixel value in a second diagonal direction centered on the first sub-pixel value, the second sub-pixel value having a lowest second direction MAD value; and    determining a motion vector representing the distance between the first macroblock and the second macroblock using the integer pixel location and the second sub-integer pixel location.    
     
     
         26 . A method of obtaining a motion vector between a first macroblock contained in a first frame and a second macroblock contained in a second frame of video image data in a video recorder, the method comprising: 
 at an integer pixel location having a lowest mean of absolute difference (“MAD”) value in the second frame relative to the first frame, determining a first sub-pixel value in a first direction having a lowest first direction MAD value;    determining a second sub-pixel value in a second direction centered on the first sub-pixel value, the second sub-pixel value having a lowest second direction MAD value;    determining a motion vector representing the distance between the first macroblock and the second macroblock using the integer pixel location and the second sub-integer pixel location; and    storing the motion vector on a storage device.