Motion estimation method using orthogonal-sum block matching

Abstract

A method for determining a best match between a first pixel array in a picture currently being encoded and a plurality of second pixel arrays in a search region of a reference picture, wherein each of the first and second pixel arrays includes a plurality of rows and columns of individual pixel values. The method is designed to be performed in a motion estimation search engine of a digital video encoder, and includes the steps of producing a first orthogonal-sum signature of the first pixel array comprised of a set of horizontal sums representative of the sums of the individual pixel values of the rows of the first pixel array and a first set of vertical sums representative of the sums of the individual pixel values of the columns of the first pixel array; producing a plurality of second orthogonal-sum signatures for respective ones of at least selected ones of the plurality of second pixel arrays, each of the plurality of second orthogonal-sum signatures being comprised of a set of horizontal sums representative of the sums of the individual pixel values of the rows of a respective one of the second pixel arrays and a set of vertical sums representative of the sums of the individual pixel values of the columns of a respective one of the second pixel arrays; and, comparing the first orthogonal-sum signature with each of the second orthogonal-sum signatures in order to determine the best match between the first and second pixel arrays. In a disclosed embodiment, the first and second pixel arrays are either decimated or undecimated macroblocks having a structure defined by an MPEG standard, e.g., the MPEG-2 standard.

What is claimed is:  
     
       1. A method implemented in a motion estimation search engine for comparing a first pixel array having a plurality of rows and columns of individual pixel values, and a second pixel array having a plurality of rows and columns of individual pixel values, the method comprising the steps of: 
       summing the individual pixel values of each row of individual pixel values of the first pixel array to produce a first set of horizontal sums;  
       summing the individual pixel values of each column of individual pixel values of the first pixel array to produce a first set of vertical sums;  
       summing the individual pixel values of each row of individual pixel values of the second pixel array to produce a second set of horizontal sums;  
       summing the individual pixel values of each column of individual pixel values of the second pixel array to produce a second set of vertical sums;  
       wherein the first set of horizontal sums and the first set of vertical sums comprises a first set of orthogonal sums,  
       wherein the second set of horizontal sums and the second set of vertical sums comprises a second set of orthogonal sums, and,  
       comparing the first set of orthogonal sums and the second set of orthogonal sums in order to determine if the second pixel array is a best match to the first pixel array.  
     
     
       2. The method as set forth in  claim 1 , wherein the first pixel array comprises of an undecimated macroblock of a picture currently being encoded, and the second pixel array comprises an undecimated macroblock in a search region of a reference picture. 
     
     
       3. The method as set forth in  claim 1 , wherein the first pixel array comprises of a decimated macroblock of a picture currently being encoded, and the second pixel array comprises a decimated macroblock in a search region of a reference picture. 
     
     
       4. The method as set forth in  claim 1 , wherein the first and second pixel arrays are macroblocks having a structure defined by an MPEG standard. 
     
     
       5. A method implemented in a motion estimation search engine for determining a best match between a first pixel array in a picture currently being encoded and a plurality of second pixel arrays in a search region of a reference picture, wherein each of the first and second pixel arrays includes a plurality of rows and columns of individual pixel values, the method comprising the steps of: 
       providing a first orthogonal-sum signature of the first pixel array comprised of a set of horizontal sums representative of the sums of the individual pixel values of the rows of the first pixel array and a first set of vertical sums representative of the sums of the individual pixel values of the columns of the first pixel array;  
       providing a plurality of second orthogonal-sum signatures for respective ones of at least selected ones of the plurality of second pixel arrays, each of the plurality of second orthogonal-sum signatures being comprised of a set of horizontal sums representative of the sums of the individual pixel values of the rows of a respective one of the second pixel arrays and a set of vertical sums representative of the sums of the individual pixel values of the columns of a respective one of the second pixel arrays; and,  
       comparing the first orthogonal-sum signature with each of the second orthogonal-sum signatures in order to determine the best match between the first and second pixel arrays.  
     
     
       6. The method as set forth in  claim 5 , wherein the comparing step is performed using a prescribed best match search metric. 
     
     
       7. The method as set forth in  claim 6 , wherein the prescribed best match search metric is a Minimum Absolute Error (MAE) search metric. 
     
     
       8. The method as set forth in  claim 5 , wherein the first and second pixel arrays are each macroblocks having a structure defined by an MPEG standard. 
     
     
       9. The method as set forth in  claim 8 , wherein the MPEG standard is the MPEG-2 standard. 
     
     
       10. The method as set forth in  claim 8 , wherein each of the macroblocks is an undecimated macroblock. 
     
     
       11. The method as set forth in  claim 8 , wherein each of the macroblocks is a decimated macroblock. 
     
     
       12. A motion estimation search engine for determining a best match between a first pixel array in a picture currently being encoded and a plurality of second pixel arrays in a search region of a reference picture, wherein each of the first and second pixel arrays includes a plurality of rows and a plurality of columns of individual pixel values, the motion estimation search engine including: 
       circuitry that provides a first orthogonal-sum signature of the first pixel array comprised of a set of horizontal sums representative of the sums of the individual pixel values of the rows of the first pixel array and a first set of vertical sums representative of the sums of the individual pixel values of the columns of the first pixel array, and that provides a plurality of second orthogonal-sum signatures for respective ones of at least selected ones of the plurality of second pixel arrays, each of the plurality of second orthogonal-sum signatures being comprised of a set of horizontal sums representative of the sums of the individual pixel values of the rows of a respective one of the second pixel arrays and a set of vertical sums representative of the sums of the individual pixel values of the columns of a respective one of the second pixel arrays; and,  
       circuitry that compares the first orthogonal-sum signature with each of the second orthogonal-sum signatures in order to determine the best match between the first and second pixel arrays.  
     
     
       13. The motion estimation search engine as set forth in  claim 12 , wherein the first and second pixel arrays are each macroblocks having a structure defined by an MPEG standard. 
     
     
       14. A motion estimation search engine for determining a best match between a first pixel array in a picture currently being encoded and a plurality of second pixel arrays in a search region of a reference picture, wherein each of the first and second pixel arrays includes a plurality of rows and a plurality of columns of individual pixel values, the motion estimation search engine including: 
       means for providing a first orthogonal-sum signature of the first pixel array comprised of a set of horizontal sums representative of the sums of the individual pixel values of the rows of the first pixel array and a first set of vertical sums representative of the sums of the individual pixel values of the columns of the first pixel array, and for providing a plurality of second orthogonal-sum signatures for respective ones of at least selected ones of the plurality of second pixel arrays, each of the plurality of second orthogonal-sum signatures being comprised of a set of horizontal sums representative of the sums of the individual pixel values of the rows of a respective one of the second pixel arrays and a set of vertical sums representative of the sums of the individual pixel values of the columns of a respective one of the second pixel arrays; and,  
       means for comparing the first orthogonal-sum signature with each of the second orthogonal-sum signatures in order to determine the best match between the first and second pixel arrays.  
     
     
       15. The motion estimation search engine as set forth in  claim 14 , wherein the first and second pixel arrays are each macroblocks having a structure defined by an MPEG standard.