View
147
Download
0
Category
Preview:
Citation preview
1
Echantillonnage,Filtrage numérique (convolution discrète) Analyse en fréquence (transformée de Fourier discrète)
TRAITEMENT NUMERIQUE DES IMAGES
2
échantillonnage (pixelisation)
g g g
ggg
de 4x4 à 128x128 pixels
3
mais une « brosse » d’impulsionsvariant en amplitude d’après la théorie de l’échantillonnage, l’image
n’est pas un pavage de pixels
attention à l’interprétation de l’échantillonnage
x
y
x
y
4
la transformée de Fourier d’une brosse périodique d’impulsions de Dirac b(x,y)est une brosse d’impulsions de Dirac B(u,v) dans le domaine des fréquences
la transformée de Fourier de l’image échantillonnée est périodique
pour reconstituer l’image continue dans le domaine spatial, il faut queson support soit limité dans le domaine des fréquences
la fonction d’interpolation idéale est la tranformée de fourier inversede la fonction support dans le domaine des fréquences (carré en général)
dans le domaine spatial :l’échantillonnage correspond au produit de f(x,y) par b(x,y)
dans le domaine des fréquences : convolution de F(u,v) et de B(u,v)
interprétation fréquentielle de l’échantillonnage
5
128 96 64 32 0 32 64 96 1280
2
4
6
.
128 96 64 32 0 32 64 96 1280
0.2
0.4
.
Fréquence
Fréquence
Rappel du cas monodimensionnel :
- l’échantillonnage se traduit par la périodisation de la transformée de Fourier - pour retrouver le signal initial, il ne faut pas que les répliques se chevauchent
- récupération du signal initial par filtrage passe bas
n
echechech
echech nTxTTnt
TTnttx )(.
/)..(
/).(sin)(
6
Rappel : la transformée de Fourier d’une suite régulière d’impulsions(théorème de Shannon dans le cas monodimensionnel)
par transformée de Fourier un produit dans le domaine spatial devient une convolution
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 160.5
0.5
1.5
.
s(t)
t0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0.5
0.5
1.5
.
S()
T.Fourier
7
première étape
illustration du théorème d’échantillonnagedes signaux bidimensionnels
étude de la fonction d’échantillonnage et sa transformée de Fourier
8
UNE BROSSE REGULIERE D IMPULSIONS
9
EST LE PRODUIT DE DEUX ‘‘LIVRES’’
livrex livrey
livrey livrex( )
x =
x
y
x
y
x
y
10
brosse
livrex livrey
x
y
x
y
x
y
exemple avecmoins de pagesdans le livre
11
la transformée de Fourier de la brosse est la convolution destransformées de Fourier des deux livres(par transformation de Fourier, le produit devient une convolution)
les transformées de Fourier des livres sont des peignes d’impulsionsleurs supports sont respectivement l’axe u et l’axe vnous les nommons ¨PX(u,v) et PY(u,v)
LIVREX LIVREY
livrex LIVREX
T.Fourier
x
y
u
v
u
v
u
v
*
12
la convolution de PY(u,v) avec une des impulsions (placée en u0) se traduitpar la création d’une réplique de PY(u,v) translatée en u0
LIVREDEC
la convolution de PY(u,v) avec PX(u,v)est la somme de toutes les répliquesde peignes décalées, c’est-à-dire une brosse
LIVREY BROSSE
u
v
u
v
u
v
13
utilisation de ce résultat pour interpréter l’effet de l’échantillonnage spatial dans le domaine des fréquences
deuxième étape :
14
dans le domaine spatial, l’échantillonnage d’une fonction f(x,y)se traduit comme un produit de f(x,y) par la fonction d’échantillonnage (la brosse)
f
g( )
avant échantillonnage après échantillonnage
x
y
x
y
15f g( )
autre image où les variations sont plus rapides(il y a plus de hautes fréquences)
avant échantillonnage après échantillonnage
x
y
x
y
16
la transformée de Fourier de la fonction échantillonnée est la convolutionde la transformée F(u,v) de f(x,y) par la transformée de Fourier de la brossequi est elle aussi une brosse
FDEC
GDEC
la convolution par la brosse est la somme des répliques décalées à laposition de chacune des impulsions de la brosse
u
v
u
v
17
retrouver la fonction dans le domaine spatial est équivalent à la retrouver dans le domaine des fréquences
FDEC
GDEC
il ne faut garder qu’une composante fréquentielleil ne faut pas que les répliques décalées se chevauchent
u
v
u
v
18
ici le pas d’échantillonnage est trop grand et les répliques se chevauchentil n’est pas possible de retrouver la fonction initiale par une simple sélection
FDEC
GDEC
u
v
u
v
19
FDEC
GDEC
sélectionner la réplique = effectuer un filtrage passe bas
u
v
u
v
20
« spectre » de l’image initiale (fonction continue de l’espace)
« spectre » de l’image échantillonnée
reconstitution de l’image initiale par filtrage passe bas (interpolation)
fFC
gG
domaine spatial domaine des fréquences
échantillonnage reconstruction
DANS LE DOMAINE DES FREQUENCES : convolution de la tf par une brosse d’impulsions = répétition du spectre suivant la brosse
DANS LE DOMAINE SPATIAL : produit par la « brosse » d’échantillonnage
21
Remarque : il est possible de choisir des motifs de « pavage » différentsmieux adaptés aux caractéristiques spectrales de l’image à échantillonner
ce qui se traduira dans le domaine spatial par un échantillonnage en quinconce plus économique que l’échantillonnage sur un motif carré
par exemple si le spectre de l’image est à symétrie circulaire, le support hexagonal permettra un pavage plus compact que le support carré
22
effectuer le filtrage dans le domaine spatial
calcul de la réponse impulsionnelle du filtre par transforméede Fourier inverse : c’est la transformée de Fourier inversed’un pavé (produit de deux créneaux monodimensionnels en u et v)
sts
x
y
x
y
23
hh.
pour reconstruire l’image à partir de ses échantillons (pixels) il faut que son support spectral soit limité à la moitié de la fréquence d’échantillonnage dans les deux directions u et v ; on en déduit (par transformée de Fourierinverse de la fonction constante sur un support carré) la réponse impulsionnelledu filtre interpolateur
interpolation idéale (voir le cours de traitement numérique du signal)
24
hh.
NOTER LESOSCILLATIONS« Parasites »
25
application à la rotation
)cos.sin.,sin.cos.(),( qpqpfqpg
p
q
)cos.sin..(
)cos.sin..(sin.
)sin.cos..(
)sin.cos..(sin).,(),(
nqp
nqp
mqp
mqpnmfqpf
m n
l’antécédent d’un pixel n’appartient pas à la grille !
)cos.sin.( qp )sin.cos.( qp
calcul par interpolation de
26
gh
gh 255 0.8 2550.2
impulsion « parfaite » avant rotation
impulsion après rotation on voit les oscillationsdes fonctions sinc
gh
gh 255 0.8 2550.2
27
reconstruction par interpolationéchantillonnage
).(
).(sin.
).(
).(sin).,(),(
ny
ny
mx
mxnmfyxf
m n
difficulté : somme infinie, la convergence n’est pas assurée !
combien faut il calculer de termes pour que le résultat ait une précision suffisante(par exemple 10bits soit 1/1000)
approximation : par des fonctions prenant en compte un nombre plus réduit de pixels dans le voisinage de l’échantillon traité
m n
nymxhnmfyxf ),().,(),(
http://www.mathcurve.com/surfaces/beziersu/beziersu.shtml
surfaces de Bézier
28
reconstruction pratique interpolation linéaire par morceaux
réponse impulsionnelle pyramidale
29
éventuellement interpolation plus élaborée tenant compte des caractéristiques spécifiques de l’image : régions lisses, contours nets par exemple
30
FAUT IL RESPECTER LES CONDITIONS DE SHANNON ?
apparition de franges sur les contours
31
inconvénient du filtre passe bas idéal :
les oscillations parasites (Gibbs, Fraunhofer, Airy)
32
transformée de Fourier discrète bidimensionnelle
pas de perte d’information : calculer autant de valeurs dans le domaine des fréquences que dans le domaine spatial (transformée de Fourier inverse)
1
0
1
02
...2exp).,(.
1),(
T
u
T
v T
yvxujvuF
Tyxf
1
0
1
0
...2exp),(),(
T
x
T
y T
yvxujyxfvuF
chaque composante étant calculée par la transformée
(expression de la transformée inverse)
valeurs discrètes (ici entières) de u et de v tout comme de x et de y
33
fréquence (0,0)
il est préférable de placer la fréquence (0,0) au centre
Présentation visuelle du résulta de la transformée de Fourier discrète
la transformée de Fourier discrète (signal échantillonné) est périodique
fréquence d’échantillonnage
½ fréquence d’échantillonnage
34
Présentation visuelle du résulta de la transformée de Fourier discrète
35
Présentation visuelle du résulta de la transformée de Fourier discrète
36
Présentation visuelle du résulta de la transformée de Fourier discrète
37
Présentation visuelle du résulta de la transformée de Fourier discrète
38
il est préférable de placer la fréquence (0,0) au centre
Présentation visuelle du résulta de la transformée de Fourier discrète
la transformée de Fourier discrète (signal échantillonné) est périodique
39
Calcul basé sur la transformée de Fourier rapide monodimensionnelle
1
0
1
0
...2exp),(),(
T
x
T
y T
yvxujyxfvuF
T
yvj
T
xujyxfvuF
T
y
T
x
..2exp
..2exp),(),(
1
0
1
0
1
0
..2exp),(),(
T
x T
xujyxfyuG
on commence par calculer la TF monodimensionnelle de chaque ligne
T
yvjyuGvuF
T
y
..2exp),(),(
1
0
puis la TF monodimensionnelle de chaque colonne de ce tableau intermédiaire
40
1
0
..2exp),(),(
T
x T
xujyxfyuG
T
yvjyuGvuF
T
y
..2exp),(),(
1
0
x
y
u
y
u
y
1. calcul de la transformée monodimensionnelle de chaque ligne de l’image et rangementdans un tableau où la variable en abscisse est u et non plus x
u
v
2. sur ce deuxième tableau, calcul de la transformée monodimensionnellecolonne par colonne et rangement dans un tableau où la variableen ordonnée est maintenant v
f (x,y) G (u,y)
G (u,y)F (u,v)
41
Convolution 2D par transformée de Fourier / produit /
transformée de Fourier inverse
' '
)','()','(),(x y
yxfyyxxhyxg
),(
),(
vuF
yxf
),(
),(
vuH
yxh
),(
),(
vuG
yxg
IMAGEINITIALE
EFFET IMAGEMODIFIEE
),().,(),( vuFvuHvuG
42
Convolution 2D par transformée de Fourier / produit / transformée de Fourier inverse
attention : tout se passe comme si les images et leurs transformées étaient périodiques
échantillonnage spatial = périodisation de la transformée de Fourier
échantillonnage de la transformée = périodisation dans le domaine spatial
1
0
1
0
...2exp),(),(
T
x
T
y T
yvxujyxfvuF
valeurs discrètes (ici entières) de u et de v tout comme de x et de y
1
0
1
02
...2exp).,(.
1),(
T
u
T
v T
yvxujvuF
Tyxf
43
Illustration avec la transformée de Fourier bidimensionnelle
Lorsqu’on effectue une convolution (nécessairement circulaire)en utilisant la transformée de Fourier discrète, le résultat est unefonction périodique dont la période est la dimension du signal (ici 128)
le résultat de la convolution qui déborde en haut de l’image seretrouve reproduit en bas du fait de la périodisation implicite
convolution de f et de g
44
le résultat est réel (mais peut se déduire de la transformée de Fourier)
utilisée en compression jpeg et mpeg
cos
cos
45
application à des médaillons 8x8 ; compression par élimination des composantesde très faible amplitude, et quantification grossière des amplitudes faibles
46
47http://www.egr.msu.edu/waves/people/Ali_files/DCT_TR802.pdf
orig
inal
ou
com
pres
sion
à 5
0%co
mpr
essi
onà
25%
48
transformée en ondelettes (wavelets) JPEG2000
http://fr.wikipedia.org/wiki/Compression_Ondelette_(Images)
antonini, barlaud, mathieu (traitement d’images SI5)
hautes fréquenceshorizontales
basses fréquenceshorizontales
hautes fréquencesverticales
basses fréquencesverticales
filtrage
filtrage
49
vertx 0 lignes rouge( ) 1 rouge
50
log fc
30 log fc
128
points communs entre la DCT et la compression par ondelettes transforméede Fourier
partentière log fc
0 bit
2bits3bits et plus
1 bit
les hautes fréquences sont peuénergétiques, il n’est pas nécessaired’utiliser beaucoup de bits pour les coder
51
signaux aléatoires bidimensionnels
les définitions et les propriétés fondamentales sont des extensions directesde celles qui sont données en traitement du signal monodimensionnel
filtrage des signaux aléatoires
autocorrélation
stationnarité : invariance spatiale des propriétés statistiques
moyenne, variance
densité spectraletransformée de Fourierde la fonction d’autocorrélation
52
bruit blanc : échantillons indépendants
autocorrélation nulle sauf à l’origine m=n=0(valeur de la variance)
densité spectrale constante mais fluctuations importantes autour de cette moyenne constante
x
y
x
y
u
v
x
y
domaine
spatial
domaine
fréquen
tiel
Recommended