VIDEO COMPRESSION FOR HIGH EFFICIENCY VIDEO CODING

• US 20130121401A1
• Filed: 11/16/2012
• Published: 05/16/2013
• Est. Priority Date: 11/16/2011
• Status: Active Grant

• Current Assignee: Beamr Imaging Ltd.
• Original Assignee: Nikolay Terterov
• Inventors: Zheludkov, Alexander, Martemyanov, Alexey, Terterov, Nikolay
• Granted Patent: US 8,693,551 B2
• Time in Patent Office: Days
• US Class Current: 375/240.02
• 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

Encoding methods directed to making coding decisions and estimating coding parameters including searching for optimal angular prediction in intra-prediction mode; choosing the best intra block subdivision; and providing motion estimation for tree-structured inter coding. The methods are targeted to HEVC specifications of video compression, however, may be used with other video coding standards.

Claims

1. (canceled)

2. A method of choosing an optimal intra prediction mode in block-based video coding, the method comprising:

calculating a minimal activity direction based on texture gradient distribution, the minimal activity direction being defined by a vector (α

(S,W), β

(S,W)) indicating minimal variation of a discrete function P(x, y) inside a spatial aria of block B with weights W;

the vector (α

(S,W), β

(S,W)) being a solution of a minimization problem;

3. The method of claim 2, further comprising calculating a strength of minimal activity direction:

4. A method of selecting an optimal angular intra prediction mode for a block-based video coding, the method comprising:

calculating following functions for a spatial area S including a texture block beginning with coordinates (x, y);

5. The method of selecting an optimal angular intra prediction mode of claim 4, wherein the minimal activity direction for each case j= 1,4 is calculated as a vector (α

(S,W), β

(S,W));

6. The method of claim 5, wherein the four cases j= 1,4 correspond to respective intervals of the angle φ

(S,W);

[0;

π

/4], [π

/4, π

/2], [π

/2, 3π

/4] and [3π

/4, π

].

7. A method of calculating tables for minimal activity directions and corresponding angular prediction modes using signs of E and F and the value of the ratio

8. The method of claim 7, wherein integers K and L are equal to 256.

9. A method of selecting an optimal intra prediction for high efficiency video coding, the method comprising:

choosing a spatial area S including a texture block B of size L×

L, starting with coordinates (x, y);

calculating a minimal activity direction (α

, β

) where α

²+β

²=1, and a corresponding angular intra prediction mode;

defining a set Q of intra predictions for selecting the optimal intra prediction mode P_k, the set Q including at least a plurality of angular intra predictions and a plurality of non-angular intra predictions;

defining constants X₁, X₂, X₃ selected according to desired coding speed and quality;

calculating a minimal activity direction strengths for the block B with weights W;

10. The method of claim 9, wherein the set Q further includes a plurality of angular prediction modes corresponding to angles neighboring the angles defined by the intra prediction mode P_k.

12. The method of claim 10, wherein S coincide with B, and S_j coincide with B_j.

11. A method of choosing a best size for an intra block in high efficiency video coding, the method comprising:

considering a texture block B having size L×

L and weight W and starting from pixel with coordinates (x, y);

constructing four sub-blocks B_j, j ∈

[0,4] of size

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

constructing a reduced resolution 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.

14. The method of motion estimation of claim 13, comprising performing the motion estimation using integer-pel, and assigning quarter-pel after a decision is made.

15. The method of motion estimation of claim 13, wherein the constructing of a reduced resolution image comprises:

representing 64×

64 blocks of original picture as 16×

16 blocks; and

calculating every pixel in reduced image as a weighted sum of pixels in the original picture.

16. The method of claim 15, wherein the reduced resolution image is calculated as follows:

Z_x/4,y/4=(O_x,y+2*O_x+1,y+O_x+2y+2*O_x,y+1′

4*O_x+1,y+1+2*O_x+2,y+1+O_x,y+2+2*O<sub>x−

1,y+2</sub>+O<sub>x−

2,y+2</sub>)/16

wherein;

Z_x/4,y/4 is the pixel of the reduced image; and

O_x,y is the pixel in the original picture.

17. The method of motion estimation of claim 13, wherein the performing a reduced resolution search comprises:

performing Census transform for every input frame;

splitting a frame into 16×

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

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

preparing a correlation surface filled with zeroes;

