Fourierova transformace ve zpracování obrazů Jean Baptiste Joseph Fourier 1768-1830
6. přednáška předmětu Zpracování obrazů Martina Mudrová 2004
Motivace Proč používat Fourierovu transformaci ? • základní matematický nástroj ve zpracování digitálních obrazů 9detekce hran a segmentace obrazu 9 úprava kvality obrazu 9 rekonstrukce obrazu 9 komprese obrazu (formát .JPG) 9 detekce objektů 9 atd.
M. Mudrová, 2004
2
Matematické minimum = převod mezi časovou x(t) a frekvenční X(f) oblastí
x(t ) ⇔ X ( f )
t...časová (prostorová oblast) f...frekvenční oblast
Základní definice: zpětná spojitá FT:
přímá spojitá FT: +∞
X(f)=
∫
+∞
x ( t ) e − i 2 π tf dt
x (t ) =
∫
X ( f ) e + i 2πtf df
−∞
−∞
Požadavky na f(t) : po částech spojitá ∞
integrovatelná
∫ | x ( t ) | dt < ∞
−∞
M. Mudrová, 2004
3
Příklad spojité FT Jak vypadá FT periodických funkcí ?
⇔
x(t ) = sin( 2π f 0t )
Def. FT: X ( f ) = Eulerovy vzorce:
e
± i 2π f 0 t
X(f ) =
+∞
∫ x(t ) e
− i 2πtf
1 (δ ( f − f 0 ) − δ ( f + f 0 ) ) 2i d(f)… Diracova funkce
dt
−∞
= cos( 2πf 0 t ) ± i sin( 2πf 0 t ) f0
Spektrum |X(f)| (amplitudová fr. charakt.)
x(t)
⇔ T=1/f0
M. Mudrová, 2004
2T
3T
t
|X(f)|
Časová (prostorová) oblast x(t)
f
-f 0
0
f0
f 4
Od spojité k diskrétní FT Co je diskrétní FT ? Diskretizace v čase:
Diskretizace ve frekvenci:
+
tY tn Y n
f Y fk Y k
Diskrétní Fourierova transformace Přímá diskrétní FT: 1 X (k ) = N
N −1
∑ x ( n) e
−i 2π
Zpětná diskrétní FT:
x ( n) ⇔ X ( k )
nk N
n =0
x(n) =
N −1
∑ X (k ) e
+ i 2π
kn N
k =0
|X(k)|
x(n)
1 0
-1 0
20
40
60 n
M. Mudrová, 2004
0 0 0
15 1.57 0.25
63 31 k...index 3.14 ωk ...kruhová frekvence 0.5 f …normalizovaná frekv. 5
Omezení vzorové funkce v čase (prostoru) = váhování = apodizace
Funkce s konečnou délkou ... Periodický signál a jeho spektrum 40 30 |X(ω)|
x(n)
1 0
20 10
-1 0
10
20
30 n
40
50
0
60
0
0.5
1
ω
1.5 od 0 do
π
ω
1.5 od 0 do
π
ω
1.5 od 0 do
π
2
2.5
3
2
2.5
3
2
2.5
3
Obdelnikové okno a jeho spektrum 40 30
1
|X(ω)|
x(n)
1.5
0.5 0
20 10
0
10
20
30 n
40
50
0
60
0
0.5
1
Omezený signál a jeho spektrum 40 30 |X(ω)|
x(n)
1 0
10
-1 n
M. Mudrová, 2004
20
0
0
0.5
1
6
1
|X(k)|
x(n)
Do dvou dimenzí 0 -1 0
10
20
30
40
50
60
0
n
n -> [n, m]
N −1 M −1
∑ ∑ x ( n, m ) e
− i 2π (
k -> [k, l]
x(n, m) ⇔ X (k , l )
kn lm + ) N M
n =0 m =0
63
k
2D DFT
Přímá 2D DFT: 1 X (k , l ) = MN
31
15
Zpětná 2D DFT: N −1 M −1
x ( n, m ) = ∑ ∑ X ( k , l ) e
nk ml + ) N M
k =0 l =0
| X ( f k ,f l ) |
x ( n ,m )
64
x ( n ,m )
+ i 2π (
m
1
1
0 64 1
64
n
M. Mudrová, 2004
64
m
1
1
n
1
1
0
fl
0 -1
-1
f
k
7
Příklad 2D DFT reálného obrazu
x(n,m)
m
1
Symetrie 1 1
270 1
M. Mudrová, 2004
0 n
1
0
366 -1
-1
1
8
Princip číslicové filtrace Co se stane při úpravě spektra? prostorová oblast x(n)
spektrum |X(k)|
1. periodická funkce
2. náhodný šum
3. =1.+2.
4. po úpravě spektra
M. Mudrová, 2004
9
2D filtrace
M. Mudrová, 2004
10
Princip diskrétní konvoluce Co se při úpravě spektra děje v prostorové oblasti? Spektrální oblast:
Y(k) = X(k) . H(k) pro∀k
Součin
Prostorová oblast: n
y (n) = x(n) * h(n) = ∑ x( j )h(n − j )
Konvoluce
j =0
Kde:
M. Mudrová, 2004
y(n)…žádaný tvar funkce x(n)...daný (poškozený) tvar funkce h(n) ...číslicový filtr 11
Příklad diskrétní konvoluce Jaký má význam konvoluce? Příklad:
x(n) = 10; 20; 30; 40; 50 h(n) = 0,5; 0,5
y(n) = x(n) * h(n)
n=0 n=1
n
= ∑ x( j )h(n − j )
n=2
j =0
n=3
n=4
j=0 j=0 j=1 j=0 j=1 j=2 j=0 j=1 j=2 j=3 j=0,1,2 j=3 j=4
f(0).h(0) f(0).h(1-0) f(1).h(1-1) f(0).h(2-0) f(1).h(2-1) f(2).h(2-2) f(0).h(3-0) f(1).h(3-1) f(2).h(3-2) f(3).h(3-3) f(4).h(4-3) f(4).h(4-4)
(Klouzavý průměr) 10 . 0,5 10 . 0,5 20 . 0,5
5 5 10
y(0)= 5 y(1)=5+10 = 15
10 15
y(2)=10+15= 25
30 . 0,5 40 . 0,5
15 20
y(3)=15+20= 35
nedef. 40 . 0,5 50 . 0,5
20 25
y(4)=25+20= 45
nedef.
20 . 0,5 30 . 0,5 nedef. nedef.
y(n) = 5; 15; 25; 35; 45 M. Mudrová, 2004
12
2D diskrétní konvoluce Jak vypadá 2D konvoluce? n
m
y (n, m) = x(n, m) * h(n, m) = ∑ ∑ x( j1 , j2 )h(n − j1 , m − j2 ) j1 = 0 j2 = 0
Prvek počítaný na pozici(n,m)
M. Mudrová, 2004
0
1
0
1
-4
1
0
1
0
matice filtru h(n,m)
matice obrázku x(n,m) 13
(=>segmentace obrazu) Hrana = náhlá změna obrazové funkce Princip: Aplikace hranových detektorů = hornopropustných filtrů Příklad matice filtru h(n,m) (filtr Prewittové)
⎡1 1 1⎤ ⎢0 0 0⎥ ⎢ ⎥ ⎢⎣− 1 − 1 − 1⎥⎦ M. Mudrová, 2004
Příklad spektra filtru |H(k,l)|
Obraz po detekci hran
Úloha detekce hran
Originální obraz
Aplikace I – detekce hran
14
Úprava obrazu Princip: Potlačení vysokofrekvenčních složek aplikací dolnopropustného filtru
Originální obraz
Aplikace II – potlačení šumu
Obraz po úpravě
Spektrum filtru |H(k,l)|
M. Mudrová, 2004
15
Úloha rekonstrukce poškozeného obrazu Princip: • Inverzní filtrace • Wienerova filtrace
Poškozený obraz
Aplikace III – ostření
• • • •
Rozostření pohybem objektu (objektivu) Špatné zaostření objektivu Turbulence atmosféry atd.
M. Mudrová, 2004
Obraz po rekonstrukci
Typ poškození:
16
Princip:
Filtr h(n,m)
• Výpočet korelační funkce = konvoluce v prostor. oblasti • Zrychlení výpočtu aplikací algoritmu FFT ve 2D -> součin ve frekvenční oblasti
M. Mudrová, 2004
Korelační funkce h(n,m)
Úloha detekce polohy objektu
Obraz x(n,m)
Aplikace IV – detekce objektů
17
Pokročilejší metody zpracování obrazů
Short-time Fourier transform = krátká FT - Kompromis mezi časovým (prostorovým) a frekvenčním rozlišením Wavelet transformace´= vlnková transformace - používá časová (prostorová) okénka s proměnlivou délkou (wavelet funkce) - Aplikace v analýze obrazu, potlačení šumu, kompresi dat,… Radonova transformace (p. Radon – české národnosti) - konverze z cylindrických souřadnic - aplikace především v biomedicíně (PET, SPECT, CT, …) …
M. Mudrová, 2004
18
