Les ondelettes de Haar simples .pdf



Nom original: Les ondelettes de Haar simples.pdf

Ce document au format PDF 1.4 a été généré par TeX / pdfTeX-1.11a, et a été envoyé sur fichier-pdf.fr le 18/02/2017 à 19:37, depuis l'adresse IP 41.96.x.x. La présente page de téléchargement du fichier a été vue 522 fois.
Taille du document: 231 Ko (18 pages).
Confidentialité: fichier public


Aperçu du document


Master1 MCO
S. M. Bahri
S2 - Février 2017
Outils d’Analyse Fonctionnelle 2

Les ondelettes de Haar Simples
1

Approximation simple

La première étape de l’analyse par ondelettes d’un signal ou d’un phénomène
physique consiste à la représentation du signal considéré par une fonction mathématique (voir …gure1).

(1a)
Figure1 (a) Signal; (b) Echantillon; (c) Approximation.
Puique les mesures pratiques de phénomènes réels nécessitent du temps et des
ressources, elles ne fournissent pas toutes les valeurs, mais seulement une suite
…nie de valeurs, appelé échantillon de la fonction représentant le phénomène
considéré, comme dans la …gurel.l(b). Par conséquent, la première étape de
l’analyse d’un signal par ondelettes consiste à approximer la fonction à l’aide de
l’échantillon seul. L’une des méthodes les plus simples d’approximation utilise
un saut horizontale prolongé par chaque point de l’échantillon, comme dans la
…gurell (c). Les sauts qui en résultent forment une nouvelle fonction, notée ici
par fe et appellée fonction simple ou fonction en escalier, qui approxime
la fonction f échantillonnée. Bien que des approximations plus précises que les
sauts simples existent, ils exigent des mathématiques plus sophistiqués, donc ce
chapitre se limite à quelques sauts simples. Une notation précise sera utile pour
indiquer l’emplacement de ces sauts.
L’analyse de la fonction d’approximation fe en termes d’ondelettes nécessite
un étiquetage précis de chaque saut, au moyen de translations et dilatations de
la fonction échelon unité de base, notée '[0;1[ et présentées dans la …gure1.2 (a).
La fonction échelon unité '[0;1[ prend les valeurs
'[0;1[ (x) =

1 si 0 x < 1;
0 sinon.
1

(2)

Pour un saut à la même unité de hauteur 1, mais avec une largeur plus étroite
w, la …gure 1.2 (b) montre la fonction en escalier '[0;w[ , dé…nie par
1 si 0 x < w;
0 sinon.

'[0;w[ (x) =

(3)

De même, pour un saut à la même hauteur unité 1, mais à partir d’une position
di¤érente x = u au lieu de 0, la …gure 1.2 (c) montre la fonction saut '[u;w[
dé…nie par
1 si u x < w;
'[u;w[ (x) =
(4)
0 sinon.

y 1.0
0.8
0.6
0.4
0.2
-0.50
-0.250.000.250.500.751.001.251.50

x

(a)

