Analyse multi-échelle

Principes et applications
Marco Cagnazzo,
cagnazzo@[Link]

IMA 201
 Introduction
Ondelettes
Applications

Outline

Introduction

Transformée en ondelettes

Applications

2/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Représentation des images numériques

! Grille discrète, image N × M pixels
! A chaque pixel (n, m), on associe un ordre de traitement k
! Généralement, balayage ligne par ligne unilatéral :
k = (n − 1)M + m
! On notera indifféremment fn,m ou fk
! Images en niveaux de gris
m M

n
fn,m = fk
N

3/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Transformations linéaires

Rappel : Cas 1D
Dans le cas 1-D, une transformée linéaire est un produit
matriciel. Soit f ∈ CN1 le vecteur d’entrée. En général, le
résultat de la transformée est un vecteur g ∈ CN2 tel que :
N1
!
g = Tf gk = Tk ,n fn
n=1

Dans la majorité des cas, nous nous intéressons au cas

N1 = N2 = N. La transformée est entièrement définie par la
matrice carrée T ∈ CN×N
Comment étendre cette définition au cas 2D ?

4/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Transformations linéaires en 2D : forme

scalaire
Soit F une image (ou un bloc de pixels) de taille N × M. Une
transformée de F est une image G de taille N × M telle que
chaque gk ,! soit une combinaison linéaire des éléments de F :
N !
! M
gk ,! = t(k, !, n, m)fn,m (1)
n=1 m=1

Une transformée 2D est alors complètement définie par le

tenseur t:
t : (k, !, n, m) → C
k ∈ 1, . . . , N ! ∈ 1, . . . , M
n ∈ 1, . . . , N m ∈ 1, . . . , M

5/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Transformations linéaires en 2D : forme

vectorielle
Une transformée 2D peut toujours s’écrire comme un produit matriciel. Il
suffit d’introduire la forme vectorielle des images.
Soient F, G et t liées par l’équation (1). On introduit x, y ∈ CNM×1 :
x = [f1,1 , f2,1 , . . . , fN,1 , f1,2 , f2,2 , . . . , fN,2 , f1,M , f2,M , . . . , fN,M ]T
y = [g1,1 , g2,1 , . . . , gN,1 , g1,2 , g2,2 , . . . , gN,2 , g1,M , g2,M , . . . , gN,M ]T
Chaque élément de y est une combinaison linéaire d’éléments de x, donc :
y = Tx

Après de calculs banals mais laborieux, on peut trouver :

Ti,j = t [r (j), c(j), r (i), c(i)]

! " ! "
j −1 j −1
r (j) = j − N c(j) = N +1
N N
La transformée est alors complètement définie par la matrice T ∈ CNM×NM
6/78 23.10.20 Une école de l’IMT Analyse multi-échelle
 Introduction
Ondelettes
Applications

Transformée inverse

On considère des transformées inversibles, c’est-à-dire telles

que T soit inversible. Dans ce cas :

x = T−1 y

Il est évident que dans ce cas, il existe un tenseur t # tel que :

N !
! M
fn,m = t # (n, m, k, !)gk ,!
k =1 !=1

La relation entre t # et T−1 est similaire à celle entre t et T

7/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Transformations linéaires en 2D : forme

matricielle
Étant donné que :
N !
! M
gk ,! = t(k , !, n, m)f (n, m)
n=1 m=1

si on définit :
" #
t(k , !, 1, 1) . . . t(k , !, 1, M)
[τk ,! ] =
t(k , !, N, 1) . . . t(k , !, N, M)

alors :
!
gk ,! = τk ,! (n, m)f (n, m)
n,m

Donc gk ,! représente le produit scalaire (le dégrée de similitude)

entre l’image f et l’image de base [τk ,! ]
8/78 23.10.20 Une école de l’IMT Analyse multi-échelle
 Introduction
Ondelettes
Applications

Transformée inverse : forme matricielle

