MPEG motion estimation based on dual start points

• US 20040247029A1
• Filed: 06/09/2003
• Published: 12/09/2004
• Est. Priority Date: 06/09/2003
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Zhong, Lefan, Prabhakar, Ram
• Granted Patent: US 8,660,182 B2
• Time in Patent Office: Days
• 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 to determine a video motion estimation 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 block in a reference frame that is a good match to a block in the search frame; and

using information from the good match block and the second predict start point, performing a second coarse search in an effort to select a block in the reference frame that is a better match to the block in the search frame.

2. The method of claim 1 further comprising:

using information from the better match block, performing a fine search in an effort to select a block in the reference frame that is yet a better match to the block the in the search frame.

3. The method of claim 1 further comprising:

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 step and go directly to the fine search step.

4. The method of claim 3 wherein a second coarse search is needed if:

|V0.x−

v.x|+|V0.y−

v.y|≧

4

wherein V0 is a motion vector associated with the second predict start and v is a motion vector associated with the block in a reference frame that is a good match to a block in the search.

5. The method of claim 1, wherein the first and second coarse searches involve a macroblock diamond search and a macroblock smaller diamond search, wherein the smaller diamond search is carried out based on information generated by the diamond search.

6. The method of claim 5, wherein the diamond search and the smaller diamond search are based on a 5SDS search.

7. 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 carried out based on information generated by the 8×

8 block search.

8. The method of claim 1, wherein the first predicted start position is based on a block immediately adjacent and on top of the block in the search frame, and the second predicted start position is based on a block immediately adjacent and left of the block in the search frame.

9. The method of claim 8, wherein a selection criteria used in the searches is a Sum of Absolute Difference (SAD) defined as:

10. A method to determine a video motion estimation 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 diamond search and a second diamond search to select two blocks in a reference frame that are good matches to a block in the search frame;

using information from the two good match blocks, concurrently performing a first smaller diamond search and a second smaller diamond search to select two blocks in the reference frame that are better matches to the block in the search frame, wherein the first smaller diamond search is based on information from the first diamond search and the second smaller diamond search is based on information from the second diamond search; and

comparing the two better match blocks to select a more matched block of the two.

11. The method of claim 10 further comprising:

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

12. The method of claim 11, wherein the diamond searches and the smaller diamond searches are based on a 5SDS.

13. The method of claim 11, wherein the fine search involves 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.

14. The method of claim 10, wherein the first predicted start position is based on a block immediately adjacent and on top of the block in the search frame, and the second predicted start position is based on a block immediately adjacent and left of the block in the search frame.

15. The method of claim 14, wherein a selection criteria used in the searches is a Sum of Absolute Difference (SAD) defined as:

16. A video motion estimator coupled to memory and a Central Processing Unit (CPU) comprising:

a diamond search module coupled to memory, the diamond search module performing diamond searches to select a block in a reference frame that is a match to a block in a search frame based on a selection criteria;

a compare and motion vector module coupled the diamond search module, the compare and motion vector module monitoring and storing an updated selection criteria value, the compare and motion vector module monitoring and determining the motion vector associated with the matched block associated with the updated criteria value; and

a scheduler coupled to the diamond search module, the scheduler controlling searches performed by the diamond search module based on a predetermined motion estimation process utilizing two predicted start positions.

17. The video motion estimator of claim 16, wherein the motion estimation process 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 block in a reference frame that is a good match to a block in the search frame; and

using information from the good matched block and the second predict start point, performing a second coarse search to select a block in the reference frame that is a better match to the block in the search frame.

18. The video motion estimator of claim 17 further comprising an 8×

8 search module coupled to memory, the compare and motion vector module, and the scheduler, wherein the motion estimation process further comprising performing a fine search to select a block in the reference frame that is yet a better match to the block the in the search frame, the 8×

8 search module performing an 8×

8 search as a part of the fine search based on the selection criteria using information from the better matched block.

19. The video motion estimator of claim 17, wherein the motion estimation process further comprising 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 step and go directly to the fine search step.

20. The video motion estimator of claim 17, wherein the first and second coarse searches involve a macroblock diamond search and a macroblock smaller diamond search, wherein the smaller diamond search is carried out based on information generated by the diamond search.

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

