Plus précisément, l'invention concerne les techniques de compression d'images, ou de séquences d'images, basées sur la mise en oeuvre de transformations mathématiques réversibles.

De très nombreuses techniques de compression d'images sont connues. pour réduire la quantité de données nécessaires pour représenter une image ou une séquence d'images animées On cherche ainsi, notamment, à réduire les débits des signaux numériques, en vue de leur transmission et/ou de leur stockage sur un support de données.

L'invention s'applique notamment, mais non exclusivement, à la transmission de signaux d'images à faible débit, ainsi qu'aux transmissions sans garantie de débit, telles que celles réalisées selon le protocole IP ( « Internet Protocol »).

Parmi les nombreux procédés de codage d'images connus, on peut notamment distinguer les techniques ISO-JPEG et ISO-MPEG, qui ont donné lieu à une norme. Ces procédés de codage reposent notamment sur la mise en oeuvre de transformées, qui permettent une élimination efficace de la redondance dans une image.

La figure 1 illustre le principe général d'un procédé de codage par transformée.

L'image à coder 11 est tout d'abord partitionnée en un ensemble de blocs 12 rectangulaires non recouvrant de mme taille, sur lesquels est appliquée une transformation inversible 13. Cette transformation génère un bloc transformé 14, formé d'un ensemble de coefficients transformés moins corrélés que les coefficients du bloc d'origine 12.

Ces coefficients subissent ensuite une quantification 15, puis un codage 16, avant d'tre transmis (17) sur le canal. ou stocké.

Si l'on note I (x, y) la luminance du pixel de coordonnées (x. y) et si l'on

considère que l'image à coder 11 a été partitionnëe en bloc 12 de taille M x N. l'application d'une transformation 13 a (x, y, m, n) orientée bloc va produire une image F avec : où m E [0, M-1] et n E [O. N-1].

A partir de la transformation a (x, y, m, n), une transformation inverse b (x, y. m, n) peut tre définie afin de reconstruire l'image originale I : Les principales transformations utilisées en compression d'images sont : -la transformation de Karhunen Loève (KLT), -la transformation de Fourier discrète (DFT), -la transformation en cosinus discrète (DCT), -et la transformation de Walsh-Hadamard (WHT).

Il est important de noter que l'opération de transformation 13, appliquée seule. n'assure aucune compression de l'image puisque son seul but est de décorréler les données originales et de concentrer la plus grande partie de l'énergie dans un faible nombre de coefficients transformés. Etant donné que l'énergie totale est conservée, la plupart des coefficients transformés ne contiennent que très peu d'énergie, et c'est donc la quantification 15 et le codage 16 efficaces de ces coefficients qui permettront la compression.

Une transformation de bonne qualité doit permettre une décorrélation efficace, tre indépendante des images traitées, et doit posséder des algorithmes rapides permettant une implémentation efficace.

La technique qui s'avère la plus performante pour la décorrélation d'un signal est la KLT. Malheureusement. elle est dépendante des images manipulées

(car il est nécessaire de calculer les statistiques du signal pour en déduire la transformée) I1 n'existe donc pas d'algorithmes rapides permettant une implémentation efficace. ce qui limite son utilisation.

Cependant, pour les images typiques dans lesquelles il existe une forte corrélation entre les pixels. la performance de la DCT est très proche de celle de la KLT. Par ailleurs, la DCT dispose de nombreux algorithmes rapides permettant une implémentation efficace. De plus, elle ne dépend pas des images manipulées.

Enfin, elle introduit moins de déformations inter-blocs que la DFT.

Si l'on considère l'équation (1), la DCT s'obtint en posant : Différents standards de compression utilisent une approche reposant sur la DCT, tels que JPEG pour les images fixes, H261 et H263 pour les séquences vidéo en vue d'application de type visiophone et visioconférence utilisant des images au format CIF (Common Intermediate Format) et QCIF (Quarter CIF), et enfin MPEG (1,2, et 4), pour les séquences vidéo de contenu quelconque, en vue d'applications de type télévision numérique.

