Method and /or apparatus for motion estimation using a hierarchical search followed by a computation split for different block sizes

• US 20040120400A1
• Filed: 12/20/2002
• Published: 06/24/2004
• Est. Priority Date: 12/20/2002
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Linzer, Elliott N.
• Granted Patent: US 7,170,934 B2
• Time in Patent Office: Days
• US Class Current: 375/240.16
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

A method for performing motion estimation comprising the steps of (a) determining one or more first vectors representative of a displacement of a first block of a first image in a second image and (b) determining one or more second vectors representative of a displacement of the first block in the second image and a first sub-block and second sub-block of the first block based upon the one or more first vectors, a plurality of error scores, and a combination of the plurality of error scores.

Claims

1. A method for performing motion estimation, comprising the steps of:

(A) determining one or more first vectors representative of a displacement of a first block of a first image in a second image; and

(B) determining one or more second vectors representative of a displacement of said first block in said second image and a first sub-block and a second sub-block of said first block based upon (i) said one or more first vectors, (ii) a plurality of error scores and (iii) one or more combinations of said error scores.

2. The method according to claim 1, wherein step (A) comprises performing a hierarchical search.

3. The method according to claim 1, wherein step (B) comprises generating one or more computational splits.

4. The method according to claim 1, wherein said plurality of error scores comprises:

a first closeness of match score for at least one displacement vector for said first sub-block of said first block; and

a second closeness of match score for at least one displacement vector for said second sub-block of said first block.

5. The method according to claim 1, wherein said plurality of error scores comprises:

a plurality of closeness of match scores for a plurality of displacement vectors for a plurality of sub-blocks of said first block.

6. The method according to claim 1, wherein said combination of error scores determines a closeness of match score for said first block.

7. The method according to claim 1, wherein said combination comprises an addition of said error scores.

8. The method according to claim 1, further comprising the step of:

decimating said first and second images into a first decimated image and a second decimated image, respectively.

9. The method according to claim 1, wherein said images are decimated horizontally, vertically or both horizontally and vertically.

10. The method according to claim 8, wherein said one or more first vectors are determined based on said first and second decimated images.

11. An apparatus comprising:

a first circuit configured to generate one or more motion vectors in response to a first image and a second image;

a second circuit configured to generate a plurality of error scores in response to said first image, said second image and said plurality of motion vectors; and

a third circuit configured to generate (i) a plurality of first select signals, each in response to one of said plurality of error scores and (ii) one or more second select signals, wherein said second select signals are each generated in response to two or more of said plurality of error scores.

12. The method according to claim 11, wherein said first circuit comprises:

a memory configured to store said first and second images and a first decimated image and a second decimated image; and

a decimator configured to generate said first and second decimated images in response to said first and second images, respectively.

13. The apparatus according to claim 12, wherein said one or more motion vectors are generated using said first and second decimated images.

14. The apparatus according to claim 11, wherein said one or more motion vectors are representative of a displacement of a first block of said first image in said second image.

15. The apparatus according to claim 14, wherein said plurality of error scores comprises:

a first closeness of match score for at least one displacement vector for a first sub-block of said first block; and

a second closeness of match score for at least one displacement vector for a second sub-block of said first block.

16. The apparatus according to claim 14, wherein said plurality of error scores comprises a plurality of closeness of match scores for a plurality of displacement vectors for a plurality of sub-blocks of said first block.

17. The apparatus according to claim 11, wherein each of said plurality of error scores comprises a sum of absolute differences between a first block of said first image and a second block of said second image.

18. The apparatus according to claim 12, wherein said decimator is configured to decimate said first and second images horizontally, vertically, or both horizontally and vertically.

19. The apparatus according to claim 11, wherein:

said first circuit is configured to perform a hierarchical search of said first and second images; and

said third circuit is configured to generate said select signals in response to one or more computational splits.

20. An apparatus comprising:

means for generating one or more motion vectors in response to a first and a second image;

means for generating a plurality of error scores in response to said first image, said second image and said plurality of motion vectors; and

means for generating (i) a plurality of first select signals, each in response to one of said plurality of error scores and (ii) one or more second select signals, wherein each of said one or more second select signals is generated in response to two or more of said plurality of error scores.