Figure2 (a) '[0;1[ ; (b) '[0;w[ ; (c) '[u;w[ ; (d) c '[u;w[ .
Finalement, pour construire une fonction saut à une hauteur c, débutant de
la position u à la position w, la Figure2(d) montre c '[u;w[ un multiple scalaire
par c de la fonction '[u;w[ ; ainsi
c '[u;w[ (x) =

c si u x < w;
:
0 sinon.
2

(5)

Donc le point échantillon Mj = (xj ; yj ) tel que yj = f (xj ) ; correspont à la
fonction saut
yj '[xj ;xj+1 [ ;
(6)
qui approche f à la hauteur yj sur l’intervalle [xj ;xj+1 [ à partir de xj (inclu)
jusqu’à xj+1 (non inclu). La somme de toutes les fonctions saut corréspondantes
à tous les points de l’échantillon (Fig1(b)) donne l’expression de la fonction saut
simple fe (Fig1(c)) représentant une approximation de f (Fig1(a)) :
fe = y0 '[x0 ;x1 [ + y1 '[x1 ;x2 [ +
=

n
X1

+ yn

1

'[xn

1 ;xn [

(7)

yj '[xj ;xj+1 [ :

j=0

Remark 1 Pour faciliter la comparaison entre di¤ érents signaux, et pour permettre l’utilisation d’un algorithme de calcul commun, des ondelettes simples
sont à l’intervalle 0 x < 1, tel que une unité correspond à la longueur entière
du signal. Donc, x = 12 représente la moitié du signal, et x = 87 représente la
localisation du sept huitième du signal.
Example 2 Le tableau (8) liste deux points échantillons, (x0 ; y0 ) = (0; 9) et
(x1 ; y1 ) = 21 ; 1 d’une fonction quelconque.
j
xj
yj

0
0
9

1
1
2

(8)

1

L’échantillon dans le tableau (8) corréspond à la fonction saut simple fe approximation de la fonction f donnée par la Figure3(a) et spéci…ée par la
formule
1
X
fe =
yj '[xj ;xj+1 [ = 9 '[0; 1 [ + 1 '[ 1 ;1[ :
(9)
2

2

j=0

Le premier saut, 9 '[0; 1 [ ; a la hauteur 9 sur l’intervalle 0; 21 :
2

3

Le deuxième saut 1 '[ 1 ;1[ admet la hauteur 1 sur l’intervalle
2

1
2; 1

:

Figure3 Exemples de fonctions saut simples
Example 3 L’échantillon dans le tableau suivant
j
xj
yj

0
0
5

1

2

3

1
4

1
2

3
4

1

2

8

(Tableau2)

corréspond à la fonction saut simple ge approximation de la fonction g donnée
par la Figure3(b) et spéci…ée par la formule
ge =

3
X

yj '[xj ;xj+1 [ = 5 '[0; 1 [ + 1 '[ 1 ; 1 [ + 2 '[ 1 ; 3 [ + 8 '[ 3 ;1[ :
4
4 2
2 4
4

j=0

4

(10)

Example 4 L’échantillon dans le tableau suivant
j
xj
yj

0
0
3

1

2

3

4

5

6

7

1
8

1
4

3
8

1
2

5
8

3
4

7
8

1

0

4

8

6

9

9

(Tableau3)

corréspond à la fonction saut simple e
h approximation de la fonction h donnée
par la Figure3(c) et spéci…ée par la formule
e
h

=

7
X

yj '[xj ;xj+1 [ = 3 '[0; 1 [ + 1 '[ 1 ; 1 [ + 0 '[ 1 ; 3 [ + 4 '[ 3 ; 1 [(11)
8
8 4
4 8
8 2

j=0

+8 '[ 1 ; 5 [ + 6 '[ 5 ; 3 [ + 9 '[ 3 ; 7 [ + 9 '[ 7 ;1[ :
2 8
8 4
4 8
8

Exercise 5 Ecrire la formule de la fonction saut pe de la fonction p tracée dans
la Figure3(d) et corréspondante au tableau suivant
j
xj
yj

0
0
8

1

2

3

4

5

6

7

1
8

1
4

3
8

1
2

5
8

3
4

7
8

6

7

3

1

1

2

4

:

Exercise 6 Tracer le graphe et écrire la formule de la fonction saut qe corréspondante à l’échantillon du tableau suivant
j
xj
yj

0
0
3

1

2

3

4

5

6

7

1
8

1
4

3
8

1
2

5
8

3
4

7
8

1

9

7

7

9

5

7

:

Exercise 7 Véri…er que pour tout nombre x,
'[0;w[ (x) = '[0;1[ (x=w)
'[u;w[ (x) = '[0;1[

x u
w u

:

Exercise 8 Dé…nissons la fonction "ondelette" de Haar
[0;1[

:= '[0; 1 [
2

[0;1[

par

'[ 1 ;1[ :
2

Véri…er que pour tout nombre x,
8
< 1

2
2.1

si 0 x < 12 ;
1 si 21 x < 1;
[0;1[ (x) =
:
0
ailleurs.

Approximation avec ondelettes simples
La Transformée en ondelettes de Haar de base

La transformation de Haar de base exprime la fonction d’approximation fe avec
des ondelettes par le remplacement d’une paire adjacente de sauts par un saut
5

plus large et une ondelette. Le plus large saut mesure la moyenne de la paire
initiale de sauts, tandis que l’ondelette, formée par deux sauts alternées, mesure
la di¤érence de la paire initiale des sauts.
Par exemple, la somme de deux étapes adjacentes avec la largeur 1=2 produit
la fonction saut unité de base '[0;1[ , comme dans la Figure4 : en e¤et,
'[0;1[ = '[0; 1 [ + '[ 1 ;1[ :
2
2

(12)

y 1.0

y 1.0

y 1.0

0.8

0.8

0.8

0.6

0.6

0.6

0.4

0.4

0.4

0.2

0.2

0.2

-0.50
-0.250.000.250.500.751.001.251.50

-0.50
-0.250.000.250.500.751.001.251.50

-0.50
-0.250.000.250.500.751.001.251.50

x

x

x

'[0; 1 [

'[0;1[

'[ 1 ;1[

2

2

+

=
Figure4.

De même, la di¤érence de ces deux sauts étroits donne l’ondelette de base
correspondante, notée [0;1[ et dé…nie par
[0;1[

= '[0; 1 [ + '[ 1 ;1[ :
2

(13)

2

L’ ondelette [0;1[ ainsi dé…nie est une fonction saut simple, avec un premièr
saut de hauteur 1 suivie d’un deuxième saut de hauteur 1. Ainsi, à partir de
son premièr saut à son second saut, les valeurs de l’ondelette [0;1[ subissent un
saut de taille 2, comme indiqué sur la Figure5.

6

y

y

1.0

0.5

0.5

-0.50
-0.25

y

1.0

-0.50
-0.25

0.250.500.751.001.251.50

x

1.0
0.5

0.250.500.751.001.251.50

-0.50
-0.25

x

-0.5

-0.5

-0.5

-1.0

-1.0

-1.0

'[0; 1 [

[0;1[

2

+
Figure5.

L’addition et la soustraction des deux équations (12) et (13),
(
'[0;1[ = '[0; 1 [ + '[ 1 ;1[ ;
2
2
'[ 1 ;1[ ;
[0;1[ = '[0; 1 [
2

(14)

2

produit la relation inverse, qui exprime les plus étroits sauts '[0; 1 [ et '[ 1 ;1[ en
2
2
termes du saut unité de base '[0;1[ et l’ondelette [0;1[ , comme le montre la
Figure6 :
8
< 1 '[0;1[ + [0;1[ = ' 1 ;
2
[0; 2 [
(15)
: 1 '[0;1[
;
=
'
1
[0;1[
;1
2
[2 [

7

x

'[ 1 ;1[

2

=

0.250.500.751.001.251.50

y

1.0

y

0.5

-0.50
-0.25

y

1.0

0.5

0.250.500.751.001.251.50

-0.50
-0.25

x

-0.5

0.5

0.250.500.751.001.251.50

y

y

1.0

0.5

0.250.500.751.001.251.50

-0.50
-0.25

x

-0.5

'[ 1 ;1[

1.0

0.5

0.250.500.751.001.251.50

x

-0.5

-0.50
-0.25

Figure6.
Pour deux sauts adjacents de hauteurs respectives y0 et y1 , les équations
(15) impliquent la représentation suivante avec un large saut et une ondelette :
= y0 '[0; 1 [ + y1 '[ 1 ;1[
2
2
1
1
= y0
'[0;1[ + [0;1[ + y1
'[0;1[
2
2
y 0 + y1
y0 y1
=
'[0;1[ +
[0;1[ :
2
2

:

(16)
[0;1[

Signi…cation de la transformée en ondelettes de Haar

Deux valeurs échantillons y0 et y1 mesurent la valeur (amplitude, hauteur) de la
fonction fe en x0 et en x1 . En contrast, les résultats de la transformée de base
ont la signi…cation suivante.
Le nombre

y0 +y1
2

mesure la moyenne de la fonction fe.
8

x

1
2

=

2.2

0.250.500.751.001.251.50

-0.5
1
2 '[0;1[

2

fe

[0;1[

+

0.5

-0.50
-0.25

x

1
2

=

1.0

0.250.500.751.001.251.50

-0.5
1
2 '[0;1[

2

y

-0.50
-0.25

x

-0.5

'[0; 1 [

1.0

[0;1[

Le nombre

y0 y 1
2

mesure le changement dans la fonction fe.

La transformée de base préserve toute l’information dans l’échantillon, en
e¤et, la transformation décrit di¤érement l’échantillon à partir des valeurs de
l’échantillon, aussi il reproduit exactement l’échantillon :
y0 + y 1
y 0 y1
'[0;1[ +
y0 '[0; 1 [ + y1 '[ 1 ;1[ = fe =
2
2
2
2

[0;1[ :

(17)

Example 9 Le tableau (8) liste deux points échantillons, (x0 ; y0 ) = (0; 9) et
(x1 ; y1 ) = 21 ; 1 d’une fonction vue dans l’exemple2. Pour deux tels sauts
adjacents à des hauteurs y0 = 9 et y1 = 1 (voir Figure7.),
9'[0; 1 [ + 1'[ 1 ;1[ =
2

y

2

9+1
9 1
'[0;1[ +
2
2

y

8

[0;1[

= 5'[0;1[ + 4

[0;1[ :

(18)

y

8

8

6

6

6

4

4

4

2

2

2

0

0

-2

0.2 0.4 0.6 0.8 1.0 1.2

-2

x

0
0.2 0.4 0.6 0.8 1.0 1.2

-2

x

-4

-4

-4

-6

-6

-6

-8

-8

=

+

-8

Figure7. Exemple d’une Transformée en Ondelettes de Haar
Le terme 5'[0;1[ signi…e que la totalité de l’échantillon a une valeur moyenne
(taille moyenne) égal à 5.
Le terme 4 [0;1[ signi…e que de sa valeur première à sa seconde valeur,
l’échantillon change comme 4 ondelettes de base: Il subit un saut de taille
4 ( 2) = 8, e¢ cace de 9 à 1.

2.3

Translations et Dilatations de la transformée de Haar

Pour appliquer la transformée de base en commençant par une position a différente de 0, et sur un intervalle s’étendant à b au lieu de 1, dé…nissons l’ondelette
translatée et dilatée [a;b[ par le point médian c := (a + b)=2 :
[a;b[

(x) =

1 si a
1 si c

x < c;
x < b:

(19)

Encore une fois, la somme et la di¤érence des deux plus étroits sauts donne un
plus grand saut et une ondelette :
'[a;b[ (x) = '[a;c[ (x) + '[c;b[ (x) ;
'[c;b[ (x) :
[a;b[ (x) = '[a;c[ (x)
9

(20)

0.2 0.4 0.6 0.8 1.0 1.2

x

En outre, l’ajout et la soustraction des deux équations obtenues donnent la
relation inverse, exprimant les deux sauts en termes plus restreints du plus
large saut et de l’ondelette :
8
< 1 '[a;b[ (x) + [a;b[ (x) = '[a;c[ (x) ;
2
(21)
: 1 '[a;b[ (x)
[a;b[ (x) = '[c;b[ (x) :
2
La transformée de Haar translatée et dilatée que venons de décrire s’applique
à toutes les paires consécutives de valeurs, séparées par des points virgules pour
plus de commodité, dans un échantillon avec 2n valeurs :
x0 ; x1 ; x2 ; x3 ; : : : ; x2k ; x2k+1 ; : : : ; x2(n

2) ; x2n 1 :

(22)

Example 10 Le tableauTableau2 liste quatre points d’échantillonnage correspondants à la fonction saut d’approximation (voir Example3),
fe = 5 '[0; 1 [ + 1 '[ 1 ; 1 [ + 2 '[ 1 ; 3 [ + 8 '[ 3 ;1[ :
4
4 2
2 4
4

(23)

La transformée de Haar appliquée à la première paire de sauts donne
5 '[0; 1 [ + 1 '[ 1 ; 1 [ =
4
4 2

5+1
5 1
'[0; 1 [ +
[0; 12 [ :
2
2
2

(24)

De la même façon, après un décalage de deux points d’échantillons vers la droite,
la transformée de Haar appliquée à la seconde paire donne
2 '[ 1 ; 3 [ + 8 '[ 3 ;1[ =
2 4
4

2+8
2 8
'[ 1 ;1[ +
[ 21 ;1[ :
2
2
2

(25)

Donc,
ge = 5 '[0; 1 [ + 1 '[ 1 ; 1 [ + 2 '[ 1 ; 3 [ + 8 '[ 3 ;1[
4
4 2
2 4
4
= 3'[0; 1 [ + 2 [0; 1 [ + 5'[ 1 ;1[ + ( 3) [ 1 ;1[ :
2

Les coe¢ cients 3; 5; 2, et

2

2

(26)

2

3, ont la signi…cation suivante :

3'[0; 1 [ indique que ge a une valeur moyenne de 3 au cours de la première
2

moitié de l’intervalle, de 0 à

1
2

5'[ 1 ;1[ indique que ge a une valeur moyenne de 5 au cours de la seconde
2

moitié de l’intervalle, de

1
2

à1

2 [0; 1 [ indique que ge a subit un saut de deux fois la taille de celui de [0; 1 [
2
2
qui saute de 1 à 1, pour un total de 2 ( 2) = 4 au cours de la première
moitié de l’intervalle, en e¤ et de 5 à 1.
( 3) [ 1 ;1[ indique que ge a subit un saut de moins trois fois la taille de
2
celui de [ 1 ;1[ qui saute de 1 à 1, pour un total de ( 3) ( 2) = 6 au
2
cours de la seconde moitié de l’intervalle, en e¤ et de 2 à 8.
10

Example 11 Le tableauTableau3 liste huit points d’échantillonnage de la fonction h de l’exemple4.Appliquée à des paires consécutives de valeurs d’échantillons
(x0 ; x1 ) ; (x2 ; x3 ) ; : : : ; (x2k ; x2k+1 ) ; : : : ; (x2 ; x6 ), la transformée en ondelettes de
Haar donne
3 1
0+4
0 4
3+1
e
'[0; 1 [ +
h =
[0; 14 [ + 2 '[ 14 ; 21 [ + 2 [ 41 ; 12 [
4
2
2
8+6
8 6
9+9
9 9
+
'[ 1 ; 3 [ +
[ 12 ; 34 [ + 2 '[ 34 ;1[ + 2 [ 43 ;1[:
2 4
2
2
Remark 12 Les lettres majuscules des mots au début des phrases techniques indiquent une signi…cation technique spéci…que. Par exemple, l’expression « Transformation en Ondelettes de Haar" désigne la transformée spéci…que avec les
ondelettes spéci…ques décrites dans ce chapitre.
Remark 13 Comme la transformée en ondelettes de Haar n’utilise pas l’abscissela première coordonnée xi du point de données (xi ; yi )- les données pour la
transformée en ondelettes de Haar peut lister les ordonnées (valeurs) yi sans
les abscisses. Par exemple, les données (y0 ; y1 ) = (2; 8) peuvent remplacer tout
le tableau(27).
j
xj
yj

0
0
2

1
1
2

(27)

8

Exercise 14 Calculer la transformée de Haar pour la donnée (y0 ; y1 ) = (2; 8).
Exercise 15 Calculer la transformée de Haar pour la donnée (y0 ; y1 ) = (7; 3).
Exercise 16 Calculer la transformée de Haar pour la première paire et pour la
dernière paire dans les données (y0 ; y1 ; y3 ; y4 ) = (2; 4; 8; 6).
Exercise 17 Calculer la transformée de Haar pour la première paire et pour la
dernière paire dans les données (y0 ; y1 ; y3 ; y4 ) = (5; 7; 3; 1).
Exercise 18 Calculer la transformée en ondelettes de Haar pour chaque paire
(y2k ; y2k ) dans le vecteur !
y = (8; 6; 7; 3; 1; 1; 2; 4).
Exercise 19 Calculer la transformée en ondelettes de Haar pour chaque paire
(y2k ; y2k ) dans le vecteur !
y = (3; I; 9; 7; 7; 9; 5; 7).
Exercise 20 Pour chaque matrice avec quatre entrées !
y = (y ; y ; y ; y ), con0

1

2

3

sidérons les moyennes de la première paire et de la dernière paire d’entrées
(y0 + y1 ) =2;
(y3 + y4 ) =2:

Véri…er algébriquement que la moyenne des deux moyennes produit la moyenne
de toutes les entrées dans !
y
[(y0 + y1 ) =2] + [(y3 + y4 ) =2]
y 0 + y 1 + y3 + y 4
=
:
2
2
11

Exercise 21 Pour les tableaux avec huit entrées y = (y0 ; y1 ; y2 ; y3 ; y4 ; y5 ; y6 ; y7 ),
considérez les moyennes
(y0 + y1 ) =2;
(y2 + y3 + y4 + y5 + y6 + y7 )=6:
Cherchez à savoir si
[(y0 + y1 ) =2] + [(y2 + y3 + y4 + y5 + y6 + y7 )=6]
2
? y 0 + y 1 + y2 + y 3 + y 4 + y5 + y 6 + y7
:
=
8
Exercise 22 Pour tout tableau y = (y0 ; y1 ; y2 ; y3 ; y4 ; y5 ; y6 ; y7 ), véri…er que
[(y0 +y1 )=2]+[(y2 +y3 )=2]
2

=

6 +y7 )=2]
+ [(y4 +y5 )=2]+[(y
2
2
y0 + y1 + y 2 + y3 + y4 + y 5 + y6 + y7
:
8

Donc, la moyenne égale à la moyenne des moyennes des moyennes.

3

Transformée en ondelettes de Haar rapide

Pour analyser un signal ou une fonction en termes d’ondelettes, la transformée
en ondelettes de Haar rapide commence par un vecteur initial de 2n entrées et
ensuite procede par n itérations de la transformée de Haar simple vue dans la
section précédente.
Pour chaque indice l 2 f1; : : : ; ng, avant l’itération numéro l, le vecteur
(n [l 1])
consiste en 2n (l 1) coe¢ cients de 2n (l 1) fonctions sauts 'k
dé…nies
çi dessus. Aprés l’itération numéro l, le vecteur consiste en la moitié ...., 2n l ;
(n l)
coe¢ cients de 2n l fonctions sauts 'k
et 2n l ; coe¢ cients de 2n l ondelettes
(n l)
.
k
De…nition 23 Pour tout entier positif n et tout indice l 2 f1; : : : ; ng, on dé…nit
(n l)
(n l)
les fonctions sauts 'k
et les ondelettes k
par
(n l)

'k

(x)

:

= '[0;1[ 2n

=

(n l)
k

(x)

:

= [0;1[
8
< 1
=
1
:
0

l

x

1 si k2l n
0 ailleurs;
2n

l

x

si k2l n
si k +
ailleurs:

12

k2l

n

x

(k + 1) 2l

n

;

n

x
1
2

k2l

1
2

k+
2l

n

x

2l n ;
(k + 1) 2l

n

;

3.1

Initialisation

Pour ondelettes de Haar, l’initialisation consiste seulement en l’établissement
d’un vecteur unidimensionnel a(n) , appelé aussi suite …nie de valeurs échantillons, de la forme
a(n)

(n)

=

(n)

(n)

(n)

a0 ; a1 ; : : : ; aj ; : : : ; a2n
=!
s = (y ; y ; : : : ; y ; : : : ; y

:

0

1

(n)
2 ; a2 n 1

2n 2 ; y 2 n 1 ) :

j

Ce vecteur correspond à la fonction saut
fe(n) =

3.2

n
2X
1

(n)

(n)

aj 'j :

j=0

Transformée en ondelettes de Haar rapide ordonnée

La section précédente a montrée comment un premier balayage de la transformée
de base s’applique à toutes les paires consécutives (y2k ; y2k+1 ) de la matrice
initiale de valeurs d’échantillons a(n) = !
s.
En général, le l eme balayage de la transformée de base commence par un
vecteur de 2n (l 1) valeurs
a(n

[l 1])

(n [l 1])

= a0

(n [l 1])

; : : : ; a2n

(l

1)

;

1

(n [l 1])

ensuite, on applique la transformation de base à chaque paire a2k
ce qui donne deux nouveaux coe¢ cients d’ondelettes
(n l)

ak

(n l)
ck

:=

a2k

(n

[l

(n

[l

a2k

:=

1])

(n

[l

+a2k+1
2
1])
(n [l
a2k+1
2

1])

;
1])

:

Ces 2n l paires de nouveaux coe¢ cients représentent le résultat du l
balayage, un résultat qui peut aussi être rassemblé dans deux vecteurs :
a(n

l)

c(n

l)

(n l)

:= a0
:=

(n l)

; a1

(n l)

; : : : ; ak

(n [l 1])

; a2k+1

(n l)

; : : : ; a2n

l 1
(n l) (n l)
(n l)
(n l)
c0
; c1
; : : : ; ck
; : : : ; c2n l 1

eme

;
:

Les matrices liées au l-ème balayage ont la signi…cation suivante.
a(n [l 1]) : La matrice de départ,
a(n

[l 1])

(n [l 1])

:= a0

(n [l 1])

; : : : ; a2(n

[l

1])

1

(n [l 1])
liste des valeurs de ak
d’une fonction saut simple fe(n [l 1]) qui approche
n [l 1]
la fonction initiale f avec 2
sauts de largeurs plus étroites 2(l 1) n :
2n

fe(n

[l 1])

=

(l

1)

X

1

(n [l 1])

aj

j=0

13

(n [l 1])

'j

:

,

a(n

l)

: La première matrice produite par le l-ième balayage,
a(n

l)

(n l)

:= a0

(n l)

; : : : ; a2(n

l)

1

;

(n l)
liste des valeurs de ak
d’une fonction saut simple fe(n l) qui approche la
n l
fonction initiale f avec 2
sauts de largeurs plus étroites 2l n :

c(n

l)

fe(n

l)

=

l
2nX
1

(n l)

aj

(n l)

'j

:

j=0

: La seconde matrice produite par le l-ième balayage,
c(n

l)

(n l)

liste les coe¢ cients ck
étroite 2l n :

(n l)

:= c0

(n l)

; : : : ; c2(n

l)

d’ondelettes simples fj

(n l)

f

=

l
2nX
1

(n l)

cj

1

;

(n l)

aussi de largeur plus

(n l)
:
j

j=0

(n l)

Les ondelettes données par la seconde nouvelle matrice, ck
, représentent la
di¤érence entre les sauts …ns de l’approximation initiale fe(n [l 1]) et les sauts
larges de fe(n l) . Donc chaque balayage des transformées de base exprime une
nouvelle approximation plus …ne comme la somme d’une nouvelle approximation
plus large et une nouvelle basse frequence qui forme un ensemble d’ondelettes.
Néanmoins, comme les sauts des transformées de Haar n’altere pas la fonction
échantillon mais l’exprime seulement avec une ondelette di¤érente, il s’en suit
que l’approximation initiale fe(n [l 1]) reste égale à la somme de deux nouvelles

approximations, fe(n

(n l)

l)

et f

fe(n

:

[l 1])

= fe(n

(n l)
l)

+f

:

Example 24 Le vecteur y = (y0 ; y1 ; y2 ; y3 ) = (5; 1; 2; 8) reproduit les données
des exemples3 et 10. Pour illustrer un usage commun [7], le présent exemple
va stocker le résultat …nal -la transformée en ondelettes de Haar- des données
ordonnées par fréquences croissantes: des plus basses fréquences produites en
dernier mais stockées dans la première partie (à gauche) du vecteur, vers les
plus hautes fréquences produites en premièr mais stockées dans la dernière partie
(à droite) du vecteur.
Initialisation.
Le vecteur
a(2) = y = (5; 1; 2; 8)
contient 22 = 4 valeurs de l’échantillon.
1ier Balayage.
14

a(1) = (

5+1 2+8
;
) = (3; 5) ;
2
2

a(1) est une approximation grossière de l’échantillon initial a(2) et signi…e
que la première moitié du signal, (5; 1); a une valeur moyenne de 3, et que la
seconde moitié du signal, (2; 8); a une valeur moyenne de 5.
c(1) = (

5
2

1 2
;

8
2

) = (2; 3) ;

c(1) signi…e que pendant la première moitié du signal, les valeurs changent
comme 2 fois le saut d’une ondelettes de 3, et que la seconde moitié du signal, (2; 8) a une valeur moyenne de 5.

3.3

Transformée en ondelettes de Haar rapide sur place

En considérant que la présentation dans la section précédente établit commodément toutes les étapes de la transformée en ondelettes rapide Haar, elle nécessite
des tableaux supplémentaires à chaque balayage, et elle suppose que l’ensemble
de l’échantillon est connu au début de l’algorithme.
En revanche, certaines applications nécessitent un traitement en temps réel
comme le produit du signal, ce qui exclut toute connaissance de l’ensemble de
l’échantillon, et certaines applications impliquent des tableaux si grands qu’elles
ne permettent pas su¢ samment d’espace pour les tableaux supplémentaires à
chaque balayage. Les deux problèmes viennent d’être décrits, le manque de
temps ou d’espace, ont une solution commune dans la transformée en ondelettes
de Haar rapide sur place présentée ici, qui di¤ère de l’algorithme précédent que
par son schéma d’indexation.
3.3.1

Balayage de base en place
(n [l 1])

(n [l 1])

Pour chaque paire a2k
; a2k+1
, au lieu de placer ses résultats dans
deux tableaux supplémentaires, le l-ièmè balayage de la transformée en place
(n [l 1]) (n [l 1])
par les nouvelles entrées
ne fait que remplacer la paire a2k
; a2k+1
(n l)

ak

(n l)

; ck

:
(n [l 1])

Initialisation Considérons la paire a2k
Calcul

(n [l 1])

; a2k+1

E¤ectuer la transformée de base
(n l)

ak

(n l)
ck

:=
:=

a2k

(n

[l

(n

[l

a2k

15

1])

(n

[l

+a2k+1
2
1])
(n [l
a2k+1
2

1])

;
1])

:

.

(n [l 1])

Replacement Remplacez la paire initiale a2k
(n l) (n l)
ak
; ck

transformée

(n [l 1])

; a2k+1

par la paire

:

Example 25 Pour le tableau initial y (1) = y = (9; 1), la transformée en ondelettes de Haar rapide sur place donne
y (1

1)

=

9+1 9 1
;
2
2

= (5; 4) :

Example 26 Pour le vecteur initial y (2) = y = (5; 1; 2; 8), la transformée en
ondelettes de Haar rapide sur place donne
y (2

1)

=

5+1 5 1 2+8 2 8
;
;
;
2
2
2
2

= (3; 2; 5; 3) :

Example 27 Pour le tableau initial y (3) = y = (3; 1; 0; 4; 8; 6; 9; 9), la transformée en ondelettes de HAAR rapide sur place donne
y (3

1)

=
=

3+1 3 1 0+4 0 4 8+6 8 6 9+9 9 9
;
;
;
;
;
;
;
2
2
2
2
2
2
2
2
(2; 1; 2; 2; 7; 1; 9; 0) :

Pour plus de commodité, les entrées en gras montrent le vecteur d’initiation
y (3 1) pour le balayage suivant, décrit dans le prochain paragraphe.
3.3.2

Transformée en ondelettes de Haar rapide sur place

Le balayage de base en place expliqué dans la partie précédente s’etend à un
algorithme complet ...
Les premieres étapes se produisent comme suit :
Initialisation.
y (n) = y = (y0 ; y1 ; y2 ; y3 ; : : : ; y2k ; y2k+1 ; : : : ; y2n

2 ; y2n 1 ):

Premier balayage.
y (n

1)

y0 + y 1 y0 y 1 y2 + y 3 y2 y 3
y2k + y2k+1 y2k y2k+1
;
;
;
;:::;
;
;
2
2
2
2
2
2
y2 n 2 + y2 n 1 y2 n 2 y2 n 1
:::;
;
)
2
2
(n 1) (n 1)
(n 1)
(n 1)
(n 1) (n 1)
(n 1) (n 1)
= (a0
; c0
; a1
; c1
; : : : ; ak
; ck
; : : : a2n 1 1 ; c2n 1 1 ):
=

(

16

Second balayage. Dans le nouveau vecteur y (n 1) ; garder mais en sotant les
(n 1)
coe¢ cients d’ondelettes ck
, et calculer sur le vecteur a(n 1) en ses nouvelles
locations, maintenant occuper toutes les autres entrées dans y (n 1) :
(n 1)

y (n

2)

(n 1)

(n 1)

(n 1)

a1
+ a1
(n 1) a0
(n 1)
; c0
;
; c1
;
2
2
(n 1)
(n 1)
(n 1)
(n 1)
a2
+ a3
a3
(n 1) a2
(n 1)
; c2
;
; c3
;:::
2
2
(n 1)
(n 1)
(n 1)
(n 1)
a n 1 2 + a2n 1 1 (n 1) a2n 1 2 a2n 1 1 (n 1)
; c2 n 1 2 ;
; c2n 1 1 ):
:::; 2
2
2
(n 2) (n 1) (n 2) (n 1)
(n 2) (n 1) (n 2) (n 1)
= (a0
; c0
; c0
; c1
; a1
; c2
; c1
; c3
;
=

(

a0

(n 2)

a2

(n 1)

; c4

(n 2)

; c2

(n 1)

; c5

(n 2)

; : : : ; c2n

2

(n 1)
1 ; c2n 1 1 ):

En général, le l-ième balayage en place commence par un vecteur
y (n

[l 1])

(n [l 1])

=

(a0

(n 1)

; c0

(n 2)

; c0

(n 1)

; c1

(n 2)

; a1

(n 1)

; c2

(n 2)

; c1

(n 1)

; c3

;

(n 2) (n 1) (n 2) (n 1)
(n 2)
(n 1)
a2
; c4
; c2
; c5
; : : : ; c2n 2 1 ; c2n 1 1 );

qui contient le vecteur
a(n

[l 1])

(n [l 1])

= a0

(n [l 1])

(n [l 1])

; a1

(n

; : : : ; a2n

(l

[l 1])
1) 1

(n [l 1])

aux positions ak
= y2 l 1 k
; en d’autres termes, un multiple de 2l
dans y (n [l 1]) ; et où le l-ième balayage est remplacé par
(n

:=

a2j

[l

1])

(n

[l

+a2j+1
2
(n [l 1])
(n [l
a2j
a2j+1
(n l)
cj
:=
2
(n [l 1])
(n l)
y2l 1 2j
:= aj
;
(n [l 1])
(n l)
y2l 1 (2j+1) := cj
;
(n l)

aj

telle que le nouveau vecteur a(n
(n l)
(n l)
(n l)
car aj
= y2l 1 2j = y2l 2j :

l)

1])

=
1])

=

y
y

(n [l 1])
(n [l 1])
+y l 1
2l 1 2j
2
(2j+1)

(n [l 1])
2l 1 2j

2
(n
y l
2

[l 1])
1 (2j+1)

2

1

k

;
;

occupe les entrées multiples de 2l dans y (n

l)

;

Example 28 Pour le vecteur initial y (2) = y = (5; 1; 2; 8), la transformée en
ondelettes de Haar rapide en place procède comme suit :
Initialisation.
(2)

(2)

(2)

(2)

y (2) = y = (5; 1; 2; 8) = a0 ; a1 ; a2 ; a3

:

Premier balayage.
y (2

1)

(2 1)

(2 1)

; c0

(2 1)

; a1

(2 1)

; c1

=

a0

=

5+1 5 1 2+8 2 8
;
;
;
2
2
2
2
17

= (3; 2; 5; 3) :

Second balayage. Le second balayage opère sur les indices paires des entrées
y (2

2)

(2 2)

(2 1)

(2 2)

=

a0

=

3 5
3+5
; 2;
; 3
2
2

; c0

; c0

(2 1)

; c1

= (4; 2; 1; 3) :

Example 29 Le vecteur y = (3; 1; 0; 4; 8; 6; 9; 9) reproduit les données de l’exemple4.
Initialisation. y (3) = y = (3; 1; 0; 4; 8; 6; 9; 9):
Transformée en ondelettes de Haar rapide en place.
y (3

1)

=
=
=

y (3

2)

=
=
=

(3 1)

a0

(3 1)

; c0

(3 1)

; a1

(3 1)

; c1

(3 1)

; a2

(3 1)

; c2

(3 1)

; a3

(3 1)

; c3

3+1 3 1 0+4 0 4 8+6 8 6 9+9 9 9
;
;
;
;
;
;
;
2
2
2
2
2
2
2
2
(2; 1; 2; 2; 7; 1; 9; 0) :
(3 2)

a0

(3 1)

; c0

(3 2)

; c0

(3 1)

; c1

(3 2)

; a1

(3 1)

; c2

2 2
7+9
7 9
2+2
; 1;
; 2;
; 1;
;0
2
2
2
2
(2; 1; 0; 2; 3; 1; 1; 0) :

18

(3 2)

; c1

(3 1)

; c3


Aperçu du document Les ondelettes de Haar simples.pdf - page 1/18

 
Les ondelettes de Haar simples.pdf - page 3/18
Les ondelettes de Haar simples.pdf - page 4/18
Les ondelettes de Haar simples.pdf - page 5/18
Les ondelettes de Haar simples.pdf - page 6/18
 




Télécharger le fichier (PDF)


Télécharger
Formats alternatifs: ZIP Texte



Documents similaires


les ondelettes de haar simples
examen final an fourier ondelettes correction
examen final an fourier ondelettes
analyse de fourier et ondelettes
seance2
theme2 machines a vecteurs de support

Sur le même sujet..




🚀  Page générée en 0.012s