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

• US 9,445,103 B2
• Filed: 05/16/2013
• Issued: 09/13/2016
• Est. Priority Date: 07/03/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): PONTIUS, JAMES M
• Application Number:
  US13/895,939
• Publication Number:
  US 20130336402A1
• Time in Patent Office: 1,216 Days
• Field of Search: 375/240.16
• US Class Current: 1/1
• 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 machine-implemented method, comprising:

computing a motion estimation search window for a first block of a first frame of a video based on a mean of motion vectors associated with other blocks of the video;

selecting a second block of a second frame of the video within the motion estimation search window and a third block within a third frame of the video based on a motion vector from the first block to the second block and a measure of visual similarity between the second and third blocks; and

deriving a motion vector for the first block based on one or more of the motion vector from the first block to the second block and a motion vector from the first block to the third block.

2. The machine-implemented method of claim 1, wherein the computing a motion estimation search window includes computing a frame level motion estimation search window based on a mean of motion vectors associated with blocks of other frames of the video.

3. The machine-implemented method of claim 1, wherein the computing a motion estimation search window includes computing a block level motion estimation search window based on a mean of motion vectors associated with other blocks of the video that have one or more of a spatial and a temporal relationship to the first block.

4. The machine-implemented method of claim 3, wherein the other blocks of the video that have one or more of a spatial and a temporal relationship to the first block include one or more of:

a block that is spatially adjacent to the first block;

a block that is temporally adjacent to the first block;

a block that is spatially adjacent to a block that is temporally adjacent to the first block; and

a block that is spatially adjacent to a block that is temporally adjacent to a block that is temporally adjacent to the first block.

5. The machine-implemented method of claim 1, wherein the computing, the selecting, and the deriving are performed based on down-sampled blocks of the video.

6. The machine-implemented method of claim 1, wherein the computing a motion estimation search window includes:

scaling the motion vectors associated with the other blocks of the video based on distances between the first frame and frames of the respective other blocks; and

computing the motion estimation search window based on a mean of the scaled motion vectors.

7. The machine-implemented method of claim 1, wherein the computing a motion estimation search window includes:

scaling the motion vectors associated with the other blocks of the video based on distances between the first frame and frames of the respective other blocks;

computing a mean of the scaled motion vectors;

scaling the mean of the scaled motion vectors; and

offsetting the scaled mean with a coordinate offset to provide the motion estimation search window.

8. The machine-implemented method of claim 1, wherein the computing a motion estimation search window includes:

computing two-dimensions of the motion estimation search window based on the mean of motion vectors associated with other blocks of the video.

9. An apparatus, comprising a processor and memory configured to:

compute a motion estimation search window for a first block of a first frame of a video based on a mean of motion vectors associated with other blocks of the video;

select a second block of a second frame of the video within the motion estimation search window and a third block within a third frame of the video based on a motion vector from the first block to the second block and a measure of visual similarity between the second and third blocks; and

deriving a motion vector for the first block based on one or more of the motion vector from the first block to the second block and a motion vector from the first block to the third block.

10. The apparatus of claim 9, wherein the processor and memory are further configured to compute the motion estimation search window to include a frame level motion estimation search window based on a mean of motion vectors associated with blocks of other frames of the video.

11. The apparatus of claim 9, wherein the processor and memory are further configured to compute the motion estimation search window to include a block level motion estimation search window based on a mean of motion vectors associated with other blocks of the video that have one or more of a spatial and a temporal relationship to the first block.

12. The apparatus of claim 11, wherein the other blocks of the video that have one or more of a spatial and a temporal relationship to the first block include one or more of:

a block that is spatially adjacent to the first block;

a block that is temporally adjacent to the first block;

a block that is spatially adjacent to a block that is temporally adjacent to the first block; and

a block that is spatially adjacent to a block that is temporally adjacent to a block that is temporally adjacent to the first block.

13. The apparatus of claim 9, wherein the processor and memory are further configured to compute the motion estimation search window, select the second and third blocks, and derive the motion vector for the first block, based on down-sampled blocks of the video.

14. The apparatus of claim 9, wherein the processor and memory are further configured to:

scale the motion vectors associated with the other blocks of the video based on distances between the first frame and frames of the respective other blocks; and

compute the motion estimation search window based on a mean of the scaled motion vectors.

15. The apparatus of claim 9, wherein the processor and memory are further configured to:

scale the motion vectors associated with the other blocks of the video based on distances between the first frame and frames of the respective other blocks;

compute a mean of the scaled motion vectors;

scale the mean of the scaled motion vectors; and

offset the scaled mean with a coordinate offset to provide the motion estimation search window.

16. The apparatus of claim 9, wherein the processor and memory are further configured to compute two-dimensions of the motion estimation search window based on the mean of motion vectors associated with other blocks of the video.

17. A non-transitory computer readable medium encoded with a computer program that includes instructions to cause a processor to:

compute a motion estimation search window for a first block of a first frame of a video based on a mean of motion vectors associated with other blocks of the video;

select a second block of a second frame of the video within the motion estimation search window and a third block within a third frame of the video based on a motion vector from the first block to the second block and a measure of visual similarity between the second and third blocks; and

deriving a motion vector for the first block based on one or more of the motion vector from the first block to the second block and a motion vector from the first block to the third block.

18. The non-transitory computer readable medium of claim 17, further including instructions to cause the processor to:

compute a frame level motion estimation search window based on a mean of motion vectors associated with blocks of other frames of the video.

19. The non-transitory computer readable medium of claim 17, further including instructions to cause the processor to:

compute a block level motion estimation search window based on a mean of motion vectors associated with other blocks of the video that have one or more of a spatial and a temporal relationship to the first block.

20. The non-transitory computer readable medium claim 19, wherein the other blocks of the video that have one or more of a spatial and a temporal relationship to the first block include one or more of:

a block that is spatially adjacent to the first block;

a block that is temporally adjacent to the first block;

a block that is spatially adjacent to a block that is temporally adjacent to the first block; and

a block that is spatially adjacent to a block that is temporally adjacent to a block that is temporally adjacent to the first block.

21. The non-transitory computer readable medium claim 17, further including instructions to cause the processor to compute the motion estimation search window, select the second and third blocks, and derive the motion vector for the first block, based on down-sampled blocks of the video.

22. The non-transitory computer readable medium claim 17, further including instructions to cause the processor to:

scale the motion vectors associated with the other blocks of the video based on distances between the first frame and frames of the respective other blocks; and

compute the motion estimation search window based on a mean of the scaled motion vectors.

23. The non-transitory computer readable medium claim 17, further including instructions to cause the processor to:

scale the motion vectors associated with the other blocks of the video based on distances between the first frame and frames of the respective other blocks;

compute a mean of the scaled motion vectors;

scale the mean of the scaled motion vectors; and

offset the scaled mean with a coordinate offset to provide the motion estimation search window.

24. The non-transitory computer readable medium claim 17, further including instructions to cause the processor to:

compute two-dimensions of the motion estimation search window based on the mean of motion vectors associated with other blocks of the video.