FR2834855A1 - Codage de donnees numeriques avec determination de parcours d'echantillons - Google Patents

Abstract

L'invention concerne un procédé de codage d'échantillons numériques d'un ensemble de données représentatives de grandeurs physiques, le codage incluant la détermination (E51) d'un parcours parmi les échantillons de l'ensemble, caractérisé en ce qu'il comporte les étapes de : - mesure (E54) d'un coût de codage qui dépend du parcours, - modification (E55, E57) du parcours, les étapes de mesure et modification étant réitérées de manière à déterminer un parcours qui minimise le coût de codage.

Description

<Desc/Clms Page number 1>

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.

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. Les signaux numériques considérés ici sont de nature quelconque, par exemple des images fixes, de la vidéo, du son, des données informatiques.

Dans la suite, on considère plus particulièrement le codage et le décodage d'une image fixe.

Dans ce contexte, certains modes de codage utilisent un parcours établi parmi un ensemble d'échantillons numériques. Par exemple, les demandes de brevet français n 01 06933 et 01 13922 concernent de tels modes de codage.

Pour que le codage soit efficace, c'est-à-dire qu'il présente un bon rapport débit-distorsion, il est nécessaire de déterminer le parcours de manière adaptée.

Il existe des techniques pour déterminer un parcours parmi un ensemble d'échantillons. Ces techniques sont connues sous le nom de techniques de résolution du problème du voyageur de commerce. Une revue

<Desc/Clms Page number 2>

de ces techniques est par exemple exposée dans l'ouvrage de Gerhard Reinelt intitulé The traveling salesman, computational solutions for TSP applications , Springer-Verlag, 1994.

Cependant, l'inventeur a constaté que ces techniques ne donnent pas un bon résultat si elles sont appliquées directement au problème du codage de données. En effet, la distance entre deux points du parcours s'exprime ici par un coût de codage qui dépend notamment du débit associé au vecteur liant les deux points. Hors ce débit dépend à son tour des vecteurs déjà choisis dans le parcours puisque ce sont ces derniers qui déterminent la statistique à partir de laquelle le débit de chaque vecteur est calculé.

En conséquence, l'insertion d'un point dans le parcours modifie toutes les distances entre points.

La présente invention vise à remédier aux inconvénients de la technique antérieure, en fournissant un procédé et un dispositif de codage d'échantillons numériques qui incluse la détermination d'un parcours parmi les échantillons de l'ensemble, qui permettent d'obtenir un bon rapport débitdistorsion.

A cette fin, l'invention propose un procédé de codage d'échantillons numériques d'un ensemble de données représentatives de grandeurs physiques, le codage incluant la détermination d'un parcours parmi les échantillons de l'ensemble, caractérisé en ce qu'il comporte les étapes de : - mesure d'un coût de codage qui dépend du parcours, - modification du parcours, les étapes de mesure et modification étant réitérées de manière à déterminer un parcours qui minimise le coût de codage.

Corrélativement, l'invention concerne un dispositif de codage d'échantillons numériques d'un ensemble de données représentatives de grandeurs physiques, le codage incluant la détermination d'un parcours parmi les échantillons de l'ensemble, caractérisé en ce qu'il comporte :

<Desc/Clms Page number 3>

- des moyens de mesure d'un coût de codage qui dépend du parcours, - des moyens de modification du parcours, les moyens de mesure et modification étant adaptés à réitérer leur fonctionnement de manière à déterminer un parcours qui minimise le coût de codage.

L'invention propose donc une technique itérative pour déterminer un parcours qui minimise un coût de codage, offrant ainsi un bon compromis débitdistorsion.

Selon une caractéristique préférée, la mesure du coût de codage comporte le calcul de la distorsion générée par le codage de chaque échantillon en fonction du parcours.

La distorsion est simple à calculer. Le coût de codage tient ainsi compte de la distorsion liée au codage.