Cette technique classique présente cependant plusieurs limitations, dues notamment au fait que le traitement ne tient pas compte du contenu de l'image d'origine. En effet, le partitionnement de l'image repose sur un découpage régulier et systématique en carrés, engendrant ainsi des effets de blocs. et ne prend pas les transitions brusques entre différentes zones de l'image.

Par ailleurs. les techniques mettant en oeuvre des transformations se prtent mal aux manipulations géométriques (zooms. rotations ou déformations géométriques (« warping »),...), qui sont classiquement utilisées pour déterminer

la compensation d'un mouvement entre deux images consécutives dans le cadre d'images animées (MPEG) ou pour réaliser l'intégration d'images naturelles dans des scènes synthétiques L'invention a notamment pour objectif de pallier ces inconvénients de l'art antérieur.

Plus précisément, un objectif de l'invention est de fournir un procédé de codage d'images fixes ou animées, basées sur la mise en oeuvre d'une transformation réversible, basée sur une partition différente, à base de triangles. II convient de noter que la simple formulation de cet objectif relève d'une démarche inventive. En effet, de nos jours, les principales approches par transformée supposent un partitionnement en blocs carrés, ou une décomposition en régions de forme quelconque, mais n'offrant pas la souplesse d'utilisation d'une partition par maillage.

Un objectif particulier de l'invention est de fournir un tel procédé. dans lequel la partition triangulaire est adaptée au contenu sémantique de l'image ou de la séquence d'images.

Un autre objectif de l'invention est, bien sûr, de fournir un tel procédé de codage qui offre un bon rapport coût/qualité de codage (c'est-à-dire de reconstruction de l'image/quantité de données à transmettre ou à stocker).

L'invention a également pour objectif de fournir un tel procédé de codage qui soit relativement aisé à mettre en oeuvre, et notamment qui ne nécessite pas un nombre important d'opérations supplémentaires complexes par rapport aux techniques connues.

Un objectif complémentaire de l'invention est, dans un mode de réalisation particulier, de fournir un tel procédé de codage qui puisse tre mis en oeuvre sélectivement sur des portions d'images, en complément d'une autre approche.

Un autre objectif de l'invention est de fournir un procédé de décodage correspondant, qui permette la reconstruction d'images de façon simple et peu coûteuse (en temps de traitement. capacité de stockage,...).

Ces objectifs ainsi que d'autres qui apparaîtront plus clairement par la

suite sont atteints selon l'invention à 1'aide d'un procédé de codage d'image. comprenant, pour un domaine correspondant à au moins une portion d'image, les étapes suivantes : -définition d'une partition triangulaire minimale, recouvrant ledit domaine ; -association a chacun desdits triangles source d'une matrice carrée représentative dudit triangle source, à 1'aide d'une première transformation réversible ; -application d'une seconde transformation réversible de décorrélation sur chacune desdites matrices carrées, délivrant des matrices transformées.

Ainsi, selon l'invention, il est possible d'appliquer une technique de transformation réversible sur des images qui ne sont pas décomposées en carrés, mais en triangles, ces derniers pouvant tre de formes quelconques (en taille et en orientation), et différents les uns des autres. Ils peuvent notamment tre adaptés au contenu de l'image.

Il est ainsi possible de cumuler les avantages des techniques à base de transformations et des techniques mettant en oeuvre une décomposition en triangles, sans que les traitements supplémentaires soient très importants, par rapport aux transformations effectuées sur des blocs carrés.

De façon avantageuse, ladite étape d'association d'une matrice carrée comprend les étapes suivantes : -transformation affine d'un triangle source en un triangle rectangle isocèle, appelé triangle de référence ; -création d'une matrice carrée dont la partie inférieure comprend les données représentatives dudit triangle rectangle isocèle : -symétrisation de ladite matrice carrée.

Ces opérations, et les opérations inverses, sont en effet très simples à mettre en oeuvre.

Selon un mode de réalisation préférentiel de l'invention, ladite matrice

carrée est obtenue à 1'aide d'une interpolation bilinéaire.

