Transformada De Fourier

UNIVERSIDADE FEDERAL DE MATO GROSSO INSTITUTO DE COMPUTAÇÃO CURSO DE CIÊNCIA DA COMPUTAÇAO DISCIPLINA: PROCESSAMENTO DE IMAGENS PROFESSOR: JOÃO PAULO RIBAS

Relatório do Trabalho

Alunos: Lauro César Renato Gonçalves Túlio Rondon de Albuquerque

Cuiabá, 10 de maio de 2009.

2

Sumário Lista de Figuras ---------------------------------------------------------------------------------

3

Introdução ---------------------------------------------------------------------------------------

5

Caracterização do Problema ------------------------------------------------------------------ 11 Resultados --------------------------------------------------------------------------------------

12

Análise dos Resultados ------------------------------------------------------------------------ 19 Conclusão --------------------------------------------------------------------------------------- 19 Referências Bibliográficas -------------------------------------------------------------------- 20 Anexos ------------------------------------------------------------------------------------------- 21

3

1.Lista de Figuras

Fig. 1: Utilização de técnicas de processamento de imagens na aproximação de imagens de satélites ---------5 Fig. 2: Ponto (pixel) f(x,y) no Plano (x,y) --------------------------------------------------------------------------------6 Fig. 3: Transformada de Fourier ------------------------------------------------------------------------------------------6 Fig. 4: Transformada Inversa de Fourier --------------------------------------------------------------------------------7 Fig. 5: Função para Transformada Discreta de Fourier ---------------------------------------------------------------7 Fig. 6: Função para Transformada Discreta Cosseno -----------------------------------------------------------------8 Fig. 7: Comparação entre DFT e DCT -----------------------------------------------------------------------------------8 Fig. 8: Transformada utilizando FFT -------------------------------------------------------------------------------------9 Fig. 9: Transformada utilizando separalidade --------------------------------------------------------------------------9 Fig. 10: Função para convolução ----------------------------------------------------------------------------------------10 Fig. 11: Teorema da convolução -----------------------------------------------------------------------------------------10 Fig. 12: lenna256.bm ------------------------------------------------------------------------------------------------------12 Fig. 13: boa256t.bmp ------------------------------------------------------------------------------------------------------12 Fig. 14: bridge.tif -----------------------------------------------------------------------------------------------------------12 Fig. 15: câmera.tif ----------------------------------------------------------------------------------------------------------13 Fig. 16: Comparação entre os espectros obtidos na imagem lena256.bmp ----------------------------------------13 Fig. 16 (a): Espectro logarítmico – DFT-2D ---------------------------------------------------------------------------13 Fig. 16 (b): Espectro logarítmico – FFT2 ------------------------------------------------------------------------------13 Fig. 16 (c): Espectro centralizado – DFT-2D --------------------------------------------------------------------------13 Fig. 16 (d): Espectro centralizado – FFT2 -----------------------------------------------------------------------------13 Fig. 17: Comparação entre os espectros obtidos na imagem boa256t.bmp ----------------------------------------14 Fig. 17 (a): Espectro logarítmico – DFT-2D ---------------------------------------------------------------------------14 Fig. 17 (b): Espectro logarítmico – FFT2 ------------------------------------------------------------------------------14 Fig. 17 (c): Espectro centralizado – DFT-2D --------------------------------------------------------------------------14 Fig. 17 (d): Espectro centralizado – FFT2 -----------------------------------------------------------------------------14 Fig. 18: Comparação entre os espectros obtidos na imagem bridge.tif --------------------------------------------15 Fig. 18 (a): Espectro logarítmico – DFT-2D ---------------------------------------------------------------------------15 Fig. 18 (b): Espectro logarítmico – FFT2 ------------------------------------------------------------------------------15 Fig. 18 (c): Espectro centralizado – DFT-2D ------------------------------------------------------------------------15

