Methods and apparatus for adaptively choosing a search range for motion estimation

• US 8,462,852 B2
• Filed: 10/20/2009
• Issued: 06/11/2013
• Est. Priority Date: 10/20/2009
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Xu, Lidong, Chiu, Yi-Jen
• Primary Examiner(s): Perungavoor, Sath V
• Assistant Examiner(s): PONTIUS, JAMES M
• Application Number:
  US12/582,061
• Publication Number:
  US 20110090964A1
• Time in Patent Office: 1,330 Days
• Field of Search: 375/240.16
• US Class Current: 375/240.16
• CPC Class Codes: H04N 19/139 Analysis of motion vectors, e.g. their magnitude, direction, variance or reliability
• CPC Class Codes: H04N 19/513 Processing of motion vectors
• CPC Class Codes: H04N 19/521 for estimating the reliability of the determined motion vectors or motion vector field, e.g. for smoothing the motion vector field or for correcting motion vectors
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/57 Motion estimation characterised by a search window with variable size or shape
• CPC Class Codes: H04N 5/144 Movement detection for video coding H04N19/503; analysis of motion in general G06T7/20

Abstract

Systems, methods, and computer program products that can be used to determine a search range (SR) when performing motion estimation at, for example, a video encoder or decoder. Determining a motion vector for a current block during motion estimation may involve searching within a search window that may reside in a reference frame, or in a previously decoded block that spatially or temporally neighbors the current block. Such a search seeks a motion vector that minimizes a metric, such as a sum of absolute differences between corresponding blocks of reference frames. A motion vector that minimizes such a metric may be a good candidate for use in motion estimation. The search may become more efficient if a search range is determined such that the extent of the search is bounded. A search range may be determined at the block level or at the picture level.

Claims

1. A method, comprising:

determining a set of motion vectors related to blocks associated with a current block;

calculating a mean value (mv) of the related motion vectors; and

calculating a search range vector SR, according to a formula

SR=(α

*mv)+β

where α

is a predetermined constant scalar and β

is a predetermined constant vector, SR bounds a motion search in performance of motion estimation for the current block, α

=1.1, β

=(4,

     4), and said determination, my calculation, and SR calculation are performed by a processor.

2. The method of claim 1, wherein the related motion vectors are associated with respective blocks of a reference frame, and wherein the search range vector SR is used for performing motion estimation for the current block of a current frame, and for all other blocks in the current frame.

3. The method of claim 2, wherein each of the related motion vectors extends from a respective block of a backward reference frame to a corresponding block of a forward reference frame.

4. The method of claim 2, wherein each of the related motion vectors extends from a respective block of a first forward reference frame to a corresponding block of a second forward reference frame.

5. The method of claim 2, wherein each of the related motion vectors extends from one of a respective block in a backward reference frame to a previous frame relative to the current frame, or a respective block in a forward reference frame to a succeeding frame relative to the current frame.

6. The method of claim 1, wherein the related motion vectors are associated with blocks that neighbor the current block, and wherein the search range vector SR is used in performance of motion estimation for the current block.

7. The method of claim 6, wherein the neighboring blocks neighbor the current block spatially in the current frame.

8. The method of claim 6, wherein the neighboring blocks occur in temporally neighboring frames relative to the current frame and correspond to the current block.

9. A system, comprising:

a processor; and

a memory in communication with said processor, for storing a plurality of processing instructions for directing said processor to

determine a set of motion vectors related to blocks associated with a current block;

calculate a mean value (mv) of the related motion vectors; and

calculate a search range vector SR, according to a formula

SR=(α

*mv)+β

where α

is a predetermined constant scalar, β

is a predetermined constant vector, α

=1.1, β

=(4,

     4), and SR is used to bound a motion search in performance of motion estimation for the current block.

10. The system of claim 9, wherein the processor and memory are incorporated in a video encoder.

11. The system of claim 9, wherein the processor and memory are incorporated in a video decoder.

12. The system of claim 9, wherein the related motion vectors are associated with respective blocks of a reference frame, and wherein the search range vector SR is used for performing motion estimation for the current block of a current frame, and for all other blocks in the current frame.

13. The system of claim 12, wherein each of the related motion vectors extends from a respective block of a backward reference frame to a corresponding block of a forward reference frame.

14. The system of claim 12, wherein each of the related motion vectors extends from a respective block of a first forward reference frame to a corresponding block of a second forward reference frame.

15. The system of claim 12, wherein each of the related motion vectors extends from one of:

a respective block in a backward reference frame to a previous frame relative to the current frame, or

a respective block in a forward reference frame to a succeeding frame relative to the current frame.

16. The system of claim 9, wherein the related motion vectors are associated with blocks that neighbor the current block, and wherein the search range vector SR is used in performance of motion estimation for the current block.

17. The system of claim 16, wherein the neighboring blocks neighbor the current block spatially in the current frame.

18. The system of claim 16, wherein the neighboring blocks occur in temporally neighboring frames relative to the current frame and correspond to the current block.

19. A computer program product including a non-transitory computer readable medium having computer program logic stored therein, the computer program logic comprising:

logic to cause a processor to determine a set of motion vectors related to blocks associated with a current block;

logic to further cause the processor to calculate a mean value (mv) of the related motion vectors; and

logic to further cause the processor to calculate a search range vector SR, according to a formula

SR=(α

*mv)+β

where α

is a predetermined constant scalar, β

is a predetermined constant vector, α

=1.1, β

=(4,

     4), and SR bounds a motion search in performance of motion estimation for the current block.

20. The computer program product of claim 19, wherein the related motion vectors are associated with respective blocks of a reference frame, and wherein the search range vector SR is used for performing motion estimation for the current block of a current frame, and for all other blocks in the current frame.

21. The computer program product of claim 20, wherein each of the related motion vectors extends from a respective block of a backward reference frame to a corresponding block of a forward reference frame.

22. The computer program product of claim 20, wherein each of the related motion vectors extends from a respective block of a first forward reference frame to a corresponding block of a second forward reference frame.

23. The computer program product of claim 20, wherein each of the related motion vectors extends from one of:

a respective block in a backward reference frame to a previous frame relative to the current frame, or

a respective block in a forward reference frame to a succeeding frame relative to the current frame.

24. The computer program product of claim 19, wherein the related motion vectors are associated with blocks that neighbor the current block, and wherein the search range vector SR is used in performance of motion estimation for the current block.

25. The computer program product of claim 24, wherein the neighboring blocks neighbor the current block spatially in the current frame.

26. The computer program product of claim 24, wherein the neighboring blocks occur in temporally neighboring frames relative to the current frame and correspond to the current block.