2-1 Introduction

L'intérêt que présentent de nombreuses transformées pour comprimer l'information est de projeter le signal sur une base de fonctions orthogonales, c'est-à-dire de distribuer l’énergie de ce signal sur des composantes décorrélées entre elles. Il existe de nombreuses transformées orthogonales dont les propriétés différent.

On peut citer la transformée de Fourier (TFD), la transformée en Cosinus (TCD), en Sinus (TSD) et celle de Karhunen-LƖ e (KL) qui sont les plus connues et les plus utilisées, ainsi que les transformes de Haar et de Hadamard.

La transformée de Karhunen-Loeve est la transformée optimale au sens où. Elle condense le mieux l’énergie sur ses composantes. L'absence d'algorithme rapide lui fait souvent préférer la DCT qui dans de nombreux cas donne des résultats très comparables. Cependant l'absence de propriété de convolution rigoureuse . pousse l'utilisation de la DFT dans sa version rapide FFT. Ces transformées localisent bien l’énergie en fréquence mais sont tout à fait délocalisées en temps : elles n'admettent pas la non-stationnarité.

A l’opposé, les transformées de Haar et de Hadamard présentent une bonne localisation temporelle mais pas fréquentielle .

La transformée de Wigner-Ville qui n'est pas une transformée orthogonale, permet de prendre en compte la non-stationnarité du signal. Elle présente cependant plusieurs inconvénients majeurs : sa bilinéarité rend son inversion délicate  et comme il ne s'agit pas d'une projection sur une base de fonctions, le nombre de points de la transformée évolue comme  si  est le nombre de points du signal.

La transformée en ondelette définie par Y. Me er et J. Lemari est une transformation orthogonale qui admet la non-stationnarité, elle est bien localisée en fréquence et en temps et peut être obtenue par un algorithme rapide. Du fait de toutes ces propriétés nous avons retenu cette transformation, que nous décrivons dans le paragraphe suivant.

2-2 : Historique des ondelettes

Avant le début des années 80, les techniques préfigurant la théorie des ondelettes avaient déjà été introduites au sein de certaines communautés scientifiques. En dépit d’une perspective scientifique commune, chacun avait imaginé et développé le concept des ondelettes pour ses propres besoins, selon une technique particulière.

Ce n’est qu’en 1985 que Stéphane Mallat relie les communautés entre elles, puisqu’il découvre les relations étroites entre les Filtres Miroirs en Quadrature, les algorithmes pyramidaux utilisés en traitement numérique de l’image et les bases orthonormées d’ondelettes .

Ce rapprochement des communautés a dès lors relancé des travaux de recherche très actifs sur la théorie des ondelettes accompagnés de toutes sortes d’applications.

Les premières utilisations de l’ondelette comme outil d’analyse ou de codage sont ensuite arrivées très rapidement, ce qui montre l’intérêt de cette technique pour l’industrie. Le premier usage industriel qui en a été fait, fut l’archivage des empreintes digitales de la population américaine par le FBI. Un taux de compression de 90% sur les coefficients en ondelettes a été atteint autorisant un archivage qui restitue des images visuellement quasi sans pertes.

Cette importante application d’archivage des années 80 a ouvert la voie à l’élaboration d’un projet de standard en 1996 pour la compression d’images . Un circuit intégré de compression vidéo par les ondelettes a également vu le jour en 1997 .

Cette technique a donc vécu un passage de la recherche vers les applications industrielles particulièrement rapide.

2-3  Définition des ondelettes

Les ondelettes sont des fonctions générées à partir d'une fonction  par translations et dilatations. Grossmann et Morlet  ont introduit cette fonction  qui, dilatée d'un facteur d'échelle a et translatée d'un temps b permet d'analyser un signal, de le manipuler puis de le resynthétiser.

…….….(2.1)

Ici, nous considérons que t est une variable monodimensionnelle.

L’ondelette mère, ainsi que sa transformée de Fourier, doivent être bien localisée. De plus la condition suivante doit être satisfaite :

……………………………………(2.2)

Cette condition entraîne que l'ondelette est oscillante (au moins quelques oscillations).

L’idée principale de la transformée en ondelette est de représenter une fonction f quelconque comme une superposition d'ondelettes. De plus, cette transformée contracte et dilate l'axe des temps ce qui permet d'introduire la notion d'échelle ou de résolution.

Y. Meyer a montré qu'il existait des fonctions telles que pour  et  les  constituent une base orthogonale de:

 ….(2.3)

C’est un sous ensemble de ces fonctions que nous utilisons dans ce chapitre.

Les coefficients d’ondelette sont alors calculés par :

……………....(2.4)

Et :

………………………………………..…(2.5)

De façon à introduire la notion de multi résolution, on définit aussi une fonction d’échelle. Comme pour la fonction  on a :

 …………..(2.6)

