FR2773927A1 - Codage et decodage de signal numerique - Google Patents

Abstract

L'invention propose un procédé de codage de signal numérique comportant une étape d'analyse (E1) du signal numérique (IM) en une pluralité de sous-bandes de fréquence, au moins une première sous-bande ayant une fréquence plus faible et au moins une seconde sous-bande ayant une fréquence plus élevée, caractérisé en ce qu'il comporte, pour chaque seconde sous-bande, les étapes de :- division (E4) de la seconde sous-bande en blocs (B i,n ). - sélection (E9) de premiers blocs qui sont à coder par mise à une valeur prédéterminée et de seconds blocs qui sont à coder par quantification codée en treillis, selon un critère de sélection,- liaison (E16) des seconds blocs sélectionnés à l'étape précédente pour former une suite de blocs,- codage (E17) de la suite de blocs par quantification codée en treillis d'une suite de coefficients extraits des seconds blocs de la seconde sous-bande.

Description

La présente invention concerne d'une manière générale le codage de signal numérique et propose à cette fin un dispositif et un procédé de codage d'un signal numérique par décomposition en sous-bandes de fréquence du signal et codage des coefficients issus de la décomposition en sous-bandes. Elle concerne également un procédé et un dispositif de décodage correspondants au procédé et au dispositif de codage.

Le codage a pour but de compresser le signal, ce qui permet de transmettre, respectivement mémoriser, le signal numérique en réduisant le temps de transmission, ou le débit de transmission, respectivement en réduisant la place mémoire utilisée.

L'invention se situe dans le domaine de la compression avec perte de signaux numériques.

II est connu de décomposer un signal en sous-bandes de fréquence avant de le compresser. La décomposition consiste à créer, à partir du signal, un jeu de sous-bandes qui contiennent chacune une gamme limitée de fréquences. Les sous-bandes peuvent être de différentes résolutions, la résolution d'une sous-bande étant le nombre d'échantillons par unité de longueur utilisés pour représenter cette sous-bande. Dans le cas d'un signal numérique d'image, une sous-bande de fréquence de ce signal peut être ellemême considérée comme une image, c'est-à-dire un tableau bidimensionnel de valeurs numériques.

II est à noter que la décomposition d'un signal en sous-bandes de fréquence ne crée aucune compression en elle-même, mais permet de décorréler le signal de façon à en éliminer la redondance préalablement à la compression proprement dite. Les sous-bandes sont ainsi codées de manière plus efficace que le signal d'origine.

Un procédé connu de codage de signal numérique, en l'occurrence d'une image numérique, comporte trois étapes principales. L'image est tout d'abord décomposée par une transformation en sous-bandes de fréquence, puis une quantification scalaire des coefficients ainsi obtenus est réalisée. Les indices quantifiés sont enfin codés par un codage entropique sans perte.

Ce procédé permet un taux de compression élevé du signal.

Cependant, le rapport entre le taux de compression et l'erreur de codage est perfectible.

La présente invention vise à remédier aux inconvénients de la technique antérieure, en fournissant un dispositif et un procédé de compression de signal numérique qui offre un rapport compression sur distorsion élevé.

L'invention propose un procédé de codage de signal numérique, comportant l'analyse du signal pour séparer l'information pertinente et l'information non pertinente, puis le codage de l'information non pertinente selon un premier mode de codage qui offre un haut taux de compression, et codage de l'information pertinente selon un second mode de codage qui limite la distorsion.

A cette fin, I'invention propose un procédé de codage de signal numérique comportant une étape d'analyse du signal numérique en une pluralité de sous-bandes de fréquence réparties selon au moins deux bandes de fréquence différentes, au moins une première sous-bande ayant une fréquence plus faible et au moins une seconde sous-bande ayant une fréquence plus élevée,
caractérisé en ce qu'il comporte, pour chaque seconde sous-bande, les étapes de:
- division de la seconde sous-bande en blocs,
- sélection de premiers blocs qui sont à coder par mise à une valeur prédéterminée et de seconds blocs qui sont à coder par quantification codée en treillis, selon un critère de sélection,
- liaison des seconds blocs sélectionnés à l'étape précédente pour former une suite de blocs,
- codage de la suite de blocs par quantification codée en treillis d'une suite de coefficients extraits des seconds blocs de la seconde sous-bande.

Corrélativement, I'invention propose un dispositif de codage de signal numérique comportant des moyens d'analyse du signal numérique en une pluralité de sous-bandes de fréquence réparties selon au moins deux bandes de fréquence différentes, au moins une première sous-bande ayant une fréquence plus faible et au moins une seconde sous-bande ayant une fréquence plus élevée,
caractérisé en ce qu'il comporte:
- des moyens de division de chaque seconde sous-bande en blocs,
- des moyens de sélection de premiers blocs qui sont à coder par mise à une valeur prédéterminée et de seconds blocs qui sont à coder par quantification codée en treillis, selon un critère de sélection,
- des moyens de liaison des seconds blocs sélectionnés à l'étape précédente pour former une suite de blocs,
- des moyens de codage de la suite de blocs par quantification codée en treillis d'une suite de coefficients extraits des seconds blocs de la seconde sous-bande.

La décomposition en sous-bande de fréquence permet de séparer l'information pertinente de l'information non pertinente. L'information non pertinente est ensuite codée par mise à la valeur prédéterminée, qui nécessite un débit nul. La compression de l'information non pertinente est maximale.

II est ainsi possible d'accorder plus de débit à l'information pertinente, présente dans les seconds blocs, qui est ainsi codée plus précisément. La distorsion de l'information pertinente est minimale, grâce à la liaison des seconds blocs et à leur codage par quantification codée en treillis.

Globalement, le rapport compression sur distorsion obtenu est élevé.

La valeur prédéterminée est par exemple nulle, de sorte qu'au décodage, sont construits des blocs dont tous les coefficients sont nuls.

