Représentations parcimonieuses adaptées à la prédiction d’image 

Télécharger le fichier pdf d’un mémoire de fin d’études

Spécificités d’H264

Modes de codage

L’un des points clés des performances d’un encodeur H.264 réside dans la grande variété des modes de codage et en particulier, des modes de prédiction spatiale et temporelle. L’image est découpée en blocs de tailles variables. Le standard H.264 / AVC offre plusieurs partitionnements de l’image, à la fois pour le processus de décorrélation spatial et pour celui dédié à la prédiction temporelle.
En spatial, l’image est décomposée en trois tailles de blocs. Initialement, il y avait les macroblocs de 16 × 16 pixels composés de blocs 8 × 8. La nouveauté est de redécouper ces macroblocs en blocs de taille inférieure,i.e. en blocs de taille 4 × 4. En temporel, ou prédiction inter-images, la découpe des blocs est encore plus détaillée. Il existe bien sûr des blocs de taille 16 × 16 mais également des partitions autres, comme illustré sur les figures 1.10 et 1.11. Il existe des partitions 16 × 8, 8 × 16 et 8 × 8. Puis un bloc 8 × 8 peut être redécoupé et fournir les sous-partitions suivantes : 8 × 4, 4 × 8 et 4 × 4.
L’avantage d’une telle décomposition est de permettre des raitements à différentes échelles et ainsi de s’adapter au contenu local de l’image. Il est plus pertinent de considérer un bloc4 × 4 si le contenu de ce bloc correspond à un détail dans l’image. Tout traitement contraint à un bloc 16 × 16 pour représenter la finesse d’un contour, sera, très certainement, voué à l’échec.
Dans le cadre du mouvement, prenons l’exemple d’une personne se déplaçant sur un fond fixe. Si on se rapproche d’un détail, par exemple du bras, on aura uncontour vertical entre deux zones bien distinctes : le fond fixe et le bras en mouvement. La parti tion 8 × 16 par exemple, permettra ici d’acquérir deux vecteurs de mouvement distincts pour chacune des zones concernées. Si seule la partition 16 × 16 était disponible, l’erreur serait d’autant plus grande quele mouvement relatif entre les deux zones serait important. On comprend ainsi la grande adaptativité introduite par ces partitions multiples, notamment grâce au partitionnement 4×4. La figure 1.12 présente un exemple de partitionnement d’un macrobloc 16 × 16 en blocs 8 × 8 et 4 × 4.
Il faut néanmoins garder à l’esprit qu’à chaque sous-partit ion est associé un vecteur de mouvement doté de ses deux composantes (dx,dy), qui vont demander un coût de codage. On s’aperçoit déjà qu’il faudra trouver un compromis entre le d écoupage en sous-partitions et le surcoût de codage.

Images bi-prédites

Les images B sont prédites à partir d’images antérieures et/ou futures. Une nouveauté introduite par H.264 / AVC est d’autoriser les images B à être utilisées comme référence pour prédire d’autres images B. On les dénomme lesB-stored.
Dans la norme précédente, il était impossible de prédire uneimage B à partir d’une autre image B. Seul était autorisé l’usage des images I et/ou P pour fournir la prédiction. Cependant, dans les cas de mouvement rapide, il peut être plus pertinent de s’appuyer sur les images les plus proches temporellement dans la séquence. Voici présenté en figure 113. un exemple d’ordonnancement des images I, P et B. Les flèches indiquent les images utilisées comme référence suivant leur type et le positionnement dans la séquence.
Cette nouvelle flexibilité, i.e. pouvoir coder une image B à partir d’une autre image B, a permi s de mettre en place une structure dite «B-hiérarchique» offrant une amélioration de 10 à 15% des performances d’un encodeur H.264 / AVC, sans B-hiérarchique. Il s’agit d’une structuration dyadique des images I, P et B, créant alors une pyramide temporelle. On améliore ainsi la prédiction en favorisant une prédiction temporelle de proche en proche. De plus, le schéma en B-hiérarchique utilise un plus grand nombre d’images B que d’images P. Les images B sont moins coûteuses en débit car elles utilisent une prédiction bidirectionnelle qui conduit généralement à une meilleure prédiction que celle obtenue via une prédiction monodirectionnelle. Cela permet donc également d’améliorer les performances de l’algorithme de compression.

CABAC

Les principaux codeurs entropiques dans la norme H.264 / AVC sont le CAVLC (Context Adaptive Variable Length Coding) et le CABAC (Context Adaptive Binary Arithmetic Coding). L’usage de tables fixes des codes à longueur variable (VLC) ne permet pas de s’adapter aux valeurs statistiques des symboles traités au fur et à mesure du processus de codage. Il peut ainsi rester de la redondance entre les symboles qui ne pourra pas être exploitée. L’idée est donc de pouvoir s’adapter à un contexte, formé des valeurs des symboles précédemment codés, pour trouver le meilleur code du symbole courant. Le CAVLC offre ainsi la possibilité de s’adapter à l’environnement local des symboles précédemment codés.
Le CABAC, bien qu’il soit plus complexe que le CAVLC, est le processus de codage utilisé par défaut car il permet d’atteindre des performances supérieures, approximativement de 15%, par rapport au CAVLC. Le schéma 1.14 illustre les étapes clés duodeur,c que nous allons détailler par la suite.
Le premier aspect remarquable du CABAC est d’être basé sur uncodage arithmétique. Ceci lui permet donc de coder plusieurs symboles sur une valeur fractionnaire de bit3. Le CABAC tire son adaptabilité du fait que les probabilités, utilisées par lecodeur arithmétique et issues du choix d’un modèle de contexte, sont mises à jour à chaque étape, à chaque traitement d’un élément binaire, un bin. En effet, la première étape du CABAC consiste à binariser les symboles en bin avant tout traitement. Puis ensuite, le codage s’opère en boucle sur chacun des bins du symbole qui vient d’être binarisé.

