ROZ1 - Cv. 2 - Fourierova transformace
´ UTIA - ZOI
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Vzoreˇ cky
Co to je FT?
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Vzoreˇ cky
Co to je FT? ◮
Transformace sign´ alu z ˇcasov´e (resp. obrazov´e) reprezentace f (t) do frekvenˇcn´ı reprezentace F (ψ) a zpˇet.
◮
D´ıky n´ı m˚ uˇzeme sign´ al analyzovat ve frekvenˇcn´ı oblasti
◮
Z´apis FT v 1D:
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Vzoreˇ cky
Co to je FT? ◮
Transformace sign´ alu z ˇcasov´e (resp. obrazov´e) reprezentace f (t) do frekvenˇcn´ı reprezentace F (ψ) a zpˇet.
◮
D´ıky n´ı m˚ uˇzeme sign´ al analyzovat ve frekvenˇcn´ı oblasti
◮
Z´apis FT v 1D: R∞ F (ξ) = −∞ f (t)ǫ−2πiξt dt
◮ ◮
Z´apis DFT v 1D:
FT
⇐⇒
f (t) =
R∞
−∞ F (ξ)ǫ
2πiξt dξ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Vzoreˇ cky
Co to je FT? ◮
Transformace sign´ alu z ˇcasov´e (resp. obrazov´e) reprezentace f (t) do frekvenˇcn´ı reprezentace F (ψ) a zpˇet.
◮
D´ıky n´ı m˚ uˇzeme sign´ al analyzovat ve frekvenˇcn´ı oblasti
◮
Z´apis FT v 1D: R∞ F (ξ) = −∞ f (t)ǫ−2πiξt dt
◮ ◮
◮
FT
⇐⇒
f (t) =
Z´apis DFT v 1D:
R∞
−∞ F (ξ)ǫ
2πiξt dξ
−2πikn DFT F (k) = n=0 f (n)ǫ N ⇐⇒ 2πikn 1 PN −1 f (n) = F (k)ǫ N N k=0 PN −1
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
K ˇcemu je FT dobr´a pˇri digit´aln´ım zpracov´an´ı obrazu?
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
K ˇcemu je FT dobr´a pˇri digit´aln´ım zpracov´an´ı obrazu?
◮
z´akladn´ı matematick´y n´ astroj
◮
odstranˇen´ı ˇsumu
◮
detekce hran
◮
segmentace
◮
rekonstrukce
◮
komprese obrazu
◮
detekce objekt˚ u
◮
atd.
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
Detekce hran ◮
Aplikace hranov´ych detektor˚ u ve frekvenˇcn´ı oblasti (filtr Prewittov´ e ) 1 1 1 0 0 0 −1 −1 −1
50
50
50
100
100
100
150
150
150
200
200
200
250
250
250
300
300
300
350
350
50
100
150
200
250
300
350
400
450
500
350
50
100
150
200
250
300
350
400
450
500
50
100
150
200
250
300
350
400
450
500
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
Detekce objekt˚ u v obraze
◮
Jde o aplikaci konvoluˇcn´ıho teor´emu: (f ∗ g)(t) = F (ψ)G(ψ)
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
Detekce objekt˚ u v obraze
◮
Jde o aplikaci konvoluˇcn´ıho teor´emu: (f ∗ g)(t) = F (ψ)G(ψ)
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
Detekce objekt˚ u v obraze
◮
Jde o aplikaci konvoluˇcn´ıho teor´emu: (f ∗ g)(t) = F (ψ)G(ψ)
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
Doostˇren´ı sc´eny ◮
I zde jde o aplikaci konvoluˇcn´ıho teor´emu:
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
Doostˇren´ı sc´eny ◮
I zde jde o aplikaci konvoluˇcn´ıho teor´emu:
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
Doostˇren´ı sc´eny ◮
I zde jde o aplikaci konvoluˇcn´ıho teor´emu:
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
N´aroˇcnost FT na v´ypoˇcet
◮
V´ypoˇcetn´ı n´aroˇcnost klasick´e DFT je:
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
N´aroˇcnost FT na v´ypoˇcet
◮
V´ypoˇcetn´ı n´aroˇcnost klasick´e DFT je:
◮
O(N 2 )
◮
V ˇcem spoˇc´ıv´a FFT?
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
N´aroˇcnost FT na v´ypoˇcet
◮
V´ypoˇcetn´ı n´aroˇcnost klasick´e DFT je:
◮
O(N 2 )
◮
V ˇcem spoˇc´ıv´a FFT?
◮
(Danielson, Lanczos, 1942): DFT posloupnosti d´elky N lze N vyj´adˇrit jako souˇcet dvou DFT posloupnost´ı d´elky 2 - v prvn´ı jsou lich´e a ve druh´e sud´e vzorky
◮
V´ypoˇcetn´ı n´aroˇcnost takov´e FFT je:
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Motivace
N´aroˇcnost FT na v´ypoˇcet
◮
V´ypoˇcetn´ı n´aroˇcnost klasick´e DFT je:
◮
O(N 2 )
◮
V ˇcem spoˇc´ıv´a FFT?
◮
(Danielson, Lanczos, 1942): DFT posloupnosti d´elky N lze N vyj´adˇrit jako souˇcet dvou DFT posloupnost´ı d´elky 2 - v prvn´ı jsou lich´e a ve druh´e sud´e vzorky
◮
V´ypoˇcetn´ı n´aroˇcnost takov´e FFT je:
◮
O(N log2 N )
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
Cviˇcen´ı I. ◮
Zobrazte amplitudu, f´ azi, re´ alnou i imagin´ arn´ı ˇc´ast - n´apovˇeda: fft2(), ifft2(), fftshift(), abs(), angle(), real(), imag(), log(), exp()
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı Ia. - amplituda Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı Ia. - amplituda Reˇ
◮
F=fft2(I); zobr(fftshift(log(abs(F)+1))); ´ UTIA - ZOI
ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı Ib. - f´aze Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı Ib. - f´aze Reˇ
◮
F=fft2(I); zobr(fftshift(angle(F))); ´ UTIA - ZOI
ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı Ic. - re´aln´a ˇc´ast Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı Ic. - re´aln´a ˇc´ast Reˇ
◮
F=fft2(I); zobr(fftshift(log(abs(real(F))+1))); ´ UTIA - ZOI
ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı Id. - imagin´arn´ı ˇc´ast Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı Id. - imagin´arn´ı ˇc´ast Reˇ
◮
F=fft2(I); zobr(fftshift(log(abs(imag(F))+1))); ´ UTIA - ZOI
ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
Cviˇcen´ı II.
◮
Zobrazte amplitudu FT ostatn´ıch sn´ımk˚ u - co lze vizu´alnˇe vysledovat?
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı II.a Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı II.b Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı II.c Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı II.d Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ Cemu se rovn´a fft2(Img) v bodˇ e (1,1)?
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ Cemu se rovn´a fft2(Img) v bodˇ e (1,1)?
◮
fft2(Img) == sum(Img(:))
◮
Proˇc?
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ Cemu se rovn´a fft2(Img) v bodˇ e (1,1)?
◮
fft2(Img) == sum(Img(:))
◮
Proˇc?
◮
F (0) =
PN −1 n=0
−2πi0n PN −1 f (n)ǫ N = n=0 f (n)
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
Cviˇcen´ı III. ◮
Zrekonstruujte sn´ımek jen z jeho f´ aze, amplitudy, re´aln´e a imagin´arn´ı ˇc´asti
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı IIIa. - z f´aze Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı IIIa. - z f´aze Reˇ
◮
F=fft2(I); zobr(abs(ifft2(exp(1i*angle(F))))); ´ UTIA - ZOI
ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı IIIb. - z amplitudy Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı IIIb. - z amplitudy Reˇ
◮
F=fft2(I); zobr(log(ifft2(abs(F))+1)); ´ UTIA - ZOI
ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı IIIc. - z re´aln´e ˇc´asti Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı IIIc. - z re´aln´e ˇc´asti Reˇ
◮
F=fft2(I); zobr(ifft2(real(F))); ´ UTIA - ZOI
ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı IIId. - z imagin´arn´ı ˇc´ast Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı IIId. - z imagin´arn´ı ˇc´ast Reˇ
◮
F=fft2(I); zobr(abs(ifft2(imag(F)))); ´ UTIA - ZOI
ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
Cviˇcen´ı IV.
◮
Zrekonstruujte sn´ımek ze dvou p˚ uvodn´ıch sn´ımk˚ u (I1, I2): 1. nakombinujete amplitudu z I1 a f´azi z I2 2. nakombinujete re´alnou ˇc´ast z I1 a imagin´arn´ı ˇc´ast z I2
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Zobrazen´ı FT
ˇ sen´ı - Cviˇcen´ı IV. Reˇ F1=fft2(I1); F2=fft2(I2); ad1.: zobr(abs(ifft2(abs(F1).*exp(1i*angle(F2))))); ad2.: zobr(ifft2(real(F1)+(1i*imag(F2))));
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Cviˇcen´ı V. ◮
Vytvoˇrte fci vracej´ıc´ı kruh: funciton K = kruh (R, N) % vrac´ı bin´arn´ı kruhovou masku o polomˇeru R v matici NxN
(1.56) kruh(4,10)
(1.57) kruh(50,150) ´ UTIA - ZOI
ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
ˇ sen´ı - Cviˇcen´ı V. Reˇ
funciton K = kruh (R, N) % vrac´ ı bin´ arn´ ı kruhovou masku o polomˇ eru R v matici NxN [X,Y]=meshgrid(-(N-1)/2:(N-1)/2, -(N-1)/2:(N-1)/2); K = double(X.b2 + Y.b2 < Rb2); end
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
ˇ ıslicov´a filtrace - jak´y je jej´ı princip? C´
◮
g =f +n
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
ˇ ıslicov´a filtrace - jak´y je jej´ı princip? C´
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Obrazov´a filtrace - Highpass & lowpass filtry
Highpass filtr
Lowpass filtr
50
50
100
100
150
150
200
200
250
250 50
100
150
200
250
50
100
150
200
250
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Cviˇcen´ı VI.
◮
Vyzkouˇsejte Highpass & Lowpass filtr na house.png:
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Cviˇcen´ı VI. ◮
Vyzkouˇsejte Highpass & Lowpass filtr na house.png:
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
ˇ sen´ı - Cviˇcen´ı VI. Reˇ
I=double(imread(’house.png’)); M=kruh(30,size(I,1)); M1=fftshift(∼M); M2=fftshift(M); FI=fft2(I); K1=FI.*M1; K2=FI.*M2; zobr(abs(ifft2(K1))); zobr(abs(ifft2(K2)));
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Cviˇcen´ı VIII. - Vynulov´an´ı kvadrant˚ u
- vynulujte u FT kvadrant (1.+3.) a (2.+4.) u slona co se stane?
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Cviˇcen´ı VIII. - Vynulov´an´ı kvadrant˚ u - vynulujte u FT kvadrant (1.+3.) a (2.+4.) u slona co se stane?
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Cviˇcen´ı IX. - Odstraˇnte poˇskozen´ı
- SVlnkama.pgm
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Cviˇcen´ı IX. - Odstraˇnte poˇskozen´ı
- SVlnkama.pgm
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Cviˇcen´ı VII. ◮
Vytvoˇrte fci poˇc´ıtaj´ıc´ı DFT: funciton V = dft(v) % vrac´ı vektor koeficient˚ u DFT(v) o d´elce length(I) vektor v
vektor koeficientù DFT(v)
4
15
3.5 3
10
2.5 2
5
1.5 1 1
2
3
4
5
6
0 1
2
3
4
5
6
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
ˇ sen´ı - Cviˇcen´ı VII. Reˇ
funciton K = dft(v) % V - vektor koeficient˚ u DFT(v) o d´ elce length(I) N = length(v); forK = 1:N F(K)=sum(P.*exp(-2*pi*i/N*(K-1)*[0:N-1])); end end
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
ˇ sen´ı - Cviˇcen´ı VII: dft([2 3 4 2 1 3]) Reˇ
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
Co jsme se dnes nauˇcili:
◮
V´ypoˇcet a zobrazen´ı FT - amplitudy, f´ aze, re´ aln´e a imagin´arn´ı ˇc´asti
◮
um´ıme filtrovat ve frekvenˇcn´ı oblasti
◮
naprogramovali jsme si DFT
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
FT
Cviˇ cen´ı FT
Filtrace
DFT
Z´ avˇ er
KONEC Dˇekuji za pozornost !
´ UTIA - ZOI ROZ1 - Cv. 2 - Fourierova transformace