Selon une caractéristique préférée, la mesure du coût de codage comporte le calcul du débit utilisé pour coder chaque échantillon en fonction du parcours.

Le coût de codage tient ainsi compte du débit nécessaire pour représenter les données codées.

Lorsque les deux caractéristiques précédentes sont combinées, le coût de codage tient compte à la fois du débit et de la distorsion, ce qui permet un réglage optimal du parcours de manière à minimiser un rapport débitdistorsion.

Selon une caractéristique préférée, la mise à jour du débit est effectuée toutes les N itérations, avec N un entier supérieur ou égal à deux.

Ainsi, les temps de calcul sont raccourcis.

Selon des caractéristiques préférées, la modification comporte : - le retrait du dernier échantillon du parcours, - l'ajout d'un échantillon n'appartenant pas au parcours à la fin du parcours, - la modification comporte l'échange de place de deux échantillons du parcours.

<Desc/Clms Page number 4>

Ces modifications permettent de trouver un parcours optimal, au cours des itérations.

Selon une caractéristique préférée, le calcul de la distorsion comporte le calcul de la différence entre la valeur de chaque échantillon et sa valeur de décodage respective.

Selon une caractéristique préférée, le calcul du débit comporte le calcul du nombre d'occurrences du vecteur décrivant l'emplacement de chaque échantillon par rapport à l'échantillon précédent dans le parcours.

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

Le dispositif de codage présente des avantages analogues à ceux précédemment présentés.

L'invention concerne aussi un appareil numérique incluant le dispositif selon l'invention, ou des moyens de mise en oeuvre du procédé selon l'invention. Cet appareil numérique est par exemple un appareil photographique numérique, un caméscope numérique, un scanner, une imprimante, un photocopieur, un télécopieur. Les avantages du dispositif et de l'appareil numérique sont identiques à ceux précédemment exposés.

Un moyen de stockage d'information, lisible par un ordinateur ou par un microprocesseur, intégré ou non au dispositif, éventuellement amovible, mémorise un programme mettant en oeuvre le procédé selon l'invention.

Un programme d'ordinateur lisible par un microprocesseur et comportant une ou plusieurs séquence d'instructions est apte à mettre en oeuvre les procédés 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 est un mode de réalisation d'un dispositif mettant en oeuvre l'invention, - la figure 2 représente un dispositif de codage selon l'invention et un dispositif de décodage correspondant,

<Desc/Clms Page number 5>

- la figure 3 est un mode de réalisation de procédé de codage selon l'invention, -la figure 4 est un mode de réalisation de procédé de codage d'emplacement inclus dans le procédé de la figure 3, - la figure 5 représente un circuit de décomposition en sous bandes de fréquence inclus dans le dispositif de codage selon l'invention, - la figure 6 est une image numérique à coder selon la présente invention, -la figure 7 est une image décomposée en sous-bandes selon la présente invention, - la figure 8 représente un modèle d'amplitude utilisé selon la présente invention.

Selon le mode de réalisation choisi et représenté à la figure 1, un dispositif mettant en oeuvre l'invention est par exemple un micro-ordinateur 10 connecté à différents périphériques, par exemple une caméra numérique 107 (ou un scanner, ou tout moyen d'acquisition ou de stockage d'image) reliée à une carte graphique et fournissant des informations à traiter selon l'invention.

Le dispositif 10 comporte une interface de communication 112 reliée à un réseau 113 apte à transmettre des données numériques à traiter ou inversement à transmettre des données traitées par le dispositif. Le dispositif 10 comporte également un moyen de stockage 108 tel que par exemple un disque dur. Il comporte aussi un lecteur 109 de disque 110. Ce disque 110 peut être une disquette, un CD-ROM, ou un DVD-ROM, par exemple. Le disque 110 comme le disque 108 peuvent contenir des données traitées selon l'invention ainsi que le ou les programmes mettant en oeuvre l'invention qui, une fois lu par le dispositif 10, sera stocké dans le disque dur 108. Selon une variante, le programme permettant au dispositif de mettre en oeuvre l'invention, pourra être stocké en mémoire morte 102 (appelée ROM sur le dessin). En seconde variante, le programme pourra être reçu pour être stocké de façon identique à celle décrite précédemment par l'intermédiaire du réseau de communication 113.