22. The video motion estimator of claim 18, wherein the fine search further includes a half-pixel search, wherein the half-pixel search is carried out by the diamond search module based on information generated by the 8×

8 block search.

23. The video motion estimator of claim 17, wherein the first predicted start position is based on a block immediately adjacent and on top of the block in the search frame, and the second predicted start position is based on a block immediately adjacent and left of the block in the search frame.

24. The video motion estimator of claim 23, wherein the selection criteria used in the searches is a Sum of Absolute Difference (SAD) defined as:

25. The video motion estimator of claim 16 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 the updated selection criteria value.

26. The video motion estimator of claim 16, wherein the motion estimation process 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, performing a first diamond search and a second diamond search to select two blocks in a reference frame that are good matches to a block in the search frame;

using information from the two good match blocks, performing a first smaller diamond search and a second smaller diamond search to select two blocks in the reference frame that are better matches to the block in the search frame, wherein the first smaller diamond search is based on information from the first diamond search and the second smaller diamond search is based on information from the second diamond search; and

comparing the two better match blocks to determine a more matched block of the two.

27. The video motion estimator of claim 26 further comprising an 8×

8 search module coupled to memory, the compare and motion vector module, and the scheduler, wherein the motion estimation process further comprising performing a fine search to select a block in the reference frame that is yet a better match to the block the in the search frame, the 8×

8 search module performing an 8×

8 search as a part of the fine search based on the selection criteria using information from the more matched block.

28. The video motion estimator of claim 26 wherein the diamond searches and the smaller diamond searches are based on 5SDS.

29. The video motion estimator of claim 27 wherein the fine search further includes a half-pixel search, wherein the half-pixel search is carried out by the diamond search module based on information generated by the 8×

8 block search.

30. The video motion estimator of claim 26, wherein the first predicted start position is based on a block immediately adjacent and on top of the block in the search frame, and the second predicted start position is based on a block immediately adjacent and left of the block in the search frame.

31. The video motion estimator of claim 30, wherein a selection criteria used in the searches is a Sum of Absolute Difference (SAD) defined as:

32. A computer system adapted to perform motion estimation on video data comprising:

a central processing unit (CPU);

system memory coupled to the CPU;

a video interface coupled to the CPU, the video interface receiving video data from a video source;

a video display coupled to the CPU;

a graphics/display controller coupled to the CPU, the video interface, the video display, and the system memory, the graphics controller comprising;

a graphics engine (GE);

an memory interface unit (MIU) coupled to the GE;

memory coupled to the MIU; and

a video encoder connected to the MIU and coupled to the memory, the video encoder comprising;

a diamond search module coupled to memory, the diamond search module performing a diamond search to select a block in a reference frame that is a match to a block in a search frame based on a selection criteria;

an 8×

8 search module coupled to memory, the 8×

8 search module performing an 8×

8 search to select a block in a reference frame that is a match to a block in a search frame based on the selection criteria;

a compare and motion generator module coupled the diamond search module and the 8×

8 search module, the compare and motion generator module monitoring and storing an updated selection criteria value, the compare and motion generator module generating the motion vector associated with the match block associated with the updated criteria value; and

a scheduler coupled to the diamond search module and the 8×

8 search module, the scheduler controlling searches performed by the diamond search module and 8×

8 search module based on a predetermined motion compensated estimation process utilizing two predicted start positions.

33. The computer system of claim 32, wherein the motion estimation process 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 block in a reference frame that is a good match to a block in the search frame;

using information from the good match block and the second predict start point, performing a second coarse search to select a block in the reference frame that is a better match to the block in the search frame; and

using information from the better match block, performing a fine search to select a block in the reference frame that is yet a better match to the block the in the search frame.

34. The computer system of claim 32, wherein the motion estimation process 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, performing a first diamond search and a second diamond search to select two blocks in a reference frame that are good matches to a block in the search frame;

using information from the two good match blocks, performing a first smaller diamond search and a second smaller diamond search to select two blocks in the reference frame that are better matches to the block in the search frame, wherein the first smaller diamond search is based on information from the first diamond search and the second smaller diamond search is based on information from the second diamond search;

comparing the two better match blocks to determine a more matched block of the two; and

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