4 Fig. 18 (d): Espectro centralizado – FFT2 ----------------------------------------------------------------------------15 Fig. 19: Comparação entre os espectros obtidos na imagem câmera.tif -------------------------------------------16 Fig. 19 (a): Espectro logarítmico – DFT-2D ---------------------------------------------------------------------------16 Fig. 19 (b): Espectro logarítmico – FFT2 ------------------------------------------------------------------------------16 Fig. 19 (c): Espectro centralizado – DFT-2D --------------------------------------------------------------------------16 Fig. 19 (d): Espectro centralizado – FFT2 -----------------------------------------------------------------------------16 Fig. 20: lenna256.bmp – Transformada Discreta de Cosseno -------------------------------------------------------17 Fig. 21: boa256t.bmp – Transformada Discreta de Cosseno --------------------------------------------------------17 Fig. 22: bridge.tif – Transformada Discreta de Cosseno -------------------------------------------------------------17 Fig. 23: câmera.tif – Transformada Discreta de Cosseno ------------------------------------------------------------17 Fig. 24: Imagens que a convolução foi aplicada ----------------------------------------------------------------------18 Fig. 25: Resultado da convolução ---------------------------------------------------------------------------------------18 Fig. 25 (a): Convolução através da função Conv2 do MATLAB ----------------------------------------------------18 Fig. 25 (b): Convolução através do Teorema da Convolução -------------------------------------------------------18

5

2.Introdução Atualmente o interesse na área de processamento de imagens tem crescido muito, principalmente em aplicações como a melhoria da qualidade de imagens e o melhor processamento dos dados das imagens, aumentando muito o seu uso em áreas como programa espacial, medicina, arqueologia, física, astronomia, etc.

Fig. 1: Utilização de técnicas de processamento de imagens na aproximação de imagens de satélites

Processar uma imagem consiste em decompo-la sucessivamente com o objetivo de extrair mais facilmente a informação nela presente. Processar uma imagem, como é feito pelo sistema visual humano (SVH), é extremamente complexo, realizar as mesmas tarefas que o SVH, com a ajuda de máquinas, exige uma compreensão dos conhecimentos humanos. Esta característica faz com que o processamento de imagens seja, atualmente, uma disciplina dependente do sistema no qual ele está associado, não existindo uma solução única e sufuciente para todos os problemas. Por isso ainda não existem sistemas de análise de imagens complexos o suficiente para funcionarem em todos os casos. Quando falamos em “análise de imagens” falamos do tratamento da imagem ou também de parametrização é nela que várias medidas (parâmetros) são utilizadas para descrever diferentes informações dentro de uma imagem.

6 A 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”).

Fig. 2: Ponto (pixel) f(x,y) no Plano (x,y)

No processamento de imagens existem vários problemas, e existe uma ferramenta matemática muito usada na solução destes problemas, a transformada de Fourier, é utilizada em diversas áreas da ciência e tecnologia hoje em dia, desde a simples filtragem até a utilização na compressão de arquivos de imagem. Esta transformada é uma das maneiras de realizar uma mudança de domínio espacial em espectral (onde um sinal fica caracterizado por suas componentes de freqüência). A transformada de Fourier de uma função f(x) é definida como:

Fig. 3: Transformada de Fourier

7

Existe também a transformada inversa, que recupera a função original e é definida como:

Fig. 4: Transformada Inversa de Fourier

onde Wx é a 7alcular7i angular, e i ≡ raiz de – 1. A transformada de Fourier facilita a análise da imagem, mostrando a imagem decomposta em seus componentes de freqüência, permitindo identificar os aspectos mais comuns da imagem, como, por exemplo, suas texturas e contornos. Ele representa em cada ponto a informação daquela freqüência da imagem inteira. Isso permite filtrar, eliminar ou ampliar mais facilmente uma faixa específica de freqüência. A transformada de Fourier, é utilizada em várias áreas e para vários problema, cada utilização possui um tipo de transformada para melhor resolver o problema, as utilizadas neste trabalho são: •

DFT (Transformada Discreta de Fourier) – A Transformada Discreta de Fourier é muito usada no estudo do espectro de sinais e é determinada numericamente com o auxílio de computador digital. Possui valores x k discretos, para isso existe a versão da transformada para funções discretas.

Fig. 5: Função para Transformada Discreta de Fourier

•

DCT (Transformada Discreta Cosseno) – A transformada de DCT de uma imagem tem como propriedades que a informação visual mais importante é concentrada em apenas alguns coeficientes da DCT.

8

