MPEG motion estimation based on dual start points

• US 8,660,182 B2
• Filed: 06/09/2003
• Issued: 02/25/2014
• Est. Priority Date: 06/09/2003
• Status: Expired due to Term

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Zhong, Lefan, Prabhakar, Ram
• Primary Examiner(s): SENFI, BEHROOZ M
• Application Number:
  US10/457,644
• Publication Number:
  US 20040247029A1
• Time in Patent Office: 3,914 Days
• Field of Search: 348/155, 348/669, 348/390, 348/400, 348/401, 348/402, 348/409, 348415-416, 348/700, 375/240, 375/240.1, 375/240.02, 375/240.12, 375/240.16, 375/240.24, 375/240.13, 375/240.01, 375/240.09, 382/232, 382/236, 382/238, 382/107, 382/106, 382/166, 382/234, 382/235, 382244-253
• US Class Current: 375/240.16
• CPC Class Codes: H04N 19/523 with sub-pixel accuracy
• CPC Class Codes: H04N 19/533 Motion estimation using multistep search, e.g. 2D-log search or one-at-a-time search [OTS]
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search

Abstract

A more efficient motion estimation process that utilizes a plurality of predicted start points (e.g., two predicted start points) based on blocks adjacent to the current block together with other improvements and requires minimal system resources (e.g., hardware resources and CPU processing) in its hardware implementation is provided. More particularly, the motion estimation technique in accordance with the present invention performs a plurality of coarse searches (either sequentially or in parallel) using a plurality of predicted start positions followed by a fine search.

Claims

1. A method for video motion estimation, said method comprising:

selecting a first predict start point in a search frame and a second predict start point in the search frame;

using the first predict start point, performing a first coarse search to select a first block in the search frame that is a better match to a reference block in a reference frame than at least one other block in the search frame to the reference block, wherein said performing said first coarse search further comprises performing said first coarse search using an electronic device;

determining, based on a distance between a motion vector associated with said first block and a motion vector associated with said second predict start point, whether a second coarse search is needed; and

if said second coarse search is needed, using information associated with the first block and the second predict start point, performing said second coarse search to enable selection of a second block in the search frame that is a better match to the reference block than the first block to the reference block, wherein said performing said second coarse search further comprises performing said second coarse search using said electronic device.

2. The method of claim 1 further comprising:

using information associated with the second block, performing a fine search to enable selection of a third block in the search frame that is a better match to the reference block than the second block to the reference block.

3. The method of claim 2 further comprising:

if the second coarse search is not needed, skipping the second coarse search and performing the fine search.

4. The method of claim 1, wherein the first and second coarse searches each comprise a respective large diamond search and a respective small diamond search, wherein the respective small diamond searches are performed based on information generated by the respective large diamond searches.

5. The method of claim 4, wherein the large diamond search and the small diamond search are based on a 5SDS search.

6. The method of claim 2, wherein the fine search involves an 8×

8 block search and a half-pixel search, wherein the half-pixel search is performed based on information generated by the 8×

8 block search.

7. The method of claim 1, wherein the first predicted start position is based on a block adjacent to and on a first side of the reference block, and the second predicted start position is based on a block adjacent to and on a second side of the reference block.

8. The method of claim 1, wherein said first coarse search comprises performing respective Sum of Absolute Difference (SAD) calculations for a plurality of blocks of said search frame to determine how well each of said plurality of blocks matches said reference block.

9. A method for video motion estimation, the method comprising:

selecting a first predict start point in a search frame and a second predict start point in the search frame;

using the first predict start point and the second predict start point in the search frame, concurrently performing a first large diamond search and a second large diamond search to select a first block in the search frame and a second block in the search frame that are better matches to a reference block in a reference frame than at least one other block in the search frame to the reference block, wherein said concurrently performing said first large diamond search and said second large diamond search further comprises performing said first large diamond and said second large diamond search using an electronic device;

using information associated with the first and second blocks, concurrently performing a first small diamond search and a second small diamond search to select a third block in the search frame and a fourth block in the search frame that are better matches to the reference block than said first and second blocks to the reference block, wherein the first small diamond search is based on information from the first large diamond search and the second small diamond search is based on information from the second large diamond search, wherein said concurrently performing said first small diamond search and said second small diamond search further comprises performing said first small diamond and said second small diamond search using said electronic device; and

comparing each of the third and fourth blocks to the reference block to determine a block that more closely matches the reference block.

10. The method of claim 9 further comprising:

using information from the more closely-matched block, performing a fine search to select a fifth block in the search frame that is a better match to the reference block than the more closely-matched block to the reference block.

11. The method of claim 10, wherein the first and second large diamond searches and the first and second small diamond searches are based on a 5SDS.

12. The method of claim 10, wherein the fine search comprises an 8×

8 block search and a half-pixel search, wherein the half-pixel search is carried out based on information generated by the 8×

8 block search.