On définit :
" #
t # (1, 1, k, !) . . . t # (1, M, k, !)
[τ # k ,! ] =
t # (N, 1, k, !) . . . t # (N, M, k, !)

Alors on trouve :
!
F= gk ,! τk# ,!
k ,!

Les gk ,! donnent les poids des différents contributions [τk# ,! ] à

l’image F.
Pour une transformée orthogonale, [τk ,! ] = [τk# ,! ]

9/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Transformée en forme matricielle : exemple

τk ,!

10/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Transformations linéaires en 2D
Propriétés

! Transformée unitaire :

T−1 = TH

! Unitaire et réelle (orthogonale) :

T−1 = TT

! Séparable :

t(k, !, n, m) = t1 (k, n)t2 (!, m)

! Séparable et symétrique : M = N et

t(k, !, n, m) = t(k, n)t(!, m)

11/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Transformée séparable
Si t(k , !, n, m) = t1 (k , n)t2 (!, m), ils existent deux matrices T1 et T2
telles que :
G = T1 FTT2
Démonstration.
N
!
H = T1 F ⇒ hp,q = T1 (p, n)f (n, q)
n=1
M
!
E = HTT2 ⇒ ek ,! = h(k , m)T2 (!, m)
m=1
N !
! M
ek ,! = T1 (k , n)f (n, m)T2 (!, m)
n=1 m=1

Donc, si T1 (k , !) = t1 (k , !) et T2 (k , !) = t2 (k , !), alors G = E CQFD.

12/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Transformée séparable : interprétation

G = T1 FTT2
$ %T
= T1 T2 FT
& 'T
= T2 (T1 F)T

Appliquer une transformée 2D séparable est équivalent à :

! appliquer d’abord la transformée 1D T2 sur les lignes de F
et ensuite la transformée 1D T1 sur les colonnes ;
! ou alors à appliquer d’abord T1 sur les colonnes de F et
ensuite T2 sur les lignes

13/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Transformée séparable et symétrique

Si N = M et t1 = t2 = t alors t(k , !, n, m) = t(k , n)t(!, m) et

T1 = T2 = C avec Ci,j = t(i, j)
Autrement dit, si on applique la transformée 1D C sur les lignes et sur
les colonnes de F, on est en train de calculer une transformée 2D
séparable et symétrique :
!
G = CFCT gk ,! = C(k , n)C(!, m)fn,m
n,m

La transformée 2D est alors complètement caractérisée par la

matrice C ∈ CN×N
On peut prouver que T est inversible [orthogonale] si et seulement si
C l’est.
Les transformées les plus intéressantes sont réelles,
séparables, symétriques et orthogonales

14/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Idées clés

! On peut étendre ce que l’on sait sur les transformées 1-D

en 2-D
! Transformée directe : analyse
! Transformée inverse : synthèse
! Coefficients : mesurent la corrélation avec fonction
d’analyse
! Unicité de la décomposition
! Représentation du signal sur un même nombre
d’éléments: les coefficients de la décomposition
! Reconstruction : utiliser la base pour décrire le signal
(synthèse)

15/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

L’analyse des signaux

! Analyse: similitude à des “atomes” φn [k]

! Similitude : produit scalaire
!
c[k] = x[n]φn [k]
n

! Projection sur un ensemble de signaux

! Changement de base
! Transformée linéaire

16/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

fréquence L’analyse des signaux

φn [k] = δ[n − k]
temps
Analyse temporelle

17/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

fréquence L’analyse des signaux

k
φn [k] = e−j2π N n

temps
Analyse en fréquence

18/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

fréquence L’analyse des signaux

k
φn,t [k] = e−j2π N n wt [k]

temps
Analyse temps-fréquence

19/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

fréquence L’analyse des signaux

φn,a [k] = φ(2−a k − n)

temps
TO
20/78 23.10.20 Une école de l’IMT Analyse multi-échelle
 Introduction
Ondelettes
Applications

Outline

Introduction

Transformée en ondelettes

Applications

21/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Ondelettes et images : Motivations

! Modèle d’images : trends + anomalies

22/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Ondelettes et images : Motivations

! Modèle d’images : trends + anomalies

22/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Ondelettes et images : Motivations

! Modèle d’images : trends + anomalies

22/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Ondelettes et images : Motivations

! Anomalies :
! Variations soudaines du signal, sur une courte durée
! Contributions aux hautes fréquences
! Contours des objets
! Bonne résolution spatiale
! Résolution en fréquence grossière
! Trends :
! Variations lentes du signal, sur une longue durée
! Contributions aux baisses fréquences
! Intérieur des objets
! Résolution spatiale grossière
! Bonne résolution en fréquence

23/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Ondelettes et images : Motivations

Modèle du signal : une ligne d’une image

24/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Ondelettes et images : Motivations

Modèle du signal : une ligne d’une image

24/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Ondelettes et images : Motivations

Modèle du signal : une ligne d’une image

24/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Ondelettes et analyse à résolutions

multiples
! Approximation : version à baisse résolution
! “Détails” : nuls pour un signal polynomial
60

x[k] = c0 [k]
40

20

−20
0 50 100 150 200 250 300 350 400 450 500

80
c1 [k] d1 [k]
60

40

20

−20
0 50 100 150 200 250 300 350 400 450 500

25/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Bancs de filtres 1D
Décomposition

č[k] c[k]
h ↓2

x[k]

ď[k] d [k]
g ↓2

Banc de filtres d’analyse

2 ↓ : opérateur de décimation : c[k] = č[2k]

26/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Reconstruction
ĉ[k]
c[k]
↑2 h̃

x̃ [k]

d̂[k]
d [k] ↑2 g̃

Banc de filtres de synthèse

2 ↑ : opérateur d’interpolation, multiplie le nombre

d’échantillons par 2
(
c[k/2] si k est pair
ĉ[k] =
0 si k est impair
27/78 23.10.20 Une école de l’IMT Analyse multi-échelle
 Introduction
Ondelettes
Applications

Propriétés des filtres

! Reconstruction parfaite
! RIF
! Orthogonalité
! Moments nuls
! Symétrie

28/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Conditions de reconstruction parfaite

En cascadant bancs de filtres d’analyse et de synthèse, on veut

la reconstruction parfaite (RP), c’est-à-dire, ∀k ∈ Z,
) (z) = z −! X (z)
x)k = xk +! ⇐⇒ X

č[k] c[k] ĉ[k]

h ↓2 ↑2 h̃

x[k] x̃ [k]

ď[k] d [k] d̂[k]

g ↓2 ↑2 g̃

29/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Relations dans le domaine Z

!
∞
filtre Č (z) = čn z −n = H (z) X (z)
n=−∞
1 & $ 1/2 % $ %'
décimateur C (z) = Č z + Č −z 1/2
2
* +
interpolateur Ĉ (z) = C z 2
* + * +
sortie ) (z) = H
X ) (z) D z 2
) (z) C z 2 + G