Selon une caractéristique préférée, pour chacun des blocs, L'étape de sélection comporte le codage du bloc par mise à la valeur prédéterminée et par un second mode de codage, la comparaison des deux modes de codage selon le critère de sélection et la sélection du codage par mise à la valeur prédéterminée si le bloc codé par mise à la valeur prédéterminée satisfait le critère de sélection.

La sélection est simple et rapide à mettre en oeuvre. Par exemple, le second mode de codage est une quantification scalaire des coefficients du bloc, ou le second mode de codage est une quantification codée en treillis d'une suite de coefficients extraits des blocs de la seconde sous-bande. Ce dernier cas permet de simplifier la structure du dispositif de codage, puisque les moyens de sélection utilisent alors le même codage que les moyens de codage des seconds blocs.

Selon une caractéristique préférée, le critère de sélection minimise une somme pondérée du débit et de l'erreur de codage provoqués par le codage du bloc considéré.

Selon une autre caractéristique préférée, un indicateur est associé à chaque bloc pour indiquer si le bloc considéré est codé par mise à la valeur prédéterminée ou non.

Selon une autre caractéristique préférée, ladite au moins une première sous-bande est codée selon un troisième mode de codage.

Le dispositif de codage comporte des moyens adaptés à mettre en oeuvre les caractéristiques précédentes.

L'invention concerne également un procédé de décodage d'un signal numérique codé, ledit signal comportant des représentations codées de blocs formés dans des sous-bandes de fréquence du signal d'origine, chaque représentation codée comportant au moins un indicateur représentatif d'un codage par mise à une valeur prédéterminée ou d'un codage par quantification codée en treillis d'une suite de coefficients extraits de blocs, caractérisé en ce qu'il comporte les étapes de:
- lecture de la valeur de l'indicateur de chacun des blocs,
- décodage des représentations par formation de blocs reconstruits dont tous les coefficients ont la valeur prédéterminée ou par déquantification codée en treillis de la suite de coefficients, en fonction de la valeur de l'indicateur respectif de chacun des blocs.

Corrélativement, I'invention concerne un dispositif de décodage de signal numérique codé, ledit signal comportant des représentations codées de blocs formés dans des sous-bandes de fréquence du signal d'origine, chaque représentation codée comportant au moins un indicateur représentatif d'un codage par mise à une valeur prédéterminée ou d'un codage par quantification codée en treillis d'une suite de coefficients extraits de blocs, caractérisé en ce qu'il comporte:
- des moyens de lecture de la valeur de l'indicateur de chacun des blocs,
- des moyens de décodage des représentations par formation de blocs reconstruits dont tous les coefficients ont la valeur prédéterminée ou par déquantification codée en treillis de la suite de coefficients, en fonction de la valeur de l'indicateur respectif de chacun des blocs.

Le procédé et le dispositif de décodage permettent de reconstruire le signal, par exemple dans un appareil récepteur correspondant à un appareil émetteur dans lequel le signal a été codé selon l'invention.

Les caractéristiques et avantages de la présente invention apparaîtront plus clairement à la lecture d'un mode préféré de réalisation illustré par les dessins ci-joints, dans lesquels:
- la figure 1 représente un bloc diagramme d'un mode de réalisation d'un dispositif de codage de signal numérique selon l'invention;
- la figure 2 représente un circuit de décomposition en sous-bandes de fréquence, inclus dans le dispositif de la figure 1;
- la figure 3 représente une image numérique à coder par le dispositif de codage selon l'invention;
- la figure 4 représente une image décomposée en sous-bandes par le circuit de la figure 2;
- la figure 5 représente une image décomposée en sous-bandes puis divisée en blocs;
- la figure 6 représente un circuit de codage par quantification codée en treillis, inclus dans le dispositif de la figure 1;
- la figure 7 représente un bloc diagramme d'un mode de réalisation d'un dispositif de décodage selon l'invention;
- la figure 8 représente un algorithme de codage d'un signal numérique selon un mode de réalisation de l'invention ; et
- la figure 9 représente un algorithme de décodage d'un signal numérique selon un mode de réalisation de l'invention.

Selon le mode de réalisation choisi et représenté à la figure 1, un dispositif de codage selon l'invention est destiné à coder un signal numérique dans le but de le compresser. Le dispositif de codage est intégré dans un appareil 100, qui est par exemple un appareil photographique numérique, ou un camescope numérique, ou un système de gestion de base de données, ou encore un ordinateur.

Le signal numérique à compresser SI est dans ce mode particulier de réalisation une suite d'échantillons numériques représentant une image.

Le dispositif comporte une source de signal 1, ici de signal d'image.

De manière générale, la source de signal soit contient le signal numérique, et est par exemple une mémoire, un disque dur ou un CD-ROM, soit convertit un signal analogique en signal numérique, et est par exemple un camescope analogique associé à un convertisseur analogique-numérique. Une sortie 11 de la source de signal est reliée à un circuit d'analyse, ou de décomposition en sous-bandes 2. Le circuit 2 a une première sortie 21 reliée à un circuit de codage 3.

Des secondes sorties 22 du circuit de décomposition 2 sont reliées à un circuit de division en blocs 4. Le circuit 4 a des premières sorties 41 reliées à un premier circuit de codage 5 et des secondes sorties 42 reliées à un second circuit de codage 6.

Une sortie 51 du circuit 5 et une sortie 61 du circuit 6 sont reliées à un circuit de comparaison 7, dont une première sortie 71 est reliée à un circuit de traitement 11 et dont une seconde sortie 72 est reliée à un circuit de liaison 8. Ce dernier a une sortie 81 reliée à un circuit 9 de codage par quantification codée en treillis, dit TCQ d'après l'Anglais "Treillis Coded Quantization".