<Desc/Clms Page number 6>

Le dispositif 10 est relié à un microphone 111. Les données à traiter selon l'invention seront dans ce cas du signal audio.

Ce même dispositif possède un écran 104 permettant de visualiser les données à traiter ou de servir d'interface avec l'utilisateur qui peut ainsi paramétrer certains modes de traitement, à l'aide du clavier 114 ou de tout autre moyen (souris par exemple).

L'unité centrale 100 (appelée CPU sur le dessin) exécute les instructions relatives à la mise en oeuvre de l'invention, instructions stockées dans la mémoire morte 102 ou dans les autres éléments de stockage. Lors de la mise sous tension, les programmes de traitement stockés dans une mémoire non volatile, par exemple la ROM 102, sont transférés dans la mémoire vive RAM 103 qui contiendra alors le code exécutable de l'invention ainsi que des registres pour mémoriser les variables nécessaires à la mise en oeuvre de l'invention.

De manière plus générale, un moyen de stockage d'information, lisible par un ordinateur ou par un microprocesseur, intégré ou non au dispositif, éventuellement amovible, mémorise un programme mettant en oeuvre le procédé selon l'invention.

Le bus de communication 101 permet la communication entre les différents éléments inclus dans le micro-ordinateur 10 ou reliés à lui. La représentation du bus 101 n'est pas limitative et notamment l'unité centrale 100 est susceptible de communiquer des instructions à tout élément du microordinateur 10 directement ou par l'intermédiaire d'un autre élément du microordinateur 10.

En référence à la figure 2, un mode de réalisation de dispositif de codage 3 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, qui est par exemple un appareil photographique numérique, un caméscope numérique, un scanner, une imprimante, un photocopieur, un télécopieur, un système de gestion de base de données, ou encore un ordinateur.

<Desc/Clms Page number 7>

Une source d'image 1 fournit une image numérique au dispositif de codage 2, dont le fonctionnement sera détaillé dans la suite. Le codage inclut la détermination d'un parcours parmi les échantillons de l'ensemble.

Le dispositif de codage comporte : - des moyens 21 de transformation de données, - des moyens 22 de calcul d'un modèle d'amplitude, - des moyens 23 de détermination d'un parcours parmi les données transformées.

Selon l'invention, le dispositif de codage comporte : - des moyens 24 de mesure d'un coût de codage qui dépend du parcours, - des moyens 25 de modification du parcours, les moyens de mesure et modification étant adaptés à réitérer leur fonctionnement de manière à déterminer un parcours qui minimise le coût de codage.

Le dispositif de codage fournit un fichier contenant des données représentant l'image compressée à des moyens de transmission et/ou de mémorisation 3. Ces moyens sont classiques et ne seront pas décrits ici.

Les moyens 3 sont reliés à un dispositif de décodage 4 dont le fonctionnement sera détaillé dans la suite.

Il est à noter que le dispositif de codage et le dispositif de décodage peuvent être intégrés dans un même appareil, par exemple l'ordinateur 10 de la figure 1.

La figure 3 représente un mode de réalisation de procédé de codage d'une image, selon l'invention. Ce procédé est mis en oeuvre dans le dispositif de codage et comporte des étapes E 1 à E7.

Le procédé comporte globalement une transformation du signal à coder, puis la détermination d'un modèle d'amplitude des coefficients issus de la transformation. Les emplacements de ces coefficients sont ensuite codés selon une méthode qui utilise un parcours établi parmi les coefficients.

<Desc/Clms Page number 8>

Un tel procédé de codage est décrit par exemple dans la demande de brevet français n 01 06933 déposée par la demanderesse.