& '
) (z) = 1 H
X ) (z) G (z) X (z)
) (z) H (z) + G
2
1 &) '
) (z) G (−z) X (−z)
+ H (z) H (−z) + G
2

30/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Conditions de reconstruction parfaite

En cascadant bancs de filtres d’analyse et de synthèse, on veut

la reconstruction parfaite (RP), c’est-à-dire, ∀k ∈ Z,
) (z) = z −! X (z)
x)k = xk +! ⇐⇒ X

H ) (z) G (z) = 2z −!
) (z) H (z) + G Non distorsion
) (z) H (−z) + G
H ) (z) G (−z) = 0 Non aliasing

31/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Conditions de reconstruction parfaite

Forme matricielle
Si les filtres d’analyse sont fixés, les filtres de synthèse sont
univoquement déterminés :
" # ,) - " #
H (z) G (z) H (z) 2z −!
· ) =
H (−z) G (−z) G (z) 0

On assume que la matrice de modulation soit inversible.

32/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Conditions de reconstruction parfaite

Filtres de synthèse
Déterminant de la matrice de modulation :

∆ (z) = H (z) G (−z) − G (z) H (−z)

−!
) (z) = 2z G (−z)
H
∆ (z)
−!
) (z) = − 2z H (−z)
G
∆ (z)

33/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Reconstruction parfaite avec filtres RIF

Filtres à réponse impulsionnelle finie:

On peut montrer que dans ce cas la condition de non aliasing
est équivalente à imposer la condition de signes alternés pour
les filtres.
Exemple:

h(k) = a b c )
h(k) = p -q r -s t
g(k) = p q r s t )(k) = -a
g b -c

34/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Orthogonalité

L’orthogonalité assure la conservation de l’énergie :

!
∞
2
!
∞
2
!
∞
2
(xk ) = (ck ) + (dk )
k =−∞ k =−∞ k =−∞

⇒ énergie de l’erreur sur les coefficients = énergie de l’erreur sur le

signal
! Erreur de quantification
! Bruit

35/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Moments nuls

! Le moments nuls (MN) représentent la capacité du filtre à