Na compressão os coeficientes mais significativos se acumulam no inicio da matriz dos dados, ficando o restante com pouca e pequenas informações, este tipo de distribuição é suficiente para utilizar técnicas de redução de ocorrência, porêm ocorre uma perda nos dados por causa da precisão finita nas representações numéricas. É a transformada mais utilizada nas principais normas internacionais de codificação de imagem – JPEG, H.261, MPEG-1, MPEG-2, H.263, MPEG-4. Sua fórmula é representada por:

Fig. 6: Função para Transformada Discreta Cosseno para 0 <= i, j <= n – 1

Fig. 7: Comparação entre DFT e DCT

•

FFT (Transformada Rápida de Fourier) – A Transformada Rápida de Fourier não é um tipo diferente de transformada, e sim um algoritmo que utiliza uma técnica que possibilita avaliar a

9 DFT (e sua inversa) de uma maneira mais rápida e eficiente gerando um menor esforço computacional. As Transformadas rápidas de Fourier são de grande importância em uma vasta gama de aplicações, de Processamento digital de sinais para a resolução de equações diferenciais parciais a algoritmos para multiplicação de grandes inteiros. O algoritmo baseia-se no chamado método de dobramentos sucessivos, onde podemos expressar a transformada de Fourier como sendo:

Fig. 8: Transformada utilizando FFT

Uma propriedade da transformada de Fourier é a separabilidade, que é utilizada para calcular uma transformada bi-dimensional com uma sucessão de duas transformadas unidimensionais.

Fig. 9: Transformada utilizando separalidade

ou seja:

onde

represente a transformada unidimensional de

sobre a coordenada Y,

mantendo-se X fixo. Utiliza-se também no processamento de imagens a convolução, que na matemática representa um operador que, a partir de duas funções produz uma terceira. Sua notação para f e g é f * g. É utilizada para operar junto com filtros. As convoluções são definidas no domínio contínuo, mas devido à necessidade de implementação por muitos dispositivos eletro-eletrônicos, o operador é discretizado, o que significa, em termos práticos, a alteração da integral pelo somatório. A definição de convolução para funções de domínio discreto é dada por:

10

.

Fig. 10: Função para convolução

O teorema da convolução diz que a transformada de Fourier de duas funções convoluídas no domínio do espaço é igual ao produto das transformadas das duas funções no domínio de Fourier, ou seja:

Fig. 11: Teorema da convolução

onde F(f) denota a transformada de Fourier de f. Como em geral a operação de convolução é mais complexa de calcular do que a transformada de Fourier, usa-se este teorema para calcular a convolução calculando-se a transformada das funções, sua multiplicação, e a transformada inversa. Este trabalho visa desenvolver algoritmos utilizando o MATLAB para a aplicação da DFT (Transformada Discreta de Fourier). Uma comparação dos resultados obtidos utilizando-se o algoritmo para o cálculo da DFT e o algoritmo FFT (Transformada Rápida de Fourier) presente no MATLAB também será apresentada. O algoritmo para cálculo da DCT (Transformada Discreta Cosseno), também presente no MATLAB, será aplicado a algumas imagens e os resultados serão mostrados. Um algoritmo para cálculo da convolução discreta também será desenvolvido e através dele, juntamente com o algoritmo da DFT, será demonstrado o teorema da convolução 2D na prática.

11

3.Caracterização do Problema

Este trabalho propõe o estudo das transformadas de Fourier mostradas na introdução, utilizando um programa próprio pra isto o MATLAB (Matrix Laboratory), que é um software de alta performance voltado para o cálculo numérico. O MATLAB abrange análises numéricas, cálculos com matrizes, processamentos de sinais e construções de gráficos em um ambiente próprio. Transformadas são fundamentais no estudo de processamento de imagens, logo esse estudo se torna essencial, no desenvolvimento do trabalho foram executadas as seguintes etapas: •

Implementação de uma função utilizando o MATLAB que calcule a DFT-2D de uma imagem digital utilizando a propriedade da separabilidade;

•

A apresentação dos espectros de Fourier e Cosseno em escala logarítmica e centralizada;

•

Uma comparação entre os resultados obtidos utilizando-se a função implementada e a função fft2 existente no MATLAB;