Le circuit 9 a des sorties 91 et 92 reliée à un circuit 10 de codage entropique dont une sortie 101 est reliée au circuit de traitement 11, qui est par exemple un circuit de transmission, ou une mémoire. Une sortie 31 du circuit de codage 3 est également reliée au circuit de traitement 11.

La source d'image 1 est un dispositif pour générer une suite d'échantillons numériques représentant une image IM. La source 1 comporte une mémoire d'image et fournit un signal numérique d'image SI à l'entrée du circuit de décomposition 2. Le signal d'image SI est une suite de mots numériques, par exemple des octets. Chaque valeur d'octet représente un pixel de l'image IM ici à 256 niveaux de gris, ou image noir et blanc.

Le circuit de décomposition en sous-bandes 2, ou circuit d'analyse, est, dans ce mode de réalisation, un ensemble classique de filtres, respectivement associés à des décimateurs par deux, qui filtrent le signal d'image selon deux directions, en sous-bandes de hautes et basses fréquences spatiales. Selon la figure 2, le circuit 2 ici comporte trois blocs successifs d'analyse pour décomposer l'image IM en des sous-bandes selon trois niveaux de résolution. II est à noter que l'invention n'implique pas nécessairement une décomposition selon plusieurs niveaux de résolution, mais seulement une décomposition du signal à coder en plusieurs sous-bandes.

De manière générale, la résolution d'un signal est le nombre d'échantillons par unité de longueur utilisés pour représenter ce signal. Dans le cas d'un signal d'image, la résolution d'une sous-bande est liée au nombre d'échantillons par unité de longueur utilisés pour représenter cette sous-bande horizontalement et verticalement. La résolution dépend du nombre de décimations effectuées, du facteur de décimation et de la résolution de l'image initiale.

Le premier bloc d'analyse reçoit le signal numérique d'image et l'applique à deux filtres numériques respectivement passe-bas et passe-haut 21 et 22 qui filtrent le signal d'image selon une première direction, par exemple horizontale dans le cas d'un signal d'image. Après passage par des décimateurs par deux 210 et 220, les signaux filtrés résultant sont respectivement appliqués à deux filtres passe-bas 23 et 25, et passe-haut 24 et 26, qui les filtrent selon une seconde direction, par exemple verticale dans le cas d'un signal d'image. Chaque signal filtré résultant passe par un décimateur par deux respectif 230, 240, 250 et 260. Le premier bloc délivre en sortie quatre sous-bandes LL1, LH1, HL1 et HH1 de résolution RES1 la plus élevée dans la décomposition.

La sous-bande LL1 comporte les composantes, ou coefficients, de basse fréquence, selon les deux directions, du signal d'image. La sous-bande
LH1 comporte les composantes de basse fréquence selon une première direction et de haute fréquence selon une seconde direction, du signal d'image.

La sous-bande HL1 comporte les composantes de haute fréquence selon la première direction et les composantes de basse fréquence selon la seconde direction. Enfin, la sous-bande HH1 comporte les composantes de haute fréquence selon les deux directions.

Chaque sous-bande est un ensemble de coefficients réels construit à partir de l'image d'origine, qui contient de l'information correspondant à une orientation respectivement verticale, horizontale et diagonale des contours de l'image, dans une bande de fréquence donnée. Chaque sous-bande peut être assimilée à une image.

La sous-bande LL1 est analysée par un bloc d'analyse analogue au précédent pour fournir quatre sous-bandes LL2, LH2, HL2 et HH2 de niveau de résolution RES2 intermédiaire dans la décomposition. La sous-bande LL2 comporte les composantes de basse fréquence selon les deux directions d'analyse, et est à son tour analysée par le troisième bloc d'analyse analogue aux deux précédents. Le troisième bloc d'analyse fournit des sous-bandes LL3,
LH3, HL3 et HH3, de résolution RES3 la plus faible dans la décomposition, résultant du découpage en sous-bandes de la sous-bande LL2.

Chacune des sous-bandes de résolution RES2 et RES3 correspond également à une orientation dans l'image.

La décomposition effectuée par le circuit 2 est telle qu'une sousbande d'une résolution donnée est découpée en quatre sous-bandes de résolution inférieure et a donc quatre fois plus de coefficients que chacune des sous-bandes de résolution inférieure.

Une image numérique IM en sortie de la source d'image 1 est représentée de manière schématique à la figure 3, tandis que la figure 4 représente l'image IMD résultant de la décomposition de l'image IM, en dix sous-bandes selon trois niveaux de résolution, par le circuit 2. L'image IMD comporte autant d'information que l'image d'origine IM, mais l'information est fréquentiellement découpée selon trois niveaux de résolution.

Le niveau de plus basse résolution RES3 comporte les sous-bandes
LL3, HL3, LH3 et HH3, c'est-à-dire les sous-bandes de basse fréquence selon les deux directions d'analyse. Le second niveau de résolution RES2 comporte les sous-bandes HL2, LH2 et HH2 et le niveau de plus haute résolution RES comporte les sous-bandes de plus haute fréquence HL1, LH1 et HH1.

La sous-bande LL3 de plus basse fréquence est une réduction de l'image d'origine. Les autres sous-bandes sont des sous-bandes de détail.

Bien entendu, le nombre de niveaux de résolution, et par conséquent de sous-bandes, peut être choisi différemment, par exemple 13 sous-bandes et quatre niveaux de résolution, pour un signal bi-dimensionnel tel qu'une image. Le nombre de sous-bandes par niveau de résolution peut également être différent. Les circuits d'analyse et de synthèse sont adaptés à la dimension du signal traité.

La sous-bande LL3, de plus basse résolution RES3 est appliquée au circuit de codage 3 qui la code en une sous-bande codée, ou compressée,
LLc3.