13. The method of claim 9, wherein the first predicted start position is based on a block immediately adjacent to and on a first side of the reference block, and the second predicted start position is based on a block immediately adjacent to and to a second side of the reference block.

14. The method of claim 9, wherein said first and second diamond searches comprise performing respective Sum of Absolute Difference (SAD) calculations for a plurality of blocks of said search frame to determine how well each of said plurality of blocks matches said reference block.

15. A video motion estimator coupled to memory and a processor, said video motion estimator comprising:

a search module coupled to said memory and operable to perform a plurality of searches to identify blocks in a search frame that closely match a reference block in a reference frame based on a selection criteria, wherein a condition for performing a subsequent coarse search of said plurality of searches is associated with a distance between a first motion vector and a second motion vector, and wherein said search module is further operable to perform at least two of said plurality of searches concurrently;

a compare and motion vector module coupled to the search module, the compare and motion vector module for monitoring and storing values for said selection criteria, the compare and motion vector module further for monitoring and determining motion vectors used by the search module for performing said plurality of searches; and

a scheduler coupled to the search module and for controlling said plurality of searches performed by the search module based on a predetermined motion estimation process.

16. The video motion estimator of claim 15, wherein the predetermined motion estimation process comprises:

selecting a first predict start point in a search frame and a second predict start point in the search frame;

using the first predict start point, performing a first coarse search to select a first block in the search frame that closely matches said reference block; and

using information associated with the first block and the second predict start point, performing a second coarse search to select a second block in the search frame that is a better match to the reference block than the first block to the reference block.

17. The video motion estimator of claim 16 further comprising an additional search module coupled to the memory, the compare and motion vector module, and the scheduler, wherein the predetermined motion estimation process further comprises performing a fine search to select a third block in the search frame that is a better match to the reference block than the second block to the reference block, wherein the fine search comprises an 8×

8 block search performed by the additional search module using the selection criteria and information associated with the second block.

18. The video motion estimator of claim 17, wherein the predetermined motion estimation process further comprises determining whether a second coarse search is needed before performing the second coarse search, wherein if the second coarse search is not needed, skipping the second coarse search and performing the fine search.

19. The video motion estimator of claim 16, wherein the first coarse search comprises a large diamond search and a small diamond search, and wherein the small diamond search is performed based on information generated by the large diamond search.

20. The video motion estimator of claim 19, wherein the large diamond search and the small diamond search are based on a 5SDS search.

21. The video motion estimator of claim 17, wherein the fine search further comprises a half-pixel search performed by the search module based on information generated by the 8×

8 block search performed by the additional search module.

22. The video motion estimator of claim 16, wherein the first predicted start position is based on a block adjacent to and on a first side of the reference block, and the second predicted start position is based on a block adjacent to and on a second side of the reference block.

23. The video motion estimator of claim 15, wherein said plurality of searches comprises performing respective Sum of Absolute Difference (SAD) calculations for a plurality of blocks of said search frame to determine how well each of said plurality of blocks matches said reference block.

24. The video motion estimator of claim 15 further comprising:

a standard deviation calculator coupled to memory and the scheduler, the standard deviation calculator computing the Mean And Standard Deviation (MAD) value of a block when receiving a signal from the scheduler that the motion estimation process is completed; and

an intra/inter decision module coupled to the scheduler and the standard deviation calculator, the intra/inter decision module determines whether an I-frame or a P-frame is involved by comparing the MAD value against an updated value of said selection criteria.

25. The video motion estimator of claim 15, wherein the predetermined motion estimation process comprises:

selecting a first predict start point in a search frame and a second predict start point in the search frame;

using the first predict start point and the second predict start point in the search frame, concurrently performing a first large diamond search and a second large diamond search to select a first block in the search frame and a second block in the search frame that closely match said reference block;

using information associated with the first and second blocks, performing a first small diamond search and a second small diamond search to select a third block in the search frame and a fourth block in the search frame that are better matches to the reference block than said first and second blocks to the reference block, wherein the first small diamond search is based on information from the first large diamond search and the second small diamond search is based on information from the second large diamond search; and

comparing each of the third and fourth blocks to the reference block to determine a selected block that more closely matches the reference block.

26. The video motion estimator of claim 25 further comprising an additional search module coupled to the memory, the compare and motion vector module, and the scheduler, wherein the predetermined motion estimation process further comprises performing a fine search to select a fifth block in the search frame that is a better match to the reference block than the selected block to the reference block, wherein the fine search comprises an 8×

8 block search performed by the additional search module using the selection criteria and information associated with the selected block.

27. The video motion estimator of claim 25, wherein the large diamond searches and the small diamond searches are based on 5SDS.

28. The video motion estimator of claim 26, wherein the fine search further comprises a half-pixel search performed by the search module based on information generated by the 8×

8 block search performed by the additional search module.

29. The video motion estimator of claim 25, wherein the first predicted start position is based on a block adjacent to and on a first side of the reference block, and the second predicted start position is based on a block adjacent to and on a second side of the reference block.