Le procédé est réalisé sous la forme d'un algorithme qui peut être mémorisé en totalité ou en partie dans tout moyen de stockage d'information capable de coopérer avec le microprocesseur. Ce moyen de stockage est lisible par un ordinateur ou par un microprocesseur. Ce moyen de stockage est intégré ou non au dispositif, et peut être amovible. Par exemple, il peut comporter une bande magnétique, une disquette ou un CD-ROM (disque compact à mémoire figée).

L'étape E1 est une transformation linéaire ou non linéaire d'une image numérique IM à traiter selon l'invention. L'image a par exemple une taille de 512 x 512 pixels.

Dans le mode préféré de réalisation de l'invention, la transformation est une décomposition en sous-bandes de fréquences.

Le signal est décomposé en sous-bandes de fréquence à plusieurs niveaux de résolution par une transformation en odelettes discrètes dite DWT (d'après l'anglais Discrete Wavelet Transform) à M niveaux de résolution.

Dans la suite, sont décrits en référence aux figures 5 à 7, un circuit de décomposition en sous-bandes de fréquence, ainsi qu'une image traitée par ce circuit.

Il est à noter que la sous-bande basse peut être codée selon le procédé décrit ci-après ou de façon classique par prédiction linéaire.

D'autres types de transformation peuvent être utilisés, par exemple la transformation en cosinus discrète dite DCT ou la transformation de Fourier ou encore une transformation non-linéaire comme une transformation morphologique.

L'étape suivante E2 est la sélection d'une première sous-bande résultant de la décomposition précédente. Les sous-bandes sont considérées une par une.

L'étape suivante E3 est un classement des coefficients de la sousbande courante. Le signe des coefficients est tout d'abord codé de manière

<Desc/Clms Page number 9>

indépendante. Les coefficients sont ensuite considérés en valeur absolue et sont classés du plus grand au plus petit.

L'étape suivante E4 est la détermination d'une fonction d'approximation de la suite des coefficients classés. Cette fonction est par exemple une exponentielle décroissante définie par un jeu de paramètres qui sont déterminés par régression.

La figure 8 représente un exemple de modèle d'amplitude A. A chaque valeur entière k en abscisse correspond une valeur A (k) fournie par le modèle d'amplitude. La valeur A (k) est une approximation de l'amplitude du kème coefficient classé par ordre décroissant.

L'étape suivante E5 est le codage des emplacements des coefficients. Cette étape comporte la détermination d'un parcours parmi les coefficients de la sous-bande courante de sorte que le coût de codage de ce parcours soit minimal. Le parcours comporte un coefficient initial et la liste des vecteurs joignant les autres coefficients. Chaque coefficient du parcours différent du coefficient initial est représenté par un vecteur décrivant son emplacement par rapport au coefficient précédent dans le parcours. Il est à noter que le parcours ne passe pas forcement par tous les coefficients de la sous-bande courante. En effet, il est possible de ne coder qu'une partie des coefficients et de mettre les autres coefficients à la valeur zéro lors du décodage ultérieur.

Une fois le parcours déterminé, les coordonnées du coefficient initial sont codées par un codage binaire et les vecteurs sont codés par un codage entropique.

L'étape E5 est détaillée dans la suite.

La forme codée d'une sous-bande de l'image comporte un modèle d'amplitude qui fournit une approximation de l'amplitude des coefficients et un parcours qui fournit une suite ordonnée des emplacements des coefficients. L'emplacement du kème coefficient de cette suite est déterminé par le parcours et son amplitude est déterminée par l'ordonnée correspondant à l'abscisse k selon le modèle d'amplitude.

<Desc/Clms Page number 10>

L'étape suivante E6 est un test pour déterminer si la sous-bande courante est la dernière sous-bande de l'image à coder.

Si la réponse est négative, cette étape est suivie de l'étape E7 à laquelle une sous-bande suivante est considérée. L'étape E7 est suivie de l'étape E3 précédemment décrite.

