Brevet FR2788655A1 — publié le 20000721

Procédé et dispositif de codage par IFS, à fonctions de collage oscillantes,procédé de décodage, fonction de collage, support de données et applications correspondantes. Le domaine de l'invention est celui du codage, et en particulier de la compression du volume d'une image, avec perte d'informations, par exemple en vue de son stockage et/ou de sa transmission. La notion de compression d'images avec perte est une notion bien connue dans le domaine du traitement de l'image. Le problème principal rencontré est bien sûr celui de l'obtention d'une approximation de l'image originale qui soit la plus fidèle possible, tout en minimisant le volume de l'approximation. Pour exprimer le gain sur un volume de données, on introduit généralement la notion de débit, dont l'unité est le bit par pixel (bpp). Le débit défini donc le rapport entre le nombre pixels de l'image originale et le nombre de bits nécessaires à la reconstruction de son approximation. L'invention concerne notamment les applications requérant un codage d'images à bas débit (par exemple avec un taux inférieur à 0,3 bpp), telles que des applications sur réseau Internet. Bien sûr, comme cela apparaît par la suite, l'invention peut être appliquée à de nombreux autres domaines techniques. En effet, l'invention apporte une amélioration importante aux techniques de compression fractale, également appelée compression à base de systèmes de fonctions itérées (IFS). Le principe de compression d'images par la méthode des IFS repose sur l'expression du contenu de l'image au moyen de ce contenu lui- même. Il peut donc être vu comme une auto-quantification de 1' image. La formalisation de la méthode des IFS provient notamment des travaux d'Hutchinson, publiés en 1981 et de ceux de Bransley, Demko et d'autres chercheurs du Georgia Institute of Technology, entre 1985 et 1988. Le premier algorithme automatique appliquant ces principes à la compression des images a été proposé par Jacquin, en 1989. Le principe général de cet algorithme repose sur le partitionnement (découpage) de l'image I à coder en régions destination (également appelé " range "). Ce partitionnement peut être prédéfini, ou dépendre du contenu de l'image. Ensuite, pour chacun des régions destination on effectue les opérations suivantes: - choix (selon différentes techniques connues) d'une autre région de l'image, de plus grande taille, non nécessairement élément d'une partition, appelé région source (ou "domain"); - détermination de la fonction de collage spatial, dans une famille de fonctions de collage spatial préalablement fixée, qui transforme le support de la région source de manière à la rendre superposable à la région destination considérée. S'il n'existe aucune fonction correspondante, on revient à l'étape précédente. Sinon, le résultat de l'application de la fonction de collage spatial identifiée sur la région source est appelé région source décimée; - détermination de la fonction de collage massique, dans la famille des fonctions de collage massique préalablement fixée qui transforme le contenu (par exemple la couleur et/ou le niveau de gris et/ou au moins une information photométrique) de la région source décimée de manière à la rendre la plus proche possible de celle de la région destination considéré. Si la proximité n'est pas satisfaisante, on reprend à la première étape précédente. L'ensemble des collages spatiaux et massiques ainsi retenus est appelé IFS. Ces fonctions de collages spatiaux et massiques sont essentiellement des fonctions affines. On appelle généralement fonction de collage le couple formé par la fonction de collage spatial et la fonction de collage massique appliquées à une région source. Soit IR, une image au contenu quelconque, de même support que l'image I ayant servi à construire l'IFS. Les applications successives de l'IFS à IR permettent de converger (par exemple en une dizaine d'itérations) vers un " point fixe ", qui est une image I' proche de I. Cette propriété est la base du codage d'images par IFS. En effet, il suffit de mémoriser l'IFS afin de caractériser I'. Tout en conservant le principe général présenté ci-dessus, de nombreuses recherches ont été effectuées afin d'améliorer les performances des premiers codeurs à base d'IFS. On a notamment proposé de réaliser des partitions adaptatives pour les régions destination. De telles partitions permettent de paver l'image avec de petites régions sur les zones texturées et difficiles à approximer, et de paver l'image avec de grandes régions sur les zones moins riches et plus faciles à approximer. Une autre avancée est l'hybridation des méthodes IFS avec d'autres méthodes de compression d'images telles que les ondelettes, la quantification vectorielle (QV) ou la décomposition en cosinus discrète (DCT). Une hybridation IFS-ondelettes consiste en une recherche des similarités entre les sous-bandes d'une décomposition en ondelettes de l'image originale. Une hybridation IFS-QV considère les IFS comme une auto-quantification de l'image, et cherche à quantifier les régions sources de l'IFS déterminées sur l'image originale. Enfin, une hybridation IFS-DCT vise par exemple à exprimer les similarités des coefficients des régions destination transformées par DCT avec des régions sources elles aussi transformées par DCT. Une telle hybridation IFS-DCT peut aussi consister à appliquer un calcul d'IFS sur l'image résiduelle d'une reconstruction DCT, ou encore, inversement, à appliquer une approximation par DCT sur l'image résiduelle d'une reconstruction par IFS. Ces différentes techniques connues sont relativement efficaces, dans de nombreuses situations. Elles présentent cependant des défauts d'analyse et de synthèse, lorsqu'elles doivent traiter des zones présentant de hautes fréquences et/ou un contenu texture, en particulier lorsqu'un très bas débit est souhaité. L'invention a notamment pour objectif de pallier les inconvénients de ces techniques antérieures. Plus précisément, un objectif de l'invention est de fournir un procédé de codage d'images mettant en oeuvre des IFS, qui soit plus efficace, notamment en terme de qualité visuelle de l'approximation, en particulier pour le traitement des hautes fréquences et des zones texturées, tout en conservant la performance sur les autres zones. Un autre objectif de l'invention est de fournir un tel procédé de codage qui soit simple à mettre en oeuvre, avec une quantité de calculs raisonnable. Notamment, un objectif de l'invention est de fournir un tel procédé de codage qui puisse bénéficier des avantages des techniques connues citées ci-dessus, en y apportant une scalabilité accrue. L'invention a également pour objectif de fournir un procédé de décodage correspondant qui puisse être, le cas échéant, paramétrable. Ces objectifs, ainsi que d'autres qui apparaîtront par la suite, sont atteints à l'aide d'un procédé de codage d'images mettant en oeuvre des systèmes de fonctions itérées (IFS), ledit procédé comprenant les étapes suivantes: * partitionnement d'une image I à coder en un ensemble de régions d'image, dites régions destination, de forme arbitraire (rectangle, triangle, etc); * association à chacune desdites régions destination D d'une région source correspondante S et d'une fonction de collage w tels que w(S) soit une bonne approximation de ladite région destination D, ladite fonction de collage se décomposant en: e une fonction de collage spatial ws, agissant sur la position et/ou la géométrie de ladite région source S, afin de créer une région source décimée S (on a: S = ws (S)); et * une fonction de collage massique WM, agissant sur le contenu (par exemple la couleur et/ou le niveau de gris et/ou au moins une information photométrique) de ladite région source décimée S. Selon l'invention, ladite fonction de collage massique WM est une fonction oscillante. L'invention repose donc sur une approche nouvelle, et non évidente, du collage. En effet, quelle que soit la technique utilisée, on a toujours considéré que seules des fonctions polynomiales (celles-ci incluant notamment les fonctions affines) étaient utilisables dans ce contexte. L'utilisation de fonctions oscillantes permet d'obtenir de bons résultats, en particulier pour le traitement de régions contenant de hautes fréquences. Ainsi, il est possible de reconstruire fidèlement des textures, en évitant l'effet de lissage commun aux techniques IFS connues. De façon avantageuse, ladite fonction de collage massique WM est une fonction harmonique, et par exemple une fonction cosinusoidale. Dans ce cas, une région source transformée S' = w(S) peut avantageusement être définie par: Si:= w(Si)= CkxS. xcos(Oi)x)cos(Oki,)+b IE[O;N, [ kE[o;N, [ o: i est l'indice du i-ème pixel de S', de coordonnées (i, iy); Si est l'image de Si par w, ; 0 est un vecteur réel de RNC tel que Oj = 2t/2j; %c et b sont des coefficients caractérisant la fonction de collage (les coefficients Ck représentant les amplitudes et b représentant le décalage). Lesdits coefficients ck% et b peuvent alors être déterminés en recherchant les coefficients minimisant une erreur entre source et destination. Cette erreur E s'écrit par exemple: E = (S j-D) iE[0O; card(D)[ avec: Card(D): nombre de pixels de D. Diverses techniques de calcul peuvent être utilisées. En particulier, on peut mettre en oeuvre un système linéaire matriciel, dont les solutions sont déterminées à l'aide d'une des méthodes appartenant au groupe comprenant: - méthode directe; - méthode itérative; - méthode de gradient. Selon un mode de réalisation préférentiel de l'invention, on met en oeuvre une méthode directe par pivot de Gauss ou par Cholesky. De façon avantageuse, ladite fonction de collage massique WM est écrite sous la forme d'une combinaison de fonctions oscillantes, dont le nombre et/ou la fréquence et/ou l'amplitude est paramétrable. L'invention concerne également un dispositif de codage d'images mettant en oeuvre ce procédé, ainsi que la fonction de collage proprement dite, dans laquelle la fonction de collage massique WM est une fonction oscillante. L'invention concerne également le procédé de décodage d'images codées à l'aide du procédé de codage décrit ci-dessus. Selon ce procédé de décodage, on reconstruit lesdites images en effectuant au moins une itération de ladite fonction de collage appliquée à ladite région source S correspondante, ladite fonction de collage massique WM étant une fonction oscillante. Selon un mode de réalisation préférentiel de l'invention, la fonction de collage massique appliquée à ladite région source décimée lors du décodage prend en compte un nombre de fonctions oscillantes inférieur et/ou égal à celui pris en compte lors du codage. Ainsi, il est possible d'effectuer un décodage progressif, et/ou une scalabilité (échelonnabilité) lors du décodage. L'invention concerne encore les supports de données contenant des images codées selon la technique décrite ci-dessus (seules lesdites régions source S et lesdites fonctions de collage étant stockées sur ledit support de données). L'invention trouve des applications dans de nombreux domaines, et en particulier dans les domaines appartenant au groupe comprenant les domaines suivants: À compression d'images fixes; * compression (d'images) en mode " intra " dans un codeur vidéo; À compression d'images, ou de partie d'images, texturées; * réalisation d'agrandissement (zoom) de zones d'images; * compression dans des espaces de dimension supérieure à 2. 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, qui illustrent, sur un exemple, le principe du codage par IFS - la figure 1 présente une image originale à compresser I; - la figure 2 illustre la construction d'une partition sur l'image originale de la figure 1; - la figure 3 illustre la recherche, pour une région D fixée de la région S et du collage w qui l'approxime au mieux; - la figure 4 illustre la détermination de la fonction de collage W de la figure 3. L'invention concerne donc une amélioration des techniques à base d'IFS. On rappelle que cette technique, connue en soi, vise à exprimer les auto- similarités d'une image. A titre d'exemple, la figure 1 présente une image originale, que l'on désire compresser. La première étape du traitement consiste à réaliser une partition de 1' image originale. Ainsi que cela est illustré par la figure 2, sous la forme de régions, ou blocs, carrés. La partition peut également être effectuée à partir d'un autre motif de base, notamment des triangles. Elle peut également être adaptative, c'est-à- dire tenir compte du contenu de l'image, et notamment de la complexité des différentes parties de cette image. Ensuite, pour chaque région D 31 de la partition, on recherche la région S (32, 33 ou 34) et le collage w qui l'approximent au mieux, ainsi que cela est illustré en figure 3. Dans l'exemple illustré, c'est la région S2 33 qui répond à ce critère. La figure 4 illustre le principe de la fonction de collage w. Celui-ci comprend tout d'abord un collage spatial ws, qui déplace, décime et oriente la région 33 de façon qu'elle se rapproche géométriquement de la région 31. Ensuite, on détermine la fonction de collage massique WM, qui permet d'obtenir la région 41 S'2, approximant la région 31. Plus précisément, lorsque l'on considère la région destination D 31, la résolution consiste à caractériser une région source S 33 ainsi qu'une fonction de collage w, tels que w(S) soit une bonne approximation de S. Dans un cas particulier, si l'on note S'=(S) et si la mesure d'erreur considérée est la distance L2, alors l'erreur à minimiser est définie par: E = (S'-D)2 i e[O;card(D)[ o S'i (respectivement Di) est l'intensité du i-ème pixel de S' (respectivement D), et o card(D) est le nombre de pixels de D. La fonction de collage w se décompose en deux sous-fonctions. La première est le collage spatial ws qui agit sur la position et la géométrie des régions. Elle transforme la région source en une région décimée S. La deuxième est le collage massique WM qui agit sur le contenu des régions. Elle transforme la région source décimée S en une région S' approximant au mieux, au sens de l'erreur définie ci-dessus, la région D considérée. L'invention concerne la nature des collages massiques WM. Selon les techniques connues, ces opérations de collage massique WM sont des fonctions polynomiales (celles-ci incluant notamment les fonctions affines). Plus précisément, elles font intervenir deux variables ca et À, appelées facteur d'échelle et facteur de décalage (ou scale et offset). On a également envisagé d'utiliser des collages massiques polynomiaux ou définis par des arbres de fonction. Mais ces techniques se sont avérées peu efficaces et/ou très complexes, et donc, notamment, non adaptées à la compression d'images en niveaux de gris. Selon l'invention, on utilise des fonctions de collage massique oscillantes. Dans le mode de réalisation décrit ci-après, à titre d'exemple, on utilise des fonctions de collage cosinusoidales. Cette approche permet d'introduire des hautes fréquences dans les collages de l'IFS, lorsque le contenu des régions source n'est pas assez riche. Le collage de l'invention permet l'optimisation conjointe de la caractérisation des régions source et des coefficients associés aux fonctions cosinusoidales. Ainsi, les régions source apportent les informations basse fréquence, ainsi que les ruptures de pente tel que les contours, que les fonctions cosinusoidales enrichissent, si la région destination considérée comporte des informations haute fréquence. Si l'on considère une région destination D et une région source S, on peut déterminer, de façon classique, un collage spatial ws. On appelle l'image S l'image de S par ws. Le contenu de la région source transformée S' approximant D peut s'exprimer, selon l'approche de l'invention, de la façon suivante: S i W=(S) S i= WM (Ws(Si)) Si= WM(Si) Si= Y X SY, xcos(O,i,) x cos(Okiy) + b IE[O;N,[kE[O;N,[ o: i est l'indice du i-me pixel de S', de coordonnées (ix, iy); Sg est l'image de Si par ws; 0j est un vecteur réel de RNC tel que Oj = 2nc/2j; c., et b sont des coefficients caractérisant la fonction de collage. La caractérisation de WM est réalisée par la détermination des valeurs d'amplitude des cosinus, représentés par une matrice, et du décalage b, représenté par un scalaire. Ces valeurs doivent minimiser l'erreur de collage E entre S' et D. L'expression à minimiser est donc la suivante: minE = min E(S'i- Di)2 i e[O;card(D)[ Le minimum de cette erreur E, strictement positive, peut être obtenue pour les coefficients ckl et b qui annulent la dérivée de E. Le problème se traduit donc par la résolution du système suivant de (No2 + 1) lignes et (NC2 + 1) inconnues: I,2 2788655 oE2 dE =0 dcoo dE =0 ojj -= dcCN-l;Vc -1 dE = o o9b Après développement des expressions, ce système peut se réécrire sous la forme d'un système linéaire matficiel: Ao.........40, A.o............. * A4,. Bo A0. xo ( CO A|. BAo o :;- : s -- "' AN' j, -I v,- b B. - tAoo,40v ' Ai,. o'/ -I.N O Ae d!:- (9;) est une matrice connue, définie comme suit k,= A,=_.S,,,,iZ. Ju, k/ViE[O..N,[,je[O..X[,ke[0..N,[,/e[0..N,.[ S, Sni l ?J V F ie [O..N.,j E [O..N,[[ AnoEO. ndD)( A,,j kt /??E|O,'ardt D) A,, - Sn*, " V i 6[O..N,.[1Ic [j,.,1,0 [ n[IO..card(D)l m61|0.., ard( g)[ Avo = card(D) En posant TJJ = cos(O, * m) * cos(O * n,) avec (m,;my) les coordonnées locales du m-ième pixel de D. O Be "?'"'- est un vecteur connu, défini comme suit |B,,,*o D,,*% " 1po,,iIO..., [ jE[o..N,f 1? 0 - rd 1), = IB...= D,, On peut résoudre ce système par différentes méthodes (méthode directe, méthode itérative, méthode de gradient,...). Notamment, on peut utiliser la méthode du pivot de GAUSS. De bons résultats de codage sont obtenus avec un nombre très réduit de coefficients. Deux ou trois fonctions oscillantes de base fournissent déjà de bons résultats. Bien sûr, plus ce nombre est important, meilleure est la qualité. Lors du décodage, il est possible de tenir compte d'un nombre inférieur de fonctions oscillantes. Cela permet de tenir compte de la capacité de traitement du récepteur, ou des besoins de l'utilisateur, mais également d'effectuer un décodage progressif (l'image étant tout d'abord reconstruite avec une qualité moyenne, puis progressivement affinée). Cela permet également d'obtenir une scalabilité (échelonnabilité) lors du décodage. La technique de l'invention peut être utilisée dans de très nombreux domaines et notamment la compression d'images, en particulier lorsque celle-ci présente quelques parties texturées. L'invention permet également la réalisation de zooms, par modification de la partition au décodage. L'invention s'applique également au traitement d'images dans des espaces de dimension supérieure à 2 (par exemple en vidéo (2D+t), images virtuelles (3D)). 14 2788655 REVENDICATIONS 1. Procédé de codage d'images mettant en oeuvre des systèmes de fonctions itérées (IFS), ledit procédé comprenant les étapes suivantes: * partitionnement d'une image I à coder en un ensemble de régions d'image, dites régions destination; * association à chacune desdites régions destination D d'une région source correspondante S et d'une fonction de collage w telles que w(S) soit une bonne approximation de ladite région destination D, ladite fonction de collage se décomposant en: * une fonction de collage spatial ws, agissant sur la position et/ou la géométrie de ladite région source S, afin de créer une région source décimée S; et * une fonction de collage massique wM, agissant sur le contenu de ladite région source décimée S, caractérisé en ce que ladite fonction de collage massique w, est une fonction oscillante. 2. Procédé de codage d'images selon la revendication 1, caractérisé en ce que ladite fonction de collage massique WM est une fonction harmonique. 3. Procédé de codage d'images selon la revendication 2, caractérisé en ce que ladite fonction de collage massique wm est une fonction cosinusoidale. 4. Procédé de codage d'images selon la revendication 3, caractérisé en ce qu'une région source transformée S' = w(S) est définie par: S-- w(Si) =; Ck% x S x cos(Oix) x cos(0kiy) + b o i est [kl'indice du è pixel de S', de coordonnées (i, [ O:' i est l'indice du i?éme pixel de S', de coordonnées (ix, i>); 2788655 est l'image de Si par ws; H. est un vecteur réel de RNC tel que 0H = 2z/2j; ck et b sont des coefficients caractérisant la fonction de collage 5. Procédé de codage d'images selon la revendication 4, caractérisé en ce que lesdits coefficients Ck, et b sont déterminés en recherchant les coefficients minimisant une erreur entre source et destination, ladite erreur s'écrivant: E =:(S'D,)2 iEO.card(D)[ avec: Card(D): nombre de pixels de D. 6. Procédé de codage d'images selon la revendication 5, caractérisé en ce qu'il met en oeuvre un système linéaire matriciel, dont les solutions sont déterminées à l'aide d'une des méthodes appartenant au groupe comprenant: méthode directe; méthode itérative; méthode de gradient. 7. Procédé de codage d'images selon la revendication 6, caractérisé en ce qu'il met en oeuvre une méthode directe par pivot de Gauss ou par Cholesky. 8. Procédé de codage d'images selon l'une quelconque des revendications 1 à 6, caractérisé en ce qu'en ce que ladite fonction de collage massique wM, est écrite sous la forme d'une combinaison de fonctions oscillantes, dont le nombre et/ou la fréquence et/ou l'amplitude est paramétrable. 9. Dispositif de codage d'images mettant en oeuvre des systèmes de fonctions itérées (IFS), comprenant: * des moyens de partitionnement d'une image I à coder en un ensemble de régions d'image, dites régions destinations D des moyens d'association à chacune desdites régions destination D d'une région source correspondante S et d'une fonction de collage w telles que w(S) soit une bonne approximation de ladite région destination D; ladite fonction de collage se décomposant en: * une fonction de collage spatial ws, agissant sur la position et/ou la géométrie de ladite région source S, afin de créer une région source décimée S; et une fonction de collage massique wM, agissant sur le contenu de ladite région source décimée S, caractérisé en ce que ladite fonction de collage massique w, est une fonction oscillante. 10. Procédé de collage, mis en oeuvre dans un procédé de codage et/ou de décodage de données numériques représentatives d'images, mettant en oeuvre des systèmes de fonctions itérées (IFS), ledit procédé de codage et/ou de décodage comprenant les étapes suivantes: * partitionnement d'une image I à coder en un ensemble de régions d'image, dites régions destination; * association à chacune desdites régions destination D d'une région source correspondante S et d'une fonction de collage w telles que w(S) soit une bonne approximation de ladite région destination D, ledit procédé de collage mettant en oeuvre une fonction de collage se décomposant en * une fonction de collage spatial ws, agissant sur la position et/ou la géométrie de ladite région source S, afin de créer une région source décimée S; et 17 2788655 une fonction de collage massique w,,M, agissant sur le contenu de ladite région source décimée S, caractérisé en ce que ladite fonction de collage massique w. est une fonction oscillante. 11. Procédé de décodage d'images codées à l'aide d'un procédé de codage mettant en oeuvre des systèmes de fonctions itérées (IFS), ledit procédé de codage comprenant les étapes suivantes * partitionnement d'une image I à coder en un ensemble de régions d'image, dites régions destination; * association à chacune desdites régions destination D d'une région source correspondante S et d'une fonction de collage w telles que w(S) soit une bonne approximation de laditerégion destination D, ladite fonction de collage se décomposant en: * une fonction de collage spatial ws, agissant sur la position et/ou la géométrie de ladite région source S, afin de créer une région source décimée S; et * une fonction de collage massique w,,, agissant sur le contenu de ladite région source décimée S, caractérisé en ce que ladite fonction de collage massique wM est une fonction oscillante, et en ce qu'on reconstruit lesdites images en effectuant au moins une itération de ladite fonction de collage appliquée à ladite région source S correspondante. 12. Procédé de décodage selon la revendication 1l 1, caractérisé en ce que la fonction de collage massique appliquée à ladite région source prend en compte un 18;t2788655 nombre de fonctions oscillantes inférieur ou égal à celui pris en compte lors du codage. 13. Support de données contenant des images codées selon un procédé de codage d'images mettant en oeuvre des systèmes de fonctions itérées (IFS), ledit procédé comprenant les étapes suivantes: * partitionnement d'une image I à coder en un ensemble de régions d'image, dites régions destination; * association à chacune desdites régions destination D d'une région source correspondante S et d'une fonction de collage w telles que w(S) soit une bonne approximation de laditerégion destination D, ladite fonction de collage se décomposant en: * une fonction de collage spatial ws, agissant sur la position et/ou la géométrie de ladite région source S, afin de créer une région source décimée S; et * une fonction de collage massique w., agissant sur le contenu de ladite région source décimée S, seules la position et/ou la géométrie desdites régions source S et desdites fonctions de collage étant stockées sur ledit support de données, caractérisé en ce que ladite fonction de collage massique wm est une fonction oscillante. 14. Application du procédé selon l'une quelconque des revendications 1 à 8 à au moins un des domaines appartenant au groupe comprenant les domaines suivants: * compression d'images fixes À compression d'images en mode " intra " dans un codeur vidéo; 19 2788655 * compression d'images, ou de partie d'images, texturées; * réalisation d'agrandissement (zoom) de zones d'images; * compression dans des espaces de dimension supérieure à 2.