A Transformada de Fourier
Por: japantkd • 23/7/2015 • Trabalho acadêmico • 1.432 Palavras (6 Páginas) • 404 Visualizações
Transformada de Fourier
- Introdução
O interesse em métodos de processamento digital de imagens vem principalmente de duas áreas de aplicações: melhoria de informação (imagem) para interpretação humana, e processamento de dados (imagens) em computador, e vem crescendo com aplicações no Programa Espacial, na Medicina, Arqueologia, Física, Astronomia, Biologia, Indústria etc. [1]
O termo imagem refere-se a uma função de intensidade de luz bi-dimensional f(x,y), onde x e y são coordenadas espaciais e o valor de f em um ponto qualquer (x,y) é proporcional ao brilho ou nível de cinza da imagem naquele ponto. Uma imagem digital é uma imagem f(x, y) discretizada no espaço e na intensidade de brilho e pode ser considerada uma matriz, cujos elementos são chamados de "pixels”. [1]
- Transformada de Fourier
Com a evolução tecnológica e o desenvolvimento de computadores digitais de alta capacidade e velocidade de processamento, o processamento Digital de Imagens tem sido cada vez mais utilizado para análise e diagnósticos.Uma das ferramentas mais utilizada neste processamento é a transformada de Fourier, a qual nos permite ter uma visão da imagem a ser analisada no domínio da freqüência, facilitando sobremaneira esta análise e o seu processamento, normalmente, aplicando-se técnicas de filtragem digital. [1]
Na prática, a utilização de algoritmos para execução rápida das transformadas de Fourier (FFT) juntamente com os teoremas de convoluto e da correlação permitem, de maneira simplificada, implementação das técnicas de filtragens para eliminação de ruídos e interferências das imagens (ou de uma maneira geral, sinais) em análise. [1]
- A Função do FFT
A essência do cálculo da Transformada Rápida de Fourier (FFT) é uma série de operações matemáticas conhecida como Transformada Discreta de Fourier (DFT), que é um conjunto m de variáveis no domínio da freqüência a partir de um conjunto n de amostras no domínio do tempo. A figura abaixo ilustra um sinal x(n) com N amostras em intervalos de T segundos. [2]
Para n variando de 0 a N-1, a duração do sinal é:
[pic 1]
A DFT de x(n) é definida pela soma finita:
[pic 2]
Onde:
[pic 3]
A função X(m) gera m variáveis no domínio da freqüência com incremento [pic 4].
Para x(n) real com N amostras, um único espectro pode ser computado para N/2 pontos da freqüência. Na verdade, X(m) é uma função periódica em m com N pontos em cada período, mas apenas N/2 são únicos. [2]
Os algoritmos de FFT funcionam melhor quando o número de pontos da amostra é uma potência inteira de 2, ou seja: N=2k, onde k é um inteiro positivo. Um programa que utiliza FFT com a finalidade de análise espectral, apresenta certas particularidades na relação entre a DFT e a transformada contínua de Fourier. Em primeiro lugar, deve-se considerar que o tratamento matemático considera o sinal como se ele fosse periódico, embora o sinal possa ou não ser periódico. [2]
Um algoritmo para o cálculo da FFT deve levar em consideração alguns fatores básicos. Se tomarmos N=4096 amostras em um período, tendo-se o incremento entre cada amostra, então o período [pic 5]. O espectro obtido da DFT também será periódico e conterá 4096 componentes espectrais. Entretanto, se a amostragem em função do tempo for real, pode ser demonstrado que metades dos componentes são coincidentes, logo, apenas N/2 componentes espectrais complexos são significativos. [2]
Tais componentes são incrementados de [pic 6].
- Uni-Dimensional FFT
Sendo a Î CZn, onde n = 2k , para k inteiro positivo. Sendo P = {2i : i = 0,1,...,log2(n) –1} e pÎ P, define-se o modelo parametrizado t(p), por:
[pic 7]
Onde:
[pic 8].
O seguinte algoritmo desenvolve a Cooley- Turkey radix-2 FFT.
a : = a o r nfor i : = 1 to log2n loop
a : = a Å t(2i-1)
end loop
Adverte-se que a definição do modelo t gera dois valores para cada 0 <= j <= n-1. Desta forma, somente 2n multiplicações complexas e n somas complexas são requeridas para o desenvolvimento de a Å t(2i-1). Como a convolução a Å t(2i-1) está contida num loop de log2n interações, são O(log n) somas e multiplicações complexas na formulação da FFT. [2]
Esmiuçando um pouco mais o algoritmo descrito, isto é, convertendo todo o formalismo gráfico para simples algoritmo, temos o programa seguinte em C. Antes de iniciarmos, é importante definir que n é o numero máximo de pontos a calcular(deve ser uma potência de 2), que Vetor[i] me dá o valor do nível de cinza correspondente ao ponto e que i é a coordenada x deste ponto. [2]
A primeira linha do algoritmo corresponde a:
for (i=0; i<=(n-1);i++) {
j=0;
m=Vetor[i];
for (l=0; l<=(log2(n)-1);l++) {
h=m/2;
j=2j+m-2h
m=h;
}
Vetor[i]=j
}
O restante do programa corresponde a:
for (l=0; l<=n-1; l++) {
b=0;
for(i=0;i<=log2n;i++) {
for (j=0;j<=n-1;j++) {
t=t(2i)j(l)
b=b+Vetor[j]*t;
}
}
Vetor[l]=b;
}
Observe que temos a linha t=t(2i)j(l), função que já foi definida anteriormente. Porém, para calcularmos t(2i)j(l), utilizamos w(j,p), que deve ser subdividido em parte real e parte imaginária, e, portanto, a variável t, b e Vetor[l] do algoritmo devem possuir duas dimensões (uma para a parte real, outra para a parte imaginária). [2]
...