Contrairement au codage de Huffman qui ne permettait pas de coder un symbole sur moins de un bit

La deuxième étape consiste à sélectionner dans une table le modèle de contexte qui correspond aux données traitées. Les modèles de contextes prédéfinis ont pour but d’exploiter au maximum les redondances résiduelles entre les observations. Il existe ainsi plusieurs modèles de contextes, chacun correspondant en une certaine position spatiale des données voisines, précédemment codées. La notion de modèles se réfère à un agencement particulier dans l’espace de ces données. Au sein d’un modèle de contexte, il existe plusieurs états. Pour un agencement spatial donné, on répertorie les combinaisons de valeurs des bits des coefficients voisins. Autrement dit, on regarde l’état binaire des coefficients voisins, par plans de bits. La notion de modèle de contexte allie deux aspects : à la fois, la disposition spatiale des données traitées (au même titre que sur une image, il est pertinent de regarder ce qui a été fait pour les blocs voisins) et l’état binaire de ces données (le bit de poids fort d’un coefficient de valeur 32 sera différent d’un coefficient qui vaut 9). Ces modèles correspondent finalement à des tables qui propos ent plusieurs états des bits des voisins. Pour chaque état du modèle de contextes, sont associées deux probabilités : la probabilité d’avoir un «1» et celle d’avoir un «0». Ce sont ces probabilités qui vont être rafraîchies au fur te à mesure. Il existe des modèles de contextes pour coder les vecteurs de mouvement, les indexs des images de référence utilisées ou encore pour coder le numéro du mode de prédiction spatiale choisi (cf section 1.6.3.1 pour la description de la prédiction intra-image).
L’étape suivante consiste à fournir au codeur arithmétiquele bin courant et les probabilités liées à l’état du modèle de contexte retenu. Puis, en fonctio de la valeur du bin courant, on met à jour la probabilité correspondante, pour cette instance. Si par exemple, le bin est un «1», la prochaine fois que la même instance sera sélectionnée, laprobabilité relative au «1» sera légèrement plus élevée.
Nous avons présenté ici le fonctionnement général du CABACSa. complexité réside dans le fait que l’on tient compte pour chaque bit des données binarisées, de l’état d’un contexte, formé des observations précédentes. La richesse de ce codeur est attachéer à la quantité de modèles de contextes. Tous ces modèles ont été définis de manière exhaustive mais on peut noter que certains ont été abandonnés car l’observation a montré qu’il était inutile de les conserver tous. Tous ces paramètres font du CABAC un outil puissant dans un schémade compression pour exploiter les corrélations résiduelles entre les données, qui n’auraient pas été exploitées par les précédents traitements de la chaîne de compression.

Autres améliorations

Jusqu’à l’apparition d’H.264 / AVC, la transformée ne s’opérait que sur des blocs de taille 8 × 8 ne permettant pas une décorrélation fine du signal. Il a donc té introduit une transformation fréquentielle sur des blocs de taille 4 × 4. L’exploitation des corrélations spatiales résiduelles à une résolution plus fine permet d’améliorer la représentation des détails. On peut remarquer que la transformation utilisée est définie de manière exacte (précision entière) afin d’éviter les erreurs d’arrondis.
Aux modifications présentées jusqu’à maintenant s’ajoutent encore quelques détails importants que nous présentons ci-dessous.
– La nouvelle norme permet de fournir jusqu’à seize vecteurs de mouvement par macrobloc. Jusqu’alors, seuls deux voire quatre vecteurs de mouvement étaient définis, ce qui limitait les performances de la prédiction temporelle.
– De même, le passage à une précision supérieure dans le calcu des vecteurs de mouvement a été une avancée majeure. Le principe de l’estimation de mouvement est de rechercher le meilleur prédicteur possible, au sein d’une image de référence. La recherche consiste à sélectionner un bloc de pixels, indépendamment d’une quelconque grille régulière. Afin d’améliorer la précision, sans se limiter à des valeurs entières pour les coordonnées retenues, on interpole l’image pour générer des positions ous-pixelliques. Dans la précédente norme, on ne pouvait interpoler que d’un facteurdeux, ce qui engendrait une précision au demi pixel pour les vecteurs. La norme H.264 / AVC autorise une recherche au quart de pixel améliorant ainsi considérablement la précision des vecteurs de mouvement.
– Une autre spécificité d’H.264 / AVC a été l’introduction de modes supplémentaires, nommés modes directs, dont le but est de déduire les vecteursde mouvement. Le principe consiste à éviter de les calculer en les estimant à partir des vecteurs définis pour les blocs voisins. Il existe deux modes directs : l’un spatial, l’autre temporel. En spatial, les vecteurs voisins correspondent à ceux retenus pour les blocs limitro phes au bloc courant. Le mode direct temporel utilise quant à lui, l’information du bloc d u colocalisé dans l’image de référence. Ces nouveaux modes sont appliqués pour les images B. Il existe également un mode direct spatial pour les images P, pour la prédiction inter 16 × 16. On gagne ainsi en débit puisque l’on évite d’avoir à coder l’information relative aux vecteurs de mouvement.
– La quantification a elle aussi été légèrement modifiée. On a augmenté le nombre de pas de quantification jusqu’à 52 niveaux afin d’améliorer la représentation du signal. Il a aussi été décidé de quantifier la chrominance de manière plus fine que la luminance afin d’améliorer le rendu visuel.