reconstruire les polynômes
! Un filtre avec p MN peut représenter des polynômes de
degré strictement inférieur à p
! Si l’entrée du banc est un polynôme de grade au plus p − 1
la sortie du filtre passe haut est strictement nulle
! Alors toute l’information est représentée avec la moitié des
échantillons (signal d’approximation)
! Un filtre avec p MN a un support non inférieur à 2p

36/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Problème des bords

! Les propriétés des bancs de filtres telles qu’on les a vues

sont valables pour signaux de durée infinie
! Pour éviter d’augmenter le nombre de coefficients, un
signal fini est périodisé avant d’entrer dans le banc
d’analyse
! Le résultat est périodique de la même période
! Une période suffit pour effectuer la synthèse
! Création de sauts (effet de bord)

37/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Symétrie

! Pour éviter de créer des coefficients à haute fréquence, on

peut penser à symétriser le signal avant de le périodiser
(comme pour la TCD)
! Mais on double le nombre de coefficients
! À moins que les filtres ne soient symétriques
! Dans ce cas le résultat du filtrage est une suite symétrique
et périodique : une demi-période suffit pour la
reconstruction
! Contrainte supplémentaire sur les filtres

38/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Problème des bords

x h

16
14 0.8
12
0.6
10
8 0.4
6
0.2
4
2 0
0
−0.2
−2
−10 0 10 20 30 −10 0 10 20 30

h*x

16
14
12
10
8
6
4
2
0
−2
−10 0 10 20 30 Expansion des coefficients
39/78 23.10.20 Une école de l’IMT Analyse multi-échelle
 Introduction
Ondelettes
Applications

Problème des bords

x h*x
PER PER

16 16
14 14
12 12
10 10
8 8
6 6
4 4
2 2
0 0
−2 −2
−10 0 10 20 30 −10 0 10 20 30

40/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Problème des bords

x h*x
SYM SYM

16 16
14 14
12 12
10 10
8 8
6 6
4 4
2 2
0 0
−2 −2
−10 0 10 20 30 −10 0 10 20 30

41/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Orthogonalité et biorthogonalité
Reconstruction parfaite pour signaux de durée finie

! Problème de l’expansion des coefficients (convolution)

! Solution : convolution circulaire
! La convolution circulaire permet de reconstruire un signal
de N échantillons avec N coefficients d’ondelettes
! Mais elle engendre des discontinuité aux bordes : “fausses”
fréquences qui demandent beaucoup de ressources mais
ne contiennent pas d’information
! Solution : Périodisation symétrique
! Pas de discontinuités introduites
! Mais ça double le nombre de coefficients !
! Sauf si le filtre est symétrique
Le seul filtre orthogonal, RIF et symétrique est celui de Haar !

42/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Filtre de Haar

h(k) = 1 1 )
h(k) = 1 1
g(k) = 1 -1 )(k) = -1
g 1

! Symétrique
! Orthogonal (normalisation)
! Nombre de moments nuls = 1
! Capable de représenter uniquement les signaux constants
par morceaux

43/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Filtres biorthogonaux

Filtres Cohen-Daubechies-Fauveau
)ap
Pour les filtres biorthogonaux, si h a p MN et h ) MN, le
)
support est au moins p + p − 1.
Ils existent des filtres biorthogonaux (CDF) qui :
! Sont symétriques (phase linéaire)
! Ont le maximum de MN pour une durée fixée
! Sont “quasi” orthogonaux (conservation de l’énergie) :
) similaires
filtres h et h
Ces filtres sont les plus communément utilisés dans le codage
d’images.

44/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Filtres biorthogonaux 9/7

Coefficients du filtre :

n 0 ±1 ±2 ±3 ±4
h[l] 0.852699 0.377403 −0.110624 −0.023849 0.037828
)
h[l] 0.788486 0.418092 −0.040689 −0.064539

Réponses impulsionnelles des filtres passe-bas d’analyse et de

synthèse biorthogonaux 9/7. On a pour les filtres passe-haut :
l+1
g[l] = (−1) h ) [l] = (−1)l−1 h [l + 1] .
) [l − 1] et g

45/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Analyse multirésolution 1D
Décomposition

h 2↓ c3 [k]

h 2↓ c2 [k]

g 2↓ d3 [k]
h 2↓ c1 [k]

g 2↓ d2 [k]
c0 [k]

g 2↓ d1 [k]

Structure de décomposition en ondelettes sur 3 niveaux de

résolution