Le circuit de codage 3 effectue un codage DPCM (Differential Pulse
Code Modulation, ou en Français, Modulation par Impulsion et Codage
Différentiel), qui est un codage par prédiction linéaire, avec perte. Chaque pixel de la sous-bande à coder LL3 est prédit en fonction de ses voisins, et cette prédiction est soustraite de la valeur du pixel considéré, dans le but de former une image différentielle qui présente moins de corrélation entre pixels que l'image originale. L'image différentielle est alors quantifiée et codée par un codage de Huffman pour former la sous-bande codée LLc3.

Selon d'autres modes de réalisation, le circuit de codage 3 effectue un codage par transformation discrète en cosinus (DCT), ou par quantification vectorielle, ou encore par codage fractal, ou par tout autre procédé de codage d'image fixe. Dans tous les cas, le codage de la sous-bande basse doit présenter une bonne qualité de codage, puisque la sous-bande basse doit être codée avec le plus de précision possible pour obtenir une bonne restitution de l'image au décodage.

Dans tous les cas, la sous-bande de plus basse fréquence est de préférence traitée à part. En effet, cette sous-bande contient une grande quantité d'information, et il est préférable de la coder avec le plus de précision possible, sans mise à zéro de bloc. Cependant, pour simplifier la mise en oeuvre, il est possible de coder la sous-bande de plus basse fréquence comme les sous-bandes de détail.

Les sous-bandes LH3, HL3 et HH3, ainsi que les sous-bandes de résolution supérieure HL2, LH2, HH2, HL1, LH1 et HH1 sont fournies au circuit de division 4, selon un ordre de sous-bande a priori quelconque, mais prédéterminé.

Comme représenté à la figure 5, le circuit de division 4 divise chaque sous-bande de détail en bloc. Selon le mode de réalisation choisi, toutes les sous-bandes fournies au circuit 4 sont divisées en un même nombre
N de blocs Bj n. OÙ l'indice i est un entier, ici entre 1 et 9, qui représente l'ordre de la sous-bande considérée et l'indice n, entre 1 et N, est un entier qui représente l'ordre du bloc dans la sous-bande considérée. Les blocs sont ici de forme carrée, mais peuvent être en variante de forme rectangulaire. De manière générale, un bloc est un ensemble de coefficients extraits de la sousbande pour former un vecteur.

L'ordre des blocs est a priori quelconque, mais prédéterminé. Pour des raisons pratiques, les blocs sont ordonnés de la même manière dans toutes les sous-bandes, par exemple de gauche à droite et de haut en bas.

En conséquence du mode de division en blocs, la surface des blocs est divisée par quatre en passant de la résolution RES1 à la résolution RES2, et de la résolution RES2 à la résolution RES3.

Cette division est simple à mettre en oeuvre, puisque toutes les sous-bandes sont divisées en un même nombre de blocs. Cependant, pour la mise en oeuvre de l'invention, le nombre et le format des blocs peuvent être différents d'une résolution à l'autre.

Le circuit de codage 5 code chaque bloc B. fourni par le circuit 4 selon le premier mode de codage. Ce mode consiste à mettre tous les coefficients du bloc à une valeur prédéterminée, par exemple la valeur zéro. Ce codage est très économique en nombre de bits, puisqu'il n'implique la transmission ou la mémorisation d'aucune donnée de codage, et par conséquent nécessite un débit de transmission nul. Cependant, I'erreur de codage risque d'être grande si le bloc considéré n'est pas d'énergie faible.

Le circuit de codage 6 code chaque bloc B. n fourni par le circuit 4 par un second mode de codage, ici par quantification scalaire uniforme de chacun des coefficients du bloc puis codage des indices issus de la quantification par un codage de Huffman.

En variante, les blocs peuvent être codé selon une autre méthode de codage, par exemple par quantification vectorielle, ou encore par quantification codée en treillis, qui sera décrite dans la suite. La méthode de codage utilisé doit être susceptible de coder avec précision un bloc contenant une quantité importante d'information.

Pour chacun des blocs, le circuit 7 compare les deux codages selon un critère pour sélectionner le codage le plus approprié, selon ce critère, pour chaque bloc considéré. A cette fin, le circuit 7 détermine les débits R1,i,n et R2,i,n nécessaires pour transmettre le bloc codé par chacun des deux circuits 5 et 6, ainsi que les erreurs de codage, ou distorsion, D1,i,n et D2 i n provoquées par le codage réalisé par chacun des deux circuits 5 et 6. Les erreurs D1 i,n et D2i n mesurent respectivement l'erreur quadratique apportée dans l'image reconstruite par le codage du bloc considéré, selon le premier et le second mode de codage. Dans le cas où la décomposition en sous-bande est orthogonale, les erreurs D1,i,n et D2,i,n sont égales aux erreurs quadratiques entre le bloc original et le bloc reconstruit.

Le circuit 7 compare ensuite, pour chacun des blocs, les sommes R1 i D 1,i,n et R2,j,n + k.D2,i,n, où # est un coefficient de réglage du rapport compression/distorsion. Le codage pour lequel la somme est la plus faible est sélectionné, pour chacun des blocs considérés.

Un indicateur l, est associé à chacun des blocs pour indiquer quel est le codage sélectionné par le circuit 7. L'indicateur Ii,n est par exemple un bit qui est mis à zéro si le bloc considéré est codé par mise à zéro, et qui est mis à un sinon. L'indicateur Ii,n fait partie de la forme codée du bloc considéré.

Les circuits 5, 6 et 7 effectuent ainsi une séparation de l'information pertinente et de l'information non pertinente. L'information non pertinente, c'està-dire les blocs à coder par mise à zéro, ont comme forme codée leur indicateur Ii,n. L'information pertinente, c'est-à-dire les autres blocs, vont ensuite être codés par les circuits 8, 9 et 10.

