Computer
Vision
Transformação de Imagens
Paulo Sérgio Rodrigues
PEL205
Computer
Vision
Transformada Rápida de Fourier (FFT)
Qual a complexidade algoritmica para implementar o par de equações?
1 N 1
 j 2u / N
F u    f x e
N x 0
N 1
f x    F u e
j 2u / N
u 0
Resposta: O(N2) para u, x = 0,1,2,...,N-1
Computer
Vision
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 N 1
F (u)   f ( x)e
N x 0
1
F (u) 
2M
j 2ux
N
2 M 1

x 0
f ( x)e
 j 2ux
2M
Computer
Vision
Transformada Rápida de Fourier (FFT)
1
F (u) 
2M
1 1
F u   
2 M

1 1
F u   
2 M

2 M 1

x 0

f 2 x  e

x 0

M 1

f 2 x  e

x 0

M 1
f ( x)e
 j 2ux
2M
 j 2 ( 2 x )
2M
 j 2
M
ux
u

1
 
 M


1
 

M


f 2 x  1 e

x 0

M 1

f 2 x  1 e

x 0

M 1
 j 2
M
 j 2 2 x 1
2M




ux

e






 j 2
2M
u







u



Computer
Vision
Transformada Rápida de Fourier (FFT)
para u = 0,1,2...,M-1
1 1
F u   
2 M


f 2 x  e

x 0

M 1
Fpar(u)
 j 2
M
ux

1
 

M


f 2 x  1 e

x 0

M 1
 j 2
M




ux

e


Fimpar(u)

1
F u    Fpar u   Fipar u  e
2


 j 2
2M




u



 j 2
2M




u



Computer
Vision
Transformada Rápida de Fourier (FFT)
para u = 0,1,2...,M-1
1 1
F u   
2 M


f 2 x  e

x 0

M 1
 j 2
M
ux

1
 

M


f 2 x  1 e

x 0

M 1
 j 2
M




ux

e






u
u  M 



 j 2
2M
para u + M = 0+M, 1+M, 2+M, ..., M-1+M
1 1
F u  M   
2 M

  Mj2
f 2 x  e

x 0

M 1




u  M x
  Mj2
1

f 2 x  1 e

M x 0

M 1




u  M x
 2jM2
e









Computer
Vision
Transformada Rápida de Fourier (FFT)
1 1
F u  M   
2 M

1 1
F u  M   
2 M


f 2 x  e

x 0

M 1
  Mj2
f 2 x  e

x 0

M 1
Fpar(u)




ux
 j 2
M




  Mj2
e


1
u  M x




Mx
1

M
1

M
 j 2
M




  Mj2
e







f 2 x  1 e

x 0

M 1
  Mj2
f 2 x  1 e

x 0

M 1
Fimpar(u)




ux
u  M x
Mx
 2jM2
e


1
 2jM2
1
F u  M    Fpar u   Fimpar u  e
2



e






 j 2
2M
u




u  M 
 2jM2
e


-1




u







M






Computer
Vision
Transformada Rápida de Fourier (FFT)

1
F u    Fpar u   Fimpar u  e
2


 j 2
2M







u




 j 2


1
F u  M    Fpar u   Fimpar u  e 2 M
2


para u = 0,1,2...,M-1
u



Computer
Vision
Translação
Um “problema” para visualizar o espectro de Fourier de
Uma função f(x,y) é o fato do pico mais alto ocorrer no eixo x = 0
Computer
Vision
Exemplo
Suponha calcular a FFT para a seqüência f de N = 8 pontos
onde 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(0),f(4)
f(2),f(6)
f(1),f(3),f(5),f(7)
f(1),f(5)
f(3),f(7)
Complexidade da FFT: O(log(n)) onde n é o número de pontos de f(x)