46/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Multiresolution Analysis 1D
60
c0 [k]
40
20
0
-20
0 50 100 150 200 250 300 350 400 450 500
80
c1 [k] d1 [k]
60
40
20
0
-20
0 50 100 150 200 250 300 350 400 450 500

80 d2 [k] d1 [k]
60 c2 [k]
40
20
0
-20
0 50 100 150 200 250 300 350 400 450 500
150
100 c4 [k] d4 [k] d3 [k] d2 [k] d1 [k]
50
0
-50
0 50 100 150 200 250 300 350 400 450 500

47/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Reconstruction

c3 [k] 2↑ )
h

c2 [k] 2↑ )
h

d3 [k] 2↑ )
g
c1 [k] 2↑ )
h

d2 [k] 2↑ )
g c0 [k]

d1 [k] 2↑ )
g

Reconstruction à partir des coefficients d’ondelettes

48/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

AMR 2D

Bancs de filtres 2D séparables

Pour 1 niveau de décomposition

h[!] (1, 2) ↓ aj+1 [n, m]

h[k] (2, 1) ↓
H [n, m]
dj+1
g[!] (1, 2) ↓
aj [n, m]

V [n, m]
dj+1
h[!] (1, 2) ↓

g[k] (2, 1) ↓
D [n, m]
dj+1
g[!] (1, 2) ↓

49/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Interprétation fréquentielle

fhor
(A) (V)

(H) (D)

fver

Les zones (A), (H), (V) et (D) correspondent effectivement aux

coefficients d’approximation, de détails horizontaux, verticaux
et diagonaux.

50/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Exemple

51/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Exemple

52/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

AMR 2D sur 3 niveaux

a3
a2 d3H
d3V
a1 d2H
d3D
d2V
a0 d1H
d2D
d1V
d1D

Mise en oeuvre d’une AMR 2D séparable sur 3 niveaux de

résolution.

53/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

AMR 2D - interprétation fréquentielle

(A) (V3)

(H3) (D3)
(V2)
fhor
(V1)

(H2) (D2)

(H1) (D1)

fver

54/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Exemple

55/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Exemple

56/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Exemple

57/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Exemple

58/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Exemple

59/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Ondelettes
Applications

Exemple

60/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Outline

Introduction

Transformée en ondelettes

Applications
Compression
Débruitage

61/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Ondelettes et codage par sous-bandes

Motivations
Limites de JPEG
! Effets de blocs
! Limites des représentations progressives (scalabilité)
! Analyse spatio-fréquentielle : ≈ STFT
! Modèle d’images : trends + anomalies
! La résolution en fréquence devrait varier avec la fréquence
! Pas de description à résolutions multiples

62/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

TO et compression

Pourquoi utiliser la T.O. ?

! Limites de la TCD : représentation des contours à faibles
débits ; effets de bloc
! T.O. : bon modèle du signal
! bonne résolution spatiale à haute fréquence
! bonne résolution fréquentielle à basse fréquence
! Meilleure concentration de l’énergie
! Absence d’effets de blocs
! Description à résolutions multiples

63/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Stratégies de codage avec TO

Méthodes ne prenant pas en compte les spécificités de l’AMR

! Allocation de bits entre les sous-bandes

! Quantification dans chaque sous-bande (quantificateur
optimal de Lloyd-Max adapté)
! Codage entropique (ex. : Huffman), éventuellement
contextuel
! Avantage : corrélations intra-bande bien exploitées (une
QV peut encore améliorer l’efficacité !)
! Inconvénient : on n’exploite pas les corrélations
résiduelles inter-bandes !

64/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Stratégies de codage avec TO

Méthodes prenant en compte les spécificités de l’AMR

! EZW (Embedded Zerotrees of Wavelet coefficients),

! SPIHT (Set Partitioning in Hierarchical Trees)
! Méthodes basées sur une représentation par arbres des
dépendances entre les sous-bandes
! Avantages : corrélations inter-bande bien exploitées, faible
complexité
! Inconvénient : plus difficile obtenir la scalabilité en
résolution

65/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

JPEG2000

! JPEG2000 vise des domaines où les standards courants ne donnent

pas les meilleures performances :
! Compression bas débit : qualité faible pour JPEG en dessous de 0.25
bpp
! Compression d’images synthétiques
! Accès aléatoire
! Transmission progressive en qualité et en résolution

66/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Nouvelles fonctionnalités