Prédiction d’images

Intra prédiction

La prédiction intra-image se déroule dans le domaine spatial et se base sur la connaissance d’un voisinage de l’image courante en cours de reconstruction. Les blocs de l’image sont reconstruits au fur et à mesure. Si bien qu’à un instant quelc onque du processus, un voisinage du bloc courant, dit causal, composé de trois, quatre ou cinq blocs, est disponible pourformer la prédiction . Cette proximité laisse tout naturellement supposer une forte corrélation entre le voisinage et le bloc à prédire, ce qui rend pertinent l’utilisation de l’information locale.
– Propagation des pixels voisins –
La prédiction intra est basée sur de simples propagations etcombinaisons linéaires de pixels. Afin de s’adapter au mieux à la texture locale, il est importan t de propager la texture selon un certain formalisme bien défini. Une texture peut présenter des caractéristiques très différentes, selon qu’il s’agisse d’une zone de l’image avec de faibles variations de niveaux de gris ou bien qu’il s’agisse d’une zone de variance élevée. Afin de répondre à cette problématique, plusieurs modes de prédiction existent.
– Prédiction de la composante continue (DC) –
Le mode DC est le mieux adapté pour modéliser les zones uniformes de l’image. Pour obtenir une prédiction DC, on calcule la moyenne des pixels limitrophes au bloc courant. L’estimation obtenue correspond à un bloc dont tous les pixels ont pour val eur la moyenne calculée. Le mode DC fournira une très bonne prédiction pour les zones de l’image où de larges plages de pixels ont, plus ou moins, les même valeurs. Ce signal n’en demeure pas moins une modélisation assez basique, non satisfaisante pour représenter des motifs plus complexes comme un contour ou une texture. Des modes directionnels furent donc créés pour synthétiser des signaux plus élaborés. Le principe est d’étendre la texture adjacente de manière judicieuse. Ces modes schématisent un sens de propagation des pixels voisins vers le bloc courant, le long d’une direction préalablement définie.
FIG. 1.15 – Présentation des 9 modes de prédiction intra4 × 4
– Modes de prédiction directionnels –
Le panel de modes disponibles varie en fonction de la taille de bloc. Pour les blocs de taille 4 × 4 et 8 × 8, il existe neuf modes de prédiction : le mode DC et huit modes directionnels. Parmi ces derniers, on peut citer les modes horizontal, vertical, diagonal gauche-bas, diagonal droite-bas. Les modes restants correspondent à des directions dont l’an gle est supérieur ou inférieur à 45°. La figure 1.15 répertorie l’ensemble des neuf modes de prédiction pour un bloc 4 × 4. Il est à noter que les même modes existent pour un bloc de taille8 × 8.
Nous pouvons remarquer dans l’exemple exposé à la figure 1.16 , que les neuf prédictions générées présentent des motifs sensiblement distincts. Laprédiction intra offre ainsi un assez large panel de prédicteurs potentiels. La génération de signal aviune simple méthode de recopie et de combinaisons linéaires, peut sembler être une approche naïve. Mais en dépit de leur simplicité apparente, ces quelques orientations suffisent à représent er la plupart des directions présentes dans une image.
Dans le cas des blocs de taille 16 ×16, quatre modes de prédictions ont été définis. On retrouve le mode DC pour synthétiser des textures uniformes, ainsi que deux modes directionnels : les modes vertical et horizontal. Le dernier mode se distingue des précédents par son caractère non directionnel. Il s’agit du mode plane. Comme son nom l’indique, la prédiction qu’il génère est un plan dont les deux vecteurs directeurs qui définissent son orientation, ont été calculés à l’aide des pixels voisins, horizontaux et verticaux. Si l’on se réfèreà la figure 1.17, on constate que le mode plane permet de générer un dégradé de niveaux de gris.

Travaux en prédiction intra

