Motion estimation of images

Patent metadata

Field	Value
Publication number	US-9357228-B2
Application number	US-201113117334-A
Country	US
Kind code	B2
Filing date	May 27, 2011
Priority date	May 27, 2010
Publication date	May 31, 2016
Grant date	May 31, 2016

Abstract

Provided is sub-block motion estimation that includes a full search with a reduced search area around a motion vector predictor. Also provided are a single (or unified) motion vector predictor and a function similar to a rate-distortion cost function. Also provided is a scanning order that can reduce or substantially eliminated redundant data loading and/or that can achieve different data re-use ratio. Further, provided herein is a reconfigurable multi-resolution motion vector re-use hardware architecture based on a single motion vector predictor and a function similar to a rate-distortion cost function. Further, through utilization of the disclosed aspects, only a small number of past motion vectors are propagated and the disclosed aspects can be reconfigured for video with different spatial resolution.

First claim

What is claimed is:

1. A method, comprising:
dividing, by a system comprising a processor, one or more video frames into a plurality of sub-blocks created from a plurality of macro-blocks;
determining, by the system, a reference frame within the one or more video frames;
defining, by the system, a search area for the plurality of sub-blocks as a function of a plurality of motion vector predictors comprising centering the search area around a location defined in the reference frame; and
searching, by the system, within at least one sub-block of the plurality of sub-blocks for a single motion vector predictor for the plurality of sub-blocks, wherein the searching is based on determining a rate-distortion cost between search points within the plurality of sub-blocks, the searching comprising:
using a first search pattern to search a first sub-block of the plurality of sub-blocks, wherein the search of the first sub-block comprises first stages of searching, and wherein the first stages of searching comprise one or more hierarchical stage of search;
using a set of previously loaded data based on a first data re-use ratio to search the first sub-block, wherein the set of previously loaded data is stored at a shift register array of a set of inter-connected internal adaptive shift registers of the system, wherein each shift register of the set of internal adaptive shift registers is capable of storing a set of previously loaded data associated with a range of sub-block sizes; and
using a second search pattern to search a second sub-block of the plurality of sub-blocks, wherein the first sub-block and the second sub-block are of different sizes and have different shapes, wherein the search of the second sub-block comprises second stages of searching wherein the second stages of searching comprises one or more hierarchical stage of search, wherein the second search pattern re-uses the set of previously loaded data based on a second data re-use ratio to search the second sub-block of the plurality of sub-blocks, and wherein the first data re-use ratio is different from the second data re-use ratio.

2. The method of claim 1 , wherein the determining the rate-distortion cost comprises determining a cost that comprises a first additive element that is a distortion measure between a current sub-block and a candidate reference sub-block and determining a second additive element that is a product of lambda, being a function of at least one of a sub-block size and location, a macro-block location and type, a quantization parameter, a target rate behavior, a buffer condition or a buffer property, and a function of a difference between a candidate motion vector and a motion vector predictor.

3. The method of claim 2 , wherein the determining the second additive element comprises determining the second additive element as a function of motion vectors of a set of neighboring macro-blocks or a set of neighboring sub-blocks corresponding to the first sub-block.

4. The method of claim 3 , further comprising:
determining, by the system, the plurality of motion vector predictors as a function of a plurality of motion vectors of the set of neighboring macro-blocks or the set of neighboring sub-blocks, and wherein the defining the search area comprises identifying a search center as a function of the plurality of motion vector predictors.

5. The method of claim 4 , further comprising assigning, by the system, a motion vector predictor from the plurality of motion vector predictors as a median of a macro-block motion vector on a left macro-block, a top macro-block, and a top-right macro-block.

6. The method of claim 1 , wherein the defining the search area comprises determining a search center as a median of motion vectors of three past neighboring macro-blocks that comprise a first macro-block at a left position, a second macro-block at a top position, and a third macro-block at a top-right position.

7. The method of claim 6 , further comprising determining, by the system, at least one alternative macro-block in response to a determination of one of the first macro-block, the second macro-block, or the third macro-block being unavailable.

8. The method of claim 7 , wherein the determining the at least one alternative macro-block comprises choosing a fourth macro-block at a top-left position.

9. A system, comprising:
a processor that executes or facilitates execution of computer executable components stored in a memory, the computer executable components comprising:
a partition component configured to divide a video frame into a plurality of macro-blocks;
a sub-partition component configured to divide the plurality of macro-blocks into a plurality of sub-blocks, wherein a first macro-block of the plurality of macro-blocks is divided into at least two sub-blocks, and wherein the first macro-block and the at least two sub-blocks are of different sizes and different shapes;
a selection component configured to choose a reference frame from the plurality of sub-blocks;
a data processing component configured to use a set of previously loaded data within a set of internal adaptive shift registers of the system based on a first data re-use ratio to search a first block of the at least two sub-blocks, wherein each shift register of the set of internal adaptive shift registers is capable of storing a respective set of previously loaded data associated with the reference frame and further configured to use the set of previously loaded data based on a second data re-use ratio to search a second block of the at least two sub-blocks, wherein the first data re-use ratio and the second data re-use ratio are different;
a classification component configured to define a search area comprising a set of search points, wherein the search area is based on a plurality of motion vector predictors, and wherein the search area is defined to capture different area sizes and area shapes; and
an evaluation component configured to calculate a rate-distortion cost function for selected search points of the set of search points in the search area based on the set of previously loaded data to choose a motion vector for the plurality of sub-blocks.

10. The system of claim 9 , wherein the rate-distortion cost function comprises a first element and a second element, wherein the first element is a distortion measure and the second element is a product of a parameter and a function of a difference between a candidate motion vector and a motion vector predictor of the plurality of motion vectors.

11. The system of claim 10 , wherein the parameter is lambda, which is a function of a sub-block size and location, a macro-block location and type, a quantization parameter, a target rate behavior, a buffer condition and a buffer property.

12. The system of claim 10 , wherein the parameter is approximated by a linear combination of a power-of-2.

13. The system of claim 10 , wherein the motion vector predictor of the second element is a function of motion vectors of past neighboring macro-blocks.

14. The system of claim 10 , wherein the motion vector predictor of the second element is a function of motion vectors of past neighboring macro-blocks on a left, a top, and a top right in relation to a current macro-block.

15. The system of claim 14 , wherein the motion vector predictor of the second element is a median of the motion vectors of past neighboring macro-blocks on the left, the top, and the top right in relation to a current macro-block.

16. The system of claim 10 , wherein the search area corresponds to the candidate motion vector between a current macro-block

Assignees

• Au Oscar Chi Lim
• Wen Xing
• Xu Jiang
• Univ Hong Kong Science & Techn

Inventors

• Au Oscar Chi Lim
• Wen Xing
• Xu Jiang

Classifications

• H04N19/52

  by predictive encoding · CPC title

• H04N19/567

  Motion estimation based on rate distortion criteria · CPC title

• H04N19/433

  characterised by techniques for memory access · CPC title

• H04N19/57 Primary

  Motion estimation characterised by a search window with variable size or shape · CPC title