Si la réponse est positive à l'étape E6, alors le codage de l'image est terminé.

La figure 4 représente un mode de réalisation de l'étape E5 de codage des emplacements des coefficients. Ce codage comporte des étapes E51 à E60.

Ce codage comporte globalement la détermination d'un parcours parmi les coefficients et le codage des coefficients en fonction du parcours. Un parcours comporte un coefficient de la sous-bande, dit coefficient initial, et une liste de vecteurs joignant au moins une partie des autres coefficients.

Le parcours est déterminé itérativement, de manière à minimiser un coût de codage. Le coût de codage représente un compromis entre débit et distorsion. Le coût de codage d'un signal S est ici la fonction C (S) = R (S) + Â. D (S), dans laquelle R (S) représente le débit de transmission de la forme codée du signal S, D (S) représente la distorsion générée dans le signal reconstruit après codage et décodage, par rapport au signal d'origine et  est un paramètre de réglage entre compression et distorsion.

Il est à noter que la minimisation de la fonction C (S) sur le signal S est équivalente à la minimisation de la fonction C (S) sur chaque élément d'une partition du signal, en particulier sur chaque échantillon du signal. Cela est du au fait que la distorsion et le débit sont respectivement additifs.

L'étape E51 est la détermination d'un parcours initial Po dans la sous-bande de fréquence courante.

Le parcours initial peut être déterminé aléatoirement. Il peut également être choisi en minimisant uniquement la distorsion D. Dans ce cas, l'ordre des coefficients est celui du modèle d'amplitude, c'est-à-dire du plus grand au plus petit.

<Desc/Clms Page number 11>

Il est encore possible de choisir les M premiers coefficients dans l'ordre du modèle d'amplitude, avec M un entier inférieur au nombre de coefficients de la sous-bande courante, de manière à limiter le débit.

L'étape suivante E52 est le calcul de la table TRo comportant le débit de codage de chaque coefficient lorsque le parcours est le parcours initial Po.

Pour cela, il faut calculer le débit de trois types de coefficients.

Tout d'abord, le débit de codage du coefficient initial est égal au nombre de bits utilisés pour coder son emplacement.

Le débit de codage des coefficients qui n'appartiennent pas au parcours est nul.

Le débit de codage des autres coefficients, c'est-à-dire les coefficients appartenant au parcours et différents du coefficient initial, est calculé de la manière suivante.

On rappelle que chaque coefficient du parcours est représenté par un vecteur décrivant son emplacement par rapport au coefficient précédent dans le parcours.

L'histogramme H de tous les vecteurs possibles dans la sous-bande est calculé. L'histogramme est un tableau comportant le nombre d'occurrences de chaque vecteur dans le parcours. Les vecteurs qui appartiennent au parcours ont un nombre d'occurrence non nul, tandis que les autres vecteurs ont un nombre d'occurrence nul.

L'histogramme est ensuite modifié de sorte que les vecteurs qui ont un nombre d'occurrence nul reçoivent un nombre d'occurrence modifié non nul.

En effet, le débit associé à chaque vecteur V est calculé à partir de l'histogramme, selon la formule suivante : R (V) =-log2 (occ (V)/occt) Où occt est le nombre total d'occurrences dans l'histogramme et occ (V) est le nombre d'occurrences du vecteur V.

Si le vecteur V a un nombre d'occurrence nul, son débit, et par conséquent son coût de codage sont infinis. Comme il va être exposé dans la suite, des itérations ultérieures ont pour but de modifier le parcours en

<Desc/Clms Page number 12>

sélectionnant les vecteurs ayant le coût de codage le plus faible. Le vecteur V ayant un coût infini ne pourra jamais être sélectionné.

Afin de ne pas éliminer a priori de tels vecteurs, les nombres d'occurrences nuls de l'histogramme sont remplacés par des valeurs non nulles. Ces valeurs modifiées restent toutefois faibles par rapport aux autres valeurs de l'histogramme, de manière à refléter le fait que ces vecteurs n'ont pas été utilisés dans le parcours.