Le but de cette section est de donner un aperçu des différentes techniques mises en oeuvre dans la littérature pour améliorer l’efficacité de la prédiction intra-image. Les méthodes présentées visent pour la plupart à améliorer la prédiction sans induire de modifications qui nécessiteraient un changement de syntaxe de l’encodeur. On peut distinguer différents types d’approche en fonction de la voie choisie pour améliorer la prédiction. Certaines se basent sur la prédiction d’H.264 / AVC mais recherchent des techniques pour améliore la propagation des pixels. Il existe également de nombreuses recherches sur l’élaboration de nouveaux prédicteurs.
– Nouveaux agencements pour H.264 / AVC –
Des travaux [Wie03] ont proposé un partitionnement des blocs intra similaire à celui utilisé dans la prédiction inter (figures 1.10 et 1.11). Ils adaptent également la transformation afin qu’elle supporte les différentes tailles de bloc, nouvellement définies. La mise en place d’un tel schéma a pour vocation d’exploiter au mieux les corrélations et d’introduire une plus grande variété de choix, et donc d’adaptabilité, au niveau de la prédiction intra. Cette technique présente d’ailleurs des résultats très intéressants, aussi bien sur l’aspect intra-image que sur celui en inter. Dans [Wie03], l’impact d’une transformée adaptative en fonction des partitions, appliquée sur une prédiction inter, a aussi été évalué.
Dans le même esprit de complexification du partitionnement, [DEY+07] propose de découper le bloc suivant une géométrie particulière. Les auteurs déterminent un modèle paramétrique linéaire définissant la coupure optimale pour diviser le bloc en sous-partitions.
Les travaux [RAPP06] présentent une solution permettant de réduire notablement les corrélations résiduelles, observées au niveau du résidursquelo la prédiction intra de la norme n’a pas suffi pour récupérer tous les contours. La technique consiste à appliquer des permutations circulaires, émulant ainsi des rotations au sein du bloc prédit, pour réordonner les pixels, qui suivent initialement des directions privilégiées prédéfinies, le long d’horizontales ou de verticales. Dans la suite du processus de codage, la DCT, transformation appliquée en ligne puis en colonne au résidu, est alors plus performante.
– Recherche de nouveaux prédicteurs –
Le Template Matching [TBS06] est une technique proche des algorithmes de block matching utilisés en prédiction inter-images. Il s’agit cependant ed rechercher au sein de l’image courante, dans le voisinage causal, un bloc de pixels supposé représenter au mieux le bloc courant inconnu. Pour déterminer le meilleur prédicteur, on évalue une erreuentre les pixels voisins du bloc courant et des pixels au sein du passé causal, appartenant à une même ormef spatiale (Figure 1.18). Cette forme est appeléetemplate. Le meilleur prédicteur est celui qui conduit à l’erreur minimale entre les pixels des deux template. Dans la mesure où l’erreur est estimée entre des données deal même image, issues du passé causal, il n’est pas nécessaire de coder une information supplémentaire, comme cela est le cas dans le cadre d’une estimation de mouvement en inter où l’on code les vecteurs de mouvement.
Comme autre exemple, nous pouvons évoquer pertinence d’utiliser une approche sous-pixellique, temporelle, pour générer de nouveaux modes intra. les travaux de [PPJ07] qui prouvent la classiquement réservée à la prédiction
Par ailleurs, de nombreux travaux proposent des solutions qui enrichissent la prédiction intra de la norme H.264 / AVC. Certains [MTKY07] proposent d’ajouter des lignes de pixels supplémentaires à celles utilisées jusqu’à présent comme éférence. D’autres solutions présentent des résultats en augmentant le nombre de prédicteurs directionnels [TYTA07] ou encore en combinant plusieurs des directions mono-dimensionnelles prédéfinies pour former des prédicteurs bi-dimensionnels [YK08]. Dans ces travaux, ils adaptent également la transformée ainsi que l’ordre des parcours des coefficients lors du processus de co dage.

Inter prédiction

La prédiction inter-images cherche à exploiter les corrélations temporelles entre plusieurs images. On pourra ainsi rechercher, pour chacune des partitions inter présentées précédemment, dans des images I, P ou B, les pixels les plus proches du bloc courant (au sens d’une métrique définie, cf. partie 1.7) .
L’estimation / compensation de mouvement peut se faire sur des images présentes dans le passé par rapport à l’image courante, mais aussi sur des images dan s le futur. Lorsque la compensation de mouvement s’effectue vers l’avant, on parle de compensation forward. Ceci revient à rechercher les prédicteurs dans une image précédente. En revanche, sia lprédiction retenue provient d’une image dans le futur, la compensation de mouvement se fait vers l’arrière : c’est une compensation backward.
Dans la nouvelle norme H.264 / AVC, il est possible d’utiliser de multiples références pour obtenir la prédiction. Auparavant, dans le cadre de la prédiction monodirectionnelle, on utilisait une seule image de référence, qui avait, de plus, la contrainte de se situer dans le passé. A présent, pour prédire une image P, on peut rechercher le meilleur prédicteur dans plusieurs images de référence, positionnées à n’importe quel endroitde la séquence. La prédiction reste monodirectionnelle dans le sens où un seul macrobloc sera utilisé pour prédire les pixels, mais il aura été choisi parmi plusieurs images de référence. Pourles images B, l’idée est la même : le processus est toujours bidirectionnel car deux macroblocs sont utilisés mais il est autorisé de changer d’image de référence au cours de processus de prédiction de l’image courante, comme illustré sur la figure 1.20.
Ainsi deux macroblocs voisins ne seront pas nécessairement prédits à partir des mêmes images de référence. Les références sélectionnées n’ontalementég plus la contrainte de positionnement temporel fixé dans la séquence. Cette grande flexibilité permet notamment de résoudre efficacement les problèmes d’apparition, d’occlusion ou encore de fading6 .
6 Variation de luminosité des pixels. Par exemple, unfading linéaire correspond à un assombrissement progressif des images, généralement utilisé pour marquer la transition entre deux scènes d’une vidéo.
Lorsque la prédiction est bidirectionnelle, celle-ci correspond à la moyenne des deux prédictions retenues pixel à pixel. Notons qu’il existe également dans la norme H.264 / AVC, une prédiction pondéréeweighted( prediction) qui permet d’ajuster l’importance d’un macrobloc par rapport à un autre, de manière implicite ou explicite. En effet, on favorisera le bloc de prédiction temporellement le plus proche, par rapport à l’image couran te.
Nous pouvons remarquer que la prédiction pondérée est aussiapplicable de façon explicite dans le cas d’une prédiction mono-directionnelle (pour uneimage P ou B) ; cela permet de réajuster la luminance des pixels. Typiquement, lorsque apparaît un fl ash d’appareil photo sur une image, le phénomène est très court et a de forte chance de n’apparaître que sur cette image. On peut être amené à faire référence à ces pixels localisés au niveau du flash, sans toutefois vouloir reproduire cet effet. La prédiction pondérée permet de compenser cettevariation brutale de luminosité. Ces pixels de l’image de référence, ainsi compensés en luminosité, serviront ensuite comme prédicteurs pour un bloc de l’image courante.

