View
222
Download
0
Category
Preview:
Citation preview
7/29/2019 75514306 Ondelettes Hermes
1/158
Ondelettes pour le signal numrique
Fred Truchetet
Janvier 1998
7/29/2019 75514306 Ondelettes Hermes
2/158
2 Ondelettes pour le signal numrique
Avant-propos 9
Chapitre 1 Historique 11
Chapitre 2 Pourquoi les ondelettes ? 13
Chapitre 3 Quelles ondelettes ? 21
3.1 Inversion - Admissibilit 21
3.2 Quelles transformes en ondelettes ? 22
Chapitre 4 Bases orthonormes, analyse multirsolution 25
4.1 Axiomatique de base 25
Espaces dapproximation 25
Espaces des dtails 28
Analyse multirsolution et localisation spatio-
frquentielle 31
Gnralisation : paquets dondelettes 35
4.2 Algorithme rcursif 35
Algorithme danalyse 37
Algorithme de reconstruction 41
4.3 Construction numrique des fonctions de base 45
Chapitre 5 Proprits et construction 53
5.1 Proprits frquentielles de la fonction dchelle 54
Relations avec le filtre associ 54
Orthonormalit dans Fourier 55
5.2 Proprits frquentielles de londelette 58
5.3 Rsum des proprits 62
Chapitre 6 Exemples de bases dondelettes 65
6.1 Ondelettes de Haar 66
7/29/2019 75514306 Ondelettes Hermes
3/158
3
6.2 Ondelette de Littlewood-Paley 68
6.3 Bases splines 70
6.4 Ondelettes support compact (Daubechies) 76
Chapitre 7 Passage deux dimensions 87
7.1 Cas gnral 87
Matrice de changement dchelle 87
Axiomatique de base de lanalyse multirsolution 88
Sur-chantillonnage et sous-chantillonnage 89
Algorithme rcursif et proprits 92
7.2 Ondelettes sparables 100
7.3 Ondelettes quinconces 103
Exemples danalyse quinconce orthonorme 111
Chapitre 8 Bases biorthogonales 117
8.1 Introduction 117
8.2 Analyse biorthogonale 117
8.3 Proprits des bases et des filtres associs 120
8.4 Bases B-splines biorthogonales 122
Recherche de solutions avec des filtres RIF
symtriques 122
Cas des B-splines. 124
Solution avec des filtres rcursifs RII 125
Chapitre 9 Trames dondelettes 131
9.1 Bornes de la trame dondelettes 132
9.2 Reconstruction dans le cas dune trame dondelettes 132
Chapitre 10 Exemple de trame dondelettes 135
10.1 Dtection de contour multichelle 136
7/29/2019 75514306 Ondelettes Hermes
4/158
4 Ondelettes pour le signal numrique
Annexe A Fonctions B-splines et bases dondelettes 141
Bibliographie 151
Index 155
7/29/2019 75514306 Ondelettes Hermes
5/158
5
Remerciements
7/29/2019 75514306 Ondelettes Hermes
6/158
6 Ondelettes pour le signal numrique
Je voudrais remercier tous ceux, collgues, tudiants et proches qui mont aid
dans la mise au point de ce document, et particulirement lors de la ralisation des
illustrations et de la correction deserreurs. Que J.C. Devaux, A. Garcia, O. laligant et F.
Nicolier, trouvent ici lexpression de ma reconnaissance. Et merci surtout Franoise
et Marie-Elise pour leur patience et leur soutien pendant ces trop nombreuses journes
de vacances distraites de la vie familiale.
7/29/2019 75514306 Ondelettes Hermes
7/158
Table des matires
7/29/2019 75514306 Ondelettes Hermes
8/158
7/29/2019 75514306 Ondelettes Hermes
9/158
Avant-propos
De nombreux documents de synthse prsentant la transforme en ondelettes et ses
applications sont actuellement disponibles en librairie. Ils sont souvent de grande
qualit et devraient suffire un tudiant cherchant acqurir les notions ncessaires
lutilisation de cet outil de traitement du signal ou un chercheur qui souhaite
connatre ltat de lart dans le domaine avant de tenter dy apporter sa contribution
ventuelle. Alors pourquoi proposer un document de plus? La rponse tient en
deux points principaux. Tout dabord, bien que les Franais et les chercheurs
francophones se soient particulirement illustrs dans les dcouvertes qui ont conduit
ltablissement de cette thorie, il existe peu douvrages en langue franaise proposant
une prsentation des transformes en ondelettes discrtes. Ensuite, la plupart des
ouvrages disponibles sont soit des prsentations caractre grand public ne
permettant pas de rentrer dans les dtails techniques et donc peu utilisables pour
qui veut pratiquer la technique prsente, soit des thses caractre mathmatique
affirm mettant plus laccent sur la rigueur des raisonnements et la gnralit des
concepts utiliss que sur les rsultats pratiques rellement mis en uvre dans les
applications. Cest pourquoi nous avonsvoulu proposer un document crit dans lesprit
des Sciences de lIngnieur dans lequel la rigueur mathmatique nest pas totalement
absente mais nest pas, et de loin, la proccupation majeure. Au risque de faire bondir
les puristes, nous avons volontairement omis un certain nombre de cas particuliers
et quand la dmonstration rigoureuse dun rsultat nous a sembl soit trop lourde
soit trop complique conceptuellement, nous avons essay de donner une pseudo-
dmonstration suffisante pour convaincre et pour faire comprendre lorigine et la
porte du rsultat. Les lments fournis dans cette prsentation doivent permettreau lecteur daborder concrtement lanalyse par transforme en ondelettes des
signaux numriques monodimensionnels ou multidimensionnels. Nous avons voulu
souligner particulirement les aspects propres au traitement des images numriques
car cest incontestablement un domaine o la transforme en ondelettes est riche de
potentialits. Il est clair que lambition de ce cours se limite une introduction aux
transformes en ondelettes discrtes, il nutilise que les outils mathmatiques dont
dispose tout tudiant de second cycle universitaire ; il est donc destin aux tudiants
de licence, matrise, DEA ( titre dintroduction) et aux lves ingnieurs. Il ne faut
en aucun cas y chercher une prsentation exhaustive du sujet et la bibliographie reste
galement trs modeste. Le jeune chercheur souhaitant se spcialiser dans ce domaine
devra imprativement complter les lments fournis ici partir dune recherche
bibliographique plus approfondie.
7/29/2019 75514306 Ondelettes Hermes
10/158
10 Ondelettes pour le signal numrique
Enfin, il faut indiquer que nous nous sommes fortement appuys, voire adosss,
deux excellents ouvrages crits par deux des principaux crateurs de cette thorie,
Ingrid Daubechies [10]et Martin Vetterli [43]. Nous ne saurions trop recommander au
lecteur dsireux den savoir plus ou de chercher la rigueur mathmatique manquant ici
de se reporter ces bibles de la transforme en ondelettes.
Une des images favorites des traiteurs de signal 2D
7/29/2019 75514306 Ondelettes Hermes
11/158
Chapitre 1
Historique
Le traitement du signal a pour principal objet la description des signaux lis au monde
rel dans un but de traitement, didentification, de compression, de comprhension
ou de transmission. Dans ce contexte, les transformations linaires ont toujours jou
un trs grand rle, et parmi ces dernires, la plus clbre et la plus anciennement
tudie est la transformation de Fourier (1822). Cette transformation permet, comme
chacun sait, dexplorer la composition frquentielle du signal et par ses proprits
de lui appliquer facilement des oprateurs de filtrage. Lors de cette transformationle signal est dcompos sur un ensemble de signaux de base qui sont les cosinus
et sinus ou lexponentielle imaginaire, mais, trs tt dans lhistoire du traitement
du signal, il est apparu que la dcomposition obtenue ntait pas toujours la plus
satisfaisante et la premire transformation en ondelettes (le nom nest pas encore
utilis) est propose par Haar en 1910 ; il serait plus judicieux de parler alors
de palo-ondelette. La transforme en ondelettes est un outil qui dcoupe les
donnes, les fonctions ou les oprateurs en composantes frquentielles suivant une
rsolution adapte lchelle. Lesprcurseurs conscients de cette technique ont t des
mathmaticiens (Calderon 1964), des physiciens (Aslaken et Klauder en 1968, Paul
en 1985), et surtout des ingnieurs (ou des chercheurs en sciences pour lingnieur)
comme Esteban et Galand (1977), Smith et Barnwell (1986), Vetterli (1986), nous
pourrions parler dans leur cas de pr-ondelette. Mais le premier avoir utilis lamthode et le premier avoir propos le nom dondelettes fut Jean Morlet (1983).
Le problme trait par Morlet tait celui de lanalyse de donnes issues de sondages
sismiques effectus pour des recherches gologiques ; ces donnes faites de nombreux
transitoires sont particulirement adaptes une technique danalyse conservant la
notion de localisation de lvnement tout en fournissant une information sur son
contenu frquentiel ce qui est tout lintrt de ce type de transformation. Les rsultats
obtenus par Morlet et formaliss par le physicien Alex Grossmann ont rapidement
veill lattention de nombreux chercheurs et bientt des bases mathmatiques solides
ont tmises en place faisant apparatre la notionde base orthogonale (Y. Meyer1985),
danalyse multirsolution (S. Mallat 1989 [25], [26], [27]) et dondelettes support
compact (I. Daubechies 1988)[11]. Les ondelettes modernes taient nes. Les lecteurs
intresss par lhistoire des ondelettes trouveront des renseignements plus complets et
7/29/2019 75514306 Ondelettes Hermes
12/158
12 Ondelettes pour le signal numrique
des anecdotes passionnantes dans lexcellent ouvrage de B.B. Hubbard [19].
Les recherches tant thoriques quappliques se sont trs largement dveloppes
ces dernires annes au point que les ondelettes sont maintenant trs la mode
et quon a parfois voulu en faire loutil idal adapt tous les problmes. Cet
optimisme excessif a naturellement conduit quelques dconvenues. On compte
actuellement (en 1997) un volume annuel de plusieurs centaines de publications sur
le sujet et une bonne dizaine de congrs internationaux lui sont consacrs ou ont
une session spcialise sur les ondelettes. Les applications les plus prometteuses
qui semblent se dgager se retrouvent dans les domaines de lanalyse vocale, de
lanalyse des signaux radar et dans le domaine de la compression des images. Les
thmatiques de recherche sorientent vers les transformes de signaux priodiques ou support compact, les transformes multidimensionnelles, les transformes adaptes
au problme, les analyses multi-ondelettes, la dconvolution des signaux bruits, les
approches multichelles dans les algorithmes stochastiques et bien entendu la mise en
uvre des algorithmes de transforme en ondelettes discrte.
Analyse multirsolution de l image favorite
7/29/2019 75514306 Ondelettes Hermes
13/158
Chapitre 2
Pourquoi les ondelettes?
La plupart des signaux du monde rel ne sont pas stationnaires, et cest justement dans
lvolution de leurs caractristiques (statistiques, frquentielles, temporelles, spatiales)
que rside lessentiel de linformation quils contiennent. Les signaux vocaux et les
images sont ce titre exemplaires. Or lanalyse de Fourier (2.1) propose une approche
globale du signal, les intgrations sont faites de moins linfini plus linfini, et toute
notion de localisation temporelle (ou spatiale pour des images) disparat dans lespace
de Fourier ; il faut donc trouver un compromis, une transformation qui renseigne sur lecontenu frquentiel tout en prservant la localisation afin dobtenir une reprsentation
temps/frquence ou espace/chelle du signal.
Transforme de Fourier :
Tfourierf() =
+
f(t)ejtdt (1)
La premire solution qui vient naturellement lesprit est de limiter le domaine
dintgration temporel (ou spatial) laide dune fonction fentre que lon pourra
faire glisser pour explorer le signal ; on obtient ainsi la transforme de Fourier fentre
glissante ; voir lquation 2.2.
Transformation de Fourier fentre glissante :
Tfglissef(t, ) =
+
f(s)g(s t)ejsds (2)
Si on pose :
t,(s) = g(s t)ejs (3)
7/29/2019 75514306 Ondelettes Hermes
14/158
14 Ondelettes pour le signal numrique
on peut interprter cette transforme comme la projection de f sur la base desfonctions fentres glissantes :
Tfglissef(t, ) = f, t, (4)
La notation f, g reprsente le produit scalaire :
f, g =+
f(x)g(x)dx (pour des fonctions relles) (5)
Un certain nombre de fonctions fentres sont utilises, les plus connues sont les
fentres de Hanning, de Hamming, et de Gauss (quation 2.6) :
g(x) = 14 e
x2
2 (6)
dans ce dernier cas la transformation a t baptise transformation de Gabor (quation
2.8) et on appelle gaborette la fonction analysante. On notera que les fonctions
enveloppes sont normalises 1 ; la norme tant dfinie par :
f2 =+
f(x)f(x)dx (7)
Transformation de Gabor :
Tgaborf(t, ) = 14 +
f(s)e
(st)2
2 ejsds (8)
On trouvera sur la courbe 2. la reprsentation de la partie relle de gaborettes
pour deux frquences diffrentes. On peut vrifier que ltendue temporelle de la
fonction est indpendante de la frquence analyse par cette fonction.
La rsolution dans le plan temps-frquence de la transformation peut tre estime
par les variances de la fonction analysante dans lespace temporel et dans lespace
frquentiel :
2x = +
x2 |(x)|2 dx (9)
Si on considre une gaborette |(x)| = ex22 on a videmment t = 1 et dans cecas comme la transforme dune gaussienne est une gaussienne (ex
2
se transforme
par Fourier en ef2
) on trouve un cart type f dans le domaine frquentiel telque : f =
12 . On constate que les rsolutions temporelle t et frquentielle f
7/29/2019 75514306 Ondelettes Hermes
15/158
Pourquoi les ondelettes ? 15
Figure 2. Gaborettes
sont indpendantes, de sorte que le pavage de lespace temps-frquence (figure 2.) est
rgulier.
f
t
te m p s
fr q u e n c e
Figure 2. Pavage temps-frquence pour la transforme fentre glissante
Dans ce cas, on comprend que lanalyse nest pas idale car si une rsolution
temporelle faible est automatiquement lie la dtection des basses frquences,
la dtection des composantes hautes frquences du signal peut tre faite avec une
rsolution temporelle suprieure. Les deux rsolutions doivent varier en sens inverse
en conservant un produit constant pour un pavage nergtiquement rgulier de
lespace temps-frquence. Ceci doit conduire une utilisation rationnelle de cet
espace par la ralisation dans tous les cas du meilleur compromis possible entre la
rsolution temporelle et la rsolution frquentielle. Ce programme est ralis par
la transformation en ondelettes dont le principe est prcis dans lquation suivante
(2.10) :
7/29/2019 75514306 Ondelettes Hermes
16/158
16 Ondelettes pour le signal numrique
Transforme en ondelettes :
Tondf(a, b) =1a
+
f(t)(t b
a)dt (10)
Dans cette expression, a est le facteur dchelle et b le paramtre de translation. Lavariable a joue le rle de linverse de la frquence : plus a est petit moins londelette(la fonction analysante) est tendue temporellement, donc plus la frquence centrale
de son spectre est leve. On peut galement interprter cette expression comme une
projection du signal sur une famille de fonctions analysantes a,b construite partirdune fonction mre conformment lquation suivante :
a,b(t) =1
a(
t ba
) (11)
On notera que la norme est conserve lors du changement de facteur dchelle :
a,b2 = +
1
a
( t ba )2 dt (2.12)
=1
a
+
|(x)|2 adx
= 2
On pourra noter :
Tondf(a, b) = f, a,b (13)
La rsolution spatio-temporelle est calcule de la mme manire que
prcdemment : Si la largeur temporelle de (lcart type) est prise comme unit : = 1 alors on peut calculer la largeur de a,0 avec lquation 2.9 :
2t =
t2
a,0(t)
2
dt
=
t21
a( ta )2 dt
=
a2x2
1
a|(x)|2 adx
ce qui donne : t = a .
7/29/2019 75514306 Ondelettes Hermes
17/158
Pourquoi les ondelettes ? 17
On peut de mme calculer loccupation frquentielle de londelette en calculant
lcart type pour la transforme de Fourier a,01 de a,0 ; en prenant comme unitlcart type de la transforme de Fourier de londelette mre :
2 =
2a,0()2 d (2.14)
=
2
1
a
a(a)2 d=
2
a21
a
a()2 da
on trouve
= 1a
. De sorte que le pav lmentaire dans lespace temps-frquence
est de surface constante tandis que la rsolution temporelle est proportionnelle a etque la rsolution frquentielle est inversement proportionnelle a comme on le voitsur la figure 2..
1 / a
a
t e m p s
f r q u e n c e :
1 / a
Figure 2. Pavage temps-frquence pour la transforme en ondelette discrte
Les premires ondelettes utilises (en dehors de londelette de Haar que nous
tudierons plus loin) ont t londelette de Morlet, une gaussienne module par une
exponentielle complexe, et le chapeau mexicain , en ralit la drive seconde dune
gaussienne.
Ondelette de Morlet :
(x) =12
ex2
2 eiox (15)
1 On notera souvent dans la suite la transforme de Fourier dune fonction de faon abrge comme
suit :g() = + g(x)ejxdx
7/29/2019 75514306 Ondelettes Hermes
18/158
18 Ondelettes pour le signal numrique
Chapeau mexicain :
(x) =2
3
14 (1 x2)ex
2
2 (16)
La figure 2. prsente le chapeau mexicain pour deux valeurs du facteur dchelle :
a = 1 pour la courbe la plus localise et a = 2 pour la courbe la plus tendue (la figure2. prsente la rponse frquentielle poura = 1). La figure 2. prsente la partie relle delondelette de Morlet pour deux valeurs du facteur dchelle, on pourra comparer avec
la figure 2. o on constate que la fentre danalyse reste constante lors du changement
dchelle (frquence).
Figure 2. Chapeau mexicain
Figure 2. Ondelette de Morlet (partie relle)
Les reprsentations frquentielles des ondelettes de Morlet (o = 5), figure2., illustrent encore une fois les diffrences entre la transforme en ondelette et la
transforme de Fourier fentre glissante. On vrifie que la largeur spectrale de
7/29/2019 75514306 Ondelettes Hermes
19/158
Pourquoi les ondelettes ? 19
londelette varie en fonction du facteur dchelle inversement la largeur spatiale.
1086420
1.4
1.2
1
0.8
0.6
0.4
0.2
0
Figure 2. Ondelette de Morlet :()
1050-5-10
2
1.5
1
0.5
0
Figure 2. Chapeau mexicain :()Le facteur dchelle a et le pas de translation b sont des rels et la transformation en
ondelettes est continue et donc redondante. Le plan temps frquence est sur-analys.
Il est donc vident quune discrtisation de la transforme doit tre envisage si
on souhaite obtenir une transformation non redondante. Le pavage temps-frquence
obtenu par la transformation en ondelettes (figure 2.) suggre une mthode de
discrtisation exponentielle pour les chelles et pour le temps. Dans lexpression( tba ) le pas de translation lchelle a estba . On posera donc :
a = amo et b = nboamo avec ao, bo Z
7/29/2019 75514306 Ondelettes Hermes
20/158
20 Ondelettes pour le signal numrique
do lexpression de la transforme en ondelettes dicrte (2.17)2 donne ci-aprs.
Transforme en ondelettes discrte :
Tondf(m, n) = am2o
+
f(t)(amo t nbo)dt (17)
Si on choisit ao = 2 et bo = 1, on parle alors de transforme dyadique.
Les bases de la transforme en ondelettes sont poses mais de grandes questions
restent poses :
La transforme est-elle inversible ? Le choix des ondelettes est-il contraint ? Peut-on former des bases orthonormes dondelettes? Existe-il des algorithmes efficaces pour traiter le cas du signal numrique ? Comment traiter les signaux plusieurs dimensions ?
Cest ces questions et quelques autres que nous tenterons de rpondre dans les
chapitres suivants.
2 Il est important de noter que cest la transforme qui est discrte, londelette reste elle une fonction
continue.
7/29/2019 75514306 Ondelettes Hermes
21/158
Chapitre 3
Quelles ondelettes ?
3.1 Inversion - Admissibilit
On peut montrer [10] que si la fonction analysante (londelette) est convenablement
choisie, la transformation en ondelettes est inversible et la fonction peut tre
reconstruite aprs analyse suivant lquation (3.1) :
f = C1+
+
1a2
f, a,b
a,b da db (1)
Cette possibilit reste thorique car le calcul nest possible que numriquement et
sa convergence peut-tre trs lente.
Le coefficient C , si il existe, est donn par lquation (3.2) :
C = 2
+
()2 d
(2)
La condition dexistence de ce coefficient est galement la condition
dadmissibilit de la fonction ondelette analysante. Cette condition est explicite par
lquation 3.3 : +0
()2 d|| =0
()2 d|| < (3)Cette relation se ramne le plus souvent la condition exprime par lquation
3.4 qui nest pas trs contraignante et indique seulement que la fonction ondelette
doit tre moyenne nulle. Le choix de londelette est donc en principe trs ouvert, il
faut cependant noter que la robustesse et la vitesse de convergence de lalgorithme de
reconstuction donn par lquation 3.1 sont trs dpendantes du choix de londelette.
Il est clair, enfin, que la transforme en ondelettes ne sera intressante comme outil
danalyse du signal que si la fonction analysante (londelette) reste bien localise dans
7/29/2019 75514306 Ondelettes Hermes
22/158
22 Ondelettes pour le signal numrique
le temps et en frquence.
+
(t) dt = 0 (4)
3.2 Quelles transformes en ondelettes ?
On peut classer les transformes en ondelettes selon la famille laquelle appartiennent
les fonctions analysantes choisies. Les transformes obtenues sont suivant les cas
discrtes ou continues, redondantes ou non.
Les transformes continues sont obtenues en prenant le facteur dchelle a etle pas de translation b dans lensemble des nombres rels. Comme nous lavonsfait remarquer dans le chapitre prcdent, ces transformes sont videmment trs
redondantes car lespace temps-frquence est parcouru continment, ce type de
transformation ne peut, dans la pratique, tre effectu que de faon approximative
et il y a toujours en fait une discrtisation du calcul qui est opre.
Lapproche discrte du problme a le mrite de traiter le problme de
lchantillonnage de lespace temps-frquence avec rigueur et de fournir une mesure
de lventuelle redondance de la transformation obtenue. De plus, dans ce cas,
les algorithmes de calcul conduisent souvent des rsultats exacts (voir les bases
orthonormes et biorthogonales) sur des intervalles donns de lespace temps-
frquence. Nous tudierons donc plus en dtail le cas des transformes discrtes
qui sont dailleurs pratiquement les seules utilises en traitement des images. Les
donnes numriques sont de plus en plus des donnes primaires des systmes
(camras CCD) et leur traitement numrique conduit des donnes numriques
utilises le plus souvent telles quelles. Les mthodes de traitement discret sont donc
fondamentales. Il ne faut pas oublier cependant que si la transforme est discrte,
les fonctions de base utilises ne le sont pas, les ondelettes restent dans tous les cas
des fonctions continues. Les coefficients de la transforme sont dnombrables sur unintervalle de lespace temps-frquence. Mais la projection de la fonction sur des sous-
espaces crs par des sous-familles dondelettes est continue et ne poura en gnral
qutre estime numriquement. Parmi les transformes discrtes on distingue les
transformes redondantes, dont les trames (traduction libre de frames) dondelettes
que nous prsenterons sommairement et les transformes non redondantes parmi
7/29/2019 75514306 Ondelettes Hermes
23/158
Quelles ondelettes ? 23
lesquelles nous tudierons les plus utilises, savoir les bases orthonormes et
biorthogonales.
Les paquets dondelettes que nous ne prsenterons pas en dtail ici peuvent
appartenir suivant le cas lune ou lautre famille.
Pour rsumer, on peut donner le classement sommaire suivant :
Transformes redondantes :
transforme continue,
trame dondelettes (frames),
paquet dondelettes.
Transformes non redondantes :
analyse multirsolution : base orthonorme,
analyse multirsolution : base biorthogonale,
paquet dondelettes.
Cela tant, il reste examiner les gnralisations de la transforme en ondelette
unimodale de signaux une dimension.
La premire extension envisageable est le passage du traitement des signaux mono-
dimensionnels au traitement des signaux bi-dimensionnels, tri-dimensionnels, voire
au-del. Lintrt de cette extension est vident pour qui se proccupe de traitement
des images 2D et 3D. Dans ce domaine, nous prsenterons les lments de base surlesquels sappuient les principales mthodes de gnralisation et nous illustrerons par
deux techniques choisies parmi les plus utilises dans les applications actuelles.
Le deuxime type de gnralisation quil conviendrait dexaminer est le problme
du traitement des signaux vectoriels ou multispectraux. Le cas le plus commun
est celui des images couleur. Les multi-ondelettes pourraient constituer une piste
intressante. Mais l, nous sommes vraiment dans le domaine de la recherche et il
ne semble pas que les rsultats soient suffisamment probants pour quils puissent tre
prsents ici. Alors, avis aux amateurs...
7/29/2019 75514306 Ondelettes Hermes
24/158
7/29/2019 75514306 Ondelettes Hermes
25/158
Chapitre 4
Bases orthonormes, analyse multirsolution
4.1 Axiomatique de base
4.1.1 Espaces dapproximation
Nous nous plaons dans lespace L2(R) des fonctions continues dune variable relleet de carr intgrable. Une analyse la rsolution j de la fonction f sera obtenue paraction dun oprateur linaire Aj surf, tel que :
Ajf Vj (1)Vj tant un sous espace de L
2, Aj sera un projecteur (idempotent).
On construira une analyse multirsolution laide de sous-espaces Vj embots lesuns dans les autres, tels que le passage de lun lautre soit le rsultat dun changement
dchelle (zoom).
Par exemple, dans le cas dyadique on aura :
f(x)
Vj
f(
x
2
)
Vj+1 (2)
ce qui correspond une dilatation dun facteur2. Lespace Vj+1 contient des signauxplus grossiers que lespace Vj et il est clair que :
Vj+1 Vj (3)
Laxiomatique correspondante peut sexprimer comme suit :
Soit un ensemble de sous espaces de L2 tels que :
..... V2 V1 V0 V1 ..... Vj+1 Vj .....
7/29/2019 75514306 Ondelettes Hermes
26/158
26 Ondelettes pour le signal numrique
jZ
Vj = L2(R) (4.4)
jZ
Vj = {0} (4.5)
j Z si f(x) Vj f(21x) Vj+1(ou f(2jx) V0) (4.6)k Z si f(x) V0 f(x k) V0(invariance par translation) (4.7)
Cet ensemble dfinit une analyse multirsolution de L2(R).
Remarque 1 La proprit 4.4 assure la convergence de lanalyse et peut aussiscrire :
limj
Vj = L2(R) (8)
On dit parfois que+ Vj est dense dans L
2(R).
Dans ces conditions, on peut montrer quil existe une fonction dite fonction
dchelle qui par dilatation et translation engendre une base orthonorme de Vj . Cettefonction sera note :
(x) L2(R) (9)
et les fonctions de bases sont construites suivant la relation :
j,n(x) = 2 j2 (2jx n) avec n Z (10)
Il suffit dailleurs que (., n) soit une base de Vo.La base sera orthonorme si :+
(x)(x + n)dx = (n) n Z (11)
Rappelons (voir quation 2.5) que le produit scalaire3 est dfini par :
f, g = +
f(x)g(x)dx (pour des fonctions relles ou complexes) (12)
3 Lanalogie avec le produit scalaire dans lespace gomtrique habituel pourra aider comprendre les
diffrents concepts utiliss (vecteur de base, sous-espace, projection, composantes dun vecteur, etc...). Il
conviendra cependant de se souvenir que lanalogie reste limite car lespace gomtrique est de dimension
3 alors que lespace des fonctions est de dimension infinie !
7/29/2019 75514306 Ondelettes Hermes
27/158
Bases orthonormes, analyse multirsolution 27
V0
V1 W1
V2 W2
V3 W3
Figure 4. Schma de lanalyse multirsolution
La relation dorthogonalit entre les fonctions de base pour une chelle donne
4.11 pourra donc scrire :j,n, j,k
= (n k) n,k,j Z (13)
Remarque 2 On peut utiliser plusieurs fonctions pour construire par translationune base du sous-espace Vo , cette libert est mise profit dans la construction desmulti-ondelettes. Les fonctions doivent, bien entendu, tre orthogonales entre elles.
Sur ce sujet, on pourra consulter les travaux de J. Geronimo [16], [13], ou, titre
introductif, louvrage de G. Strang [35].
Laction du projecteur surf fournira sa dcomposition sur la base des fonctionsdchelle et les coefficients de cette dcomposition constituent lapproximation
lchelle j de f.
Ajf =n
f, j,n
j,n (14)
On pose :
ajn =
f, j,n
(15)
lapproximation la rsolution j de la fonction f sera dfinie par la suite discrte desnombres (rels ou complexes) ajn.
7/29/2019 75514306 Ondelettes Hermes
28/158
28 Ondelettes pour le signal numrique
x21.510.50-0.5
1
0.8
0.6
0.4
0.2
0
Figure 4. Fonction dchelle de lanalyse de Haar
Une suite numrique forme par chantillonnage dun signal continu rel pourra
tre considre comme une approximation une rsolution donne du signal continu.
La base tant orthonorme, la norme de la fonction (lnergie) peut tre calcule
partir de ses coordonnes :
Ajf2 =+
n= ajn
2
(16)
4.1.2 Espaces des dtails
Lespace des dtails vient complter lanalyse.
On peut dfinir pour chaque Vj son complment orthogonal Wj dans Vj1 tel que :
Vj1 = Vj WjL2(R) =
jZ Wj
Comme Wj1 est orthogonal Vj1, alors Wj1 sera orthogonal Wj ; cette
proprit scrit :
j, k = j alors Wj Wk (17)
Les sous-espaces Wj ne forment pas une famille despaces embots, mais lesproprits dchelle et dinvariance par translation sont conserves.
7/29/2019 75514306 Ondelettes Hermes
29/158
Bases orthonormes, analyse multirsolution 29
x21.510.50-0.5
1
0.5
0
-0.5
-1
Figure 4. Ondelette mre de lanalyse de Haar
Dans ces conditions, on peut montrer quil existe une fonction appele ondelette
qui par dilatations et translations engendre une base orthonorme des Wj et donc deL2.
Cette fonction est note :
(x) L2(R) (18)
et les fonctions de base sont construites suivant la relation :
j,n(x) = 2 j2 (2jx n) avec n Z (19)
Lorthonormalit de la base dondelettes scrit :j,n, i,k
= (j i)(n k) j, i, n, k Z (20)
Lapproximation lchelle immdiatement plus fine pourra donc tre reconstruite
en utilisant les dtails du signal fournis par sa projection sur la base de Wj suivant larelation suivante :
Aj1f = Ajf +n f, j,nj,n (21)
On notera Dj le projecteur surWj et le signal de dtail sera dcrit par la suitenumrique :
djn =
f, j,n
(22)
7/29/2019 75514306 Ondelettes Hermes
30/158
30 Ondelettes pour le signal numrique
Figure 4. Fonction exemple
donc :
Djf =n
f, j,n
j,n (23)
et la formule de reconstruction scrit :
Aj1f = Ajf + Djf (24)
Le signal de dtail est constitu dune suite numrique dont les lments sont aussi
les coefficients de la transforme en ondelettes.
Le schmade la dcomposition est reprsent symboliquement sur la figure 4. dans
laquelle la largeur des rectangles symbolisant les sous-espaces est proportionnelle la
densit de lchantillonnage ralis par la projection du signal dans le sous-espace
considr.
Exemple 1 En exemple, on peut prsenter lanalyse de Haar. Les sous espaces Vjsont dfinis par :
Vj =
f L2(R) telles que k Z on a f[2jk,2j(k+1)[ = constante
(25)
Le sous espace Vj est lensemble des fonctions constantes sur les intervalles delargeur 2j . Les fonctions de base sont construites partir de la fonction dchelle(x) gale 1 de 0 1 et nulle partout ailleurs :
(x) =
0 si x < 01 si 0 x < 10 si 1 x
(26)
7/29/2019 75514306 Ondelettes Hermes
31/158
Bases orthonormes, analyse multirsolution 31
Figure 4. Aof (en trait fin) et A1f
La fonction ondelette est dfinie par :
(x) =
0 si x < 01 si 0 x < 1/21 si 1/2 x < 10 si 1 x
(27)
Les figures 4. et4. prsentent les reprsentations graphiques de ces fonctions.
Nous prenons une fonction quelconque pour illustrer la dcomposition aux
chelles j = 0 etj = 1. Cette fonction est prsente sur le graphe de la figure 4..
Ses projections sur le sous espace Vo et sur le sous espace V1 sont prsentes dansla figure 4..
La projection surW1, donc le signal de dtail, est donne sur la figure 4..
On vrifie bien que :
Aof = A1f + D1f
conformment lquation 4.24.
4.1.3 Analyse multirsolution et localisation spatio-frquentielle
On aura une illustration plus visuelle de la signification spatio-frquentielle de
lanalyse multirsolution en considrant un signal 2 dimensions. Nous prendrons
7/29/2019 75514306 Ondelettes Hermes
32/158
32 Ondelettes pour le signal numrique
x420-2-4
0.1
0.05
0
-0.05
-0.1
Figure 4. D1f
une image volontairement dgrade par un bruit haute frquence (voir les figures du
tableau 4.) pour que lespace frquentiel soit rempli.
Cette image est dcompose par une analyse de Haar et on obtient une image
grossire et une image de dtails (voir les figures du tableau 4.).
On constate que les dtails de limage (voir les figures du tableau 4.) sont bien
localiss, ils correspondent approximativement aux contours et videmment au bruit
ajout.
Lanalyse de Fourier de ces images montre que la localisation frquentielle est
relativement mdiocre, la sparation en deux bandes de frquences nest pas nette.
Limage qui prsente le spectre de lapproximation ne devrait contenir que des basses
frquences, tandis que limage qui donne le spectre de limage des dtails ne devrait
rvler que les composantes haute frquence du signal.
Si la mme opration est mene avec uneautre analyse multirsolutionutilisant des
bases (chelle et ondelette) dont la localisation espace-frquence est mieux quilibre,
on trouve des rsultats sensiblement diffrents. Les bases utilises dans lexemple
trait ici seront prsentes ultrieurement, il sagit de fonctions construites partir de
B-splines cubiques (voir les images du tableau 4.). Limage de dtail (voir les images
du tableau 4.) montre que la localisation spatiale est moins bonne que dans lanalyse
de Haar.
La localisation frquentielle des composantes est en revanche bien meilleure et
le dcoupage en deux sous-bandes frquentielles apparat nettement sur les images
spectrales.
7/29/2019 75514306 Ondelettes Hermes
33/158
Bases orthonormes, analyse multirsolution 33
Tableau 4. Image originale et transforme de Fourier
Tableau 4. Analyse de Haar : approximation lchelle 1 et son spectre
Tableau 4. Analyse de Haar : image des dtails lchelle 1 et son spectre
7/29/2019 75514306 Ondelettes Hermes
34/158
34 Ondelettes pour le signal numrique
Tableau 4. Analyse B-spline cubique : approximation 1 et son spectre
7/29/2019 75514306 Ondelettes Hermes
35/158
Bases orthonormes, analyse multirsolution 35
Tableau 4. Analyse B-spline cubique : image des dtails 1 et son spectre
4.1.4 Gnralisation : paquets dondelettes
Le principe de lanalyse multirsolution de lespace L2 des fonctions continues dunevariable relle et de carr intgrable peut-tre tendu des sous-espaces de celui-ci.
On peut, par exemple, appliquer le mme schma aux sous-espaces Wj engendrs parlanalyse prcdente. Cette analyse peut tre mene avec les mmes basesde fonctions
dchelle et dondelettes ou avec des bases diffrentes. On peut, de mme, changer de
fonctions de base chaque chelle. Dans ces algorithmes, la reconstruction parfaite
est assure par la rutilisation lors de la synthse, pour une rsolution donne, de la
mme base que lors de lanalyse pour cette rsolution.
La gnralisation prsente qui consiste analyser les sous-espaces de dtail du
signal est baptise analyse en paquets dondelettes. Lalgorithme correspondant peut-
tre schmatis par le diagramme 4..
Cet algorithme conduit une dcomposition en sous-bandes de frquence du
signal ; cette dcomposition est ajustable par le choix des composantes. Ce type
danalyse offre une grande souplesse pour lutilisateur et lui permet de sadapter au
signal analyser. Les principales applications de lanalyse en paquets dondelettes
sont dans le domaine de la compression des images. Tous les algorithmes et toutes les
proprits des fonctions dchelle, des ondelettes et des filtres associs que nous allons
tudier dans les pararaphes et chapitres suivants sont utilisables dans ce schma. Nous
ne reviendrons donc pas sur cette gnralisation de lanalyse multirsolution.
4.2 Algorithme rcursif
Le problme pour effectuer concrtement la dcomposition est que lon ne dispose
pas en gnral du signal f mais seulement dune approximation une chelle donne.Il faut donc trouver un algorithme qui, partir de cette approximation, permet de
trouver lapproximation et les dtails la rsolution immdiatement infrieure, ce
qui par itrations successives conduit lanalyse du signal pour toutes les rsolutions
7/29/2019 75514306 Ondelettes Hermes
36/158
36 Ondelettes pour le signal numrique
V0
V1 W1
V2 W2,1
V3 W3,1
W2,2 W2,3
W3,2 W3,7W3,6W3,5W3,4W3,3
Figure 4. Analyse en paquets dondelettes
infrieures celle de dpart. Deux algorithmes principaux ont t mis en vidence :
lalgorithme trous [33] et lalgorithme de Mallat [25][26][27]. Le premier concerne
des analyses multirsolution non-orthogonales, le second est pratiquement le seul
utilis dans le cas des analyses orthogonales et biorthogonales. Nous ne prsenterons
ici que lalgorithme de Mallat. Une prsentation complte est donne dans [32].
7/29/2019 75514306 Ondelettes Hermes
37/158
Bases orthonormes, analyse multirsolution 37
4.2.1 Algorithme danalyse
4.2.1.1 Projection sur les fonctions dchelle
Le point clef est fourni par la dcomposition de ajn =
f, j,n
en fonction de
aj1n =
f, j1,n.
Par construction (x) est une fonction de V0 ; comme V0 V1 on peutdcomposer(x) sur la base de V1. Et donc h[n] suite numrique avec n Ztelle que :
(x) = n
h[n]1,n(x) (28)
avec, conformment 4.10, 1,n(x) = 212 (2x n), soit :
h[n] =
, 1,n
(29)
La suite numrique h[n] sera considre comme tant la rponse impulsionnelledun filtre numrique.
La construction de cette suite peut tre mene partir de la donne de (x) et nousverrons quun choix de h[n] tant fait (certaines conditions sont respecter) la fonctiondchelle peut tre dtermine. On pourra donc dfinir une analyse multirsolution
indiffremment en partant de la fonction dchelle ou du filtre numrique associ. Il
faut noter que cette dualit dapproche correspond lexistence de deux coles : les
traiteurs de signal continu qui ont abord le problme par les fonctions de projection et
les traiteurs de signal discret qui ont travaill sur le filtrage et sur les bancs de filtres.
Il a t largement reconnu et dmontr que ces deux approches reposaient en fait sur
les mmes concepts de base et ne diffraient pas vraiment ; il nen reste pas moins que
les deux coles subsistent au moins dans la faon de prsenter les choses. Nous nous
sommes plutt placs dans la perspective des traiteurs de signal continu mme si dans
notre esprit, le signal dentre de nos systmes est discret et correspond directement
aux coefficients dune premire projection sur le sous-espace de rsolution 0.
Remarque 3 Remarquons tout dabord que (x) tant par construction norme (en
7/29/2019 75514306 Ondelettes Hermes
38/158
38 Ondelettes pour le signal numrique
nergie) on a :
(x)2 = , = 1
=
+
(x)(x)dx
=
+
k
h[k]1,k(x)n
h[n]1,n(x)dx
=k
n
h[n]h[k]
+
1,k(x)1,n(x)dx
= k n h[n]h[k]1(x)2
(n k)
et donc, la norme se conservant travers les chelles :n
h2[n] = 1 (30)
Montrons que la dcomposition est la mme pour des chelles quelconques.
On a :
(x) =n
h[n]21/2(2x n) (31)
donc :
j,n(x) = 2j/2k
h[k]21/2(2(2jx n) k) (32)
ce qui en regroupant les indices et les exposants conduit lquation :
j,n =k
h[k]j1,k+2n (33)
Donc on peut calculer les coefficients ajn =
f, j,n
de lapproximation la
rsolution j :
ajn =k
h[k]
f, j1,k+2n
(34)
si on pose l = k + 2n, cette expression scrit :
ajn =l
h[l 2n] f, j1,l (35)et si on note : h[n] = h[n] (36)
7/29/2019 75514306 Ondelettes Hermes
39/158
Bases orthonormes, analyse multirsolution 39
la squence retourne ou le filtre symtrique de h, on obtient :
ajn =l
h[2n l] f, j1,l (37)et on aura finalement lquation rcursive suivante :
ajn =l
h[2n l]aj1l (38)Si on considre ajn comme une squence numrique indexe par n, le calcul
prcdent peut tre interprt comme un produit de convolution entreh et aj1 valu
pour un indice sur deux ; ou encore comme le filtrage de la squence aj1par le filtrede rponse impulsionnelle h suivi par un sous-chantillonnage de rapport 2.Exemple 2 Encore une fois lexemple de Haar pourra tre trait avec profit.
Rappelons que dans ce cas la fonction dchelle est construite partir de la fonction
mre (x) dfinie par :
(x) =
0 si x < 01 si 0 x < 10 si 1 x
(39)
On aura donc :1,0(x) =
2(2x) = 1 si x 0, 12
1,0(x) =
2(2x) = 0 sinon(40)
Ce qui permet la dcomposition suivante pour (x) :
(x) =1
21,0(x) +
12
1,1(x)
La squence numrique correspondant la rponse impulsionnelle du filtre h[n]sera donc :
h[n] =
..., 0,1
2,
12
, 0,...
(41)
Llment soulign correspond n = 0.
7/29/2019 75514306 Ondelettes Hermes
40/158
40 Ondelettes pour le signal numrique
4.2.1.2 Projection sur les fonctions ondelettes
Un schma analogue est bti partir de la dcomposition de londelette de Wo sur labase de V1 :
=n
g[n]1,n (42)
ou de faon plus dtaille :
(x) =n
g[n]
2(2x n) (43)
ce qui conduit lquation de construction de g[n] suivante :
g[n] = , 1,n (44)g[n] sera galement considre comme la rponse impulsionnelle dun filtre
numrique ; nous verrons que ce filtre est li au filtre h[n] et quil peut tre construit partir de ce dernier.
Un calcul analogue en tous points au prcdent permet dcrire les coefficients de
dtail :
djn =
f, j,n
(45)
djn =
kg[k]
f, j1,k+2n
(46)
On introduit galement le filtre symtrique dont la rponse impulsionnelle
correspond la squence g[n] retourne :g[n] = g[n] (47)La dcomposition en ondelettes lchelle j pourra donc scrire :
djn =l
g[2n l] f, j1,l (48)ou encore :
djn = l g[2n l]aj1l (49)
Cette relation sera interprte de la mme manire que prcdemment.
Exemple 3 Reprenons lexemple de lanalyse multirsolution de Haar. Rappelons
que dans ce cas la fonction dondelette est construite partir de la fonction mre
7/29/2019 75514306 Ondelettes Hermes
41/158
Bases orthonormes, analyse multirsolution 41
(x) dfinie par :
(x) =
0 si x < 01 si 0 x < 1/21 si 1/2 x < 10 si 1 x
(50)
On aura donc la dcomposition suivante pour (x) :
(x) = (2x) (2x 1) (51)
soit :
(x) =1
21,0(x)
12
1,1(x) (52)
La squence numrique correspondant la rponse impulsionnelle du filtre g[n]sera donc :
g[n] =
..., 0,
12
, 12
, 0,...
(53)
On constate que dans le cas de lanalyse de Haar, lalgorithme de dcomposition
est trs simple car les filtres h[n] et g[n] impliqus sont trs courts. En fait le signalnumrique la rsolution infrieure est obtenu par un simple moyennage entre le
point tudi et son plus proche voisin, tandis que le signal de dtail (perdu lors du
changement de rsolution) est obtenu en faisant la diffrence entre le point tudi et
son plus proche voisin, le tout un facteur de normalisation prs. Malheureusement
nous verrons que cette simplicit algorithmique ne conduit pas une analyse trs
performante du point de vue de la rsolution spatio-frquentielle.
La figure 4. rsume lalgorithme rcursif danalyse multirsolution de Mallat.
4.2.2 Algorithme de reconstruction
La dcomposition est gouverne par lquation :
Aj1f =n
ajnj,n +n
djnj,n (54)
avec ajn =
f, j,n
et djn =
f, j,n.
7/29/2019 75514306 Ondelettes Hermes
42/158
42 Ondelettes pour le signal numrique
anj-1 an
j
dnj
h
g
2
2
Figure 4. Algorithme danalyse de Mallat
Aj est un projecteur donc Aj(Ajf) = Ajf ce qui scrit :
Aj1f =n
aj1n
Aj1f, j1,n j1,n (55)
En remplaant dans aj1n le terme Aj1f par son expression donne dans 4.54, onobtient lquation suivante :
aj1n =k
ajk
j,k, j1,n
+k
djk
j,k, j1,n
(56)
Or nous avons vu (quation 4.33) au paragraphe prcdent que :
j,k =l
h[l]j1,l+2k (57)
on peut donc valuer le produit scalaire des fonctions dchelle pour deux rsolutions
successives quelconques :j,k, j1,n
=l
h[l][n l 2k]j1,l+2k, j1,n (58)car les fonctions dchelle forment une base orthonorme pour une chelle donne ; ce
qui donne :
j,k, j1,n
= h[n 2k] (59)
et de mme pour les ondelettes :j,k, j1,n
= g[n 2k] (60)
do lquation de reconstruction :
aj1n =k
ajkh[n 2k] +k
djkg[n 2k] (61)
7/29/2019 75514306 Ondelettes Hermes
43/158
Bases orthonormes, analyse multirsolution 43
Cette quation est une somme dquations de filtrage (produits de convolution) si
on remplace la suite ajk par une suite ajl qui concide avec a
jk pourl = 2k ; a
j2k = a
jk
et qui est nulle pour les valeurs de l intermdiaires (et de mme pour la suite djk).
ajk = {, , , , , }ajl = {, 0, , 0, , 0, , 0, , 0, , 0}
(62)
Cette opration qui consiste intercaler un zro entre les chantillons dune srie
sappelle sur-chantillonnage. Lquation 4.61 scrit alors :
aj1n =l
ajl h[n l] +l
djl g[n l] (63)
Remarque 4 Une autre solution aurait t de sous-chantillonner les filtres h etg.
La figure 4. prsente lalgorithme de synthse ou de reconstruction tudi. Les
algorithmes danalyse et de reconstruction que nous venons de prsenter sont appels
algorithmes de Mallat ou parfois algorithmes pyramidaux.
anj-1
anj
dn
h
g
2
2
+
Figure 4. Algorithme de synthse de Mallat
On peut dire en conclusion que le calcul de la transforme en ondelettes
discrte (rappelons que la transforme est discrte, pas les ondelettes) sur des basesorthonormes se ramne des oprations de filtrage numrique suivies de sous-
chantillonnage. La reconstruction est parfaite et seffectue galement par des filtrages
numriques prcds de sur-chantillonnage. Les mmes filtres ( un renversement
du temps prs) sont utiliss dans les deux cas. La mise en uvre de cet algorithme
doit tre mene en profitant au maximum de ces particularits. Toutes les techniques
7/29/2019 75514306 Ondelettes Hermes
44/158
44 Ondelettes pour le signal numrique
classiques de mise en uvre de filtres linaires numriques peuvent tre utilises, mais
devront tre adaptes. Ltude des consquences des troncatures et quantifications
diverses inhrentes toute mise en uvre devra tre mene en tenant compte des
spcificits de lalgorithme pyramidal.
Comme toujours quand il est question de filtrage linaire, la nature des filtres
utiliss (RIF ou FIR, symtriques ou non, rcursifs ou non) conditionne le cot
de calcul et le choix de lventuelle architecture matrielle dimplantation. Le
choix des filtres est li dune part aux contraintes lies aux principes de lanalyse
multirsolution et dautre part aux contraintes mises a priori sur les bases dondelettes
et/ou de fonctions dchelle choisies. Le chapitre suivant est ddi lexploration des
contraintes du premier type et fournit les lments qui doivent servir de guide lors de la
construction dune analyse multirsolution et des filtres et fonctions de base associs.
Nous verrons, dans le prochain paragraphe, comment lalgorithme de
reconstructionpeut tre utilis pour construire uneapproximation numrique aussi fine
que souhaite des fonctions dchelle et des ondelettes partir des filtres numriques
associs.
Exemple 4 Un bon exercice pour bien comprendre le fonctionnement de cet
algorithme trs simple consiste le tester la main sur un cas lmentaire. Nous
proposons de traiter le problme de lanalyse et de la reconstruction sur un niveau en
chelle dun signal numrique en forme de rampe par une analyse de Haar.
Nous avons vu que les filtres associs sont les suivants (le coefficient de rang0 est
soulign) :
h[n] =
1
2,
12
et donc h[n] = 1
2,
12
et :
g[n] =
1
2, 1
2
et donc g[n] = 1
2,
12
Le signal numrique analyser sera :
ao[n] = {..., 0, 1, 2, 3, 4, 5, 6, 7,...}
et nous supposerons quil constitue la liste des coefficients du signal dapproximation lchelle j = 0.
On applique le filtre h[n] suivi dun sous-chantillonnage, ce qui donne :a1[n] =
...,
12
,5
2,
92
,13
2..
7/29/2019 75514306 Ondelettes Hermes
45/158
Bases orthonormes, analyse multirsolution 45
On fait de mme avec g[n], do :d1[n] =
..., 1
2, 1
2, 1
2, 1
2..
Pour la reconstruction, on sur-chantillonne en intercalant un 0 entre chaquecoefficient avant de filtrer parh[n] etg[n] :
a1[n]
...,1
2, 0,
52
, 0,9
2, 0,
132
..
d
1
[n] ..., 12 , 0, 12 , 0, 12 , 0, 12 ..puis aprs filtrage :
...,1
2,
1
2,
5
2,
5
2,
9
2,
9
2,
13
2, ..
+
..., 1
2,
1
2, 1
2,
1
2, 1
2,
1
2, 1
2, ..
on retrouve bien la squence initiale :
ao[n] = {..., 0, 1, 2, 3, 4, 5, 6, 7,...}
4.3 Construction numrique des fonctions de base
Nous prsentons dans ce paragraphe un algorithme qui dcoule de lalgorithme
dyadique de Mallat et qui permet de construire numriquement des approximations
des fonctions dchelle et donc des ondelettes. On peut choisir volont la rsolution
avec laquelle ces approximations sont obtenues. Cet algorithme est souvent appel
Algorithme cascade, et il a t propos initialement, semble-t-il par I. Daubechie en
1988.
Dans lanalyse multirsolution dune fonction f de L2 les coefficients de laprojection sur le sous espace Vj sont :
ajn =
f, j,n
(64)
La fonction dchelle mre est :
(x) = o,o(x) (65)
La famille engendre est orthonorme par translation, on a :, o,n
= (n) (66)
7/29/2019 75514306 Ondelettes Hermes
46/158
46 Ondelettes pour le signal numrique
Les ondelettes forment des bases des sous-espaces orthogonaux Vj , donc :, j,n
= 0 j 0 et k Z (67)
Lanalyse multirsolution de la fonction dchelle (x) donne donc lchellej = 0
a0n = (n)et
d0n = 0(68)
Ces valeurs peuvent tre utilises comme valeurs initiales pour lalgorithme
de reconstruction permettant de calculer les approximations plus fines de . Lescoefficients de dtail restent nuls car nous explorons les chelles ngatives :
djn = 0 j 0 et n Z (69)
Nous aurons donc simplement :
a1n =k
h[n 2k]a0n (70)
cette expression sera simplement itre, de sorte que lapproximation lchelle jde la fonction dchelle sera obtenue aprs j itrations par :
ajn = k
h[n 2k]aj+1n (71)
Nous avons vu que ce calcul se ramne un sur-chantillonnage de la squence
dentre suivi du filtrage de la squence obtenue par le filtre h[n]. La convergencede lalgorithme est assure par la convergence de lanalyse multirsolution et
rciproquement, les axiomes de base indiquent que si j alors Vj tend versL2. Un analyse mathmatique rigoureuse indique quune interpolation simple de lasquence ajn (considre comme lchantillonne dune fonction continue) conduit une fonction continue qui tend vers quand j . Dans la pratique on pourrautiliser une interpolation par des fonctions polynomiales dordre 0 (fonction constante
par morceaux) ou 1 (fonction linaire par morceaux).Pour cette interpolation on admet
donc que :
j,o(n) = 2 j2 (n2j) ajn (72)
A partir de lapproximation de la fonction dchelle on peut construire uneapproximation la mme rsolution de la fonction dondelette qui est une combinaison
7/29/2019 75514306 Ondelettes Hermes
47/158
Bases orthonormes, analyse multirsolution 47
an-j
h2 h2(n)
cellules identiques
Figure 4. Algorithme cascade pour la fonction dchelle
linaire de translates entires de cette fonction : =
n
g[n]1,n (73)
ce qui scrit :
(x) =
2n
g[n](2x n) (74)
On peut donc envisager de calculer une approximation de londelette pour des
valeurs discrtes de la variable en posant :
x = 2jk, k tant un entier
il vient :
(2j1k) =
2n
g[n](2jk n) (75)
ou encore :
j,o = 2J2 (2j1k)
2n
g[n]ajn2jk (76)
Linterprtation de cette relation en terme de filtrage numrique conduit
introduire une version sur-chantillonne dun facteur 2j du filtre g note g(j) dfiniepar :
g(j)
(k) = g(2jk) si 2jk est entier0 sinon (77)Dans ces conditions, londelette sera approxime par le filtrage de lapproxim de
la fonction dchelle par le filtre sur-chantillonn :
j,o = 2J2 (2j1k)
2g(j) ajk (78)
7/29/2019 75514306 Ondelettes Hermes
48/158
48 Ondelettes pour le signal numrique
Il est, dautre part, possible de construire un algorithme cascade de la mme
faon pour obtenir lapproximation de la fonction dondelette. En effet, les ondelettes
forment des bases des sous-espaces orthogonaux entre eux, donc :, j,n
= (j, n) j 0 et k Z (79)
Lanalyse multirsolution de la fonction dondelette (x) donne donc lchellej = 0
a0n = 0et
d0n = (n)(80)
Ces valeurs peuvent tre utilises comme valeurs initiales pour lalgorithme
de reconstruction permettant de calculer les approximations plus fines de . Lescoefficients dapproximation ne sont nuls qu lchelle 0 etceux de dtails restent nulspour les chelles plus fines car, comme pour les fonction dchelle, nous explorons les
chelles ngatives :
djn = 0 j < 0 et n Z (81)
Nous aurons donc simplement :
a1n =k
g[n 2k]d0n (82)
et :
a2n =k
h[n 2k]a1n
cette expression sera simplement itre, de sorte que lapproximation lchelle jde la fonction dondelette sera obtenue aprs j itrations par :
ajn =k
h[n 2k]aj+1n (83)
Nous avons vu que ce calcul se ramne un sur-chantillonnage de la squence
dentre suivi du filtrage de la squence obtenue par le filtre h[n]. La convergence delalgorithme est toujours assure par la convergence de lanalyse multirsolution. On
aura donc :
j,o(n) ajn (84)
Lalgorithme cascade est donc identique celui permettant de construire la
fonction dchelle, seule la premire tape diffre car cest le filtre g qui y est appliqu
7/29/2019 75514306 Ondelettes Hermes
49/158
Bases orthonormes, analyse multirsolution 49
( la premire itration seulement). On peut vrifier que les deux mthodes proposes
pour construire des approximations des ondelettes sont en fait quivalentes.
On trouvera sur les schmas 4. et 4. une description illustre de lalgorithme
cascade pour la construction de la fonction dchelle et la mthode qui permet den
dduire londelette.
g(j)
g
2jg(j)
a-jn 2-1/2j(n)
(a)
(b)
Figure 4. Construction numrique de londelette : (a) sur-chantillonnage du filtre
g, (b) construction de
Les figures du tableau 4. montrent la reconstruction progressive de la fonctiondchelle correspondant au filtre de Daubechies pourN = 2 (voir paragraphe 6.4). Cesfonctions ne peuvent pas tre construites directement car il nexiste aucune formule
analytique le permettant. En comparant avec la fonction dchelle reconstruite par un
grand nombre ditrations, on constate que la convergence de lalgorithme cascade est
rgulire et rapide.
Cet algorithme cascade peut, en fait, tre considr comme un cas particulier dun
algorithme plus gnral qui permet de construire des approximations des projections
sur les sous-espaces Vj et Wj dune fonction f de L2(R). Le calcul direct de cesprojections, qui sont des fonctions continues, serait trs lourd et lerreur invitable
affectant le rsultat difficile matriser. Ce calcul, dans le cas dune projection surVjconsisterait valuer lexpression suivante :
Ajf =+n=
ajnj,n (85)
Si on se place dans le cas o j > 0, on peut se contenter de lapproximation de
7/29/2019 75514306 Ondelettes Hermes
50/158
50 Ondelettes pour le signal numrique
x543210
0.8
0.6
0.4
0.2
0 x 1086420
0.6
0.5
0.4
0.3
0.2
0.1
0-0.1
x20151050
0.4
0.3
0.2
0.1
0
-0.1
x403020100
0.3
0.2
0.1
0
Tableau 4. Premires itrations et fonction dchelle (Daubechies-2)
7/29/2019 75514306 Ondelettes Hermes
51/158
Bases orthonormes, analyse multirsolution 51
Ajf lchelle 0 :
Ao(Ajf) = A1(Ajf) + D1(Ajf) (86)
Or, comme W1 V1 et Vj V1, alors W1 Vj et donc :
D1(Ajf) = 0 (87)
donc :
Ao(Ajf) = A1(Ajf) (88)
et en continuant le raisonnement, on montre que :
Ao(Ajf) = Aj(Ajf) (4.89)
Ao(Ajf) = Ajf
Comme la dcomposition est une transformation bijective, la reconstruction,
mene partir des ajn, obtenus par lanalyse de f, et des coefficients de dtail mis zro, conduit aux coefficients de Ao(Ajf). La squence de ces coefficients reprsenteune approximation lchelle 0 de la projection de f sur le sous-espace Vj .
Pour le signal de dtail, Djf, on aura :
Ao(Djf) = A1(Djf) + D1(Djf) (4.90)= A1(Djf) (4.91)
CarWi Wj , j = 1. En poursuivant le raisonnement et en remarquant queVj Wj et que loprateurDj est idempotent, on arrive :
Ao(Djf) = Aj(Djf) + Dj(Djf) (4.92)
Ao(Djf) = Djf (4.93)
On devra donc mener la reconstruction du signal de dtail en partant des djn(donns par lanalyse du signal f) et en mettant zro tous les autres coefficients.
La squence des coefficients obtenus constituera une approximation lchelle 0 dusignal de dtail lchelle j.
On peut, bien entendu, choisir daffiner davantage ces approximations en
continuant la reconstruction pour des valeurs de j ngatives. La reconstruction estmene en utilisant lalgorithme de reconstruction de Mallat. Le rsultat nous donne
une vue non sous-chantillonne du signal dapproximation ou du signal de dtail
7/29/2019 75514306 Ondelettes Hermes
52/158
52 Ondelettes pour le signal numrique
de f lchellej. Cest lamthode qui a t utilise pour construire la srie des images4..
On retrouve lalgorithme cascade en prenant f = j,o. On aura ajn = (n) et
djn = 0 :
Ajj,o =+n=
j,o,j,n
j,n (4.94)
=+n=
(n)j,n
Ajj,o = j,o
et donc :
Ao(Ajj,o) = Aoj,o (95)
Ce qui justifie quen reconstruisant partir dun Dirac et avec des dtails nuls on
obtienne une approximation lchelle 0 de la fonction dchelle j,o.
De mme, en prenant f = j,o, on aura djn = (n) et a
jn = 0 :
Djj,o =+
n=(n)j,n (4.96)
=
+n= (n)
j,n
Djj,o = j,o
Ao(Djj,o) = Aoj,o (97)
On retrouve lalgorithme cascade pour londelette.
7/29/2019 75514306 Ondelettes Hermes
53/158
Chapitre 5
Proprits et construction
Nous allons, dans ce paragraphe, tudier les proprits de h[n], g[n], et pour en dduire les rgles de construction des bases dondelettes et de fonctions
dchelle et des filtres associs une analyse multirsolution. Jusqu prsent, seuls
des cas pathologiques et sans intrt pratique de base orthonorme dondelettes
non associe une analyse multirsolution (au sens prsent ici) ont pu tre mis
en vidence. Nous admettrons donc que base orthonorme dondelettes et analyse
multirsolution vont ensemble. Nous verrons que la construction commence, engnral, par le choix de la fonction dchelle (ou du filtre numrique associ) et que le
reste peut tre dduit. Cela peut tre droutant pour ceux qui voudraient commencer
par ce qui semblerait le plus naturel savoir la famille dondelettes ; en fait dans ce
cas le cheminement est plus complexe et le rsultat moins assur. Et dailleurs les
contraintes pesant sur les fonctions dchelles sont moins fortes car elles nont tre
orthogonales entre elles qu lintrieur dune mme chelle (rsolution j) alors queles ondelettes doivent former une base orthonorme globale et tre orthogonales
travers les chelles aussi bien que pour une chelle donne.
Les proprits des fonctions de base et des filtres associs qui sont donnes dans ce
paragraphe sont lies lorthogonalit des bases. Les respecter lors de la construction
dune analyse multirsolution ne garantit pas la convergence de lalgorithme quil
convient de vrifier par ailleurs. Un bon test est fourni par la formule de rcurrence
de lquation 5.6 ou encore par lalgorithme cascade de construction de la fonction
dchelle du paragraphe 4.3.
7/29/2019 75514306 Ondelettes Hermes
54/158
54 Ondelettes pour le signal numrique
5.1 Proprits frquentielles de la fonction dchelle
5.1.1 Relations avec le filtre associ
Nous avons vu que la suite numrique h[n] pouvait tre considre comme la rponseimpulsionnelle dun filtre numrique. La rponse frquentielle de ce filtre est obtenue
en exprimant la transforme de Fourier de cette suite. Cette transforme, comme toutes
les rponses frquentielles des filtres numriques est priodique de priode 2 ; ellescrit comme suit :
h() =
nh[n]ein (1)
Or la fonction dchelle (x) peut sexprimer en fonction de hpar lquation 4.28,qui peut scrire :
(x) =n
h[n]
2(2x n) (2)
Si on prend la transforme de Fourier de cette relation et si on utilise les proprits
de cette transforme concernant la translation et le changement dchelle4, on obtient :
() = n h[n]
21
2(
2
)ein2 (3)
ce qui, en regroupant les termes :
() = 12(
2)n
h[n]ein2 (4)
fait apparatre la rponse frquentielle du filtre numrique exprime en /2, soit larelation suivante :
() =
12
h(
2)
(
2) (5)
cette relation, trs importante en pratique, exprime simplement la projection de lafonction dchelle sur la rsolution infrieure dans lespace de Fourier. En notant
4 La transforme dune fonction dilate est donne par : f(ax) 1|a|f(
a).
La transforme dune fonction translate est donne par : f(xn) f()ein.
7/29/2019 75514306 Ondelettes Hermes
55/158
Proprits et construction 55
par anticipation que (0) = 0 (voir quation 5.28), on peut dailleurs ltendrepar rcurrence pour obtenir une relation entre la fonction dchelle et la rponse
frquentielle du filtre numrique associ :
() = j=1
12h(
2j) (6)
La construction de la fonction dchelle (dans lespace de Fourier) convergera si le
filtre h[n] choisi conduit une analyse multirsolution de L2.
5.1.2 Orthonormalit dans Fourier
Voyons tout dabord une consquence de la formule de Poisson :n
(t nT)fourier
2
T
n
( n 2T
) (7)
Si on considre une fonction (t) de L2(R) engendrant par translation une familleorthonorme, et donc telle que :
(t), (t + n) = (n) n Z (8)ce produit scalaire est lchantillonn de la fonction dautocorrlation de (t) en effet,cette fonction dautocorrlation scrit :
r() =
(t)(t + )dt = (t), (t + ) (9)
La transforme de Fourier de cette fonction dautocorrlation scrit :
r() =()() = |()|2 (10)La version chantillonne de cette fonction sera note re(). On aura :
re() = r() k
( k) (11)
on peut calculer la transforme de Fourier de cette expression en utilisant le thorme
de Plancherel pour faire apparatre un produit de convolution et en estimant la
transforme du peigne de Dirac par la formule de Poisson (quation 5.7) :
re() = 12r() 2
n
( n2) (12)
7/29/2019 75514306 Ondelettes Hermes
56/158
56 Ondelettes pour le signal numrique
Ce qui scrit galement :
re() = n
r( 2n) (13)En remplaant la transforme de la fonction dautocorrlation par son expression
en fonction de () (quation 5.10) et en crivant que la transforme dun Diracest lunit, on obtient lexpression 5.14 qui exprime lorthonormalit de la fonction
dchelle dans Fourier. n
|
( + 2n)|2 = 1 (14)
Cette relation est fondamentale si le choix de la fonction dchelle est men dansFourier ; elle permet dassurer lorthonormalit de la base choisie. Elle est galement
trs utilise pour la construction du filtre numrique associ. Elle se traduit dailleurs,
comme nous allons le voir maintenant, par une propritgalement fondamentalepour
ce filtre.
On peut reporter ce rsultat dans lquation 5.5 exprime la pulsationdouble pour
obtenir la contrainte qui dcoule de cette orthonormalit sur la rponse frquentielle
du filtre numrique associ :n
|
(2 + 2n)|2 =
n
1
2|
( + n)|2
h( + n)
2
= 1 (15)
Si on spare dans la sommation les termes correspondant aux indices pairs des
impairs :
12
n
h( + 2n)2 |( + 2n)|2 +12
n
h( + (2n + 1))2 |( + (2n + 1))|2 = 1 (16)et si on utilise la priodicit deh() :h()
2
n1
2|
( + 2n)|2 +
h( + )
2
n1
2|
( + + 2n)|2 = 1 (17)
En utilisant la proprit 5.14 pour les deux termes, on obtient la contrainte
correspondant lorthonormalit de la fonction dchelle sur la rponse frquentielle
du filtre numrique : h()2 + h( + )2 = 2 (18)
7/29/2019 75514306 Ondelettes Hermes
57/158
Proprits et construction 57
Ce rsultat va nous permettre de prciser la signification physique du filtre h[n].Mais nous devons tout dabord admettre par avance que la fonction dchelle nest pas
moyenne nulle. On peut, pour sen convaincre, rflchir lanalyse multirsolution
de la fonction unit, ou se reporter simplement la relation 5.28.+
(x)dx = 0 (0) = 0 (19)Ce rsultat est bien entendu li au fait que la fonction dchelle permet de lisser le
signal lors du passage dune rsolution fine une rsolution plus grossire.
Dans ces conditions lexpression 5.5 conduit :
h( 2
) =
2()(2 ) (20)
Si on applique ce rsultat en 0 puis si on le combine avec 5.18 en , on obtient : h(0) = n h[n] = 2h() = 0 (21)On pourra donc admettre que le filtre h est de la famille des filtres passe-bas ce
qui correspond bien lide intuitive que lon a du passage une approximation
grossire du signal par limination des dtails donc des hautes frquences.
Remarque 5 La relation qui est caractristique de lorthonormalit des fonctions
dchelle pour une rsolution donne a son quivalent en ce qui concerne le filtre
passe-bas associ. En effet, si on reprend lquation qui exprime cette proprit :
(t), (t + n) = (n) n Z (22)en remplaant(t) par son expression :
(t) =n
h[n]
2(2t n) (23)
on montre aisment que la rponse impulsionnelle du filtre doit obir la relation
suivante 5.24 : k
h [k] h [2n + k] = [n] (24)
qui est lquivalente pour le filtre de 5.22. Malheureusement la contrainte exprime
par cette relation est difficilement utilisable dans la pratique pour construire un filtre
et donc une analyse multirsolution associe.
7/29/2019 75514306 Ondelettes Hermes
58/158
58 Ondelettes pour le signal numrique
Lexpression 5.5 va nous permettre dtre plus prcis en ce qui concerne les
proprits de la fonction dchelle, en particulier en ce qui concerne sa valeur
moyenne. En effet si on applique cette relation pour = 2n on obtient :
(2n) = 12(n)h(n) (25)
Cette expression est nulle pourn impair ( cause de la proprit 5.21 du filtre) cequi permet, par rcursivit, de sapercevoir que tous les termes correspondant n = 0sont nuls galement :
(2n) = 0 n = 0 (26)
En appliquant la relation 5.14 en = 0 on vrifie que :
|(0)| = 1 (27)Si on choisit la fonction dchelle telle que sa valeur moyenne soit relle et positive,
ce qui ne doit pas restreindre beaucoup la gnralit du problme, on obtient la
contrainte suivante :
(0) = +
(x)dx = 1 (28)
5.2 Proprits frquentielles de londelette
Nous allons examiner, pour la fonction dondelette (x) et son filtre numriqueassoci g[n], les proprits quivalentes celles trouves prcdemment. Cesproprits devraient tre plus contraignantes car les fonctions dondelette forment une
base orthonorme travers les rsolutions, alors que les fonctions dchelle ne sont
orthogonales qu lintrieur dune chelle donne.
La fonction dondelette se dcompose lchelle infrieure sur la base des
fonctions dchelle, les coefficients de la dcomposition sont les coefficients du filtre
numrique associ :
(x) = n g[n]
2(2x n) (29)
Si on transforme cette expression dans Fourier on obtient la relation suivante :
() = 12g(
2)(
2) (30)
7/29/2019 75514306 Ondelettes Hermes
59/158
Proprits et construction 59
Lorthonormalit des ondelettes vis vis de la translation conduit une relation
analogue 5.14 : n
( + 2n)2 = 1 (31)Ce qui, avec le mme traitement que prcdemment, implique pour le filtre g[n] la
proprit suivante :
|g()|2 + |g( + )|2 = 2 (32)Pour construire le filtre et londelette, nous avons besoin dune relation
supplmentaire qui va nous tre fournie par la traduction dans Fourier delorthogonalit de avec :
, 0,k
= 0 , k Z (33)
Ou, en exprimant le produit scalaire :+
(x)(x + k)dx = 0 (34)
Remarque 6 Cette relation associe avec la dcomposition de londelette sur la
base chelle la rsolution infrieure contient la proprit dorthogonalit de la
famille des fonctions dondelette travers les chelles.
On trouve facilement la relation correspondante dans Fourier si on considre
(comme prcdemment) que ce calcul correspond lchantillonnage de la fonction
dintercorrlation entre et .n
( + 2n) ( + 2n) = 0 (35)Cette relation applique en = 0 et en utilisant la proprit 5.28 implique que :
(0) = +
(x)dx = 0 (36)
Contrairement la fonction dchelle, la fonction dondelette est moyenne nullece qui en fait dailleurs une ondelette admissible.
Si on combine ce rsultat avec 5.30 et avec 5.32 on en dduit que : g(0) = n g[n] = 0|g()| = 2 (37)
7/29/2019 75514306 Ondelettes Hermes
60/158
60 Ondelettes pour le signal numrique
Ce qui semblerait indiquer quon est en prsence dun filtre passe-haut.
Si dans la relation 5.35 on remplace et par les expressions dduites de 5.5 et5.30 on obtient :
n
g( 2
+ n)( 2
+ n) h( 2
+ n)( 2
+ n) = 0 (38)
Do en sparant les indices pairs et impairs :
ng(2 + 2n)
h(2 + 2n) (2 + n)
2+
ng(2 + (2n + 1))h(2 + (2n + 1)) (2 + (2n + 1))2 = 0Si on utilise la priodicit des transformes de Fourier des filtres numriques et la
proprit 5.14 on obtient la relation suivante :
g()h() +g( + )h( + ) = 0 (39)Linterprtation de ce rsultat est un peu dlicate mais cest la clef qui permet de
construire le filtre g si on a dj choisi la fonction dchelle et donc le filtre h.
On peut, tout dabord, dduire une relation entre les modules des rponses
frquentielles des filtres ; en effet, lquation 5.39 implique que :
|g()|2 h()2 = |g( + )|2 h( + )2 (40)Si on combine cette relation avec 5.32 et 5.18, on obtient :
|g()|2 h()2 = 2 |g()|22 h()2 (41)Do en simplifiant :
|g()|2
+ h()2
= 2 (42)
Dautre part, sih() = 0 on peut dduire de lquation 5.39 :g() = g( + )h()h( + ) (43)
7/29/2019 75514306 Ondelettes Hermes
61/158
Proprits et construction 61
Dans le cas contraire, h( + ) = 2 et doncg( + ) = 0 donc |g()| = 2ou encore : |g()| = h( + ). Dans tous les cas, on peut donc crire :
g() = () h( + ) (44)avec les conditions suivantes sur la fonction() :
() est 2 priodique() +( + ) = 0()
= 1
(45)
Les deux dernires conditions se dduisent des relations 5.39 et 5.42.
La fonction() doit donc tre choisie sur le cercle unit et doit respecter certainesconditions de symtrie ; le choix est loin dtre unique, mais on sen tient souvent au
cas o la linarit en phase est prserve. Dans cette hypothse et en labsence de
contrainte supplmentaire, le choix le plus simple est :() = ei, ce qui donne :g() = ei h( + ) (46)
Si on revient dans lespace habituel pour obtenir une relation entre les rponses
impulsionnelles :
g() = n
g[n]ein
= n
ei
h[n]ein(+)
(47)
donc : n
g[n]ein = n
h[n]ei einein (5.48)
= n
(1)nh[n]ei(n+1)
= n
(1)n1h[1 n]ein
Ce qui implique :
g[n] = (1)nh[1 n] (49)
On obtient bien une relation qui permet de construire le filtre g en connaissant h, ilne faut cependant pas oublier que cette solution est loin dtre unique et que dautres
choix pour la fonction() sont possibles si besoin.
7/29/2019 75514306 Ondelettes Hermes
62/158
62 Ondelettes pour le signal numrique
Il est parfois plus intressant dexprimer ce rsultat dans lespace des transformes
en z, en particulier si les filtres sont susceptibles de mises en uvre rcursives. Le
rsultat peut tre obtenu en remplaant simplement eiparz dans lquation 5.46 :
G(z) = z1H(1z
) (50)
Remarque 7 La relation 5.46 entre les filtres associs lanalyse multirsolution
permet de trouver une relation entre londelette et la fonction dchelle. En effet, si on
remplace dans 5.30g(2 ) par son expression dduite de 5.46, on obtient :
() = ei2 1
2h(
2+ )
(
2)
et en utilisant 5.5 pour exprimerh(2 + ) en fonction de on obtient :() = ei2( + 2)(2 + ) ( 2 )
Cette relation ne semble malheureusement pas utilisable pour dterminer une fonction
dchelle partir dune ondelette.
5.3 Rsum des proprits
Le tableau ci-aprs rsume les principales proprits prsentes dans ce chapitre. Ces
proprits sont utilises dans la construction des bases orthonormes dondelettesassocies des analyses multirsolutions.
On construira, en gnral, une telle analyse multirsolution en suivant lune des
deux dmarches suivantes :
a - On commence par choisir une famille de bases orthonormes de fonctions
dchelle, lorthogonalisation peut tre faite en utilisant le truc utilis pour les bases
spline (voir chapitre 6). On dtermine ensuite le filtre h associ par projection de lafonction dchelle sur la base de rsolution immdiatement plus fine. On vrifie, en
utilisant lalgorithme cascade, que la convergence de lanalyse est correcte. Puis il
reste dfinir le filtre g partir du filtre h et construire laide de lalgorithmecascade la fonction dondelette associe.
b - On choisit un filtre numrique h, passe-bas, ayant la proprit dorthogonalit,vrifie dans Fourier ou dans lespace direct ; puis on sassure, laide de lalgorithme
cascade, que lanalyse converge bien et que la fonction dchelle a des proprits de
compacit et de rgularit correctes. On peut, ensuite, construire le filtre g partir dufiltre h et en dduire par lalgorithme cascade la fonction dondelette associe. Dansune variante de cette mthode, on peut commencer par choisir un filtre numrique
7/29/2019 75514306 Ondelettes Hermes
63/158
Proprits et construction 63
passe-haut qui sera le filtre g puis, aprs vrification de la convergence et des bonnesproprits de la fonction dondelette associe, on pourra en dduire le filtre h et lafonction dchelle correspondante.
Dans les deux cas, on constate que la fonction dondelette est dtermine en
dernier, ce qui ne correspond pas lapproche la plus naturelle. Il est, en gnral, trs
difficile de faire autrement et le choix a priori dune base dondelettes nest pas la
mthode la plus directe pour construire une transformation en ondelettes discrte!
Rsum des principales proprits des fonctions et des filtres associs
une analyse multirsolution orthogonale
(t), (t + n) = (n) n Z (t), (t + n) = 0 n Z
(t), (t + n) = (n) n Z
() = 12h(2 )(2 ) () = 12g(2 )(2 )
n |( + 2n)|2 = 1 n ( + 2n)2 = 1
|
(0)| = 1(0) = 0
n( + 2n) ( + 2n) = 0 g()h() +g( + )h( + ) = 0
k h [k] h [2n + k] = [n]k |h [k]|2 =
k |g [k]|2 = 1h()2 + h( + )2 = 2 |g()|2 + |g( + )|2 = 2
h()2 + |g()|2 = 2
h(0) =
n h[n] =
2
h() = 0 g(0) =
n g[n] = 0
|g()| =
2
g() = () h( + )() est 2 priodique() +( + ) = 0() = 1
7/29/2019 75514306 Ondelettes Hermes
64/158
64 Ondelettes pour le signal numrique
Et on peut choisir le filtre g suivant :g() = ei h( + ) soit : g[n] = (1)nh[1 n]Remarque 8 Les paires de filtres numriques relis par cette relation sont parfois
appels filtres miroirs en quadrature : QMF. Ils jouent un rle majeur dans la thorie
de la dcomposition des signaux en sous-bandes. Cela tant, pour quune telle paire
de filtres soit lorigine dune analyse multirsolution au sens dfini prcdemment,
dautres proprits doivent tre vrifies(en particulier la convergence de lalgorithme
rcursif). Nous ntudierons pas ici ce problme et laisserons le lecteur consulter
labondante littrature existant ce sujet [43].
Exemple 5 Nous verrons comment on peut utiliser les proprits prcdentes pourretrouver les lments de lanalyse multirsolution de Haar. Mais nous rservons
cette prsentation dexemples un chapitre entier, ce qui nous permettra une plus large
perspective.
.
7/29/2019 75514306 Ondelettes Hermes
65/158
Chapitre 6
Exemples de bases dondelettes
Nous allons, dans ce chapitre, prsenter quelques exemples de bases dondelettes
orthonormes choisis parmi les plus populaires. Nous commencerons par la base la
plus simple que nous avons dj utilise plusieurs fois comme illustration, lanalyse
de Haar ; nous continuerons par une base que lon pourrait qualifier de duale de la
prcdente, savoir la base des ondelettes de Littlewood-Paley. Nous prsenterons
ensuite une famille choisie parmi celles qui sont les plus utilises dans la pratique,
la famille des bases construites partir de fonctions splines. Toutes ces analysescorrespondent des filtres linaires en phase qui ont donc des proprits de symtrie
apprcies en traitement des images (isotropie gauche-droite) ; malheureusement ces
filtres ( part ceux lis lanalyse de Haar) sont de rponse impulsionnelle infinie
(RII) donc de mise en uvre souvent coteuse. Nous prsenterons donc, pour clore
ce chapitre, les bases construites par I. Daubechies qui conduisent des filtres
rponse impulsionnelle finie (RIF) mais qui ne sont pas linaires en phase. Nous
verrons, dans un chapitre ultrieur (chapitre 8) comment, en relchant un peu la
contrainte dorthogonalit, on peut construire des bases dondelettes non-redondantes
conduisant des filtres linaires en phase et rponse impulsionnelle finie ; il sagit des
bases biorthogonales. Pour complter ce panorama,on pourra trouver une prsentation
relativement complte des bases dondelettes utilises ou utilisables pour des analyses
multirsolution dans [1].
7/29/2019 75514306 Ondelettes Hermes
66/158
66 Ondelettes pour le signal numrique
6.1 Ondelettes de Haar
Nous prendrons comme point de dpart de la construction la fonction de Haar utilise
comme mre des fonctions dchelle :
(t) =
1 0 t < 10 sinon
(1)
Nous avons vu que cette fonction pouvait se dcomposer sur les fonctions de
rsolution infrieure suivant :
(t) = (2t) + (2t 1) (2)
Si on calcule la transforme de Fourier de cette expression, on obtient :
() =( 2
)1 + ei
2
2(3)
Si on compare ce rsultat lexpression 5.5 dmontre au chapitre prcdent, on
peut en dduire par simple identification lexpression de la rponse frquentielle du
filtre h associ :
h() = 12
(1 + ei) (4)
La fonction de transfert du filtre scrit donc :
H(z) =1
2(1 + z1) (5)
Si on dtermine le filtre g en utilisant la proprit des filtres miroirs en quadrature
(quation 5.46) on obtient :
G(z) =1
2(1 z1) (6)
Ces deux filtres correspondent exactement ceux trouvs lors des prsentations
prcdentes de cette analyse multirsolution. Si on applique la proprit 5.30, on
7/29/2019 75514306 Ondelettes Hermes
67/158
Exemples de bases dondelettes 67
obtient la fonction dondelette par sa transforme de Fourier :
() = 12
(1 ei2 )( 2
) (7)
Soit :
(t) = (2t) (2t 1) (8)
Ce qui correspond la fonction :
(t) = 1 0 t 3 et le calcul des zros de P(y) doit tre fait laide dune mthode
numrique (voir par exemple la mthode de Bairstow). Pour des valeurs leves de N,la prcision des calculs peut poser problme et lorthonormalit des bases obtenues
peut alors ntre quapproximative.
Les fonctions dchelle correspondantes sont construites par lalgorithme cascade,
nous donnons quelques exemples de ces fonctions et de leur tendue spectrale (voir
figures du tableau 6.). On constate que lorsque lordre des polynmes augmente, la
fonction dchelle gagne en rgularit et voit son tendue spectrale diminuer ; cette
volution apparat de la mme faon pour les ondelettes. Elle se paie, videmment,
par lallongement des filtres associs.
7/29/2019 75514306 Ondelettes Hermes
84/158
84 Ondelettes pour le signal numrique
N 1 2 3
2 1, 93185165258 2, 6613644236
0, 517638090205 1, 528961196310, 281810335086
N 4 5 6
3, 68604501294 5, 12327673517 7, 138607574413, 30663492292 6, 29384704236 11, 17571646091, 20436190091 3, 41434077007 8, 047755262890, 169558428561 0, 936300109646 3, 24691364198
0, 106743209135 0, 7194280974590, 0689472694597
N 7 8 9
9, 96506292288 13, 9304556142 19, 495909050318, 9984075665 31, 3485176398 50, 619828051117, 0514392132 33, 6968524121 63, 39516597839, 03858510919 22, 07104076339 49, 36754822812, 93696631047 0, 38930245651 25, 86003633190, 547537574895 2, 56627196249 9, 2449158877550, 0452753663967 0, 413507501939 2, 18556614566
0, 0300740567359 0, 3103176047560, 0201458280019
Tableau 6. Coefficients HN(z) pour les filtres de Daubechies
7/29/2019 75514306 Ondelettes Hermes
85/158
Exemples de bases dondelettes 85
Tableau 6. Fonctions dchelle Daubechies et leurs spectres (N=2 5)
7/29/2019 75514306 Ondelettes Hermes
86/158
7/29/2019 75514306 Ondelettes Hermes
87/158
Chapitre 7
Passage deux dimensions
7.1 Cas gnral
Nous allons examiner dans ce chapitre comment les principes de lanalyse
multirsolution monodimensionnelle prsents prcdemment peuvent tre tendus
aux signaux multidimensionnels. Nous nous intresserons plus spcialement au cas
des signaux deux dimensions que nous assimilerons dans la pratique des imagesunimodales. Lanalyse des signaux multispectraux est un autre problme que nous
nenvisagerons pas ici. Cela tant, les proprits et dfinitions donnes dans le premier
paragraphe de ce chapitre sont valablesquelle que soit la dimension de lespace auquel
appartiennent les fonctions (2D, 3D et au-del).
Les fonctions que nous voulons traiter seront de carr intgrable surRN, donc les
signaux appartiendront L2(RN) (N = 2 dans le cas des signaux 2D).
7.1.1 Matrice de changement dchelle
Les sous-espaces Vj doivent tre tendus NDimensions et le facteur de dilatationou dchelle discret j deviendra une matrice de dilatation ou dchelle permettant depasser dune rsolution la suivante (exemple en 2D) :
x
y
= J
xy
(1)
J sera donc une matrice carre de dimension N N (soit 2 2 2D) soumise un certain nombre de contraintes ; il faudra en particulier que le dilat dun vecteur
7/29/2019 75514306 Ondelettes Hermes
88/158
88 Ondelettes pour le signal numrique
dentiers soit un vecteur dentiers6. On aura donc dans le cas 2D :xy
Z2 =
x
y
Z2
Une consquence est que la matrice J doit avoir des coefficients entiers et il en
sera de mme pour|det J| J1.La matrice doit assurer une dilatation suivant chaque
Recommended