Avantageusement, ladite étape de création d'une matrice carrée met en oeuvre un facteur d'échelle a permettant une expansion ou une compression dans le domaine spatial. On peut ainsi facilement adapter le nombre de données nécessaires pour coder l'image en fonction des besoins et/ou des ressources disponibles.

Dans ce cas, ladite matrice carrée peut comprendre lignes, où E représente la fonction délivrant la partie entière supérieure, A étant l'aire dudit triangle rectangle isocèle.

Ladite seconde transformation peut notamment appartenir au groupe des transformations usuelles du domaine, telles que par exemple : -la transformation de Karhunen Loève (KLT) ; -la transformation de Fourier discrète (DFT) ; -la transformation en cosinus discrète (DCT) ; -la transformation de Walsh-Hadamard (WHT).

Comme on le verra par la suite, la DCT semble actuellement la mieux adaptée.

Préférentiellement, le procédé de codage d'image selon l'invention comprend ensuite une étape de quantification et de codage des données de la partie inférieure de ladite matrice transformée. La plupart des techniques de quantification et de codage peuvent tre utilisées.

En particulier, ladite quantification peut avantageusement appartenir au groupe comprenant : -une quantification uniforme ; -une quantification à parcours zigzag, le pas de quantification étant incrémenté au fur et à mesure dudit parcours ; -une quantification basée sur au moins une matrice de pondération pré-évaluée ou optimisée pour l'image traitée.

Par ailleurs, le codage comprend préférentiellement une étape de codage RLE ("Run Length Encoding" : codage par longueur de séquences) et entropique

des données quantifiées.

De façon avantageuse, le procédé de l'invention est paramétrable.

Notamment, on peut prévoir que ledit facteur d'échelle a, le type de quantification et/ou le pas de quantification sont modifiables, pour chacun desdits triangles et/ou pour chacune desdites portions d'image.

Le procédé décrit s'applique quelle que soit la méthode utilisée pour déterminer les triangles à traiter. Selon un mode de réalisation avantageux. ladite partition triangulaire est obtenue selon une méthode tenant compte du contenu de l'image ou de la portion d'image.

En d'autres termes. les sommets et les artes des triangles coïncident. autant que faire se peut. avec des transitions dans l'image considérée Notamment, ladite méthode appartient avantageusement au groupe comprenant : <BR> <BR> <BR> <BR> -les méthodes mettant en oeuvre une DCT ;<BR> <BR> <BR> <BR> <BR> <BR> -les méthodes à base de décomposition fractale ; -les méthodes dites"matching pursuit" (ou méthodes de poursuites d'appariement) ; -les méthodes mettant en oeuvre une SADCT ("Shape Adaptive DCT").

Le procédé décrit ci-dessus peut bien sûr s'appliquer à une image (ou une séquence d'images) complète. II peut également, selon un mode de réalisation avantageux. tre mis en oeuvre sur des portions d'image présentant une texture dont l'erreur de représentation est supérieure à un seuil donné. Ladite erreur de représentation peut notamment correspondre à un écart de luminance entre ledit triangle source et le triangle après reconstruction.

Dans ce cas, le procédé de codage est préférentiellement mis en oeuvre sur une image d'erreur, correspondant à la différence entre une image source et une image approximée. obtenue en mettant en oeuvre un procédé préalable distinct de codage.

Ledit procédé préalable de codage peut notamment tre un procédé

d'approximation par affinement. mettant en oeuvre un maillage hiérarchique à partir duquel on construit un arbre quaternaire présentant autant de niveaux qu'il y a de niveaux dans ledit maillage hiérarchique. chacun desdits niveaux présentant un nombre de noeuds égal au nombre de triangles dans le niveau de maillage correspondant. Dans ce cas, pour les noeuds répondant à un critère prédéterminé, on remplace avantageusement ledit codage préalable par un codage à base de transformée tel que décrit ci-dessus.

Ledit critère prédéterminé peut reposer. selon un mode de réalisation préférentiel, sur l'écart de luminance entre le triangle de l'image approximée et celui de l'image source.

