Video compression for high efficiency video coding using a reduced resolution image

• US 8,891,633 B2
• Filed: 11/14/2013
• Issued: 11/18/2014
• Est. Priority Date: 11/16/2011
• Status: Active Grant

• Current Assignee: Beamr Imaging Ltd.
• Original Assignee: Vanguard Video LLC (Beamr Ltd.)
• Inventors: Zheludkov, Alexander, Martemyanov, Alexey, Terterov, Nikolay
• Primary Examiner(s): LEE, Y YOUNG
• Application Number:
  US14/080,188
• Publication Number:
  US 20140072053A1
• Time in Patent Office: 369 Days
• Field of Search: 375/240.01, 375/240.24, 375/240.26
• US Class Current: 375/240.26
• CPC Class Codes: H04N 19/11 among a plurality of spatial predictive coding modes
• 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/137 Motion inside a coding unit, e.g. average field, frame or block difference
• CPC Class Codes: H04N 19/139 Analysis of motion vectors, e.g. their magnitude, direction, variance or reliability
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/19 using optimisation based on Lagrange multipliers
• CPC Class Codes: H04N 19/51 Motion estimation or motion 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/521 for estimating the reliability of the determined motion vectors or motion vector field, e.g. for smoothing the motion vector field or for correcting motion vectors
• CPC Class Codes: H04N 19/523 with sub-pixel accuracy
• 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/567 Motion estimation based on rate distortion criteria
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/65 using error resilience

Abstract

Method for multi-level motion estimation in block-based video coding. The method is targeted to HEVC specifications of video compression, however, may be used with other video coding standards.

Claims

1. A method of multi-level motion estimation for block-based video coding, the method comprising:

constructing a reduced resolution image by;

representing 64×

64 blocks of original picture as 16×

16 blocks; and

calculating every pixel in the reduced image;

performing a reduced resolution search for blocks 64×

64;

performing refinement by neighboring blocks;

providing a motion assignment for 16×

16 blocks using neighboring blocks;

performing a refinement search for 16×

16 blocks;

providing an error distribution analysis information for split-merge prediction and non-square block selection;

performing a sub-pixel refinement;

splitting 16×

16 blocks into 8×

8 blocks;

merging four 16×

16 blocks into one 32×

32 partition;

merging four 32×

32 blocks into one 64×

64 partition; and

selecting a best non-square prediction using an error distribution field;

wherein the reduced resolution image is calculated as a weighted sum of pixels in the original picture, as follows;

Z_x/4,y/4=(O_x,y+2*O_x+1,y+O_x+2,y+2*O_x,y+1+4*O_x+1,y+1+2*O_x+2,y+1+O_x,y+2+2*O_x+1,y+2+O_x+2,y+2)/16;

where;

Z_{x/4, y/4} is a pixel of the reduced image; and

O_{x, y} is a pixel in the original picture.

2. The method of claim 1, wherein the motion estimation is performed by using integer-pel, and assigning quarter-pel after a decision is made.

3. The method of claim 1, wherein the performing a reduced resolution search comprises:

performing Census transform for every input frame;

splitting a frame into 16×

16 blocks and representing the frame as a 256-bytes vector A;

preparing a 256-bytes vector B, where at each position addressed by value from the vector A, placing an actual position of the vector A;

preparing a correlation surface filled with zeroes;

subtracting element-by-element vector A from vector B and receiving a resulting vector;

returning into a two-dimensional space and incrementing points of the correlation surface at a position given by the resulting vector;

finding maximum on the correlation surface in full-pels; and

interpolating a sub-pixel value using neighbor values on the correlation surface.

4. The method of claim 1, wherein the refinement is performed as a multi-pass motion vector field refinement for integer motion estimation.

5. The method of claim 4, wherein the multi-pass motion vector field refinement comprises:

selecting a threshold T as a desired percent of all blocks in the picture;

setting a variable count C=0;

for every block in the picture;

using motion vectors of eight neighbor blocks as candidate motion vectors;

comparing the vectors and selecting a best motion vector;

if the vector has changed, incrementing variable count C; and

if C<

T, repeating the step of setting the count C.

6. The method of claim 1, wherein the reduced resolution search comprises:

selecting four reduced frames in each direction X and Y;

performing reduced resolution search in blocks 16×

16 using reduced frames; and

obtaining motion for 64×

64 blocks in original frames.

7. The method of claim 1, wherein the motion assignment for 16×

16 blocks is performed using non-parametric local transform.

8. The method of claim 1, wherein the refinement search for 16×

16 blocks comprises;

performing Census transform for every input frame;

splitting the frame into 16×

16 blocks and representing it as 256-byte vector A;

preparing a 256-byte vector B corresponding to the vector A;

preparing a correlation surface filled with zeroes;

receiving vector C by subtracting vector A from vector B element-by-element;

incrementing points of the correlation surface at a position given by vector C;

finding maximum on the correlation surface in full pels; and

interpolating a sub-pixel value using neighbor values on the correlation surface.

9. The method of claim 1, wherein the error distribution analyses comprises:

calculating SAD for every 8×

8 block receiving a 8×

8 error distribution block for every 64×

64 block; and

providing split-merge prediction comprising SPLIT decision optimization and MERGE decision optimization.

10. The method of claim 9, wherein the SPLIT decision optimization comprises:

defining a Split Threshold as desired level of SPLIT sensitivity;

calculating an average SAD of the whole error distribution block (EDB);

marking the EDB as a SPLIT candidate if the difference between any SAD in the EDB and a calculated average SAD is larger than the Split Threshold; and

performing an additional refinement search for every SPLIT candidate block.

11. The method of claim 10, wherein the MERGE decision optimization comprises:

defining a Merge threshold as desired level of MERGE sensitivity;

preparing an EDB pyramid based on averaging 2×

2 block of SADs at each level, wherein the pyramid comprises;

Level 0;

an original EDB block of 8×

8 SADs;

Level 1;

averaged once 4×

4 SADs;

Level 2;

averaged twice 2×

2 SADs; and

Level 3;

one averaged SAD;

at every level from 1 to 3, examining four corresponding SADs to check for a MERGE flag;

if the difference from lower level SAD for all four SADs is no larger than the Merge Threshold, marking this block as a MERGE candidate; and

performing a MERGE check for every block marked as MERGE candidate.