Optimisation du filtrage temporel

Optimisation des vecteurs impliqués dans la prédiction

Les sous-bandes temporelles de détail constituent la majeure partie du flux binaire et une façon simple d’améliorer l’efficacité globale du codeur vidéo est de diminuer la complexité de ces images. On cherche ici à améliorer l’opérateur de prédiction mis en jeu dans la transformée temporelle 5/3 en optimisant les champs de vecteurs utilisés. La stratégie proposée dans cette section a conduit à la publication d’un article de conférence [105], repris dans un article de revue [106] plus général sur l’utilisation du schéma lifting compensé en mouvement en codage vidéo scalable. 

Présentation du problème

On rappelle la transformée temporelle 5/3 utilisée par le schéma de codage présenté dans la section 3.1.3 qui s’exprime sous la forme lifting suivante : h 0 t (n) = x2t+1(n) − 1 2 ¡ C(x2t , v + 2t+1)(n) + C(x2t+2, v − 2t+1)(n) ¢ (4.1) l 0 t (n) = x2t(n) + γ C −1 (ht−1, v − 2t−1 )(n) + δ C −1 (ht , v + 2t+1)(n) (4.2) ht(n) = 1/ √ 2 h 0 t (n) (4.3) lt(n) = √ 2 l 0 t (n) (4.4) avec    γ = δ = 1/4 si n est connecté des deux côtés γ = 1/2 et δ = 0 si n est connecté seulement à gauche γ = 0 et δ = 1/2 si n est connecté seulement à droite γ = 0 et δ = 0 si n n’est pas connecté Nous nous intéressons ici uniquement à l’optimisation de la prédiction dans le but de diminuer la complexité des images de détail ht . Pour simplifier les notations, nous omettons le coefficient de normalisation 1/ √ 2 dans nos raisonnements. En développant l’opérateur de compensation de mouvement C, on peut alors réécrire l’équation (4.1) et détailler les coefficients des sous-bandes de détail : ht(n) = x2t+1(n) − 1 2 ³ x2t ¡ n − v + 2t+1(n) ¢ + x2t+2¡ n − v − 2t+1(n) ¢ ´ (4.5) On considère ici le problème de l’estimation bidirectionnelle des champs de mouvement avant v + 2t+1 et arrière v − 2t+1 impliqués dans la prédiction, de manière à minimiser la distorsion des images de détail ht . Sous la réserve d’un choix judicieux d’une mesure de distorsion, on espère ainsi minimiser le coût de codage des images ht . Il est par exemple raisonnable de penser que le choix de la norme ℓ2 et donc la minimisation de l’énergie des images de détail ht conduise à une réduction de leur coût de codage. On notera que cette approche a été poursuivie ultérieurement par Cagnazzo [27] dans un cas plus simple. Compte tenu de la structure en blocs des champs de mouvement v + 2t+1 et v − 2t+1 due à la méthode choisie pour leur estimation, on choisit de minimiser la distorsion des images 79 de détail ht , bloc par bloc. En nous concentrant sur la minimisation d’un bloc B courant appartenant à l’image x2t+1, nous choisissons d’omettre l’indice spatial n pour alléger les notations et écrivons alors v + = v + 2t+1(n) et v − = v − 2t+1(n). La minimisation de la distorsion des images de détail ht revient ainsi à un problème de recherche d’optimum à deux paramètres. Elle peut se faire sous une contrainte de débit liée au coût des vecteurs λ ¡ R(v +) + R(v −) ¢ ou non (en prenant λ = 0), et conduit à la minimisation du critère J général suivant : J(v +, v −) = X n∈B d ¡ ht(n) ¢ + λR(v +) + λR(v −) (4.6) où B est un bloc de l’image courante x2t+1 à prédire, d une mesure de distorsion usuelle (erreur absolue ℓ1, norme quadratique ℓ2 , etc…) et R le coût de codage d’un vecteur. En minimisant la distorsion de tous les blocs des images de détail ht comme illustré sur la Fig. 4.1, on espère ainsi minimiser leur complexité et donc faciliter leur codage. ht v − x2t x2t+1 x2t+2 B v + FIG. 4.1 – Opérateur de prédiction mis en jeu dans la transformée 5/3 et minimisation de la distorsion du bloc B. Estimation indépendante de v + et v − Dans la transformée temporelle 5/3 proposée dans la section 3.1 du chapitre précédent, les champs de mouvement avant v + et arrière v − sont estimés de façon indépendante. Le champ de mouvement avant v + est ainsi calculé par la procédure d’appariement de blocs (block-matching) HVSBM, décrite en section 2.2.4, où chaque bloc de l’image courante x2t+1 est mis en correspondance avec un bloc de l’image de référence x2t , de façon à minimiser le coût D + λR où D est une mesure de distorsion usuelle : la SAD (Sum of Absolute Differences). Le champ de mouvement arrière v − est calculé de la même façon et indépendamment de v + mais en prenant x2t+2 comme image de référence. Les vecteurs mouvements v + et v − vérifient donc : v + = arg min v X n∈B h d ¡ x2t+1(n) − x2t(n − v(n))¢ i + λR(v) (4.7) v − = arg min v X n∈B h d ¡ x2t+1(n) − x2t+2(n − v(n))¢ i + λR(v) (4.8)  Pour la simple raison que les vecteurs v + et v − ont été estimés de manière indépendante, ils n’ont aucune raison à priori de minimiser le critère J précédemment défini et ne peuvent donc minimiser l’énergie du bloc B de l’image de détail ht . On souhaite ainsi estimer conjointement ce couple de vecteurs de façon à minimiser le critère J. Cependant, la minimisation directe de ce problème d’optimisation à deux paramètres est difficile et sa complexité quadratique est largement prohibitive. Nous proposons dans la section suivante une solution quasi-optimale, permettant de trouver un couple de vecteurs v + et v − constituant un minimum local de J .

