UNIVERSIDADE FEDERAL DE MATO GROSSOINSTITUTO DE COMPUTAÇÃO
CURSO DE CIÊNCIA DA COMPUTAÇAODISCIPLINA: 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.
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
2
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
3
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
4
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.
5
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
6
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.
7
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
8
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:
9
.
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.
10
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.
11
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
12
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
13
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
14
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
15
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).
16
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
17
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 Fig. 25 (b): Convolução através do Teorema Conv2 do MATLAB da Convolução
18
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.
19
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 <http://pt.wikipedia.org/wiki/Transformada_de_Fourier>,
acessado em 05/05/2009;
Transformada Discreta de Cosseno, disponível em
<http://pt.wikipedia.org/wiki/Transformada_Discreta_de_Cosseno>, acesso em 05/05/2009;
Processamento Digital de Imagens no Domínio da Freqüência, disponível em
<http://www.if.ufrgs.br/ast/med/imagens/node42.htm>, acessado em 05/05/2009;
Transformada de Fourier, disponível em <http://www.cs.unm.edu/~brayer/vision/fourier.html>,
acessado em 05/05/2009.
20
8.Anexos
Anexo 1: Transformada de Fourier com separabilidade
1 Transformada Discreta de Fourier (DFT) com Separabilidade2 % Autores: Lauro César3 % Renato Lustre4 % Túlio Rondon56 % 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 resultante9 function ImageRes = dft2(imagem,tipo)1011 % captura a dimensao da imagem12 [dimensao,dimensao]=size(imagem);1314 % inicializacao das variaveis15 imagem=double(imagem);16 nivelDeCinza=0;17 res=0;18 ImagemAux=zeros(dimensao,dimensao);19 ImageRes=zeros(dimensao,dimensao);2021 % Define se sera DFT ou IDFT22 23 if tipo==124 imaginario=-j;1625 elseif tipo==026 imaginario=j;27 else28 error ('Voce nao digitou um tipo valido. Digite 1 para DFT e 0 para IDFT');29 end3031 %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 end38 ImagemAux(x+1,v+1)=res;
21
39 res=0;40 end41 end42 terminouPrimeiraParte=-143 somatorio=0;44 % Somatorio Externo45 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 end50 ImageRes(u+1,v+1)=somatorio;51 somatorio=0;52 end53 end54 Return
Anexo 2: Demonstração do Teorema da Convolução
1 % Demonstracao do Teorema da Convolucao2 % Autores: Lauro Cesar3 % Renato Gonçalves4 % Túlio Rondon56 %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 412131415 function [convolucao,imagemres] = demonstrarConvolucao(imagem1,imagem2)16 [tamanho,tamanho]=size(imagem1);17 dobro=tamanho*2;1819 convolucao=conv2(imagem1,imagem2); % etapa 1)2021 %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;2627 img1fft = fft2(img1);28 img2fft = fft2(img2);29 %fim da etapa 2)3031 multi = img1fft.*img2fft; % etapa 3)
22
32 multi = ifft2(multi); % etapa 4)3334 imagemres = (abs(multi));35 return
Anexo 3: Função para exibir as imagens obtidas
1 %Funcao para tratar as imagens geradas pela funcao dft22 %Autores: Lauro Cesar3 % Renato Gonçalves4 % Túlio Rondon56 %funcao mostrarImagem7 %param imagem A imagem que deseja-se exibir8 %param param Indica o modo que deseja exibir. Modos disponiveis:9 % 0 - Espectro de Fourier Logaritmico10 % 1 - Espectro de Fourier Logaritmico com escala11 % 2 - Espectro de Fourier Logaritmico centralizado12 % 3 - Espectro de Fourier Logaritmico centraliza com escala1314 function ImagemResultante = mostrarimagem(imagem,param)1516 espectroLogaritmico=log(abs(imagem)+1); %017 especLogaritmicoComEscala=(uint8(espectroLogaritmico*(255/max(espectroLogaritmico(:))))); %118 espectroLogaritmicoCentralizado=fftshift(espectroLogaritmico); %219 centralizadoComEscala=(uint8(espectroLogaritmicoCentralizado*(255/max(espectroLogaritmico(:))))); %32021 if param == 022 ImagemResultante=espectroLogaritmico;23 elseif param == 124 ImagemResultante=especLogaritmicoComEscala;25 elseif param == 226 ImagemResultante=espectroLogaritmicoCentralizado;27 elseif param ==328 ImagemResultante = centralizadoComEscala;29 else30 error('Voce nao digitou um valor valido (0,1,2,3)');31 end3233 imShow(ImagemResultante);34 return;
23