Device and method for fast sub sample block-matching motion estimation in video encoders
AssigneeFastVDO LLC
InventorsAlexandros Tourapis, Pankaj N. Topiwala
Life of this patent
Estimating the term…
Abstract
Methods of using motion estimation techniques with video encoders to provide significant data compression with respect to video signals so that the video signals may subsequently be reconstructed with minimal observable information loss. Methods include a fast fractional motion estimation scheme.
Claims28
A method of using a video encoder for selecting the best matching block in a reference frame of a video, matching a block in a current frame of the video, according to a given distortion metric, the method comprising repeating the following steps for each of a one or more examination resolutions:
- a) Setting an examination resolution;
- b) Setting a center position as a current best location;
- c) Examining a plurality of diamond positions around said center position a best location;
- d) Finding a best motion vector;
- e) Storing a second best motion vector;
- f) Testing a set of conditions involving the best motion vector, a predictor motion vector, the center position, and also testing an early termination criterion;
- i) If all said set of conditions are met and an early termination criterion is met, exiting and declaring a best motion vector;
- ii) If said set of conditions are not met, proceeding to step (g);
- g) Testing a plurality of positions and conditions, wherein said testing includes comparisons relating to the best motion vector, the second best motion vector, the center position, and the predictor motion vector;
- h) Determining a new best motion vector;
- i) Resetting the center position to be said new best motion vector;
- j) Testing the examination resolution relative to a maximum resolution;
- and
- k) Increasing the examination resolution if the examination resolution is less than the maximum resolution, and returning to step (c).
A method of using a video encoder for selecting the best matching block in a reference frame of a video, matching a block in a current frame of the video, according to a given distortion metric, the method comprising repeating the following steps for each of a one or more examination resolutions:
- a) Setting an examination resolution;
- b) Setting a center position as current best location;
- c) Examining a plurality of diamond positions around said center position;
- d) Finding a best motion vector;
- e) Storing a second best motion vector;
- f) Testing a set of conditions involving the best motion vector, a predictor motion vector, and the center position;
- i) If said conditions are met, testing an early termination criterion;
- (1) If the early termination criterion is met, exiting and declaring a best motion vector;
- (2) If the early termination criterion is not met, proceeding to step (j);
- ii) If said conditions are not met, going to step (g);
- g) Testing a plurality of positions and conditions, wherein said testing includes conditions relating to the best motion vector, the second best motion vector, the center position, and the predictor motion vector;
- h) Determining a new best motion vector;
- i) Resetting the center position to be said new best motion vector;
- j) Testing the resolution of the examination resolution relative to a maximum resolution;
- k) Increasing the examination resolution if the examination resolution is less than a maximum resolution, and returning to step (c).
A method of using a video encoder for selecting the best matching block in a reference frame of an image, matching a block in a current frame of the image, according to a given distortion metric, the method comprising repeating the following steps for each of a one or more examination resolutions:
- a) Setting an examination resolution;
- b) Setting a center position as current best location;
- c) Examining a plurality of diamond positions around said center position;
- d) Finding a best motion vector;
- e) Storing a second best motion vector;
- f) Testing if the best motion vector matches a predictor motion vector;
- i) If the best motion vector does match the predictor motion vector, testing if the best motion vector also matches the center position;
- ii) If either the best motion vector does not match the predictor motion vector or does not match the center position, testing a plurality of positions and conditions, wherein said testing includes comparisons relating to the best motion vector, the second best motion vector, the center position, and the predictor motion vector;
- (1) Determining a new best motion vector;
- (2) Resetting the center position to the new best motion vector;
- (3) Testing if the examination resolution is a maximum resolution;
- (a) If the current examination resolution is the maximum resolution, exiting the search and declaring a best motion vector;
- (b) if the current examination resolution is not the maximum resolution, increasing the resolution;
- (4) Returning to step (c);
- iii) If the best motion vector matches the predictor motion vector and matches the center position, testing an early termination criterion based on a given threshold of the distortion metric;
- (1) If the early termination criterion is met, exiting and declaring a best motion vector;
- (2) If the early termination criterion is not met, returning to step (f)(ii)(3).
Dependencies are inferred from the claim text.