Motion estimation method using orthogonal-sum block matching

• US 6,480,629 B1
• Filed: 04/06/1999
• Issued: 11/12/2002
• Est. Priority Date: 04/06/1999
• Status: Expired due to Term

• Current Assignee: Funai Electric Co., Ltd.
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Bakhmutsky, Michael
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US09/287,161
• Time in Patent Office: 1,316 Days
• Field of Search: 382/236, 348/407.1, 348/412.1, 348/413.1, 348/422.1
• US Class Current: 382/236
• CPC Class Codes: H04N 19/43 Hardware specially adapted for motion estimation or compensation
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/59 involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution

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.

Claims

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.