•

Uma demonstração prática do Teorema da Convolução 2D (caso discreto) seguindo os seguintes passos: a. Utilize duas imagens 256x256: f (x,y) e g (x,y); b. Aplique a função conv2 e obtenha f (x,y) * g (x,y); c. Aplique a função DFT-2D em f (x,y) e g (x,y) obtendo F (u,v) e G (u,v); d. Faça a multiplicação de F (u,v) com G (u,v); e. Aplique a IDFT em F (u,v) . G (u,v) e obtenha f (x,y) * g (x,y); f. Compare f (x,y) * g (x,y) obtido no item b com o obtido no item c.

12

4.Resultados A seguir apresentaremos as tabelas das imagens resultantes através da aplicação do algoritmo DFT-2D desenvolvido no MATLAB, a apresentação segue nos exemplos na seguinte ordem: na coluna da esquerda a imagem original, na coluna central o espectro de Fourier e na coluna da direita o espectro de Fourier centralizado.

Fig. 12: lenna256.bmp

Fig. 13: boa256t.bmp

Fig. 14: bridge.tif

13

Fig. 15: câmera.tif As tabelas abaixo apresentam, para uma análise, os resultados obtidos utilizando-se a função DFT-2D desenvolvida em MATLAB e a função fft2 já presente no mesmo programa. A exibição das imagens segue a seguinte ordem para todos os exemplos: na coluna da esquerda estão as imagens do espectro logarítmico de Fourier (acima) e do espectro centrado de Fourier (abaixo) obtidos pela função DFT-2D. Na segunda coluna, na mesma ordem, estão as imagens obtidas utilizando-se a função fft2. Fig. 16: Comparação entre os espectros obtidos na imagem lena256.bmp

Fig. 16 (a): Espectro logarítmico – DFT-2D

Fig. 16 (b): Espectro logarítmico – FFT2

Fig. 16 (c): Espectro centralizado – DFT-2D

Fig. 16 (d): Espectro centralizado – FFT2

14

Fig. 17: Comparação entre os espectros obtidos na imagem boa256t.bmp

Fig. 17 (a): Espectro logarítmico – DFT-2D

Fig. 17 (b): Espectro logarítmico – FFT2

Fig. 17 (c): Espectro centralizado – DFT-2D

Fig. 17 (d): Espectro centralizado – FFT2

15

Fig. 18: Comparação entre os espectros obtidos na imagem bridge.tif

Fig. 18 (a): Espectro logarítmico – DFT-2D

Fig. 18 (b): Espectro logarítmico – FFT2

Fig. 18 (c): Espectro centralizado – DFT-2D

Fig. 18(d): Espectro centralizado – FFT2

16

Fig. 19: Comparação entre os espectros obtidos na imagem câmera.tif

Fig. 19 (a): Espectro logarítmico – DFT-2D

Fig. 19 (b): Espectro logarítmico – FFT2

Fig. 19 (c): Espectro centralizado – DFT-2D

Fig. 19 (d): Espectro centralizado – FFT2

As tabelas abaixo apresentam os resultados obtidos através da aplicação da função DCT2 (para cálculo da Transformada de Cosseno). A exibição das imagens segue, para todos os exemplos, a seguinte ordem: na coluna da direita fica a imagem original, na coluna do meio fica a imagem em escala logarítmica após a aplicação da função e na coluna da direita fica a imagem em escala logarítmica centralizada (através da função fftshift).

17

Fig. 20: lenna256.bmp – Transformada Discreta de Cosseno

Fig. 21: boa256t.bmp – Transformada Discreta de Cosseno

Fig. 22: bridge.tif – Transformada Discreta de Cosseno

Fig. 23: câmera.tif – Transformada Discreta de Cosseno

18 Abaixo estão os resultados obtidos através da aplicação da função Conv2 existente no MATLAB e da aplicação do ‘Teorema da Convolução’ nas imagens. As imagens que passaram pela convolução já foram apresentadas neste trabalho, no entanto elas são reapresentadas na figura 19. Como a função de convolução gera uma matriz com números de grandeza muito grande, para visualização da imagem, os elementos da matriz resultante foram divididos por 800.000.000 (oitocentos milhões) para que fosse possível ver os efeitos da convolução.

