Brevet FR2862470A1 — publié le 20050520

Codage vidéo par descriptions multiples Christophe Tillier et Béatrice Pesquet-Popescu November 16, 2003 1 Codage par descriptions multiples (ENST) Plaçons nous dans un réseau basé sur une commutation de paquets (mode data-gramme), de type IP. Dans ce type de réseau, chaque GOF d'une vidéo sera divisé en différents paquets qui seront routés individuellement. Pour différentes raisons, des paquets peuvent ne pas arriver (panne d'un équipement sur le réseau, ou expiration du TTL -Time To Live- entrainant la destruction du paquet), arriver avec des erreurs (détectées généralement par un code détecteur de type CRC), ou simplement arriver trop tard pour être traités (dans une application de type streaming par exemple où le flux est traité en "temps réel"). Si pour beaucoup d'applications s'appuyant sur le protocole TCP, ce type de problème se résoud par une demande de réémission du paquet défectueux ou manquant, il existe beaucoup d'applications en vidéo où, de toutes façons, la réémission d'un paquet ne pourra pas se faire, car il arriverait trop tard pour être traité. De plus, même s'il existe certains codes cor- recteurs d'erreurs très efficaces (bien que généralement couteux en temps de calcul), ils permettraient au mieux de redonner sa valeur initiale à un paquet arrivant avec quelques erreurs, mais ils ne permettraient pas de toutes façons de résoudre la perte ou l'arrivée trop tardive d'un paquet. Il faut donc prévoir d'autres mécanismes pour répondre à ce problème de transmission. De plus, la conséquence de la perte d'un paquet dépendra beaucoup de la sous-bande spatio-temporelle que code ce paquet, la problématique de cette transmission étant donc directement liée à l'organisation hiérarchique du bitstream à la sortie du codeur ondelette 3D. Le codage à description multiple (MDC) est une solution possible pour ce type de communication. Ce type de codage prévoit un certain réordonnancement des paquets à envoyer, ainsi que l'ajout nécessaire d'une certaine redondance. Avec le codage à description multiple, si tous les paquets sont bien réceptionnés, on doit naturellement pouvoir recréer la vidéo avec la qualité originale, et si un paquet est perdu, quelque soit ce paquet, on doit essayer de minimiser la perte de qualité engendrée par cette perte. Une autre contrainte est la complexité de l'algorithme. Le codage par ondelettes 3D offre une scalabilité "naturelle" presque sans coût de calcul, et donc permet à un serveur de diffuser une même vidéo à différents équipements sur des réseaux hétérogènes sans surcharge de calcul. Nous devons garder ce même objectif pour la MDC et donc prévoir des algorithmes ayant des coûts de calcul très légers. Nous allons par la suite comparer 2 types de MDC, tous deux basés sur le schéma 3 bandes, le premier étant cité dans [9]. 1.1 Schéma existants: MDC 3-bandes avec répétition de la sous-bandes d'approximation Ce codage à description multiple est basé sur une décomposition temporelle 3-bandes (fig. 1). Figure 1: Le schéma lifting 3 bandes utilisé pour l'algorithme de MDC Sans MDC, on a donc à envoyer les sous-bandes de détails ht et ht et la sous-bande d'approximation lt. Il est évident ici que si on envoit de cette manière la vidéo, et qu'on perd un paquet contenant toute ou une partie de l'information de lt, les conséquences sur la qualité finale de la reconstruction seront catastrophiques. La solution proposée ici est donc d'accentuer fortement la redondance sur lt en envoyant 2 fois cette sous-bande: 1 fois avec la sous-bande ht et 1 fois avec la sous-bande g. Cette solution permet effectivement une reconstruction avec la qualité originale si aucun paquet ne se perd, et une solution dégradée (avec une sous-bande de détails en moins) si un des 2 paquets se perd. 1.2 Description de la décomposition temporelle 3-bandes redondante utilisée pour le codage par description multiple Une autre solution possible pour un algorithme de codage à description multiple est de garder le schéma 3-bandes vu précédemment, mais de l'appliquer sur une vidéo dont les trames auraient subies un sous-échantillonage d'un facteur 2 suivant le schéma 2. Figure 2: Le schéma lifting 3 bandes appliqué sur une vidéo souséchantillonée par un facteur 2 1.3 Analyse du schéma avec un seul niveau de décomposition temporelle Notations: Nous introduisons le facteur de redondance, p, comme étant le rapport entre le nombre de trames envoyées dans les descriptions multiples, et le nombre de trames qui seraient envoyées avec un encodeur 3D non robuste (2-bandes ou 3-bandes) comme vu précédemment. Le dénominateur correspond alors au nombre d'images dans la séquence, L, le nominateur au nombre de trames envoyées dans chaque description, multiplié par le nombre de descriptions, D (nous considérons par la suite D = 2). Dans la première description nous transmettons les sous-bandes issues du traite-ment des groupes de trames correspondant à t impairs (que nous noterons Dl), dans la deuxième description les sous-bandes issues du traitement des groupes de trames correspondant à t pairs (que nous noterons D2). Facteur de redondance: Pour effectuer le calcul du facteur de redondance, nous allons calculer le facteur de redondance à des instants temporels multiples entiers du nombre de trames dans un GOF à la fois dans l'encodeur 3D non robuste et dans notre modèle à 2 descriptions, et pour lesquels les deux descriptions ont un nombre égal de GOFs également. Soit L la longueur de la séquence. Dans le codec non robuste les trames sont decomposées par groupes de trois: 3n, 3n + 1, 3n + 2, avec n E {0, . . . , N}, la longueur de la séquence est donc L = 3(N + 1). Le codec avec deux descriptions va encoder les trames 2n', 2n' + 1, 2n' + 2, où n' E {0, ... , N'}. Le nombre de trames envoyées dans les descriptions multiples sera donc L' = 3(N' + 1). L'expression du facteur de redondance p sera L' alors ici: p = - L Comme dit précédemment, pour pouvoir effectuer notre calcul, il faut être syn- chronisé temporellement, c'est-à-dire ici que l'instant temporel 3n + 2 quand n = N doit correspondre à l'instant 2n' + 2 quand n' = N'. On obtient donc 3N = 2N'. N N' Notons alors P = 2 3 On a donc: _L'_3(N'+1) _3(3P+1) _3P+1 p L 3(N + 1) 3(2P + 1) 2P + 1 On en déduit p -> 3/2 quand P - oo. De plus, nous voulions que dans notre modèle à 2 descriptions, les 2 descriptions aient un nombre égal de GOF, ceci signifie ici que le nombre de décompositions temporelles N' + 1 doit être pair, donc P doit être impaire. Le premier cas vérifiant ces conditions est P = 1 L = 9 et correspond au schéma suivant: Séquence originale 0 1 2 3 4 5 6 7 8 Codeur non robuste hi Il hi h2 12 h2 h3 13 h3 Description 1 hi- li hi+ h3- l3 h3+ Description 2 h2 l2 h2+ h2_4 l4 h4+ Figure 3: Construction des 2 descriptions (illustration pour L=9) Dans la suite, nous formaliserons ce type de schéma comme sur la fig. 4. Reconstruction: Si on reçoit les deux descriptions, on dispose de toutes les trames, donc on peut réaliser une reconstruction parfaite. En plus, nous disposons pour chaque trame 2n, n E {1, . . . , N - 1} de deux possibilités pour la reconstruire, à partir de chaque description. On peut améliorer la qualité de la trame reconstruite en faisant une moyenne des deux reconstructions de moins bonne qualité (éventuellement, un xt o o >11 1 hl+ O O > t,l h2_ D > 1,t A A > ll2,t h2+ 0 0 1,t Figure 4: Synchronisation temporelle des trames dans les 2 descriptions algorithme POCS comme nous le décrivons précédemment peut être envisagé à cet effet) Si on perd une description, on va reconstruire trois trames sur quatre de la séquence originale. Les trames manquantes peuvent être interpolées à partir de leur voisines reconstruites, par moyennage de ces trames compensées en mouvement. Il faut utiliser pour cela un "prolongement" des champs de vecteurs mouvement dont on dispose. 1.4 Analyse du schéma MDC avec plusieurs étages de décomposition Le schéma précédent, composé d'un seul étage de décomposition, permet un facteur de scalabilité de 3 et, en le combinant avec une décomposition 2- bandes, on peut obtenir des facteurs de scalabilité de 6 et éventuellement réduire ainsi la redondance (au cas où le schéma trois- bandes intervient au dernier étage de la décomposition). L'efficacité de codage des structures en sous-bandes est cependant accrue quand on cascade plusieurs niveaux de décomposition. Nous pouvons alors créer les descriptions de plusieurs manières: Schéma 1 nous créons le premier étage redondant, en utilisant le schéma précédent, et on itère sur les trames des sous-bandes d'approximation des deux descriptions. Schéma 2 les premiers étages sont obtenus avec une décomposition non redondante et on introduit de la redondance au dernier étage. Pour analyser ces différentes options, considérons deux étages de décomposition. Schéma 1 Dans le premier cas, illustré dans le schéma 5, après un étage de décomposition, les trames des deux sous-bandes d'approximation sont entrelacées et on cascade le schéma sur cette nouvelle "séquence". Nous avons 2 * 1/2 * L trames de détails au premier niveau, et 1/2 * L trames d'approximation. Au deuxième niveau on a donc 1/2 * L détails et 1/2 * 1/2 * L trames d'approximation. Au total: (1 + 1/2 + 1/4) * L pour deux étages. Pour un nombre jrrzax d'étages, on obtient un facteur de redondance qui tend vers 2 quand " oo. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1- - xt o o o o o o o o o o h2_ 1,t 12 1,t h2+ 1,t e e e d A A e e o -o A o A o A o A -11,t hi t,2 0 0 0 > 1,2 ht1+2 O O O, h2-e e > t,2 A A lt 2 h2+ e e > t,2 Figure 5: Synchronisation temporelle des trames obtenues sur 2 niveaux de décomposition (schéma 1) Schéma 2 Construction La construction des deux descriptions dans le deuxième cas est illustré Fig. 6. On repartit les groupes de trois trames, alternativement entre les deux descriptions. Les trames des deux sous-bandes d'approximation sont ensuite entrelacées et le traite-ment est itéré dessus. Redondance Dans ce deuxième cas, nous avons 2/3 * L trames de détails au premier niveau de décomposition, et 1/3*3/2*L trames crées au deuxième niveau. De manière générale, la redondance étant introduite seulement au dernier niveau de la décomposition, le facteur de redondance global est fortement réduit. Il sera de p = 1 + 1/3imax * 3/2. Reconstruction Si on reçoit les deux descriptions, le dernier étage sera reconstruit avec une très bonne qualité, et ensuite on dispose de toutes les trames pour faire une reconstruction parfaite. --- 11 11 I I I 11 I 11 I I--- 11 I > xt É 11 t,l h tl,l h2- 1,t 1,t h2+ l,t o A A o A o -11,t o o o o A A A A A A A A A e A y y y Y y y A o hl- 0 0 > t,2 lt 2 hl+ 0 > t,2 h2- e e t,2 lÉ t2 h2+ e É t,2 Figure 6: Synchronisation temporelle des trames obtenues sur 2 niveaux de décomposition (schéma 2) Si on reçoit seulement une des descriptions, au dernier niveau, on applique les procédé d'interpolation décrit pour le schéma avec un seul étage. Ensuite, pour retrouver les trois trames au niveau supérieur, on peut appliquer le schéma de synthèse sur cette trame d'approximation, en injectant des détails nuls. On peut améliorer la qualité de deux trames avoisinant les trames reconstruites parfaitement en moyennant cette reconstruction avec une image compensée en mouvement à partir de la trame voisine (à gauche ou à droite). References [1] S.J. Choi, J.W. Woods, "Motion-compensated 3-D subband coding of video", IEEE Transactions on Image Processing, vol. 8, pp 155-167, 1999. [2] B. Pesquet-Popescu, V. Bottreau, "Three-dimensional lifting schemes for motion compensated video compression", ICASSP 2001, Salt Lake City, UT, mai 2001. [3] C. Tillier, B. Pesquet-Popescu, "Weighted Average Spatio-Temporal Update Operator for Subband Video Coding", article en préparation. [4] C. Tillier, B. Pesquet-Popescu, Y. Zhan, H. Heijmans, "Scalable video compression with temporal lifting using 5/3 filters", article invité, PCS 2003, Saint-Malo, 23-25 avril 2003. D [5] G. Pau, C. Tillier, B. Pesquet-Popescu, H. Heijmans, "Motion compensation and scalability in lifting-based video coding", article invité à la revue Image Communication. [6] F.J. Hampson, J.-C. Pesquet, "M-band nonlinear subband decompositions with perfect reconstruction", IEEE Transactions on Image Processing, vol. 7, pp 1547-1560, 1998. [7] C. Tillier, B. Pesquet-Popescu, "3D, 3-band, 3-tap temporal lifting for scalable video coding", ICIP 2003, Barcelone, 14-17 septembre 2003. [8] C. Tillier, B. Pesquet-Popescu,M. Van der Schaar, "Bidirectional predictupdate 3-band schemes", article soumis à ICASSP 2004. [9] Mihaela Van der Schaar, Deepak S. Turaga, "Multiple description scalable coding using wavelet-based motion compensated temporal filtering", ICIP 2003, Barcelone, 14-17 septembre 2003. REVENDICATIONS 1 Procédé pour le codage vidéo par descriptions multiples en trois bandes caractérisé en ce que on accentue fortement la redondance sur lt en envoyant 2 fois cette sous-bande, 1 fois avec la sous-bande ht et 1 fois avec la sous-bande ht+ . 2 Procédé pour le codage vidéo par descriptions multiples en trois bandes caractérisé en ce qu'il s'applique sur une vidéo dont les trames auraient subies un sous-échantillonage d'un facteur 2. 3 - Procédé pour le codage vidéo par descriptions multiples caractérisé en ce que la redondance est introduite seulement au dernier niveau de la décomposition, le facteur de redondance global est fortement réduit. Il sera de p = 1 + 1/3"ax * 3/2