Le circuit 7 transmet au circuit de liaison 8 I'indicateur lin de chaque bloc codé. Le circuit de liaison 8 prend en compte les blocs qui ne sont pas codés par mise à zéro et lie ces blocs de manière à former une suite de blocs {Bm}, m étant un entier compris entre 1 et M, et M étant le nombre de blocs de la suite. Pour former la suite, les blocs sont par exemple considérés de gauche à droite et de haut en bas, dans chaque bande de fréquence, les bande de fréquence étant elles-mêmes considérées de gauche à droite et de haut en bas. Le circuit 8 fournit cette suite au circuit de codage 9.

En référence à la figure 6, le circuit 9 est un circuit de codage par quantification codée en treillis, dit TCQ, d'après l'Anglais Trellis Coded
Quantization. Le circuit 9 comporte un circuit 91 de codage selon l'algorithme de Viterbi, un registre à décalage 92, un circuit de sélection de dictionnaire 93 et des moyens de mémoire 94 pour mémoriser des dictionnaires de vecteurs de code.

Le codage par quantification codée en treillis est décrit par exemple dans l'article intitulé "Trellis Coded Quantization of Memoryless and Gauss
Markov Sources" de M.W. Marcellin et T.R. Fischer, paru dans IEEE
Transactions on Communications, Vol. 38, n" 1, Janvier 1990, ainsi que dans l'article "Universal Trellis Coded Quantization de J.H. Kasner, M.W. Marcellin et
B.R. Hunt, disponible par Internet à l'adresse http://vail .ece.arizona.edu/Pu blications. html.

De manière générale, le circuit de codage 9 code une suite de symboles (Sk) pour fournir deux flux binaires i(k) et j(k), où i(k) représente une suite de transitions et j(k) représente une suite d'indices des dictionnaires de vecteurs de code. Dans le contexte de l'invention, les symboles sk sont les coefficients extraits des blocs Bm, éventuellement quantifiés, fournis par le circuit 8.

Le fonctionnement du circuit 9 est celui d'une machine à états finis, le passage d'un état à un autre étant identifié par une transition. Dans un premier mode de réalisation, chaque état correspond à un dictionnaire et est identifié par les deux valeurs binaires i(k-2) et i(k-l).

Chacun des dictionnaires contient des vecteurs de code qui sont chacun identifiés par un indice dans le dictionnaire concerné. Un vecteur de code est par conséquent complètement identifié par son indice et par l'état représentant le dictionnaire auquel il appartient.

Les transitions possibles de la machine à états finis, pour la suite de symboles à coder, forment une structure régulière, ou treillis. Le circuit 91 met en oeuvre un algorithme de Viterbi pour déterminer un chemin optimal dans le treillis, c'est-à-dire un dictionnaire pour chacun des symboles sk de la suite à coder.

Le chemin est optimal au sens d'un coût qui est minimisé sur tout le treillis, donc sur toute la suite à coder. Le coût d'une transition est l'erreur quadratique mesurée entre le symbole à coder et le vecteur de code sélectionné dans le dictionnaire identifié par l'état dans lequel aboutit la transition. Le coût d'un état du treillis est la somme des coûts des transitions aboutissant à cet état. L'algorithme de Viterbi calcule le coût minimal de chaque état pour déterminer le chemin optimal représenté par la suite de transitions i(k).

Dans un second mode de réalisation, le nombre d'états est supérieur au nombre de dictionnaires. Par exemple, quatre dictionnaires et huit états sont utilisés. Le registre à décalage mémorise alors trois valeurs binaires pour définir les huit états. Chaque état est associé à deux dictionnaires.

Dans tous les cas, le circuit 9 fournit les deux flux binaires i(k) et j(k) au circuit de codage entropique 10 qui les combine et réalise un codage entropique.

Le circuit Il reçoit ainsi la sous-bande basse codée, les indices des blocs des sous-bandes de détail qui sont codés par mise à zéro, et les suites des indices et des transitions issus de la quantification codée en treillis.

En référence à la figure 7, le dispositif de décodage réalise globalement des opérations inverses de celles du dispositif de codage. Le dispositif de décodage est intégré dans un appareil 300, qui est par exemple un lecteur d'image numérique, ou de séquence vidéo numérique, ou un système de gestion de base de données, ou encore un ordinateur.

Un même appareil peut comporter à la fois le dispositif de codage et le dispositif de décodage selon l'invention, de manière à effectuer des opérations de codage et de décodage.

Le dispositif de décodage comporte une source de données codées 30 qui comporte par exemple un circuit de réception associé à une mémoire tampon.

Une première sortie 301 du circuit 30 est reliée à un circuit 31 de lecture d'indicateur IjXn dont une sortie 311 est reliée à un circuit de décodage 32.

Le circuit de décodage 32 a une sortie 321 reliée à un circuit de reconstruction 33. Ce dernier a une sortie 331 reliée à un circuit 34 d'exploitation des données décodées, comportant par exemple des moyens de visualisation d'image.

Le circuit 30 fournit des données codées au circuit 31, qui détermine le mode de codage utilisé pour chacun des blocs en analysant l'indicateur Ij n.

Si l'indicateur l, indique que le bloc considéré est codé par mise à zéro, son décoda

Le circuit de décodage 35 effectue des opérations inverses de celles du circuit de codage 3 et fournit la sous-bande décodée LLd3 au circuit de reconstruction 33.

Selon un mode préféré de réalisation de l'invention, les circuits de décomposition en sous-bandes 2, de codage 3, de division en bloc 4, de codage 5 et 6, de comparaison 7 de liaison 8, de codage 9 et 10 et de traitement 11, tous inclus dans le dispositif de codage représenté à la figure 1, sont réalisés par un microprocesseur associé à des mémoires vives et mortes.

La mémoire morte comporte un programme pour coder chacun des blocs de données, et la mémoire vive comporte des registres adaptés à enregistrer des variables modifiées au cours de l'exécution du programme.