Prédiction itérative bidirectionnelle jointe

La minimisation de J peut se faire par une suite de minimisations alternées du champ avant v + et du champ arrière v −, en prenant compte des champs précédemment estimés. Nous avons ainsi présenté un algorithme itératif [105], capable de minimiser J et convergeant vers un minimum local. Un des intérêts de cet algorithme réside dans le fait qu’il ne nécessite pas la construction d’un nouvel estimateur de mouvements et repose sur un opérateur d’appariement de blocs quelconque que nous notons BM. Pour un bloc B courant et une image de référence x donnée, BM est défini comme un opérateur capable de fournir un vecteur v=BM(B,x), pointant vers un bloc de l’image de référence et minimisant le coût D + λR associé au bloc B. Notre algorithme itératif de prédiction bidirectionnelle jointe permet de trouver les vecteurs v + et v − optimaux au sens de J et donc de minimiser le coût du bloc B. Il est dit itératif car il repose sur la construction d’une suite de couples de vecteurs {v + i , v − i }i∈N, conduisant à la convergence du critère {J(v + i , v − i )}i∈N vers un minimum local. L’algorithme s’énonce de la façon suivante : Initialisation Le vecteur avant v + 0 est obtenu par un appariement de blocs classique entre le bloc B de l’image courante x2t+1 et l’image de référence x2t . On a alors v + 0 = BM(B, x2t). Itération i, pour i ≥ 1 – Le vecteur arrière v − i est obtenu par une procédure d’appariement de blocs entre un bloc virtuel B ′ et l’image de référence x2t+2/2. Le bloc virtuel B ′ dépend du vecteur v + i−1 précédent et est défini par B ′ (n) = x2t+1(n) − x2t ¡ n − v + i−1 (n) ¢ /2. Cette technique revient à faire une sorte d’appariement de blocs semi-compensé en mouvement. On a alors v − i = BM(B ′ , x2t+2/2). – De façon similaire, le vecteur avant v + i est obtenu par appariement de blocs entre entre le bloc virtuel B ′′ semi-compensé en mouvement défini par B ′′(n) = x2t+1(n)− x2t+2¡ n − v − i (n) ¢ /2 et l’image x2t/2. On a alors v + i = BM(B ′′, x2t/2). L’initialisation de l’algorithme revient ainsi à estimer d’abord le vecteur avant v + 0 par un appariement de blocs classique. Lors de la première itération, le vecteur arrière v − 1 est alors estimé grâce à la connaissance de v + 0 . Ensuite, et à chaque itération, les vecteurs avant v + i et arrière v − i sont réestimés et permettent la convergence rapide du critère J vers un minimum local. On minimise ainsi le coût du bloc B au sens du critère J. 81 Chaque itération possède une complexité équivalente à deux recherches de blocs, sans compter l’initialisation. La complexité globale de l’algorithme avec n itérations est donc équivalente à 2n + 1 procédures de recherche de blocs. Cependant, la complexité globale peut être réduite en diminuant à chaque itération le domaine de recherche des blocs. Ceci est justifié par le fait qu’il est probable que la direction du vecteur v + i soit proche de celle de v + i−1 et que l’on peut ainsi réestimer v + i sur un domaine réduit. Comme dit précédemment, cet algorithme ne repose que sur l’utilisation d’une procédure d’appariement de blocs générique BM, rendant son implémentation grandement simplifiée. On remarquera enfin qu’il est possible de stopper l’algorithme au cours d’une itération, en s’arrêtant après l’estimation du vecteur arrière v − i ; on parlera alors de demi-itération.

