Brevet FR3050598A1 — publié le 20171027

Procédé de décodage d'une image numérique, procédé de codage, dispositifs, et programmes d'ordinateurs associés 1. Domaine de l'invention Le domaine de l'invention est celui de la compression de signal, en particulier d'une image numérique ou d'une séquence d'images numériques, divisée en blocs de pixels. L'invention concerne plus particulièrement la transformation d'un bloc de pixels, issu ou non d'une prédiction. Elle trouve notamment son application dans un contexte de compétition de transformées. Le codage/décodage d'images numériques s'applique notamment à des images issues d'au moins une séquence vidéo comprenant : - des images issues d'une même caméra et se succédant temporellement (codage/décodage de type 2D), - des images issues de différentes caméras orientées selon des vues différentes (codage/décodage de type 3D), - des composantes de texture et de profondeur correspondantes (codage/décodage de type 3D), - etc. La présente invention s'applique de manière similaire au codage/décodage d'images de type 2D ou 3D. L'invention peut notamment, mais non exclusivement, s'appliquer au codage vidéo mis en oeuvre dans les codeurs vidéo actuels AVC (pour « Advanced Video Coding », en anglais) et HEVC (pour « High Efficiency Video Coding », en anglais) et leurs extensions (MVC, 3D-AVC, MV-HEVC, 3D-HEVC, post-HEVC, etc), et au décodage correspondant. 2. Présentation de l'art antérieur On considère un schéma de compression classique d'une image numérique, selon lequel l'image est divisée en blocs de pixels. Un bloc courant à coder, qui constitue une unité de codage initiale, est généralement découpé en un nombre variable de sous-blocs selon un mode de découpage prédéterminé. En relation avec la Figure 1, on considère une séquence d'images numériques Ii, 12, 4, avec J entier non nul. Une image I; est découpée en unités de codage initiales ou CTU (pour « Coding Tree Unit » en anglais) selon la terminologie de la norme HEVC, telle que spécifiée dans le document "ISO/IEC 23008-2:2013 - High efficiency coding and media delivery in 3050598 2 heterogeneous environments -- Part 2: High efficiency video coding », International Organization for Standardization, publié en novembre 2013. Les codeurs standards proposent généralement un partitionnement régulier, qui s'appuie sur des blocs carrés ou rectangulaires, appelés CU (pour « Coding Units », en anglais) de taille fixe. Le partitionnement se fait toujours à partir de l'unité de 5 codage initiale, non partitionnée, et le partitionnement final est calculé puis signalé à partir de cette base neutre. Chaque CU subit une opération d'encodage ou de décodage consistant en une suite d'opérations, comprenant de manière non exhaustive une prédiction, un calcul de résidu, une transformation, une quantification et un codage entropique. Cette suite d'opérations est connue de 10 l'art antérieur et présentée en relation avec la Figure 2. Au cours d'une étape E0, on sélectionne comme bloc courant c le premier bloc CTU à traiter. Par exemple, il s'agit du premier bloc (dans l'ordre lexicographique). Ce bloc est par exemple de taille 64x64 selon la norme HEVC. On suppose qu'il existe D partitionnements en blocs CU possibles numérotées de 1 à D, 15 avec D entier non nul et que le partitionnement utilisé sur le bloc c correspond au partitionnement numéro d. Par exemple, il peut y avoir 4 tailles de partitionnement carré possibles, en sous-blocs de taille 4x4, 8x8, 16x16, et 32x32 selon un mode de découpage régulier de type « quad tree » comme spécifié dans la norme HEVC. Un partitionnement en sous-blocs rectangulaires est aussi possible. 20 Dans la suite, on désigne par bloc courant un sous-bloc P issu du partitionnement du bloc CTU c. Les étapes qui vont être décrites sont répétées pour les autres sous-blocs. Au cours d'une étape El, on détermine une prédiction Pr du bloc CU P. Il s'agit d'un bloc de prédiction construit par des moyens connus, typiquement par compensation de mouvement (bloc issu d'une image de référence précédemment décodée), ou par prédiction intra (bloc construit à partir des pixels 25 décodés appartenant à l'image ID). Les informations de prédiction liées à Pr sont codées dans le train binaire TB ou fichier compressé FC. On suppose ici qu'il y a P modes de prédiction possibles ml, m2,..., mp, avec P entier non nul. Par exemple, le mode de prédiction choisi pour le bloc courant x est le mode mp. Certains modes de prédiction sont associés à une prédiction de type Intra, d'autres à une prédiction de type INTER. 30 Au cours d'une étape E2, un résidu original R est formé, par soustraction R = P-Pr de la prédiction Pr du bloc courant P au bloc courant P. 3050598 3 En E3, on identifie une transformée T à appliquer au résidu R ou à un sous-bloc issu d'une subdivision de R. L'étape de transformation joue un rôle crucial dans un tel schéma de codage vidéo : en effet, c'est elle qui concentre l'information avant l'opération de quantification. Il en résulte qu'un 5 ensemble de pixels avant encodage se voit représenté sur un faible nombre de coefficients fréquentiels non-nuls représentant la même information. Ainsi, au lieu de transmettre un grand nombre de coefficients, seul un petit nombre sera nécessaire pour reconstituer avec fidélité un bloc de pixels. Cette étape de transformation est complexe à implémenter aussi bien côté codeur que côté 10 décodeur, lequel doit mettre en oeuvre la transformation inverse de celle appliquée par l'encodeur. Au cours d'une étape E4, le résidu R est transformé en un bloc résidu transformé, appelé RT, par la transformée identifiée. De façon alternative, en l'absence de prédiction, on obtient un bloc transformé RT à partir du bloc c. Il s'agit par exemple d'une transformée de type bloc ou d'une transformée en ondelettes, toutes connues de l'homme de métier et notamment mises en oeuvre 15 dans les normes JPEG/MPEG pour la DCT/DST et JPEG2000 pour la transformée en ondelettes. En codage d'image et vidéo, on utilise généralement des transformées blocs (4x4, 8x8 etc), orthogonales ou quasi-orthogonales. Les transformées les plus employées sont à base de bases cosinus ou sinus. On les désigne généralement par DTT (pour « Discrete Trigonometric Transforms », en anglais). La DCT est ainsi présente dans la plupart des standards pour l'image et 20 la vidéo. Récemment la norme HEVC a également introduit la DST (pour « Discrete Sine Transform », en anglais) pour le codage de résidus particuliers dans le cas de blocs de taille 4x4. Dans les faits, ce sont des approximations de ces transformées qui sont employées, les calculs étant effectués sur des entiers. En général, les bases de transformées sont approximées à l'entier le plus proche, après multiplication par un facteur qui conditionne la précision donnée à 25 l'approximation (ce facteur est souvent en puissance de 2 généralement de 8 ou 10 bits). A titre d'exemple on présente en relation avec les Figures 2A et 2B, les transformées utilisées par la norme HEVC sur les blocs de taille 4x4 : Il s'agit des transformées DCT et DST. Les valeurs présentées dans ce tableau sont à diviser par 128 pour retrouver les transformations quasiorthonormales. 30 En E5, de façon connue dans l'état de l'art, ces coefficients sont parcourus dans un ordre prédéterminé de façon à constituer un vecteur monodimensionnel RQ[j], où l'indice j varie de 0 à 3050598 4 Nb-1, avec Nb entier égal au nombre de pixels du bloc x. L'indice j est appelé fréquence du coefficient RQ[j]. Classiquement, on scanne ces coefficients par ordre globalement croissant ou décroissant de valeurs de fréquence, par exemple selon un parcours prédéterminé, par exemple diagonal ou horizontal. 5 En E6, le bloc transformé RT est quantifié par des moyens classiques de quantification, par exemple scalaire ou vectorielle, en un bloc quantifié RQ comprenant autant de coefficients Nb que le bloc RT. Lors d'une étape E7, on vient coder les informations relatives aux coefficients du bloc RQ par codage entropique, par exemple selon une technique de codage de Huffman ou de codage 10 arithmétique. Ces informations comprennent au moins l'amplitude des coefficients et leur signe. Par amplitude, on entend ici la valeur absolue du coefficient. Classiquement, on peut coder pour chaque coefficient une information représentative du fait que le coefficient est non nul. Ensuite, pour chaque coefficient non nul, une ou plusieurs informations relatives à l'amplitude sont codées. On obtient les amplitudes codées CA. On code aussi les signes des coefficients non nuls. En 15 général, ils sont simplement codés par un bit 0 ou 1, chaque valeur correspondant à une polarité donnée. Un tel codage obtient des performances efficaces, car, du fait de la transformation, les valeurs des amplitudes à coder sont en grande majorité nulles. Concernant la transformée appliquée, dans le cas de la norme HEVC, on indique au décodeur par un bit, appelé « transfornn skip flag », la transformée inverse à appliquer parmi les 20 deux alternatives DST ou absence de transformée. Ce cas se présente dans le cas de blocs de taille 4x4. En E8, les données codées relatives au bloc courant x sont insérées dans le train binaire TB. Les autres sous-blocs qui constituent le bloc R de l'image I1 sont traités de la même façon, 25 puis les autres blocs CTU de l'image Il, ainsi que les blocs des images suivantes de la séquence. 2. Présentation de l'art antérieur L'étape de transformation d'un bloc courant en un bloc transformé engendre des calculs complexes, que l'homme du métier a tenté de simplifier et/ou d'accélérer. 30 Cette complexité augmente avec la taille des blocs traités. Dans HEVC, les transformées peuvent atteindre une taille de 32x32. 3050598 5 On connait notamment du document de Markus Püschel intitulé Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs, publié dans la revue IEEE transactions on Signal Processing, en avril 2008, une méthode d'implémentation rapide des familles de transformations DCT ou DST. Cette méthode concerne en particulier des transformées 5 trigonométriques DCT et DST de types I à VIII et il est montré que des algorithmes rapides pour des tailles très particulières (typiquement en puissance de 2 ou proche d'une puissance de deux) peuvent être mis en oeuvre. 3. Inconvénients de l'art antérieur Un inconvénient de ces types transformations DCT ou DST est que toutes ne sont pas applicables à 10 toutes les tailles de blocs, notamment parmi celles spécifiées dans la norme HEVC. Par exemple, la DST telle que spécifiée dans HEVC est limitée aux tailles de bloc 4x4, car elle induit une complexité importante pour les tailles supérieures. Un autre inconvénient est que certaines transformées n'ont pas d'algorithmes rapides. 4. Objectifs de l'invention 15 L'invention vient améliorer la situation. L'invention a notamment pour objectif de pallier ces inconvénients de l'art antérieur. Plus précisément, un objectif de l'invention est de proposer une solution qui permette de réduire la complexité des calculs mis en oeuvre lors de l'application d'une transformée à un bloc de pixels, au codeur comme au décodeur. 20 - Un autre objectif de l'invention est de proposer un gain en complexité qui n'ait pas d'impact sur l'efficacité en compression. 5. Exposé de l'invention Ces objectifs, ainsi que d'autres qui apparaîtront par la suite, sont atteints à l'aide d'un procédé de décodage d'une image numérique, à partir d'un train binaire comprenant des données codées 25 représentatives de ladite image, ladite image étant divisée en une pluralité de blocs traités dans un ordre défini, ledit procédé comprenant les étapes suivantes, mises en oeuvre pour un bloc, dit bloc courant transformé: - Décodage des coefficients du bloc courant à partir de données codées lues dans le train binaire ; 3050598 6 - Transformation du bloc courant en un bloc décodé, ladite étape mettant en oeuvre une première sous-étape destinée à produire un bloc intermédiaire, s'appliquant aux vecteurs colonnes respectivement lignes du bloc courant, la deuxième destinée à produire un bloc de pixels s'appliquant aux vecteurs lignes respectivement colonnes du bloc intermédiaire, issu 5 de la première sous-étape ; et - Reconstruction de l'image à partir du bloc décodé transformé. Un tel procédé est particulier en ce qu'au moins une desdites première et deuxième sous-étapes de transformation, comprend, pour un vecteur ligne respectivement colonne, dit vecteur d'entrée : - la formation d'au moins un premier sous-vecteur de taille K REVENDICATIONS1. Procédé de décodage d'au moins une image numérique (Ij), à partir d'un train binaire (TB) comprenant des données codées représentatives de ladite image, ladite image (Ij) étant divisée en une pluralité de blocs traités dans un ordre défini, ledit procédé comprenant les étapes suivantes, mises en oeuvre pour un bloc, dit bloc courant transformé (C') : Décodage (Dl, D3) des coefficients du bloc courant à partir de données codées lues dans le train binaire ; Transformation (D7) du bloc courant en un bloc décodé transformé, ledit bloc courant comprenant M vecteurs lignes et N vecteurs colonnes, avec M et N entiers non nuls, ladite étape mettant en oeuvre une première sous-étape destinée à produire un bloc intermédiaire, s'appliquant aux vecteurs colonnes respectivement lignes du bloc courant, la deuxième sous-étape destinée à produire un bloc de pixels s'appliquant aux vecteurs lignes respectivement colonnes du bloc intermédiaire, issu de la première sous-étape ; Reconstruction (D8) de l'image à partir du bloc décodé transformé ; caractérisé en ce que : au moins une desdites première et deuxième sous-étapes de transformation, comprend, pour un dit vecteur ligne respectivement colonne, dit vecteur d'entrée : la formation d'au moins un premier sous-vecteur de taille K 2. Procédé de décodage d'au moins une image numérique selon la revendication 1, caractérisé en ce que ladite au moins une sous étape de transformation comprend en outre la formation d'au moins un deuxième sous-vecteur de taille inférieure ou égale à N-K respectivement M-K à partir d'éléments adjacents du vecteur d'entrée, non compris dans le premier sous vecteur, telle que la somme des tailles des sous-vecteurs formées est égale à la taille du vecteur d'entrée, l'application d'une deuxième sous transformée partielle audit deuxième sous- vecteur et en ce que la composition du vecteur transformé comprend l'insertion des éléments du premier et du au moins un deuxième sous vecteur transformé aux positions initiales du premier et du au moins un deuxième sous-vecteurs formés dans le vecteur d'entrée. 3050598 28 3. Procédé de décodage d'au moins une image numérique selon la revendication 2, caractérisé en ce qu'une des au moins deux sous-transformées partielles est une transformée identité. 4. Procédé de décodage d'au moins une image numérique selon l'une des revendications 1 à 3, caractérisé en ce qu'au moins un des sous-vecteurs du vecteur d'entrée est de taille impaire. 5 5. Procédé de décodage d'au moins une image numérique selon l'une des revendications 2 à 4, comprenant une étape de sélection en fonction d'un critère débit-distorsion d'un couple de transformées parmi une pluralité de couples prédéterminés, caractérisé en ce qu'au moins une sous-transformée d'un dit couple se décompose en au moins la première et la deuxième sous transformées. 10 6. Dispositif (200) de décodage d'au moins une image numérique, à partir d'un train binaire (TB) comprenant des données codées représentatives de ladite image, ladite image (Ij) étant divisée en une pluralité de blocs traités dans un ordre défini, ledit dispositif comprenant les unités suivantes, aptes à être mises en oeuvre pour un bloc, dit bloc courant transformé (C') : 15 Décodeur (DEC) des coefficients du bloc courant transformé à partir de données codées lues dans le train binaire ; Transformateur (TRANS') du bloc courant en un bloc décodé, ledit bloc courant comprenant M vecteurs lignes et N vecteurs colonnes, avec M et N entiers non nuls, ledit transformateur étant apte à mettre en oeuvre une première sous-unité de transformation 20 apte à produire un bloc intermédiaire, s'appliquant aux vecteurs colonnes respectivement lignes du bloc courant, une deuxième sous-unité de transformation apte à produire un bloc de pixels s'appliquant aux vecteurs lignes respectivement colonnes du bloc intermédiaire, issu de la première sous-unité ; Reconstructeur (RCONST) de l'image à partir du bloc décodé ; 25 Caractérisé en ce que : au moins une desdites première et deuxième sous-unités de transformation, comprend, pour un dit vecteur ligne respectivement colonne, dit vecteur d'entrée : - la formation d'au moins un premier sous-vecteur de taille K 7. Procédé de codage d'au moins une image numérique, ladite image (Ii) étant divisée en une pluralité de blocs de pixels traités dans un ordre défini, ledit procédé comprenant les étapes 5 suivantes, mises en oeuvre pour un bloc courant (x), de dimensions prédéterminées : - Transformation (E4) du bloc courant en un bloc transformé, ledit bloc courant comprenant M vecteurs lignes et N vecteurs colonnes, avec M et N entiers non nuls, ladite étape comprenant une première sous-étape (E42) de transformation des M vecteurs lignes, respectivement colonnes, destinée à fournir un bloc intermédiaire formé à partir des 10 vecteurs lignes respectivement colonne, transformés et une deuxième sous-étape (E45) de transformation des M vecteurs colonne, respectivement lignes du bloc intermédiaire ; - Encodage du bloc transformé destiné à produire des données codées représentatives du bloc transformé ; - Insertion des données codées dans un train binaire représentatif de l'image codée ; 15 caractérisé en ce que au moins une desdites première et deuxième sous-étapes de transformation, comprend, pour un vecteur ligne respectivement colonne, dit vecteur d'entrée : - la formation d'au moins un premier sous-vecteur de taille K 8. 11. Programme d'ordinateur comprenant des instructions pour la mise en oeuvre du procédé de 5 décodage d'au moins une image numérique selon l'une des revendications 1 à 5, lorsqu'il est exécuté par un processeur. 12. Programme d'ordinateur comprenant des instructions pour la mise en oeuvre du procédé de codage d'au moins une image numérique selon la revendication 7, lorsqu'il est exécuté par un processeur. 10