Device and method for fast block-matching motion estimation in video encoders

• US 8,913,660 B2
• Filed: 04/14/2006
• Issued: 12/16/2014
• Est. Priority Date: 04/14/2005
• Status: Active Grant

• Current Assignee: FastVDO LLC
• Original Assignee: FastVDO LLC
• Inventors: Tourapis, Alexis Michael, Cheong, Hye-Yeon, Topiwala, Pankaj N.
• Primary Examiner(s): Czekaj, Dave
• Assistant Examiner(s): Werner, David N
• Application Number:
  US11/404,602
• Publication Number:
  US 20060245497A1
• Time in Patent Office: 3,168 Days
• Field of Search: None
• US Class Current: 375/240.12
• CPC Class Codes: H04N 19/139 Analysis of motion vectors, e.g. their magnitude, direction, variance or reliability
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/43 Hardware specially adapted for motion estimation or compensation
• CPC Class Codes: H04N 19/513 Processing of motion vectors
• CPC Class Codes: H04N 19/52 by predictive encoding
• CPC Class Codes: H04N 19/527 Global motion vector estimation
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• 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
• CPC Class Codes: H04N 19/567 Motion estimation based on rate distortion criteria

Abstract

Motion estimation is the science of predicting the current frame in a video sequence from the past frame (or frames), by slicing it into rectangular blocks of pixels, and matching these to past such blocks. The displacement in the spatial position of the block in the current frame with respect to the past frame is called the motion vector. This method of temporally decorrelating the video sequence by finding the best matching blocks from past reference frames—motion estimation—makes up about 80% or more of the computation in a video encoder. In this patent disclosure, we define a method of searching only a very sparse subset of possible displacement positions (or motion vectors) among all possible ones, to see if we can get a good enough match, and terminate early. This sparse subset of motion vectors is preselected using prior knowledge and extensive testing on video sequences.

Claims

1. An apparatus for processing video signals through motion estimation of a video sequence comprising:

a computer readable medium storing the video sequence comprising a plurality of video frames, each frame comprising a plurality of blocks; and

a video signal processor comprising a multistage motion vector prediction engine configured to estimate a plurality of best block-matching motion vectors for each block in each video frame of the video sequence in a number of stages, wherein the estimating comprises;

for each stage of the number of stages of motion vector estimation for a block of a video frame of the video sequence;

selecting a test vector from a set of test vectors, wherein the set of test vectors is selected from a plurality of sets of vectors using at least one of a priori knowledge of the video sequence and a priori knowledge of a plurality video sequences stored in a database, and wherein the test vectors of a set of test vectors are arbitrary and sorted based on a distance between each test vector and a median test vector of the set of test vectors and each test vector is unique from other test vectors of the set of the test vectors;

computing a distortion metric using the selected test vector;

responsive to the test vector of the set of test vectors meeting a criterion of adaptive threshold criteria based on the computed distortion metric, the adaptive threshold criteria associated with the block of the video frame of the video sequence and derived based on a rate-distortion optimization measure;

selecting the test vector as an individual best matched motion vector of the set of test vectors; and

skipping motion vector estimation process for the remaining test vectors of the set of test vectors;

responsive to the test vector of the set of test vectors not meeting a criterion of the adaptive threshold criteria based on the computed distortion metric;

testing remaining test vectors of the set of test vectors in an order according to corresponding positions of the test vectors in the sorted set of the test vectors; and

selecting a test vectors as an individual best matched motion vector of the set of test vectors based on the distortion metric associated with each test vector, the selected test vector having the minimum distortion among the test vectors;

comparing the individual best matched motion vectors from the plurality of sets of test vectors to select a total best matched motion vector based on the comparison;

applying a global threshold criterion to the selected total best matched motion vector;

responsive to no global threshold criterion being satisfied, refining search area in the proximity of the total best matched motion vector and iteratively searching for best motion vector in the refined search area using additionally defined sets of test vectors and selection criteria;

selecting a new best matched motion vector based on the search;

testing the new best matched motion vector based on another global matching criterion; and

