Dual-prime motion estimation engine

• US 6,501,799 B1
• Filed: 08/04/1998
• Issued: 12/31/2002
• Est. Priority Date: 08/04/1998
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Kohn, Leslie
• Primary Examiner(s): Kelley, Chris
• Assistant Examiner(s): PHILIPPE, GIMS S
• Application Number:
  US09/128,730
• Time in Patent Office: 1,610 Days
• Field of Search: 348/416, 348/415, 348/417, 348/699, 348/700, 348/412, 348/403, 348/405, 348/409, 348/420, 348/407, 382/282, 382/179, 382/180, 382/277, 375/240, 375/240.24
• US Class Current: 375/240.16
• CPC Class Codes: H04N 19/43 Hardware specially adapted for motion estimation or compensation

Abstract

An apparatus performs motion estimation based on an average of previous field references in a flexible, yet high performance manner. The apparatus has a command memory for storing a motion estimation command list segment which in turn contains a search command for specifying a merged search operation over one or more search positions. The apparatus also has a score memory for storing the result of each merged search operation. The score memory is initialized when the merged search operation is initiated. During the search operation, the score memory accumulates the result of each search position. The apparatus also has a search engine connected to the command memory and to the score memory for determining from the score memory a search position with the lowest score. The search engine then generates dual prime motion estimation outputs in the form of motion estimation result list segments.

Claims

1. An apparatus for performing motion estimation, comprising:

a command memory for storing a motion estimation command list segment, said segment having a search command for specifying a merged search operation over one or more search positions, wherein a merged search operation allows the score of a current search position to be accumulated with the score of one or more previous search positions;

a score memory for storing results of the merged search operation, said score memory being initialized when the merged search operation is initiated, said score memory accumulating a result for each search position during a subsequent merged search operation; and

a search engine coupled to the command memory and to the score memory, said search engine determining from the score memory a search position with the lowest score.

2. The apparatus of claim 1, wherein the search command has a merge bit to select the merged search operation.

3. The apparatus of claim 2, wherein the score memory is initialized when the merge bit of a current search command is set and the merge bit of a previous search command is cleared.

4. The apparatus of claim 2, wherein the score memory accumulates the result for each search position when the merge bit of the previous search command is set.

5. The apparatus of claim 2, wherein the search position with the lowest score is determined when the merge bit of a current search command is cleared and the merge bit of a previous command is set.

6. The apparatus of claim 1, further comprising means for estimating a common vector using merged search operations on fields spaced two temporal units apart at a first pel grid resolution with a common input velocity estimate.

7. The apparatus of claim 6, wherein the first pel grid resolution is a ½

pel grid resolution.

8. The apparatus of claim 6, further comprising means for estimating a common vector using additional merged search operations on adjacent fields at a second pel grid resolution with a first scaled common input velocity estimate and merged search operations on fields spaced three temporal units apart at a third pel grid resolution with a second scaled common input velocity estimate.

9. The apparatus of claim 8, wherein the second pel grid resolution is a ¼

pel grid resolution and the first scaled common input estimate is ½

of the common input velocity estimate.

10. The apparatus of claim 9, wherein the third pel grid resolution is a ¾

pel grid resolution and the second scaled common input estimate is 3/2 of the common input velocity estimate.

11. The apparatus of claim 1, wherein the apparatus estimates a differential vector using a merged search operation on adjacent fields at a predetermined pel grid resolution with a first scaled common input velocity estimate and a predetermined search range;

and

a merged search operation on fields spaced three temporal units apart at the predetermined pel grid resolution with a second scaled common input velocity estimate and the predetermined search range.

12. The apparatus of claim 11, wherein the predetermined pel grid resolution is a ½

pel grid resolution.

13. The apparatus of claim 11, wherein the first scaled common input velocity estimate is ½

of the common input velocity estimate.

14. The apparatus of claim 11, wherein the second scaled common input velocity estimate is 3/2 of the common input velocity estimate.

15. The apparatus of claim 11, wherein the predetermined search range is one.

16. The apparatus of claim 1, wherein the search engine compensates for differing search grid resolutions between same and opposite parity motion vector searches.

17. The apparatus of claim 16, wherein temporally adjacent fields are compensated by duplicating a search result to four score memory positions.

18. A method for performing motion estimation based on a reference image and a target image, each image having one or more search positions, the method comprising:

initializing a score memory when a merged search operation is initiated, wherein the merged search operation allows the score of a current search position to be accumulated with the score of one or more previous search positions; and

repetitively accumulating the result for each search position into the score memory for each merged search.

19. The method of claim 18, further comprising selecting the search position with the lowest score as an output.

20. The method of claim 19, wherein the selecting step is performed simultaneously with a final accumulation.

21. The method of claim 18, further comprising compensating for differing search grid resolutions between same and opposite parity motion vector searches.

22. The method of claim 21, wherein the compensating step for adjacent fields duplicates a search result to four score memory positions.

23. The method of claim 22, wherein two of the duplicated score memory positions are horizontally adjacent.

24. The method of claim 22, wherein two of the duplicated score memory positions are vertically adjacent.

25. The method of claim 23, wherein two of the duplicated score memory positions are vertically adjacent and two of the score memory positions are horizontally adjacent.

26. An apparatus for performing motion estimation based on a reference image and a target image, comprising:

a command memory for storing a motion estimation command list segment, said segment having a search command for specifying a merged search operation over one or more search positions, wherein a merged search operation allows the score of a current search position to be accumulated with the score of one or more previous search positions;

a score memory for storing results of the merged search operation, said score memory being initialized when the merged search operation is initiated, said score memory accumulating a result for each search position during a subsequent merged search operation; and

a search engine coupled to the command memory and to the score memory, said search engine determining from the score memory a search position with the lowest score and producing a motion estimation result list, the search engine having;

a reference window memory system containing one or more reference data segments;

a target memory system containing one or more target data segments; and

a data path engine coupled to the reference window memory system and the target memory system, the data path engine generating a measure of differences between data in the reference window memory system and data stored in the target memory system; and

a result memory system coupled to the motion estimation search engine, said result memory system storing one or more result list segments.

27. The apparatus of claim 26, wherein the command list segment and the result list segment use an identical format for a search starting point in the command list segment and a motion vector in the result list segment.

28. The apparatus of claim 26, wherein the format for performing hierarchical searches includes a horizontal displacement field, a vertical displacement field, a score field, a search parameter field, a field bit, and an advance bit.

29. The apparatus of claim 26, wherein the reference window memory allows reference data to be shared between a plurality of targets.

30. The apparatus of claim 26, wherein the shared targets are vertically adjacent, horizontally adjacent, or a combination thereof.