Device and method for fast block-matching motion estimation in video encoders
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
2 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.
-
Specification