De même, les circuits de lecture 31, de décodage 32 et 35, de reconstruction 33, inclus dans le dispositif de décodage représenté à la figure 7, sont réalisés par un second microprocesseur associé à des mémoires vives et mortes. La mémoire morte comporte un programme pour décoder chacun des blocs de données, et la mémoire vive comporte des registres adaptés à enregistrer des variables modifiées au cours de l'exécution du programme.

En référence à la figure 8, un procédé de codage selon l'invention d'une image IM, mis en oeuvre dans le dispositif de codage, comporte des étapes El à E17.

L'étape El est la décomposition en sous-bandes de l'image IM, comme représenté à la figure 4. L'étape El a pour résultat les sous-bandes
LL3, HL3, LH3 et HH3 de plus faible résolution RES3, les sous-bandes LH2, HL2,
HH2 de résolution intermédiaire RES2, et les sous-bandes LH1, HL1 et HH1 de plus haute résolution RES1.

La sous-bande LL3 est séparée des autres sous-bandes à l'étape suivante E2.

L'étape E3 code la sous-bande LL3 selon un codage DPCM (Differential Pulse Code Modulation) et a pour résultat la sous-bande codée LLC3 qui est mémorisée et/ou transmise.

L'étape E3 est suivie par l'étape E4 qui est la division des autres sous-bandes en blocs Bj,ns comme représenté à la figure 5.

L'étape suivante E5 est une initialisation pour considérer la première sous-bande. Les sous-bandes sont prises en compte selon un ordre a priori quelconque, tout en étant prédéterminé.

L'étape suivante E6 est une initialisation pour considérer le premier bloc de la sous-bande courante. Les blocs dans la sous-bande courante sont pris en compte selon un ordre quelconque et prédéterminé.

L'étape E6 est suivie par l'étape E7 qui est le codage par mise à une valeur prédéterminée, ici zéro, des coefficients du bloc courant B. L'étape suivante E8 est le codage par un second mode de codage, ici quantification scalaire, du bloc courant Bi,n. Le second mode de codage peut être une pluralité de modes de codage.

L'étape suivante E9 est la comparaison des deux modes de codage, pour le bloc courant, selon un critère prédéterminé. L'étape E9 détermine si le bloc courant Bi,n est à coder par mise à zéro ou par quantification codée en treillis.

A cette fin, les sommes R1,i,n + #.D1,i,n et R2,i,n + #.D2,i,n sont calculées, où R1,j,n et RP,i,n sont les débits nécessaires pour transmettre le bloc courant codé par les deux modes, D1 i n et D2 i n sont les distorsions provoquées dans le bloc courant par les deux modes de codage, et X est un coefficient de réglage du rapport compression/distorsion. Comme exposé plus haut, les erreurs D1 jan et D2,i,n mesurent respectivement l'erreur quadratique apportée dans l'image reconstruite par le codage du bloc considéré, selon le premier et le second mode de codage. Le codage pour lequel la somme est la plus faible est sélectionné, pour le bloc courant.

A l'étape suivante E10, un indicateur Ijn est associé au bloc courant pour indiquer quel est le codage sélectionné à l'étape E9. L'indicateur l, est par exemple un bit qui est mis à zéro si le bloc considéré est codé par mise à zéro, et qui est mis à un si le bloc considéré est à coder par quantification codée en treillis.

L'étape suivante El 1 est la mémorisation de la valeur de l'indicateur li,n.

Les étapes E12 et E14 sont des tests pour vérifier, respectivement si tous les blocs d'une sous-bande, et si toutes les sous-bandes ont été traités.

S'il reste au moins un bloc à traiter dans la sous-bande courante, l'étape E12 est suivie par l'étape E13 pour considérer le bloc suivant. L'étape E13 est suivie par l'étape E7 précédemment décrite.

S'il reste au moins une sous-bande à traiter, l'étape E14 est suivie par l'étape E15 pour considérer la sous-bande suivante. L'étape E15 est suivie par l'étape E6 précédemment décrite.

Lorsque toutes les sous-bandes ont été traitées, il a été déterminé quel mode de codage est affecté à chacun des blocs, l'étape E14 est suivie de l'étape E16 à laquelle les blocs qui ne sont pas à coder par mise à zéro sont liés. Les blocs sont par exemple considérés de gauche à droite et de haut en bas, dans chaque bande de fréquence, les bandes de fréquence étant ellesmêmes considérées de gauche à droite et de haut en bas. L'étape E16 a pour résultat une suite de blocs à coder {Bm} En variante, l'étape E16 est réalisée avant l'étape E14, c'est-à-dire qu'une suite est formée pour chaque sousbande, chaque suite étant alors traitée indépendamment des autres suites.

L'étape suivante E17 est le codage par quantification codée en treillis de la suite de blocs à coder. Le codage est effectué comme précédemment exposé (figure 6), et peut être suivi d'un codage entropique des suites binaires obtenues.

Le codage de l'image a ainsi pour résultat une sous-bande basse codée à part, des blocs codés par mise à zéro et des blocs liés puis codés par quantification codée en treillis. L'image codée peut être transmise et/ou mémorisée.

En référence à la figure 9, un procédé de décodage selon l'invention d'une image IM, mis en oeuvre dans le dispositif de décodage, comprend des étapes E20 à E30.

L'étape E20 est le décodage de la sous-bande basse LLC3 pour former une sous-bande basse décodée LLd3 qui est mémorisée.

L'étape suivante E21 est une initialisation pour considérer la première sous-bande de détail à décoder.

L'étape E21 est suivie de l'étape E22 qui est une initialisation pour considérer le premier bloc à décoder dans la sous-bande courante. Les sousbandes sont décodées dans un ordre prédéterminé, par exemple le même ordre qu'au codage, et les blocs dans une sous-bande donnée sont décodés dans un ordre prédéterminé, par exemple le même ordre qu'au codage, bien que des ordres différents soient possibles.

