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

• US 20060245497A1
• Filed: 04/14/2006
• Published: 11/02/2006
• 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.
• Granted Patent: US 8,913,660 B2
• Time in Patent Office: Days
• US Class Current: 375/240.160
• 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. That is, it is enormously expensive, and methods do so that are efficient are in high demand. Thus the field of motion estimation within video coding is rich in the breadth and diversity of approaches that have been put forward. Yet it is often the simplest methods that are the most effective. So it is in this case. While it is well-known that a full search over all possible positions within a fixed window is an optimal method in terms of performance, it is generally prohibitive in computation. In this patent disclosure, we define an efficient, new 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 set of sparse subset of motion vectors is preselected, using a priori knowledge and extensive testing on video sequences, so that these “predictors” for the motion vector are essentially magic. The art of this method is the preselection of excellent sparse subsets of vectors, the smart thresholds for acceptance or rejection, and even in the order of the testing prior to decision.

Claims

1. A method of selecting a motion prediction vector for a pixel or a group of pixels in an image comprising the steps of:

a) selecting a test motion vector from an adaptive predictor set;

b) testing the test motion vector against a preselected early stopping criterion;

c) if the test motion vector meets the early stopping criterion going to step i;

d) if the test motion vector fails the early stopping criterion, recursively selecting additional test motion vectors from the adaptive predictor set and repeating steps b and c until the set is exhausted;

e) when the adapted predictor set is exhausted, selecting the best predictor that does not meet the early stopping criterion;

f) selecting a refinement pattern comprising plural comparison points to apply to the best predictor that does not meet the early stopping criterion;

g) computing the distortion of each of the plural comparison points and selecting the comparison point with the minimum distortion;

h) testing the motion vector against a second stopping criterion;

i) repeating steps f, g, and h until the stopping criterion is met; and

j) accepting the refined motion vector as the estimated motion vector for the pixel or group of pixels.

2. A method for selecting in a previous frame of a stream of video frames a block of pixels that best matches a selected block of pixels in a frame of interest, comprising;

a) establishing an adaptive early termination criterion;

b) establishing a group of predictors;

c) refining the group of predictors to achieve a most likely predictor using adaptive patterns;

and

d) repeating steps b) and c) until said adaptive early termination criterion is met.