Memoire Online - Compression d'images fixes: comparaison des méthodes par transformations en ondelettes et celle par curvelets

Nous avons vu comment, de l'analyse de Fourrier, en passant par l'analyse de Gabor, nous sommes aboutis à l'analyse par ondelettes. La transformée de Fourrier malgré ses inconvénients a connu un succès dans plusieurs domaines d'applications (compression des images à travers la norme JPEG, le débruitage des signaux et plusieurs autres domaines) et, doit son succès à sa capacité à bien décrire un grand nombre de signaux (tous les signaux stationnaires en fait) et à être implantée dans un système réel très efficacement. La transformation en ondelettes, elle aussi, a connu un grand succès qui repose sur le même type d'arguments. Précisons ici que la transformée en ondelettes a une ambition bien plus grande que celle de la transformée de Fourrier car la classe des signaux qu'elle vise à décrire, c'est-à-dire les signaux non stationnaires, est d'une bien plus grande diversité mais demeure dans certains cas moins efficace. Une particularité fondamentale pour classer les ondelettes est leur degré de redondance. La transformée en ondelettes continue est par construction très redondante mais la transformée en ondelettes discrète peut ne pas l'être et l'absence de redondance est même recherchée dans des applications comme la compression d'images.

CHAPITRE III : BASES D'ONDELETTES ORTHOGONALES DE HAAR : APPLICATION A LA COMPRESSION D'UNE IMAGE FIXE

Nous avons vu au chapitre précédent qu'il existe plusieurs familles d'ondelettes caractérisées chacune par l'ondelette mère ip(t). Le tableau1 présente les plus courantes et leurs spécificités. Pour évaluer la transformée en ondelettes dans le domaine de la compression d'images fixes, notre choix porte sur l'analyse par ondelettes de Haar.

Le choix de l'ondelette résulte en fait d'un compromis entre son support et son nombre de moments nuls ; plus son support est petit, moins nombreux seront les gros coefficients affectées par une irrégularité d'un signal. D'un autre côté, prendre une ondelette avec beaucoup de moments nuls permet d'avoir des coefficients de petites échelles sur les parties régulières du signal. Or favoriser l'une de ses propriétés se fait au détriment de l'autre.

INTRODUCTION

