Brevet FR2842670A1 — publié le 20040123

Perfectionnement à la compression de données numériques L'invention concerne la compression de données numériques, notamment pour des signaux multimédia. Pour réduire le débit de transmission des données numériques, on les comprime, en cherchant à s'approcher du maximum théorique que les spécialistes appellent "l'entropie du signal". On utilise souvent des codes statistiques aussi appelés codes à longueurs variables, par exemple les codes de Huffman. Encore faut-il se préoccuper également des effets des perturbations du signal. En effet, celles-ci réduisent le débit utile: lorsque des codes correcteurs d'erreurs détectent une erreur à la réception, il faut re-transmettre la partie correspondante du signal. Les solutions actuelles, sur lesquelles on reviendra, se fondent sur l'hypothèse qu'une certaine qualité de service du transport des données est garantie. Ceci permet d'atteindre un taux d'erreur résiduel quasi nul à la réception, après décodage. Mais cette hypothèse de taux d'erreur résiduel quasi nul n'est plus vraie lorsque les caractéristiques des canaux varient 2 0 dans le temps (canaux non stationnaires), notamment dans les réseaux sans fil et mobiles. Le besoin se fait donc sentir de solutions qui soient moins dépendantes du caractère stationnaire des canaux de transmission. 2 5 La présente invention vient proposer des avancées en ce sens. Selon un aspect de l'invention, il est proposé un codeur de compression de données numériques, qui comprend: - une entrée (physique ou non) pour un premier flux de données (SH), et un second flux de 3 0 données (SL), - une table de codage, contenant une correspondance entre des symboles du premier flux de données et des mots de code, o, pour certains symboles, il existe plusieurs mots, dits redondants, correspondant au même symbole, et - un module de traitement pour coder les symboles du premier flux de données d'après la table, en choisissant parmi les mots redondants, en fonction d'une partie au moins du second flux de données. Selon différents autres aspects: - les mots de code peuvent être de longueur fixe, - le module de traitement comprend: une fonction de calcul de la capacité de multiplexage courante du premier flux de données (SH), au vu de la table de codage, et 10. une fonction d'extraction, dans le second flux de données (SL), d'une partie multiplexée, déterminée d'après la capacité de multiplexage courante, pour être portée par lesdits mots redondants. - le codeur comprend une transformation d'un flux binaire en un flux de variable multivaluée, en particulier en utilisant les transformations décrites dans la table 2 ci-après. - le second flux de données est préalablement encodé. - le reste du second flux de données est concaténé aux données transmises. L'invention vise également un décodeur, propre à effectuer les opérations inverses ou réciproques de celle du codeur, dans ses différents aspects. L'invention vise encore un procédé de compression de données numériques, qui comprend les étapes suivantes: a. établir une table de codage, contenant une correspondance entre des symboles du premier flux de données et des mots de code, o, pour certains symboles, il existe 2 5 plusieurs mots, dits redondants, correspondant au même symbole, et b. coder les symboles d'un premier flux de données d'après la table, en choisissant parmi les mots redondants, en fonction d'une partie au moins d'un second flux de données. 3 0 Ce procédé peut intégrer les autres aspects du codage. Enfin, l'invention vise également le procédé de décompression de données numériques, comprenant les étapes réciproques de celles du procédé de compression. D'autres caractéristiques et avantages de l'invention apparaîtront à l'examen de la description détaillée ci-après, et des dessins annexés, sur lesquels: - la figure 1 illustre de façon schématique un procédé de création de codes, - la figure 2 est un diagramme formant vue générale du processus d'encodage, - la figure 2A ou table 1 illustre un exemple simplifié de code multiplexé, à quatre éléments, - la figure 3 illustre un premier mode de réalisation d'un processus détaillé d'encodage, - la figure 4 illustre une variante de réalisation du processus de la figure 3, - la figure 5 illustre un exemple de création d'une capacité de stockage par l'attribution de plusieurs mots de code à un symbole, un flux de données q pouvant être conjointement stocké, et - la figure 6 ou table 2 illustre des transformations utilisées un exemple o le paramètre f, est égal à 5. En outre: - l'annexe 1 contient des expressions utilisées dans la présente description, et - l'annexe 2 contient des algorithmes en langage naturel utilisés dans la présente description. Les dessins et les annexes à la description comprennent, pour l'essentiel, des éléments de caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la description, mais aussi contribuer à la définition de l'invention, le cas échéant. La description détaillée ci-après est structurée en sections, qui facilitent la lecture et les renvois. 1. Contexte Tout système de compression de signaux multimédia (image, vidéo, audio, parole) fait appel à des codes statistiques aussi appelés codes à longueurs variables. Ceux-ci permettent 3 0 d'obtenir des débits approchant ce que les spécialistes appellent "l'entropie du signal". Les codes les plus utilisés dans les systèmes existants (en particulier dans les standards) sont les codes de Huffman. K Plus récemment, on a vu un regain d'intérêt pour les codes arithmétiques en raison de leurs performances accrues en terme de compression. Ils permettent en effet de découpler le processus d'encodage du modèle supposé de la source. Ceci permet aisément d'utiliser des modèles statistiques d'ordre supérieur. Jusque récemment, la conception des systèmes de compression se faisait en supposant une qualité de service transport garantie. On supposait en effet que les couches inférieures du modèle OSI incorporent des codes correcteurs d'erreurs garantissant un taux d'erreur résiduel vu de l'application quasi-nul. Les codes à longueurs variables pouvaient donc être largement utilisés malgré leur forte sensibilité au bruit de transmission. Toute erreur dans le train binaire peut engendrer une désynchronisation du décodeur et donc une propagation des erreurs sur la suite des informations décodées. Pour pallier ce problème de propagation, les standards de premières générations (H.261, H.263, MPEG-1, MPEG-2) ont incorporé dans la syntaxe du train binaire transmis des marqueurs de synchronisation. Ce sont des mots de code longs (16 ou 22 bits constitués d'une suite de 15 ou 21 bits à '1' suivis d'un 'O') non émulables par des erreurs se produisant 2 0 sur les autres mots du codes et qui peuvent donc être reconnus par le décodeur avec une probabilité proche de '1'. Cela conduit à structurer le train binaire en paquets délimités par ces marqueurs de synchronisation. Cela permet de confiner la propagation des erreurs au sein du paquet. 2 5 Cependant si une erreur intervient en début de paquet la suite du paquet peut être perdue. En outre, la périodicité de ces marqueurs de synchronisation doit être restreinte pour éviter une perte trop grande en efficacité de compression. Cette hypothèse de taux d'erreur résiduel quasi nul n'est plus vraie dans les réseaux sans fil et mobiles, dont les caractéristiques des canaux varient dans le temps (canaux non stationnaires). Ce taux d'erreur résiduel vu par le décodeur des signaux de source est souvent loin d'être négligeable. cY Les nouveaux standards (H.263+ et MPEG-4) ont alors fait appel à des codes à longueurs variables réversibles (RVLC []). La particularité de ces codes est qu'ils peuvent être décodés du premier vers le dernier bit d'un paquet, et, à l'inverse, du dernier vers le premier bit du paquet. Si une erreur s'est produite en milieu de paquet, cette symétrie du code permet de confiner la propagation des erreurs sur un segment en milieu de paquet au lieu de la propager jusqu'à la fin du paquet délimité par un marqueur de synchronisation. Cependant, la symétrie du code engendre une perte en efficacité de compression par rapport à un code de Huffman de 1 0 l'ordre de 10 %. En outre les codes à longueurs variables réversibles n'évitent pas complètement le problème de propagation des erreurs: si une erreur se produit en début et en fin de paquet, tout le paquet risque d'être erroné. La conception de codes qui soient à la fois performants en compression (i. e., qui permettent d'approcher l'entropie de la source), tout en étant robustes au bruit de transmission, constitue donc un enjeu important, notamment pour les futurs systèmes de communication multimédia (image, vidéo, audio, parole) mobiles. Pour ces systèmes de nouveaux standards sont à l'étude à la fois au sein de l'ITU (International Telecommunication Union) et de l'ISO (International Standard Organization). Bien que les standards occupent une place prépondérante dans le secteur des télécommunications, une telle famille de codes peut aussi trouver des applications sur des marchés de niche faisant appel à des solutions propriétaires. 2 5 2 Description 2.1 Principe général Le principe général du procédé consiste à créer des codes de longueur fixée pour les données 3 0 de source importantes (flux s1l), en attribuant plusieurs mots de codes à chaque réalisation possible de cette source. Ainsi, pour transmettre un symbole, il est possible de choisir parmi les différentes représentations possibles de celui-ci. Ce choix, qui est une variable multi-valuée, définit une capacité de stockage qui va pouvoir être utilisée pour transmettre conjointement d'autres données (cf. exemple de la figure 5). Ce sont les données d'importance moindre, représentées par un flux noté SL, qui vont être représentées via la représentation multiple des symboles. Ce document présente le procédé de création de ces codes, et le procédé de codage. Une variante permettant d'éviter les calculs sur entiers longs est également présentée. Le processus de décodage associé est effectué en procédant aux opérations inverses de celles de l'encodage. 2.2 Création des codes multiplexés La source importante, sT, prend ses valeurs dans un alphabet à Q éléments, qui peut être défini par l'expression (El) en annexe. La loi [i de probabilité d'apparition des symboles sur cet alphabet est supposée connue. On note pli la probabilité associée au symbole ai de l'alphabet de la source s1, comme représenté par l'expression (E2). Le procédé de création des codes, représenté sur la figure 1, peut se décomposer en 2 étapes - Pour chaque symbole ai, choix du nombre Ni de mots de code affectés à ce symbole, 2 5 - Allocation des mots de codes aux symboles. 2.2.1 Sélection des paramètres de codes c et (Ni) 3 0 1. Choix d'un paramètre c de longueur de mot de code, en nombre de bits. Usuellement c 14. Ceci définit 2 c mots de codes, à répartir entre les symboles de l'alphabet A. O -7 2. On partitionne l'ensemble des symboles de l'alphabet A en deux sous-ensembles A, et AM. Le premier est l'ensemble des symboles ai dont la probabilité F i est inférieure ou égale à 1 /2 c, le second est son complémentaire dans A. Les cardinaux de ces ensembles sont notés respectivement Qm et QM. 3. La loi de probabilité j sur les symboles de AM est alors calculée. Elle est donnée par l'expression (E3). 4 Le nombre de mots de codes par symbole est alors choisi de manière à vérifier approximativement l'expression (E4), sous la contrainte de l'expression (E5). Dans ce but, un algorithme classique d'optimisation peut être utilisé. Variante: Dans une variante, Une étape additionnelle est ajoutée (Svar), et les étapes 1 et 4 se déclinent respectivement sous la forme suivante: lvar - Soient f1 = 2, f2 = 3,..., f, les v premiers nombres premiers. En plus du paramètre c, un nombre premier f, est également choisi. Usuellement f, = 5. 2 0 - 4var On procède de la même manière, mais en ajoutant un contrainte supplémentaire pour le choix du nombre de mots de code Ni associés à chaque symbole : la décomposition en facteurs premiers de tous les N i ne doit pas contenir de facteur premier supérieur à f,. 2 5 - 5var La décomposition en facteurs premiers de chaque Ni est alors effectuée, et on calcule pour tout Ni le nombre de fois que chaque facteur premier f, avec 1 indexe le symbole a, considéré et j indexe le nombre premier fi considéré. 2.2.2 Allocation des mots de codes aux symboles L'ordre lexicographique de l'étiquetage binaire (0000, 0001,..) est utilisé pour affecter aux différents symboles le nombre Ni de mots de codes déterminé à l'étape précédente. L'ensemble des mots de codes ainsi associés à un symbole ai est appelé classe d'équivalence de ai, et notée Ci. On associe alors aux mots de codes de chaque classe d'équivalence une valeur entre 0 et Ni -1, appelée ici état. Cette valeur identifie le mot de code au sein de la classe d'équivalence. Ainsi, à chaque mot de code c; est associé un symbole ai et une variable d'état comprise entre 0 et N1 - 1, comme illustré par l'expression (E6). Un exemple de code ainsi construit est donné dans la table 1. 2.3 Processus d'encodage Le processus d'encodage (cf. figure 2 et 3) se décompose de la manière suivante: 1. Le flux de données d'importance moindre subit est encodé en une suite binaire b = (b" b2, -., byB) A cet effet, un codeur réversible de type Huffman ou codeur arithmétique (non restrictif) 2 0 peut être utilisé. Cela aboutit à la génération d'une suite de bits, notée b. 2. De la séquence de symboles s,, S2, sKH du flux s%, on déduit les valeurs n1, n2,... nKH associées. 2 5 3. On en déduit la valeur A, ici selon l'expression (E7). On calcule le nombre K'B de bits qui vont pouvoir être stockés en utilisant la redondance intrinsèque des codes multiplexés, selon l'expression (E8) 4. Les KB derniers bits du flux b sont utilisés pour calculer un entier long y, donné ici par 3 0 la relation (E9) 5. La valeur y permet alors de calculer les états q,, 1 précédente permet de choisir le mot de code dans la table des mots de codes multiplexés. 7. Les KH - K', bits du flux d'importance moindre sont alors concaténés à la séquence de mots de codes multiplexés précédemment évaluée. 2.4 Variante au processus d'encodage La variante du processus d'encodage (cf. figure 4) se décompose de la manière suivante: 1. Cf étape 1 de la section 2.3 2. Cf. étape 2 de la section 2.3 3. Le nombre total de fois o chaque facteur premier ft apparaît dans l'ensemble des 2 0 décompositions en facteurs de la séquence nr est alors calculé. Il est noté dj dans la suite, et représente le nombre de variables f,-valuées qui peuvent être multiplexées avec le flux s11. 4. On choisit alors les transformations qui vont être utilisées pour transformer le train binaire en ces variables f,-valuées. Ces transformations dépendent de la valeur de f, choisie. Les 2 5 transformations utilisés pour f, = 5 sont présentées dans la table 2. Elles se présentent sous la forme illustrée dans les expressions (El 0) annexées. Ainsi elles prennent UT bits en entrée et les transforment en respectivement VT, T2,..., VTv 3 0 variables 2, 3,..., f. -valuées. Or le nombre requis de variables de chaque type est connu: pour chaque type de variable fj, il est dj (cf. étape 3). L'algorithme A2 annexé peut être utilisé pour calculer le nombre gT, de fois que la transformation T z doit être utilisée.(Les transformations sont supposées être classées dans l'ordre décroissant de leur pertinence dans la table). 5. Ayant choisi le nombre de transformations de chaque type qui seront utilisées, on les applique à la fin au flux binaire b. - Les UT bits en entrée sont vus comme la représentation binaire d'un entier e. - Cet entier est alors décomposé en plusieurs variables f, -valuées, comme précisé dans les expressions (El0). On note eJ ces variables, o: j indique que la valeur obtenue est la réalisation d'une variable fj-valuée, et r indique le numéro de variable f1 -valuée. Les valeurs des er peuvent s'obtenir à partir de e avec le procédé de l'algorithme A3. A l'issue de cette étape, v séquences de variables sont disponibles: le premier, noté F,, est une séquence de longueur dl de variables 2-valuée (bits), le j-ème, noté Fj, est une séquence de longueur dj de variables fj-valuée. Des pointeurs de positions sont associés aux séquences, ils sont initialement positionnés sur le début de chaque séquence. 2 5 6. A partir de ces variables, on calcule le flux d'état q =( qj, q2,.., qKH). Pour tout t tel que 1 ,fi-valuées,...,f,-valuées) qui permettront de créer la variable nivaluée (q,). Notons qu'à la fin de cette étape, toutes..DTD: les variables des flux Fj ont été utilisées. 7. Pour tout t tel que 1 mots de codes multiplexés précédemment évaluée. Ainsi, l'invention permet le multiplexage de deux flux de données SH et SL, afin de diminuer la sensibilité aux erreurs de l'un d'eux SH, désigné comme plus important ou prioritaire. Ces deux flux peuvent être distingués dans la même source de signaux, notamment comme dans les quelques exemples suivants de sources SH et SL: - basses fréquences et hautes fréquences extraites par décomposition multi-résolution (par bancs de filtres, transformées en ondelettes) d'un signal, - information de texture (ex: coefficients DCT, coefficients ondelettes) et information de mouvement, bits de poids forts et bits de poids faibles des coefficients ondelettes ou des échantillons 2 0 quantifiés d'un signal. Bien entendu, l'énumération ci-dessus n'a aucun caractère exhaustif. Par ailleurs, dans la mesure o les mots de code sont de longueur fixe (ou bien si l'on utilisait des marqueurs de synchronisation), l'invention permet la création d'un code multiplexé permettant de décrire conjointement deux flux, dont un au moins bénéficie d'une synchronisation parfaite. Annexe 1 - Formules (El) A = {ai,..., ai,, an} (E2) Hi = P(ai) (E3) = 2nc% (E4) Ni = (2C Qm)* pi (E5) EiZ. Ni =2c (E6) cij = (si, qj) (E7) A =IKH nt (E8) KB= [l092(A)j (E9) a= E-1 br+KB KI2r-1. vl variables 2-valuée, el,1, e2,1,..., et71,î (EIO) u-bits VT| Vr,2 variables 3-valuée, el,2, e2,2,..,ev,2 V-r,,v-, variables f,,-valuée, el,> , e2,,,... eVT,, Annexe 2 - Algorithmes Pour t = 1: KH Ai qt = y' modulo nt te = n),-t Fin pour z= O % Tant qu'il reste des variables fj-valuées à obtenir Tant que sum(dj) > O % Calcul du nombre de fois que la transformation Tz est utilisée g2- = floor(min( di ")) o vfz, # O A2 % Calcul du nombre de variables fj-valuée % qui n'ont pas été transformées par la transformation T, Pour chaque j entre 1 et v dj = d-gTz * vT.,j % Essaie la transformation suivante z= z+1 e' =e Pour j=1: v Pour r = VT,j A3 erj = e' modulo fj e' = !e- fi Fin pour Fin pour Revendications 1. Codeur de compression de données numériques, caractérisé en ce qu'il comprend: - une entrée pour un premier flux de données (S., et un second flux de données (SL), - une table de codage, contenant une correspondance entre des symboles du premier flux de données et des mots de code, o, pour certains symboles, il existe plusieurs mots, dits redondants, correspondant au même symbole, et - un module de traitement pour coder les symboles du premier flux de données d'après la table, en choisissant parmi les mots redondants, en fonction d'une partie au moins du second flux de données. 2. Codeur selon la revendication 1, caractérisé en ce que les mots de code sont de longueur fixe. 3. Codeur selon l'une des revendications 1 et 2, caractérisé en ce que le module de traitement comprend: - une fonction de calcul de la capacité de multiplexage courante du premier flux de données (S.), au vu de la table de codage, et - une fonction d'extraction, dans le second flux de données (SI), d'une partie multiplexée, 2 0 déterminée d'après la capacité de multiplexage courante, pour être portée par lesdits mots redondants. 4. Codeur selon l'une des revendications précédentes, caractérisé en ce qu'il comprend une transformation d'un flux binaire en un flux de variable multi-valuée, en particulier en 2 5 utilisant les transformations décrites dans la table 2. 5. Codeur selon l'une des revendications précédentes, caractérisé en ce que le second flux de données est préalablement encodé. 6. Codeur selon l'une des revendications précédentes, caractérisé en ce que le reste du second flux de données est concaténé aux données transmises. 7. Décodeur, propre à effectuer les opérations inverses de celle du codeur de l'une des revendications précédentes. 8. Procédé de compression de données numériques, caractérisé par les étapes suivantes: a. établir une table de codage, contenant une correspondance entre des symboles du premier flux de données et des mots de code, o, pour certains symboles, il existe plusieurs mots, dits redondants, correspondant au même symbole, et b. coder les symboles d'un premier flux de données d'après la table, en choisissant parmi les mots redondants, en fonction d'une partie au moins d'un second flux de 1 0 données. 9. Procédé selon la revendication 8, caractérisé en ce que les mots de code sont de longueur fixe. 10. Procédé selon l'une des revendications 8 et 9, caractérisé en ce que l'étape b. comprend - de calculer la capacité de multiplexage courante du premier flux de données (S.), au vu de la table de codage, et - d'extraire, dans le second flux de données (S.), d'une partie multiplexée, déterminée d'après la capacité de multiplexage courante, pour être portée par lesdits mots redondants. 11. Procédé selon l'une des revendications 8 à 10, caractérisé en ce que l'étape b. comprend de transformer un flux binaire en un flux de variable multi-valuée, en particulier en utilisant les transformations décrites dans la table 2. 2 5 12. Procédé selon l'une des revendications 8 à 11, caractérisé en ce que le second flux de données est préalablement encodé. 13. Procédé selon l'une des revendications 8 à 12, caractérisé en ce que le reste du second flux de données est concaténé aux données transmises. 14. Procédé de décompression de données numériques, caractérisé par les étapes réciproques de celles du procédé selon l'une des revendications 8 à 13.