Métriques de distorsion et critère d’optimisation des modes

Le processus de sélection des modes n’est pas normatif dans H.264 / AVC, ce qui signifie que l’on peut choisir n’importe quel algorithme de sélection. Pour un macrobloc donné appartenant à une image P ou B, on commence par déterminer les prédictionsntrai et inter images, correspondant à toutes les partitions possibles. Si l’image courante est u ne image I seule la prédiction intra-image sera activée. Par exemple, on peut décider de générer toutesles prédictions inter et intra, pour l’ensemble des partitions définies et ne choisir qu’ensuite le meilleur mode pour le macrobloc. Ou alors, on procède par étape en choisissant le meilleur mode pour une partition donnée et pour un type de prédiction (intra ou inter). Parmi ces meilleurs modes, on sélectionne le meilleur pour le macrobloc. Cette technique est donc nécessairement sousoptimale par rapport à la précédente qui met en concurrence tous les modes, en une seule fois. La fig ure 1.21 présente un exemple d’algorithme de sélection des modes.
La sélection des modes se fait en général par le biais de la mimisation d’une fonction de coût. Cette fonction peut être définie selon plusieurs critères prenant en compte plus ou moins de paramètres. Nous présentons dans cette section les critères basés uniquement sur une mesure de distorsion et ceux, plus complexes, basés sur une optimisation débit / distorsion.

Optimisation débit / distorsion

Pour affiner l’évaluation de deux images dans le cadre de la compression, il fut mis en place un processus cherchant le meilleur compromis entre la qualité de la reconstruction et le nombre de bits nécessaires pour coder puis transmettre l’information résiduelle. Il s’agit d’un problème d’optimisation connu sous le nom RDO pour Rate Distorsion Optimization.
Ce critère est basé sur une fonction de coût lagrangienneJλ que l’on cherche à minimiser : Jλ =D+λ.R
où D est une mesure de distorsion, R représente le débit en bits etλ un paramètre d’ajustement qui dépend des contraintes de quantification. La métrique de distorsion utilisée est en général la SSE ou la SAD.
Notons qu’il existe des décisions a priori et a posteriori. Dans le cadre de la décision a posteriori, la valeur exacte du débit R doit être connue, ce qui nécessite alors de passer par le processus complet de codage (transformation – quantificati on). La SSE quant à elle impose la reconstruction via les étapes de quantification et transformation inverses.
La technique est performante mais reste coûteuse car cela nécessite de répéter le processus pour chaque bloc et chaque mode à tester. L’alternative est l ‘utilisation d’une approche moins complexe mais néanmoins sous-optimale, qui consiste à évaluer a priori le coût qu’aurait le bloc en fin de processus. Pour estimer le débit R, on se base sur des modèles empiriques d’optimisation débit / distorsion, permettant d’approcher les performances des algorithmes a posteriori.

Codage scalable

Nous présentons dans cette section le concept global d’un codeur scalable et plus spécifiquement, la norme SVC, pour Scalable Video Coding. Un encodeur SVC repose sur les concepts connus d’H.264 / AVC mais inclut des traitements entre les images à différentes résolutions. Nous nous limiterons dans la section 1.8.1 à exposer la philosophie générale puis nous détaillerons dans la partie 1.8.2 un point particulier lié àla prédiction spatiale inter-couches de SVC, qui a fait l’objet d’une application dans cette thèse (au chapitre 4, section 4.4).

Principe général

La scalabilité est un terme désignant un système ayant la capacité d’évoluer en performances. Dans le cadre de la compression vidéo, la scalabilité désigne l’aptitude d’un algorithme de compression à représenter une vidéo hiérarchiquement, surplusieurs trains binaires. Parmi ceux-ci, une couche de base est indépendamment décodable des autres et permet la reconstruction des données à un niveau de qualité minimum. La prise en compte de ous-flux binaires de raffinement par le décodeur permet d’obtenir des incréments de qualité edreconstruction. Ces sous-flux peuvent être emboîtés dans un même train binaire ou diffuséssur des canaux distincts. Cette spécificité permet de s’adapter à la capacité des récepteurs, comme le schématise la figure 1.22. Dans SVC, il existe trois niveaux de scalabilité :
1. la scalabilité spatiale ou scalabilité en résolution, définit une hiérarchie de résolutions spatiales. La résolution désigne la taille en pixels des images reconstruites.
2. la scalabilité temporelleporte sur la fréquence de rafraîchissement des images : elledéfinit une hiérarchie de résolutions temporelles.
3. la scalabilité en fidélitéou scalabilité SNR (Signal to Noise Ratio) consiste à augmenter le rapport signal à bruit d’une couche donnée de la hiérarchie,c’est-à-dire réduire la distorsion de quantification entre images originales et reconstruites .
La figure 1.23 schématise les trois scalabilités rencontrées dans SVC. L’image en haut à gauche correspond à l’image, pleine résolution pour les trois scalabilités. L’image en haut à droite présente l’image avec un niveau de scalabilité spatiale, celle en basà gauche, pour un niveau en scalabilité SNR et celle en bas à droite, pour un niveau de scalabilité temporelle.
Une particularité de ce standard se base ainsi dans la possibilité d’exploiter les corrélations entre les images aux différentes résolutions. Une couche debase est définie comme point de départ, puis des couches d’amélioration de résolutions supérieuresont ajoutées en fonction des besoins.