Dans ce chapitre, nous nous restreignons à l'étude des ondelettes orthogonales qui sont un cas particulier des ondelettes discrètes. Ce type d'ondelettes est extrêmement utile en pratique car les ondelettes orthogonales sont non redondantes (la non redondance est à la fois bénéfique pour la rapidité de calcul de la transformation et pour les performances en terme de taux de compression) et leur inversibilité est assurée. Dans le chapitre précédent nous avons vu qu'il est "facile" de construire une transformation en ondelettes continue puisqu'il il suffit de trouver une fonction de moyenne nulle (l'ondelette mère). Par contre, il est beaucoup plus difficile de trouver des ondelettes orthogonales. Les travaux pionniers dans cette recherche sont ceux de J. Strömberg (1981) et ceux de Y. Meyer (1985). Dans ces travaux, des exemples de bases d'ondelettes orthogonales sont proposées mais aucune méthode générique pour trouver de telles bases n'a alors été proposée. C'est précisément là que l'analyse multirésolution (AMR) entre en scène. L'une des vertus de l'analyse multirésolution est de produire "facilement" des bases d'ondelettes orthogonales. C'est en voulant expliciter le lien entre les algorithmes pyramidaux du traitement d'image et la théorie des ondelettes que Stéphane Mallat a mis au point l'analyse multirésolution. Deux autres vertus de l'AMR est qu'elle est très adaptée à décrire certaines situations physiques telles que celles rencontrées en

CHAPITRE III : BASES D'ONDELETTES ORTHOGONALES DE HAAR : APPLICATION A LA COMPRESSION D'UNE IMAGE FIXE

traitement d'image où l'information est répartie à des échelles qui peuvent être très différentes, et elle se prête naturellement à une implantation rapide.

I. ANALYSE MULTIRESOLUTION

Soit un ensemble de sous-espaces de L²(R) (l'ensemble des signaux à énergie finie) tel que : ...c V2 c V1 c V0c V-1c...c _Vj+1 c Vjc...

L'analyse multirésolution a été définie par Mallat. L'idée est de projeter un signal f(t) E L²(R) appartenant à un espace Vj sur un sous-espace _Vj+1 et un sous-espace _Wj+1 dans le but de réduire la résolution de moitié. Le schéma est donné en figure ci-dessous. Il existe donc deux opérateurs de projection Aj et Dj qui projettent respectivement le signal f(t) sur _Vj+1^et Wj+1. Vj+1 est le sous-espace d'approximation et _Wj+1 le sous-espace de détails. On peut démontrer qu'il existe une fonction d'échelle =(t) E L²(R) qui engendre par dilatation et translation une base orthonormée de _Wj+1. Les espaces obtenus ne sont pas quelconques, ils possèdent des propriétés intéressantes. Par construction, les espaces d'approximation _Vj+1 et de détails Wj+1 sont supplémentaires : Vj = Vj+1g Wj+1.

V1		W1
V2	W2

CHAPITRE III : BASES D'ONDELETTES ORTHOGONALES DE HAAR : APPLICATION A LA COMPRESSION D'UNE IMAGE FIXE

Les fonctions de bases dilatées sont données par les relations : (Di_,n(t)=2^-i/2(D(2^-it-n) avec nEZ et yri_,n(t)=2^-i/2yr(2^-it-n) avec nEZ .

On a donc Aif= < f, (Di,n> (Di,n et Dif=?_n < f, yrin > yri,n où < f(t), g(t) > désigne le produit scalaire n de f(t) par g(t) : < f(t), g(t) > = f00 ₀₀₀₀ f(t)g(t)^GGGGGGd_t

Puisque les fonctions utilisées appartiennent toutes à L²(R), on a g(t)^GGGGGG=g(t). On pose

ai,n= < f, (Di,n> ^et di,n= < f, _-th,n >. _ai,n^et_di,n sont respectivement les coefficients d'approximation et de détails de la transformation en ondelettes de la fonction f.

I.1 APPLICATION DE L'AMR A L'ALGORITHME D'ANALYSE DE HAAR POUR

Considérons un signal échantillonné régulièrement sur [0;1] en 2^P points, on note ces points

xk =	z On associe à cet échantillon une fonction f définie par f (x)= (fk si x E [xk; xk+1[ k 0 sinon

Quand cet échantillonnage varie, la fonction f décrit l'ensemble E_p des fonctions constantes sur chacun des intervalles, et nulles en dehors de l'intervalle [0,1[. E_p est un sous-espace vectoriel de l'espace vectoriel des fonctions réelles à valeurs réelles. De plus, quand on fait varier p, les espaces E_p sont emboîtés, c'est à dire que E0 c E1 c...c _EP+1 c.... Leur réunion est donc encore un sous-espace vectoriel E de l'espace vectoriel des fonctions réelles à valeurs réelles.

On munit l'espace vectoriel E du produit scalaire définit par : (fIg) = fô f(x)g(x)dx Pour obtenir une base de E_p, il suffit de considérer les fonctions (p_p,kdéfinies par :

En effet, par définition même de E_p, toute fonction f de E_p se décompose de façon unique sous la forme. f = _EXp o1 fk(pp,k. Ces fonctions (pp,k peuvent s'écrire sous la forme (pp,k (x) ⁼(p(2pX - K), où (p est définie par (p :

Cette base est orthogonale, en effet on remarque que ((pp,kI(pp,k^')=⁰ si k ? k' et

CHAPITRE III : BASES D'ONDELETTES ORTHOGONALES DE HAAR : APPLICATION A LA COMPRESSION D'UNE IMAGE FIXE

}vw,l~vw,l^'= m ~ et. Il s'ensuit que la base des vw,lest orthogonale. Les espaces E_p sont alors

des espaces euclidiens. On considère le supplémentaire orthogonal F_p de E_p dans _Ep+1. Ainsi on a E_p = E1 € F0 € ...€ _Fp-1 pour tout p. Cette décomposition sert à définir la tendance grossière d'un signal E0, et ses détails à des résolutions de plus en plus fines (F0,F1,...).

A partir de cette fonction, on définit les fonctions Øp,k par Øp,k = Ø(2px-k) De même que dans le paragraphe précédent, }vw,l~øw,l^à = 0 si k ? k' et, }vw,l~øw,l = 0 car f_o^l (2wx - e) ø(2x - k)dx = 0. On en déduit que la famille qui réunit les vw,let ^lesøw,l(0 OE e OE 2w - 1) est une base orthogonale de _Ep+1, donc les Øp,k forment une base orthogonale de l'espace F_p de E_p dans _Ep+1 et on a le résultat fondamental suivant :Pour tout pç 1, la famille ~øw,l~~élé~m0~est une base orthogonale de F_p. De plus, }øw,l~øw,l = ~ 2m. Nous pouvons désormais calculer les coefficients d'ondelettes associés à un signal s_p y E_p. Il

Pour les mêmes raisons, }vw,l~vw,1,l' = 0 et }vw,l~øw,1,l' = 0 si x ' «2k^N, 2k^N + 1» et

Ceci permet de déterminer facilement la décomposition de s_p y E_p sur la base des vw^,1,l et øw^,1,l. En effet, si s_p = sp-1+ d_p alors l'orthogonalité de la base implique

CHAPITRE III : BASES D'ONDELETTES ORTHOGONALES DE HAAR : APPLICATION A LA COMPRESSION D'UNE IMAGE FIXE

L'intérêt est que l'on passe d'un échantillon de taille 2^pà un échantillon principal de taille 2p-1 et un échantillon de taille 2^p-1en utilisant que des sommes ou des différences.

Si le signal est régulier, les valeurs des échantillons successifs seront proches. Les coefficients de détails issus de la différence de deux valeurs consécutives de l'échantillon seront donc petits. En s'imposant une précision F, on ne gardera que les coefficients d'ondelettes supérieurs en valeur absolue à F.Ceci permet une compression du signal.

Voici l'algorithme utilisé : on reçoit un signal de la forme s(p) = ? Fw,lvw,l

décompose en s_p= sp-1+ dp-1 et on transforme _dp-1^end^Gp-1, d^Gp-1 = ? ~m^èê,~ dG p-1,køw,1,l avec d^Gp-

1,k = dp-1,k si ~d^,l,z~ ç F et dp-1,k = 0 sinon . On recommence ensuite le procédé avec le signal sp-1.

CHAPITRE III : BASES D'ONDELETTES ORTHOGONALES DE HAAR : APPLICATION A LA COMPRESSION D'UNE IMAGE FIXE

Décomposition et approximation d'une image selon l'algorithme de Haar Présentation de l'algorithme

Une image en noir et blanc peut être considérée comme un ensemble de pixels, chaque pixel représentant un niveau de gris. On peut modéliser cette image par une matrice carré de taille égale à la résolution de l'image. Pour une image en couleur, il suffit de considérer trois images, chacune représentant le niveau de rouge, de vert et de bleu de l'image originale.

Pour mettre en application la méthode de Haar on pourrait considérer la matrice comme un échantillonnage en mettant ses lignes bout à bout. Cependant on perd le lien avec les colonnes. Il est donc plus efficace d'appliquer l'algorithme de Haar aux lignes de la matrice puis à ses colonnes. Cet algorithme de différentiation-sommation se traduit par la multiplication matricielle à l'aide d'une matrice contenant beaucoup de 0.

La décomposition d'un signal 2D tel qu'une image selon l'AMR ce présente comme suit :

CHAPITRE III : BASES D'ONDELETTES ORTHOGONALES DE HAAR : APPLICATION A LA COMPRESSION D'UNE IMAGE FIXE

Figure 8 Décomposition et approximation de l'image de lenna sous MATLAB selon Haar

Compression d'images fixes: comparaison des méthodes par transformations en ondelettes et celle par curvelets

CHAPITRE II : DE L'ANALYSE DE FOURRIER A L'ANALYSE PAR ONDELETTES

CONCLUSION

CHAPITRE III : BASES D'ONDELETTES ORTHOGONALES DE HAAR : APPLICATION A LA COMPRESSION D'UNE IMAGE FIXE

INTRODUCTION

I. ANALYSE MULTIRESOLUTION

I.1 APPLICATION DE L'AMR A L'ALGORITHME D'ANALYSE DE HAAR POUR