Motion estimation engine for video encoding

• US 9,106,922 B2
• Filed: 03/15/2013
• Issued: 08/11/2015
• Est. Priority Date: 12/19/2012
• Status: Active Grant

• Current Assignee: Beamr Imaging Ltd.
• Original Assignee: Vanguard Software Solutions, Inc. (Dolby Laboratories Incorporated)
• Inventors: Fludkov, Mikhail, Kan, Mikhail, Pyko, Sergey, Terterov, Nickolay
• Primary Examiner(s): Dastouri, Mehrdad
• Assistant Examiner(s): DOBBS, KRISTIN SENSMEIER
• Application Number:
  US13/836,174
• Publication Number:
  US 20140169472A1
• Time in Patent Office: 879 Days
• US Class Current: 1/1
• CPC Class Codes: H04N 19/119 Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
• CPC Class Codes: H04N 19/139 Analysis of motion vectors, e.g. their magnitude, direction, variance or reliability
• 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/52 by predictive encoding
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

The motion estimation engine has a multi-threaded structure and comprises a preprocessor for rough motion estimation of motion vectors and in-loop motion estimator for creating a coding tree unit, as well as a shared memory for interaction of the pre-processor with the in-loop motion estimator. The coding tree unit is formed by merging neighboring partitions of coding units using a list of best MV candidates.

Claims

1. A method of motion estimation for video coding, comprising:

creating a transformed reference image for encoding a frame by sequentially transforming original luma pixels, and storing the transformed image in a frame image buffer;

performing rough motion estimation in transformed image space, and storing resulted motion vectors MV for a coding unit CU 16×

16 into a MV buffer;

generating a merge mode list of MV candidates and an AMVP mode list of MV candidates;

removing repetitive vectors from the lists and storing unique merge mode MV according to MV identifiers;

storing fractional parts of MV according to an index number of a prediction unit PU inside a coding tree unit CTU;

loading reference blocks from a reference buffer into a merge motion estimator;

defining SAD for 5 partitions (1×

(16×

16), 2×

(8×

16), 2×

(16×

8)), which are calculated using a current CU and its prediction from a reference picture;

comparing a weighted SAD of a current MV candidate to a weighted SAD of a previous MV candidate for each of the 5 partitions and storing the best merge mode MV candidates with SAD;

repeating steps of loading reference blocks, defining SADs and comparing weighted SADs until all MM candidates are considered, or until the end of predetermined calculation time;

loading resulting MV of rough estimation from MV buffer into AMVP list of candidates;

loading a search window from the reference buffer according to the MV candidates from the AMVP list;

performing a full search of best MV candidates inside the loaded window;

comparing the weighted SAD of the current MV candidate with the weighted SAD of the previous MV candidate for each 5 CU partitions, and storing the best AMVP candidates with SAD;

repeating steps of loading search window to storing the best AMVP candidates until all of the AMVP candidates are considered, or until the end of predetermined calculation time;

comparing estimation results of the Merge Mode and the AMVP Mode and selecting best decisions for each of the 5 CU partitions;

repeating motion estimation for all 16×

16 CU in the Coding Tree Unit (CTU); and

merging neighboring partitions according to MV identifiers using entire list of best MV candidates.

2. The method of motion estimation of claim 1, wherein the MV are rounded to full-pel accuracy.

3. The method of motion estimation of claim 1, wherein the MV identifier is an address of a cell memory where the MV is located.

4. The method of motion estimation of claim 1, wherein the MV candidate from the Merge Mode list defines placement of the reference block in the reference buffer, and the candidate from the AMVP mode list defines placement of the search window in the reference picture.

5. The method of motion estimation of claim 1, wherein the best MVs for 5 partitions (16×

16, 2×

(8×

16), 2×

(16×

8)) are defined by comparing the weighted SAD for different predictions.

6. The method of motion estimation of claim 1, wherein the step of creating the reference image is performed using binarization algorithm, comprising:

defining a local average M;

calculating a new value PN=P+(P−

M) for current pixel P to provide image sharpening;

defining a threshold for binarization;

THR=(M+8)>

>

4; and

calculating a value of binary image pixel PB as;

PB=PN<

=(M−

THR)?2′

b00;

PN>

=(M+THR)?2′

b01;

2′

b10.

7. The method of motion estimation of claim 5, wherein the local average M is calculated as a moving average with the help of 2D-band pass convolution kernel.

8. The method of motion estimation of claim 6, wherein the local average M is calculated as a moving average using a sum with exponential forgetting.

9. The method of motion estimation of claim 1, wherein the rough motion estimation is performed according to Rough Searching Algorithm, comprising:

searching for a best matching position with two metrics, wherein the first metrics is based on calculation of a sum of absolute difference for binary image; and

the second metrics is based on calculation of correlation coefficients; and

selecting a final estimation of the motion vector as a vector with the smallest length.

10. The method of motion estimation of claim 1, wherein the full search is performed according to Fine Search Algorithm comprising:

performing an integer motion estimation (IME) in sequentially-parallel mode; and

performing fractional adjustment of best motion vectors using parabolic approximation of SAD samples to achieve q-pel accuracy of the motion estimation;

wherein IME comprises;

defining SADs of each quadrant and merging the SADs according to geometry of a partition;

detecting a best position as a position with a minimum SAD; and

saving the best position and SADs around the best position.

11. The method of motion estimation of claim 1, wherein merging the partitions comprises:

identifying each full-pel MV of the 5 partitions (1×

(16×

16), 2×

(8×

16), 2×

(16×

8)) by a unique descriptor;

comparing descriptors of the neighbors for the 5 partitions;

merging pairs of partitions with equal full-pel motion vectors into at least one coding unit; and

repeating the merging of coding units until the size of the coding unit is less than a predetermined maximum size.

12. The method of motion estimation of claim 1, further comprising calculating the factional parts of the MV and adding the fractional parts to a integer part of the best MV after merging of partitions inside the CTU, wherein the fractional parts of MV are defined by weighted average estimation of the fractional parts of merged prediction units.

13. The method of motion estimation of claim 12, wherein the size of the CTU is 64×

64, the CTU comprising no more than 16 unique MV taken from spatial neighbors and 16 MV taken from temporal neighbors, each MV divided into parts of 4 MSB bits and 8 LSB bits for compact storage and quick comparison.

14. The method of motion estimation of claim 12, wherein the fractional parts of MVs are stored separately from integer parts in the MV prediction tables, and a position of the fractional part of a motion vector in the tables is defined by a descriptor.