Dans ce cas, le traitement pour chaque noeud (sachant qu'un noeud correspond à un triangle sur un niveau donné de l'arbre) est avantageusement le suivant : -on calcule un écart de luminance entre l'image à coder et l'image interpolée sur ledit triangle, à partir des sommets du maillage emboîté auquel appartient le noeud considéré ; -on compare ledit écart de luminance à un écart seuil ; -on effectue le choix suivant : -si ledit écart de luminance est inférieur audit écart seuil, on interrompt le procédé d'approximation par raffinement du maillage hiérarchique, pour le noeud considéré ; -si ledit écart de luminance est supérieur audit écart seuil, mais inférieur à un second seuil, on continue à appliquer ledit procédé mettant en oeuvre un maillage hiérarchique ; -si ledit écart de luminance est supérieur audit second seuil. on met en oeuvre le procédé de codage décrit précédemment.

Selon un mode de réalisation particulier de l'invention, ledit second seuil vautkxS. avec : k : réel supérieur ou égal à 1 :

S : valeur réelle proportionnelle à l'écart de luminance d'erreur moyen.

Préférentiellement. ledit écart de luminance représente une erreur quadratique ou une erreur absolue entre ledit triangle source et le triangle approximé correspondant.

L'invention concerne également les décodeurs et le décodage des images codées selon le procédé de codage décrit ci-dessus. Le procédé de décodage de données représentatives d'une image codée selon le procédé de codage de l'invention comprend notamment les étapes suivantes de reconstruction d'une approximation de l'image d'origine : a) application d'une transformation inverse à ladite seconde transformation réversible sur lesdites matrices transformées, délivrant lesdites matrices carrées reconstruites : b) association à chacune desdites matrices carrées reconstruites d'un triangle reconstruit correspondant, à l'aide d'une transformation affine inverse de ladite première transformation réversible ; c) reconstruction de ladite partition minimale, à partir desdits triangles reconstruits.

En d'autres termes, la reconstruction des images codées repose, en particulier, sur la mise en oeuvre des transformations inverses à celles utilisées lors du codage.

Notamment, lesdites matrices carrées peuvent tre recréées à partir des données d'un train binaire reçu, dont les données décodées sont les coefficients du triangle à reconstruire, qui forment la partie inférieure de ladite matrice.

Lorsqu'un codage préalable, tel que décrit précédemment, a été mis en oeuvre, les étapes a), b) et c) sont bien sûr appliquée sur la partie correspondante du train binaire reçu, l'autre partie du train binaire ayant été codée et étant décodée selon une autre méthode.

Notamment, lorsque le train binaire comprend d'une part des données codées selon un codage préalable, et d'autre part des données codées à l'aide desdites transformations réversibles, ledit procédé de décodage comprend :

-un décodage préalable desdites données codées selon un codage préalable. permettant la description d'une représentation initiale ; -un décodage complémentaire desdites données codées à 1'aide desdites transformations réversibles, mettant en oeuvre lesdites étapes a), b) et c), et permettant d'affiner ladite représentation initiale.

Préférentiellement, ledit codage préalable mettant en oeuvre un codage hiérarchique, ledit décodage préalable assure la lecture, dans le train binaire reçu, d'au moins une des informations appartenant au groupe comprenant : -le nombre de niveaux de la hiérarchie ; -l'identification de la technique de codage utilisée pour chacun des triangles ; -la succession des valeurs différentielles des composantes associées aux noeuds dudit maillage hiérarchique ; -l'identification des arcs sur lesquels une inversion de diagonale est réalisée.

D'autres caractéristiques et avantages de l'invention apparaîtront plus clairement à la lecture de la description suivante d'un mode de réalisation préférentiel donné à titre de simple exemple illustratif et non limitatif, et des dessins annexés parmi lesquels : -la figure 1, déjà commentée en préambule, illustre la technique connue d'un codage mettant en oeuvre une transformation ; -la figure 2 est un organigramme simplifié du procédé de l'invention -la figure 3 illustre le principe des deuxième et troisième étapes du procédé de la figure 2 ; -la figure 4 est un extrait, plus précis, de la figure 3, correspondant à la deuxième étape du procédé de la figure 1 ; -les figures 5 et 6 présentent deux modes de quantification pouvant tre utilisés dans le procédé de la figure 2 :

