Ondes Cours

TIPE: Introduction à la théorie des ondelettes
Xavier Friederich et Gaétan Bahl

5 juin 2014
Table des matières

1 L’analyse de Fourier, outil certes efficace mais insuffisant 5
1.1 Le cas des signaux périodiques : l’utilisation des séries de Fourier . . . . . . . . . . . . . . . . 5
1.2 L’utilisation de la transformée de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Définition de la transformation de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Propriétés de la transformation de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Transformée inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.4 Ce qu’apporte la transformée de Fourier d’un signal . . . . . . . . . . . . . . . . . . . 7
1.2.5 Exemples de transformée de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.6 Application de la transformation de Fourier . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Transformée de Fourier Discrète ou TFD et limites . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Des applications de la TFD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.3 Des limites à la Transformée de Fourier Discrète . . . . . . . . . . . . . . . . . . . . . 10
2 Premières définitions 11
2.1 Définition 1 : Ondelette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Exemples d’ondelettes mères : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Ondelette de Haar : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Ondelette ”chapeau mexicain” : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.3 Ondelette de Morlet : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Transformation en ondelettes 13
3.1 Transformation en ondelette continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Transformation en ondelettes discrète. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 Comparaison avec la transformation de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 La théorie de l’analyse multirésolution, un outil pour la construction de bases d’onde-

lettes 16
4.1 Définition d’une analyse multirésolution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Intéret d’une analyse multirésolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5 Algorithme de décomposition en ondelettes de Stéphane Mallat (1989) 17

5.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 Démonstration dans un cas simple : le cas des ondelettes de Haar. . . . . . . . . . . . . . . . 17
5.2.1 Introduction et définition des notations . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2.2 Propriété mathématique : Orthogonalité dans les espaces euclidiens . . . . . . . . . . . 18
5.2.3 Utilisation de la propriété : décomposition orthogonale en somme directe. . . . . . . . 19
5.2.4 Étape principale de l’algorithme : passage à la résolution inférieure, détermination des
coefficients à la résolution inférieure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.3 Schématisation de l’algorithme de Mallat (compression d’un signal Ψp par des ondelettes) . . 22
5.4 Représentation matricielle de l’algorithme utilisant les ondelettes de Haar . . . . . . . . . . . 23
5.4.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1
Introduction à la théorie des ondelettes Xavier Friederich et Gaétan Bahl
6 Application à la compression des données 24
7 Utilisation pratique de la transformation par ondelettes discrète 24

7.1 Le choix des outils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.1.1 Le langage : Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.1.2 La librairie de traitement d’image : PIL . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.1.3 La librairie d’interface graphique : Tkinter . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.1.4 La librairie de calcul parallélisé : PyOpenCL . . . . . . . . . . . . . . . . . . . . . . . 25
7.1.5 Le module time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.1.6 Le module struct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.1.7 Le module socket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.2 L’algorithme matriciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
7.3 Exemples d’images traitées avec notre algorithme . . . . . . . . . . . . . . . . . . . . . . . . . 27
7.4 L’application graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.5 L’algorithme fasthaar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.5.1 Fonctionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.5.2 Coût et Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7.6 Transferts et échanges d’images par le réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
7.6.1 But du programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
7.6.2 Processus d’archivage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
7.6.3 Processus de restauration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
7.7 Optimisation : utilisation de l’accélération matérielle avec OpenCL . . . . . . . . . . . . . . . 37
7.7.1 L’accélération matérielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
7.7.2 Haar et OpenCL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
7.7.3 Performances réelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
8 Description du code 40
8.1 Le fichier ondelettes.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
8.1.1 La classe Matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
8.1.2 La classe MatriceImage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
8.2 Le fichier ondelettesGUI.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
8.2.1 La classe Appli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
8.2.2 La classe DialogScale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
8.2.3 La fonction main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8.3 Le fichier bench.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8.3.1 La fonction image gen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8.3.2 La fonction randomize . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8.3.3 La fonction bench square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8.3.4 La fonction fasthaar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8.3.5 La fonction main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8.4 Le fichier serveur.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8.4.1 La fonction main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8.4.2 La fonction recvImage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8.4.3 La fonction fasthaar srv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.4.4 La fonction sendCoef . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.5 Le fichier client.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.5.1 La fonction main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.5.2 La fonction sendImage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.5.3 La fonction askcompress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.5.4 La fonction storeImage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.5.5 La fonction askcoeff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
8.6 Le fichier ondeletttesCL.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
8.6.1 La classe Climage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
8.6.2 Les fonctions gettl, gettr, getll et getlr . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2
8.6.3 La fonction execute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

8.6.4 La fonction save . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
9 Conclusion 45
10 Bibliographie, Liens et Remerciements 45
11 Annexes 46
11.1 Fichier ondelettes.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
11.2 Fichier ondelettesGUI.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
11.3 Fichier bench.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
11.4 Fichier serveur.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
11.5 Fichier client.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
11.6 Fichier ondelettesCL.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
11.7 Fichier haar.cl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
11.8 Images utilisées pour les performances de haar.cl . . . . . . . . . . . . . . . . . . . . . . . . . 62
11.8.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Table des figures

1 Illustration du théorème de Fourier pour les signaux périodiques . . . . . . . . . . . . . . . . 6
2 Spectre de Fourier en fréquence d’un signal périodique . . . . . . . . . . . . . . . . . . . . . . 7
3 Allure d’une gaussienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4 Spectre d’amplitude de la fonction Π . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5 Ondelette de Haar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6 Ondelette ”chapeau mexicain” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
7 Ondelette de Morlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8 Dilatation d’ondelette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
9 Translation d’ondelette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
10 Le graphe de la fonction W(a; b)(Π) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
11 Comparaison des méthodes de compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
12 L’algorithme matriciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
13 La transformation appliquée aux matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
14 L’image de départ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
15 Détail de l’image de départ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
16 Détail de l’image compressée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
17 Détail de l’image compressée à 100% . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
18 Fenêtre principale de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
19 Menus de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
20 Le sélecteur de seuil de compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
21 Fonctionnement de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
22 Tableau créé par l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
23 Tableau après l’étape 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
24 Tableau après l’étape 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
25 Tableau après compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
26 Tableau après synthèse sur les colonnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
27 Tableau après synthèse sur les lignes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
28 Tableau après synthèse sur les lignes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
29 Pixels avant et après traitement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
30 Coût temporel de l’algorithme fasthaar en fonction de la taille de l’image . . . . . . . . . . . 34
31 Processus d’archivage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
32 Processus de restauration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
33 Comparaison entre les architectures CPU et GPU . . . . . . . . . . . . . . . . . . . . . . . . . 37
34 Exécution de ondelettesCL.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3
35 Temps d’exécution de haar.cl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

36 Graphique d’activité du GPU lors du traitement de l’image 3 . . . . . . . . . . . . . . . . . . 39
37 Image 1 : 3 mégapixels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
38 Image 2 : 5 mégapixels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
39 Image 3 : 12 mégapixels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4
1 L’analyse de Fourier, outil certes efficace mais insuffisant

Les séries de Fourier (pour les signaux périodiques) et la transformée de Fourier (pour un signal quel-
conque) ont longtemps été les outils essentiels de l’analyse harmonique.
Le but de cette première partie est de présenter brièvement l’analyse de Fourier et de montrer ses limites.
1.1 Le cas des signaux périodiques : l’utilisation des séries de Fourier

Considérons f fonction 2π-périodique de classe C 1 par morceaux.
Notons Sp (f ) la p-ième somme partielle de Fourier de f , ou p-ième somme partielle de la série de Fourier de
f.
On a :
Xp
Sp (f ) = cn (f )eint
n=−p
en notation exponentielle ou bien

p
a0 X
Sp (f ) = + (an (f ) cos(nt) + bn (f ) sin(nt))
2 n=1
en notation trigonométrique ;
les an et bn étant donnés par les relations
Z 2π
1
an = f (t) cos(nt)dt
π 0
Z 2π
1
bn = f (t) sin(nt)dt
π 0
Le cours de mathématiques (plus particulièrement le théorème de Dirichlet) nous donne alors le résultat bien
connu suivant, avec les hypothèses sur f données plus haut :
f est somme de sa série de Fourier, ce qui se réécrit de la façon suivante :

+∞
a0 X
∀t ∈ R, f (t) = + (an (f ) cos(nt) + bn (f ) sin(nt))
2 −∞
On peut ainsi très facilement décomposer un signal périodique en une somme infinie de sinusoı̈des.
5
Figure 1 – Illustration du théorème de Fourier pour les signaux périodiques
Le signal ”carré” en noir est la somme de toutes les sinusoı̈des représentées, la sinusoı̈de rouge d’amplitude
majeure étant appelée fondamentale et les autres sinusoı̈des étant les harmoniques.
Bien évidemment, la plupart des signaux que l’on peut rencontrer sont non-périodiques et il est impossible
d’obtenir une décomposition analogue à celle décrite ci-dessus. Dans le cas général et dans la limite de la
possibilité de le faire, on effectue une transformation de Fourier.
1.2 L’utilisation de la transformée de Fourier

Il est nécessaire dans le cas plus général de fonctions/signaux non nécessairement périodiques de passer
d’une écriture discrète en uneécriture en somme continue.
Le cadre le plus naturel pour définir les transformations de Fourier est celui des fonctions f intégrables 1 .
On note alors traditionnellement L1 (R) l’ensemble des fonctions intégrables sur R et L2 (R) l’ensemble des
fonctions de carré intégrable sur R.
1.2.1 Définition de la transformation de Fourier

On appelle transformation de FourierZl’application notée F qui, à toute fonction f de L1 (R), associe la
∞
1
fonction fˆ telle que ∀ω ∈ R,fˆ(ω) = √ f (t)e−iωt dt
2π −∞
fˆ est appelée transformée de Fourier de f .
Notons toutefois que l’on peut donner plusieurs versions de définitions : nous avons ici choisi la définition
plus ”physicienne”, car on y voit directement les paramètres de temps (t) en s et de pulsation (ω) en rad.s−1 .
Notons aussi qu’il est possible de définir la transformée de Fourier pour des fonctions qui ne sont pas forcément
dans L1 (R).
1.2.2 Propriétés de la transformation de Fourier

— F est clairement linéaire.
R
1. continues par morceaux et telles que ∃M ∈ R, ∀I ⊂ R, f (x) ≤ M
I
6
— On peut montrer que F conserve la parité.
— Propriété de translation :
Soit a ∈ R et f ∈ L1 (R) de la variable t. En effectuant le changement de variable u = t − a, on obtient
la transformée de Fourier de la fonction d’expression f (t − a). En effet :
Z ∞ Z ∞
F[f (t − a)] = f (t − a)e −iωt
dt = e −iωa
f (u)e−iωu du = e−iωa .fˆ(ω)
−∞ −∞
1.2.3 Transformée inverse

On utilise les mêmes notations que précédemment. Si fˆ est elle-même une fonction intégrable, la formule
dite de transformation de Fourier inverse, opération notée F −1 , et appliquée à fˆ, permet (sous conditions
appropriéees) de retrouver f : Z ∞
1
f (t) = √ fˆ(ω)eiωt dω
2π −∞
Cette formule peut se démontrer facilement à partir de la formule sommatoire de Poisson.
1.2.4 Ce qu’apporte la transformée de Fourier d’un signal

Dans le cas général, la transformation de Fourier d’une fonction produit comme transformée une fonction
fˆ à valeurs complexes. Ainsi, on peut obtenir deux informations de cette transformée :
Le spectre d’amplitude : il s’agit du tracé du module de fˆ(ω) en fonction de la pulsation ω.
Le spectre de phase : il s’agit du tracé de l’argument de fˆ(ω) en fonction de la pulsation ω.
Notons que l’on rencontre très souvent en traitement du signal les spectres en fréquence ; on passe de la
1
pulsation ω à la fréquence par la relation de proportionnalité suivante : f = ω.
2π
On remarquera, comme le montre la figure ci-dessous, que le spectre d’amplitude d’un signal périodique
est formé de traits verticaux.
Figure 2 – Spectre de Fourier en fréquence d’un signal périodique
1.2.5 Exemples de transformée de Fourier

Facilement, on peut montrer que la transformée de Fourier d’une gaussienne 2 est une gaussienne.
Si on note Π la fonction porte définie par ∀t ∈ − 21 , 21 , Π(t) = 1 et ∀t ∈ R\ − 21 , 21 , Π(t) = 0, on obtient

eix − e−ix
directement par intégration de l’exponentielle complexe et en tenant compte de la relation sin x = ,
2i
−x2
2. une fonction en e 2 .
7
Figure 3 – Allure d’une gaussienne
F(Π)(ω) = sinc( ω2 ). 3
La fonction étant réelle, son spectre de phase correspond à la fonction nulle et son spectre d’amplitude est le
suivant :
Figure 4 – Spectre d’amplitude de la fonction Π
1.2.6 Application de la transformation de Fourier

En physique, la transformation de Fourier permet de déterminer le spectre d’un signal.
En traitement d’images, on effectue des transformations de Fourier à deux dimensions : si f est une
fonction de R2 , sa transformée de Fourier est définie par :
Z ∞Z ∞
fˆ(u, v) = f (x, y).e−i(ux+vy) dx dy
−∞ −∞
On comprendra que la très grande majorité des signaux sont numériques et que les définitions mathématiques
données jusqu’à présent ne sont pas adaptées au domaine du discret.
sin x
3. la fonction sinc (sinus cardinal) est au premier sens mathématique la fonction définie sur R* par sinc(x) = x
.
8
1.3 Transformée de Fourier Discrète ou TFD et limites