Structure de prédiction pyramidale

Chaque couche est basée sur un encodage H.264 / AVC auquel se rajoute un processus de prédiction basé sur l’exploitation de données entre couches. Dans SVC, on distingue trois types de prédiction inter-couche : la prédiction spatiale, la prédiction des vecteurs de mouvement et la prédiction du résidu. Chacun de ces modes supplémentairesisev à utiliser les informations connues d’une couche de base, pour former de nouveaux prédicteurs. Nous ne présentons dans cette partie que la prédiction spatiale inter-couches.
La prédiction spatiale dite intra est constituée, comme nous venons de l’exposer en section 1.6.3.1, de neuf modes de prédiction qui exploitent la connaissance d’un voisinage causal de pixels connus, limitrophes au bloc courant. A ces neuf modes, s’ajoute un mode de prédiction inter-couches basé sur l’interpolation du bloc colocalisé dans une couche de base, comme l’illustre la figure 1.24. Cette couche n’étant pas à la même résolution, ilest nécessaire d’interpoler le bloc de la couche de base. Notons que la prédiction spatiale inter-couches n’est possible que dans les cas où le macrobloc dans lequel se situe le bloc colocalisé dans al couche de base, a été codé en mode intra.

Comment juger de la qualité de la synthèse ?

L’évaluation de la qualité d’une texture obtenue par synthèse est un problème majeur. La méthodologie générale en synthèse consiste à générer une ageim texturée à partir d’un petit échantillon connu du motif à reproduire. Les outils mathématiques classiques sont de fait inadaptés
à cette problématique. Ils ne mesurent en effet la qualité dela reconstruction qu’en calculant une erreur pixel à pixel. De plus, comme nous l’expliciteron s par la suite, les algorithmes de synthèse ne cherchent pas nécessairement à obtenir une copie conforme au signal d’origine. Seule une réalisation perceptuellement semblable suffit. Par conséquent, pour juger de la qualité de la synthèse, nous ne pouvons, a priori, nous fier qu’à notre seule perception visuelle, avec toute l a subjectivité que cela implique. C’est pourquoi des critères psychovisuels ont été introduits afin de répondre à cette problématique. Ils sont basés sur des modélisations avancées du système visuel humain qui visent à émuler les interprétations de notre cerveau face à des stimuli visuels [WS04].

Exemples de techniques de synthèse

On s’accorde en général pour distinguer deux grandes classe de texture : celles qui présentent des aspects réguliers aux motifs bien déterminés, de cellesdont l’agencement est plus aléatoire et donc dépourvues de structures établies. Nous retrouvonsainsi, de façon tout à fait logique, deux catégories d’algorithmes. On distingue ceux basés surune approche structurelle déterministe visant à restituer la régularité du motif, de ceux dont l’approche est probabiliste, cherchant à caractériser l’aspect anarchique des textures stochastiques.

Approche stochastique

La philosophie d’une approche stochastique n’est pas de reproduire la texture à l’identique.
On recherche plus exactement à créer une nouvelle texture comme si elle avait été générée par le même processus aléatoire.

L’image : une réalisation d’un champ de Markov

La technique basée sur les champs de Markov ou MRF (Markov Random Field) est l’une des plus anciennes du domaine [CJ83, PP93, HB95, PL95]. Le principe consiste à modéliser l’image comme un champ stationnaire, où les pixels sont des variables aléatoires. Les dépendances entre elles forment le signal texturé. L’enjeu est alors de sélectionner la réalisation ou encore l’agencement optimal des pixels, qui conduit à une restitut ion acceptable du motif source. Pour estimer quel sera l’ordonnancement le plus probable, il est nécessaire d’apprendre la distribution sur l’ensemble de l’image. L’approche a démontré son efficacité pour un ensemble assez vaste et divers de textures. On peut supposer que cette robustesse est liée à l’adaptativité intrinsèque de la technique qui dépend directement du signal source. Cependant, les algorithmes mis en place restent encore actuellement beaucoup trop coûteux.

Structure hiérarchique