-la figure 7 illustre le parcours en zig-zag de l'étape de codage du procédé de la figure 2 ; -la figure 8 illustre la correspondance entre le maillage emboîté et l'arbre quaternaire dans un procédé de codage hiérarchique : -la figure 9 est un exemple de sélection des noeuds de l'arbre de la figure 8, sur lesquels le procédé de la figure 2 va tre mis en oeuvre ; -la figure 10 est un organigramme simplifié illustrant le choix du traitement à effectuer, lorsque l'on met en oeuvre de façon associée le procédé de l'invention et un codage hiérarchique L'invention propose donc la mise en oeuvre d'une transformation, par exemple une transformation DCT, adaptée à une partition triangulaire. La figure 2 est un organigramme général illustrant le procédé correspondant.

Le traitement avec noeud selon l'invention est donc le suivant : -définition 21, sur le domaine de l'image à coder, d'une partition triangulaire, qui peut tre adaptée au contenu, sur le domaine de l'image (ou de la, ou des, portion (s) d'image) à coder ; détermination, pour chaque élément de la partition obtenue, des transformations permettant d'associer à chaque élément triangulaire un triangle de référence 22, puis un carré (c'est-à-dire une matrice) 23 ; réalisation d'une DCT 24 sur chacune de ces matrices ; -application d'un procédé de quantification 25 et de codage 26, pouvant tre identique à ceux des standards actuels.

Selon la première étape 21 du procédé de l'invention, on définit tout d'abord, sur le domaine de l'image, une partition triangulaire. Cette partition triangulaire est généralement initialement régulière (bien qu'elle puisse également tre irrégulière). Elle peut donc parfois sembler inadaptée, lorsqu'elle est régulière, pour représenter une image comportant des disparités au niveau de son contenu et/ou mlant des régions uniformes à des zones plus texturées. nécessitant

une forte densité de sommets.

Cette étape 21 comprend donc avantageusement une optimisation de la position des sommets du maillage définissant les triangles, de façon à déplacer les concentrations de sommets du maillage vers les zones le nécessitant. Une telle technique est par exemple présentée dans le document de brevet FR-98 12 525. au nom des titulaires de la présente demande de brevet.

L'effet visuel le plus immédiat d'une telle optimisation se manifeste par un rapprochement des sommets du maillage vers les contours physiques de l'objet de l'image.

Les deuxième et troisième étapes 22 et 23 du procédé de l'invention sont illustrées par la figure 3.

On détermine, pour chaque élément triangulaire 31 de la partition, la transformation affine 32 permettant d'associer à chaque triangle quelconque 31 un triangle de référence 33, qui soit isocèle. On transforme ensuite le triangle de référence en un carré, et plus précisément une matrice carrée 34, par symétrisation 35.

Plus précisément. la première transformation 32 consiste à déterminer la transformation affine permettant de passer d'un triangle quelconque 31 au triangle de référence 33, ainsi que cela est illustré par la figure 4.

La transformation affine inversible F telle que Pi = F (Q ;), avec Pj = (xj, yj) et Q, = (X,, Y,), s'écrit : Cette transformation affine est inversible, car le déterminant de la matrice est égal (au signe près) à 2A (où A représente l'aire du triangle quelconque 31), qui est supposé non nul. Cette transformation affine inverse s'écrit donc :

La deuxième transformation 23,36 consiste à transposer les informations contenues dans chaque triangle d'aire A dans la partie inférieure d'une matrice carrée G deE (a x 2 x A) lignes, où E représente la partie entière supérieure de la valeur entre parenthèses, et a E R+, * représente un facteur d'échelle, qui agit sur la représentation visuelle de l'image, en réalisant une expansion (a>l) ou une compression (a<l) dans le domaine spatial.

D'après les formules (1) et (2), on a : F (m, n) = F (n, m) car I (x, y) = I (x, y), du fait de la symétrisation 35.

