Brevet FR2908007A1 — publié le 20080502

L'invention concerne un procédé de codage d'une séquence d'images, exploitant en particulier le mode de prédiction intra. Le domaine est celui de la compression vidéo pour le stockage ou la transmission de données. On s'intéresse en particulier aux schémas de compression par blocs dans le cadre d'opérations de codage du type MPEG4. Le standard H264/MPEG4 part 10 définit 9 modes de prédiction io intra pour les blocs d'image de dimensions 4x4, 4 lignes de 4 pixels. La figure 1 représente ces différents modes de prédiction. Il définit également 4 modes de prédiction pour des blocs de dimension 16x16, modes de prédiction horizontal, vertical, mode DC et mode plan effectuant une interpolation bilinéaire de valeurs de pixels en fonction de la position dans la 15 ligne et la colonne du pixel à prédire. Pour ces 4 modes de prédiction, le calcul des coefficients DCT est effectué sur des blocs de résidus de taille 4x4. Le mode DC ou mode 2 sur la figure 1 est aussi appelé par la suite mode de codage intra prédictif DC, les autres modes, modes de codage intra directionnels prédictifs. 20 Pour la version MPEG 4 part 10 high profile , la prédiction et le codage DCT peuvent également être appliqués sur des blocs de résidus, blocs courants moins blocs prédits, de taille 8x8. On pourra se référer aux documents décrivant les nouveaux outils relatifs aux extensions FRExt, de l'anglais Fidelity Range Extensions, du standard de codage vidéo 25 H264/MPEG4-AVC, pour une explication plus complète de ces modes. Les modes de prédiction intra font référence à des valeurs de luminance de pixels de blocs voisins ou même du bloc courant pour le mode DC. Ces valeurs de prédiction, positionnées aux emplacements (i, j) des pixels du bloc courant sur lesquels elles agissent, constituent un bloc de 30 prédiction, les emplacements non concernés étant affectés de la valeur luminance nulle. Le bloc de résidus sur lequel est appliqué la transformation 2908007 2 cosinus discrète est obtenu, dans le mode de prédiction intra, par la différence entre le bloc de luminance courant et le bloc de prédiction intra retenu. Pour effectuer le codage en mode intra, dans le standard MPEG4 5 part 10, un macrobloc courant 16x16 est découpé en 4 blocs 8x8, en 16 blocs 4x4 et un test de chacun des modes de codage intra est effectué sur chacun des blocs. Il est d'autre part nécessaire de reconstruire une partie du macrobloc courant, celui qui est donc en cours de codage, pour définir les blocs de prédiction intra 4x4, pour effectuer cette sélection. Un choix est effectué parmi les 9 blocs de prédiction calculés pour un bloc 4x4 du macrobloc courant selon des critères connus tels que le coût de codage et la distorsion pour définir la meilleure prédiction. Un critère de sélection connu est le critère a posteriori basé débit-distorsion, représenté par exemple par l'équation suivante : J =sse + X rate avec sse, somme des erreurs au carré, A un coefficient et rate le nombre exact de bits utilisés pour le codage d'un bloc. Dans cette équation : Nù1 2 sse(s,r) = (sy(i,i)ùry(i,i)) i, j=0 avec N la taille du bloc à encoder en nombre de lignes ou de colonnes, i et j les indices relatifs à la ligne et colonne du bloc, sy et ry les valeurs de luminance du bloc courant source et du bloc prédit décodé ou reconstruit. y indique que les mesures sont effectuées sur les composantes luminance. L'algorithme de décision relatif au choix de codage intra pour le macrobloc de taille 16x16 est relativement simple et ne nécessite pas de puissance de calcul importante, les modes intra testés étant appliqués sur le seul macrobloc. Il en est différemment des blocs 4x4 et 8x8, qui doivent être reconstruits pour pouvoir exploiter les blocs voisins du bloc testé. Le calcul du critère de sélection du mode de codage d'un bloc, celui donnant le 2908007 3 meilleur compromis taux/distorsion, doit être effectué pour l'ensemble des modes de prédiction et est donc très consommateur en termes de puissance de calcul et de temps de traitement de l'unité centrale. La complexité des calculs, dus en partie aux problèmes de récursivité, réduit l'efficacité des 5 circuits de traitement ou nécessite des circuits complexes et coûteux à mettre en oeuvre. Une solution consiste à effectuer deux passes, une première passe basée sur un critère a priori pour sélectionner les meilleurs prédicteurs, par exemple un calcul du type SATD, acronyme de l'anglais io Sum of Absolute Transform Differences et consistant à calculer, pour un bloc de résidus relatif à un bloc prédit, une transformation donnant des coefficients puis la somme de la valeur absolue de ces coefficients. Une deuxième passe permet d'affiner la recherche en exploitant un critère plus élaboré pour les modes retenus lors de la première passe. Ce type de 15 solution n'est cependant pas satisfaisant car il est toujours nécessaire de tester les 9 modes de prédiction pour les blocs de taille 4x4 et les blocs de taille 8x8 et l'économie en termes de coût de calcul ou temps de traitement est limitée, le traitement se faisant en deux passes. La complexité est encore plus grande pour la version high profile . 20 Un des buts de l'invention est de pallier les inconvénients précités. L'invention a pour objet un procédé de codage d'une séquence d'images exploitant des modes de codage intra directionnels prédictifs privilégiant différentes directions de prédiction, pour le codage d'un bloc 25 d'une image, caractérisé en ce que, pour la détermination du mode de codage d'un macrobloc constitué de blocs d'image, il effectue une présélection du ou de modes de codage intra prédictifs directionnels des blocs du macrobloc selon les étapes suivantes : - calcul des activités gradient d'un bloc dans les directions de 30 prédiction, 2908007 4 - présélection du ou des modes de codage intra directionnel du bloc dont les directions correspondent à l'activité ou aux activités gradient de valeur minimum. Selon une mise en oeuvre particulière, la présélection est 5 également effectuée sur le mode de codage intra prédictif DC, une activité DC est affectée au bloc qui est une moyenne pondérée des activités gradient dans les différentes directions de prédiction pour le bloc et ce mode est présélectionné si l'activité est inférieure à l'activité gradient de valeur minimum. io Selon une mise en oeuvre particulière, les modes de codage comportent également des modes de codage inter images, un mode de codage intra non prédictif et un mode de codage intra prédictif DC. Selon une mise en oeuvre particulière, l'étape de calcul de l'activité gradient d'un bloc est effectuée à partir d'une fenêtre de 15 convolution 2D se déplaçant dans le bloc. Selon une mise en oeuvre particulière, les fenêtres de convolution, pour les différentes directions spatiales, sont les suivantes : 0 -1 0 0 0 0 0 0 -1 -1 0 0 Do = 0 0 0 Dl = -1 0 1 D3 = 0 0 0 D4 = 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 -1 0 0 0 0 0 -1 0 0 0 1 20 D5 = 0 0 0 D6 = -1 0 0 D~ = 0 0 0 D8 = -1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 Selon une mise en oeuvre particulière, la détermination du mode de codage est effectuée à partir d'un critère de sélection coût/distorsion. Selon une mise en oeuvre particulière, pour le codage d'un 25 macrobloc de taille 16x16, le procédé comporte - une étape de préanalyse pour le calcul de chacune des énergies directionnelles relatives à chacun des blocs de dimensions 4x4 et à chacun des blocs de dimension 8x8 du macrobloc, 2908007 5 - une étape de présélection de modes de codage intra prédictifs correspondant aux modes de codage intra directionnels relatifs aux énergies les plus faibles, pour chacun des blocs 4x4 et pour chacun des blocs 8x8, - une étape de sélection de modes de codage intra prédictif par 5 bloc en fonction de la valeur d'un critère coût/distorsion J calculé pour chacun de leurs modes présélectionnés, - une étape de sélection de mode pour le macrobloc en fonction de la valeur d'un critère de sélection J calculé pour le macrobloc 16x16 en prenant en compte les critères calculés pour les modes sélectionnés des 10 blocs constituant le macrobloc, la valeur minimale définissant le partitionnement du macrobloc et les modes de codage intra des partitions. Selon une mise en oeuvre particulière, le critère de sélection coût/distorsion J est égal à: J=sse+2^,•rate 15 avec sse, somme des erreurs au carré entre le bloc courant et le bloc prédit, A un coefficient et rate le nombre exact de bits utilisés pour le codage d'un bloc. Selon une mise en oeuvre particulière: Nù1 2 sse(s,r) = (sy(i,i)ùry(i,i)) i, j=0 20 avec N la taille du bloc à encoder en nombre de lignes ou de colonnes, i et j les indices relatifs à la ligne et colonne du bloc, sy et ry les valeurs de luminance du bloc courant source et du bloc prédit décodé ou reconstruit. L'invention concerne également un dispositif de codage mettant 25 en oeuvre le procédé de codage d'une séquence d'images précédemment décrit, caractérisé en ce qu'il comporte un circuit de préanalyse pour la détermination du mode de codage d'un macrobloc, comprenant un circuit de calcul de gradients de blocs du macrobloc. 2908007 6 L'idée de l'invention est de déterminer, pour un bloc, la direction correspondant à la plus forte énergie, le mode intra choisi étant alors celui dont le bloc prédit correspond à cette direction. En effet, la probabilité d'avoir une prédiction la plus proche du bloc est plus grande dans la 5 direction la moins porteuse d'informations différentes, c'est à dire d'énergie la plus faible. Ces énergies sont par exemple définies à partir des valeurs de gradient. Des fenêtres de convolution sont exploitées, chaque fenêtre privilégiant une direction dans le bloc correspondant à une direction parmi io celles relatives aux modes de codage intra proposés par la norme MPEG4. Ces fenêtres permettent de calculer les énergies directionnelles et en particulier la direction possédant la plus forte énergie. Grâce à l'invention, il n'est plus nécessaire de tester l'ensemble des prédicteurs et donc d'effectuer des calculs complexes et longs pour 15 définir un mode de prédiction intra. D'autres particularités et avantages de l'invention apparaîtront clairement dans la description suivante donnée à titre d'exemple non limitatif, et faite en regard des figures annexées qui représentent ; 20 -la figure 1, les différents modes de prédiction pour le codage intra de blocs 4x4, - la figure 2 un organigramme du procédé de codage. Le procédé de codage selon l'invention met en oeuvre un 25 algorithme d'analyse qui permet de réduire le nombre de prédicteurs 4x4 et 8x8 à tester. Il est basé sur une analyse de gradients dans les différentes directions pour déterminer une direction privilégiée d'un bloc de pixels. Pour ce faire, une solution consiste à effectuer des calculs à partir des matrices suivantes. Il s'agit en fait de 8 fenêtres ou noyaux de convolution 2D définis 30 selon les 8 directions précédemment décrites pour la prédiction des modes intra, le mode DC étant exclu. 2908007 Do = D5 = D1= D6 = 7 D3 = D~ = D4 = D8 = 5 0 -1 0 0 0 0 0 1 0 0 -1 0 0 0 0 0 0 1 0 0 0 -1 0 1 0 0 0 0 0 0 -1 0 0 0 0 1 o o -1 0 0 0 1 0 0 0 -1 0 0 0 0 1 0 0 -1 0 0 0 0 0 0 0 1 0 0 1 -1 0 0 0 0 0 Les énergies directionnelles Eo à E$ sont calculées selon l'expression : N-1,N-1 Ed = L(Y*Dd)(i,j) i=o,i=o 10 I et j sont les index des pixels contenus dans la sous-partition ou bloc à encoder, Y est la valeur de luminance d est l'index correspondant aux différentes directions de prédiction, 0 à 8 représentées à la figure 1, 15 * est l'opérateur de convolution. Ed est donc la sommation des NxN convolutions. Par exemple, pour la direction d = 1 et pour le pixel (1, 1) du bloc courant, c'est à dire ligne i=1, colonne j=1, la valeur calculée est la luminance du pixel (1, 2) moins la luminance du pixel (1, 0). L'ensemble des 20 valeurs calculées sur le bloc donne Ed. Il y a donc 16 sommations pour les blocs de dimensions 4x4 et 64 sommations pour les blocs de dimensions 8x8. S'agissant de masques inversés, la valeur d'énergie Ed la plus faible qui correspond donc à la plus faible activité gradient dans cette 25 direction d, définit la direction d et donc le prédicteur à exploiter pour le calcul du codage intra. 2908007 8 Il est possible, plutôt que de ne conserver qu'un seul prédicteur, de sélectionner p prédicteurs donnant les valeurs d'énergie les plus faibles puis de les tester de manière classique, pour n'en conserver qu'un seul. Un premier algorithme de présélection consiste à sélectionner 5 systématiquement, parmi ces p prédicteurs, celui correspondant au mode DC. Par exemple, l'histogramme du bloc source de l'image donnant les valeurs d'énergies Ed du bloc en fonction des modes d de prédiction intra est exploité en forçant la valeur de E2 à zéro. La probabilité de sélection du mode DC est en effet plus grande que celle des autres modes lors de la io mise en oeuvre de l'algorithme de décision de mode de codage intra, par exemple l'algorithme d'optimisation taux/distorsion connu sous l'appellation RDO pour rate distortion optimization . Un bon compromis entre le nombre de calculs à effectuer et la perte engendrée par un moindre choix, consiste à présélectionner les modes 15 correspondant aux 3 énergies les plus faibles parmi les 9 directions disponibles en imposant, parmi les 3 modes, le mode DC. Parmi ces 3 modes, celui sélectionné sera celui donnant la plus faible valeur du critère de sélection J. Un second algorithme de présélection consiste à attribuer une 20 valeur d'énergie particulière au mode DC. Cette valeur est choisie égale à la moyenne pondérée de tous les modes dans chacune des directions, donc excepté D2. d=8 Eavr - g L(Ed) avec d # 2 E2 = Eavr x 0,8125. 25 Cette pondération, par exemple d'un coefficient 0,8125, calculé de manière empirique, permet de favoriser le mode DC lorsque les énergies directionnelles ont des valeurs voisines, la probabilité d'avoir une valeur E2 plus faible que les autres énergies étant plus grande. Et, dans le cas d'énergies uniformes, c'est à dire dans le cas où aucune orientation claire d=0 2908007 9 n'apparaît, l'exploitation du mode de prédiction intra DC paraît le plus pertinent. La figure 2 représente un organigramme du procédé selon 5 l'invention. Un macrobloc courant, de taille 16x16 pixels, de l'image à coder est pris en compte à l'étape 1. Une préanalyse, étape 2, est effectuée sur ce macrobloc. Cette préanalyse consiste à calculer les énergies directionnelles Ed, y compris l'énergie EDc, comme indiqué précédemment, sur les 4 blocs 10 8x8 et les 16 blocs 4x4 composant le macrobloc. N-1,N1 Ed = L(Y*Dd)(i,J) i=oj=o d=8 _ (0,8125)- E(Ed) avec d # 2 8 d=0 Les 2 modes de prédiction directionnelle donnant la plus faible valeur d'énergie ainsi que le mode DC sont par exemple choisis pour chacun 15 des blocs, à savoir 4 x 3 prédictions pour les blocs de taille 8x8 et 16 x 3 prédictions pour les blocs de taille 4x4. L'étape suivante 3 effectue un calcul du critère de sélection J pour chacun des modes d intra retenus à l'étape précédente, appelés modd. Les blocs prédits relatifs aux différents modes intra, mode DC ou modes 20 directionnels, sont définis par exemple au chapitre 8.5 intitulé intra prediction du document relatif à la norme H264 et référencé ISO/IEC 14496-10 ou au chapitre 8.3 intitulé intra prediction process du document ITU-T Rec. H264 (2006). Ces blocs prédits sont exploités pour le calcul du critère de sélection. Cette étape fournit donc une valeur de J pour 25 chacun des 4 blocs 8x8 et chacun des 16 blocs 4x4 du macrobloc. J(modd) = sse(s, predmodd) + 2intra blockcos tmodd 2908007 10 - sse est la somme des erreurs au carré, c'est à dire des différences au carré, pixel à pixel, entre la luminance des pixels du bloc source s et du bloc prédit predmodd pour le mode d. -blockcostmodd correspond au coût de codage du bloc pour le mode 5 d, le paramètre - Àintra est une valeur de coefficient prédéfinie permettant de pondérer le coût et la distorsion de codage lors d'un codage en mode modd. Cette étape effectue ensuite une sélection des modes d correspondant à la plus faible valeur de J, soit un mode d pour chacun des io blocs 8x8 et un mode d pour chacun des blocs 4x4. L'étape 4 qui suit récupère ces 4 + 16 modes et les valeurs de J associées aux modes d sélectionnés ; Elle compare, dans une première phase, la somme des valeurs de J des 16 blocs 4x4 à celle des 4 blocs 8x8. Le mode intra choisi pour le macrobloc, pour cette première phase, qui 15 définit à la fois le partitionnement du macrobloc et le mode des blocs de la partition, est celui donnant la plus faible valeur de J pour l'ensemble du macrobloc. Une deuxième phase consiste à comparer le mode intra ainsi sélectionné et relatif aux prédictions sur des blocs 4x4 ou 8x8 du macrobloc, aux modes de codage intra 16x16 relatifs aux prédictions sur l'ensemble du 20 macrobloc 16x16, pour sélectionner le mode de codage intra le plus efficace. Une étape ultérieure, non représentée sur la figure, consiste à comparer à nouveau ce mode de codage intra aux autres modes de codage mis en oeuvre par le codeur tels que les modes de codage de type inter, pour le choix final du mode de codage du macrobloc. 25 Il serait bien sûr également possible de traiter le mode de codage intra prédictif 16x16 du macrobloc à partir des fenêtres de convolution et donc en même temps que les modes de codage intra prédictifs 4x4 et 8x8, en exploitant les fenêtres correspondant aux directions horizontales et verticales dans le cas ou seules ces directions sont exploitées, c'est à dire 30 dans la version high profile de la norme. Le mode plan peut être traité séparément, par exemple en pondérant la somme des énergies dans les 2908007 11 directions horizontale et verticale mais de manière moindre que pour le mode DC. L'invention concerne également un dispositif de codage mettant 5 en oeuvre le procédé de codage précédemment décrit. Ce dispositif comporte un circuit de préanalyse pour la détermination du mode de codage intra d'un macrobloc. Ce circuit comprend des moyens de calcul de gradients de blocs du macrobloc pour effectuer les calculs des activités gradient des blocs dans les différentes directions. Le circuit de préanalyse 10 présélectionne, pour chaque bloc, par exemple les 2 modes intra directionnels donnant l'activité de gradient la plus faible ainsi que le mode intra DC. Il effectue un calcul classique basé sur le critère coût/distorsion, pour ces modes présélectionnés, pour déterminer le mode intra du macrobloc à comparer aux autres modes mis en oeuvre par le codeur. 15 L'invention a été décrite pour des blocs de taille 4x4 et 8x8 constituant un macrobloc de taille 16x16. Elle s'applique cependant à tout type de bloc dont la taille correspond à une des tailles de bloc choisies pour la définition des modes de codage intra directionnels prédictifs. L'invention 20 peut aussi bien s'appliquer à des blocs de luminance qu'à des blocs de chrominance. Les applications concernent la compression de données, les standards concernés sont le standard MPEG4 part 10 et tous les standards à venir exploitant le mode de codage intra directionnel prédictif. 25 REVENDICATIONS 1. Procédé de codage d'une séquence d'images exploitant des modes de codage intra directionnels prédictifs privilégiant différentes directions de prédiction, pour le codage d'un bloc d'une image, caractérisé en ce que, pour la détermination du mode de codage d'un macrobloc (1, 3, 4) constitué de blocs d'image, il effectue une présélection (2) du ou de modes de codage intra prédictifs directionnels des blocs du macrobloc selon les étapes suivantes : - calcul des activités gradient d'un bloc (2) dans les directions de prédiction, - présélection du ou des modes de codage intra directionnel (2) du bloc dont les directions correspondent à l'activité ou aux activités gradient de valeur minimum. 2. Procédé selon la revendication 1, caractérisé en ce que la présélection est également effectuée sur le mode de codage intra prédictif DC (2), en ce qu'une activité DC est affectée au bloc qui est une moyenne pondérée des activités gradient dans les différentes directions de prédiction pour le bloc et en ce que ce mode est présélectionné si l'activité est inférieure à l'activité gradient de valeur minimum. 3. Procédé selon la revendication 1, caractérisé en ce que les modes de codage comportent également des modes de codage inter images, un mode de codage intra non prédictif et un mode de codage intra prédictif DC (2). 4. Procédé selon la revendication 1, caractérisé en ce que l'étape de calcul de l'activité gradient d'un bloc est effectuée à partir d'une fenêtre de convolution 2D se déplaçant dans le bloc. 5. Procédé selon la revendication 4, caractérisé en ce que les fenêtres de convolution, pour les différentes directions spatiales, sont les suivantes : 2908007 0 -1 0 0 0 0 D 0 = 0 0 0 D1 = -1 0 1 D3= 0 1 0 0 0 0 0 0 -1 0 0 0 1 0 0 -1 0 0 D4= 0 0 0 0 0 1 -0 -1 0 - 0 0 0_ D5= 0 0 0 D6= -1 0 0 0 0 1 _0 0 1 _ 0 -1 0 0 0 1 D,=0 0 0 D8= -1 0 0 1 0 0 0 0 0 6. Procédé selon la revendication 1, caractérisé en ce que la détermination du mode de codage est effectuée à partir d'un critère de sélection coût/distorsion. 7. Procédé selon la revendication 1, pour le codage d'un macrobloc de taille 16x16, caractérisé en ce qu'il comporte - une étape de préanalyse (2) pour le calcul de chacune des énergies directionnelles relatives à chacun des blocs de dimensions 4x4 et à chacun des blocs de dimension 8x8 du macrobloc, - une étape de préselection (2) de modes de codage intra prédictifs correspondant aux modes de codage intra directionnels relatifs aux énergies les plus faibles, pour chacun des blocs 4x4 et pour chacun des blocs 8x8, - une étape de sélection (3) de modes de codage intra prédictif par bloc en fonction de la valeur d'un critère coût/distorsion J calculé pour chacun de leurs modes présélectionnés, - une étape de sélection de mode pour le macrobloc en fonction de la valeur d'un critère de sélection J (3) calculé pour le macrobloc 16x16 en prenant en compte les critères calculés pour les modes sélectionnés des blocs constituant le macrobloc, la valeur minimale définissant le partitionnement du macrobloc et les modes de codage intra des partitions. 8. Procédé selon la revendication 6, caractérisé en ce que le critère de sélection coût/distorsion J est égal à: J=sse+•rate 2908007 14 avec sse, somme des erreurs au carré entre le bloc courant et le bloc prédit, X un coefficient et rate le nombre exact de bits utilisés pour le codage d'un bloc. 9. Procédé selon la revendication 7, caractérisé en ce que: N-1 2 sse(s,r)= E(sy(i, j)-ry(i,_0) i, j=0 avec N la taille du bloc à encoder en nombre de lignes ou de colonnes, i et j les indices relatifs à la ligne et colonne du bloc, sy et ry les valeurs de luminance du bloc courant source et du bloc prédit décodé ou reconstruit. 10. Dispositif de codage pour la mise en oeuvre du procédé selon l'une des revendications précédentes, caractérisé en ce qu'il comporte un circuit de préanalyse pour la détermination du mode de codage d'un macrobloc, comprenant un circuit de calcul de gradients de blocs du macrobloc.