Les travaux de [Bon95] introduisent une structure hiérarchique au coeur du processus de synthèse. Une hypothèse fondamentale de la technique consiste à supposer qu’une texture est composée de plusieurs régions, qui se distinguent les unes esd autres à une faible valeur près.
Autrement dit, certaines caractéristiques d’une texture peuvent être visibles à une résolution sans l’être à une autre. Partant de cette hypothèse, l’analyse est basée sur une décomposition de l’image à plusieurs échelles, visant à extraire jusqu’aux composan tes les plus basiques de l’image : on obtient une décomposition en sous-bandes de différentes fréquences spatiales, un exemple est représenté en figure 2.3.
Une solution proposée par Javier Portilla et Eero Simoncell [PS00] offre de bons résultats. Leur approche est basée sur l’exploitation des corrélations entre coefficients d’ondelettes aux différentes sous-bandes de la transformation. Le modèle atistique est paramétré en tenant compte de diverses valeurs statistiques dépendantes des corrélations entre coefficients, voisins en termes de localisation spatiale, d’orientation et d’échelle.

Approches structurelles

Méthodes supervisées basées pixel

Ces dernières années des méthodes très efficaces ont été développées, basées sur la recopie de pixels issus d’un patch modèle. La philosophie de ce type de méthode peut s’apparenter à une approche déterministe de la synthèse par des champs de Markov. La technique a d’abord été introduite par Alexei A. Efros et Thomas K. Leung [EL00]. Puis, les travaux de Li -Yi Wei et Marc Levoy [EL00] ont démocratisé ce type d’algorithmes. Ils génèrent la texture en recherchant des correspondances point à point, entre le voisinage de l’imag e en cours de synthèse et des voisinages du patch source, comme l’illustre la figure 2.4.
Par la suite, des travaux, notamment ceux de Michael Ashikhmin [Ash01], se sont orientés vers une extension de la technique de Wei et Levoy. L’exploitation de stationnarités locales dans sa méthode lui permet de réduire le nombre de candidats possibles. La figure 2.5 présente quelques uns de ses résultats. Puis, les travaux dans le domaine se sont tout naturellement axés vers des techniques visant de plus en plus à recopier des morceaux com plets du patch source. Citons les travaux de Vivek Kwatra et al. [KEBK05] qui mettent en place une approche d’optimisation plus globale basée sur un algorithme de type EM .

Méthodes basées bloc

– Chaos mosaic –
Cette idée originale a été développée par Ying-Quing Xu et. al[XGS00]. La technique proposée est basée sur un placement répété et aléatoire dutchpasource dans une nouvelle image. La technique faisant apparaître de nombreuses discontinuités entre blocs voisins, les contours sont ensuite filtrés pour éliminer ces artefacts. La figure 2.6 présente un exemple de résultats de synthèse par cette méthode. Par nature, cette technique ynthétise ainsi une texture d’aspect déstructuré tout en conservant néanmoins la nature localeudmotif. L’algorithme est donc efficace pour générer des textures stochastiques mais présente de iblesfa résultats quant à la synthèse de textures ordonnées.
– Synthèse par graphcut –
A. Efros et W.T. Freeman [EF01] ont cherché à combiner deux idées : celle du chaos mosaic qui recopie aléatoirement le patch source et celle qui introduit des contraintes spatiales au niveau pixellique [EL00]. L’idée consiste à recopier côte à côte le s patchs source dans une nouvelle image, tout en tolérant une zone de recouvrement entre eux. La texture ainsi synthétisée est ensuite uniformisée en déterminant la couture optimale au iveaun du recouvrement. La jointure optimale est calculée via des algorithmes de programmation dynamique. La figure 2.7 présente le principe de la méthode. Kwatra et al. [KSE+03] proposent d’obtenir cette couture en se basant sur la théorie des graphes plutôt que par la programme dynamique. Au niveau du recouvrement des patchs, on détermine le chemin de coût minimal puis la coupe minimale, qui en découle, va définir la séparation optimale entre les blocs.

Table des matières