Après symétrisation de G, sa transformation 24 selon l'équation (1) engendre une matrice également symétrique H.

De ce fait, les informations contenues dans la partie inférieure de chaque matrice G étant identiques à la partie supérieure (25), l'utilisation de la transformation DCT 24 basée bloc peut tre mise en oeuvre comme par exemple dans MPEG ou JPEG.

Après transformation 24, seules les parties inférieures des matrices H seront quantifiées (25) et codées (26).

Afin d'optimiser les performances du coût de codage 26, deux moyens d'action peuvent tre mis en oeuvre, modulés par exemple en fonction de la pertinence de la texture sous-jacente aux triangles considérés, à savoir : -le facteur d'échelle a (on prendra alors a< 1) ; -le choix de la quantification, et en particulier amplitude des pas de quantification retenus Parmi les quantifications 25 possibles, on peut notamment utiliser : -une quantification uniforme ; -une quantification à parcours zig-zag ;

-une quantification par utilisation d'une matrice de pondération pré- évaluée sur critère psycho-visuel.

La quantification à parcours zig-zag consiste à initialiser le processus de quantification à une valeur Q',,,. qui au cours du parcours. à chaque remontée, est incrémentée d'une valeur AAt-, ainsi que cela est illustré par la flèche 51 de la figure 5.

Un exemple de matrice de pondération pré-évaluée sur critère psycho- visuel est la matrice QM standard JPEG, illustré en figure 6. On peut également considérer la matrice de la norme MPEG4. Les matrices G et QM pouvant tre de taille différente, on procédera à une interpolation de la matrice QM, ramenant cette dernière à la taille de G comme pour JPEG. il est alors possible de définir un facteur de qualité qf agissant comme multiplicateur à la matrice QM. On peut également mettre en oeuvre une matrice de pondération optimisée pour l'image traitée Le codage effectif 26 est par exemple réalisé en effectuant un codage de type RLE (Run Length Encoding) et entropique, sur le parcours zig-zag 71 représenté en figure 7.

I1 apparaît clairement que le procédé décrit ci-dessus peut tre utilisé seul, sur des images complètes.

Il peut également, avantageusement tre mise en oeuvre sur des portions d'images, en complément d'une autre approche de codage. En particulier, il peut avantageusement tre utilisé de façon sélective sur des régions particulières de l'image, et notamment les parties très texturées.

Ainsi, par exemple, le procédé de l'invention s'avère particulièrement bien adapté à la technique de codage décrite dans la demande de brevet FR-98 12 525, au nom des mmes titulaires que la présente demande de brevet. et ayant pour titre "procédé de codage d'images fixes ou animées avec réduction et adaptation du débit". II apparaît en effet que cette dernière technique a des difficultés à représenter les textures.

Avant de montrer comment le procédé de l'invention peut tre ainsi utilisé,

on rappelle brièvement le principe du procédé décrit dans la demande de brevet FR-98 12 525.

Cette technique a pour objet un procédé de codage d'une image numérique. visant à produire un train binaire représentatif de cette image. la longueur du train binaire étant fonction de la représentation voulue. Ce procédé reprend les étapes suivantes : définir, sur un domaine de l'image à coder, un maillage hiérarchique comportant une pluralité de maillages emboîtés dont les sommets de mailles peuvent tre des pixels de ladite image ; -réaliser les optimisations de luminance. chrominance. et positions sur chaque niveau de maillage ; déterminer, pour chaque maille dudit maillage hiérarchique, un écart de luminance entre l'image à coder et une image interpolée obtenue à partir des sommets du maillage emboîté auquel appartient la maille considérée, et -introduire dans le train binaire les valeurs (avantageusement codées en différentiel par rapport au niveau hiérarchique précédent) de positions, de luminance et de chrominance des sommets des mailles dont l'écart de luminance est supérieur à un écart seuil.

On notera que cette technique n'est pas limitée aux signaux de luminance et de chrominance, mais peut s'appliquer à tout modèle de couleurs.

Le procédé de la présente invention peut avantageusement intervenir lors du calcul de cet écart seuil.