Bien évidemment, la transformée de Fourier telle qu’elle est utilisée dans un ordinateur (transformée de
Fourier discrète (TFD) possède une définition numérique différente de la définition mathématique donnée
plus haut.
1.3.1 Définition
Nous nous placerons dans le cas complexe (le cas réel en découle) sur un intervalle de temps fini corres-
pondant à N échantillons. Quand N tend vers l’infini, on peut penser que l’on s’approche du cas continu
mais il faut garder à l’esprit que la TFD suppose que le signal est périodique de période N .
Nous proposons la définition de la TFD d’un point de vue de l’algèbre linéaire, qui semble plus schématique :
On définit ainsi la TFD comme un endomorphisme de CN ayant pour matrice dans la base canonique de CN
1 jk
la matrice S de terme général sj,k = e−2iπ N , où j, k ∈ {0, 1, ..., N − 1}.
N
La TFD s’applique ainsi à des suites de longueur N (ou de période N) et on peut d’ailleurs remarquer
que la TFD est périodique de période N.
On obtient ainsi, en l’appliquant à un vecteur f = (f0 , ..., fN −1 ) de CN de matrice F ∈ MN,1 (C), le vecteur
g = (g0 , ..., gN −1 ) de matrice G = S× F .
On a clairement de la définition et du produit matriciel :
N −1
X 1 −2iπ jk
∀j ∈ {0, 1, ..., N − 1} , gj = e N f
k
N
k=0
En notant W l’inverse de la racine N -ième de l’unité 4 , il vient bien sûr :
N
X −1
∀j ∈ {0, 1, ..., N − 1} , gj = W kj fk
k=0
(1)
1.3.2 Des applications de la TFD

La TFD a plusieurs applications, parmi lesquelles :
1. L’analyse spectrale des signaux.

Il est intéressant pour un électronicien de mesurer par exemple la largeur de la bande de fréquence
occupée par la transmission d’un signal, ceci grâce à une analyse spectrale.
2. La compression de données.
On applique sur les signaux la TFD pour réduire leur complexité. La suite des coefficients obtenus (en
appliquant la formule (1) est alors quantifiée avec des pas de quantification plus élevés pour les hautes
fréquences, considérées comme négligeables pour la perception humaine. Le gain en compression vient
de la réduction de précision de ces coefficients (voire leur suppression totale) : cela nécessite de ce fait
moins de bits pour le codage.
2iπ
−
4. W = e N
9
3. La multiplication des grands nombres.

Certains des algorithmes les plus rapides (type FFT) pour la multiplication de grands nombres entiers
sont fondés sur la TFD.
Néanmoins, toutes ces applications nécessitent l’existence d’un algorithme rapide de calcul de la TFD et
de son inverse. Les multiplications dans les cas où N est petit sont ”triviales”, mais quand N devient grand
il est en effet indispensable d’utiliser un tel algorithme permettant de diminuer le nombre de multiplications.
1.3.3 Des limites à la Transformée de Fourier Discrète

La TFD présente des limites considérables.
On ne peut pas analyser un morceau de musique avec une TFD simple. En effet, on perdrait l’information
temporelle. Prenons par exemple deux signaux semblables :
1. un signal composé d’une sinusoı̈de à 100Hz pendant une seconde puis d’une sinusoı̈de à 200Hz pendant
une seconde
2. un second composé d’une sinusoı̈de à 200Hz pendant une seconde puis d’une sinusoı̈de à 100Hz pendant
la seconde suivante.
Leurs transformées de Fourier respectives seront identiques, ce qui est clair sur l’expression (1) (commu-
tativité de l’addition).
Par conséquent, la TFD n’est applicable que sur des signaux dont l’on sait que l’information fréquentielle est
la même partout.
En outre, l’algorithme FFT nécessite que N soit une puissance de 2 à cause de l’architecture récursive
du programme. De plus, les algorithmes type FFT que l’on programme ne sont pas toujours efficaces au
niveau de la mémoire et de la rapidité car on doit tenir compte des matrices et des nombres complexes que
le logiciel de programmation ne connaı̂t a priori pas.
On verra dans ce qui suit une transformation des fonctions/signaux plus performante, la transformation
par les ondelettes qui est capable de détecter les portions du signal qui varient plus rapidement que d’autres.
10
2 Premières définitions
La transformation en ondelettes est apparue pour la première fois dans le domaine de la géophysique vers
1980 pour l’analyse des données sismiques. Elle aura été formalisée par Morlet, Grassmann et Goupillard.
De manière analogue à la théorie des séries de Fourier, les ondelettes sont principalement utilisées pour la
décomposition de fonctions. La décomposition d’une fonction en ondelettes consiste à l’écrire comme une
somme pondérée de fonctions obtenues à partir d’opérations simples effectuées sur une fonction principale
appelée ondelette-mère. Ces opérations consistent en des translations et dilatations de la variable. Selon que
ces translations et dilatations sont choisies de manière continue ou discrète, on parlera d’une transformée
en ondelettes discrète ou continue. Le travail suivant fera l’objet du cas particulier de la transformation en
ondelettes unidimensionnelle.
2.1 Définition 1 : Ondelette

Une ondelette est d’un point de vue géométrique et schématique une forme d’onde, l’idéalisation d’une
note de musique, d’une durée limitée et qui a une valeur moyenne égale à 0.
Plus formellement, pour le cas d’une ondelette-mère (celle que l’on va pouvoir dilater et translater afin
d’obtenir les autres ondelettes définissant ainsi une famille d’ondelettes), il s’agit d’une fonction ψ de l’espace
de Lebesgue L2 (R) (espace des fonctions à valeurs dans C de carré intégrable) et telle que :
Z
ψ(t) · dt = 0
R
2
ce qui provient de la condition R |ψ̂(ω)|
R
|ω| dω < ∞ où ψ̂ est la transformée de Fourier de ψ, donnée par la
Z +∞
formule ψ̂(ω) = ψ(t) · e−2iπωt dt
−∞
Cette condition, dite condition d’admissibilité est nécessaire pour que la transformée en ondelettes d’une
fonction existe !
Si l’ondelette -fonction analysante- est convenablement choisie, la transformation en ondelettes est inver-
sible et la fonction peut être reconstruite après analyse suivant l’équation :
Z +∞ Z +∞
1
f= Cψ−1 2
hf, ψ a,b iψa, bda · db
−∞ −∞ a
Z ˆ 2
|ψ(ω)|
Le coefficient Cψ , si donc il existe, est donné par : Cψ = 2π dω < ∞
R |ω|
De manière plus « imagée », l’ondelette doit osciller localement autour de l’axe des abscisses. Il existe
une infinité de fonctions d’ondelettes car toute fonction oscillante localisée est une ondelette-mère possible.
Différentes familles d’ondelettes peuvent être utilisées en fonction du problème à résoudre. C’est un des
nombreux avantages de la transformée en ondelettes par rapport à la transformée de Fourier (qui est liée
exclusivement aux fonctions sinus et cosinus) que de pouvoir choisir l’ondelette à utiliser pour l’analyse.
2.2 Exemples d’ondelettes mères :

2.2.1 Ondelette de Haar :
H: [0, 1] −→
{−1;
( 1}
Il s’agit de la fonction 1 si x ∈ [0; 12 ]
x 7−→
−1 si x ∈] 12 ; 1]
On pourra remarquer que H est discontinue en 12 .
2.2.2 Ondelette ”chapeau mexicain” :

ψ : R −→ R
On peut définir cette fonction par 1 t2
t 7−→ √2 π − 4 (1 − t2 )e− 2
3
11
Figure 5 – Ondelette de Haar
Figure 6 – Ondelette ”chapeau mexicain”
2.2.3 Ondelette de Morlet :

ψ : R −→ R
On peut définir cette fonction par t2
t 7−→ cos(5t)e− 2
Figure 7 – Ondelette de Morlet
12
3 Transformation en ondelettes
La transformée en ondelettes est une transformée linéaire qui décompose un signal en fréquences en
conservant une certaine localisation spatiale. Concrètement, le signal de départ est projeté sur un ensemble
de fonctions de base qui varient en fréquence et en espace.
3.1 Transformation en ondelette continue

La transformée en ondelette continue utilise des dilatations et des translations de la fonction ondelette
mère.
Définition : produit scalaire

Soient f et g deux fonctions réelles ; on définit sur le R-espace vectoriel F (R,R) leur produit scalaire par
l’intégrale suivante :
Z
hf |gi = f (x)g(x)dx
R
Avec la condition d’admissibilité donnée en première page, la transformée en ondelette continue de la fonction
f est définie à facteur constant près comme le produit scalaire de f et de ψ.
Z +∞
1 t−b
W(a,b) (f ) = √ f (t) · ψ( ) · dt avec a ∈ R∗+ , b ∈ R
a −∞ a
Notons que a permet de donner l’échelle (c’est le coefficient de dilatation, de fréquence) et b détermine
la position de l’ondelette sur l’axe des temps.
√1 est le facteur de normalisation de l’énergie nécessaire pour que le signal transformé ait la même énergie
a
à toutes les échelles.
Ex : dilatation. L’ondelette verte a été dilatée à partir de l’ondelette rouge (ondelette-mère). On a b = 0

et a 6= 1.
Figure 8 – Dilatation d’ondelette
Ex : translation. L’ondelette verte a été translatée à partir de l’ondelette rouge (ondelette-mère). On a

b 6= 0 et a = 1.
13
Figure 9 – Translation d’ondelette
14
3.2 Transformation en ondelettes discrète.

La transformation en ondelettes discrète qui a été introduite par Morlet se construit à partir de « bases
» de fonctions du type :

1 t − t0
ft0 ,∆t (t) = √ f avec ∆t > 0, t0 ∈ R
∆t ∆t
∆t peut être choisi « géométriquement » ; les paramètres de translations t0 et ∆t sont proportionnels
(c’est-à-dire ∃k ∈ R, t0 = k · ∆t).
Une gamme d’échelles ∆t utilisée couramment est la gamme d’échelles dyadiques 21p
On a alors avec t0 = k · ∆t :
p p
ft0 ,∆t (t) = 2 2 f (2p · x − k), c’est-à-dire on peut considérer la famille d’ondelettes ψ k,p = 2 2 ψ(2p x −
k), (k, p) ∈ Z2
Il est intéressant de considérer des familles orthogonales d’ondelettes formant une base hilbertienne de
L2 (R) alors
Xtoute fonction f de cet espace peut s’écrire
f= fk,p ψ k,p où les fk,p = hf |ψk,p i sont appelés coefficients d’ondelettes.
(k,p)∈Z2
La transformation en ondelettes discrète est presque naturellement associée à des algorithmes plus efficaces
et plus rapides que des algorithmes du type FFT qui utilisent la transformée de Fourier.
Une famille d’ondelettes par exemple couramment utilisée dans la transformation en ondelettes discrète
est la famille infinie des ondelettes orthogonales de Daubechies : c’est une des familles d’ondelettes les plus
performantes.
Le graphique suivant (Fig.10), représentant l’application W(a; b) appliquée en la fonction (ou signal en
1D) f = Π (définie dans la première section de ce dossier) et utilisant l’ondelette mère de Morlet (définie
plus haut), illustre la richesse de la transformation en ondelettes continue.
A partir d’une ondelette mère, on peut créer une pluralité d’ondelettes ”filles” qui vont fournir, par rapport à
la transformation classique de Fourier, une plus grande précision dans le traitement des signaux de fréquences
constamment changeantes.
Figure 10 – Le graphe de la fonction W(a; b)(Π)
15
3.3 Comparaison avec la transformation de Fourier

Un des avantages de la transformation par les ondelettes (en comparaison avec la transformation de Fou-
rier), c’est que le fait de modifier ou de supprimer un des coefficients de la transformée d’un signal ne va en
rien dégrader le signal.
En outre, les algorithmes de transformation en ondelettes 2D s’appliquent à la totalité de l’image et non pas à
des blocs de pixels comme par exemple les algorithmes type FFT, ce qui permet d’éviter les carrés uniformes
lorsque le taux de compression est relativement élevé.
Enfin, l’utilisation d’une ondelette réversible permet une compression sans perte de données.
Figure 11 – Comparaison des méthodes de compression
La figure 11 montre les résultats de deux compressions de la même image de départ, l’une utilisant la trans-
formation de Fourier (à gauche), l’autre utilisant la transformation en ondelettes (à droite).
Enfin, le coût d’un algorithme utilisant les ondelettes, c’est-à-dire le nombre d’opérations à effectuer, est
en O(N ), ce qui est mieux que le coût des meilleurs algorithmes type FFT en O(N log N ).
4 La théorie de l’analyse multirésolution, un outil pour la construc-

tion de bases d’ondelettes
Pour construire des bases d’ondelettes orthonormées, les théoriciens Mallat et Meyer ont introduit la
notion d’analyse multirésolution.
4.1 Définition d’une analyse multirésolution.

Une analyse multirésolution est une suite {Vk }k∈Z de sous-espaces fermés de L2 (R) tels que :
— ∀(k, l) ∈ Z2 , f ∈ Vk ⇔ f (· − 2k l) ∈ Vk (propriété d’invariance par translation)

— ∀k ∈ Z, Vk+1 ⊂ Vk
— ∀k ∈ Z, f ∈ Vk ⇔ f ( 2· ) ∈ Vk+1
\
— lim Vk = Vk = Ø
j→∞
k∈Z
\
— lim Vk = Vk = L2 (R) où la notation Ā désigne l’adhérence de A.
j→−∞
k∈Z
— ∃φ, {φ(·−n)}n∈Z forme une base orthonormée de V0 . φ est appelée fonction d’échelle associée à l’analyse
multirésolution
16
4.2 Intéret d’une analyse multirésolution

La fonction φ permet notamment la connaissance de la suite {Vk }k∈Z et ainsi la déduction d’une base or-
thonormée de Vk pour tout k ∈ Z. On peut alors définir une ondelette associée à l’analyse multirésolution : il
s’agira de toute fonction ψ qui forme avec ses translatées entières une base orthonormée de W0 , supplémentaire
M
orthogonal de V1 dans V0 . En effet, il découle de la définition de Wk que L2 (R) = k∈Z Wk .
. − 2m n

1
Par suite, la famille √ ψ forme une base orthonormée de L2 (R).
2m 2m
Les espaces Wk pour k ∈ Z sont appelés espaces des détails. Ils ne forment pas une famille d’espaces
emboı̂tés mais les propriétés d’échelles et d’invariance par translation sont conservées. En effet, pour k ∈
M
Z, Wk−1 est orthogonal à Vk−1 , d’où Wk−1 orthogonal à Wk en vertu de l’égalité L2 (R) = k∈Z Wk .
5 Algorithme de décomposition en ondelettes de Stéphane Mallat

(1989)
5.1 Principe
C’est un algorithme linéaire qui fait appel à un sous-échantillonnage. Concrètement, on procède à une
décomposition par projections successives (c’est-à-dire de manière récursive) sur deux sous-espaces orthogo-
naux, l’un donnant l’allure générale de l’image (il s’agira de l’image en résolution moitié) et l’autre les détails.
L’algorithme de Mallat a cependant le défaut de ne pas être invariant par translation.
On peut donner une démonstration mathématique de cet algorithme ; ici, pour simplifier, on va se limiter
au cas particulier de décomposition d’un signal par les ondelettes de Haar.
5.2 Démonstration dans un cas simple : le cas des ondelettes de Haar.

La démonstration suivante montre comment on calcule les coefficients des ondelettes de Haar : on est bien
évidemment dans le cadre d’une transformation en ondelettes discrètes.
5.2.1 Introduction et définition des notations

k
Considérons un signal échantillonné régulièrement sur [0,1] en 2p points
( notés xk avec xk = 2p .
fk si x ∈ Ik = [xk , xk+1 [
On associe à cet échantillon une fonction f définie par f (x) = . Quand
0 sinon
l’échantillonnage varie, f varie en décrivant l’ensemble Kp des fonctions constantes sur chacun des intervalles
Ik et nulles sur K \ [0, 1].
F (R,R), ensemble des fonctions réelles à valeurs réelles, est un R-espace vectoriel et on montre facilement
que Kp est un sous-espace vectoriel de F (R, R).
S
De plus, pour p ∈ N, on a K0 ⊂ K1 ⊂ .. ⊂ Kp ⊂ Kp+1 ⊂ ... ce qui montre Kp est un sous-espace
p∈N
vectoriel de F (R, R).
À partir de la fonction de Haar H, on définit la fonction Hp,k par Hp,k (x) = H(2p x − k).(p, k) ∈ N2 .
p
[Pour alléger l’écriture et les calculs, on peut comme ici choisir d’omettre le facteur 2 2 devant H(2p x−k).]
Soit la fonction définie par


1 si x ∈ I = [ k , k + 1 ]
k
hp,k (x) = 2p 2p = h(2p x − k)
0 sinon

(avec h définie comme la fonction de Haar mais associant 1 quel que soit x ∈ [0, 1].).
17
Or toute fonction f de Kp se décompose de manière unique sous la forme :

p
2X −1
f= fk hp,k = f0 hp,0 + f1 hp,1 + ... + f2p −1 hp,2p −1
k=0 ( ( (
1 si x ∈ I0 1 si x ∈ I1 1 si x ∈ I2p −1
On a bien ∀x ∈ [0, 1[, f (x) = f0 × + f1 × + ... + f2p −1 × .
0 sinon 0 sinon 0 sinon
D’où (hp,0 , hp,1 , ..., hp,2p −1 ) est une base de Kp .
Avec F (R, R) muni du produit scalaire défini en définition 2, on a :
— Si k 6= k 0 : Z 1 Z 1
hhp,k |hp,k0 i = hp,k (x) · hp,k0 (x) = 0 · dx = 0
0 0
— Si k = k 0 :
Z 1
hhp,k |hp,k0 i = (hp,k (x))2 dx
0
Z xk Z xk+1 Z 1
= (hp,k (x))2 dx + (hp,k (x))2 dx + (hp,k (x))2 dx
0 xk xk+1
Z xk Z xk+1 Z 1
= 02 dx + 12 dx + 02 dx = 0 + [x]xxk+1
k
+ 0 = xk+1 − xk
0 xk xk+1
1
=
2p
Ainsi la base (hp,0 , hp,1 , ..., hp,2p −1 ) est une base orthogonale ; ce qui fait des espaces Kp des espaces
euclidiens.
5.2.2 Propriété mathématique : Orthogonalité dans les espaces euclidiens

Énoncé Soient E un espace euclidien de dimension n ≥ 1, h.|.i son produit scalaire et F un sous-espace
vectoriel de E.
Alors F admet un supplémentaire orthogonal dans E et ce supplémentaire est unique. On le note : F ⊥ .
Démonstration :
— Existence :
— Si F = {0E }, on a E = F ⊕ E de manière immédiate. De plus, si y ∈ F, y = 0E et ∀x ∈ E, hx|0E i =
0. D’où E est un supplémentaire orthogonal à F .
— Si F = E, par un raisonnement analogue, on trouve que {0E } est un supplémentaire orthogonal à F .
— Si F 6= {0E } et F 6= E, on considère (ei )1≤i≤p une base orthonormale de F avec p = dim F ∈ N∗ .
L’ensemble F ⊥ = {x ∈ E|∀y ∈ F, hx|yi = 0} est par définition orthogonal à F .
Soit x ∈ E.
p
X p
X
∃(λ1 , ..., λp ) ∈ Rp , x = λk ek + (x − λ k ek )
k=1 k=1
18
Or le premier vecteur de la somme est dans F . Donc le second entre parenthèses appartient à F ⊥
si et seulement si
p
X
∀k ∈ [|1, p|], hek |x − λk ek i = 0, c’est-à-dire λk = hek |xi
k=1
Avec x écrit de la manière suivante, on établit ainsi que E = F + F ⊥ .
Xp Xp
x= hek |xi · ek + (x − hek |xi · ek )
k=1 k=1
On a aussi immédiatement F ∩ F ⊥ = {0E }, ce qui établit E = F ⊕ F ⊥ et ainsi l’existence d’un
supplémentaire orthogonal à F
— Unicité :
Soit G un sous-espace vectoriel supplémentaire de F dans E et orthogonal à F .
On a déjà G ⊂ F ⊥ puisque tous les vecteurs de G sont
( orthogonaux à tous les vecteurs de F .
E = F ⊕ F⊥
De plus, dim G = dim E− dim F = dim F ⊥ car ; on en déduit G = F ⊥ et l’unicité
E =F ⊕G
du supplémentaire orthogonal.
5.2.3 Utilisation de la propriété : décomposition orthogonale en somme directe.

Soit donc Sp le supplémentaire orthogonal de Kp dans Kp+1 .
On a Kp+1 = Sp ⊕ Kp . D’où de proche en proche on arrive à :

p−1
Kp+1 = Sp ⊕ Sp−1 ⊕ Sp−2 ⊕ ... ⊕ S0 ⊕ K0 , soit encore Kp = K0 ⊕ i=0 Si
de H la fonction Hp,k par Hp,k (x) = H(2p x − k) ; (p, k) ∈ N2 .

On a défini à partir 
1
1 si x ∈ [ k ; k + 2 [




 2p 2p
On alors Hp,k (x) = k+ 1 k+1 .
 −1 si x ∈ [ p 2 ; p [



 2 2
0 dans les autres cas

Facilement, on montre que (hp,1 , hp,0 , ..., hp,2p −1 , Hp,0 , Hp,1 , ..., Hp,2p −1 ) forme une base de Kp+1 .
De plus, on a :
— Si k 6= k 0
Z 1
hhp,k |Hp,k0 i = hp,k (x) · Hp,k0 (x) · dx
Z0 xk Z xk+1 Z xk0
= 0dx + 1 · 0dx + 0dx+
0 xk xk+1
x 0 +x 0
k k +1
Z 2
Z xk0 +1 Z 1
0 · 1dx + x 0 +x 0
0(−1)dx + 0.dx
k k +1
xk 0 2 xk0 +1
=0
— Si k = k 0
19
Z 1
hhp,k |Hp,k0 i = hp,k (x) · Hp,k0 (x) · dx
0
Z xk Z xk+1 Z 1
= 0dx + 1 · Hp,k (x)dx + 0 · dx
0 xk xk+1
x 0 +x 0
k k +1
Z 2
Z xk0 +1
= 1dx + x 0 +x 0
−1dx
k k +1
xk 0 2
= 0.
De ce qui précède, il résulte que (hp,1 , hp,0 , ..., hp,2p −1 , Hp,0 , Hp,1 , ..., Hp,2p −1 ) forme une base orthogonale
de Kp+1 .
Alors le système (Hp,0 , Hp,1 , ..., Hp,2p −1 , ) est une base orthogonale de l’orthogonal Sp de Kp dans Kp+1 .
De plus, on peut déjà remarquer :
Z 1 Z xk0 +x2 k0 +1 Z xk0 +1
2 1
hHp,k |Hp,k i = (Hp,k (x)) · dx = 12 · dx + x 0 +x 0 (−1)2 · dx = p
0 xk0 k
2
k +1 2
-Soit un signal Ψp ∈ Kp .
p
2X −1
2p
Alors ∃!(Ψp,0 , Ψp,1 , ..., Ψp,2p −1 , ) ∈ R , Ψp = Ψp,k hp,k .
k=0
Puisque Kp = Kp−1 ⊕ Sp−1 , ∃!(Ψp−1 , dp−1 ) ∈ Kp−1 × Sp−1 , Ψp = Ψp−1 + dp−1 .
Et on peut décomposer Ψp−1 et dp−1 comme suit :

p p
2X −1 2X −1
Ψp−1 = Ψp−1,k hp−1,k et dp−1 = dp−1,k Hp−1,k .
k=0 k=0
5.2.4 Étape principale de l’algorithme : passage à la résolution inférieure, détermination des

coefficients à la résolution inférieure.
-Déterminons les Ψp−1,k et dp−1,k :
Premières égalités L’orthogonalité de la base (hp,1 , hp,0 , ..., hp,2p −1 , Hp,0 , Hp,1 , ..., Hp,2p −1 ) avec Ψp =
Ψp−1,k dp−1,k
Ψp−1 +dp−1 et les résultats précédents sur les produits scalaires amène à : hΨp |hp−1,k i = 2p−1 et hΨp |Hp−1,k i = 2p−1 .
Démonstration On a
hΨp |hp−1,k i = hΨp−1 |hp−1 i + hdp−1 |hp−1,k i par linéarité du produit scalaire.
X 2p−1
X−1
= Ψp−1,i hhp−1,i |hp−1,k i + Ψp−1,k hhp−1,k |hp−1,k i + dp−1,i hHp−1,i |hp−1,k i
i6=k i=0
p−1
2X −1
X Ψp−1,k Ψp−1,k
= Ψp−1,i · 0 + p−1 + dp−1,i · 0 = p−1
2 i=0
2
i6=k
20
Et on a
hΨp |Hp−1,k i = hΨp−1 |Hp−1 i + hdp−1 |hp−1,k i

2p−1
X−1 X
= Ψp−1,i hhp−1,i |Hp−1,k i + dp−1,i hHp−1,i |Hp−1,k i + dp−1,k hHp−1,k |Hp−1,k i
i=0 i6=k
2p−1
X−1 X
= Ψp−1,i · 0 + dp−1,i · 0 + dp−1,k hHp−1,k |Hp−1,k i
i=0 i6=k
dp−1,k
=
2p−1
Ψp,2k + Ψp,2k+1 Ψp,2k − Ψp,2k+1

Secondes égalités D’autre part, on peut montrer hΨp |hp−1,k i = et hΨp |Hp−1,k i =
2p 2p
Z 1 Z xk+1
Démonstration On a hhp,k |hp−1,k0 i = hp,k (x) · hp−1,k0 (x) · dx = hp−1,k0 (x) · dx
0 xk
Or, on sait par définition que

 0 0
1 si x ∈ [ k ; k + 1 ]
hp−1,k0 (x) = 2p−1 2p−1
0 sinon

D’où :
Z xk+1
1 k0 k0 + 1

hhp,k |hp−1,k0 i =

 1 · dx = p si p−1 ≤ xk ≤ xk+1 ≤ p−1 , ou encore k ∈ {2k 0 , 2k 0 + 1}
x 2 2 2
Z xk k+1
/ {2k 0 , 2k 0 + 1}

hhp,k |hp−1,k0 i =
 0 · dx = 0 si k ∈
xk
On a de même Z 1 Z xk+1
hhp,k |Hp−1,k i =
0 hp,k (x) · H p−1,k0 (x) · dx = Hp−1,k0 (x) · dx
0 xk
On sait par définition que

 k 0 k 0 + 21
1 si x ∈ [
 ; ]


 2p−1 2p−1
Hp−1,k0 (x) = k0 + 1 k0 + 1
 −1 si x ∈ [ p−12 ; p−1 ]



 2 2
0 sinon

D’où :
k0 + 1
 Z xk+1
1 k0
hhp,k |Hp−1,k0 i = 1 · dx = p si p−1 ≤ xk ≤ xk+1 ≤ p−12 , ou encore k = 2k 0





 xk 2 2 2
0 1
 Z xk+1
1 k + k0 + 1

hhp,k |Hp−1,k0 i = −1 · dx = − p si p−12 ≤ xk ≤ xk+1 ≤ p−1 , soit k = 2k 0 + 1
 x 2 2 2
Z xk k+1




/ {2k 0 , 2k 0 + 1}

hhp,k |Hp−1,k0 i = 0 · dx = 0 si k ∈


xk
À partir de cela, il est facile de décomposer comme suit et d’obtenir les résultats :
21
—
p
2X −1
hΨp |hp−1,k i = h Ψp,k hp,k |hp−1,k i
k=0
X X
= Ψp,i hhp,i |hp−1,k i + Ψp,i hhp,i |hp−1,k i
i∈{2k
/ 0 ,2k 0 +1} i∈{2k
/ 0 ,2k 0 +1}
1 1
= 0 + Ψp,2k · + Ψp,2k+1 · p
2p 2
—
p
2X −1
hΨp |Hp−1,k i = h Ψp,k hp,k |Hp−1,k i
k=0
X X
= Ψp,i hhp,i |Hp−1,k i + Ψp,i hhp,i |hp−1,k i
i∈{2k
/ 0 ,2k 0 +1} i∈{2k
/ 0 ,2k 0 +1}
1 −1
= 0 + Ψp,2k · p
+ Ψp,2k+1 · p
2 2
Conclusion On obtient finalement avec les égalités encadrées les équations d’échelles suivantes.
Ψp,2k + Ψp,2k

Ψp−1,k =
 k(Ψp−1,k )k∈[|0;2p−1 −1|] est la famille des coefficients d’approximation à la résolution2p−1
2
Ψp,2k − Ψp,2k
k(dp−1,k )k∈[|0;2p−1 −1|] est la famille des coefficients d’ondelettes

d
p−1,k =
2
Ainsi, lorsqu’on connaı̂t les coefficients d’ondelettes à un niveau de résolution p, on peut aisément
déterminer ceux du niveau p − 1 et l’égalité des sous-espaces vectoriels en somme directe se comprend par :
Kp = Kp−1 ⊕ Sp−1
|{z} | {z } | {z }
Signal à la résolution 2p Signal à la résolution 2p−1 Détails (ou pertes)
L’intérêt principal de cet algorithme est qu’il permet de passer d’un échantillon de taille 2p à un nouvel
échantillon principal de taille 2p−1 et un échantillon de taille 2p−1 en utilisant que des sommes ou des
différences.
5.3 Schématisation de l’algorithme de Mallat (compression d’un signal Ψp par

des ondelettes)
Etape 1
Ψp → Ψp−1
& dp−1 (détails)
En réitérant le processus jusqu’à la dernière étape (étape p), on obtient la configuration suivante :
Etape 1 Etape 2 Etape p

Ψp → Ψp−1 → Ψp−2 → ... → Ψ0
& dp−1 & dp−2 & dp−3 & d0
Ce travail est en réalité la première partie de l’algorithme, appelée analyse.
Il s’ensuit une deuxième partie appelée synthèse, qui correspond à l’opération inverse de l’analyse. Dans
cette partie, les coefficients d’ondelettes « omis » dans l’analyse entraı̂nent des erreurs.
22
Notons toutefois que l’algorithme posé par Stéphane Mallat se fonde sur la notion d’analyse multirésolution
de L2 (R) (qui a été d’ailleurs introduite afin de construire des bases orthogonales d’ondelettes). Il s’agit
toutefois comme ici d’une suite de sous-espaces vectoriels fermés de l’espace L2 (R) mais vérifiant certaines
propriétés plus générales.
5.4 Représentation matricielle de l’algorithme utilisant les ondelettes de Haar

Une image peut être considérée comme un ensemble de pixels, chaque pixel représentant un niveau de
gris si l’image est en noir et blanc, ou un niveau de rouge, de vert et de bleu si l’image est en couleur. On
peut par conséquent représenter l’image par une matrice Hn carrée 2n ∗ 2n de taille égale à la résolution de
l’image.
Les équations d’échelle (c’est-à-dire le passage d’une résolution à la résolution inférieure) renseignent sur
le type de matrice à utiliser dans l’algorithme spécifique de Haar.
1 1

2 0 2 0
1 0 −1 0 
H2 =  2 2 
0 1 0 1 
2 2
0 12 0 − 21
est la matrice 4 ∗ 4 associée à l’algorithme utilisant les ondelettes de Haar.
On retrouve bien le fait que les deux premières colonnes (moitié gauche) représentent l’échantillon principal
et que les deux dernières colonnes (moitié droite) de la matrice symbolisent les détails.
1 1

2 0 0 0 2 0 0 0
1 0 0 0 −1 0 0 0 
2 1 2
1

0 0 0 0 0 0 
 2 2 
0 1 0 0 0 − 1
0 0 
H3 =   2 2 
1 1
 0 0 2 0 0 0 2 0 

0 0 1 0 0 0 − 1
0 
 2 2 
0 0 0 1 0 0 0 1 
2 2
0 0 0 12 0 0 0 − 21
est la matrice 8*8 associée à l’algorithme de Mallat.
L’intérêt du choix de telles matrices réside dans leur adaptation pour la multiplication matricielle (en
raison de l’arrangement des nombres de la matrice suivant les colonnes et le nombre de zéros).
5.4.1 Exemple
On nomme M2 une matrice 4 ∗ 4 quelconque associée à une famille de pixels.
 
a b c d
e f g h
M2 = i j

k l
m n o p
Alors on obtient la nouvelle matrice de pixels (représentant la résolution moitié) en effectuant le produit
M2 × H2 .
On obtient  a+b c+d a−b c−d 
2 2 2 2
 e+f g+h e−f g−h 
M1 = M1 × H2 =  2
 i+j
2
k+l
2
i−j
2 
k−l 
2 2 2 2
m+n o+p m−n o−p
2 2 2 2
On obtient alors en première moitié verticale de la matrice le nouvel échantillon principal et en seconde
moitié les coefficients représentants les nouveaux détails.
On réitère ensuite le processus et on obtient finalement à partir d’une matrice initiale de pixels Mp les
matrices Mp−1 , Mp−2 , . . . M1 , M0 avec la relation de récurrence Mk−1 = Mk × Hp (k ∈ {p, p − 1, . . . , 1} et Hp
23
désigne la matrice carrée 2p ∗ 2p spécifique à l’algorithme de Haar, choisie de telle sorte que son nombre p de
colonnes et de lignes soit celui des colonnes et lignes de la matrice initiale de pixels).
En reprenant l’exemple précédent, il resterait à calculer M0 = M1 × H2 .
On obtiendrait  a+c−(b+d) a+b−(c+d) a+b−(b+c)

a+b+c+d
4 4 4 4
 e+f +g+h e+g−(f +h) e+f −(g+h) e+h−(f +g) 
M0 =
 4 4 4 4 
 i+j+k+l i+k−(j+l) i+j−(k+l) i+l−(j+k) 
4 4 4 4
 
m+n+o+p m+o−(n+p) m+n−(o+p) m+p−(n+o)
4 4 4 4
Mais en pratique, pour chaque matrice Mk calculée, on ne garde que les coefficients supérieurs à une
certaine précision choisie on effectue une compression. Les coefficients d’ondelettes inférieurs à cette précision
sont remplacés par des 0. Lors de l’étape inverse de décompression ou synthèse, pour réobtenir la matrice
initiale Mp , il suffit de calculer les nouvelles matrices M10 , M20 , . . . , Mp0 par la relation de récurrence suivante :
0
Mk+1 = Mk0 × (Hp )−1 , avec k ∈ {0, 1, . . . , p − 1}, (Hp )−1 désigne la matrice inverse de Hp et M00 = M0
En reprenant l’exemple précédent, on aurait :
 
1 1 0 0
0 0 1 1 
(H2 )−1 =  1 −1 0 0 

0 0 1 −1
Bien sûr, la matrice finale Mp0 se quelque peu différente de la matrice Mp puisque certains coefficients
sont devenus des 0.
6 Application à la compression des données

La transformation en ondelettes se révèle très efficace pour transformer la plupart des signaux que l’on
peut rencontrer, notamment les images et il est facile d’en comprendre la raison.
En effet, la majeure partie des informations à laquelle nous sommes sensibles se trouve dans les contours
de l’image où l’intensité varie brutalement, et les coefficients d’ondelettes correspondants sont significatifs, y
compris aux petites échelles.
Or, une image contient généralement relativement peu de contours, et est régulière (lentement variable)
sauf au voisinage des contours. Par conséquent, beaucoup de coefficients d’ondelettes sont faibles (surtout aux
petites échelles) ; les détails étant presque nuls, ils peuvent être négligés sans que cela entraı̂ne de distorsion
visible sur l’image.
Il suffit alors de s’imposer une précision . On ne va garder ainsi que les coefficients d’ondelettes supérieurs
à . On dit alors qu’on effectue une compression du signal.
Il y a notamment des applications de la compression par ondelettes dans le domaine de l’imagerie médicale.
Le cinéma numérique a quant à lui adopté le format JPEG 2000 qui utilise également la transformée en
ondelettes.
7 Utilisation pratique de la transformation par ondelettes discrète

Nous avons choisi de mettre en pratique ce que nous avons vu plus haut de manière théorique. Notre but
a été de mettre en place un algorithme de compression d’image utilisant la compression par ondelettes, ainsi
que des applications graphiques qui utilisent cet algorithme.
Pour que notre travail rentre dans le cadre du thème de cette année,qui est ”Transfert, Échange”, nous
avons aussi créé une application client/serveur utilisant la compression par ondelettes.
Le code complet de nos algorithmes est disponible en annexe à la fin de ce dossier, mais aussi sur le
Github de notre projet (cf. section Liens).
7.1 Le choix des outils

Pour nos programmes, nous avons utilisé le langage Python, ainsi que plusieurs librairies.
24
7.1.1 Le langage : Python

Nous avons choisi d’utiliser le langage Python pour plusieurs raisons. Celui-ci offre beaucoup de possibi-
lités, est facile à utiliser (et à comprendre) et permet de créer de gros projets assez rapidement. C’est aussi
un langage approprié pour un débutant en programmation. C’est un très bon langage de prototypage, ce
qui permet de donner un aperçu assez fonctionnel d’une application pour ensuite pouvoir la réaliser dans un
autre langage (plus rapide, par exemple). C’est un langage de script, ce qui permet une grande flexibilité du
code, et enlève l’étape de la compilation.
La version 2.7 de Python a été utilisée pour notre projet, car celle-ci est plus stable et plus mûre que la
plus récente version 3. Aussi, beaucoup de modules Python assez utiles n’ont toujours pas été portés vers
Python 3 à l’heure actuelle et nous ne voulions pas être freinés par cela.
7.1.2 La librairie de traitement d’image : PIL

Pour que notre application puisse supporter plusieurs types de fichiers, nous avons eu recours à une
librairie graphique. Nous l’avons utilisée simplement afin de récupérer un tableau contenant les pixels d’une
image, ce qui aurait été redondant à programmer nous-même.
PIL nous donne aussi accès à l’écriture de fichiers image dans tous les formats, ce qui offre de la flexibilité
à notre programme.
Nous n’avons pas utilisé les autres fonctionnalités de cette librairie, bien entendu, puisqu’il s’agissait avant
tout de concevoir notre propre algorithme de compression.
7.1.3 La librairie d’interface graphique : Tkinter

Pour la partie «interface graphique utilisateur» (ou GUI), nous avons utilisé la librairie Tkinter, qui est
incluse par défaut avec l’installation standard de Python. Elle est simple d’utilisation et convenait parfai-
tement à ce que nous voulions en faire, c’est-à-dire une simple application montrant la compression d’une
image en utilisant notre algorithme.
Beaucoup d’autres librairies existent pour la réalisation de GUI, mais celles-ci sont à télécharger en plus
de Python, et nous ne voulions pas surcharger notre projet. De plus, les fonctionnalités qu’elles apportent
n’auraient pas été utilisées dans le cadre de notre projet.
7.1.4 La librairie de calcul parallélisé : PyOpenCL

Nous avons utilisé cette librairie pour implémenter le calcul accéléré par GPU dans la partie 7.7.
7.1.5 Le module time

Ce module nous a été utile lors du chronométrage de nos algorithmes et pour introduire des délais dans
l’envoi de données dans le programme client/serveur. Nous avons préféré celui-ci à d’autres (comme timeit)
pour sa simplicité d’utilisation et sa précision suffisante.
7.1.6 Le module struct

Le module struct a pour but de transformer des chaı̂nes de caractères (et autres objets Python) en
variables binaires (telles que celles utilisées par le langage C). Par exemple, le nombre ”123” utilise 3 octets
quand il est écrit en chaı̂ne de caractères Python, alors que quand il est écrit en mémoire en tant que
variable de type byte, il n’utilise qu’un octet. Nous avons donc utilisé cela pour la sauvegarde de coefficients
d’ondelettes et les transferts d’images entre client et serveur. En effet, les valeurs RGB des pixels ne peuvent
être supérieures à 255 et tiennent donc dans un seul octet. Ce qui nous donne au final des paquets et des
fichiers 3 fois plus petits. Cela augmente aussi la vitesse des transferts.
7.1.7 Le module socket

Ce module a été utilisé pour transférer des images à travers le réseau. Nous avons préféré utiliser ce
module plutôt que les sockets d’une librairie externe (telle que PySFML), car celui-ci est inclus dans Python
et nous voulions que le programme reste simple.
25
7.2 L’algorithme matriciel

Nous avons mis au point un algorithme de compression utilisant des matrices. Celui-ci applique deux fois
la transformation par ondelettes de Haar (une fois pour la hauteur, une fois pour la largeur), et stocke les
coefficients d’ondelettes dans des matrices séparées de l’image. On peut ensuite supprimer certains de ces
coefficients au-delà d’un certain seuil, pour compresser l’image.
La figure 12 est un schéma-bloc montrant l’algorithme. La partie «Transformation DWT» est explicitée
par la figure 13
Matrice R
Transformation DWT
Image JPG Matrice G Image JPG

Séparation RGB Transformation DWT Réunion RGB
Matrice B
Transformation DWT
Figure 12 – L’algorithme matriciel
Matrice des coef.

d’ondelette (lignes) Suppression
des coefficients
Matrice des coef. négligeables
d’approximation
Matrice Couleur Matrice compressée

Analyse Analyse Synthèse Synthèse
(colonnes) (lignes) (lignes) (colonnes)
Matrice des
coef. d’approx.
Suppression
des coefficients
Matrice des coefficients négligeables
d’ondelette (colonnes)
Figure 13 – La transformation appliquée aux matrices
26
7.3 Exemples d’images traitées avec notre algorithme

La figure 14 montre l’image à laquelle nous avons appliqué la compression. La figure 15 montre un détail
de l’image.
Figure 14 – L’image de départ
Figure 15 – Détail de l’image de départ
La figure 16 représente le même détail de l’image une fois que la compression a été appliquée avec un
seuil assez petit pour garder la plupart des détails importants de l’image mais assez grand pour compresser
les «aplats» de couleur, les ombres, etc. L’image compressée occupe 35% de mémoire en moins par rapport à
l’image de départ. Ce qui montre que la compression par ondelettes est plutôt efficace et que notre algorithme
est fonctionnel.
Sur la figure 17, on peut voir le même détail quand l’image a été compressée avec le seuil maximal. Ici,
tous les détails ont été éliminés. Cela revient simplement à diviser la résolution de l’image par deux.
27
Figure 16 – Détail de l’image compressée
Figure 17 – Détail de l’image compressée à 100%
28
7.4 L’application graphique

L’application graphique que nous avons créée permet plusieurs choses :
— Ouverture d’une image
— Enregistrement d’une image
— Affichage d’une image dans une fenêtre
— Conversion d’une image en nuances de gris
— Compression d’une image par deux méthodes
— Réduction de la résolution d’une image de 50%
— Envoi d’une image à un serveur grâce au programme client.py
La figure 18 montre la fenêtre principale de l’application, avec une image en cours d’édition. L’interface
est minimaliste, mais suffisante.
Figure 18 – Fenêtre principale de l’application
La figure 19 montre les menus de l’application, qui permettent de choisir entre toutes les actions décrites
ci-dessus.
La figure 20 montre le sélecteur de seuil, qui apparaı̂t lorsqu’on choisit «Compresser» ou «Compresser
(new)» dans les menus.
29
Figure 19 – Menus de l’application
Figure 20 – Le sélecteur de seuil de compression
30
7.5 L’algorithme fasthaar

Nous avons mis au point un autre algorithme de compression n’utilisant pas de matrices. Celui-ci est plus
rapide et moins gourmand en mémoire que haar, mais l’inconvénient est qu’il ne permet pas d’utiliser la
transformation par ondelettes discrète à un niveau de récursivité plus grand que 1.
7.5.1 Fonctionnement
L’algorithme découpe l’image en carrés de 4 pixels, qu’il va traiter à la suite, colonne par colonne. Comme
montré sur la figure 21
Figure 21 – Fonctionnement de l’algorithme
Analyse : Pour chaque carré de 4 pixels, l’algorithme applique la transformation par ondelettes discrète.
On commence par stocker les valeurs RGB des 4 pixels dans un tableau. Nous allons, pour l’exemple, utiliser
les 4 pixels mis en valeur sur la figure 21. Le tableau créé est montré par la figure 22.
R G B
171 147 137 109 109 86
169 140 135 102 107 79
Figure 22 – Tableau créé par l’algorithme
L’algorithme remplace ensuite les valeurs des colonnes de gauche de chaque couleur par la moyenne de
chaque ligne et les valeurs des colonnes de droite par la différence divisée par deux. Ce qui nous donne le
tableau de la figure 23. Les coefficients d’ondelette sont surlignés.
31
R G B
160 11 123 14 97.5 11.5
154.5 14.5 118.5 16.5 93 14
Figure 23 – Tableau après l’étape 1
Enfin, l’algorithme remplace la case en haut à gauche de chaque couleur par la moyenne des lignes et la
case en bas à gauche par la différence divisée par deux. Le résultat est montré par la figure 24.
R G B
157.25 11 120.75 14 95.25 11.5
2.75 14.5 2.25 16.5 2.25 14
Figure 24 – Tableau après l’étape 2
Compression et synthèse : Après la phase d’analyse vient la phase de compression. On va supprimer les
coefficients d’ondelettes inférieurs à un certain seuil. Pour l’exemple, nous allons choisir un seuil de 12.
Après compression, le tableau est celui de la figure 25.
R G B
157.25 0 120.75 14 95.25 0
0 14.5 0 16.5 0 14
Figure 25 – Tableau après compression
Ensuite, l’algorithme reconstitue l’image avec les coefficients restants. On effectue d’abord pour la colonne
de gauche de chaque couleur une addition pour retrouver le coefficient du haut, et une soustraction pour le
coefficient du bas. Ce qui nous donne le tableau de la figure 26. Puisque les coefficients étaient égaux à 0, les
pixels ne sont pas changés.
R G B
157.25 0 120.75 14 95.25 0
157.25 14.5 120.75 16.5 95.25 14
Figure 26 – Tableau après synthèse sur les colonnes
L’algorithme effectue ensuite les mêmes opérations sur les lignes. Le résultat est donné par la figure 27
R G B
157.25 157.25 134.75 106.75 95.25 95.25
171.75 143 137.25 104.25 109.25 81.25
Figure 27 – Tableau après synthèse sur les lignes
Enfin, on arrondit les valeurs à l’entier le plus proche. Le tableau final est donné par la figure 35. La figure
29 montre une comparaison entre l’état des pixels avant traitement, et l’état des pixels après.
Les pixels peuvent sembler réellement différents après traitement, mais la valeur moyenne des couleurs
est conservée, ce qui, au final, donnera le même rendu quand les pixels seront à leur taille normale.
32
R G B
157 157 135 107 95 95
172 143 137 104 109 81
Figure 28 – Tableau après synthèse sur les lignes
Figure 29 – Pixels avant et après traitement
33
7.5.2 Coût et Performance

Nous avons été curieux de voir les performances de l’algorithme fasthaar.
Coût en mémoire : Cet algorithme est peu coûteux en mémoire, par rapport à la version matricielle. En
effet, ce dernier devait stocker plusieurs matrices contenant l’image, les coefficients d’ondelettes, les différentes
couleurs, etc. fasthaar, quant à lui, ne stocke que l’image et les valeurs de 4 pixels. Un pixel est un tuple
contenant 3 entiers codés sur 8 bits (= 1 octet).
Soient L et l la longueur et la largeur de l’image à traiter. La place de l’algorithme fasthaar en mémoire
est donc de 3 × l × L + 4 × 3 octets.
Coût temporel : Vu le principe de fonctionnement de fasthaar, on peut deviner que celui-ci a un coût en
O(l · L) (ou O(n2 ) pour une image carrée de côté n). Nous avons créé un fichier bench.py servant à mesurer
le temps que prend l’algorithme à traiter des images de différentes tailles. L’algorithme génère une image
d’une taille donnée avec des pixels aléatoires puis lui applique fasthaar en chronométrant.
La figure 30 représente le temps de traitement d’une image (en secondes) en fonction de sa taille (pixels
d’un côté divisé par 2). On vérifie donc que le coût est bien quadratique.
35
30
Temps de compression (s)
25
20
15
10
0
0 100 200 300 400 500 600 700 800 900 1000
Taille de l’image (px/2)
Figure 30 – Coût temporel de l’algorithme fasthaar en fonction de la taille de l’image
34
7.6 Transferts et échanges d’images par le réseau

Nous avons créé un programme serveur/client permettant de transférer des images et des coefficients
d’ondelette par le réseau.
7.6.1 But du programme

Ce programme permet de stocker les coefficients d’ondelette d’une image sur un serveur distant pour
ensuite ne garder sur la machine locale que les coefficients d’approximation (c-à-d l’image réduite de moitié
sur chaque dimension). Ainsi une version légère de l’image est gardée pour que l’on puisse toujours savoir
quelle image nous voulons (thumbnail), mais celle-ci occupe 4 fois moins de place en mémoire. Lorsque
l’utilisateur veut afficher l’image en grandeur réelle, la machine locale demande les coefficients d’ondelette au
serveur et reconstitue l’image de départ.
Ceci peut être très utile, par exemple dans le cas d’un périphérique de stockage amovible de taille réduite,
tel qu’une clef USB - on peut ainsi stocker 4 fois plus d’images pour la même capacité.
7.6.2 Processus d’archivage

Étape 1 Le client ouvre l’image à stocker et encode les pixels, ainsi que les dimensions de l’image en binaire,
puis envoie ces données au serveur par des sockets TCP. Chaque pixel de l’image occupe 3 bits, donc, si L et
l sont les dimensions de l’image, le client doit envoyer 3 · l · L + 2 octets au serveur.
Étape 2 Le serveur ouvre l’image qu’il vient de réceptionner pour la compresser et stocker les coefficients
d’ondelette. Il applique pour cela une version modifiée de fasthaar qui ne garde que les coefficients d’ondelette
et les encode en binaire grâce à struct pour les enregistrer dans un fichier.
Étape 3 Le client reçoit un signal de la part du serveur indiquant si oui ou non le tranfert et la compression
se sont bien déroulés. Si c’est le cas, le client crée une nouvelle image, de dimensions L2 et 2l et la remplit
avec la moyenne des carrés de 4 pixels de l’image de départ (coefficients d’approximation).
La figure 31 montre le processus d’archivage.
Figure 31 – Processus d’archivage
35
7.6.3 Processus de restauration

Étape 1 Le client crée une image à partir de celle qui avait été stockée en doublant ses dimensions, ainsi,
chaque pixel devient un carré de 4 pixels.
Étape 2 Le client demande les coefficients d’ondelette au serveur en spécifiant le nom de l’image. Le serveur
lit le fichier qui contient les coefficients qu’il avait enregistrés et envoie directement les données au client.
Étape 3 Le client décode les données binaires reçues et opère la transformation inverse en remplaçant les
pixels de chaque carré par les valeurs qu’il obtient. Ensuite, il peut afficher l’image ou la stocker.
La figure 32 illustre ce processus
Figure 32 – Processus de restauration
36
7.7 Optimisation : utilisation de l’accélération matérielle avec OpenCL

7.7.1 L’accélération matérielle
Introduction L’accélération matérielle d’une tâche informatique consiste à dédier une certaine partie d’une
unité de calcul à une tâche spécifique. C’est ce qui est fait avec le traitement du son avec les cartes son, les
cartes d’acquisition vidéo, ou encore l’affichage 3D avec les cartes graphiques.
Le GPU, ou Graphical Processing Unit Un ordinateur comporte un processeur, aussi appelé CPU,
pour Central Processing Unit. Mais les ordinateurs modernes possèdent aussi des puces dédiées à l’affichage,
qu’il soit 2D ou 3D. Ce sont les GPU.
Un CPU est une puce servant à effectuer rapidement des tâches non ou très peu parallélisées. Il comporte
généralement plusieurs ”coeurs”, qui sont relativement peu nombreux (2 voire 4 pour des processeurs grand
public). Il est possible d’effectuer des tâches simultanément sur tous ces coeurs, c’est ce qui est fait naturel-
lement par le système d’exploitation, qui répartit les tâches entre les coeurs. Par exemple, lors de l’affichage
d’une page web contenant une vidéo, le décodage de la vidéo peut être effectué par un coeur, tandis qu’un
autre s’occupera de l’affichage de la page elle-même.
Un GPU, au contraire, est une puce fortement parallélisée, se trouvant sur les cartes graphiques, ou plus
récemment dans une partie du CPU dédiée à l’affichage. Elle contient une multitude de petits ”processeurs
de flux” (plusieurs centaines pour des cartes graphiques modernes), effectuant tous la même tâche au même
moment. Ceci est très utile pour l’affichage 3D, pour la compression vidéo, ou encore pour le traitement du
son, grâce à des technologies telles que TrueAudio.
Figure 33 – Comparaison entre les architectures CPU et GPU
37
Le calcul sur GPU Il est donc possible d’utiliser le GPU pour le traitement d’images, et donc pour notre
transformation en ondelettes, puisqu’il s’agit de traiter une multitude de pixels de la même manière. s Les
gains possibles sont importants, en effet, prenons l’exemple d’une image de 12 mégapixels (résolution classique
pour un appareil photo moderne) et d’un GPU AMD Pitcairn (présent dans les cartes graphiques Radeon
HD séries 7800) comportant 1024 processeurs de flux avec une fréquence de 1000MHz. Notre algorithme
travaille sur des ”blocs” de 4 pixels (comme vu plus haut) et fait environ une dizaine d’opérations de calcul
sur ceux-ci, soit probablement un millier d’opérations élémentaires au niveau matériel environ.
Cela nous donne donc un temps de traitement théorique de l’ordre de T = 12 · 106 ∗ 103 /4/1024/1 · 109 =
3 · 10−3 s. Ce qui est relativement faible en comparaison avec les temps obtenus avec un CPU. On peut donc
bien parler ”d’accélération” matérielle.
7.7.2 Haar et OpenCL

OpenCL OpenCL, pour Open Compute Language est un langage de programmation semblable au C,
permettant de coder des tâches fortement parallélisées. Nous avons ici utilisé l’implémentation d’OpenCL
en Python, appelée pyopencl. Le code OpenCL peut aussi bien être utilisé sur un CPU que sur un GPU,
car tous les types de processeurs sont accessibles de la même manière au niveau de l’API elle-même, et sont
appelés des ”Workers”.
Figure 34 – Exécution de ondelettesCL.py
38
L’implémentation de l’algorithme Les fichiers ondelettesCL.py et haar.cl peuvent être trouvés en

annexe.
Implémenter un algorithme en pyopencl est simple, seule la partie à faire exécuter par le GPU est à coder
dans un fichier différent, qui sera compilé à part lors du lancement du programme, puis envoyé à la carte
graphique, qui l’exécutera ensuite quand il sera appelé par le programme principal.
Le but est que chaque processeur de flux du GPU exécute la transformation montrée en section 7.5 sur
un bloc de 4 pixels, avant de passer au suivant. On sépare donc l’image en ces blocs de 4 pixels, que l’ont
met dans une grande liste, qui sera passée en argument au programme haar.cl.
Le fonctionnement du programme est représenté sur la figure 34.
7.7.3 Performances réelles

Le programme a été exécuté à l’aide d’un GPU AMD Radeon HD 7870, sur plusieurs images (voir annexes).
Les temps d’exécution sont plus longs que les temps théoriques, ce qui est sans doute dû au temps de copie
des données entre la mémoire RAM du système et celle du GPU.
Image (résolution) IMG1 (3 mégapixels) IMG2 (5 mégapixels) IMG3 (12 mégapixels)

Temps (secondes) 0.057 0.079 0.122
Figure 35 – Temps d’exécution de haar.cl
Nous avons également surveillé l’activité du GPU lors du traitement à l’aide du logiciel MSI Afterburner.
Figure 36 – Graphique d’activité du GPU lors du traitement de l’image 3
39
8 Description du code
Ce qui suit est une description du code de tous nos programmes.
8.1 Le fichier ondelettes.py

Dans ce fichier, nous définissons des classes qui permettent le traitement des images. Il peut très bien être
utilisé tout seul (sans l’interface graphique).
8.1.1 La classe Matrice

Au lieu d’utiliser la classe Matrice du module numpy, nous avons préféré créer la notre. En effet, nous
n’avons pas besoin de toutes les fonctions qu’elle offre. Aussi, nous voulions faire un maximum de choses
nous-mêmes.
La fonction init Cette fonction prend en argument la taille de la matrice et le premier élément qu’elle
doit contenir pour ensuite créer un tableau de tableaux contenant ce premier élément. Elle enregistre aussi
les dimensions de la matrice dans l’objet créé.
La fonction transpose Comme son nom l’indique, elle transforme la matrice en sa transposée. Elle est
utilisée lors de la transformation par ondelettes de Haar.
La fonction add Elle permet l’addition de matrices. La matrice sur laquelle est appelée la fonction est
replacée par le résultat de l’addition. Elle n’est pas utilisée dans ce programme, mais pour que notre classe
soit réutilisable dans d’autres projets, il fallait qu’elle soit créée.
La fonction multiply Cette fonction est analogue à la fonction add pour la multiplication.
La fonction copy Cette fonction transorme la matrice en celle qui est passée en argument.
La fonction update Cette fonction met à jour les dimensions de la matrice si le tableau a changé de taille.
Les fonctions save et save1 Elles permettent de sauvegarder l’état de la matrice dans un tableau auxil-
liaire.
La fonction restore Elle remet en place le tableau sauvegardé par la fonction save.
8.1.2 La classe MatriceImage

Cette classe utilise la classe Matrice pour stocker une image afin de pouvoir travailler dessus. Elle contient
également des fonctions de compression et d’enregistrement.
La fonction init Cette fonction prend en argument l’emplacement d’une image et la charge à l’aide de
PIL. Elle crée puis remplit une Matrice avec les informations des pixels de l’image (cf. fonction fill).
La fonction fill Cette fonction stocke les pixels de l’image dans la Matrice.
Les fonctions grayscalemean et grayscalemeanmatrix Elles transforment l’image en nuances de

gris en remplaçant chaque couleur de chaque pixel par la moyenne des trois composantes RGB du pixel.
grayscalemean fait l’opération sur l’image directement alors que grayscalemeanmatrix la fait sur la Matrice
de l’image.
40
Les fonctions getmatrixred, getmatrixgreen et getmatrixblue Créent des tableaux dans l’objet et
les remplissent avec les composantes RGB (respectivement) de l’image. Cela permet de traiter chaque couleur
séparément.
La fonction save Elle prend en argument une chaı̂ne de caractère et sauvegarde l’image sous ce nom dans
le dossier courant.
La fonction ondelette haar Cette fonction prend en argument un tableau de valeurs et le nombre de
récursions qu’elle doit faire. Elle renvoie le tableau des coefficients d’approximation ainsi que le tableau des
coefficients d’ondelette.
Les fonctions getcolonne et getligne Ces fonctions servent à récupérer une liste contenant les données
d’une colonne/d’une ligne, pour pouvoir ensuite être traitées par la fonction ondelette haar.
La fonction setcolonne Elle permet de remettre une colonne dans une matrice après traitement.
Les fonctions apply haar lig et apply haar col Ces fonctions appliquent la transformation avec l’on-
delette de haar à toutes les lignes/toutes les colonnes d’une matrice.
La fonction haar grayscale Cette fonction convertit une image en nuances de gris, puis applique la
transformation par ondelettes sur l’image. Elle l’applique d’abord sur les lignes, puis transpose la Matrice,
puis la réapplique sur les lignes.
La fonction update Elle est similaire à celle qui a été décrite plus haut.
La fonction create coef matrix Elle crée les tableaux nécessaires à la mise en mémoire des coefficients
d’ondelette de chaque couleur.
La fonction haar Elle a le même effet que la fonction haar\_{}grayscale, mais elle s’applique aux 3
composantes de l’image.
La fonction makeimage Cette fonction crée une image à partir des matrices des coefficients d’approxi-
mation.
La fonction compression Cette fonction, une fois que les matrices de coefficients d’ondelette ont été
créées, permet de supprimer les coefficients qui sont inférieurs au epsilon passé en paramètre.
Les fonctions syntheseligne et synthesecolonnes Ces fonctions appliquent la transformation inverse

à l’image, à partir des coefficients d’approximation et des coefficients d’ondelette qui ont été conservés par la
fonction compression.
La fonction clearimage Elle supprime toutes les données d’une image en la remplissant d’une couleur
définie.
La fonction fasthaar Cette fonction permet d’appliquer la transformation par ondelettes sans passer par
les matrices. Pour cela elle prend tous les «carrés» de 4 pixels d’une image et leur applique la transformation
et la compression. Elle est plus rapide que les autres fonctions, mais l’inconvénient est que la récursivité n’est
pas permise. Elle est donc utilisée pour compresser légèrement une image. Les résulats restent tout de même
impressionnants puisqu’elle peut faire gagner jusqu’à 45% d’espace en seulement quelques secondes.
41
8.2 Le fichier ondelettesGUI.py

Ce fichier est l’interface graphique du programme, qui requiert le fichier ondelettes.py pour fonctionner.
En effet, l’interface graphique n’est qu’une façade pour les fonctions qui ont été décrites plus haut.
8.2.1 La classe Appli

Cette classe représente la fenêtre principale de l’application.
La fonction init Cette fonction définit simplement l’instance de la fenêtre en appelant la fonction initUI
décrite plus bas.
La fonction initUI Cette fonction crée tous les éléments de la fenêtre (le titre et les menus, entre autres).
La fonction askopenfilename Cette fonction ouvre une boı̂te de dialogue demandant quel fichier ouvrir.
La boite de dialogue est incluse dans l’installation de Tkinter. Une fois que le fichier a été choisi, la fonction
crée la zone où l’image sera affichée.
La fonction asksaveasfilename Cette fonction ouvre une boı̂te de dialogue demandant où enregistrer le
fichier qui a été modifié.
Les fonctions askcompression et askcompression2 Elles servent à ouvrir une boı̂te de dialogue du
type DialogScale (défini plus bas) pour demander à l’utilisateur le seuil de compression à utiliser lors de
l’appel des fonctions compression ou compression2.
Les fonctions compression et compression2 Ces fonctions utilisent respectivement les fonctions haar
et fasthaar de ondelettes.py pour réaliser la compression de l’image avec le seuil donné par les fonctions
askcompression et askcompression2. L’ancienne image est ensuite effacée de l’écran et la nouvelle est
affichée grâce à displayimage ;
La fonction grayscale Elle utilise les fonctions de ondelettes.py pour convertir l’image en nuances de
gris.
La fonction displayimage Elle crée une zone pour afficher la nouvelle image qui a été créée par compres-
sion, puis l’affiche dans cette zone.
La fonction onExit Elle est appelée lors de la fermeture de l’application et est là pour être sûr que tout
est fermé correctement.
8.2.2 La classe DialogScale

C’est la classe qui définit la boı̂te de dialogue de compression (Fig.20). Elle est construite sur la même
base de fenêtre que la classe Appli.
La fonction initUI Cette fonction crée le texte de la boı̂te de dialogue, la réglette qui permet de choisir
la compression, et le bouton «Ok».
La fonction onScale Elle est appelée lorsque l’utilisateur modifie la position de la réglette. Elle stocke la
position de celle-ci en mémoire.
La fonction ok Elle est appelée lorsque l’utilisateur clique sur le bouton «ok». Elle sauvegarde la valeur
de la position de la réglette, puis ferme la boı̂te de dialogue.
42
8.2.3 La fonction main

Elle crée simplement une instance de la classe Appli et l’exécute.
8.3 Le fichier bench.py

Ce fichier a été utilisé pour le chronométrage de l’algorithme fasthaar, expliqué plus haut.
8.3.1 La fonction image gen

Cette fonction crée une instance d’une image PIL dont la taille est passée en paramètre.
8.3.2 La fonction randomize

Elle prend en paramètre une image créée par image_gen, pour la remplir de pixels aléatoires. Afin d’être
sûr que l’algorithme fasthaar fera des calculs.
8.3.3 La fonction bench square

Cette fonction prend en argument un tableau de nombres qui vont servir à créer des images de tailles
différentes avec image_gen, puis les remplir avec randomize et enfin chronométrer le traitement de celles-ci
avec le module time de Python.
8.3.4 La fonction fasthaar

C’est la même que celle du fichier ondelettes.py sauf qu’elle n’a pas besoin de la classe ImageMatrice
pour fonctionner.

Elle appelle la fonction bench_square sur un tableau de nombres allant de 1 à 1000 (pour des images de
2 à 2000 pixels de côté).
8.4 Le fichier serveur.py

Ce fichier est celui qui est exécuté en permanence sur le serveur, comme décrit à la page 35.

C’est la fonction principale du programme qui contient la boucle d’exécution du serveur. Elle commence
par créer un socket qui va attendre un client sur le port 13337.
Lors de la connexion d’un client, le serveur entre dans la boucle d’exécution, qui tourne jusqu’à ce que
le client envoie ”stop” au serveur. À chaque fois que le client envoie un message au serveur, ce dernier en
analyse les premières lettres pour connaı̂tre la commande que le client veut exécuter, puis l’exécute.
8.4.2 La fonction recvImage

Cette fonction est exécutée quand le client envoie ”sendimg” au serveur. Le serveur récupère les dimensions
de l’image, puis se met en attente des pixels de l’image, qu’il réceptionne dans une chaı̂ne de caractères qui
fait office de buffer. La réception se termine quand le client envoie ”end”. Le serveur décode ensuite la chaı̂ne
de caractère pixel par pixel en la parcourant par morceaux de 3 bytes, et insère les pixels décodés dans une
image aux dimensions égales à celles qui ont été envoyées. Enfin, il enregistre l’image et signale au client que
l’opération s’est complétée avec succès.
43
8.4.3 La fonction fasthaar srv

C’est une fonction qui ressemble à fasthaar du fichier ondelettes.py, mais elle ouvre elle même un
image à partir du nom envoyé par le client. Ensuite elle opère la transformation par ondelettes discrète et
sauvegarde ceux-ci après les avoir encodés en binaire, uniquement s’ils sont supérieurs au paramètre optionnel
epsilon (fixé à 0 par défaut, pour garder des images entières). Une fois que la transformation est terminée, le
serveur le signale au client.
8.4.4 La fonction sendCoef

Cette fonction est appelée quand le client veut reconstituer une image. Il envoie alors ’coef nom_image’.
Le serveur ouvre le fichier qui contient les coefficients d’ondelette, et les envoie au client sans les décoder.
Une fois que c’est terminé, le client envoie "ok" en binaire au serveur pour lui signaler que l’opération s’est
bien déroulée.
8.5 Le fichier client.py

Ce fichier est exécuté par le l’utilisateur quand il veut demander quelque chose au serveur (soit demander
le stockage d’une image, soit demander des coefficients). Celui-ci est appelé de cette façon :
./client.py [arguments:-rsd] image.jpg [optionnel : serveur]

Cette fonction a pour arguments ceux passés par l’utilisateur en ligne de commande. Ils peuvent être :
— r pour communiquer avec un serveur distant. Ce paramètre peut être omis pour établir la connection
à un serveur local.
— s pour stocker une image. C’est à dire : envoi de l’image au serveur, compression de l’image par le
serveur, enregistrement de l’image réduite par le client.
— d pour récupérer les coefficients d’ondelette d’une image et la reconstituer.
Dans le cas de l’utilisation de la commande r, on peut utiliser un serveur autre que celui définit par défaut
en en spécifiant l’adresse après le nom de l’image à traiter. Une fois que l’échange client/serveur est terminé,
la fonction envoie "stop" au serveur, lui signifiant la fin de la connexion.
8.5.2 La fonction sendImage

Cette fonction est appelée lors de l’utilisation de la commande s, elle envoie au serveur "sendimg" suivi
des dimensions du nom de l’image et de ses dimensions. Ensuite l’image est encodée en binaire puis envoyée
au serveur. Le client signale ensuite que le transfert est terminé en envoyant "end" au serveur. Le client
affiche ensuite la réponse du serveur.
8.5.3 La fonction askcompress

C’est la deuxième fonction appelée quand la commande s est utilisée. Elle demande au serveur de com-
presser l’image qui a été envoyée plus tôt, avec "compress" suivi du nom de l’image. Le client affiche ensuite
la réponse du serveur.
8.5.4 La fonction storeImage

C’est la dernière fonction appelée quand la commande s est utilisée. Cette fonction crée une image
dont les dimensions ont été divisées par deux (par rapport à l’image originale) et y copie les coefficients
d’approximation. Cette image est très légère et peut être affichée.
44
8.5.5 La fonction askcoeff

Cette fonction est appelée lors de l’utilisation de la commande d. Elle demande au serveur d’envoyer les
coefficients d’ondelette de l’image. La fonction décode ensuite les coefficients reçus, puis ouvre l’image réduite
qui avait été enregistrée par storeImage. Le client crée une image de la taille de l’image originale, puis opère
la transformation par ondelettes inverse. Après ça, le client enregistre l’image.
8.6 Le fichier ondeletttesCL.py

Ce fichier est exécuté par le CPU lors de l’utilisation d’OpenCL.
8.6.1 La classe Climage

Cette classe contient les fonctions qui sont exécutées lors de l’envoi des données au GPU et de la réception
des données traitées.
8.6.2 Les fonctions gettl, gettr, getll et getlr

Ces fonctions servent à recomposer l’image à partir des blocs de 4 pixels qui ont été traités par le GPU.
8.6.3 La fonction execute

Cette fonction sépare l’image en blocs de 4 pixels, puis envoie le tableau créé à la mémoire du GPU. Elle
appelle ensuite le programme haar.cl et récupère l’image traitée. L’image est ensuite recomposée à l’aide des
fonctions décrites plus haut.
8.6.4 La fonction save

Cette fonction sauvegarde l’image traitée au format JPG.
9 Conclusion
La théorie des ondelettes symbolise en quelque sorte l’évolution des sciences mathématiques induite par
l’introduction de l’outil informatique.
Bien que l’analyse par les ondelettes soit encore loin de nous donner une réponse universelle et finale
au problème de la représentation et du codage des signaux, elle se révèle être un outil mathématique parti-
culièrement performant dans plusieurs domaines, comme l’aura très nettement montré notre implémentation
informatique. D’ailleurs, nous aurons nous-mêmes pu exploiter la richesse des ondelettes dans le domaine de
transferts-échanges de fichiers en proposant un service qui permet la compression d’images et leur affichage
grâce à la connexion à un ordinateur distant.
10 Bibliographie, Liens et Remerciements

— http ://www.cmi.univ-mrs.fr/˜melot/Master2/TPsignal PS.html
— Tous les fichiers .tex, .py de ce document :
https ://github.com/timosis/TIPE2013-2014
— L’interpréteur Python : http ://www.python.org/
— La librairie PIL pour Python : http ://www.pythonware.com/products/pil/
— La licence Creative Commons BY-SA :
http ://creativecommons.org/licenses/by-sa/3.0/
— Remerciements à : M. Petitjean
45
11 Annexes
Tout le code de ce projet est sous licence Creatice Commons BY-SA (voir p.45).
11.1 Fichier ondelettes.py

1 #−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
2 # Name : o n d e l e t t e s . py
3 # Purpose : d e f i n i t i o n de c l a s s e s de t r a i t e m e n t d ’ image
4 #
5 # Author : Gaetan
6 #
7 # Created : 10/07/2013
8 # Copyright : ( c ) Gaetan Bahl / X a v i e r F r i e d e r i c h 2013
9 # Licence : CC−BY−SA
10 #−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
11
12 import Image , math
13 import time
14
15
16 class Matrice :
17
18 def init ( s e l f , x , y , what ) :
19 s e l f . tableau = [ ]
20 self .x, self .y = x,y
21
22 f o r i in range ( s e l f . x ) :
23 s e l f . t a b l e a u . append ( [ ] )
24 f o r j in range ( s e l f . y ) :
25 s e l f . t a b l e a u [ i ] . append ( what )
26
27 def t r a n s p o s e ( s e l f ) :
28 s e l f . t a b l e a u = [ [ row [ i ] f o r row in s e l f . t a b l e a u ] f o r i in range ( s e l f . y ) ]
29 self .x, self .y = self .y, self .x
30
31 def add ( s e l f , m a t r i c e ) :
32
33 f o r i in range ( n ) :
34 f o r j in range ( p ) :
35 s e l f . t a b l e a u [ i ] [ j ] += m a t r i c e . t a b l e a u [ i ] [ j ]
36
37 def m u l t i p l y ( s e l f , m a t r i c e ) :
38
41 somme = 0
42 f o r k in range ( s e l f . y ) :
43 somme += s e l f . t a b l e a u [ i ] [ k ] ∗ m a t r i c e . t a b l e a u [ k ] [ j ]
44
45 def copy ( s e l f , m a t r i c e ) :
46
49 s e l f . tableau [ i ] [ j ] = matrice . tableau [ i ] [ j ]
50
51 def update ( s e l f ) :
52 s e l f . x = len ( s e l f . t a b l e a u )
53 s e l f . y = len ( s e l f . t a b l e a u [ 0 ] )
54
55 def s a v e ( s e l f ) :
56 s e l f . tableau2 = l i s t ( s e l f . tableau )
57
58 def s a v e 1 ( s e l f ) :
59 s e l f . mat orig = l i s t ( s e l f . tableau )
60
61 def r e s t o r e ( s e l f ) :
46
62 s e l f . tableau = l i s t ( s e l f . mat orig )

63
64 c l a s s MatriceImage ( ) :
65
66 def init ( self , lienimage ) :
67 s e l f . lienimage = lienimage
68 s e l f . image = Image . open ( l i e n i m a g e )
69 s e l f . p i x = s e l f . image . l o a d ( )
70 s e l f . s i z e x , s e l f . s i z e y = s e l f . image . s i z e
71 s e l f . matrice = Matrice ( s e l f . sizex , s e l f . sizey , s e l f . pix [ 0 , 0 ] )
72 s e l f . f i l l ()
73
74 def f i l l ( s e l f ) :
75 f o r i in range ( s e l f . s i z e x ) :
76 f o r j in range ( s e l f . s i z e y ) :
77 s e l f . matrice . tableau [ i ] [ j ] = s e l f . pix [ i , j ]
78
79 def g r a y s c a l e m e a n ( s e l f ) :
82 mean = ( s e l f . p i x [ i , j ] [ 0 ] + s e l f . p i x [ i , j ] [ 1 ] + s e l f . p i x [ i , j ] [ 2 ] ) /3
83 s e l f . p i x [ i , j ] = ( mean , mean , mean )
84
85 def g r a y s c a l e m e a n m a t r i x ( s e l f ) :
86 s e l f . matrixgray = Matrice ( s e l f . sizex , s e l f . sizey , 0 )
89 mean = ( s e l f . p i x [ i , j ] [ 0 ] + s e l f . p i x [ i , j ] [ 1 ] + s e l f . p i x [ i , j ] [ 2 ] ) /3
90 s e l f . m a t r i x g r a y . t a b l e a u [ i ] [ j ] = mean
91
92 def g e t m a t r i x r e d ( s e l f ) :
93 s e l f . matrixred = Matrice ( s e l f . sizex , s e l f . sizey , s e l f . pix [ 0 , 0 ] [ 0 ] )
96 s e l f . matrixred . tableau [ i ] [ j ] = s e l f . matrice . tableau [ i ] [ j ] [ 0 ]
97
98 def g e t m a t r i x b l u e ( s e l f ) :
99 s e l f . matrixblue = Matrice ( s e l f . sizex , s e l f . sizey , s e l f . pix [ 0 , 0 ] [ 2 ] )
102 s e l f . matrixblue . tableau [ i ] [ j ] = s e l f . matrice . tableau [ i ] [ j ] [ 2 ]
103
104 def g e t m a t r i x g r e e n ( s e l f ) :
105 s e l f . matrixgreen = Matrice ( s e l f . sizex , s e l f . sizey , s e l f . pix [ 0 , 0 ] [ 1 ] )
108 s e l f . matrixgreen . tableau [ i ] [ j ] = s e l f . matrice . tableau [ i ] [ j ] [ 1 ]
109
110 def s a v e ( s e l f , nom) :
111 s e l f . image . s a v e (nom)
112
113 def o n d e l e t t e h a a r ( s e l f , t a b l e a u v a l e u r s , o r d r e ) :
114 l o n g u e u r = len ( t a b l e a u v a l e u r s )
115 coeff approx , coeff ondelettes = [ ] , [ ]
116 f o r i in range ( l o n g u e u r / 2 ) :
117
118 c o e f f a p p r o x . append ( ( t a b l e a u v a l e u r s [ 2 ∗ i ] + t a b l e a u v a l e u r s [ 2 ∗ i +1]) / 2 )
119 c o e f f o n d e l e t t e s . append ( ( t a b l e a u v a l e u r s [ 2 ∗ i ] − t a b l e a u v a l e u r s [ 2 ∗ i +1]) / 2 )
120
121 i f o r d r e == 1 :
122 return c o e f f a p p r o x , c o e f f o n d e l e t t e s
123 else :
124 return o n d e l e t t e h a a r ( c o e f f a p p r o x , o r d r e −1) , c o e f f o n d e l e t t e s
125
126 def g e t c o l o n n e ( s e l f , tab , num) :
127 col = [ ]
128 f o r i in range ( len ( tab ) ) :
129 c o l . append ( tab [ i ] [ num ] )
47
130 return c o l
131
132 def s e t c o l o n n e ( s e l f , m a t r i c e , tab , num) :
133 f o r i in range ( len ( tab ) ) :
134 m a t r i c e [ num ] [ i ] = tab [ i ]
135
136 def g e t l i g n e ( s e l f , tab , num) :
137 return tab [ num ]
138
139 def a p p l y h a a r l i g ( s e l f , m a t r i c e , c h i f f r e ) :
140 f o r i in range ( len ( m a t r i c e ) ) :
141 matrice [ i ] = s e l f . ondelette haar ( matrice [ i ] , 1 ) [ c h i f f r e ]
142
143 def a p p l y h a a r c o l ( s e l f , m a t r i c e ) :
144 f o r i in range ( len ( m a t r i c e [ 0 ] ) ) :
145 c o l = s e l f . getcolonne ( matrice , i )
146 col = s e l f . ondelette haar ( col , 1 ) [ 0 ]
147 s e l f . s e t c o l o n n e ( matrice , col , i )
148
149 def makeimagegray ( s e l f , m a t r i c e i m a g e ) :
150 m a t r i c e i m a g e . update ( )
151 im = Image . new ( ”RGB” , ( m a t r i c e i m a g e . x , m a t r i c e i m a g e . y ) , ” w h i t e ” )
152 p i x = im . l o a d ( )
153
154 f o r i in range ( m a t r i c e i m a g e . x ) :
155 f o r j in range ( m a t r i c e i m a g e . y ) :
156 pix [ i , j ] = ( int ( matriceimage . tableau [ i ] [ j ] ) , int ( matriceimage . tableau [ i ] [ j ] ) ,
int ( matriceimage . tableau [ i ] [ j ] ) )
157 return im
158
159 def h a a r g r a y s c a l e ( s e l f ) :
160 s e l f . grayscalemeanmatrix ( )
161
162 self . a p p l y h a a r l i g ( s e l f . matrixgray . tableau , 0 )
163 self . m a t r i x g r a y . update ( )
164 self . matrixgray . transpose ( )
166 self . a p p l y h a a r l i g ( s e l f . matrixgray . tableau , 0 )
168 self . matrixgray . transpose ( )
169 self . i m a g e h a a r g r a y = s e l f . makeimagegray ( s e l f . m a t r i x g r a y )
170
171 def update ( s e l f ) :
172 s e l f . s i z e x = matrice . x
173 s e l f . s i z e y = matrice . y
174
175 def c r e a t e c o e f m a t r i x ( s e l f ) :
176 s e l f . matrixcoefr = Matrice ( s e l f . matrixred . x , s e l f . matrixred . y , 0 )
177 s e l f . matrixcoefg = Matrice ( s e l f . matrixred . x , s e l f . matrixred . y , 0 )
178 s e l f . matrixcoefb = Matrice ( s e l f . matrixred . x , s e l f . matrixred . y , 0 )
179 s e l f . m a t r i x c o e f r . copy ( s e l f . m a t r i x r e d )
180 s e l f . m a t r i x c o e f g . copy ( s e l f . m a t r i x g r e e n )
181 s e l f . m a t r i x c o e f b . copy ( s e l f . m a t r i x b l u e )
182
183
184 def haar ( s e l f ) :
185
186 f o r i in [ s e l f . m a t r i x r e d , s e l f . m a t r i x g r e e n , s e l f . m a t r i x b l u e ] :
187 s e l f . a p p l y h a a r l i g ( i . tableau , 0 )
188 i . update ( )
189 i . save ( )
190 i . transpose ()
191 i . update ( )
193 i . update ( )
195
196 f o r i in [ s e l f . m a t r i x c o e f r , s e l f . m a t r i x c o e f g , s e l f . m a t r i x c o e f b ] :
48
197 i . save1 ( )
199 i . update ( )
200 i . save ( )
201 i . update ( )
202 i . restore ()
204 i . update ( )
206 i . update ( )
208 i . update ( )
210
211
212
213 def makeimage ( s e l f ) :
214 im = Image . new ( ”RGB” , ( s e l f . m a t r i x r e d . x , s e l f . matrixred . y ) , ” white ” )
215 p i x = im . l o a d ( )
216
217 f o r i in range ( s e l f . m a t r i x r e d . x ) :
218 f o r j in range ( s e l f . m a t r i x r e d . y ) :
219 pix [ i , j ] = ( int ( s e l f . matrixred . tableau [ i ] [ j ] ) , int ( s e l f . matrixgreen . tableau [ i
] [ j ] ) , int ( s e l f . matrixblue . tableau [ i ] [ j ] ) )
220 return im
221
222 def c o m p r e s s i o n ( s e l f , e p s i l o n ) :
223 f o r tab in [ s e l f . m a t r i x c o e f r . t a b l e a u , s e l f . m a t r i x c o e f g . t a b l e a u , s e l f . m a t r i x c o e f b .
tableau ] :
224 f o r i in tab :
225 f o r j in range ( len ( i ) ) :
226 i f abs ( i [ j ] ) < e p s i l o n :
227 i[j] = 0
228
229 f o r tab in [ s e l f . m a t r i x c o e f r . t a b l e a u 2 , s e l f . m a t r i x c o e f g . t a b l e a u 2 , s e l f . m a t r i x c o e f b .
tableau2 ] :
230 f o r i in tab :
231 f o r j in range ( len ( i ) ) :
232 i f abs ( i [ j ] ) < e p s i l o n :
233 i[j] = 0
234
235 def s y n t h e s e l i g n e s ( s e l f ) :
236 f o r i in range ( s e l f . s i z e x / 2 ) :
237 f o r j in range ( s e l f . s i z e y / 2 ) :
238 s e l f . pix [ 2 ∗ i , 2 ∗ j ] = ( int ( s e l f . matrixred . tableau [ i ] [ j ] + s e l f . m a t r i x c o e f r .
tableau [ i ] [ j ] ) , int ( s e l f . matrixgreen . tableau [ i ] [ j ] + s e l f . matrixcoefg .
tableau [ i ] [ j ] ) , int ( s e l f . matrixblue . tableau [ i ] [ j ] + s e l f . matrixcoefb .
tableau [ i ] [ j ] ) )
239 s e l f . p i x [ 2 ∗ i +1 ,2∗ j ] = ( i n t ( s e l f . m a t r i x r e d . t a b l e a u [ i ] [ j ] − s e l f . m a t r i x c o e f r .
tableau [ i ] [ j ] ) , int ( s e l f . matrixgreen . tableau [ i ] [ j ] − s e l f . matrixcoefg .
tableau [ i ] [ j ] ) , int ( s e l f . matrixblue . tableau [ i ] [ j ] − s e l f . matrixcoefb .
tableau [ i ] [ j ] ) )
240
241 def s y n t h e s e c o l o n n e s ( s e l f ) :
242
243 f o r y in range ( len ( s e l f . m a t r i x c o e f r . t a b l e a u 2 [ 0 ] ) ) :
244
245 f o r x in range ( len ( s e l f . m a t r i x c o e f r . t a b l e a u 2 ) ) :
246
247 s e l f . pix [ x , 2 ∗ y ] , s e l f . pix [ x ,2∗ y + 1 ] = ( int ( s e l f . pix [ x , 2 ∗ y ] [ 0 ] + s e l f .
m a t r i x c o e f r . tableau2 [ x ] [ y ] ) , int ( s e l f . pix [ x , 2 ∗ y ] [ 1 ] + s e l f . matrixcoefg .
tableau2 [ x ] [ y ] ) , int ( s e l f . pix [ x , 2 ∗ y ] [ 2 ] + s e l f . matrixcoefb . tableau2 [ x ] [
y ] ) ) , ( int ( s e l f . pix [ x , 2 ∗ y ] [ 0 ] − s e l f . m a t r i x c o e f r . tableau2 [ x ] [ y ] ) , int (
s e l f . pix [ x , 2 ∗ y ] [ 1 ] − s e l f . matrixcoefg . tableau2 [ x ] [ y ] ) , int ( s e l f . pix [ x
,2∗ y ] [ 2 ] − s e l f . matrixcoefb . tableau2 [ x ] [ y ] ) )
248
249 def c l e a r i m a g e ( s e l f ) :
49
252 s e l f . pix [ i , j ] = (255 ,0 ,0)
253
254 def f a s t h a a r ( s e l f , e p s i l o n , xa , xb , ya , yb ) :
255
256 f o r x in range ( xa / 2 , xb / 2 ) :
257
258 f o r y in range ( ya / 2 , yb / 2 ) :
259 #c o p i e r l e s 4 p i x e l s dans un c a r r e
260
261 carres = [ ]
262
263 f o r i in range ( 3 ) :
264 c a r r e s . append ( [ [ s e l f . pix [2∗ x ,2∗ y ] [ i ] , s e l f . pix [2∗ x ,2∗ y + 1 ] [ i ] ] , [
s e l f . p i x [ 2 ∗ x +1 ,2∗ y ] [ i ] , s e l f . p i x [ 2 ∗ x +1 ,2∗ y + 1 ] [ i ] ] ] )
265
266 ##ANALYSE
267 o n d l h a u t = [ ( c a r r e s [ i ] [ 0 ] [ 0 ] − c a r r e s [ i ] [ 1 ] [ 0 ] ) /2 f o r i in range ( 3 ) ]
268 o n d l b a s = [ ( c a r r e s [ i ] [ 0 ] [ 1 ] − c a r r e s [ i ] [ 1 ] [ 1 ] ) /2 f o r i in range ( 3 ) ]
269
270 f o r i in range ( 3 ) :
271 c a r r e s [ i ] [ 0 ] [ 0 ] = ( c a r r e s [ i ] [ 0 ] [ 0 ] + c a r r e s [ i ] [ 1 ] [ 0 ] ) /2
273
274 ondlmix = [ ( c a r r e s [ i ] [ 0 ] [ 0 ] − c a r r e s [ i ] [ 0 ] [ 1 ] ) /2 f o r i in range ( 3 ) ]
275
276 f o r i in range ( 3 ) :
278
279 ##SYNTHESE
280 f o r i in range ( 3 ) :
281 i f abs ( ondlmix [ i ] ) < e p s i l o n :
282 carres [ i ] [ 0 ] [ 1 ] = carres [ i ][0][0]
283 else :
284 carres [ i ] [ 0 ] [ 1 ] = carres [ i ] [ 0 ] [ 0 ] − ondlmix [ i ]
285 carres [ i ] [ 0 ] [ 0 ] = carres [ i ] [ 0 ] [ 0 ] + ondlmix [ i ]
286
287 i f abs ( o n d l h a u t [ i ] ) < epsilon :
288 carres [ i ] [ 1 ] [ 0 ] = carres [ i ] [ 0 ] [ 0 ]
289 else :
290 carres [ i ] [ 1 ] [ 0 ] = c a r r e s [ i ] [ 0 ] [ 0 ] − ondlhaut [ i ]
291 carres [ i ] [ 0 ] [ 0 ] = c a r r e s [ i ] [ 0 ] [ 0 ] + ondlhaut [ i ]
292
293 i f abs ( o n d l b a s [ i ] ) < e p s i l o n :
294 carres [ i ] [ 1 ] [ 1 ] = carres [ i ][0][1]
295 else :
296 carres [ i ] [ 1 ] [ 1 ] = carres [ i ] [ 0 ] [ 1 ] − ondlbas [ i ]
297 carres [ i ] [ 0 ] [ 1 ] = carres [ i ] [ 0 ] [ 1 ] + ondlbas [ i ]
298
299 f o r i in [ 2 ∗ x , 2 ∗ x + 1 ] :
300 f o r j in [ 2 ∗ y , 2 ∗ y + 1 ] :
301 s e l f . p i x [ i , j ] = ( c a r r e s [ 0 ] [ i −2∗x ] [ j −2∗y ] , c a r r e s [ 1 ] [ i −2∗x ] [ j −2∗y ] ,
c a r r e s [ 2 ] [ i −2∗x ] [ j −2∗y ] )
302
303
304
305 def main ( ) :
306
307 image = MatriceImage ( ” images / c h a t . j p g ” )
308 s t a r t = time . time ( )
309
310 image . f a s t h a a r ( 2 , 1 0 , image . s i z e x , 0 , image . s i z e y )
311
312 end = time . time ( )
313 print end − s t a r t
314 image . image . s a v e ( ” c h a t . j p g ” , ’JPEG ’ , q u a l i t y = 1 0 0 )
315
316 if name == ’ main ’:
50
317 main ( )
11.2 Fichier ondelettesGUI.py

1 #−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
2 # Name : o n d e l e t t e s G U I . py
3 # Purpose : i n t e r f a c e g r a p h i q u e du TIPE s u r l e s o n d e l e t t e s
4 #
5 # Author : Gaetan Bahl
6 #
7 # Created : 08/08/2013
8 # Copyright : ( c ) Gaetan Bahl 2013
10 #−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
11
12 from T k i n t e r import ∗
13 import t k F i l e D i a l o g , ImageTk
14 from o n d e l e t t e s import ∗
15 from t t k import Frame , S t y l e
16 from T k c o n s t a n t s import ∗
17 from s u b p r o c e s s import c a l l
18
19
20 c l a s s A p p l i ( Frame ) :
21
22 def init ( s e l f , parent ) :
23 Frame . init ( s e l f , parent )
24
25 s e l f . parent = parent
26 s e l f . initUI ()
27
28 def c l i ( s e l f ) :
29 c a l l ( [ ” . / c l i e n t . py ” , ” s r ” , s e l f . f i l e n a m e ] )
30
31
32 def i n i t U I ( s e l f ) :
33
34 s e l f . p a r e n t . t i t l e ( ” O n d e l e t t e s GUI” )
35 s e l f . pack ( f i l l =BOTH, expand =1)
36 menubar = Menu( s e l f . p a r e n t )
37 s e l f . p a r e n t . c o n f i g ( menu=menubar )
38
39 f i l e M e n u = Menu( menubar )
40 f i l e M e n u . add command ( l a b e l=” O u v r i r ” , command= s e l f . a s k o p e n f i l e n a m e )
41 f i l e M e n u . add command ( l a b e l=” E n r e g i s t r e r ” , command= s e l f . a s k s a v e a s f i l e n a m e )
42 f i l e M e n u . add command ( l a b e l=” E x i t ” , command= s e l f . o n E x i t )
43 f i l e M e n u . add command ( l a b e l=” Send t o S e r v e r ” , command= s e l f . c l i )
44 menubar . a d d c a s c a d e ( l a b e l=” F i c h i e r ” , menu=f i l e M e n u )
45
46 editMenu = Menu( menubar )
47 editMenu . add command ( l a b e l=” Nuances de g r i s ” , command= s e l f . g r a y s c a l e )
48 editMenu . add command ( l a b e l=” Compresser ” , command= s e l f . a s k c o m p r e s s i o n )
49 editMenu . add command ( l a b e l=” Compresser ( new ) ” , command= s e l f . a s k c o m p r e s s i o n 2 )
50 editMenu . add command ( l a b e l=” R e s o l u t i o n 1/2 ” , command= s e l f . o n E x i t )
51 menubar . a d d c a s c a d e ( l a b e l=” E d i t i o n ” , menu=editMenu )
52
53 S t y l e ( ) . c o n f i g u r e ( ”TFrame” , background=”#FFF” )
54
55 def a s k o p e n f i l e n a m e ( s e l f ) :
56
57 filename = tkFileDialog . askopenfilename ( d e f a u l t e x t e n s i o n = ” jpg ” )
58 s e l f . filename = filename
59 s e l f . m a t r i c e i m a g e = MatriceImage ( f i l e n a m e )
60 s e l f . image = s e l f . m a t r i c e i m a g e . image
61 s e l f . imgtk = ImageTk . PhotoImage ( s e l f . image )
62 s e l f . l a b e l i m g = L a b e l ( s e l f , image= s e l f . imgtk )
51
63 s e l f . l a b e l i m g . image = s e l f . imgtk
64 s e l f . l a b e l i m g . p l a c e ( x = 0 , y=0)
65 s e l f . l a b e l i m g . pack ( )
66
67
68 s e l f . p a r e n t . geometry ( s t r ( s e l f . m a t r i c e i m a g e . s i z e x +5)+” x ”+s t r ( s e l f . m a t r i c e i m a g e . s i z e y
+5)+”+100+300” )
69
70 def a s k s a v e a s f i l e n a m e ( s e l f ) :
71
72 filename = tkFileDialog . asksaveasfilename ( d e f a u l t e x t e n s i o n = ” jpg ” )
73
74 s e l f . image . s a v e ( f i l e n a m e , ’JPEG ’ , q u a l i t y = 1 0 0 )
75
76 def a s k c o m p r e s s i o n ( s e l f ) :
77 global c om pr e ss
78 f e n = Tk ( )
79 f e n . geometry ( ” 300 x100 +300+300” )
80 box = D i a l o g S c a l e ( f e n )
81 f e n . mainloop ( )
82 fen . destroy ()
83 s e l f . compression ( )
84
85 def a s k c o m p r e s s i o n 2 ( s e l f ) :
87 f e n = Tk ( )
88 f e n . geometry ( ” 300 x100 +300+300” )
89 box = D i a l o g S c a l e ( f e n )
90 f e n . mainloop ( )
91 fen . destroy ()
92 s e l f . compression2 ( )
93
94 def c o m p r e s s i o n ( s e l f ) :
95
96 self . matriceimage . getmatrixblue ( )
97 self . matriceimage . getmatrixgreen ( )
98 self . matriceimage . getmatrixred ( )
99 self . matriceimage . c r e a t e c o e f m a t r i x ( )
100 self . m a t r i c e i m a g e . haar ( )
101 self . m a t r i c e i m a g e . c o m p r e s s i o n ( c om pr e ss )
102 self . matriceimage . s y n t h e s e l i g n e s ( )
103 self . matriceimage . synthesecolonnes ( )
104 self . labelimg . destroy ()
105
106 s e l f . displayimage ()
107
108 def c o m p r e s s i o n 2 ( s e l f ) :
109
110
111 s e l f . m a t r i c e i m a g e . f a s t h a a r ( compress , 0 , s e l f . m a t r i c e i m a g e . s i z e x , 0 , s e l f .
matriceimage . s i z e y )
112
113 s e l f . labelimg . destroy ()
114
116
117 def g r a y s c a l e ( s e l f ) :
118 s e l f . matriceimage . grayscalemeanmatrix ( )
119 s e l f . image = s e l f . m a t r i c e i m a g e . makeimagegray ( s e l f . m a t r i c e i m a g e . m a t r i x g r a y )
120 s e l f . m a t r i c e i m a g e . image = s e l f . m a t r i c e i m a g e . makeimagegray ( s e l f . m a t r i c e i m a g e .
matrixgray )
121 s e l f . labelimg . destroy ()
122
124
125 def d i s p l a y i m a g e ( s e l f ) :
126 s e l f . imgtk = ImageTk . PhotoImage ( s e l f . m a t r i c e i m a g e . image )
127 s e l f . l a b e l i m g = L a b e l ( s e l f , image= s e l f . imgtk )
52
128 self . l a b e l i m g . image = s e l f . imgtk

129 self . l a b e l i m g . p l a c e ( x = 0 , y=0)
130 self . l a b e l i m g . pack ( )
131 self . update ( )
132
133
134
135 def o n E x i t ( s e l f ) :
136 s e l f . quit ()
137
138
139 c l a s s D i a l o g S c a l e ( Frame ) :
140 def init ( s e l f , parent ) :
141 Frame . init ( s e l f , parent )
142
143 s e l f . parent = parent
144 s e l f . initUI ()
145
146 def i n i t U I ( s e l f ) :
147
148 s e l f . p a r e n t . t i t l e ( ” Compression ” )
149 s e l f . style = Style ()
150 s e l f . s t y l e . theme use ( ” d e f a u l t ” )
151
152 s e l f . pack ( f i l l =BOTH, expand =1)
153
154 s c a l e = S c a l e ( s e l f , f r o m =0 , t o =255 ,command= s e l f . o n S c a l e , o r i e n t= HORIZONTAL)
155 s c a l e . p l a c e ( x=90 , y=20)
156
157
158 self . l a b e l 2 = L a b e l ( s e l f , t e x t=” C h o i s i s s e z un n i v e a u de c o m p r e s s i o n ” )
159 self . l a b e l 2 . p l a c e ( x=52 , y=0)
160 self . q u i t B u t t o n = Button ( s e l f , t e x t=” Ok ” , command= s e l f . ok )
161 self . q u i t B u t t o n . p l a c e ( x =120 , y=65)
162
163 def o n S c a l e ( s e l f , v a l ) :
164
165 s e l f . v a r i a b l e = int ( val )
166
167 def ok ( s e l f ) :
169 co mp re s s = s e l f . v a r i a b l e
170 s e l f . quit ()
171
172
173 def main ( ) :
174
175 r o o t = Tk ( )
176 r o o t . geometry ( ” 250 x250 +300+300” )
177 app = A p p l i ( r o o t )
178 r o o t . mainloop ( )
179
180
182 main ( )
11.3 Fichier bench.py

1 #−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
2 # Name : bench . py
3 # Purpose : benchmarking d ’ a l g o r i t h m e s
4 #
6 #
7 # Created : 19/08/2013
53
10 #−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
11
12
13 import Image
14 import time
15 import random
16 from o n d e l e t t e s import ∗
17
18
19 def i m a g e g e n ( x ) :
20 im = Image . new ( ”RGB” , ( x , x ) , ” w h i t e ” )
21 return im
22
23
24 def randomize ( pix , x ) :
25 f o r i in range ( x ) :
26 f o r j in range ( x ) :
27 p i x [ i , j ] = ( random . r a n d r a n g e ( 2 5 5 ) , random . r a n d r a n g e ( 2 5 5 ) ,
28 random . r a n d r a n g e ( 2 5 5 ) )
29
30
31 def b e n c h s q u a r e ( ran ) :
32
33 f o r i in ran :
34 image = i m a g e g e n ( 2 ∗ i )
35 p i x = image . l o a d ( )
36 randomize ( pix , 2 ∗ i )
38 f a s t h a a r ( pix , 0 , 0 , 2 ∗ i , 0 , 2 ∗ i )
40 print s t r ( i ) + ” ” + s t r ( end − s t a r t )
41
42
43 def f a s t h a a r ( pix , e p s i l o n , xa , xb , ya , yb ) :
44
45 f o r x in range ( xa / 2 , xb / 2 ) :
46
47 f o r y in range ( ya / 2 , yb / 2 ) :
48
49 carres = [ ]
50
51 f o r i in range ( 3 ) :
52 c a r r e s . append ( [ [ p i x [ 2 ∗ x , 2 ∗ y ] [ i ] , p i x [ 2 ∗ x , 2 ∗ y + 1 ] [ i ] ] ,
53 [ pix [2 ∗ x + 1 , 2 ∗ y ] [ i ] , pix [2 ∗ x + 1 , 2 ∗ y + 1 ] [ i ] ] ] )
54
55 ondlhaut = [ ( c a r r e s [ i ] [ 0 ] [ 0 ] − c a r r e s [ i ] [ 1 ] [ 0 ] ) / 2
56 f o r i in range ( 3 ) ]
57 ondlbas = [ ( c a r r e s [ i ] [ 0 ] [ 1 ] − c a r r e s [ i ] [ 1 ] [ 1 ] ) / 2
59
61 carres [ i ] [ 0 ] [ 0 ] = ( carres [ i ] [ 0 ] [ 0 ] + carres [ i ] [ 1 ] [ 0 ] ) / 2
63
64 ondlmix = [ ( c a r r e s [ i ] [ 0 ] [ 0 ] − c a r r e s [ i ] [ 0 ] [ 1 ] ) / 2
66
69
71 i f abs ( ondlmix [ i ] ) < e p s i l o n :
72 carres [ i ] [ 0 ] [ 1 ] = carres [ i ][0][0]
73 else :
74 carres [ i ] [ 0 ] [ 1 ] = carres [ i ] [ 0 ] [ 0 ] − ondlmix [ i ]
75 carres [ i ] [ 0 ] [ 0 ] = carres [ i ] [ 0 ] [ 0 ] + ondlmix [ i ]
76
54
77 i f abs ( o n d l h a u t [ i ] ) < epsilon :

78 carres [ i ] [ 1 ] [ 0 ] = carres [ i ] [ 0 ] [ 0 ]
79 else :
80 carres [ i ] [ 1 ] [ 0 ] = c a r r e s [ i ] [ 0 ] [ 0 ] − ondlhaut [ i ]
81 carres [ i ] [ 0 ] [ 0 ] = c a r r e s [ i ] [ 0 ] [ 0 ] + ondlhaut [ i ]
82
83 i f abs ( o n d l b a s [ i ] ) < e p s i l o n :
84 carres [ i ] [ 1 ] [ 1 ] = carres [ i ][0][1]
85 else :
86 carres [ i ] [ 1 ] [ 1 ] = carres [ i ] [ 0 ] [ 1 ] − ondlbas [ i ]
87 carres [ i ] [ 0 ] [ 1 ] = carres [ i ] [ 0 ] [ 1 ] + ondlbas [ i ]
88
89 f o r i in [ 2 ∗ x , 2 ∗ x + 1 ] :
90 f o r j in [ 2 ∗ y , 2 ∗ y + 1 ] :
91 pix [ i , j ] = ( c a r r e s [ 0 ] [ i − 2 ∗ x ] [ j − 2 ∗ y ] ,
92 carres [ 1 ] [ i − 2 ∗ x ] [ j − 2 ∗ y ] ,
93 carres [ 2 ] [ i − 2 ∗ x ] [ j − 2 ∗ y ])
94
95
96 def main ( ) :
97 b e n c h s q u a r e ( range ( 1 , 1 0 0 0 ) )
98
99
101 main ( )
11.4 Fichier serveur.py

1 #! / u s r / b i n / python2
2 #−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
3 # Name : s e r v e u r . py
4 # Purpose : s e r v e u r du TIPE s u r l e s o n d e l e t t e s
5 #
7 #
8 # Created : 20/08/2013
11 #−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
12
13
14 import socket
15 import Image
16 import time
17 import struct
18
19
20
21 def r e c v I m a g e ( conn , msg ) :
22 t i t l e = msg . s p l i t ( ’ ’ )
23 s i z e x , s i z e y = int ( t i t l e [ 1 ] ) , int ( t i t l e [ 2 ] )
24 image = Image . new ( ”RGB” , ( s i z e x , s i z e y ) , ” w h i t e ” )
26 conn . send ( b” ok ” )
27 msg , img = ” ” , ” ”
28 unpacker = s t r u c t . S t r u c t ( ”BBB” )
29 while msg . e n d s w i t h ( ” end ” ) == F a l s e :
30 img += msg
31 msg = conn . r e c v ( 3 )
32
33
34 print ” p i x e l s r e c u s ”
35
36 f o r i in range ( s i z e x ) :
37 f o r j in range ( s i z e y ) :
55
38 p i x e l = unpacker . unpack ( img [ ( i ∗ s i z e y + j ) ∗ unpacker . s i z e : ( i ∗ s i z e y + j + 1 ) ∗

unpacker . s i z e ] )
39 pix [ i , j ] = ( int ( p i x e l [ 0 ] ) , int ( p i x e l [ 1 ] ) , int ( p i x e l [ 2 ] ) )
40
41 print ” image c r e a t e d ”
42
43 image . s a v e ( ” s r v ” + t i t l e [ 3 ] , ’JPEG ’ , q u a l i t y = 1 0 0 )
44 print ” image e n r e g i s t r e e ”
45 conn . send ( b ’ s a v e d image ’ )
46
47
48 def f a s t h a a r s r v ( s o c k e t , msg , e p s i l o n =0) :
49 t = msg . s p l i t ( ’ ’ )
50 image = Image . open ( t [ 1 ] )
52
53 f i c h i e r = open ( ” c o e f / ” + t [ 1 ] [ : − 4 ] + ” . o d l ” , ’wb ’ )
54 s i z e x , s i z e y = image . s i z e
55
56
57 print ” c o m p r e s s i o n en c o u r s ”
58 f o r x in range ( s i z e x / 2 ) :
59 f o r y in range ( s i z e y / 2 ) :
60
61 carres = [ ]
62
64 c a r r e s . append ( [ [ p i x [ 2 ∗ x , 2 ∗ y ] [ i ] , p i x [ 2 ∗ x , 2 ∗ y + 1 ] [ i ] ] ,
65 [ pix [2 ∗ x + 1 , 2 ∗ y ] [ i ] , pix [2 ∗ x + 1 , 2 ∗ y + 1 ] [ i ] ] ] )
66
67 ondlhaut = [ ( c a r r e s [ i ] [ 0 ] [ 0 ] − c a r r e s [ i ] [ 1 ] [ 0 ] ) / 2
69 ondlbas = [ ( c a r r e s [ i ] [ 0 ] [ 1 ] − c a r r e s [ i ] [ 1 ] [ 1 ] ) / 2
71
75
76 ondlmix = [ ( c a r r e s [ i ] [ 0 ] [ 0 ] − c a r r e s [ i ] [ 0 ] [ 1 ] ) / 2
78
79
80 f o r i in [ ondlmix , ondlhaut , o n d l b a s ] :
81 f i c h i e r . w r i t e ( s t r u c t . pack ( ” bbb ” , i [ 0 ] , i [ 1 ] , i [ 2 ] ) )
82
83
84 f i c h i e r . close ()
85 print ’ c o m p r e s s i o n OK ’
86 s o c k e t . send ( b”OK” )
87
88
89 def s e n d C o e f ( sock , msg ) :
90 banana = msg . s p l i t ( ” ” )
91 f i c h i e r = open ( ” c o e f / s r v ” + banana [ 1 ] [ : − 4 ] + ” . o d l ” , ’ rb ’ )
92 print ” e n v o i d e s c o e f f i c i e n t s ”
93 txt = f i c h i e r . readlines ()
94 f o r i in t x t :
95 s o c k . send ( i )
96 print ” c o e f f i c i e n t s e n v o y e s ”
97 s o c k . send ( b ’ end ’ )
98 ms = s o c k . r e c v ( 2 )
99 print ms . d ec od e ( )
100 f i c h i e r . close ()
101
102
103
104 def main ( ) :
56
105
106 hote = ’ ’
107 p o r t = 13337
108
109 c o n n e x i o n = s o c k e t . s o c k e t ( s o c k e t . AF INET , s o c k e t .SOCK STREAM)
110 c o n n e x i o n . bind ( ( hote , p o r t ) )
111 while 1 :
112 connexion . l i s t e n (5)
113
114 m s g r e c u = b” ”
115 print ” a t t e n t e d ’ un c l i e n t ”
116 c o n n e x i o n c l i e n t , i n f o s c o n n e x i o n = connexion . accept ( )
117
118 print ” c l i e n t c o n n e c t e d ”
119
120 while m s g r e c u != b” s t o p ” :
121 time . s l e e p ( 0 . 1 )
122 msg = m s g r e c u . de co de ( )
123
124 i f msg . s t a r t s w i t h ( ’ sendimg ’ ) :
125 print ” image en c o u r s de r e c e p t i o n ”
126 r e c v I m a g e ( c o n n e x i o n c l i e n t , msg )
127 i f msg . s t a r t s w i t h ( ’ c om p re ss ’ ) :
128 f a s t h a a r s r v ( c o n n e x i o n c l i e n t , msg )
129 i f msg . s t a r t s w i t h ( ’ c o e f ’ ) :
130 s e n d C o e f ( c o n n e x i o n c l i e n t , msg )
131
132
133 msg recu = c o n n e x i o n c l i e n t . recv (1024)
134
135
136
137
138 print ( ” E x i t i n g ” )
139 connexion client . close ()
140 connexion . c l o s e ( )
141
142 if name == ” main ”:
143 main ( )
11.5 Fichier client.py

1 #! / u s r / b i n / python2
2 #−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
3 # Name : c l i e n t . py
4 # Purpose : c l i e n t du TIPE s u r l e s o n d e l e t t e s
5 #
7 #
8 # Created : 20/08/2013
11 #−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
12
13 import socket
14 import Image
15 import time
16 import struct
17 import sys
18
19 def sendImage ( s o c k e t , l i n k ) :
20 image = Image . open ( l i n k )
22 x , y = image . s i z e
23 s t r i n g = ” sendimg ” + s t r ( x ) + ” ” + s t r ( y ) + ” ” + l i n k
24 s o c k e t . send ( s t r i n g . e nc ode ( ’ a s c i i ’ ) )
57
25 reply = socket . recv (32)

26 i f r e p l y == b” ok ” :
27 t = ””
28 f o r i in range ( x ) :
29
30 f o r j in range ( y ) :
31 r , g , b = pix [ i , j ]
32 p a c k e r = s t r u c t . S t r u c t ( ”BBB” )
33 p i x e l = p a c k e r . pack ( r , g , b )
34 s o c k e t . send ( p i x e l )
35
36
37 s o c k e t . send ( b” end ” )
38 reply = socket . recv (11)
39
40 print ” server says : ” + reply
41
42 def a s k c o m p r e s s ( c o n n e x i o n , nom) :
43
44 mess = ” c om pr e ss ” + nom
45 c o n n e x i o n . send ( mess . en co de ( ’ a s c i i ’ ) )
46 reply = connexion . recv (2)
47 print ” s e r v e r s a y s : ” + r e p l y
48 return r e p l y
49
50 def s t o r e I m a g e ( l i n k ) :
51 image = Image . open ( l i n k )
53 x , y = image . s i z e
54
55 im = Image . new ( ”RGB” , ( x / 2 , y / 2 ) , ” w h i t e ” )
56 p i = im . l o a d ( )
57
58 f o r i in range ( x / 2 ) :
59 f o r j in range ( y / 2 ) :
60 r = ( ( ( pix [2 ∗ i , 2 ∗ j ][0] + pix [2 ∗ i + 1, 2 ∗ j ] [ 0 ] ) / 2) + ( ( pix [ 2 ∗ i , 2 ∗
j + 1 ] [ 0 ] + pix [2 ∗ i + 1, 2 ∗ j + 1][0]) / 2) ) / 2
61 g = ( ( ( pix [2 ∗ i , 2 ∗ j ][1] + pix [2 ∗ i + 1, 2 ∗ j ] [ 1 ] ) / 2) + ( ( pix [ 2 ∗ i , 2 ∗
j + 1 ] [ 1 ] + pix [2 ∗ i + 1, 2 ∗ j + 1][1]) / 2) ) / 2
62 b = ( ( ( pix [2 ∗ i , 2 ∗ j ][2] + pix [2 ∗ i + 1, 2 ∗ j ] [ 2 ] ) / 2) + ( ( pix [ 2 ∗ i , 2 ∗
j + 1 ] [ 2 ] + pix [2 ∗ i + 1, 2 ∗ j + 1][2]) / 2) ) / 2
63 pi [ i , j ] = ( r , g , b)
64
65 im . s a v e ( ” s t o r ” + l i n k , ’JPEG ’ , q u a l i t y = 1 0 0 )
66
67
68
69 def a s k c o e f f ( conn , nom) :
70
71 unpacker = s t r u c t . S t r u c t ( ” bbbbbbbbb ” )
72
73 print ’ demande en c o u r s ’
74 mess = ” c o e f ” + nom
75 conn . send ( mess . en co de ( ” a s c i i ” ) )
76
77 print ” r e c e p t i o n c o e f s ”
78 coefs = ’ ’
79 msg = ’ ’
80 while msg . e n d s w i t h ( b ’ end ’ ) == F a l s e :
81 c o e f s += msg
82 msg = conn . r e c v ( 9 )
83 print s t r ( len ( c o e f s ) ) + ” o c t e t s r e c u s ”
84 print ” r e c o n s t i t u t i o n image ”
85 image = Image . open ( ” s t o r ” + nom)
87 dim = image . s i z e
88 im = Image . new ( ”RGB” , ( dim [ 0 ] ∗ 2 , dim [ 1 ] ∗ 2 ) , ” w h i t e ” )
89 px = im . l o a d ( )
58
90 f o r i in range ( dim [ 0 ] ) :
91 f o r j in range ( dim [ 1 ] ) :
92 tab = unpacker . unpack ( c o e f s [ ( i ∗dim [ 1 ] + j ) ∗ unpacker . s i z e : ( i ∗dim [ 1 ] + j +1)∗
unpacker . s i z e ] )
93
94 px [ 2 ∗ i , 2 ∗ j ] = ( p i x [ i , j ] [ 0 ] + tab [ 0 ] + tab [ 3 ] , p i x [ i , j ] [ 1 ] + tab [ 1 ] + tab [ 4 ] ,
p i x [ i , j ] [ 2 ] + tab [ 2 ] + tab [ 5 ] )
95 px [ 2 ∗ i +1 ,2∗ j ] = ( p i x [ i , j ] [ 0 ] + tab [ 0 ] − tab [ 3 ] , p i x [ i , j ] [ 1 ] + tab [ 1 ] − tab [ 4 ] ,
p i x [ i , j ] [ 2 ] + tab [ 2 ] − tab [ 5 ] )
96 px [ 2 ∗ i , 2 ∗ j + 1 ] = ( p i x [ i , j ] [ 0 ] − tab [ 0 ] + tab [ 6 ] , p i x [ i , j ] [ 1 ] − tab [ 1 ] + tab
[ 7 ] , p i x [ i , j ] [ 2 ] − tab [ 2 ] + tab [ 8 ] )
97 px [ 2 ∗ i +1 ,2∗ j +1] = ( p i x [ i , j ] [ 0 ] − tab [ 0 ] − tab [ 6 ] , p i x [ i , j ] [ 1 ] − tab [ 1 ] − tab
[ 7 ] , p i x [ i , j ] [ 2 ] − tab [ 2 ] − tab [ 8 ] )
98
99
100 print ” e n r e g i s t r e m e n t ”
101 im . s a v e ( ’ 2 ’ + nom , ’JPEG ’ , q u a l i t y = 1 0 0 )
102 conn . send ( b ’ ok ’ )
103
104
105 def main ( a r g ) :
106
107 c o n n e x i o n = s o c k e t . s o c k e t ( s o c k e t . AF INET , s o c k e t .SOCK STREAM)
108 i f ’ r ’ in a r g [ 1 ] :
109 try :
110 connexion . connect ( ( argv [ 3 ] , 13337) )
111 except :
112 c o n n e x i o n . c o n n e c t ( ( ’ s r v . o r d i c l i c . eu ’ , 1 3 3 3 7 ) )
113 else :
114 connexion . connect ( ( ’ l o c a l h o s t ’ , 13337) )
115
116 if ’ s ’ in a r g [ 1 ] :
117 sendImage ( c o n n e x i o n , a r g [ 2 ] )
118 askcompress ( connexion , ’ sr v ’ + arg [ 2 ] )
119 storeImage ( arg [ 2 ] )
120 if ’ d ’ in a r g [ 1 ] :
121 a s k c o e f f ( connexion , arg [ 2 ] )
122
123 c o n n e x i o n . send ( b” s t o p ” )
124 connexion . c l o s e ( )
125
126
127 if name == ” m a i n ”:
128 main ( s y s . a r g v )
11.6 Fichier ondelettesCL.py

1 #nouveau programme pour l ’ a c c e l e r a t i o n m a t e r i e l l e
2 #g a e t a n 8/09/13
3
4 import Image
5 import numpy
6 import pyopencl as c l
7 import sys
8 import time
9
10 c l a s s Climage :
11
12 def init ( s e l f , image ) :
13
14 self . context = c l . create some context ()
15 self . queue = c l . CommandQueue ( s e l f . c o n t e x t )
16 self . nom = image
17 self . image = Image . open ( image )
18 self . p i x = s e l f . image . l o a d ( )
19 self . x , s e l f . y = s e l f . image . s i z e
59
20
21 f = open ( ’ haar . c l ’ , ’ r ’ )
22 f s t r = ”” . join ( f . readlines () )
23 s e l f . program = c l . Program ( s e l f . c o n t e x t , f s t r ) . build ()
24 f . close ()
25
26 def e x e c u t e ( s e l f , e p s i l o n ) :
27
28 tabstl = s e l f . gettl ()
29 t l r = numpy . a r r a y ( t a b s t l [ 0 ] , dtype = numpy . i n t 3 2 )
30 t l g = numpy . a r r a y ( t a b s t l [ 1 ] , dtype = numpy . i n t 3 2 )
31 t l b = numpy . a r r a y ( t a b s t l [ 2 ] , dtype = numpy . i n t 3 2 )
32
33 tabstr = s e l f . gettr ()
34 t r r = numpy . a r r a y ( t a b s t r [ 0 ] , dtype = numpy . i n t 3 2 )
35 t r g = numpy . a r r a y ( t a b s t r [ 1 ] , dtype = numpy . i n t 3 2 )
36 t r b = numpy . a r r a y ( t a b s t r [ 2 ] , dtype = numpy . i n t 3 2 )
37
38 tabsll = s e l f . g e t l l ()
39 l l r = numpy . a r r a y ( t a b s l l [ 0 ] , dtype = numpy . i n t 3 2 )
40 l l g = numpy . a r r a y ( t a b s l l [ 1 ] , dtype = numpy . i n t 3 2 )
41 l l b = numpy . a r r a y ( t a b s l l [ 2 ] , dtype = numpy . i n t 3 2 )
42
43 tabslr = s e l f . getlr ()
44 l r r = numpy . a r r a y ( t a b s l r [ 0 ] , dtype = numpy . i n t 3 2 )
45 l r g = numpy . a r r a y ( t a b s l r [ 1 ] , dtype = numpy . i n t 3 2 )
46 l r b = numpy . a r r a y ( t a b s l r [ 2 ] , dtype = numpy . i n t 3 2 )
47
49 f o r i in [ [ t l r , t r r , l l r , l r r ] , [ t l g , t r g , l l g , l r g ] , [ t l b , trb , l l b , l r b ] ] :
50 mf = c l . m e m f l a g s
51 t l b u f = c l . Buffer ( s e l f . context , mf .READ WRITE | mf . COPY HOST PTR,
h o s t b u f=i [ 0 ] )
52 t r b u f = c l . Buffer ( s e l f . context , mf .READ WRITE | mf . COPY HOST PTR,
h o s t b u f=i [ 1 ] )
53 l l b u f = c l . Buffer ( s e l f . context , mf .READ WRITE | mf . COPY HOST PTR,
h o s t b u f=i [ 2 ] )
54 l r b u f = c l . Buffer ( s e l f . context , mf .READ WRITE | mf . COPY HOST PTR,
h o s t b u f=i [ 3 ] )
55 e p s i l o n = numpy . i n t 3 2 ( e p s i l o n )
56
57 s e l f . program . haar ( s e l f . queue , i [ 0 ] . shape , None , t l b u f , t r b u f ,
ll buf , lr buf , epsilon )
58
59
60 c l . e n q u e u e r e a d b u f f e r ( s e l f . queue , t l b u f , i [ 0 ] ) . w a i t ( )
61
62 c l . e n q u e u e r e a d b u f f e r ( s e l f . queue , t r b u f , i [ 1 ] ) . w a i t ( )
63 c l . e n q u e u e r e a d b u f f e r ( s e l f . queue , l l b u f , i [ 2 ] ) . w a i t ( )
64 c l . e n q u e u e r e a d b u f f e r ( s e l f . queue , l r b u f , i [ 3 ] ) . w a i t ( )
65
67
68 print end − s t a r t
69
70 f o r i in range ( s e l f . x / 2 ) :
71 f o r j in range ( s e l f . y / 2 ) :
72 t = s e l f . y /2∗ i + j
73
74 self . pix [2∗ i ,2∗ j ] = ( t l r [ t ] , t l g [ t ] , t l b [ t ] )
75 self . p i x [ 2 ∗ i +1 ,2∗ j ] = ( t r r [ t ] , t r g [ t ] , t r b [ t ] )
76 self . p i x [ 2 ∗ i , 2 ∗ j +1] = ( l l r [ t ] , l l g [ t ] , l l b [ t ] )
77 self . p i x [ 2 ∗ i +1 ,2∗ j +1] = ( l r r [ t ] , l r g [ t ] , l r b [ t ] )
78
79
80 def s a v e ( s e l f , a ) :
81
82 s e l f . image . s a v e ( a , ’JPEG ’ , q u a l i t y = 1 0 0 )
60
83
84
85 def g e t t l ( s e l f ) :
86
87 t a b r , tabg , tabb = [ ] , [ ] , [ ]
90 t a b r . append ( s e l f . p i x [ 2 ∗ i , 2 ∗ j ] [ 0 ] )
91 tabg . append ( s e l f . p i x [ 2 ∗ i , 2 ∗ j ] [ 1 ] )
92 tabb . append ( s e l f . p i x [ 2 ∗ i , 2 ∗ j ] [ 2 ] )
93 return t a b r , tabg , tabb
94
95 def g e t t r ( s e l f ) :
96
97 t a b r , tabg , tabb = [ ] , [ ] , [ ]
100 t a b r . append ( s e l f . p i x [ 2 ∗ i +1 ,2∗ j ] [ 0 ] )
101 tabg . append ( s e l f . p i x [ 2 ∗ i +1 ,2∗ j ] [ 1 ] )
102 tabb . append ( s e l f . p i x [ 2 ∗ i +1 ,2∗ j ] [ 2 ] )
104
105 def g e t l l ( s e l f ) :
106
107 t a b r , tabg , tabb = [ ] , [ ] , [ ]
110 t a b r . append ( s e l f . p i x [ 2 ∗ i , 2 ∗ j + 1 ] [ 0 ] )
111 tabg . append ( s e l f . p i x [ 2 ∗ i , 2 ∗ j + 1 ] [ 1 ] )
112 tabb . append ( s e l f . p i x [ 2 ∗ i , 2 ∗ j + 1 ] [ 2 ] )
114
115
116 def g e t l r ( s e l f ) :
117
118 t a b r , tabg , tabb = [ ] , [ ] , [ ]
121 t a b r . append ( s e l f . p i x [ 2 ∗ i +1 ,2∗ j + 1 ] [ 0 ] )
122 tabg . append ( s e l f . p i x [ 2 ∗ i +1 ,2∗ j + 1 ] [ 1 ] )
123 tabb . append ( s e l f . p i x [ 2 ∗ i +1 ,2∗ j + 1 ] [ 2 ] )
125
126
127 def main ( a r g s ) :
128 img = Climage ( a r g s [ 1 ] )
129
130 img . e x e c u t e ( 1 0 )
131
132 img . s a v e ( a r g s [ 2 ] )
133
134
135 if name == ” m a i n ”:
136 main ( s y s . a r g v )
11.7 Fichier haar.cl

1 kernel
2 v o i d haar ( g l o b a l i n t ∗ t l , g l o b a l int ∗ tr , g l o b a l int ∗ l l , g l o b a l int ∗ l r , int
epsilon ){
3
4 int i = g e t g l o b a l i d ( 0 ) ;
5
6
7 int ondlhaut = ( t l [ i ] − t r [ i ] ) / 2 ;
8 int ondlbas = ( l l [ i ] − l r [ i ] ) / 2 ;
61
9 tl [ i ] = ( tl [ i ] + tr [ i ]) /2;
10 ll [ i ] = ( ll [ i ] + lr [ i ]) /2;
11 i n t ondlmix = ( t l [i ] − l l [ i ] ) /2;
12 tl [ i ] = ( tl [ i ] + ll [ i ]) /2;
13
14 i f ( abs ( ondlmix ) < e p s i l o n ) { o n d l h a u t = 0 ; } ;
15 i f ( abs ( o n d l b a s ) < e p s i l o n ) { o n d l b a s = 0 ; } ;
16 i f ( abs ( o n d l h a u t ) < e p s i l o n ) { ondlmix = 0 ; } ;
17
18 l l [ i ] = t l [ i ] − ondlmix ;
19 t l [ i ] = t l [ i ] + ondlmix ;
20
21 t r [ i ] = t l [ i ] − ondlhaut ;
22 t l [ i ] = t l [ i ] + ondlhaut ;
23
24 l r [ i ] = l l [ i ] − ondlbas ;
25 l l [ i ] = l l [ i ] + ondlbas ;
26 }
11.8 Images utilisées pour les performances de haar.cl

11.8.1
Figure 37 – Image 1 : 3 mégapixels
62
63
64

Ondes Cours

Transféré par

Droits d'auteur :

Formats disponibles

Ondes Cours

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Ondes Cours

Transféré par

Droits d'auteur :

Formats disponibles

TIPE: Introduction à la théorie des ondelettes

Xavier Friederich et Gaétan Bahl

Table des matières

4 La théorie de l’analyse multirésolution, un outil pour la construction de bases d’onde-

5 Algorithme de décomposition en ondelettes de Stéphane Mallat (1989) 17

6 Application à la compression des données 24

7 Utilisation pratique de la transformation par ondelettes discrète 24

8.6.3 La fonction execute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

10 Bibliographie, Liens et Remerciements 45

Table des figures

35 Temps d’exécution de haar.cl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

1 L’analyse de Fourier, outil certes efficace mais insuffisant

1.1 Le cas des signaux périodiques : l’utilisation des séries de Fourier

en notation exponentielle ou bien

f est somme de sa série de Fourier, ce qui se réécrit de la façon suivante :

Figure 1 – Illustration du théorème de Fourier pour les signaux périodiques

1.2 L’utilisation de la transformée de Fourier

1.2.1 Définition de la transformation de Fourier

1.2.2 Propriétés de la transformation de Fourier

— On peut montrer que F conserve la parité.

1.2.3 Transformée inverse

1.2.4 Ce qu’apporte la transformée de Fourier d’un signal

Figure 2 – Spectre de Fourier en fréquence d’un signal périodique

1.2.5 Exemples de transformée de Fourier

Si on note Π la fonction porte définie par ∀t ∈ − 21 , 21 , Π(t) = 1 et ∀t ∈ R\ − 21 , 21 , Π(t) = 0, on obtient

Figure 3 – Allure d’une gaussienne

Figure 4 – Spectre d’amplitude de la fonction Π

1.2.6 Application de la transformation de Fourier

1.3 Transformée de Fourier Discrète ou TFD et limites

En notant W l’inverse de la racine N -ième de l’unité 4 , il vient bien sûr :

1.3.2 Des applications de la TFD

1. L’analyse spectrale des signaux.

3. La multiplication des grands nombres.

1.3.3 Des limites à la Transformée de Fourier Discrète

2.1 Définition 1 : Ondelette

2.2 Exemples d’ondelettes mères :

2.2.2 Ondelette ”chapeau mexicain” :

Figure 5 – Ondelette de Haar

Figure 6 – Ondelette ”chapeau mexicain”

2.2.3 Ondelette de Morlet :

Figure 7 – Ondelette de Morlet

3.1 Transformation en ondelette continue

Définition : produit scalaire

Ex : dilatation. L’ondelette verte a été dilatée à partir de l’ondelette rouge (ondelette-mère). On a b = 0

Figure 8 – Dilatation d’ondelette

Ex : translation. L’ondelette verte a été translatée à partir de l’ondelette rouge (ondelette-mère). On a

Figure 9 – Translation d’ondelette

3.2 Transformation en ondelettes discrète.

Figure 10 – Le graphe de la fonction W(a; b)(Π)

3.3 Comparaison avec la transformation de Fourier

Figure 11 – Comparaison des méthodes de compression

4 La théorie de l’analyse multirésolution, un outil pour la construc-

4.1 Définition d’une analyse multirésolution.

— ∀(k, l) ∈ Z2 , f ∈ Vk ⇔ f (· − 2k l) ∈ Vk (propriété d’invariance par translation)

4.2 Intéret d’une analyse multirésolution

5 Algorithme de décomposition en ondelettes de Stéphane Mallat

5.2 Démonstration dans un cas simple : le cas des ondelettes de Haar.

5.2.1 Introduction et définition des notations

Soit la fonction définie par