Ces fonctions, forment une famille orthogonale pour j fixé. Elles possèdent la priorité suivante :

 ………………….………...(2.7)

Ce qui entraîne   que l'ondelette associée suit la relation :

………….……..(2.8)

On a donc, en projetant sur cette famille de fonctions  une approximation du signal à la résolution. La perte d'information, lors du passage d'une résolution à une résolution  plus grossière, est alors décrite par les coefficients définis précédemment. Des exemples de fonction d'échelle et d'ondelette (ondelette de Meyer) sont présentés dans les figures 1 et 2.

2-4 :Mise en œuvre algorithmique sur des signaux échantillonnés

Les  signaux d'images que nous utilisons en pratique sont des signaux échantillonnés. Les échantillons de ces signaux d'origine sont considérés comme les coefficients d'approximation de plus grande résolution; cette résolution est déterminée par la fréquence d'échantillonnage des signaux.

Soient  et des filtres tels que :

……………..(2.9)

…………(2.10)

L'algorithme de décomposition multi-résolution d'un signal est alors décrit par la formule (2.9) et la figure 3 (pour de plus amples informations ).

…………………………(2.11)

………………………….(2.12)

I. Daubechies a montré que les coefficients  correspondent aux coefficients de la formule (5) [18]. La condition nécessaire et suffisante pour avoir une base orthogonale d'ondelettes est alors :

…………………(2.13)

………………….…….(2.14)

La valeur 2 est due au coefficient de normalisation, H et G sont les transformées de Fourier respectives des filtres h et g. Ces 2 filtres orthogonaux H et G, de somme constante, décomposent le signal en deux sous-bandes. Ceci correspond bien aux Conjugate Quadrature Filters (CQF) introduits par Smith et Barnwell .

Ces filtres, utilisés aussi pour la synthèse du signal, donnent alors une reconstruction exacte :

…..…(2.15)

Cependant, la décomposition sur une base d'ondelettes orthogonales permet, par rapport aux filtres CQF à reconstruction exacte, de transcrite le signal à décomposer comme une superposition d'ondelettes relativement douces. Ceci se traduit par la possibilité de choisir la régularité de l'ondelette. En effet, cette condition de régularité n'est pas satisfaite habituellement par les filtres reconstruction exacte utilisés dans les algorithmes de codage en sous-bande.

Se référant aux travaux de Smith et Barnwell et I .Daubechies, il n'existe pas de filtre symétrique (à phase linéaire), à support compact, permettant la reconstruction exacte en conservant la condition d'orthogonalité. La mise en œuvre de filtres CQF courts à phase non linéaire pour le codage d'images conduit de mauvais résultats (importance de la phase en traitement d'image). Les seules solutions acceptables en codage d'image sont, soit une solution approchée à filtres symétriques courts par Quadrature Mirror Filters (QMF), soit un filtre CQF de longueur infinie à reconstruction  exacte (Ondelette de Meyer). C'est cette deuxième solution, c'est-à-dire l'utilisation de l'ondelette de Meyer, que nous avons retenu.

2-5  Problèmes de bord 

Le filtrage numérique pose toujours des problèmes de bord dus à la longueur spatiale du filtre. La convolution que l'on est amené à effectuer ici est délicate du fait de la longueur de l'ondelette dont le support n'est pas compact et de la volonté de ne pas perdre d'information sur les bords de l'image.

Compte tenu du grand nombre de convolutions à effectuer nous avons choisi, pour réduire la charge de calcul, la méthode qui consiste à effectuer le produit des transformées de Fourier. Cela présente encore deux a avantages : G et H sont définis en fréquence et sont périodiques par construction; en effet ces filtres correspondent aux transformées de Fourier de g et h.

L'algorithme de Fast Fourier transform (FFT) suppose la périodicité à la fois en espace et en fréquence, il génère donc des signaux périodiques. L'image, lors de la transformation par FFT, est supposée périodique, ce qui n'est bien sûr pas le cas général.

Considérons par exemple une ligne de l'image; la valeur de l'intensité des pixels est notée  où  représente l'indice de colonne :

Il existe en général une discontinuité si en considérant la périodicité, on fait suivre, de  Cette discontinuité introduit de nombreuses fréquences parasites, lors de la FFT, qui perturbent l'algorithme de reconstruction .

Une solution que nous avons déjà préconisée ,  est de symétriser la ligne de la manière suivante :

Cette nouvelle ligne est obtenue par recopie des valeurs de pixels de  à. La valeur du point z supplémentaire est interpolée, par exemple de manière polynomiale. La périodisation de cette ligne n'introduit plus de discontinuité sur le signal. On obtient ainsi une ligne de longueur (2 N). Du fait de la propriété de symétrie qui a été imposée, la transformée de Fourier de la ligne est symétrique et réelle, ce qui n'augmente pas le nombre de données à  traiter. Ce prétraitement est effectué sur toutes les lignes et les colonnes lorsque cela est nécessaire.