accepting the new best matched motion vector responsive to the criterion being satisfied or a defined number of iterations of search being performed.

2. The apparatus according to claim 1, wherein at least one set of the plurality of sets of vectors is compiled based on temporal correlations within the video sequence or other a priori temporal correlation information associated with the video sequence.

3. The apparatus according to claim 1, wherein at least one set of the plurality of sets of vectors is compiled based on spatial correlations within the video sequence or other a priori spatial correlation information associated with the video sequence.

4. The apparatus according to claim 1, wherein at least one adaptive threshold criterion is compiled based on temporal correlations within the video sequence or other a priori temporal correlation information associated with the video sequence.

5. The apparatus according to claim 1, wherein at least one adaptive threshold criterion is compiled based on spatial correlations within the video sequence or other a priori spatial correlation information associated with the video sequence.

6. The apparatus according to claim 1, wherein testing the new best matched motion vector comprises:

selecting a second best matched motion vector based on the search in the refined search area; and

responsive to the second best matched motion vector being close to the new best matched motion vector, terminating the iterative searching for the best motion vector.

7. The apparatus according to claim 6, wherein the second best matched motion vector is determined to be close to the new best matched motion vector responsive to the second best matched motion vector being within a predefined distance measured in number of pixels.

8. A method for processing video signals through motion estimation of a video sequence, comprising:

storing a video sequence on a computer readable medium, wherein the video sequence comprises a plurality of video frames and each frame comprises a plurality of blocks;

for each stage of a number of stages of motion vector estimation for a block of a video frame of the video sequence;

selecting a test vector from a set of test vectors, wherein the set of test vectors is selected from a plurality of sets of vectors using at least one of a priori knowledge of the video sequence and a priori knowledge of a plurality video sequences stored in a database, and wherein the test vectors of a set of test vectors are arbitrary and sorted based on a distance between each test vector and a median test vector of the set of test vectors and each test vector is unique from other test vectors of the set of the test vectors;

computing a distortion metric using the selected test vector;

responsive to the test vector of the set of test vectors meeting a criterion of adaptive threshold criteria based on the computed distortion metric, the adaptive threshold criteria associated with the block of the video frame of the video sequence derived based on a rate-distortion optimization measure;

selecting the test vector as an individual best matched motion vector of the set of test vectors; and

skipping motion vector estimation process for the remaining test vectors of the set of test vectors;

responsive to the test vector of the set of test vectors not meeting a criterion of the adaptive threshold criteria based on the computed distortion metric;

testing remaining test vectors of the set of test vectors in an order according to corresponding positions of the test vectors in the sorted set of the test vectors; and

selecting a test vectors as an individual best matched motion vector of the set of test vectors based on the distortion metric associated with each test vector, the selected test vector having the minimum distortion among the test vectors;

comparing the individual best matched motion vectors from the plurality of sets of test vectors to select a total best matched motion vector based on the comparison;

applying a global threshold criterion to the selected total best matched motion vector;

responsive to no global threshold criterion being satisfied, refining search area in the proximity of the total best matched motion vector and iteratively searching for best motion vector in the refined search area using additionally defined sets of test vectors and selection criteria;

selecting a new best matched motion vector based on the search;

testing the new best matched motion vector based on another global matching criterion; and

accepting the new best matched motion vector responsive to the criterion being satisfied or a defined number of iterations of search being performed.

9. The method according to claim 8, wherein at least one set of the plurality of sets of test vectors is compiled based on temporal correlations within the video sequence or other a priori temporal correlation information associated with the video sequence.

10. The method according to claim 8, wherein at least one set of the plurality of sets of test vectors is compiled based on spatial correlations within the video sequence or other a priori spatial correlation information associated with the video sequence.

11. The method according to claim 8, wherein at least one adaptive threshold criterion is compiled based on temporal correlations within the video sequence or other a priori temporal correlation information associated with the video sequence.

12. The method according to claim 8, wherein at least one adaptive threshold criterion is compiled based on spatial correlations within the video sequence or other a priori spatial correlation information associated with the video sequence.