La modification de l'histogramme H est la suivante :
H1 = H + b
Où b est un nombre non nul, choisi pour que le coût des vecteurs non encore utilisés ne soit pas trop élevé de manière à avoir des chances d'être utilisés dans le parcours. On choisit par exemple b= 0.02.

L'étape suivante E53 est le calcul de la table TDo comportant la distorsion générée par le codage de chaque coefficient lorsque le parcours est le parcours initial Po.

Pour cela, il faut calculer la distorsion de deux types de coefficients.

Tout d'abord, pour un coefficient appartenant au parcours et situé en kème position sur celui-ci, la distorsion est égale à la différence entre la valeur du coefficient et la valeur A (k) donnée par le modèle d'amplitude.

Pour un coefficient n'appartenant pas au parcours Po, la distorsion est égale à la différence entre la valeur du coefficient et zéro.

L'étape suivante E54 est une évaluation de modificateurs du parcours courant Pi, avec i entier.

Pour cela, des modificateurs sont appliqués au parcours et pour chacun d'eux l'incidence sur le coût global est mesurée.

Les modificateurs utilisés sont ici les suivants : - le dernier coefficient du parcours est retiré. Le débit de codage de ce coefficient devient nul et sa distorsion devient égale à la différence entre la valeur du coefficient et zéro.

- un coefficient n'appartenant pas au parcours est ajouté à la fin de celui-ci. Il y a autant de modificateurs de ce type que de coefficients n'appartenant pas au parcours. Pour chaque modificateur, le débit du

<Desc/Clms Page number 13>

coefficient ajouté est lu dans la table des débits TRi et sa distorsion devient égale à la différence entre la valeur du coefficient et la valeur donnée par le modèle d'amplitude.

- deux coefficients du parcours sont interchangés. Il y a autant de modificateurs de ce type que de paires de coefficients dans le parcours. Pour chaque modificateur, les vecteurs commençant et aboutissant aux deux coefficients échangés, soit quatre vecteurs, sont modifiés. Les débits liés à ces quatre vecteurs sont lus dans la table des débits TR,. Les distorsions des deux coefficients échangés deviennent respectivement égales à la différence entre la valeur du coefficient et la valeur donnée par le modèle d'amplitude.

L'étape suivante E55 est un test pour déterminer si l'un des modificateurs appliqués au parcours courant fournit un parcours modifié ayant un coût de codage inférieur à celui du parcours courant.

Si la réponse est négative, cela signifie que le parcours courant est le meilleur au sens de la minimisation du coût de codage. L'étape E55 est alors suivie de l'étape E56 de codage des emplacements des coefficients.

Si la réponse est positive à l'étape E55, cela signifie que l'un des parcours modifiés est meilleur que le parcours courant au sens de la minimisation du coût de codage. Si plusieurs parcours modifié sont meilleurs que le parcours courant, alors celui qui a le coût de codage le plus faible est considéré. L'étape E55 est alors suivie de l'étape E57 à laquelle le parcours P, +, qui a le coût de codage le plus faible devient le parcours courant.

A l'étape suivante E58, la table des distorsions Tu, +1 est mise à jour pour le nouveau parcours courant. Cette mise à jour est simple, puisque, comme exposé plus haut, la modification a impliqué un ou deux coefficients. Il suffit de calculer la distorsion du ou des coefficients impliqués.

L'étape suivante E59 est un test sur le nombre d'itérations effectuées. On choisit de remettre à jour la table des débits seulement toutes les N itérations, où N est un entier déterminé en fonction du nombre de coefficients dans la sous-bande courante. Par exemple, l'entier N est égal à environ 5 % du nombre de coefficients dans la sous-bande courante. En effet, un changement de coefficient du parcours provoque un changement de

<Desc/Clms Page number 14>

