TRANSFORMADA DE FOURIER PROCESSAMENTO DE IMAGENS DIGITAIS Matemática Aplicada

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

UNIVERSIDADE FEDERAL DO MARANHÃO
CENTRO DE CIÊNCIAS EXATAS E TECNNOLOGIA
DEPARTAMENTO DE INFORMÁTICA
CURSO DE CIÊNCIA DA COMPUTAÇÃO
MATEMÁTICA APLICADA
TRANSFORMADA DE FOURIER
PROCESSAMENTO DE IMAGENS DIGITAIS
Mayckerson Alexandre Franco Santos CP99111-19 
São Luís
2007�
Transformada de Fourier
PROCESSAMENTO DE IMAGENS DIGITAIS
Introdução 
A transformada de Fourier é extensivamente usada em teoria de informação, processo notável e processamento de imagem. A derivação de teoria da transformada de Fourier não é considerada aqui, mas exemplos de sua utilidade no melhoramento de imagem são discutidos. 
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.
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" ("picture elements"). 
Devido à gama de utilizações de tal ferramenta e à sua importância em processamento de imagens, uma implementação eficiente pode ajudar em muito qualquer um dos estudos acima.
Embora os algoritmos que implementam a transformada de Fourier sejam relativamente compactos e simples, possuem um número gigantesco de operações complexas, o que torna extremamente lenta a execução em grandes resoluções. Sendo assim, este trabalho propõe estudar a implementação de uma técnica de transformada de Fourier que trabalha separadamente com cada dimensão.
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. 
Na prática, a utilização de algoritmos para execução rápida das transformadas de Fourier (FFT) juntamente com os teoremas de convolução e da correlação permitem, de maneira simplificada, a 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. 
A teoria da transformada de Fourier assume que o sinal é contínuo com uma extensão infinita, para o qual a transformada é desejada. Por outro lado, imagens são freqüentemente descontínuas ao longo de uma linha ou coluna da imagem. Para analisar dados de pixel de uma imagem contínua a versão discreta de transformada de Fourier foi desenvolvida e foi chamada de transformada rápida de Fourier (FFT). Esta implementação é a base para a maioria de algorítmos de processamento de imagens usando transformada de Fourier. 
Qualquer imagem pode ser representada por uma transformada de Fourier bi-dimensional, a qual pode ser considerada como uma imagem com uma parte real e uma parte complexa. A bi-dimensional FFT é um mapeamento de valores de pixel de imagem no espaço de freqüência da imagem espacial. Executando a bi-dimensional FFT em uma imagem, cria-se um mapa bi-dimensional de todas as freqüências de espaço dentro de uma imagem. 
A Transformada de Fourier (FT) é uma ferramenta largamente empregada em processamento de sinais, processamento de sons e em processamento de imagens. Denominada assim em homenagem ao físico francês Jean Baptiste Joseph Fourier (1768-1830), a FT decompõe um sinal em suas componentes elementares seno e cosseno. A FT aplicada a uma imagem no domínio espacial gera uma informação no domínio da freqüência, em que cada ponto, definido por um vetor do tipo (k.cosseno, k.seno), representa uma dada freqüência contida no domínio espacial da imagem. 
As aplicações referentes à FT são inúmeras: filtragem, segmentação, reconhecimento de padrões, descrição de imagens, compressão e reconstrução constituem algumas delas.
A transformada de Fourier representa a soma de uma série de formas de onda senoidais com diferentes amplitudes, fase e frequência. Pode ser uma utilizada em processamento digital de imagens quando queremos conhecer frequências espaciais de um determinado padrão. 
Entretanto, a transformada pode ser utilizada também na reconstrução bi-dimensional de imagens em geral, por sua facilidade e rapidez de cálculo, comparado com a resolução das equações de projeção algebricamente, que consistem na montagem de uma matriz e sua resolução.
Na prática, quando queremos trabalhar uma imagem no domínio da freqüência, por exemplo, simplesmente fazemos a transformada de Fourier da referida imagem e a multiplicamos pela função de transferência de um filtro (convenientemente de acordo com a aplicação) no entanto, muitas vezes, é mais simples "zerarmos" os coeficientes das componentes de freqüência que queremos filtrar e tomamos, em seguida, em ambos os casos, a transformada inversa obtendo, assim, a imagem filtrada (processada). Quando zeramos os coeficientes da transformada de Fourier a partir de um certo valor, obtemos um filtro passa-baixa, ou até um certo valor, temos um filtro passa-alta, ou entre dois valores de freqüência, um filtro passa-faixa ou rejeita-faixa. 
A função transformada de Fourier
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.
Para n variando de 0 a N-1, a duração do sinal é:
A DFT de x(n) é definida pela soma finita:
onde:
A função X(m) gera m variáveis no domínio da freqüência com incremento . 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. 
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. 
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 . 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 metade dos componentes são coincidentes, logo, apenas N/2 componentes espectrais complexos são significativos. Tais componentes são incrementados de e m=0 corresponde à componente DC, m=1 é a fundamental, m=2 é o segundo harmônico, etc. Para evitar a sobreposição espectral, a taxa de amostragem deve ser maior ou igual ao dobro da maior freqüência do espectro, ou seja, se a maior freqüência for fm, o máximo intervalo entre as amostras deve satisfazer: .
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:
onde
:
.
O seguinte algoritmo desenvolve a Cooley- Turkey radix-2 FFT.
a : = a o r n
for 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.
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.
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).
O cálculo de t(2i)j(l) é simplesmente cinco condições de verificação para saber qual parte da função será calculada, sendo que isto pode ser facilmente implementado utilizando as funções switch/case da linguagem C.
A FFT Bidimensional
Como já vimos, podemos calcular uma DFT bidimensional através de duas DFT unidimensionais. Analogamente, se quisermos a DFT bidimensional de uma determinada imagem utilizando o mesmo procedimento de DFT unidimensionais, devemos aplicar à imagem a formulação algébrica da FFT unidimensional em simples sucessão.
Contudo, para se executar as operações e especificadas pelo algoritmo, torna-se necessário estender a função pn e ao padrão t(p) para parâmetros bidimensionais. Para isso, supomos que X=Zm x Zn, onde n=2h e n=2k, n £ m.
A permutação p é estendida à função r:X® X de maneira similar, restringindo suas ações para as linhas de X, definimos:
rm:X® X
by rm(i,j)=(pm(i),j).
Com as definições de r e t completas, podemos especificar a FFT bidimensional em termos da notação de álgebra de imagem.
Se X, rm e t são especificados acima e aÎ Cx, então o seguinte algoritmo calcula a FFT bidimensional de a.
a:=a o rm 
for i:=1 to log2m loop
a:=aÅ t(2i-1)
end loop
a:=a’ o rn
for i:=1 to log2n loop
a:=aÅ t(2i-1)
end loop
â:=a’.
Formulação Algébrica da Imagem Alternada
A formulação da FFT assume que a operação do modelo da imagem Å é somente aplicada sobre o suporte do modelo.
Se não for este o caso, a "rápida" formulação usando modelos resultará em uma performance muito pobre.
A formulação algébrica da imagem para a transformada rápida usa transformadas espaciais melhor do que modelos.
A formulação alternada é mais apropriada se a implementação de Å não restringe sua própria operação para o suporte de modelo.
Para a formulação alternada, as variáveis da bi-dimensional FFT permanecem como definido acima.
As imagens wi Î Cx usadas na formulação alternada são definidas como:
A formulação alternada para a transformada rápida de Fourier usando transformadas espaciais é dada por:
a : = a o rm
for i : =1 to log2m loop
a : = a o gi + wi . (a o fi)
end loop
a : = a´ o rn
for i : = 1 to log2n loop
a : = a o gi + wi . (a o fi)
end loop
â : = a´.
Com relação ao algoritmo acima, pode-se concluir que "a" corresponde a uma linha, "log2m" é o número de colunas que esta linha possui, "a’ " corresponde a esta mesma linha "a" só que em colunas (transposta de "a") e "log2n" é o de linhas que esta coluna possui.
Note que o uso da transposta a’ antes e depois do segundo loop no algoritmo acima é usado para notação simplificada, não para eficiência computacional. O uso das transpostas pode ser eliminado pelo uso de funções análogas fi, gi e wi no segundo loop que são funções de coluna coordenada de X.
A discussão presente aqui concentra-se em uma otimização geral algébrica da transformada de Fourier. Importantes regras surgem quando otimizando a formulação para específicas implementações. O cálculo da função permutação r n, adiciona o custo computacional da FFT. Cada iÎ {0, 1, ..., n-1}, r n(i) requer O(log2n) operações inteiras. A quantia de aritmética inteira envolvida no processamento de r n é da mesma ordem de magnitude da importância de ponto aritmético real para a FFT. Em conseqüência, associado acima com o bit reverso não é trivial no processamento da FFT, freqüentemente em torno de 10% a 30% do total de tempo de processamento.
Conclusão
Após a verificação de cada um dos métodos apresentados, sua complexidade de implementação e eficiência para o cálculo, fica claro que o método a se implementar deve ser a transformada rápida de Fourier (Fast Fourier Transform).
A complexidade destes algoritmos é relativamente grande, porém com a unidimensional FFT podemos ter a base e compreender o princípio da formulação dos algoritmos da bidimensional FFT, já que esta é uma aplicação da unidimensional FFT nos eixos X e Y. A FFT- é uma conseqüência da FFT.
Aperfeiçoamentos e otimizações dos algoritmos ainda podem ser estudados, porém já é possível prever uma implementação satisfatória destas funções com os métodos e algoritmos propostos.