substructing element-by-element vector A from vector B 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,

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

19. The method of motion estimation of claim 18, 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.

20. The method of claim 13, 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.

21. The method of claim 13, wherein the motion assignment for 16×

16 blocks is performed using non-parametric local transform.

22. The method of claim 13, wherein the refinement search for 16×

16 blocks comprising;

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 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 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.

23. A method for error distribution analyses in inter coding motion estimation, the method comprising:

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;

providing SPLIT decision optimization by;

defining a Split Threshold as desired level of SPLIT sensitivity;

calculating 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; and

providing MERGE decision optimization by;

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 correspondence SADs to check for a MERGE flag;

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

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

24. A method of selecting an optimal directional intra prediction mode in block-based video coding, comprising:

constructing a plurality of sets for angular intra predictions P₀, P₁, . . . , P₃₂;

S₃₂={P₁₆);

S₁₆=P₂₄);

S₈={P₀, P₈, P₁₆, P₂₄, P₃₂};

S₄={P₀, P₄, P₈, P₁₂, P₁₆, P₂₀, P₂₄, P₂₈, P₃₂};

S₂={P₀, P₂, P₄, P₆, P₈, P₁₀, P₁₂, P₁₄, P₁₆, P₁₈, P₂₀, P₂₂, P₂₄, P₂₆, P₂₈, P₃₀, P₃₂};

presenting planar prediction mode P₃₃ and DC prediction mode P₃₄; and

performing a logarithmic search to reduce a number of intra predictions being tested for optimal intra prediction mode.

25. The method of claim 24, comprising:

(i) from a plurality of sets of angular intra predictions selecting a set S_L, a value L∈

{32, 16, 8, 4, 2} and a cost function R(P_K) depending on desired coding parameters;

(ii) from the set S_L selecting an intra prediction P_K minimizing a value of cost function R(P), where K is an index for this intra prediction;

(iii) finding an intra prediction P∈

{P_K, P<sub>K−

L/2</sub>, P_K+L/2} which minimizes the value of R(P) and setting a value of index K for this intra prediction;

(iv) setting a pre-defined threshold T_o depending on desired coding parameters;

if K=2, or R(P_K)<

T₀, going to step (v);

otherwise, performing step (iii) for L=L/2; and

(v) if K=2, selecting a best intra prediction from a set {P_K, P<sub>K−

1</sub>, P_K+1, P₃₃, P₃₄ } as a prediction minimizing the value of R(P);

otherwise, the optimal intra prediction is R(P_K).

26. The method of claim 24, comprising:

selecting from the set S₈={P₀, P₈, P₁₆, P₂₄, P₃₂} an intra prediction P_K minimizing a value of cost function R(P), where K is an index of intra prediction,

set a threshold T₀, T₀ being a pre-defined coding parameter;

if R(P_K)<

T₀, the optimal intra prediction is P_K;

if R(P_K)≧

T₀, testing following sets of intra predictions;

Q₀={P₃₂, P₀, P₁, P₂, P₃, P₅, P₆};

Q₈={P₄, P₅, P₆, P₇, P₈, P₉, P₁₀};

Q₈₊={P₆, P₇, P₈, P₉, P₁₀, P₁₁, P₁₂};

Q₁₆₋

={P₁₂, P₁₃, P₁₄, P₁₅, P₁₆, P₁₈, P₁₉};

Q₁₆₊={P₁₄, P₁₅, P₁₆, P₁₇, P₁₈, P₁₉, P₂₀};

Q₂₄₋

={P₂₀, P₂₁, P₂₂, P₂₃, P₂₄, P₂₅, P₂₆};

Q₂₄₊={P₂₂, P₂₃, P₂₄, P₂₅, P₂₆, P₂₇, P₂₈};

Q₃₂={P₀, P₂₇, P₂₈, P₂₉, P₃₀, P₃₁, P₃₂}.

choosing an intra prediction set Q according to the following requirements;

if K=0 or K=32, the intra prediction set Q=Q_k−

;

if K≠

0 and K≠

32, then;

if R(P<sub>K−

8</sub>)<

R(P_K+8), Q=Q_k−

; and

if R(P<sub>K−

8</sub>)≧

R(P_K+8);

Q=Q_K+; and

finding the optimal intra prediction from the set Q=Q_K∪

{P₃₃, P₃₄}, as the one minimizing the value of R(P).