Embed Size (px)
DESCRIPTION
Transformação de Imagens. Paulo Sérgio Rodrigues PEL205. Qual a complexidade algoritmica para implementar o par de equações?. Transformada Rápida de Fourier (FFT). Resposta: O(N 2 ) para u, x = 0,1,2,...,N-1. Supomos N = 2 n , para um n qualquer inteiro positivo. - PowerPoint PPT Presentation
Citation preview
ComputerVision
Transformação de Imagens
Paulo Sérgio RodriguesPEL205
ComputerVision
Transformada Rápida de Fourier (FFT)
Qual a complexidade algoritmica para implementar o par de equações?
1
0
/21 N
x
NujexfN
uF
1
0
/2N
u
NujeuFxf
Resposta: O(N2) para u, x = 0,1,2,...,N-1
ComputerVision
Transformada Rápida de Fourier (FFT)
Supomos N = 2n, para um n qualquer inteiro positivo
Então, N = 2M, para um M qualquer inteiro positivo
Assim,
1
0
2
)(1)(N
x
Nuxj
exfN
uF
12
0
22
)(2
1)(M
x
Muxj
exfM
uF
ComputerVision
Transformada Rápida de Fourier (FFT)
12
0
22
)(21)(
M
x
Muxj
exfM
uF
1
0
21221
0
2)2(2
1212121 M
x
u
MxjM
x
u
Mxj
exfM
exfM
uF
1
0
2221
0
2
1212121 M
x
u
Mjux
MjM
x
ux
Mj
eexfM
exfM
uF
ComputerVision
Transformada Rápida de Fourier (FFT)para u = 0,1,2...,M-1
1
0
2221
0
2
1212121 M
x
u
Mjux
MjM
x
ux
Mj
eexfM
exfM
uF
Fpar(u) Fimpar(u)
u
Mj
iparpar euFuFuF 22
21
ComputerVision
Transformada Rápida de Fourier (FFT)
para u = 0,1,2...,M-1
1
0
2221
0
2
1212121 M
x
Mu
MjxMu
MjM
x
xMu
Mj
eexfM
exfM
MuF
1
0
2221
0
2
1212121 M
x
u
Mjux
MjM
x
ux
Mj
eexfM
exfM
uF
para u + M = 0+M, 1+M, 2+M, ..., M-1+M
ComputerVision
Transformada Rápida de Fourier (FFT)
1
0
2221
0
2
1212121 M
x
Mu
MjxMu
MjM
x
xMu
Mj
eexfM
exfM
MuF
Fpar(u) Fimpar(u)1 1 -1
u
Mj
imparpar euFuFMuF 22
21
1
0
22
22221
0
22
1212121 M
x
M
Mju
MjMx
Mjux
MjM
x
Mx
Mjux
Mj
eeeexfM
eexfM
MuF
ComputerVision
Transformada Rápida de Fourier (FFT)
u
Mj
imparpar euFuFMuF 22
21
u
Mj
imparpar euFuFuF 22
21
para u = 0,1,2...,M-1
ComputerVision Translação
Um “problema” para visualizar o espectro de Fourier deUma função f(x,y) é o fato do pico mais alto ocorrer no eixo x = 0
ComputerVision Exemplo
Suponha calcular a FFT para a seqüência f de N = 8 pontosonde f = (f(0),f(1),...,f(7))
FFT de 8 pontos(f(0),f(1),f(2),f(3),f(4),f(5),f(6),f(7))
f(0),f(2),f(4),f(6) f(1),f(3),f(5),f(7)
f(0),f(4) f(2),f(6) f(1),f(5) f(3),f(7)
Complexidade da FFT: O(log(n)) onde n é o número de pontos de f(x)