En effet, selon la technique antérieure, et ainsi que cela est illustré par la figure 8, au terme de l'étape de maillage, on construit une structure en arbre quaternaire 81. associé au maillage hiérarchique 82. pour manipuler les valeurs (couleurs et positions) des sommets des mailles. L'arbre 81 présente un nombre de noeuds égal au nombre de triangles dans le niveau de maillage correspondant.

Chaque noeud 83 de l'arbre se rapporte à un unique triangle 84 du maillage hiérarchique 82.

Une fois l'arbre 81 construit, il faut déterminer les données de l'arbre à introduire dans le train binaire représentatif de l'image. Cette détermination dépend de la qualité voulue.

Pour réaliser cette détermination, on prévoit de calculer, pour chaque triangle, un écart de luminance entre l'image à coder et l'image interpolée à partir des sommets du maillage emboîté auquel appartient la maille considérée. Cet écart est ensuite comparé à un écart seuil pour chaque triangle. La valeur de l'écart seuil est fonction de la qualité de représentation voulue.

On introduit ensuite dans le train binaire la partie de l'arbre se rapportant aux triangles dont l'écart de luminance est supérieur. Cette sélection des noeuds de l'arbre par parcours en profondeur est illustrée par la figure 9. Seuls sont conservés les noeuds se trouvant au-dessus de la frontière 91.

L'écart seuil permet donc de transmettre les données relatives à l'image fonction de la qualité locale de ces différentes partitions triangulaires. En effet, sur une partie texturée, la transmission des données intervient jusqu'au dernier niveau de maillage (maillage le plus fin) et, pour les parties plus lisses, un niveau grossier s'avère suffisant.

Selon la présente invention, on peut avantageusement mixer les deux approches, à savoir la transmission affine, symétrisée et transformée par DCT (nommée par soucis de concision DCT par la suite), avec la technique des maillages emboîtés qui vient d'tre décrite.

En effet, selon cette technique des maillages emboîtés, on définit tout d'abord, sur le domaine de l'image à coder. un maillage hiérarchique comportant une pluralité de maillages emboîtés. Les sommets de ces maillages sont des pixels de l'image à coder. Ce maillage est par exemple obtenu par divisions régulières et successives des mailles du maillage grossier.

Selon la présente invention, on se place à un niveau n (compris entre le premier et le dernier niveau de maillage) de maillage, on calcule l'image interpolée par la technique du maillage hiérarchique, et on en déduit une image d'erreur correspondant à la différence de luminance entre l'image originale et

l'image interpolée.

On construit ensuite l'arbre relatif aux n premiers niveaux de maillages. et on calcule 1'écart de luminance pour chacun des triangles du maillage de l'image d'erreur. et on choisit un écart seuil S. Le critère de l'écart de luminance sur un triangle T correspond à l'erreur quadratique suivante : ET = I (I c (X, Y)) 2 = E I' ( 1 1 l \ Il c, yE7' r. y Avec I, l'image d'erreur entre l'image interpolée et l'image originale sur le triangle T.

Selon la présente invention, on détermine alors les noeuds de l'arbre permettant de spécifier si la procédure d'approximation doit s'arrter, si l'on doit continuer la subdivision du maillage par interpolation affine avec la technique du maillage hiérarchique, ou si l'on doit utiliser la DCT selon la technique décrite précédemment. Pour cela, on peut utiliser le procédé illustré en figure 10. Si, pour le niveau n donné, l'écart de luminance d'un triangle T du maillage est : -101 : inférieur à l'écart seuil : la partie de l'image interpolée sur ce triangle est d'une qualité visuelle correcte, et la procédure s'arrte (102) ; -103 : supérieur à l'écart seuil mais inférieur à k x S, avec k 2 1 : le procédé d'approximation continu avec la technique du maillage hiérarchique (104), la partie de l'image interpolée correspondant à une image moyennement texturée ; -105 : supérieur à k x S avec k s 1 : le triangle est traité par une DCT appliquée au triangle de l'image d'erreur (106).

Cette sélection se justifie de la manière suivante. On sait que : dEprès (1)

