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

Abstract

Methods, devices, and systems for performing half-pixel accuracy fast search in video coding are disclosed. In one embodiment, a method 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 comprises determining 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 relative to the integer pixel location having a lowest first direction MAD value; identifying a second conjugate sub-pixel value in a second direction relative to the integer pixel location 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.

What is claimed is: 
     
         1 . A method 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:
 determining 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 relative to said integer pixel location having a lowest first direction MAD value;   identifying a second conjugate sub-pixel value in a second direction relative to said integer pixel location having a lowest second direction MAD value; and   determining a motion vector representing the distance between the first macroblock and the second macroblock using said integer pixel location and a sub-integer pixel location, wherein the sub-pixel location is obtained from said first conjugate sub-pixel value and said second conjugate sub-pixel value having the lowest MAD value.   
     
     
         2 . The method of  claim 1 , wherein said identifying a first conjugate sub-pixel value further comprises:
 performing bi-linear interpolation to determine a first and a second half-pixel value in said first direction centered on said integer pixel location, wherein said first and said second half-pixel values are conjugally related;   determining a MAD value at each of said first and said second half-pixel locations; and   comparing said MAD values to determine the half-pixel location having the lowest MAD value in said first direction.   
     
     
         3 . The method of  claim 1 , wherein said identifying a second conjugate sub-pixel value further comprises:
 performing bi-linear interpolation to determine a first and a second half-pixel value in said second direction centered on said integer pixel location, wherein said first and said second half-pixel values are conjugally related;   determining a MAD value at each of said first and said second half-pixel locations; and   comparing said MAD values to determine the half-pixel location having the lowest MAD value in said second direction.   
     
     
         4 . The method of  claim 1 , wherein said identifying a second conjugate sub-pixel value further comprises:
 performing bi-linear interpolation to determine a first and a second half-pixel value in said second direction centered on said first conjugate sub-pixel value in said first direction having said lowest first direction MAD value, wherein said first and said second half-pixel values in said second direction are conjugally related;   determining a MAD value at each of said first and said second half-pixel locations in said second direction; and   comparing said MAD values to determine the half-pixel location having the lowest MAD value in said second direction.   
     
     
         5 . The method of  claim 1 , wherein said determining a motion vector further comprises:
 generating an integer motion vector using said integer pixel location;   generating a sub-pixel motion vector using said sub-pixel location; and   generating a final motion vector by adding said integer motion vector to said sub-pixel motion vector.   
     
     
         6 . The method of  claim 2 , wherein said 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 said half-pixel location having the lowest MAD value in said first direction, wherein said first and said second half-pixel values in said second direction are conjugally related;   determining a MAD value at each of said first and said second half-pixel locations in said second direction; and   comparing said MAD values to determine the half-pixel location having the lowest MAD value in said second direction.   
     
     
         7 . The device of  claim 1 , wherein said first direction is horizontal and parallel to an x-axis, and said second direction is vertical and parallel to a y-axis. 
     
     
         8 . The device of  claim 1 , wherein said first direction is perpendicular to said second direction. 
     
     
         9 . 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 first component configured to determine an integer pixel location having a lowest mean of absolute difference (“MAD”) value in the second frame relative to the first frame;   a second component configured to identify a first conjugate sub-pixel value in a first direction relative to said integer pixel location having a lowest first direction MAD value;   a third component configured to identify a second conjugate sub-pixel value in a second direction relative to said integer pixel location having a lowest second direction MAD value; and   a fourth component configured to determine a motion vector representing the distance between the first macroblock and the second macroblock using said integer pixel location and a sub-integer pixel location, wherein the sub-pixel location is obtained from said first conjugate sub-pixel value and said second conjugate sub-pixel value having the lowest MAD value.   
     
     
         10 . The device of  claim 9 , wherein said second component is further configured to perform bi-linear interpolation to determine a first and a second half-pixel value in said first direction centered on said integer pixel location, wherein said first and said second half-pixel values are conjugally related; determine a MAD value at each of said first and said second half-pixel locations; and compare said MAD values to determine the half-pixel location having the lowest MAD value in said first direction. 
     
     
         11 . The device of  claim 9 , wherein said third component is further configured to perform bi-linear interpolation to determine a first and a second half-pixel value in said second direction centered on said integer pixel location, wherein said first and said second half-pixel values are conjugally related; determine a MAD value at each of said first and said second half-pixel locations; and compare said MAD values to determine the half-pixel location having the lowest MAD value in said second direction. 
     
     
         12 . The device of  claim 9 , wherein said third component is further configured to perform bi-linear interpolation to determine a first and a second half-pixel value in said second direction centered on said first conjugate sub-pixel value in said first direction having said lowest first direction MAD value, wherein said first and said second half-pixel values in said second direction are conjugally related; determine a MAD value at each of said first and said second half-pixel locations in said second direction; and compare said MAD values to determine the half-pixel location having the lowest MAD value in said second direction. 
     
     
         13 . The device of  claim 9 , wherein said fourth component is further configured to generate an integer motion vector using said integer pixel location; generate a sub-pixel motion vector using said sub-pixel location; and generate a final motion vector by adding said integer motion vector to said sub-pixel motion vector. 
     
     
         14 . The device of  claim 10 , wherein said third component is further configured to perform bi-linear interpolation to determine a first and a second half-pixel value in the second direction centered on said half-pixel location having the lowest MAD value in said first direction, wherein said first and said second half-pixel values in said second direction are conjugally related; determine a MAD value at each of said first and said second half-pixel locations in said second direction; and compare said MAD values to determine the half-pixel location having the lowest MAD value in said 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 processor coupled to a memory containing processor-executable instructions, wherein said processor is operable to:   determine an integer pixel location having a lowest mean of absolute difference (“MAD”) value in the second frame relative to the first frame;   identify a first conjugate sub-pixel value in a first direction relative to said integer pixel location having a lowest first direction MAD value;   identify a second conjugate sub-pixel value in a second direction relative to said integer pixel location having a lowest second direction MAD value; and   determine a motion vector representing the distance between the first macroblock and the second macroblock using said integer pixel location and a sub-integer pixel location, wherein the sub-pixel location is obtained from said first conjugate sub-pixel value and said second conjugate sub-pixel value having the lowest MAD value.   
     
     
         16 . The device of  claim 15 , wherein said processor is further configured to perform bi-linear interpolation to determine a first and a second half-pixel value in said first direction centered on said integer pixel location, wherein said first and said second half-pixel values are conjugally related; determine a MAD value at each of said first and said second half-pixel locations; and compare said MAD values to determine the half-pixel location having the lowest MAD value in said first direction. 
     
     
         17 . The device of  claim 15 , wherein said processor is further configured to perform bi-linear interpolation to determine a first and a second half-pixel value in said second direction centered on said integer pixel location, wherein said first and said second half-pixel values are conjugally related; determine a MAD value at each of said first and said second half-pixel locations; and compare said MAD values to determine the half-pixel location having the lowest MAD value in said second direction. 
     
     
         18 . The device of  claim 15 , wherein said processor is further configured to perform bi-linear interpolation to determine a first and a second half-pixel value in said second direction centered on said first conjugate sub-pixel value in said first direction having said lowest first direction MAD value, wherein said first and said second half-pixel values in said second direction are conjugally related; determine a MAD value at each of said first and said second half-pixel locations in said second direction; and compare said MAD values to determine the half-pixel location having the lowest MAD value in said second direction. 
     
     
         19 . The device of  claim 15 , wherein said processor is further configured to generate an integer motion vector using said integer pixel location; generate a sub-pixel motion vector using said sub-pixel location; and generate a final motion vector by adding said integer motion vector to said sub-pixel motion vector. 
     
     
         20 . The device of  claim 16 , wherein said processor is further configured to perform bi-linear interpolation to determine a first and a second half-pixel value in the second direction centered on said half-pixel location having the lowest MAD value in said first direction, wherein said first and said second half-pixel values in said second direction are conjugally related; determine a MAD value at each of said first and said second half-pixel locations in said second direction; and compare said MAD values to determine the half-pixel location having the lowest MAD value in said second direction.