Fig. 24: Imagens que a convolução foi aplicada

Fig. 25: Resultado da convolução

Fig. 25 (a): Convolução através da função Conv2 do MATLAB

Fig. 25 (b): Convolução através do Teorema da Convolução

19

5.Análise dos Resultados Observando os resultados, descobrimos que em todas as imagens, o algoritmo DFT-2D implementado pelos membros do grupo obteve os mesmos resultados do algoritmo FFT2 já desenvolvido pelo programa MATLAB. A função fffshift permitiu obter o espectro centralizado, essa função é ótima para análise dos espectros gerados pela Transformada, pois ela permite enxergar a concentração de energia das fotos. A DCT apresentou espectros diferentes em relação aos espectros obtidos na DFT, ao utilizar a função fffshift para centralizar o espectro gerado, os pixels de nível mais baixo apareceram com maior freqüência na parte inferior direita da imagem (dividindo-se a imagem em quatro partes iguais a partir do centro horizontal e vertical). As experiências feitas com as imagens utilizando a convolução (função Conv2 do MATLAB) e o Teorema da Convolução geraram como resultado imagens iguais. As duas são obtidas usando a função ‘demonstrarConvolução’, como é apresentado no anexo 2.

6.Conclusão O trabalho descrito neste relatório apresentou exemplos gráficos e práticos da aplicação da Transformada de Fourier em 4 imagens de dimensões 256x256 utilizando o software MATLAB, que é uma ferramenta específica e muito boa para trabalhar com processamento de imagens, pois já possui funções implementadas (facilitando o desenvolvimento de algoritmos) e possui uma facilidade no trabalho com elementos do tipo matriz. Apesar de obter as mesmas imagens do algoritmo da FFT (já implementado no MATLAB) com o algoritmo desenvolvido pelos alunos da DFT, é muito mais recomendado se utilizar o algoritmo da FFT, uma vez que este possui uma complexidade menos, resultando em um tempo de execução menor, ponto este fundamental no desenvolvimento de algoritmos. Provamos o Teorema da Convolução através da função FFT2, uma vez que as imagens resultantes tanto pela função da convolução (conv2) quanto pela transformada inversa da multiplicação das transformadas diretas de duas funções são iguais. Porem, vale lembrar que o Teorema da Convolução utilizando a FFT é a forma mais eficiente de se aplicar a convolução em duas imagens.

20

Este trabalho nos proporcionou a descoberta de um grande número de conhecimentos, já que a área de processamento de imagens abrange um número enorme de conceitos e técnicas de desenvolvimento, que poderão ser muito úteis no futuro.

7.Referência Bibliográfica

MACHADO, Kleber Daum. Equações Diferenciais Aplicadas à Física. 2ª Edição. Local: Editora UEPG, 2000; Transformada de Fourier, disponível em , acessado em 05/05/2009; Transformada Discreta de Cosseno, disponível em , acesso em 05/05/2009; Processamento Digital de Imagens no Domínio da Freqüência, disponível em , acessado em 05/05/2009; Transformada de Fourier, disponível em , acessado em 05/05/2009.

21

8.Anexos Anexo1: TransformadadeFouriercomseparabilidade 1 Transformada Discreta de Fourier (DFT) com Separabilidade 2 % Autores: Lauro César 3 % Renato Lustre 4 % Túlio Rondon 5 6 % param imagem - A imagem que deseja-se "transformar" 7 % param tipo - 1 para DFT e 0 para a inversa (IDFT) 8 % return ImageRes - A Imagem resultante 9 function ImageRes = dft2(imagem,tipo) 10 11 % captura a dimensao da imagem 12 [dimensao,dimensao]=size(imagem); 13 14 % inicializacao das variaveis 15 imagem=double(imagem); 16 nivelDeCinza=0; 17 res=0; 18 ImagemAux=zeros(dimensao,dimensao); 19 ImageRes=zeros(dimensao,dimensao); 20 21 % Define se sera DFT ou IDFT 22 23 if tipo==1 24 imaginario=-j; 16 25 elseif tipo==0 26 imaginario=j; 27 else 28 error ('Voce nao digitou um tipo valido. Digite 1 para DFT e 0 para IDFT'); 29 end 30 31 %Somatorio interno. 32 for v=0:(dimensao-1), 33 for x=(0:dimensao-1), 34 for y=0:(dimensao-1), 35 nivelDeCinza=imagem(x+1,y+1); 36 res=nivelDeCinza*exp((imaginario*2*pi*v*y)/dimensao)+res; 37 end 38 ImagemAux(x+1,v+1)=res;

