TRAITEMENT DES
IMAGES
et
RECONNAISSANCE
DES FORMES
SUPELEC – ACS
2007
Jean-Marc Vézien
[email protected]
III. TRAITEMENT
FREQUENTIEL
Jean-Marc Traitement d'images 2
Vezien
III. TRAITEMENT FREQUENTIEL
Transformée de Fourier continue:
fF
f(x) → F(u)
+∞
∫ f ( x )e
− 2 iπux
F (u ) = dx
−∞
fF −1
F(u) → f(x)
+∞
∫
2 iπux
f ( x) = F (u ) e du
−∞
F est une transformée bijective et unitaire (elle
conserve la norme).
Jean-Marc Traitement d'images 3
Vezien
III. TRAITEMENT FREQUENTIEL
+∞ +∞
F (u ) = ∫ f ( x) cos(2πux)dx + i ∫ f ( x) sin(2πux)dx
−∞ −∞
i Φ(u )
F(u) = F(u)e
F(u) = spectre de Fourier
Φ(u) = phase complexe du spectre
Transformation bidimensionnelle:
+∞ +∞
∫ ∫ f ( x, y )e
− 2 iπ ( ux + vy )
F (u , v) = dxdy
− ∞− ∞
+∞+∞
∫ ∫ F (u, v) e
2 iπ ( ux + vy )
f ( x, y ) = dudv
− ∞− ∞
Jean-Marc Traitement d'images 4
Vezien
III. TRAITEMENT FREQUENTIEL
Fréquence maximale:
clair
T ≈ 2d
1
fmax =
2d
sombre d
F(nu,0) = f(x,y) • (n=5 ici)
Si f ne contient pas cette harmonique, les
deux signaux sont décorrélés et F(nu,0) ≈ 0
F(nu,mv) = f(x,y) •
Jean-Marc Traitement d'images 5
Vezien
III. TRAITEMENT FREQUENTIEL
En fait, transformée discrète sur un
support fini:
… I0 …
I0 I0 I0
… I0 …
f(x,y) = f(x0+x.Dx, y0+y.Dy)
x dans [0,N-1] , y dans [0,M-1]
Echantillonnage fréquentiel minimal correspondant:
1 1
Du = Dv =
M .Dx N .Dy
Jean-Marc Traitement d'images 6
Vezien
III. TRAITEMENT FREQUENTIEL
M −1 N −1 ux vy
1 − 2 iπ ( + )
F (u , v ) =
M N
∑∑ f ( x, y )e
0 0
M N
M −1 N −1 ux vy
2 iπ ( + )
f ( x, y ) = ∑∑ F (u, v)e M N
0 0
Complexité = M2.N2
Si M=2K1 et N=2K2, FFT (Fast Fourier Transform)
plus rapides M.N.log(M.N)
v
x
y
Jean-Marc Traitement d'images 7
Vezien
III. TRAITEMENT FREQUENTIEL
⎛
N −1M −1
ux ⎞ − 2iπ vy
F(u,v) = ∑⎜ ∑ f(x, y)e M ⎟ e M
1 1 − 2 i π
N 0 ⎝M 0 ⎠
F(u,y)
successivement deux algorithmes de FFT
monodimensionnels, l'un sur les lignes, et l'autre
sur les colonnes.
1D
horiz.
f(x,y) 1D F(u,y)
vert.
F(u,v)
Jean-Marc Traitement d'images 8
Vezien
III. TRAITEMENT FREQUENTIEL
Gain de la FFT par rapport à une
transformée directe:
N N2 Nlog2N Gain
64 4096 384 10.67
128 16384 896 18.29
256 65536 2048 32
512 262144 4608 56.89
1024 1e6 10240 102.40
Jean-Marc Traitement d'images 9
Vezien
III. TRAITEMENT FREQUENTIEL
Théorème de convolution:
+∞ +∞
f ( x , y ) ∗ g ( x, y ) = ∫ ∫ f (u, v) g ( x − u, y − v) du dv
− ∞− ∞
f(x,y) ∗ g(x,y) → F(u,v) . G(u,v)
f(x,y).g(x,y) → F(u,v) ∗ G(u,v)
f(x,y)
∗ f(x,y) ∗ g(x,y)
g(x,y)
Ou bien :
f(x,y) fF
-1
. fF f(x,y) . g(x,y)
g(x,y) fF
Jean-Marc Traitement d'images 10
Vezien
III. TRAITEMENT FREQUENTIEL
Autres propriétés:
• Translation:
f ( x, y ) exp[2π j (u0 x + v0 y ) / N ] = F (u − u0 , v − v0 )
En particulier:
[ ]
F f ( x, y )(−1) x + y = F (u − N / 2, v − N / 2)
• Rotation:
F [ f (r , θ + θ 0 )] = F (ω , φ + θ 0 )
• Symétrie: si f réelle,
F (u, v) = F * (−u ,−v)
F (u , v) = F (−u ,−v)
Jean-Marc Traitement d'images 11
Vezien
III. TRAITEMENT FREQUENTIEL
Spectre d’une image (énergie):
2
S f = F ( f ( x, y ) ∗ f (− x,− y )) = F (u , v)
Problème: en pratique, cette norme varie
entre 0 et 1e6 → perte de contraste
En pratique, on visualise plutôt la fonction:
D(u , v) = c log[1 + F (u , v) ]
.
Jean-Marc Traitement d'images 12
Vezien
III. TRAITEMENT FREQUENTIEL
Systèmes optiques et TF:
Système linéaire, homogène:
h(x,y) → H(u,v)
MTF : fonction de transfert de modulation =
2
H(u,v)
lentille circulaire parfaite:
H (r ) =
2
π
[cos −1
(λFr ) − λFr 1 − (λFr ) 2 ]
λ = longueur d' onde
d dist. focale
r = u +v 2 2
F = =
D diam.lentille
Jean-Marc Traitement d'images 13
Vezien
III. TRAITEMENT FREQUENTIEL
FILTRAGE DANS LE DOMAINE FRÉQUENTIEL
Traitements (x,y) et (u,v) équivalents en théorie
Spatial
+ Op. non-linéaires
+ Op. non-stationnaires
+ si petite réponse impulsionnelle
- Contrôle de la réponse fréquentielle
Fréquentiel
+ implémentation facile (si linéaire),
+ réponse fréquentielle facile à contrôler,
+ si réponse impulsionnelle étendue
- Op. non-linéaires ou non-stationnaires impossibles
- lenteur
Jean-Marc Traitement d'images 14
Vezien
III. TRAITEMENT FREQUENTIEL
Principe:
F(u,v) G(u,v) -1
f(x,y) F .
F g(x,y)
image
améliorée
H(u,v)
Filtre d'amélioration
Influence de la phase primordiale dans
une image !
H(u,v) ≥ 0 et Im(H(u,v)) = 0
→ limitation des perturbations.
Jean-Marc Traitement d'images 15
Vezien
III. TRAITEMENT FREQUENTIEL
Filtrage passe-bas:
• Idéal:
H (u, v ) = 1 si u 2 + v 2 ≤ D ,
0
H (u, v ) = 0 ailleurs.
Jean-Marc Traitement d'images 16
Vezien
III. TRAITEMENT FREQUENTIEL
Passe-bas idéal, ex:
Jean-Marc Traitement d'images 17
Vezien
III. TRAITEMENT FREQUENTIEL
Attention à garder l’information pertinente
3 4
5
Jean-Marc Traitement d'images 18
Vezien
III. TRAITEMENT FREQUENTIEL
Autres filtre passe-bas:
• Butterworth:
1 D : fréquence de
H (u, v) =
⎡ u 2 + v2 ⎤
2N
coupure,
1+ ⎢ ⎥ N : ordre du filtre.
⎣ D ⎦
• Exponentiel:
⎡ ⎛ 2 ⎞
N
⎤
u + v 2
H (u, v) = exp ⎢− ⎜ ⎟ ⎥
⎢ ⎜ D ⎟ ⎥
⎣ ⎝ ⎠ ⎦
Jean-Marc Traitement d'images 19
Vezien
III. TRAITEMENT FREQUENTIEL
Filtrage passe-haut: renforcer les détails
• Idéal:
1
• Butterworth: H(u,v) =
⎡ D0 ⎤ 2 N
1+ ⎢ 2 ⎥
⎣ u + v 2⎦
Jean-Marc Traitement d'images 20
Vezien
III. TRAITEMENT FREQUENTIEL
• Alternative: filtre exponentiel
N
⎡ D0 ⎤
H (u , v) = exp − ⎢ ⎥
⎣ u +v ⎦
2 2
A B
C D
Jean-Marc Traitement d'images 21
Vezien
III. TRAITEMENT FREQUENTIEL
Autres exemples de traitement:
• Filtre passe-bande visuel
H(u,v) = 2.6 [0.0152 + 9.114D] exp (-[0,114D]1.1)
D(u, v) = u 2 + v 2 (u,v): fréquence angulaire,
en cycles / degré
H (u ,v)
100
10
cycles/ d egré
8 40
Jean-Marc Traitement d'images 22
Vezien
III. TRAITEMENT FREQUENTIEL
Autres exemples de traitement:
• Masquage du flou (unsharp)
+
f(x,y) g(x,y)
-
Filtre passe-bas
g(x,y) = (1+ß) f(x,y) – ß fl(x,y)
Jean-Marc Traitement d'images 23
Vezien
III. TRAITEMENT FREQUENTIEL
Autres exemples de traitement:
• Elévation à la puissance S
g(u,v) = |f(u,v)|s exp(i Ф (u,v)) (0 ≤ S ≤ 1).
S = 0 → information de phase de l'image
phase = information primordiale de l'image !
Jean-Marc Traitement d'images 24
Vezien
