1
Przekształcenie Fouriera obrazów
FFT
2006 © P. Strumiłło, M. Strzelecki
2
( )
( )
∫
∞
∞
−
+
=
ω
ω
ω
d
e
F
t
f
t
j
transformata Fouriera
Przekształcenie Fouriera
Fourier wymyślił sposób rozkładu szerokiej klasy funkcji
(sygnałów) okresowych na składowe harmoniczne; taką
reprezentację sygnału można uzyskać z odpowiednio
ważonej sumy funkcji harmonicznych o różnych
częstotliwościach
Joseph Fourier
(1768-1830)
( )
( )
∫
∞
∞
−
−
=
dt
e
t
f
F
t
j
ω
ω
odwrotna
prosta
3
Przekształcenie Fouriera - przykład
czas
częstotliwość
( )
(
)
(
)
(
)
(
)
0
0
0
2
1
ω
ω
δ
ω
ω
δ
ω
ω
ω
+
+
−
=
=
∫
+∞
∞
−
−
dt
e
t
cos
X
t
j
1/2
0
ω
0
ω
−
t
0
2
ω
π
=
T
ω
X
(
ω
)
4
Przekształcenie Fouriera - przykład
( )
>
<
=
T
t
,
T
t
,
t
f
0
1
T
( )
2
0
2
2
T
j
T
t
j
e
T
sin
A
dt
e
A
F
ω
ω
ω
ω
ω
−
−
=
=
∫
- 2
π/T
2
π/T
FT
A
AT
t
|F(
ω
)|=?
ω
5
Przekształcenie Fouriera - przykład
( )
(
)
(
)
∑
∑
+∞
∞
−
+∞
∞
−
−
↔
−
=
0
ω
ω
δ
ω
δ
δ
k
kT
t
t
s
T
ω
t
-2T
0
2T
T
-T
1
-4π/T
0
4π/
T
2π/
T
-
2π/
T
2π/T
x(t)
x(
ω
)
FT
T
s
π
ω
2
=
Szereg impulsów Diraca
6
Transformacja Fouriera obrazów
obraz monochromatyczny
widmo Fouriera obrazu
7
W jakim celu stosuje się
transformacje obrazów?
1.
Uzyskanie bardziej zwartego (oszczędnego) sposobu
kodowania obrazów (ich
kompresji,
np. standard kompresji obrazów
JPEG)
2.
Uwidocznienie cech obrazu niezauważalnych w dziedzinie
przestrzennej, np. zakłóceń okresowych
3.
Projektowanie filtrów obrazów w dziedzinie częstotliwości
oraz realizacja
szybkich metod filtracji obrazów
8
Transformacja Fouriera obrazu
1.
Detekcja cech obrazu w dziedzinie widma, np.
zakłóceń okresowych
9
Transformacja Fouriera obrazu
(
)
(
)
(
)
(
)
∫ ∫
∫ ∫
∞
∞
−
∞
∞
−
+
+
∞
∞
−
∞
∞
−
+
−
=
=
dudv
e
v
,
u
F
y
,
x
f
dxdy
e
y
,
x
f
v
,
u
F
)
vy
ux
(
j
)
vy
ux
(
j
π
π
2
2
odwrotna
prosta
10
Widmo amplitudowe i fazowe
transformaty obrazu
(
)
(
)
(
)
[
]
(
)
(
)
[
]
(
)
[
]
(
)
[
]
(
)
[
]
(
)
[
]
v
,
u
F
Re
v
,
u
F
Im
arctan
v
,
u
F
arg
v
,
u
F
Im
v
,
u
F
Re
|
v
,
u
F
|
e
|
v
,
u
F
|
v
,
u
F
v
,
u
F
arg
j
=
+
=
=
−
2
2
11
Dyskretna transformacja Fouriera obrazu
(
)
(
)
(
)
(
)
1
1
0
1
1
1
0
1
1
0
1
0
2
2
1
0
1
0
−
=
=
−
=
=
∑∑
∑∑
−
=
−
=
+
+
+
−
−
=
−
=
N
,...,
,
y
,
x
dla
e
v
,
u
F
N
y
,
x
f
N
,...,
,
v
,
u
dla
e
y
,
x
f
N
v
,
u
F
N
u
N
v
N
/
)
vy
ux
(
j
N
/
)
vy
ux
(
j
N
x
N
y
π
π
Liczba działań, np. dla
obrazu 512x512?
12
Przykład obliczeniowy
dla funkcji jenowymiarowej
( )
]
4
4
3
1
[
=
x
f
( )
( )
∑
=
−
=
−
=
3
1
0
2
1
N
x
N
/
ux
j
e
x
f
N
u
F
π
( )
( )
( )
( )
( )
( )
[
]
[
]
( )
(
)
( )
( )
( )
(
)
j
......
..........
..........
..........
..........
..........
..........
..........
F
......
..........
..........
..........
..........
..........
..........
..........
F
j
......
..........
..........
..........
..........
..........
..........
..........
F
f
f
f
f
e
x
f
N
F
N
x
N
/
x
j
+
−
=
=
−
=
=
+
−
=
=
=
+
+
+
=
=
+
+
+
=
=
∑
=
−
=
−
3
4
1
3
2
4
1
2
3
4
1
1
3
4
4
3
1
4
1
3
2
1
0
4
1
1
0
3
1
0
0
2
π
θ
θ
θ
sin
cos
j
e
j
+
=
13
50
100
150
200
250
50
100
150
200
250
10
20
30
40
50
60
Przykład widma
amplitudowego obrazu
MIT
14
FFT
FFT
Przykłady widm obrazów
15
Detekcja zakłóceń harmonicznych
MIT
64 okresy sinusoidy
64 okresy sinusoidy
256
256
128
128
64
64
256 punktów
256 punktów
64
64
16
Widmo fazowe obrazu
MIT
(
)
[
]
v
,
u
F
arg
(
)
v
,
u
F
(
)
{
}
v
,
u
F
1
−
ℑ
17
f(x,y)
(64x64)
|F(u,v)|
log(1+|F(u,v)|)
18
Podstawowe własności
przekształcenia Fouriera
Rozłączność transformacji dwuwymiarowej:
f(x,y)
(0,0)
(N-1)
(N-1)
F(x,v)
(0,0)
(N-1)
(N-1)
F(u,v)
(0,0)
(N-1)
(N-1)
tr. wierszy
tr. kolumn
Dwuwymiarową transformację Fouriera można wyznaczyć
obliczając transformacje jednowymiarowe, tj. przez wykonanie
transformacji wierszy a następnie kolumn obrazu.
19
Rozłączność dwuwymiarowego
przekształcenia Fouriera
(
)
∑
∑
∑
−
=
−
−
−
=
−
=
−
=
=
1
0
/
2
/
2
1
0
1
0
/
2
,
1
)
,
(
)
,
(
1
)
,
(
N
x
N
ux
j
N
vy
j
N
x
N
y
N
ux
j
e
v
x
F
N
v
u
F
e
y
x
f
e
N
v
u
F
π
π
π
F(x,v)
N
vy
ux
j
N
x
N
y
e
y
x
f
N
v
u
F
/
)
(
2
1
0
1
0
)
,
(
1
)
,
(
+
−
−
=
−
=
∑ ∑
=
π
20
FT
Obrazy
Widma
amplitudowe
Przykład
21
FT
Obrazy
Widma
amplitudowe
(
)
(
)
(
)
+
−
⇔
−
−
N
vy
ux
j
exp
v
,
u
F
y
y
,
x
x
f
0
0
0
0
2
π
Przesunięcie w dziedzinie przestrzennej
22
Transformata iloczynu i splotu
ℑ
ℑ
ℑ
ℑ
{f(x,y) g(x,y)} = F(u,v)
∗ G(u,v)
ℑ
ℑ
ℑ
ℑ
{f(x,y)
∗ g(x,y)} = F(u,v) G(u,v
)
Druga własność jest szczególnie przydatna w
filtracji obrazów, jest ona również wykorzystywana
w projektowaniu filtrów obrazu w dziedzinie widma.
23
α
2
1
f(
α
)
α
1
1/2
g(
α
)
-1
α
1/2
g(-
α
)
x
3
1/2
f(x)
*g(x)
0
Splot funkcji ciągłych
- przykład
α
2
1/2
f(
α
)g(x-
α
)
x
1
α
2
1/2
f(
α
)g(x-
α
)
x
1
α
1/2
g(x-
α
)
x
-1
( ) (
)
α
α
α
d
x
g
f
x
g
x
f
−
=
∗
∫
∞
∞
−
)
(
)
(
24
Splot dwuwymiarowych
funkcji dyskretnych
f(i,j), g(i,j) - funkcje dyskretne o okresie N
należy wydłużyć okres f(i,j) oraz g(i,j) do wartości
M=2N-1 w następujący sposób:
−
≤
≤
−
≤
≤
=
−
≤
≤
−
≤
≤
=
1
0
1
0
1
0
1
0
M
j
,
i
N
N
j
,
i
)
j
,
i
(
g
)
j
,
i
(
g
M
j
,
i
N
N
j
,
i
)
j
,
i
(
f
)
j
,
i
(
f
e
e
∑ ∑
−
=
−
=
−
−
=
∗
1
0
1
0
M
m
e
e
M
n
e
e
)
n
j
,
m
i
(
g
)
n
,
m
(
f
)
j
,
i
(
g
)
j
,
i
(
f
25
Korelacja funkcji ciągłych
- przykład
α
1
1/2
g(
α
)
α
1/2
f(
α
)g(x+
α
)
|x|
x
1.5
1/2
f(x)◦g(x)
-1.5
α
1
1/2
g(x+
α
)
|x|
α
2
1/2
f(
α
)g(x+
α
)
( ) (
)
α
α
α
d
x
g
f
x
g
x
f
+
=
∫
∞
∞
−
)
(
)
(
o
α
2
1
f(
α
)
2
|x|
26
Korelacja dwuwymiarowych
funkcji dyskretnych
f(i,j), g(i,j) - funkcje dyskretne o okresie N
(dokonuje się tu analogicznego wydłużenia okresu
jak dla operacji splotu)
∑ ∑
−
=
−
=
+
+
=
1
0
1
0
M
m
e
e
M
n
e
e
)
n
j
,
m
i
(
g
)
n
,
m
(
f
)
j
,
i
(
g
)
j
,
i
(
f
o
27
Okresowość transformaty oraz
symetria widma amplitudowego
F(u,v
)
=F(u+N,v
)
=F(u,v+N)=F(u+N,v+N)
Jeżeli f(x,y) jest funkcją rzeczywistą, to zachodzi:
oraz dla widma amplitudowego:
Dla transformaty F(u,v) o wymiarze NxN są prawdziwe
tożsamości:
(
)
(
)
v
,
u
F
v
,
u
F
−
−
=
∗
(
)
(
)
v
,
u
F
v
,
u
F
−
−
=
28
f(x,y)
f(x,y)
f(x,y)
f(x,y)
f(x,y)
f(x,y)
f(x,y)
f(x,y)
f(x,y)
Przyjmuje się, że
obraz jest funkcją
okresową o
okresie (N, N)
Okresowość transformaty Fouriera
29
Przesunięcie dziedzinie widma
(
)
(
)
(
)
0
0
0
0
2
v
v
,
u
u
F
N
y
v
x
u
j
exp
y
,
x
f
−
−
⇔
+
π
Własność ta jest nazywana również własnością
(lub twierdzeniem) o modulacji.
30
Przesuniecie w dziedzinie widma
N/2
N/2
N
0
0
N
jeden okres widma
Matlab: fftshift
|F(u)|
fftshift(|F(u)|)
31
Przesunięcie w dziedzinie widma
(
)
(
)
(
)
(
)
(
)
(
)
(
)
[
]
(
)( )
y
x
y
,
x
f
y
x
j
exp
y
,
x
f
N
y
v
x
u
j
exp
y
,
x
f
N
v
,
N
u
F
N
v
u
dla
v
v
,
u
u
F
N
y
v
x
u
j
exp
y
,
x
f
+
−
=
+
=
=
+
−
−
⇔
=
=
−
−
⇔
+
1
2
2
2
2
2
0
0
0
0
0
0
0
0
π
π
π
32
Przesunięcie w dziedzinie widma
|F(u,v)|
fftshift(|F(u,v)|)
N
(0,N-1)
(0,0)
(N-1, N-1)
(N-1,0)
(0,0)
33
θ
θ
θ
θ
0
= 45°
θ
θ
θ
θ
0
= 0°
Własność obrotu
transformaty dwuwymiarowej
f(r,
θ
+
θ
0
) ⇔ F(
ω
,
φ
+
θ
0
)
34
Liniowość transformacji
ℑ
{a f(x,y) + b g(x,y)} = a F(u,v) + b G(u,v)
f(x,y)
g(x,y)
FT
g(x,y)
FT
f(x,y)
FT
35
Twierdzenie o zmianie skali
ℑ
{f(ax,by)} = |ab|
-1
F(u/a, v/b)
R
b
,
a
∈
36
Wartość średnia obrazu
(
)
(
)
( )
(
)
(
)
( )
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
2
,
F
N
y
,
x
f
y
,
x
f
N
,
F
y
,
x
f
N
y
,
x
f
N
x
N
y
N
x
N
y
=
=
=
∑∑
∑∑
−
=
−
=
−
=
−
=
F(0,0)
F(0,0)
37
Rozdzielczość transformacji Fouriera
f=zeros(30,30);
f(5:24,13:17)=1;
imshow(f,'notruesize')
F=fft2(f);
%oblicz transformatę Fouriera
F1=log(abs(F)+1);
%wyznacz widmo amplitudowe
imshow(F1,[0 5],'notruesize');
f
|F1|
38
Dyskretna
Transformacja
Fouriera
1
30
1
15
Funkcje bazowe
30-punktowej
transformacji
Fouriera
(składowa
sinusoidalna)
39
Rozdzielczość transformacji Fouriera
%zwiększenie rozdzielczości
f=zeros(30,30);
f(5:24,13:17)=1;
F=fft2(f,256,256);
F2=log(abs(F)+1);
imshow(fftshift(F2),[0 5],'notruesize');
f
|F2|
40
Szybka transformacja Fouriera
(ang. Fast Fourier Transform, FFT)
Jeżeli N=2
n
to N jest liczbą parzystą daną w postaci N=2*M.
Można dla takich N wykazać, że:
M
j
M
u
M
e
nieparzyst
parzyste
u
M
e
nieparzyst
parzyste
M
x
ux
M
e
nieparzyst
M
x
ux
M
parzyste
e
W
M
u
W
u
F
u
F
M
u
F
M
u
W
u
F
u
F
u
F
W
x
f
M
u
F
W
x
f
M
u
F
/
2
2
2
1
0
1
0
1
,...,
0
],
)
(
)
(
[
2
1
)
(
1
,...,
0
],
)
(
)
(
[
2
1
)
(
)
1
2
(
1
)
(
,
)
2
(
1
)
(
π
−
−
=
−
=
=
−
=
−
=
+
−
=
+
=
+
=
=
∑
∑
41
Nakład obliczeń
transformaty Fouriera
N
N
2
(FT) NlogN
(FFT)
Zysk
N/logN
16
256
64
4
256
65535
2048
32
512
262144
4608
64
2048
~4e6
22528
186
42
Transformacja Fouriera obrazów
Redukcja zakłóceń obrazu przeprowadzona
w dziedzinie częstotliwości
FFT
IFFT
43
(
)
(
)
(
)
(
)
+
+
=
∑∑
−
=
−
=
N
y
v
cos
N
x
u
cos
y
,
x
f
N
v
,
u
F
N
i
N
k
2
1
2
2
1
2
2
1
0
1
0
π
π
Transformacja kosinusowa
1
2
1
−
=
N
,
,
,
v
,
u
K
dla:
-N
-N
N-1
N-1
oryginał
Widmo Fouriera funkcji
rzeczywistej i symetrycznej
posiada rzeczywiste
współczynniki, tj. tylko
współczynniki związane z
kosinusowymi wyrazami
szeregu Fouriera.
44
Transformacja kosinusowa
Funkcje bazowe
przekształcenia
kosinusowego
o wymiarze 8x8
45
obraz ‘autumn’
transformata kosinusowa
(0,0)
szybkie zanikanie
współczynników
Standard kompresji obrazów JPEG
wykorzystuje transformację kosinusową
Transformacja kosinusowa
46
Inne transformacje obrazów
transformacja Karhunena-Loevego, zwana
też transformacją
PCA (ang. Principal
Component Analysis)
transformacja falkowa
obrazu, wykorzystywana
w nowym standardzie
kompresji JPEG-2000
eigenfaces
©AT&T Labs
47
Inne transformacje obrazów
JPEG 0.1
JPEG 0.1
bpp
bpp
8
8
bpp
bpp
Playboy Magazine
Wavelet
Wavelet
0.1
0.1
bpp
bpp
JPEG-2000
Wyszukiwarka
Podobne podstrony:
5 Przekształcenie Fouriera
6 i 7 Właściwości przekształcenia Fouriera
Przekształcenie Fouriera narzedzie nie tylko analizy przebiegów schodkowych
Dyskretne przekształcenie Fouriera
Dyskretne Przekształcenie Fouriera, WAT, SEMESTR V, Cfrowe przetwarzanie sygnałów, Cps, od borysa, C
5 Przekształcenie Fouriera
Dyskretne przekształcenie Fouriera, cz 1
6 i 7 Właściwości przekształcenia Fouriera
Dyskretne przekształcenie Fouriera, cz 4
Dyskretne przekształcenie Fouriera, cz 2
Dyskretne przekształcenie Fouriera, cz 3
Dyskretne przeksztaĹ'cenie Fouriera
Diagnostyka obrazowa Podstawowe przeksztalcenia obra
Dyskretne przeksztaĹ'cenie Fouriera
Przeksztalcanie wzorow
więcej podobnych podstron