22 39 res=0; 40 end 41 end 42 terminouPrimeiraParte=-1 43 somatorio=0; 44 % Somatorio Externo 45 for u=0:dimensao-1, 46 for v=0:dimensao-1, 47 for x=0:dimensao-1, 48 somatorio=ImagemAux(x+1,v+1)*exp((imaginario*2*pi*u*x)/dimensao)+somatorio; 49 end 50 ImageRes(u+1,v+1)=somatorio; 51 somatorio=0; 52 end 53 end 54 Return Anexo 2: Demonstração do Teorema da Convolução 1 % Demonstracao do Teorema da Convolucao 2 % Autores: Lauro Cesar 3 % Renato Gonçalves 4 % Túlio Rondon 5 6 %Etapas: 7 % 1) Aplique a funcao de convolucao e obtenha f(x,y)*g(x,y) 8 % 2) Aplique a funcao da DFT-2D em f(x,y) e g(x,y) obtendo, F(u,v) e G(u,v) 9 % 3) Multiplique F(u,v) por G(u,v) 10 % 4) Aplique a IDFT em F(u,v).G(u,v) e obtenha f(x,y)*g(x,y) 11 % 5) Compare f(x,y)*g(x,y) obtido na etapa 1 c/ o obtido na etapa 4 12 13 14 15 function [convolucao,imagemres] = demonstrarConvolucao(imagem1,imagem2) 16 [tamanho,tamanho]=size(imagem1); 17 dobro=tamanho*2; 18 19 convolucao=conv2(imagem1,imagem2); % etapa 1) 20 21 %inicio da etapa 2) 22 img1=imagem1; 23 img2=imagem2; 24 img1(1:dobro-1,dobro-1)=0; 25 img2(dobro-1,1:dobro-1)=0; 26 27 img1fft = fft2(img1); 28 img2fft = fft2(img2); 29 %fim da etapa 2) 30 31 multi = img1fft.*img2fft; % etapa 3)

23 32 multi = ifft2(multi); % etapa 4) 33 34 imagemres = (abs(multi)); 35 return Anexo 3: Função para exibir as imagens obtidas 1 %Funcao para tratar as imagens geradas pela funcao dft2 2 %Autores: Lauro Cesar 3 % Renato Gonçalves 4 % Túlio Rondon 5 6 %funcao mostrarImagem 7 %param imagem A imagem que deseja-se exibir 8 %param param Indica o modo que deseja exibir. Modos disponiveis: 9 % 0 - Espectro de Fourier Logaritmico 10 % 1 - Espectro de Fourier Logaritmico com escala 11 % 2 - Espectro de Fourier Logaritmico centralizado 12 % 3 - Espectro de Fourier Logaritmico centraliza com escala 13 14 function ImagemResultante = mostrarimagem(imagem,param) 15 16 espectroLogaritmico=log(abs(imagem)+1); %0 17 especLogaritmicoComEscala=(uint8(espectroLogaritmico*(255/max(espectroLogaritmico(:)) ))); %1 18 espectroLogaritmicoCentralizado=fftshift(espectroLogaritmico); %2 19 centralizadoComEscala=(uint8(espectroLogaritmicoCentralizado*(255/max(espectroLogarit mico(:))))); %3 20 21 if param == 0 22 ImagemResultante=espectroLogaritmico; 23 elseif param == 1 24 ImagemResultante=especLogaritmicoComEscala; 25 elseif param == 2 26 ImagemResultante=espectroLogaritmicoCentralizado; 27 elseif param ==3 28 ImagemResultante = centralizadoComEscala; 29 else 30 error('Voce nao digitou um valor valido (0,1,2,3)'); 31 end 32 33 imShow(ImagemResultante); 34 return;