L'étape suivante E23 est la lecture de l'indicateur Ij n pour déterminer quel mode de codage a été utilisé pour coder le bloc courant.

L'étape E23 est suivie de l'étape E24 qui est le décodage du bloc courant. Si le bloc a été codé par mise à zéro, le décodage consiste à créer un bloc dont tous les coefficients sont à la valeur zéro. La taille du bloc créé dépend de la sous-bande en cours de décodage, et est par exemple déterminée par l'indice du bloc. Si le bloc a été codé par quantification codée en treillis, des opérations inverses de celles effectuées au codage sont effectuées. Les données de codage du bloc considéré sont extraites des suites d'indices et de transitions. Pour chaque symbole à décoder, la transition i(k) est lue pour déterminer un dictionnaire de vecteurs de code et l'indice j(k) est lu pour déterminer un vecteur de code dans ce dictionnaire. L'ensemble des symboles décodés forme un bloc décodé.

Le bloc décodé Bd1,n est mémorisé à l'étape suivante E25.

Les étapes E26 et E28 sont des tests pour vérifier, respectivement si tous les blocs d'une sous-bande, et si toutes les sous-bandes ont été décodées. S'il reste au moins un bloc à décoder dans la sous-bande courante,
L'étape E26 est suivie par l'étape E27 pour considérer le bloc suivant. L'étape
E27 est suivie par l'étape E23 précédemment décrite.

S'il reste au moins une sous-bande à décoder, l'étape E28 est suivie par l'étape E29 pour considérer la sous-bande suivante. L'étape E29 est suivie par l'étape E22 précédemment décrite.

Lorsque toutes les sous-bandes ont été décodées, c'est-à-dire que la réponse est positive à l'étape E28, cette dernière étape est suivie de l'étape
E30 de construction de l'image décodée. Cette dernière peut ensuite être visualisée, par exemple.

En variante, tous les blocs codés par mise à zéro sont décodés d'une part, et tous les blocs codés par quantification codée en treillis sont décodés d'autre part.

Bien entendu, la présente invention n'est nullement limitée aux modes de réalisation décrits et représentés, mais englobe, bien au contraire, toute variante à la portée de l'homme du métier.

En particulier, I'invention peut aisément être appliquée à d'autres types de signaux.

Ces signaux peuvent être des signaux mono-dimensionnels tel que des sons, ou des relevés sismiques, ou encore des électrocardiogrammes ; en fonction de leur nature, l'analyse des signaux est réalisée selon des fréquences temporelles ou spatiales.

Ces signaux peuvent être tri-dimensionnels tels que des séquences vidéo représentées selon deux fréquences spatiales et une fréquence temporelle. On met alors en oeuvre une décomposition en sous-bandes de fréquence en dimension trois, et la décomposition du signal en vecteurs s'effectue également en dimension trois.

Pour un signal ayant des composantes dans plusieurs bandes de fréquences, tel qu'un signal d'image en couleur ayant des composantes rouge, verte et bleue, l'invention s'applique dans chacune des bandes de fréquence.

Claims (26)

REVENDICATIONS

1. Procédé de codage de signal numérique comportant une étape d'analyse (El) du signal numérique (IM) en une pluralité de sous-bandes de fréquence réparties selon au moins deux bandes de fréquence différentes, au moins une première sous-bande ayant une fréquence plus faible et au moins une seconde sous-bande ayant une fréquence plus élevée,

caractérisé en ce qu'il comporte, pour chaque seconde sous-bande, les étapes de:

- division (E4) de la seconde sous-bande en blocs (Bj,),

- sélection (E9) de premiers blocs qui sont à coder par mise à une valeur prédéterminée et de seconds blocs qui sont à coder par quantification codée en treillis, selon un critère de sélection,

- liaison (ex6) des seconds blocs sélectionnés à l'étape précédente pour former une suite de blocs,

- codage (ex 7) de la suite de blocs par quantification codée en treillis d'une suite de coefficients extraits des seconds blocs de la seconde sousbande.

2. Procédé de codage selon la revendication 1, caractérisé en ce que les premiers blocs sélectionnés sont destinés à être décodés sous la forme de blocs dont tous les coefficients sont nuls.

3. Procédé de codage selon la revendication 1 ou 2, caractérisé en ce que, pour chacun des blocs, L'étape de sélection comporte:

- le codage (E7) du bloc (bon) par mise à la valeur prédéterminée et par un second mode de codage (E8),

- la comparaison (E9) des deux modes de codage selon le critère de sélection, et

- la sélection du codage par mise à la valeur prédéterminée si le bloc codé par mise à la valeur prédéterminée satisfait le critère de sélection.

4. Procédé de codage selon la revendication 3, caractérisé en ce que le second mode de codage est une quantification scalaire des coefficients du bloc (B1n).

5. Procédé de codage selon la revendication 3, caractérisé en ce que le second mode de codage est une quantification codée en treillis d'une suite de coefficients (sk) extraits des blocs de la seconde sous-bande.

6. Procédé de codage selon l'une quelconque des revendications 1 à 5, caractérisé en ce que le critère de sélection minimise une somme pondérée du débit et de l'erreur de codage provoqués par le codage du bloc considéré.

7. Procédé de codage selon l'une quelconque des revendications 1 à 6, caractérisé en ce qu'un indicateur (Ij n) est associé à chaque bloc (Bj,n) pour indiquer si le bloc considéré est codé par mise à la valeur prédéterminée ou non.

8. Procédé de codage selon l'une quelconque des revendications 1 à 7, caractérisé en ce que ladite au moins une première sous-bande est codée (E3) selon un troisième mode de codage.

