The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Jun. 04, 2002
Filed:
Apr. 06, 1999
Michael Bakhmutsky, Spring Valley, NY (US);
Koninklijke Philips Electronics N. V., New York, NY (US);
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 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−1 and N=C−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.