l'histogramme des vecteurs et par conséquent un changement de tous les débits des vecteurs. On fait l'hypothèse que le modificateur appliqué n'a qu'une influence faible sur les débits.

Lorsque N itérations n'ont pas été effectuées depuis la mise à jour précédente de la table des débits, l'étape E59 est suivie de l'étape E54 précédemment décrite. Le parcours qui est alors considéré n'a eu que la table de distorsion mise à jour.

Toutes les N itérations, la table des débits Tir, +1 est mise à jour. Pour cela, l'étape E59 est alors suivie de l'étape E60. A cette étape, tous les débits correspondant à l'histogramme modifié sont calculés. Le calcul est similaire à celui de l'étape E52, avec le parcours courant. Le calcul inclut le calcul d'un histogramme et la modification de celui-ci, comme exposé précédemment.

En variante, il est possible de faire diminuer la valeur au fur et à mesure des itérations, de manière à être de plus en plus sélectif. Par exemple, on choisit : b = 0.001 + 0. 0199. e' ' de manière à avoir b = 0.02 à la première itération et à tendre asymptotiquement vers b = 0.001 au cours des itérations suivantes.

L'étape E60 est suivie de l'étape E54 précédemment décrite.

Ainsi, la détermination du parcours ayant le coût de codage le plus faible est effectuée par itération des étapes E54 à E60.

Le décodage de l'image codée est effectué comme exposé dans la demande de brevet français n 01 06933.

Le modèle d'amplitude est lu et décodé, pour fournir les amplitudes des coefficients. Le parcours est lu et décodé pour fournir les emplacements des coefficients. L'ordre de chaque coefficient dans le parcours détermine son amplitude, puisque le kème coefficient reçoit l'amplitude A (k) correspondant à l'abscisse k.

Les coefficients qui ne font pas partie du parcours sont mis à zéro.
Selon la figure 5, le circuit 21 comporte trois blocs successifs d'analyse pour décomposer l'image IM en des sous-bandes selon trois niveaux de résolution.

<Desc/Clms Page number 15>

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 pour représenter cette sous-bande. La résolution dépend notamment du nombre de décimations effectuées.

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 210 et 220 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 2100 et 2200, les signaux filtrés résultant sont respectivement appliqués à deux filtres passe-bas 230 et 250, et passe-haut 240 et 260, 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 2300,2400, 2500 et 2600. 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 une image construite à partir de l'image d'origine, qui contient de l'information correspondant à une orientation respectivement verticale, horizontale et diagonale de l'image, dans une bande de fréquence donnée.

La sous-bande LL1 est analysée par un bloc d'analyse analogue au précédent pour fournir quatre sous-bandes LLs, LH2, HL2 et HH2 de niveau de résolution RESz intermédiaire dans la décomposition. La sous-bande LL2 comporte les composantes de basse fréquence selon les deux directions

<Desc/Clms Page number 16>

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 21 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 6, tandis que la figure 7

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 21. 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 RES1 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é.

<Desc/Clms Page number 17>

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.

L'invention s'applique à tout mode de codage incluant le calcul d'un parcours parmi des échantillons à coder. En particulier, elle s'applique au procédé de codage décrit dans la demande de brevet français n 01 03922.

Claims (21)

REVENDICATIONS

1. Procédé de codage d'échantillons numériques d'un ensemble de données représentatives de grandeurs physiques, le codage incluant la détermination (E51) d'un parcours parmi les échantillons de l'ensemble, caractérisé en ce qu'il comporte les étapes de : - mesure (E54) d'un coût de codage qui dépend du parcours, - modification (E55, E57) du parcours, les étapes de mesure et modification étant réitérées de manière à déterminer un parcours qui minimise le coût de codage.

2. Procédé selon la revendication 1, caractérisé en ce que la mesure du coût de codage comporte le calcul (E53, E58) de la distorsion générée par le codage de chaque échantillon en fonction du parcours.

