Optimal intra prediction in block-based video coding

1. 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 0 , P 1 , . . . , P 32 :

S 32 ={P 16 };

S 16 ={P 8 , P 24 };

S 8 ={P 0 , P 8 , P 16 , P 24 , P 32 };

S 4 ={P 0 , P 4 , P 8 , P 12 , P 16 , P 20 , P 24 , P 28 , P 32 };

S 2 ={P 0 , P 2 , P 4 , P 6 , P 8 , P 10 , P 12 , P 14 , P 16 , P 18 , P 20 , P 22 , P 24 , P 26 , P 28 , P 30 , P 32 };

presenting planar prediction mode P 33 and DC prediction mode P 34 ; and

performing a logarithmic search inside a set of intra prediction directions to reduce a number of intra predictions to be tested for optimal intra prediction mode;

wherein the optimal mode P j corresponds to a minimal value of a prediction cost function R(P).

2. The method of claim 1 , wherein the logarithmic search comprises:

(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 providing the minimal value of cost function R(P), where K is an index for this intra prediction;

(iii) finding an intra prediction, which minimizes the value of R(P) over Pε{P K , P K−L/2 , P K+L/2 } and setting a value of index K for this intra prediction;

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

if K=2, or R(P K )<T 0 , 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 K−1 , P K+1 , P 33 , P 34 } as a prediction minimizing the value of R(P);

otherwise, the optimal intra prediction is R(P K ).

3. The method of claim 1 , wherein reducing the number of intra predictions for testing comprises:

selecting an initial set containing a small number of intra predictions for testing;

selecting a best angle from the initial set of intra predictions; and

constructing a testing set of intra prediction angles around the best angle from the initial set.

4. The method of claim 3 , wherein the initial set is S 8 ={P 0 , P 8 , P 16 , P 24 , P 32 }.

5. The method of claim 4 , further comprising:

from the initial set finding an intra prediction P K minimizing the value of a cost function R(P), where K is an index of the intra prediction;

setting a threshold T 0 , wherein T 0 is a pre-defined coding parameter;

if R(P K )<T 0 , the optimal intra prediction is P K ;

if R(P K )≧T 0 , testing the following sets of intra predictions:

Q 0 ={P 32 , P 0 , P 1 , P 2 , P 3 , P 5 , P 6 };

Q 8− ={P 4 , P 5 , P 6 , P 7 , P 8 , P 9 , P 10 };

Q 8+ ={P 6 , P 7 , P 8 , P 9 , P 10 , P 11 , P 12 };

Q 16− ={P 12 , P 13 , P 14 , P 15 , P 16 , P 18 , P 19 };

Q 16+ ={P 14 , P 15 , P 16 , P 17 , P 18 , P 19 , P 20 };

Q 24− ={P 20 , P 21 , P 22 , P 23 , P 24 , P 25 , P 26 };

Q 24+ ={P 22 , P 23 , P 24 , P 25 , P 26 , P 27 , P 28 };

Q 32 ={P 0 , P 27 , P 28 , P 29 , P 30 , P 31 , P 32 };

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 K−8 )<R(P K+8 ), Q=Q K− ; and

if R(P K−8 )≧R(P K+8 ); Q=Q K+ ; and

defining the optimal intra prediction P K from the set Q=Q K ∪{P 33 , P 34 }, as the one minimizing the value of R(P).

6. The method of claim 5 , wherein the T 0 is a pre-defined coding parameter depending on at least one of desired speed, quality and block size.

7. The method of claim 3 , comprising constructing and testing a plurality of subsets Q 0 , Q 8− , Q 8+ , Q 16− , Q 16+ , Q 24− , Q 24+ , Q 32 according to desired coding parameters.

8. A video codec comprising a processor configured and arranged to select an optimal intra prediction mode by:

constructing a plurality of sets for angular intra predictions P 0 , P 1 , . . . , P 32 :

S 32 ={P 16 };

S 16 ={P 8 , P 24 };

S 8 ={P 0 , P 8 , P 16 , P 24 , P 32 };

S 4 ={P 0 , P 4 , P 8 , P 12 , P 16 , P 20 , P 24 , P 28 , P 32 };

S 2 ={P 0 , P 2 , P 4 , P 6 , P 8 , P 10 , P 12 , P 14 , P 16 , P 18 , P 20 , P 22 , P 24 , P 26 , P 28 , P 30 , P 32 };

presenting planar prediction mode P 33 and DC prediction mode P 34 ; and

reducing a number of intra predictions to be tested for optimal intra prediction mode by performing a logarithmic search inside a set of intra prediction directions.

9. The video codec of claim 8 , comprising a control circuit configured and arranged to perform the logarithmic search by:

(i) selecting from a plurality of sets of angular intra predictions: 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) selecting from the set S L an intra prediction P K providing the minimal value of cost function R(P), where K is an index for this intra prediction;

(iii) finding an intra prediction, which minimizes the value of R(P) over Pε{P K , P K−L/2 , P K+L/2 }, and setting a value of index K for this intra prediction;

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

if K=2, or R(P K )<T 0 , 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 K−1 , P K+1 , P 33 , P 34 } as a prediction minimizing the value of R(P);

otherwise, the optimal intra prediction is R(P K ).

10. The video codec according to claim 8 , comprising a control circuit configured to reduce a number of intra predictions to be tested by:

selecting an initial set containing a small number of intra predictions for testing;

selecting a best angle from the initial set of intra predictions; and

constructing a testing set of intra prediction angles around the best angle from the initial set.

11. The video codec according to claim 10 , wherein the control circuit is configured and arranged to reduce a number of intra predictions and to test them for optimal intra prediction mode by:

selecting from the initial set {P 0 , P 8 , P 16 , P 24 , P 32 } of intra predictions an intra prediction P K minimizing the value of a cost function R(P), where K is an index of the intra prediction;

setting a threshold T 0 , wherein T 0 is a pre-defined coding parameter;

if R(P K )<T 0 , the optimal intra prediction is P K ;

if R(P K )≧T 0 , testing the following sets of intra predictions:

Q 0 ={P 32 , P 0 , P 1 , P 2 , P 3 , P 5 , P 6 };

Q 8− ={P 4 , P 5 , P 6 , P 7 , P 8 , P 0 , P 10 };

Q 8+ ={P 6 , P 7 , P 8 , P 9 , P 10 , P 11 , P 12 };

Q 16− ={P 12 , P 13 , P 14 , P 15 , P 16 , P 18 , P 19 };

Q 16+ ={P 14 , P 15 , P 16 , P 17 , P 18 , P 19 , P 20 };

Q 24− ={P 20 , P 21 , P 22 , P 23 , P 24 , P 25 , P 26 };

Q 24+ ={P 22 , P 23 , P 24 , P 25 , P 26 , P 27 , P 28 };

Q 32 ={P 0 , P 27 , P 28 , P 29 , P 30 , P 31 , P 32 };

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 K−8 )<R(P K+8 ), Q=Q K− ; and

if R(P K−8 )≧R(P K+8 ); Q=Q K+ ; and

selecting from the set Q=Q K ∪{P 33 , P 34 } the optimal intra prediction P K minimizing the value of R(P).

12. The video codec according to claim 11 , wherein the T 0 is a pre-defined coding parameter depending on at least one of: desired codec speed, block size and quality of encoding.