On constate donc que le coefficient F (m, n) tend vers zéro lorsque l'écart de luminance tend vers zéro. Une faible erreur quadratique entraîne des coefficients AC après transformée de faible amplitude, ayant de fortes chances d'tre annules après quantification.

Ainsi, réaliser sur de telles mailles une interpolation affine moins coûteuse qu'une transformation DCT s'avère plus judicieux.

Le procédé global consiste donc à traiter une partie de l'image par la technique du maillage hiérarchique, et à traiter les parties très texturées de cette image par une DCT selon la présente invention, appliquée sur des triangles de l'image d'erreur correspondante.

On applique donc ici sur la partie texturée de l'image d'erreur une DCT sur les triangles dont l'écart de luminance est important.

De plus, la technique du maillage hiérarchique n'est qu'un exemple. La technique de l'invention mettant en oeuvre une DCT sur des triangles peut tre utilisée par toute autre technique mettant en oeuvre des triangles, tels que par exemple : les méthodes à base de décomposition fractale : le principe de compression d'images en niveaux de gris par la méthode des IFS, aussi appelée compression fractale, repose sur 1'expression du contenu de l'image au moyen du contenu lui-mme.

II peut tre vu comme une auto-quantification de l'image. La formalisation de cette méthode provient notamment des travaux de Hutchinson en 1981. et de ceux de Bradley. Demko et d'autres chercheurs du Georgia Institute of Technology entre 1985 et 1988.

Le premier algorithme automatique appliquant ces idées à la

compression des images a été proposé par Jacquin en 1989.

Des améliorations à cette technique sont proposées dans le document de brevet FR-99 00656. intitulé"procédé et dispositif de codage à base de schémas IFS, à fonctions de collage oscillantes, procédé de codage, fonction de collage, support de données et applications correspondants".

-les méthodes dites de"matching pursuit" (encore appelées poursuites d'appariemments), notamment décrit dans l'article de Ralph Neff et Avideh Zakhor. intitulé"Very Low Bit Rate Video Coding based on Matching Pursuits". publié dans IEEE Transactions on circuits and systems for video technology.

Le codage (du résidu) par matching pursuit est une méthode itérative qui utilise un dictionnaire de fonctions redondantes. A chaque itération, on cherche la fonction qui représente le mieux le résidu obtenu à l'étape précédente. On décompose ainsi l'image sur une suite d'atomes qui la représentent de manière optimale ; -la SADCT ("Shape Adaptive DCT"), décrite par exemple par T.

Sikora et B. Makai dans"Shape Adaptive DCT for generic Coding" (IEEE Transactions on Circuits and Systems for Video Technology, 5 (1), pp. 59-62, février 1995).

L'invention concerne également le décodage des données codées selon le procédé de codage décrit précédemment. Ce procédé de décodage se déduit directement des étapes de codage.

Ainsi, lorsqu'un codage préalable, notamment de type hiérarchique a été mis en oeuvre, le décodage repose sur la réception d'un train binaire contenant : -la description d'une représentation initiale de l'image, issue du codage préalable (qui sera soumise à un décodage préalable symétrique) ; -les valeurs quantifiées et codées après transformation DCT associées aux triangles sélectionnés.

Les coefficients de pondération des matrices peuvent tre transmis dans le train binaire. Cependant. préférentiellement. ils sont connus du décodeur.

Le décodage des valeurs quantifiées et codées après transformation DCT comprend notamment les étapes suivantes : création d'une matrice carrée symétrique dont la partie inférieure comprend les coefficients décodés du triangle à représenter, lu dans le train binaire ; transformation DCT inverse de la matrice ainsi créée ; -transformation affine du triangle rectangle isocèle associé à la partie inférieure de la matrice, vers le triangle à représenter.

Lorsque le codage préalable repose sur un maillage hiérarchique, le décodage correspondant assure notamment la lecture, dans le train binaire reçu : -du nombre de niveaux de la hiérarchie ; -de l'identification de la technique de codage utilisée pour chacun des triangles ; -de la succession des valeurs différentielles des composantes associées aux noeuds dudit maillage hiérarchique.