3. Procédé selon la revendication 1 ou 2, caractérisé en ce que la mesure du coût de codage comporte le calcul (E52, E60) du débit utilisé pour coder chaque échantillon en fonction du parcours.

4. Procédé selon la revendication 3, caractérisé en ce que la mise à jour du débit (E60) est effectuée toutes les N itérations, avec N un entier supérieur ou égal à deux.

5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que la modification (E54) comporte le retrait du dernier échantillon du parcours.

6. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que la modification (E54) comporte l'ajout d'un échantillon n'appartenant pas au parcours à la fin du parcours.

<Desc/Clms Page number 19>

7. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que la modification (E54) comporte l'échange de place de deux échantillons du parcours.

8. Procédé selon l'une quelconque des revendications 2 à 7, caractérisé en ce que le calcul de la distorsion (E53, E58) comporte le calcul de la différence entre la valeur de chaque échantillon et sa valeur de décodage respective.

9. Procédé selon l'une quelconque des revendications 3 à 8, caractérisé en ce que le calcul du débit (E52, E60) comporte le calcul du nombre d'occurrences du vecteur décrivant l'emplacement de chaque échantillon par rapport à l'échantillon précédent dans le parcours.

10. Dispositif de codage d'échantillons numériques d'un ensemble de données représentatives de grandeurs physiques, le codage incluant la détermination d'un parcours parmi les échantillons de l'ensemble, caractérisé en ce qu'il comporte : - des moyens (24) de mesure d'un coût de codage qui dépend du parcours, - des moyens (25) de modification du parcours, les moyens de mesure et modification étant adaptés à réitérer leur fonctionnement de manière à déterminer un parcours qui minimise le coût de codage.

11. Dispositif selon la revendication 10, caractérisé en ce que les moyens (24) de mesure du coût de codage comporte des moyens de calcul de la distorsion générée par le codage de chaque échantillon en fonction du parcours.

<Desc/Clms Page number 20>

12. Dispositif selon la revendication 10 ou 11, caractérisé en ce que les moyens (24) de mesure du coût de codage comporte des moyens de calcul du débit utilisé pour coder chaque échantillon en fonction du parcours.

13. Dispositif selon la revendication 12, caractérisé en ce qu'il est adapté à mettre à jour le débit toutes les N itérations, avec N un entier supérieur ou égal à deux.

14. Dispositif selon l'une quelconque des revendications 10 à 13, caractérisé en ce que les moyens (25) de modification sont adaptés à retirer le dernier échantillon du parcours.

15. Dispositif selon l'une quelconque des revendications 10 à 13, caractérisé en ce que les moyens (25) de modification sont adaptés à ajouter un échantillon n'appartenant pas au parcours à la fin du parcours.

16. Dispositif selon l'une quelconque des revendications 10 à 13, caractérisé en ce que les moyens (25) de modification sont adaptés à échanger de place deux échantillons du parcours.

17. Dispositif selon l'une quelconque des revendications 11 à 16, caractérisé en ce que les moyens (24) de calcul de la distorsion sont adaptés à calculer la différence entre la valeur de chaque échantillon et sa valeur de décodage respective.

18. Dispositif selon l'une quelconque des revendications 12 à 17, caractérisé en ce que les moyens (24) de calcul du débit sont adaptés à calculer le nombre d'occurrences du vecteur décrivant l'emplacement de chaque échantillon par rapport à l'échantillon précédent dans le parcours.

<Desc/Clms Page number 21>

19. Dispositif de codage selon l'une quelconque des revendications 10 à 18, caractérisé en ce que les moyens de mesure et modification sont incorporés dans : - un microprocesseur (100), - une mémoire morte (102) comportant un programme pour traiter les données, et - une mémoire vive (103) comportant des registres adaptés à enregistrer des variables modifiées au cours de l'exécution dudit programme.

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

22. Appareil de traitement (10) d'une image numérique, caractérisé en ce qu'il comporte le dispositif selon l'une quelconque des revendications 10 à 19.