2-6 : Discrétisation, Algorithmes de la Transformée en Ondelettes

Le traitement numérique des données nécessite la discrétisation de l'analyse en ondelettes, et le principal problème est sans doute la reconstruction du signal.

Plusieurs approches d'une analyse en ondelettes discrète ont été élaborées. Par exemple celle associée à la décomposition de Littlewood-Paley, de Burt et Adelson, et plus récemment l'analyse en multirésotution introduite dans la théorie de S- Mallat. Mais d'une manière plus générale, les bases d'interpolation dans   permettent de bien décrire l'analyse en ondelettes discrète .

2-6-1 : Algorithme de S. Mallat

2-6-1-1 : Analyse en Multirésolution

La théorie de l'analyse en multirésolution  développée par Y. Meyer et S.Mallat permet d'exprimer une fonction S de L2 comme une suite d'approximations successives. Ces approximations n'ont pas la même résolution. L'analyse s'effectue alors en calculant ce qui diffère d'une résolution à l'autre, c'est à dire tes détails qui permettent d'accéder à une représentation d'une qualité meilleure. Cette décomposition conduit à un algorithme général permettant une reconstruction qui conserve le nombre des échantillons du signal.

2-6-1-2 : Ondelettes Associées à l'Analyse en Multirésoiution

Les fonctions  et   , approximations de la fonction  aux résolutions  et , ne sont pas identiques. La perte d'information correspond aux détails de la fonction  qui ne peuvent être restitués par  mais qui sont présents dans , La différence entre les deux fonctions correspond à une projection de   sur un sous-espace vectoriel , complémentaire de , dans et orthogonal à .

Pour décrire te signal détail, on introduit une fonction  (fonction d'ondelettes) conduisant aux bases de , par translation et dilatation. On pose:

   …………………..(2.16)                                                            

L'ensemble des fonctions forme une base orthonormée de . On peut décomposer toute fonction de  sur  telle que :

…….(2.17)

Les coefficients  se calculent par simple convolution avec le filtre discret g défini par  et tel que:

………………………………………..…….(2.18)

    ……………………………………….……(2.19)                                            

…………………………………….…….(2.20)

Les filtres  et  sont dits filtres miroir conjugués.

En convolant la fonction  par  et  on obtient respectivement la fonction S. et le signal détail  En itérant sur , on peut ainsi calculer la transformée en ondelettes de la fonction  (Fig.2.4).

Fig 2.4 Passage d'une Résolution à la Suivante

2-6-1-3 : Reconstruction

Les ensembles de fonctions forment une base orthogonale de . D'où l'on peut écrire:

En prenant le produit scalaire:

On passe d'une résolution à une autre en écrivant:

    On reconstruit la fonction en mettant des zéros entre chaque échantillon de  et  et en convoluant les signaux obtenus par les filtres  et  respectivement (Fig2.5).

Fig 2.5 Passage d'une Résolution à la Précédente

2-6-1-4 : Extension de l'Analyse en Multirésolution à deux Dimensions

L'analyse en multirésolution est liée au concept d'échantillonnage. Son extension à des fonctions de  s'effectue de manière naturelle par séparation des variables. Le sous- espace , correspondant à la résolution , est le produit tensoriel des sous-espaces  et

                                                       (3.14)

La base d'interpolation est de la forme:

                                                            (3.15)

Le signal est convolué par les filtres  et . Les fonctions échantillonnées obtenues sont décimées d'un point sur deux. On itère sur les signaux basse fréquence, jusqu'au dernier échantillon. Pour restaurer, on intercale un zéro entre chaque échantillon dans les signaux bas et haute fréquences. On convolue avec les filtres  et . On additionne puis on multiplie par 4. On itère jusqu'à la plus grande résolution,

Le passage de la résolution    à la résolution se fait par:

Le signal détail appartient au sous-espace , complémentaire de  dans  , et est contenu dans les trois sous-images correspondant respectivement aux ondelettes verticale, horizontale et diagonale. La transformée en ondelettes peut être interprétée comme la décomposition sur un ensemble de voies fréquentielles [49] orientées spatialement (Fig. 3.3).

La restauration s'effectue par:

Fig.2.6: Présentation de la TO d’une Image

   Conclusion

Dans ce chapitre, on a défini la transformée en ondelettes discrète mathématiquement, et on a vue comment elle est utilisée pour le traitement de signal que se soit unidimensionnel ou bien bidimensionnel, notamment pour ce dernier ou on a vu comment se fait la décomposition en détails.