Introduction
1 Introduction à la compression vidéo 
1.1 Représentation des couleurs
1.2 Perception visuelle
1.3 Effets visuels exploités en compression
1.3.1 Masquage entre composantes chromatiques
1.3.2 Notions de masquage et de facilitation
1.3.3 Sensibilité au contraste
1.3.4 Sensibilité statique à la fréquence spatiale
1.3.5 Variation de la sensibilité en fonction du mouvement entre images
1.4 Compression d’images fixes
1.4.1 Vers un compromis : la transformée en cosinus discrète
1.4.2 Quantification
1.4.2.1 Quantification scalaire uniforme
1.4.2.2 Quantification scalaire à zone morte
1.4.3 Codage
1.5 Compression d’images animées
1.5.1 Exploitation de la corrélation temporelle
1.5.2 Estimation et compensation de mouvement
1.5.3 Problématiques soulevées
1.6 Codage MPEG-4 AVC / H.264
1.6.1 Préambule
1.6.2 Spécificités d’H264
1.6.2.1 Modes de codage
1.6.2.2 Images bi-prédites
1.6.2.3 CABAC
1.6.2.4 Autres améliorations
1.6.3 Prédiction d’images
1.6.3.1 Intra prédiction
1.6.3.2 Travaux en prédiction intra
1.6.3.3 Inter prédiction
1.7 Métriques de distorsion et critère d’optimisation des modes
1.7.1 Mesures de distorsion
1.7.2 Optimisation débit / distorsion
1.8 Codage scalable
1.8.1 Principe général
1.8.2 Structure de prédiction pyramidale
1.9 Conclusion
2 Synthèse de texture 
2.1 Introduction
2.1.1 Qu’est-ce qu’une texture ?
2.1.2 Axes de recherche
2.1.3 Comment juger de la qualité de la synthèse ?
2.2 Exemples de techniques de synthèse
2.2.1 Approche stochastique
2.2.1.1 L’image : une réalisation d’un champ de Markov
2.2.1.2 Structure hiérarchique
2.2.2 Approches structurelles
2.2.2.1 Méthodes supervisées basées pixel
2.2.2.2 Méthodes basées bloc
2.2.2.3 Synthèse de texture inverse
2.2.3 Conclusion de la partie
2.3 L’inpainting d’images
2.3.1 Introduction
2.3.2 Synthèse de la géométrie
2.3.3 Synthèse combinée de la géométrie et de la texture
2.4 Étude harmonique
2.4.1 Seuillage itératif
2.4.2 Analyse en composantes morphologiques (MCA)
2.4.3 Apprentissage de dictionnaire
2.4.4 Algorithme EM et analyse harmonique
2.5 Conclusion
3 Représentations parcimonieuses : état de l’art 
3.1 Introduction à la parcimonie
3.2 Problème à résoudre
3.2.1 Problématique
3.2.2 Distinction de deux axes d’étude
3.3 Algorithmes de décomposition parcimonieuse
3.3.1 Approche sous-optimale
3.3.1.1 Matching Pursuit
3.3.1.2 Orthogonal matching pursuit
3.3.2 Approche globale
3.3.2.1 Basis Pursuit
3.3.2.2 Basis Pursuit Denoising
3.3.2.3 Algorithme du LARS
3.3.2.4 Le filtre adapté global
3.4 Dictionnaires
3.4.1 Des bases orthonormales aux dictionnaires redondants
3.4.1.1 Enrichir le dictionnaire
3.4.1.2 Danger de la redondance
3.4.1.3 Atomes corrélés au signal
3.4.1.4 Dictionnaires adaptatifs
3.4.2 Dictionnaires redondants
3.4.2.1 Atomes fréquentiels
3.4.2.2 Dictionnaires temps-fréquence
3.4.2.3 Dictionnaires temps-échelle
3.5 Conclusion
4 Représentations parcimonieuses adaptées à la prédiction d’image 
4.1 Introduction
4.2 Prédiction parcimonieuse
4.2.1 Principe
4.2.2 Motivations théoriques
4.2.3 Choix et optimisation du voisinage d’approximation
4.2.3.1 Fonction de pondération
4.2.3.2 Segmentation du voisinage
4.2.4 Critère d’arrêt
4.2.4.1 Erreur quadratique moyenne
4.2.4.2 Fonction de coût lagrangienne
4.2.5 Choix du dictionnaire
4.3 Application à la prédiction intra dans un codeur H.264 / AVC
4.3.1 Pourquoi vouloir améliorer la prédiction intra de la norme ?
4.3.2 Support de prédiction : le passé causal
4.3.3 Codage du nombre d’itérations
4.4 Application à la prédiction inter-couches dans SVC
4.4.1 Raffinement de la prédiction SVC
4.4.2 Mise en place de la prédiction
4.5 Résultats expérimentaux dans le cadre H.264 / AVC
4.5.1 Substitution à un mode de la norme H.264 / AVC
4.5.2 Analyse des performances
4.5.3 Analyse en terme débit / distorsion
4.5.4 Évaluation du coût de codage du nombre d’itérations
4.5.5 Résultats sur différentes images
4.5.6 Influence du codage entropique sur les résultats
4.5.7 Comparaison des algorithmes
4.5.8 Critère d’arrêt lagrangien
4.5.9 Optimisation du voisinage d’approximation
4.5.10 Application : raffinement de la prédiction inter – image
4.5.10.1 Débruitage de la prédiction inter
4.5.10.2 Dé-crossfading
4.6 Résultats expérimentaux dans le cadre SVC
4.7 Discussion sur le critère d’arrêt non-causal
4.8 Conclusion
5 Déconvolution spectrale pour la prédiction 
5.1 Approche spectrale
5.1.1 Modélisation du problème
5.1.2 Principe de la déconvolution
5.1.3 Descriptif de l’algorithme
5.2 Analogie avec les représentations parcimonieuses
5.2.1 Réécriture de l’algorithme du MP
5.2.2 Introduction des notations liées aux transformées de Fourier
5.2.3 Algorithme du MP dans le cas de la base de Fourier
5.2.4 Analogie
5.2.5 Discussion dans le cas bi-dimensionnel
5.3 Application à la prédiction
5.3.1 Adaptation du fenêtrage
5.3.2 Critère d’arrêt
5.3.3 Résultats dans un encodeur de type H.264 / AVC
5.4 Conclusion
6 Dictionnaires 
6.1 Adaptabilité des fonctions de base
6.1.1 Scan directionnel des observations
6.1.2 Réajustement de la phase spatiale des atomes
6.1.2.1 Introduction
6.1.2.2 Corrélation de phase appliquée aux atomes
6.1.2.3 Corrélation de phase sous-pixellique
6.1.2.4 Méthode de mise à jour des atomes du dictionnaire
6.2 Atomes spécifiques
6.2.1 Atomes spatiaux
6.2.1.1 Exploitation des données issues du Template Matching
6.2.1.2 Mise à jour du dictionnaire
6.2.2 Atomes directionnels
6.2.3 Atomes mono-dimensionnels
6.3 Conclusion
Glossaire 
Bibliographie 

Télécharger le rapport complet