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

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.