Adaptive motion search range

• US 8,107,748 B2
• Filed: 09/16/2005
• Issued: 01/31/2012
• Est. Priority Date: 09/16/2005
• Status: Expired due to Fees

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Miao, Zhourong, Carrig, James J., Paniconi, Marco
• Primary Examiner(s): Lu, Tom Y
• Assistant Examiner(s): CONWAY, THOMAS A
• Application Number:
  US11/228,656
• Publication Number:
  US 20070064803A1
• Time in Patent Office: 2,328 Days
• Field of Search: None
• US Class Current: 382/236
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• 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

Abstract

A technique for performing motion estimation using an adaptive motion search range includes calculating motion vectors for blocks of pixels in a target image, using the calculated motion vectors to generate a search range associated with a target block of pixels in the target image, and using the generated search range to estimate motion of the target block of pixels.

Claims

1. A method carried out by an electronic data processor, comprising:

calculating motion vectors for blocks of pixels in a target image;

applying a high pass filter to the calculated motion vectors to determine a variance of the calculated motion vectors;

generating a search range associated with a target block of pixels in the target image using the variance of the calculated motion vectors;

calculating a safety margin for the search range based on motion vectors of at least one preceding neighboring block of pixels;

expanding the search range using the safety margin; and

using the generated search range to estimate motion of the target block of pixels.

2. The method of claim 1, further comprising:

determining a block scanner order for the blocks in the target image selected from the group consisting of;

a raster scanning order and a sub-sampling order.

3. The method of claim 1, wherein calculating motion vectors for blocks of pixels in the target image comprises:

calculating the motion vectors using multiple reference images.

4. The method of claim 1, wherein calculating the safety margin comprises using a standard deviation of motion vectors of the at least one preceding block of pixels to calculate the safety margin.

5. The method of claim 1, wherein generating the search range comprises:

using the calculated motion vectors to determine an estimated motion range.

6. The method of claim 5, wherein determining the estimated motion range comprises:

applying a low pass filter to the calculated motion vectors.

7. The method of claim 6, wherein applying the filter to the calculated motion vectors comprises:

=L×

(M_x)^T, =L×

(M_y)^T,

where L is a filter having n taps, such that L=[l1, l2, . . . , ln], and li is the filter coefficient of tap i;

 

is the x-axis value of the estimated motion range of the target block;

M_x is a vector containing x-axis values of the calculated motion vectors;

(M_x)^T is a transpose of vector M_x;

 

is the y-axis value of the estimated motion range of the target block;

M_y is a vector containing y-axis calculated motion vectors; and

(M_y)^T is a transpose of vector M_y.

8. An apparatus comprising:

a motion vector calculator that calculates motion vectors for blocks of pixels in a target image;

a search range calculator that uses the calculated motion vectors to generate a search range associated with a target block of pixels in the target image, wherein the search range is calculated by determining a variance of the calculated motion vectors and wherein the variance is determined by applying a high pass filter to the calculated motion vectors;

a safety margin calculator that uses motion vectors of at least one preceding neighboring block of pixels to calculate a safety margin for the search range;

a safety margin applicator that expands the search range using the safety margin; and

a motion estimator that uses the generated search range to estimate motion of the target blocks of pixels.

9. The apparatus of claim 8, wherein the blocks in the target image are scanned in a raster scanning order or a sub-sampling order.

10. The apparatus of claim 8, wherein the motion vector calculator calculates the motion vectors using multiple reference images.

11. The apparatus of claim 8, wherein the safety margin calculator uses a standard deviation of motion vectors of the at least one preceding block of pixels to calculate the safety margin.

12. The apparatus of claim 8, wherein the search range calculator uses the calculated motion vectors to determine an estimated motion range.

13. The apparatus of claim 12, wherein the search range calculator applies a low pass filter to the calculated motion vectors.

14. The apparatus of claim 13, wherein the search range calculator applies

=L×

(M_x)^T, =L×

(M_y)^T,

where L is a filter having n taps, such that L=[l₁, l₂, . . . , l_n], and l_i is the filter coefficient of tap i;

 

is the x-axis value of the estimated motion range of the target block;

M_x is a vector containing x-axis values of the calculated motion vectors;

(M_x)^T is a transpose of vector M_x;

 

is the y-axis value of the estimated motion range of the target block;

M_y is a vector containing y-axis values of the calculated motion vectors; and

(M_y)^T is a transpose of vector M_y.

15. A non-transitory computer readable medium storing a program of instructions which, when executed by a processing system, cause the system to perform a method comprising:

calculating motion vectors for blocks of pixels in a target image;

applying a high pass filter to the calculated motion vectors to determine a variance of the calculated motion vectors;

generating a search range associated with a target block of pixels in the target image using the variance of the calculated motion vectors;

calculating a safety margin for the search range based on motion vectors of at least one preceding neighboring block of pixels;

expanding the search range using the safety margin; and

using the generated search range to estimate motion of the target block of pixels.

16. The non-transitory computer readable medium of claim 15, further comprising:

determining a block scanning order for the blocks in the target image selected from the group consisting of;

a raster scanning order and a sub-sampling order.

17. The non-transitory computer readable medium of claim 15, wherein calculating motion vectors for block of pixels in the target image comprises:

calculating the motion vectors using multiple reference images.

18. The non-transitory computer readable medium of claim 15, wherein calculating the safety margin comprises using a standard deviation of motion vectors of the at least one preceding block of pixels to calculate the safety margin.

19. The non-transitory computer readable medium of claim 15, wherein generating the search range comprises:

using the calculated motion vectors to determine an estimated motion range.

20. The non-transitory computer readable medium of claim 19, wherein determining the estimated motion range comprises:

applying a low pass filter to the calculated motion vectors.

21. The non-transitory computer readable medium of claim 20, wherein applying the filter to the calculated motion vectors comprises:

=L×

(M_x)^T, =L×

(M_y)^T,

where L is a filter having n taps, such that L=[l₁, l₂, . . . , l_n], and l_i is the filter coefficient of tap i;

 

is the x-axis value of the estimated motion range of the target block;

M_x is a vector containing x-axis values of the calculated motion vectors;

(M_x)^T is a transpose of vector M_x;

 

is the y-axis value of the estimated motion range of the target block;

M_y is a vector containing y-axis values of the calculated motion vectors; and

(M_y)^T is a transpose of vector M_y.