! Codage des régions d’intérêt

! Scalabilité en qualité et en résolution
! Tiling
! Capacité d’atteindre un débit donné
! Du codage sans perte au codage avec perte dans un seul
système et un seul flux binaire

67/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Algorithme

! Transformation en ondelettes
! Partition en blocs
! EBCOT:
! Quantification
! Codage entropique
! Allocation de débit (optimisation RD)
! Ondelettes utilisées :
! mode “sans perte” : biorthogonales 5/3 (lifting entiers vers
des entiers)
! mode “avec perte” : Daubechies biorthogonales 9/7

68/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Débruitage
Principes
Modèle : On observe un signal r (t) qui est la somme d’un signal utile
inconnu s(t) et d’un bruit aléatoire b(t).
Après décomposition sur un base d’ondelettes on a :

cjr [k ] = cjs [k ] + cjb [k ]

Hypothèses :
! base orthonormale,
! décomposition orthogonale,
! signal original (résolution j = 0) de taille multiple de 2jmax
! RSB élevé en bande d’approximation :

asjmax ≈ arjmax

Critère : minimisation de l’EQM : E 2 (s) = E{,s − ŝ,2 }

69/78 23.10.20 Une école de l’IMT Analyse multi-échelle
 Introduction
Compression
Ondelettes
Débruitage
Applications

Débruitage

Principes

! Signal utile régulier

! Énergie concentrée dans les basses fréquences
! Signal creux dans les hautes fréquences
! Beaucoup de coefficients très petits
! Quelques coefficients de grande amplitude (information !)
! Le bruit est souvent blanc et stationnaire
! Modèle : blanc, stationnaire, centré et de puissance σ 2
! Puissance équi-repartie entre les sous-bandes
! Qu’est-ce qu’on retrouve dans les sous-bandes à haute
fréquence ?

70/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Exemples

SNR: 22.4 dB;

σ = 10

71/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Exemples

Sousbande d’approximation

SNR: 46.4 dB

72/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Exemples

Sousbande de détail

SNR: 15.2 dB

73/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Estimateur par atténuation

! cjŝ [k] = θj [k]cjr [k]

! La valeur optimale de θj [k] dépend de cjs [k] qui est
inconnu !
! Si on contraint θ à être binaire : θj [k] ∈ {0, 1}, alors
! L’EQM est le double du cas précédent
! Il est plus facile de déterminer la valeur optimale de θ :
c’est 1 uniquement si |cjs [k ]| > σ
! En conclusion : il faut retenir les coefficients d’ondelettes
ou le signal est censé avoir une valeur élevée, et mettre à
zéro les autres.

74/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Notion de seuillage
c ŝ c ŝ

χ cr χ cr

Hard Thresholding Soft Thresholding


( r r
c r if |c r | > χ c − χ if c > χ

ŝ c ŝ = 0
c = if |c r | ≤ χ
0 if |c r | ≤ χ 
 r
c + χ if c r < χ

75/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Notion de seuillage

! Le seuillage dur a un comportement discontinu au

voisinage du seuil ±χ
! Le seuillage doux introduit un biais ∓χ sur l’estimation des
coefficients de grande amplitude
! Problème principale : choix de la valeur du seuil

76/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Approche minimax

Si les coefficients d’ondelettes du bruit cjb [k] sont de même loi

marginale µ̃ symétrique (de variance σ 2 )
Alors
! On peut donner un’équation donnant χm , le seuil qui
minimise le maximum de l’EQM sur l’ensemble des
signaux s.
! On peut relier cette EQM au cas idéal d’oracle binaire
Tableaux de solutions numériques

77/78 23.10.20 Une école de l’IMT Analyse multi-échelle

 Introduction
Compression
Ondelettes
Débruitage
Applications

Valeur asymptotique du seuil optimal

! Supposons que les coefficients d’ondelettes du bruit soient
de densité marginale :

∀z ∈ R, µ(z) = Ce−h(z)

où C ∈ R∗+ et h est une fonction paire, continue,

strictement croissante sur R+ , convexe et majoré all’infini
par un polynome
! Quand la taille du signal Km va vers +∞, on a

χm ∼ χU = h−1 (ln Km )
√
! Dans le cas gaussien, χU = σ 2 ln Km
! χU est appelé seuil universel

78/78 23.10.20 Une école de l’IMT Analyse multi-échelle