Prédiction bidirectionnelle à vecteur de mouvement unique

La transformée temporelle de Haar est mono-directionnelle mais ne nécessite le codage que d’un seul champ de mouvement. Au contraire, la transformée 5/3 est bidirectionnelle et utilise deux champs de mouvement, lui permettant ainsi d’effectuer une prédiction temporelle de meilleure qualité. Cependant, cet avantage a un coût car il nécessite le codage d’un champ de mouvement supplémentaire. Nous avons pu ainsi observer dans la section 3.2 du chapitre précédent qu’à bas débit, la transformée de Haar possède une efficacité de codage supérieure à la transformée 5/3, pénalisée par le surcoût de codage engendré par son deuxième champ de mouvement. Nous souhaitons construire une transformée temporelle capable de concilier une prédiction bidirectionnelle tout en n’utilisant qu’un seul champ de mouvement. En faisant l’hypothèse d’un mouvement apparent souple et uniforme entre trois images consécutives, il est possible de construire une telle transformée en se basant sur le filtre temporel 5/3. L’idée réside dans l’utilisation d’un champ de mouvement arrière obtenu par une simple opposition de signe du champ avant, conduisant ainsi à une transformée dont la prédiction s’écrit : ht(n) = x2t+1(n) − 1 2 ³ x2t ¡ n − v2t+1(n) ¢ + x2t+2¡ n + v2t+1(n) ¢ ´ (4.13) L’estimation du champ de mouvement v2t+1 minimisant l’énergie d’un bloc B de ht et donc la minimisation du critère J devient ici un problème mono-dimensionnel plus simple à résoudre. La construction d’un nouvel estimateur de mouvement est cependant nécessaire. Des travaux similaires ont été poursuivis dans [156] où les auteurs construisent une transformée bidirectionnelle à un seul champ de mouvement en utilisant un estimateur de mouvement minimisant la somme des erreurs quadratiques avant et arrière. 83 4.1.4 Résultats expérimentaux Prédiction itérative et décroissance de la distorsion Dans le contexte de l’implémentation du codeur vidéo décrit dans le chapitre précédent, nous souhaitons tout d’abord vérifier expérimentalement les propriétés de l’algorithme itératif d’estimation jointe. Celui-ci a été implémenté au sein de la transformée 5/3 présentée dans la section 3.1.3 pour optimiser le choix des champs de mouvement mis en jeu dans la prédiction. Nous avons alors étudié les sous-bandes temporelles issues de la décomposition sur 4 niveaux des séquences vidéo Stefan et Mobile, sans codage spatial ni quantification. Plusieurs simulations ont été effectuées en faisant varier le nombre d’itérations de l’algorithme de prédiction bidirectionnelle et en le comparant avec l’approche classique où les champs de mouvement sont estimés de façon indépendante. Les tableaux Tab. 4.1, 4.2, 4.3 et 4.4 montrent les résultats obtenus en présentant la norme ℓ1 et l’énergie moyenne (norme ℓ2) observées sur les sous-bandes temporelles de détail, calculées sur la composante Y à différents niveaux temporels.