Brevet FR2899744A1 — publié le 20071012

Procédé et dispositif de codage et de décodage d'une image, notamment d'une séquence d'images vidéo, signal correspondant et produit programme d'ordinateur L'invention concerne un procédé et un dispositif de codage et de décodage d'une image numérisée, notamment d'une séquence d'images vidéo. L'invention concerne également un signal numérique correspondant ainsi qu'un produit programme d'ordinateur pour la mise en oeuvre des procédés de codage et de décodage. Elle s'applique en particulier pour l'amélioration du rapport entre le débit et la distorsion des images vidéo décodées. Un ensemble de données compressé peut être mémorisé en occupant une place mémoire réduite par rapport à l'ensemble initial non compressé. La compression peut concerner différents types de données, par exemples des séquences ou des suites d'images, de son ou d'autres signaux mono ou multidimensionnels. Parmi toutes ces données, les séquences d'images sont connues d'une part pour occuper une grande place mémoire et d'autre part pour nécessiter un débit élevé. Pour résoudre les problèmes de surcharge des réseaux, il est nécessaire de fournir des solutions de compression de plus en plus efficace des signaux pour tous les média et donc en particulier pour la vidéo. Pour les applications vidéo, la compression d'images est réalisée par des codeurs vidéo. L'amélioration de l'efficacité de codage des codeurs se traduit par un meilleur compromis débit / distorsion. En d'autres termes, à qualité constante cela revient à obtenir un flux représentatif des pixels qui prend le moins de place possible ou pour une taille de flux donné, à obtenir une meilleure qualité. La plupart des codeurs vidéo actuels agissent sur des blocs de pixels. Un bloc de pixels est un regroupement de pixels adjacents. Ces codeurs sont basés sur un traitement des informations contenues dans ces blocs qui implique une étape de transformation, une étape de quantification et une étape de codage entropique. En ce qui concerne l'étape de transformation, deux grandes familles de 30 transformation sont connues : - La transformation de type DCT ou Transformée en cosinus discrète (Discrete Cosine Transform dans la littérature anglo-saxonne) est notamment utilisée dans tous les codeurs vidéo normalisés à ce jour (MPEG-1, -2, -3, -4, H263, H264 ...) ainsi que dans la plupart des codeurs d'images fixes de première génération (JPEG). La transformation DCT est notamment décrite dans le document Discrete Cosine Transform : algorithms, advantages, applications de K.R.Rao et P.Yip û Academic Press Professional, Inc., 1990 ; - La transformation par ondelettes est notamment utilisée dans les codeurs d'images fixes du type JPEG 2000, comme décrit par exemple dans le document ISO/IEC 15444 JPEG 2000 Final Committee Draft version 1.0, mars 2000. Les transformations par ondelettes, dites de première génération, sont simples et relativement efficaces, mais souffrent de plusieurs défauts : en particulier elles ne sont pas adaptées à traiter les discontinuités qui apparaissent le long des contours de l'image lorsque ceux-ci ne sont pas orientés selon les lignes ou selon les colonnes. Des solutions à ce problème ont été mises en oeuvre par des transformations dites de secondes génération. Trois de ces transformations connues sont respectivement appelées contourlets , bandelettes et directionlets . Ces transformations s'attachent à détecter les contours dans une image ou portion d'image, puis le filtrage est effectué le long de ces contours. Elles présentent plusieurs inconvénients. La transformation des contourlets est notamment décrite dans le document The contourlet transform : An efficient directional multiresolution image representation de M.N.Do et M.Vetterli, IEEE Transactions on Image Processing, vol. 14, n 12, pages 2091-2106, décembre 2005. Cette transformation n'est pas à échantillonnage critique, c'est-à-dire qu'il y a plus d'échantillons à traiter après la transformation qu'avant. Elle est, de ce fait, assez peu efficace en compression. Les bandelettes sont notamment décrites dans le document Sparse geometric image representation with bandelets de E.Le Pennec et S.Mallat, IEEE Transactions on Image Processing, vol. 14, n 4, pages 423-438, avril 2005, et dans le document Discrete bandelets with geometric orthogonal filters de G.Peyre et S.Mallat, IEEE International Conference on Image Processing (ICIP'05), vol. 1, pages 65-68, septembre 2005. Cette transformation nécessite une déformation généralement appelée warping de chaque bloc de façon à aligner la courbe de régularité qui a été préalablement calculée sur la verticale ou l'horizontale du bloc. De ce fait, le bloc est ré-échantillonné suivant des directions particulières. Il n'y a pas de reconstruction parfaite. De plus, la détermination des courbes de régularité est une opération non systématique et complexe. Les directionlets sont notamment décrits dans le document Directionlets : anisotropic multi-directional representation with separable filtering de V.Velisavljevic et M.Vetterli, IEEE Transaction on Image Processing, september 2005. Cette transformation, contrairement à celles mentionnées précédemment, ne nécessite pas de warping ni de ré-échantillonnage. Elle nécessite cependant le choix d'une direction principale pour l'application de la transformation et le choix d'une direction secondaire pour l'alignement des échantillons issus de la transformation après sous-échantillonnage. Elle n'est donc pas générique. De plus, elle ne mentionne pas comment sont traités les bords de blocs. La transformation DCT privilégie l'axe vertical et l'axe horizontal des images, ces axes n'étant pas nécessairement adaptés à l'orientation des images. Afin de s'adapter aux orientations de l'image, une solution évidente est d'effectuer une rotation de l'image. Des méthodes de rotation d'image ont déjà été proposées, en particulier pour effectuer une rotation globale comme cela est décrit par exemple dans le document Convolution-based interpolation for fast, high-quality rotation of images , IEEE Transactions on Images Processing, octobre 1995. La plupart de ces méthodes s'appliquent à une image complète. En effet, la rotation des blocs individuels d'une image pose des problèmes de recouvrement et découvrement qui sont très difficiles à résoudre. Ces méthodes sont généralement basées sur une rotation matricielle associée à une interpolation des données, cette interpolation étant nécessaire pour retomber sur des positions entières de pixels. La qualité de l'algorithme dépend dans ce cas directement de la qualité d'interpolation. Dans tous les cas, le procédé n'est pas réversible. Toutes les méthodes décrites précédemment tentent de s'adapter au contenu des blocs de pixels. Comme cela été montré, ces méthodes présentent en particulier plusieurs inconvénients : - Elles doivent déterminer l'orientation ou les orientations principales dans chaque bloc avant traitement, cette analyse étant non déterministe car dépendant notamment de l'algorithme utilisé ; -Elles effectuent un warping et donc un ré-échantillonnage avec interpolation des données des blocs, non réversible ; - Elles n'utilisent pas les transformations utilisées dans les processus standards, mais s'adaptent au signal. Un but de l'invention est notamment de pallier les inconvénients précités, en permettant en particulier de conserver la transformation, par exemple de type DOT, telle qu'elle existe dans les codeurs actuels. A cet effet, l'invention a pour objet un procédé de codage d'une image numérisée utilisant une transformation par blocs de pixels où des permutations de pixels sont définies pour des tailles de blocs Bj : - un redressement de l'orientation des blocs Bj étant effectué selon chaque permutation définie ; - un codage de chacun de ces blocs Bj redressés étant simulé pour calculer le débit du flux de données après codage et la distorsion de l'image reconstruite après codage et décodage ; une permutation étant sélectionnée pour chaque bloc selon un critère donné fonction du débit et de la distorsion, la transformation étant appliquée aux blocs redressés selon leur permutation sélectionnée. Avantageusement, les blocs étant regroupés à l'intérieur de macroblocs MBk pour former une partition, pour chaque macrobloc MBk des permutations de pixels sont définies pour des tailles de blocs différentes à l'intérieur d'un macrobloc, le débit du flux de données relatif au macrobloc après codage du macrobloc étant calculé à partir des débits de chacun des blocs et la distorsion de l'image reconstruite induite par le codage du macrobloc étant calculée, une partition étant sélectionnée en fonction d'un critère donné fonction du débit et de la distorsion. Le critère utilisé est par exemple le minimum de débit pour une distorsion donnée ou le minimum de distorsion pour un débit donné. De façon systématique, les permutations peuvent être définies pour toutes 35 les tailles possibles de blocs Bj, un redressement étant effectué pour chacun de ces blocs. De même, elles peuvent être définies pour tous les modes de prédictions, spatiales intra ou temporelles inter. Avantageusement, les orientations des blocs composant une partition sont par exemple calculées préalablement. Les blocs Bj ayant une orientation comprise dans un même intervalle d'angles peuvent alors être soumis à un même redressement, le codage simulé pour obtenir le rapport débit/distorsion étant effectué pour au moins un de ces blocs. Après codage d'un macroblocs MBk, son en-tête comporte par exemple les informations de permutation des blocs Bj le composant. Avantageusement, l'en-tête peut comporter une seule information de permutation pour tous les blocs du macrobloc. Les permutations sont par exemple effectuées en lignes ou en colonnes. La transformation est par exemple une transformation en cosinus discrète DOT. Les blocs sont par exemple redressés selon l'axe horizontal ou l'axe vertical de l'image. L'invention concerne également un procédé de décodage d'une image numérisée utilisant une transformation par blocs de pixels et comportant une phase de réception des informations de codage des blocs et de décodage de ces blocs à partir desdites informations. Le procédé de décodage comporte en outre une phase de réception et de décodage des informations de permutation des blocs et une phase de redressement des blocs selon les permutations inverses. Les permutation inverses sont par exemple effectuées en lignes ou en colonnes. Chaque bloc a par exemple sa propre information de permutation. Une image étant découpée en macroblocs de pixels codés chacun avec un en-tête, l'en-tête d'un macrobloc est par exemple décodée avec les informations de permutation des blocs Bj composant le macrobloc. L'en-tête peut comporter une seule information de permutation pour tous les blocs du macrobloc. L'information de permutation est par exemple décodée de manière prédictive. L'invention concerne également un dispositif de codage pour la mise en oeuvre du procédé de codage précédent, le dispositif comportant des moyens d'application d'une transformation par blocs de pixels et des moyens de réorganisation des pixels : - pour définir des permutations de pixels (Oi) pour des tailles de blocs Bj - pour effectuer un redressement de l'orientation des blocs Bj selon chaque permutation définie ; - pour simuler un codage de chacun de ces blocs Bj redressés pour calculer le débit du flux de données après codage et la distorsion de l'image reconstruite après codage et décodage ; une permutation étant sélectionnée pour chaque bloc selon un critère donné fonction du débit et de la distorsion, la transformation étant appliquée aux blocs redressés selon leur permutation sélectionnée. Avantageusement, les moyens de réorganisation des pixels sont par exemple implantés dans les moyens d'application de la transformation par 15 blocs. L'invention concerne également un dispositif de décodage pour la mise en oeuvre du procédé de décodage précédent, comportant des moyens de réception des informations de codage des blocs et des moyens de décodage 20 de ces blocs à partir desdites informations. Le dispositif comporte en outre des moyens de réception et de décodage des informations de permutation des blocs et des moyens de redressement des blocs selon les permutations inverses. Une image étant découpée en macroblocs de pixels MBk, il comporte par 25 exemple des moyens de décodage de l'en-tête d'un macrobloc, l'en-tête comportant les informations de permutation des blocs Bj le composant. L'invention concerne également un produit programme d'ordinateur comprenant des instructions de programme pour l'exécution du procédé de 30 codage précédent et un produit programme d'ordinateur comprenant des instructions de programme pour l'exécution du procédé de décodage précédent. L'invention concerne enfin un signal comprenant une image numérisée 35 codée par utilisation d'une transformation par blocs. Le signal comporte une information de permutation des blocs, une information de permutation étant utilisée pour effectuer le redressement d'un bloc selon la permutation inverse après décodage du bloc. Une image étant découpée en macroblocs de pixels MBk, le signal comporte par exemple un en-tête pour chaque macrobloc comportant les informations de permutation des blocs Bj composant le macrobloc. L'image s'intègre par exemple dans une séquence d'images vidéo. D'autres caractéristiques et avantages de l'invention apparaîtront à l'aide de la description qui suit faite en regard de dessins annexés qui représentent : - la figure 1, une illustration par un synoptique d'un codeur vidéo ; - la figure 2, une illustration des étapes possibles d'un procédé de codage selon l'invention ; - la figure 3, une illustration d'un exemple d'étape de redressement ; 15 - la figure 4, une illustration de l'étape de détermination d'une permutation optimale d'un bloc de pixels ; - la figure 5, un exemple de partition d'un macrobloc dans lequel peut être appliqué le procédé de codage selon l'invention ; - la figure 6, une illustration d'une solution avantageuse permettant 20 d'économiser des bits de l'information d'orientation contenue dans l'en-tête d'un macrobloc ; - la figure 7, une illustration des étapes d'un procédé de décodage selon l'invention ; - la figure 8, une représentation simplifiée de dispositifs de codage et de 25 décodage pour la mise en oeuvre des procédés de codage et de décodage selon l'invention ; - la figure 9, une illustration d'une variante de mise en oeuvre du procédé de codage selon l'invention permettant une accélération de traitement. 30 La figure 1 présente par un synoptique un codeur vidéo 10 de type H.264. A titre d'exemple, l'invention sera décrite par la suite pour un codeur de ce type. Le codeur vidéo 10 est apte à coder une séquence vidéo en un flux de données 20. Une séquence d'images vidéo 1 est enregistrée par un capteur 35 non représenté. L'enregistrement comporte des informations décrivant les images, plus particulièrement les coordonnées et caractéristiques des pixels formant l'image. Par la suite on appellera aussi pixels les informations enregistrées. Dans tout codeur vidéo normalisé, les images sont au préalable découpées en macroblocs, par exemple 16x16 pixels, avant d'être traitées. Dans le cas du codeur vidéo H.264, il existe plusieurs modes de codage, un mode 16x16 pixels, un mode 8x8 pixels et un mode 4x4 pixels. Les pixels formant les images présentes à l'entrée 2 du codeur sont donc regroupés par blocs. Chaque bloc correspond par exemple à une partie 3, par exemple à un carré ou à un rectangle, de l'image 1. Une image est donc découpée en blocs, la taille des blocs pouvant varier. Les blocs subissent une transformation et une quantification 4 à l'intérieur du codeur. Il est à noter que tous les blocs avant transformation contiennent uniquement de l'information résiduelle, dans le cas par exemple du H.264, puisqu'ils ont subi une prédiction 5. Ils subissent soit une prédiction intra, soit une prédiction inter, connues par ailleurs. Une image codée par rapport à elle-même dite image "intra", est nécessaires pour le rafraîchissement et pour permettre un accès aléatoire dans la séquence. Une image dite inter est codée par rapport à une ou plusieurs images de référence. De manière classique, après la prédiction, les données résiduelles de chaque bloc, intra et/ou inter, sont transformées en utilisant l'une des transformations du codeur H.264. Le codeur comporte par ailleurs une estimation des mouvements 7 à l'intérieur des images à partir de laquelle est réalisée une compensation de mouvement 8 qui sert à la prédiction des images. En sortie du circuit de transformation 4, les images sont reconstruites par une quantification et une transformation inverses 9 pour obtenir un ensemble d'images reconstruites 11 utilisées pour la prédiction des images suivantes. Enfin, à la suite de la transformation 4, les données subissent un codage entropique 12. La sortie du circuit de codage entropique 12 forme la sortie du codeur vidéo. On obtient en sortie de ce circuit le flux de données 20. Comme indiqué précédemment, le codeur vidéo de la figure 1 exécute donc successivement les étapes de transformation et quantification 4, ainsi que de codage entropique 12. Ces étapes peuvent être réalisées par un processeur implanté dans le codeur. Le codeur comporte par ailleurs de l'espace mémoire pour stocker les images reconstruites ou autres données intermédiaires ou de codages qui seront décrites par la suite. La figure 2 illustre des étapes possibles pour la mise en oeuvre du procédé de codage selon l'invention, ces étapes sont mises en oeuvre avant l'étape de transformation. Plus particulièrement, l'image étant découpée en macroblocs ou en blocs 21, le procédé selon l'invention détermine pour chaque bloc une permutation qui permet d'obtenir un gain de codage. Pour cela, le procédé selon l'invention effectue un redressement du bloc suivant au moins l'une de ses composantes pour la texture. De préférence, et pour optimiser la transformation DCT appliquée par la suite, les blocs sont redressés selon l'un des axes de la transformation DOT, c'est-à-dire par exemple l'axe horizontal ou l'axe vertical. Le procédé selon l'invention comporte donc une étape 22 de détermination de la permutation optimale pour chaque bloc du macrobloc suivie d'une étape 23 de redressement des blocs par la permutation ainsi déterminée. La permutation optimale est celle qui donne par exemple le meilleur rapport débit/distorsion. Cette étape 23 est suivie d'une étape 24 de codage des macroblocs. Dans cette étape 24, les macroblocs sont codés classiquement avec les circuits 4, 12 du codeur vidéo. Dans le cas du codeur H.264 les macroblocs sont transformés avec la DCT 4x4 avant quantification et codage entropique. La figure 2 illustre le codage d'un macrobloc, mais le procédé qu'elle décrit peut aussi s'appliquer pour le codage d'un bloc. La figure 3 illustre l'étape 23 de redressement des blocs. Plus particulièrement la figure 3 illustre les orientations possibles d'un bloc 4x4 pixels et leurs redressements vers l'axe horizontal ou vertical. L'orientation d'un bloc correspond en fait à l'orientation de sa texture, elle-même définie par l'agencement des pixels et de leurs caractéristiques lumineuses. La figure 3 illustre un cas simple où le bloc est composé de pixels noirs et de pixels blancs. Pour un bloc 4x4, il existe par exemple sept orientations simples dont six 31, 32, 33, 34, 35, 36 sont représentées sur la figure 3. La première orientation, non représentée correspond au cas où le bloc a déjà une orientation horizontale ou verticale. Les autres orientations simples, considérées selon le sens trigonométrique, sont illustrées par : - un bloc 31 ayant une orientation HI, positive, et un bloc 32 ayant une orientation H2, négative, proche de l'horizontale lorsque le bloc a une 5 orientation située dans un intervalle autour de 26,565 par rapport à l'horizontale ; - un bloc 33 ayant une orientation proche de la verticale positive et un bloc 34 ayant une orientation proche de la verticale négative, lorsque le bloc a une orientation située dans un intervalle autour de 63,435 10 par rapport à l'horizontale ; - un bloc 35 ayant une orientation proche de la diagonale positive et un bloc 36 ayant une orientation proche de la diagonale négative, lorsque le bloc a une orientation située dans un intervalle autour de 45 par rapport à l'horizontale. 15 A chacune de ces orientations correspond un redressement particulier du bloc réalisé par des permutations circulaires des pixels 37, ces permutations étant réalisées selon les lignes ou les colonnes. Ainsi, le bloc 31 dont l'orientation est proche de l'horizontale positive est redressé pour former un bloc 38 ayant une orientation horizontale. Dans l'exemple de ce bloc 31, 20 deux pixels noirs sont situés en bas des deux premières colonnes et deux pixels noirs sont centrés dans les deux dernières colonnes. Une permutation circulaire 39 est par exemple appliquée sur les pixels de la première colonne. Une même permutation circulaire est appliquée sur les pixels de la deuxième colonne. Les pixels des troisième et quatrième colonnes bien orientés autour 25 de l'horizontale restent inchangés. Après ces deux permutations, le bloc est orienté horizontalement, les pixels noirs se trouvant tous répartis autour de l'horizontale. Les autres blocs subissent des redressements analogues, par permutations circulaires de lignes ou de colonnes. Les blocs 33, 34 proches de la verticale sont redressés pour former un bloc à orientation verticale et 30 les blocs 35, 36 proches de la diagonale sont redressés par exemple vers l'horizontale. Connaissant l'orientation initiale d'un bloc, donnée par sa texture, il est aisé de définir les permutations circulaires de pixels, en lignes ou en colonnes, qui orientent la texture selon l'axe vertical ou l'axe horizontal. D'autres modes de redressement pourraient être adoptés. Le principe de redressement par permutations circulaires a été décrit pour le bloc 31 d'orientation proche de l'horizontale. On obtient de la même manière des blocs redressés 38 pour les autres blocs 32, 33, 34, 35, 36 orientés différemment. Des redressements, obtenus selon le même principe, peuvent aussi s'appliquer à des blocs 8x8 pixels et 16x16 pixels. Pour un bloc 8x8 on peut par exemple sélectionner quinze orientations possibles : - le bloc est dit "non orienté" s'il a une orientation horizontale ou verticale, c'est-à-dire qu'il n'est pas candidat à un redressement ; - le bloc a une orientation proche de l'horizontale, positive ou négative, s'il a une orientation située dans un intervalle autour de 14,036 par rapport à l'horizontale ; - le bloc a une orientation proche du milieu de l'horizontale, positive ou négative, s'il a une orientation située dans un intervalle autour de 15 26,565 par rapport à l'horizontale ; - le bloc a une orientation proche de la diagonale horizontale, positive ou négative, s'il a une orientation située dans un intervalle autour de 36,870 par rapport à l'horizontale ; - le bloc a une orientation proche de la diagonale, positive ou négative, 20 s'il a une orientation située dans un intervalle autour de 45 par rapport à l'horizontale ; - le bloc a une orientation proche de la diagonale verticale, positive ou négative, s'il a une orientation située dans un intervalle autour de 53,130 par rapport à l'horizontale ; 25 - le bloc a une orientation proche du milieu de la verticale, positive ou négative, s'il a une orientation située dans un intervalle autour de 63,435 par rapport à l'horizontale ; - le bloc a une orientation proche de la verticale, positive ou négative, s'il a une orientation située dans un intervalle autour de 75,964 par 30 rapport à l'horizontale. A chacune de ces orientations correspond un redressement particulier du bloc 8x8 réalisé par des permutations circulaires des pixels, de lignes ou de colonnes, comme décrit précédemment. Pour un bloc 16x16 pixels, on peut sélectionner de façon analogue trente et 35 une orientations possibles : une non-orientation et trente orientations, positives ou négatives, lorsque par exemple le bloc a une orientation située dans un intervalle autour de 7,125 , 14,036 , 20,556 , 26,565 , 32,005 , 36,870 , 41,186 , 45 , 48,814 , 53,130 , 57,995 , 63,435 , 69,444 , 75,964 , ou 82,875 . A chacune de ces orientations correspond un redressement particulier du bloc 16x16 réalisé par des permutations circulaires des pixels, de lignes ou de colonnes, selon le même principe que pour les blocs 4x4 et 8x8. La figure 4 illustre l'étape 22 de détermination de la permutation optimale des blocs d'un macrobloc en vue d'obtenir la meilleure partition au sens du rapport débit/distorsion. Cette étape 22 part d'une image 21 découpée en macroblocs 16x16 pixels. Un macrobloc peut être composé de différents blocs selon différentes partitions. Ainsi un macrobloc 16x16 peut être composé de deux blocs 8x8 et de huit blocs 4x4, d'autres partitions sont possibles. La figure 5 décrite par la suite illustre un exemple de partition pour un macrobloc 16x16 pixels. Cette étape 22 opère de façon systématique, c'est-à-dire qu'elle teste toutes les permutations possibles et conserve la meilleure partition. Par cette série de tests et la sélection de la meilleure partition pour chaque macrobloc, le procédé selon l'invention effectue une réorganisation des pixels dans les macroblocs avant l'étape de transformation. Dans le cas du codeur vidéo H.264, il existe plusieurs modes de codage, un mode 16x16, un mode 8x8 et un mode 4x4. Selon l'invention ils sont tous testés afin d'en extraire le meilleur au sens débit/distorsion. Le procédé selon l'invention va donc effectuer les tests 41 de toutes les permutations 16X16, les tests 42 de toutes les permutations 8x8 et les tests 43 de toutes les permutations 4x4. Les tests effectués vont être décrits par la suite. Dans le cas d'un codeur vidéo H.264 par exemple, lorsque le mode 16x16 est utilisé, on teste chacune des trente et une orientations définies précédemment avec les redressements correspondants dans tous les modes de prédictions, spatiales intra ou temporelles inter,. Les macroblocs ainsi redressés, dans chacun des modes et chacune des orientations, sont ensuite codés classiquement. Ils sont ainsi par exemple codés par la transformation DCT 4X4 et la transformation Hadamard DC. Puis on leur applique une quantification et un codage entropique. De préférence, les macroblocs ainsi codés ne sont pas mis en mémoire dans le codeur, seuls leurs rapports débit/distorsion sont sauvegardés. Puis ces rapports débit/distorsion sont analysés. Le mode de prédiction et l'orientation donnant le meilleur rapport débit/distorsion sont alors conservés 44 avec ce rapport. Pour obtenir ce meilleur rapport débit/distorsion, le procédé selon l'invention opère par exemple comme suit : - il effectue la somme des débits pour obtenir le débit global du macrobloc ; - il calcule la distorsion globale sur tout le macrobloc, entre l'ensemble du macrobloc codé puis décodé, quel que soit le mode, et l'original. La distorsion d'un macrobloc peut être donnée par l'erreur quadratique D définie selon la relation suivante : D = Zm Zn (iMB(m, n) ù IMB(m, n))2 (1) où iMB(m, n) est le pixel considéré du macrobloc original, m et n étant respectivement les rangs en colonne et en ligne du pixel dans le macrobloc, m et n sont compris entre 1 et 16. ÎMB(m, n)) est le pixel dans le macrobloc reconstruit selon les rangs m et n. De la même manière que dans le cas 16x16, on teste chacune des quinzeorientations définies pour les blocs 8x8, avec leurs redressements correspondants. Cependant ces blocs 8x8 peuvent avoir plusieurs structures. Si la norme FRExt, extension de la norme AVC, est utilisée, le mode de codage 8x8 est disponible. Dans ce cas, en intra il y a 9 modes de prédiction spatiale, identiques à ceux du cas 4x4, et en inter et intra la transformation DCT 8x8 peut être effectuée. Si la norme FRExt n'est pas utilisée, le mode de codage 8x8 est indisponible. En intra, le codeur utilise des blocs 8x8 composés de quatre blocs 4x4 prédits spatialement en 4x4. Neuf modes de prédiction pour les quatre blocs font 94 = 6561 possibilités si tous les modes sont testés. Tous ces blocs 8x8 redressés, avec ou sans FRExt, dans chacun des modes et chacune des orientations, sont ensuite codés classiquement avec la transformation disponible, la quantification et le codage entropique. Comme précédemment, ils ne sont pas mis en mémoire, seuls leurs rapports débit/distorsion étant sauvegardés. Le mode de prédiction, avec FRExt pour le bloc 8x8, ou les modes de prédiction, sans FRExt pour les quatre blocs 4x4, ainsi que l'orientation, pour le bloc 8x8 dans les deux cas, correspondant au meilleur rapport débit/distorsion sont alors conservés 45 avec ce dernier. Comme dans les deux cas précédents, chacune des sept orientations de blocs 4x4 est testée avec son redressement correspondant. Les blocs 4x4 sont également issus de prédictions spatiales en intra, selon neuf modes, et temporelles en inter. Tous les blocs ainsi redressés 38 sont ensuite codés classiquement. Le mode de prédiction et l'orientation donnant le meilleur rapport débit/distorsion sont alors conservés 46 avec ce dernier. Quel que soit le mode utilisé, 16x16, 8x8 ou 4x4, on détermine donc le rapport débit/distorsion comme décrit précédemment pour le mode 16x16 conformément à la relation (1). Cela permet ensuite de comparer les trois rapports débit/distorsion 44, 45, 46 pour le macrobloc, rapports correspondant chacun à un des trois modes 16x16, 8x8 ou 4x4. Le meilleur rapport débit / distorsion parmi ces trois définit la meilleure partition avec son orientation associée. Cette partition est alors sélectionnée, elle donne notamment le mode de codage à utiliser pour le macrobloc, soit 16x16, soit 8x8, soit 4x4. Le macrobloc redressé est conservé 47, avec les informations de permutation des pixels qui ont permis le redressement du macrobloc. La figure 5 illustre une partition de macrobloc MBk hybride, c'est-à-dire que le macrobloc MBk comporte des blocs 8x8 et des blocs 4x4. La figure 5 illustre plus particulièrement un exemple de partition d'un macrobloc. Dans cet exemple, le macrobloc Bk comporte deux blocs Bk8 à 8x8 pixels et huit blocs Bk4 à 4x4 pixels. Les étapes de codage décrites précédemment s'appliquent à des blocs ou à des macroblocs homogènes, c'est-à-dire des macroblocs composés de blocs de mêmes tailles, soit 8x8 seulement ou 4x4 seulement par exemple. Le cas 16x16 correspond au cas où le macrobloc forme un bloc unique. Le procédé selon l'invention peut néanmoins s'appliquer à un macroblocs hybrides en décomposant par exemple celui-ci en sous-macroblocs homogènes. Dans le cas de la partition de la figure 5, le procédé peut s'appliquer à un premier sous-macrobloc composé des deux blocs Bk8 à 8x8 pixels et à un deuxième sous-macrobloc composé des huit blocs Bk4 à 4x4 pixels. On considère donc par la suite un macrobloc MBk homogène, sachant que si l'on part d'un macrobloc hybride, il est toujours possible de se ramener à plusieurs blocs ou macroblocs homogènes. Pour chaque macrobloc MBk d'une image, k étant compris entre 1 et K, le procédé selon l'invention recherche donc la meilleure partition et les permutations associées. C'est-à-dire que pour chaque taille i de blocs possible, par exemple 16x16, 8x8 ou 4x4, il y a recherche de la meilleure permutation pour chaque bloc Bk compris dans le macrobloc. La figure 5 illustre une partition parmi d'autres où les permutations sont effectuées sur les blocs Bk8, Bk4 ainsi que sur l'ensemble du macrobloc MBk. Une suite d'opérations pour mettre en oeuvre le procédé tel que décrit précédemment peut donc être la suivante : Pour chaque bloc Bj et chaque permutation Oi proposée : - on effectue un redressement du bloc Bj selon la permutation, i étant compris entre 0 et Imax, Imax variant avec la taille du bloc, Imax étant égal à 6 pour les blocs 4x4 des codeurs H.264 comme l'illustrent les six permutations possibles de la figure 3 ; - on simule le codage du macroblocs, par exemple par une transformation DCT, une quantification et un codage entropique, pour 20 obtenir le débit et la distorsion ; - on calcule par exemple le rapport débit/distorsion, et on le conserve s'il est meilleur que le précédent. A l'issue de cette suite d'opérations, on obtient la meilleure permutation Oopt,Bj correspondant au meilleur rapport débit/distorsion pour le bloc Bj. 25 Enfin, on mémorise la meilleure partition Pk du macrobloc MBk et les permutations Oopt,Bj associées aux blocs Bj la composant. Un exemple de critère retenu pour sélectionner une permutation ou une partition est la valeur du rapport débit/distorsion. Ce critère peut correspondre à l'un des deux critères, l'un correspondant à un débit minimum 30 pour pour une distorsion donnée et l'autre correspondant à une distorsion minimum pour un débit donné. Après le pré-traitement d'orientation, effectué dans les étapes 22, 23 précédemment décrites, le macrobloc est codé classiquement avec les 35 moyens du codeur vidéo, dans l'étape suivante 24. Dans le cas du codeur H.264 le macrobloc est transformé avec la DCT 4x4 avant quantification et codage entropique. Une fois le macrobloc codé, il faut lui adjoindre l'information d'orientation, plus particulièrement l'information de permutations des pixels. Cette information sera utilisée lors du décodage du macrobloc. Les permutations appliquées aux pixels ont notamment été illustrées relativement à la figure 3. Cette information peut être par exemple codée dans l'en-tête du macrobloc. En particulier, dans la norme H.264, chaque macrobloc possède un en-tête dans lequel est explicité le mode de prédiction utilisé pour le codage, ces modes étant notamment le mode de prédiction intra, le mode de partitionnement en inter ou encore les modes de découpage 16x16, 8x8, 4x4. Selon le type de macrobloc, il peut ou non être découpé en quatre blocs 8x8 qui possèdent eux-mêmes leur type de prédiction. Une première solution consiste à insérer l'information d'orientation au niveau de cette information de prédiction du macrobloc ou du bloc avec cet en-tête pour que le décodeur puisse prendre connaissance de l'état d'orientation. Cette solution peut être cependant coûteuse en terme de volume d'information supplémentaire. Si le macrobloc est découpé en blocs 4x4, il faut transmettre trois bits d'information par bloc 4X4, ce qui est coûteux, ces trois bits étant nécessaires pour coder l'un des sept états d'orientation possibles tels qu'illustrés par la figure 3 notamment. Pour coder les quinze états d'orientation des blocs 8x8, quatre bits sont nécessaires par exemple. La figure 6 illustre une solution avantageuse qui permet d'économiser des bits de codage de l'information d'orientation contenue dans l'en-tête d'un macrobloc. Cette solution utilise une syntaxe analogue à celle des modes de prédiction intra. Dans la norme H.264 par exemple, chaque macrobloc possède un en-tête dans lequel est explicité le mode de codage utilisé, mode de partition intra ou mode de partition en inter notamment. Avantageusement, l'information de permutation des blocs composant le macrobloc peut être indiquée dans l'en-tête du macrobloc. Cette information d'orientation des blocs est par exemple indiquée de manière conditionnelle dans l'en-tête du macrobloc. En effet, les permutations pour les blocs voisins sont souvent très corrélées. Afin de tirer parti de cette corrélation, l'invention utilise un codage prédictif pour les blocs 4x4 ou 8x8, c'est-à-dire que pour chaque bloc E à encoder, l'encodeur et le décodeur calculent un prédicteur, par exemple le minimum de la permutation des blocs voisins A et B. Si l'un des blocs voisins A, B n'est pas disponible le mode de permutation est par exemple 0, indiquant l'absence de permutation. L'encodeur transmet alors un indicateur pour chaque bloc 4x4. Si l'indicateur est à l'état 1 par exemple, la prédiction la plus probable est utilisée. Sinon, un autre paramètre est transmis dans le flux pour indiquer un changement de mode. Avantageusement, il y a ainsi une seule information de permutation pour tous les blocs du macrobloc. ~o La suite d'instructions qui suit donne un exemple de syntaxe algorithmique permettant d'appliquer ce codage. mb_pred( mb_type ) { if( MbPartPredMode( mb_type, 0) = = Intra_4x4 I I MbPartPredMode( mb_type, 0) = = Intra_16x16 ) { If( MbPartPredMode( mb_type, 0) = = Intra_4x4 ) for( Iuma4x4Blkldx=0; Iuma4x4Blkldx Else If(MbROTPredMode ( mb_type, 0) = = 4x4 ) for( luma4x4Blkldx=0; luma4x4Blkldx Afin de tirer parti de la corrélation des permutations de blocs voisins, un codage prédictif est prévu pour les blocs 4x4, 8x8 ou 16x16. Le codeur transmet ainsi par exemple un indicateur pour chaque bloc 4x4 prev_4x4_ ROT_mode_flag , ou prev_8x8_ ROT_mode_flag pour le mode 8x8. Si l'indicateur flag est "1", la prédiction la plus probable est utilisée. Sinon, un autre paramètre rem_4x4_ROT_mode est transmis dans le flux pour indiquer un changement de mode. Il en est de même avec le paramètre rem_8x8_ROT mode pour le mode 8x8. Avantageusement, les macroblocs peuvent être regroupés pour former des régions. En effet, l'orientation des blocs étant déterminée, il est possible de fusionner les blocs de même orientation pour obtenir des ensembles de blocs ou régions de même orientation. Ces ensembles peuvent alors être redressés en une seule opération, ce qui est plus rapide et plus économique que de redresser chacun des blocs constituant l'ensemble. La figure 7 illustre le procédé de décodage des macroblocs ou des blocs. Le processus de décodage doit notamment prendre en compte la réorganisation des pixels effectuée dans les blocs lors du codage avant l'étape de transformation afin de restituer correctement les images. Le décodage appliqué est par exemple celui du décodeur vidéo utilisé. Dans le cas de la norme H.264, il est possible d'utiliser le décodeur défini par la norme JVT û ISO/IEC 14496 û 10 û ITU-T Recommendation H.264, Advanced video coding for generic audio-visual services , Draft ITU-T Recommendation and Final Draft International Standard, JVT û G050r1, 2003. Le décodage commence par une phase 61 de réception des macroblocs. Le flux vidéo est reçu par le décodeur, ce flux contient les informations relatives aux macroblocs codés. Ainsi pour chaque macrobloc, le décodeur reçoit : - les informations de codage classique des blocs constituant le macrobloc, telles que la texture ou le mouvement notamment ; - les informations d'orientation, plus particulièrement les informations de partitions et de permutation des blocs. Le décodage est appliqué en plusieurs phases 62, 64. Dans une première 35 phase 62, le décodeur effectue un décodage classique des blocs à partir des informations classiques précitées, c'est-à-dire un décodage entropique ainsi que la quantification inverse et la transformation inverse de celle qui avait été réalisée dans la phase de codage. Dans le cas de la norme H.264 le décodeur effectue le décodage entropique CABAC, la quantification inverse et la transformation inverse DCT entière 4x4. A partir de la réception 63 des informations indiquant la partition et les permutations des blocs, le redressement 64 des blocs est réalisé selon les permutations inverses. Pour cela le décodeur utilise les informations de permutation fournies par le codeur. Si le bloc considéré est orienté, ayant un état différent de 0, le décodeur applique à ce bloc le traitement inverse de celui appliqué pour le redressement de la phase de codage. Il applique en fait les permutations circulaires inverse de celles utilisée lors du codage, illustrées par exemple par la figure 3. Il s'agit effectivement d'un redressement inverse de celui effectué lors du codage. Le redressement des blocs 64 se fait donc par le décodage de la partition et des informations de permutation fournies par le codeur, en particulier : - chaque bloc du macrobloc a sa propre information de permutation directement utilisable par le décodeur ; - en variante, l'information de permutation est décodée de manière 20 prédictive par rapport aux blocs voisins du bloc, grâce aux informations contenues dans l'en-tête du macrobloc ; L'information de permutation peut être décodée de manière contextuelle. Le décodage utilise par exemple le CABAC inverse dans le cas de la norme H.264. 25 La figure 8 illustre la chaîne de codage et de décodage mise en oeuvre par l'invention, et récapitule les composants impliqués. Le codeur vidéo 10 reçoit une séquence d'images 1 numérisées. Il comporte au moins un processeur 81 pour effectuer notamment la réorganisation des pixels à l'intérieur des 30 blocs, puis les étapes de transformation, de quantification et de codage entropique. Il comporte par ailleurs une mémoire 82 pour conserver des données intermédiaires, par exemple les résultats des tests de permutation pendant la phase de réorganisation des pixels à l'intérieur des blocs. La mémoire conserve par ailleurs des images reconstruites. Le codeur 10 35 délivre un signal 83 correspondant à un flux de données. Ce signal véhicule les images codées, c'est-à-dire compressées, avec notamment les informations de permutations appliquées aux blocs d'origine, ces informations étant nécessaires au décodage. Lorsqu'une image est découpée en blocs, le signal 83 comporte par exemple une en-tête pour chaque macrobloc, cette en-tête comportant les informations des blocs composant le macrobloc. Un décodeur 84 reçoit ce signal 83. Le décodeur a par exemple une structure matérielle analogue au codeur, comportant au moins un processeur 85 et un espace mémoire 86. Le décodeur applique la phase de décodage décrite précédemment. La figure 9 illustre une variante de mise en oeuvre du procédé selon l'invention. Dans cette variante, la détermination des permutations des blocs est accélérée. Dans la mise en oeuvre du procédé selon l'invention telle que décrite précédemment, la détermination de la permutation des blocs par comparaison est réalisée de façon systématique. La variante de la figure 7 permet d'éviter cet aspect systématique et de sélectionner les blocs sur lesquels la détermination de la permutation est réalisée. Cela permet un gain de temps et donc une accélération du processus. Dans une première phase, on calcule l'orientation des blocs. Pour calculer une orientation d'un macrobloc ou d'un bloc, on utilise par exemple un simple calcul de gradient. Les gradients horizontaux et verticaux VId du bloc sont calculés selon les relations suivantes : b Dlab = ad =L(Ib(i+1,i)ùIb(i,i) si d = x (2) aI b VI , = ad = L1,; (I b (i, J + 1) ù lb (i, J) où d est la direction du gradient calculé, selon l'horizontale x ou la verticale y, 30 Ib est le bloc b de l'image I et Ib(i, j) est le pixel (i, j) du bloc b. La connaissance des gradients horizontaux et verticaux permet alors de calculer la norme pl et la direction d( /Ib) du vecteur gradient selon les relations suivantes : si d = y (3) 22 Pb = .\1 vib z + vlb z (4) d (âI b) = arctan (5) Puis, si l'amplitude de ce vecteur gradient est supérieure à un certain seuil S, l'orientation du bloc est évaluée comme étant la direction du vecteur gradient. Ce seuil S permet de s'affranchir du traitement des blocs non orientés ainsi que des blocs n'ayant pas de contours réels. Ce seuil S permet donc dans une deuxième phase 72 de sélectionner les blocs dont les orientations sont supérieures à ce seuil, la détermination des permutations étant par la suite faite sur ces blocs. Les orientations calculées sont des grandeurs continues. Il est possible de les quantifier et d'en réduire le nombre, égal par exemple aux orientations définies précédemment, soit sept états pour les blocs 4x4 et quinze états pour les blocs 8x8 et trente et un états pour les blocs 16x16. Chacun de ces états correspond à un intervalle d'angles calculé directement dans un bloc et est donc dépendant de la taille de ce bloc. Dans le cas 4x4, il y a trois états pour les angles positifs, trois états pour les angles opposés et un état pour les blocs non orientés. Dans le cas 8x8, il y a sept états pour les angles positifs, sept états pour les angles opposés et un état pour les blocs non orientés. Dans le cas 16x6, il y a quinze états pour les angles positifs, quinze états pour les angles opposés et un état pour les blocs non orientés. Ainsi, on calcule pour chaque bloc Bj de chaque macrobloc le gradient selon les directions horizontale et verticale. On en déduit une orientation pour ce bloc Bj. Si l'orientation calculée est valide, c'est-à-dire si elle est dans un certain intervalle approprié : - une permutation est associée à l'orientation ; - la permutation est appliquée au bloc Bj. Pour accélérer 73 le processus systématique décrit relativement à la figure 4, il est possible de conditionner les étapes de ce processus à ce calcul de l'orientation. Au lieu de tester toutes les orientations pour un bloc donné, par exemple 4x4, on teste les N orientations principales les plus proches. On calcule par exemple toutes les orientations sur tous les blocs composant toutes les partitions d'un macrobloc, 16x16, 8x8 ou 4x4. Si les orientations des blocs 4x4, 8x8 sont cohérentes entre elles, c'est-à-dire qu'elles sont comprises dans des mêmes intervalles d'angles ou des intervalles proches, alors on effectue le redressement directement sur le regroupement dans un macrobloc 16x16. L'invention a été décrite pour un codeur vidéo qui reprendrait une évolution de la norme H.264. Elle s'applique bien sûr pour d'autres codeurs vidéo opérant sur des macroblocs et des blocs et effectuant une transformation sur ces derniers. L'invention a par ailleurs été décrite pour le codage et le décodage d'une séquence d'images vidéo. Elle s'applique pour le codage et le décodage d'une simple image numérisée.15 REVENDICATIONS 1. Procédé de codage d'une image numérisée (1) utilisant une transformation par blocs de pixels, caractérisé en ce que des permutations de pixels (39, Oi) étant définies (22) pour des tailles de blocs Bj : - un redressement (23) de l'orientation des blocs Bj est effectué selon chaque permutation définie ; - un codage (24) de chacun de ces blocs Bj redressés est simulé pour calculer le débit du flux de données après codage et la distorsion de l'image reconstruite ; une permutation étant sélectionnée (44, 45, 46) pour chaque bloc selon un 10 critère donné fonction du débit et de la distorsion, la transformation étant appliquée aux blocs redressés selon leur permutation sélectionnée. 2. Procédé de codage selon la revendication 1, caractérisé en ce que les blocs étant regroupés à l'intérieur de macroblocs (MBk) pour former une 15 partition, pour chaque macrobloc (MBk) des permutations de pixels (39, Oi) sont définies pour des tailles de blocs différentes à l'intérieur d'un macrobloc, le débit du flux de données relatif au macrobloc après codage du macrobloc étant calculé à partir des débits de chacun des blocs et la distorsion de l'image reconstruite induite par le codage du macrobloc étant calculée, une 20 partition étant sélectionnée en fonction d'un critère donné fonction du débit et de la distorsion. 3. Procédé de codage selon l'une quelconque des revendications précédentes, caractérisé en ce que le critère appartient à la liste suivante : 25 - le minimum de distorsion pour un débit donné ; - le minimum de débit pour une distorsion donnée. 4. Procédé de codage selon l'une quelconque des revendications précédentes, caractérisé en ce que les permutations (Oi) sont définies pour 30 toutes les tailles possibles de blocs Bj, un redressement étant effectué pour chacun de ces blocs. 5. Procédé de codage selon l'une quelconque des revendications précédentes, caractérisé en ce que l'image appartient à une séquence d'images vidéo. 6. Procédé de codage selon la revendication 5, caractérisé en ce que les permutations (Oi) sont définies pour tous les modes de prédictions, spatiales intra ou temporelles inter. 7. Procédé de codage selon l'une quelconque des revendications 2 à 6, caractérisé en ce que les orientations des blocs composant une partition sont calculées préalablement (71), les blocs Bj ayant une orientation comprise dans un même intervalle d'angles étant soumis à un même redressement, le codage simulé pour calculer le débit et la distorsion étant effectué pour au moins un de ces blocs. 8. Procédé de codage selon l'une quelconque des revendications 2 à 7, caractérisé en ce qu'après codage d'un macroblocs (MBk), son en-tête comporte les informations de permutation des blocs Bj le composant. 9. Procédé de décodage d'une image numérisée utilisant une transformation par blocs de pixels, comportant une phase de réception des informations de codage des blocs (61) et de décodage de ces blocs (62) à partir desdites informations, caractérisé en ce qu'il comporte en outre une phase de réception (63) et de décodage (64) des informations de permutation des blocs et une phase de redressement des blocs selon les permutations inverses (64). 10. Procédé de décodage selon la revendication 9, caractérisé en ce que chaque bloc a sa propre information de permutation. 11. Procédé de décodage selon la revendication 9, caractérisé en ce qu'une image étant découpée en macroblocs de pixels (MBk) codés chacun avec un en-tête, l'en-tête d'un macrobloc est décodée avec les informations de permutation des blocs Bj composant le macrobloc. 35 12. Procédé de décodage selon la revendication 11, caractérisé en ce que l'en-tête comporte une seule information de permutation pour tous les blocs du macrobloc. 13. Procédé de décodage selon l'une quelconque des revendications 9 à 12, caractérisé en ce que l'information de permutation est décodée de manière prédictive. 14. Dispositif de codage pour la mise en oeuvre du procédé selon l'une ~o quelconque des revendications 1 à 8, comportant des moyens d'application d'une transformation par blocs de pixels (81), caractérisé en ce qu'il comporte des moyens de réorganisation des pixels (81) : - pour définir des permutations de pixels (Oi) pour des tailles de blocs Bj 15 - pour effectuer un redressement de l'orientation des blocs Bj selon chaque permutation définie ; - pour simuler un codage de chacun de ces blocs Bj redressés pour calculer le débit du flux de données après codage et la distorsion de l'image reconstruite après codage et décodage ; 20 -pour sélectionner des permutations ; une permutation étant sélectionnée pour chaque bloc selon un critère donné fonction du débit et de la distorsion, la transformation étant appliquée aux blocs redressés selon leur permutation sélectionnée. 25 15. Dispositif de décodage pour la mise en oeuvre du procédé selon l'une quelconque des revendications 9 à 13, comportant des moyens de réception des informations de codage des blocs et des moyens de décodage de ces blocs à partir desdites informations (85), caractérisé en ce qu'il comporte en outre des moyens de réception et de décodage des informations de 30 permutation des blocs et des moyens de redressement des blocs selon les permutations inverses (85). 16. Produit programme d'ordinateur comprenant des instructions de programme pour l'exécution du procédé de codage selon l'une au moins des 35 revendications 1 à 8. 17. Produit programme d'ordinateur comprenant des instructions de programme pour l'exécution du procédé de décodage selon l'une au moins des revendications 9 à 13. 18. Signal comprenant une image numérisée codée par utilisation d'une transformation par blocs, caractérisé en ce qu'il comporte une information de permutation des blocs, une information de permutation étant utilisée pour effectuer le redressement d'un bloc selon la permutation inverse après décodage du bloc. 19. Signal selon la revendication 18, caractérisé en ce qu'une image étant découpée en macroblocs de pixels MBk, il comporte un l'en- tête pour chaque macrobloc comportant les informations de permutation des blocs Bj composant le macrobloc.20