9. Procédé de décodage de signal numérique codé, ledit signal comportant des représentations codées de blocs formés dans des sous-bandes de fréquence du signal d'origine, chaque représentation codée comportant au moins un indicateur (li,) représentatif d'un codage par mise à une valeur prédéterminée ou d'un codage par quantification codée en treillis d'une suite de coefficients extraits de blocs, caractérisé en ce qu'il comporte les étapes de:

- lecture (E23) de la valeur de l'indicateur de chacun des blocs,

- décodage (E24) des représentations par formation de blocs reconstruits dont tous les coefficients ont la valeur prédéterminée ou par déquantification codée en treillis de la suite de coefficients, en fonction de la valeur de l'indicateur respectif de chacun des blocs.

10. Procédé de décodage selon la revendication 9, caractérisé en ce que la valeur prédéterminée est nulle.

11. Dispositif de codage de signal numérique comportant des moyens d'analyse du signal numérique (IM) en une pluralité de sous-bandes de fréquence réparties selon au moins deux bandes de fréquence différentes, au moins une première sous-bande ayant une fréquence plus faible et au moins une seconde sous-bande ayant une fréquence plus élevée,

caractérisé en ce qu'il comporte:

- des moyens (4) de division de chaque seconde sous-bande en blocs (Bi,n)

- des moyens (5, 6, 7) de sélection de premiers blocs qui sont à coder par mise à une valeur prédéterminée et de seconds blocs qui sont à coder par quantification codée en treillis, selon un critère de sélection,

- des moyens (8) de liaison des seconds blocs sélectionnés à l'étape précédente pour former une suite de blocs,

- des moyens (9) de codage de la suite de blocs par quantification codée en treillis d'une suite de coefficients extraits des seconds blocs de la seconde sous-bande.

12. Dispositif de codage selon la revendication 11, caractérisé en ce que les premiers blocs sélectionnés sont destinés à être décodés sous la forme de blocs dont tous les coefficients sont nuls.

13. Dispositif de codage selon la revendication Il ou 12, caractérisé en ce que, pour chacun des blocs, les moyens de sélection (5, 6, 7) sont adaptés à coder le bloc (Bjn) par mise à la valeur prédéterminée et par un second mode de codage, à comparer les deux modes de codage selon le critère de sélection et à sélectionner le codage par mise à la valeur prédéterminée si le bloc codé par mise à la valeur prédéterminée satisfait le critère de sélection.

14. Dispositif de codage selon la revendication 13, caractérisé en ce que les moyens de sélection sont adaptés à appliquer (6) un second mode de codage qui est une quantification scalaire des coefficients du bloc.

15. Dispositif de codage selon la revendication 13, caractérisé en ce que les moyens de sélection sont adaptés à appliquer (6) un second mode de codage qui est une quantification codée en treillis d'une suite de coefficients extraits des blocs de la seconde sous-bande.

16. Dispositif de codage selon l'une quelconque des revendications Il à 15, caractérisé en ce que les moyens de sélection sont adaptés à appliquer (7) un critère de sélection qui minimise une somme pondérée du débit et de l'erreur de codage provoqués par le codage du bloc considéré.

17. Dispositif de codage selon l'une quelconque des revendications 11 à 16, caractérisé en ce qu'il est adapté à associer un indicateur (Ijn) à chaque bloc (Bjn) pour indiquer si le bloc considéré est codé par mise à la valeur prédéterminée ou non.

18. Dispositif de codage selon l'une quelconque des revendications 11 à 17, caractérisé en ce qu'il comporte des moyens (3) de codage de ladite au moins une première sous-bande selon un troisième mode de codage.

19. Dispositif de codage selon l'une quelconque des revendications Il à 18, caractérisé en ce que les moyens de division (4), de sélection (5, 6, 7), de liaison (8) et de codage (9) sont incorporés dans:

- un micro-processeur,

- une mémoire morte comportant un programme de codage, et

- une mémoire vive comportant des registres adaptés à enregistrer des variables modifiées au cours de l'exécution dudit programme.

20. Dispositif de décodage de signal numérique codé, ledit signal comportant des représentations codées de blocs formés dans des sous-bandes de fréquence du signal d'origine, chaque représentation codée comportant au moins un indicateur (ion) représentatif d'un codage par mise à une valeur prédéterminée ou d'un codage par quantification codée en treillis d'une suite de coefficients extraits de blocs, caractérisé en ce qu'il comporte:

- des moyens de lecture (31) de la valeur de l'indicateur de chacun des blocs,

- des moyens de décodage (32) des représentations par formation de blocs reconstruits dont tous les coefficients ont la valeur prédéterminée ou par déquantification codée en treillis de la suite de coefficients, en fonction de la valeur de l'indicateur respectif de chacun des blocs.

21. Dispositif de décodage selon la revendication 20, caractérisé en ce qu'il est adapté à former des blocs dont tous les coefficients ont la valeur prédéterminée nulle.

22. Dispositif de décodage selon l'une quelconque des revendications 20 à 21, caractérisé en ce que les moyens de lecture (31) et les moyens de décodage (32) sont incorporés dans:

- un micro-processeur,

- une mémoire morte comportant un programme de décodage, et

- une mémoire vive comportant des registres adaptés à enregistrer des variables modifiées au cours de l'exécution dudit programme.

23. Appareil (100) de traitement de signal numérique, caractérisé en ce qu'il comporte des moyens adaptés à mettre en oeuvre le procédé de codage selon l'une quelconque des revendications 1 à 8.

24. Appareil (300) de traitement de signal numérique, caractérisé en ce qu'il comporte des moyens adaptés à mettre en oeuvre le procédé de décodage selon l'une quelconque des revendications 9 à 10.

25. Appareil (100) de traitement de signal numérique, caractérisé en ce qu'il comporte le dispositif de codage selon l'une quelconque des revendications Il à 19.

26. Appareil (300) de traitement de signal numérique, caractérisé en ce qu'il comporte le dispositif de décodage selon l'une quelconque des revendications 20 à 22.