MOTION ESTIMATION METHOD FEATURING ORTHOGONAL-SUM CONCURRENT MULTI MATCHING

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 R of rows and a plurality C of columns of individual pixel values. The method includes the steps of providing a first full 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 partial orthogonal-sum signatures for respective ones of the plurality of second pixel arrays, each of the plurality of partial orthogonal-sum signatures being comprised of a set of partial horizontal sums representative of the sums of the individual pixel values of a plurality M of the rows of a respective one of the second pixel arrays and a set of partial vertical sums representative of the sums of the individual pixel values of a plurality N of the columns of a respective one of the second pixel arrays, wherein M<R and N<C; concurrently computing a plurality of second full orthogonal-sum signatures for the respective ones of the plurality of second pixel arrays using the plurality of partial orthogonal-sum signatures; and, comparing the first full orthogonal-sum signature with each of the second full orthogonal-sum signatures in order to determine the best match between the first and second pixel arrays. In a presently preferred embodiment, M=R&#8722;1 and N=C&#8722;1; the set of partial horizontal sums is representative of the sums of the individual pixel values contained in N columns of R+1 rows of an (C+1)-by-(R+1) pixel array that encompasses all of the second pixel arrays, and the set of partial vertical sums is representative of the sums of the individual pixel values contained in M rows of C+1 columns of the (C+1)-by-(R+1) pixel array; the R+1 rows and the C+1 columns collectively comprise the (C+1)-by-(R+1) pixel array that encompasses all of the second pixel arrays; and, the M rows and N columns are centered in the (C+1)-by-(R+1) pixel array. Also disclosed is a device, e.g., a motion estimation search engine of a digital video encoder, that implements the method of the present invention.