35
Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM) Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012 Representando Imagens no Domínio da Frequência Percepções Iniciais da Transformada Discreta Bidimensional de Fourier Michel Alves dos Santos Universidade Federal de Alagoas, Campus A. C. Simões Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 Docente Responsável: Prof. Dr. Dimas Martinez {michel.mas}@gmail.com 12 de Novembro de 2012 Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Representing Images in Frequency Domain

Embed Size (px)

DESCRIPTION

The Fourier transform, named after Joseph Fourier, is a mathematical transform with many applications in physics and engineering. The Fourier Transform is an important image processing tool which is used to decompose an image into its sine and cosine components. The output of the transformation represents the image in the Fourier or frequency domain, while the input image is the spatial domain equivalent. In the Fourier domain image, each point represents a particular frequency contained in the spatial domain image.

Citation preview

Page 1: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Representando Imagens no Domínio da FrequênciaPercepções Iniciais da Transformada Discreta Bidimensional de Fourier

Michel Alves dos Santos

Universidade Federal de Alagoas, Campus A. C. SimõesTabuleiro do Martins - Maceió - AL, CEP: 57072-970Docente Responsável: Prof. Dr. Dimas Martinez

{michel.mas}@gmail.com

12 de Novembro de 2012

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 2: Representing Images in Frequency Domain

Podem ser solucionadosatravés do mesmo método!

A Transformada deFourier!

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Introdução

O que esses problemas possuem em comum?

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 3: Representing Images in Frequency Domain

Podem ser solucionadosatravés do mesmo método!

A Transformada deFourier!

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Introdução

O que esses problemas possuem em comum?

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 4: Representing Images in Frequency Domain

Podem ser solucionadosatravés do mesmo método!

A Transformada deFourier!

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Introdução

O que esses problemas possuem em comum?

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 5: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Objetivos da Apresentação

Principais Objetivos da Apresentação

I Introduzir a forma discreta da Transformada de Fourier.I Introduzir a representação de imagens no Domínio da Frequência.I Exibir algumas aplicações da Transformada em áreas diversas.

Figure: Representações no domínio da frequência da imagem Lenna: parte real,parte imaginária, magnitude ou espectro, ângulo fase e potência do espectro.Imagem em tons de cinza (8 bits) com 128 pixels de largura por 128 de altura.

Mas antes, vamos falar um pouco sobre o ‘pai’ dessa família de ferramentas!

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 6: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Objetivos da Apresentação

Principais Objetivos da Apresentação

I Introduzir a forma discreta da Transformada de Fourier.I Introduzir a representação de imagens no Domínio da Frequência.I Exibir algumas aplicações da Transformada em áreas diversas.

Figure: Representações no domínio da frequência da imagem Lenna: parte real,parte imaginária, magnitude ou espectro, ângulo fase e potência do espectro.Imagem em tons de cinza (8 bits) com 128 pixels de largura por 128 de altura.

Mas antes, vamos falar um pouco sobre o ‘pai’ dessa família de ferramentas!

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 7: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Jean Baptiste Joseph Fourier

Um Pouco Sobre Fourier

I Fourier nasceu em Auxerre, França, 1768.I Mais conhecido por seu trabalho ‘La

Théorie Analytique de la Chaleur’publicado em 1822.

I Traduzido para o Inglês em 1878: ‘TheAnalytic Theory of Heat’.

Uma das grandes contribuições de Jean Baptiste Joseph Fourier para ocampo de Processamento de Sinais foi a Transformada de Fourier.

Poucas pessoas prestaram a devida atenção aos seus trabalhos quandoforam publicados pela primeira vez.

Atualmente suas descobertas, figuram como as mais importantes teoriasmatemáticas da engenharia moderna.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 8: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Série e Transformada de Fourier

Princípios da Série e da Transformada de Fourier

I Série de Fourier: Qualquerfunção que se repita de maneiraperiódica pode ser expressacomo a soma de funções seno ecosseno de diferentesfrequências, cada qualmultiplicada por um coeficienteponderador.

I Transformada de Fourier:Funções não periódicas, cuja asáreas abaixo da curva sejamfinitas, podem ser expressascomo a integral de funções senoe cosseno, multiplicadas poruma função ponderadora.

Hoje, nosso objeto de estudo será a Transformada DiscretaBidimensional de Fourier e suas Aplicações.

Figure: A última função é a soma dasquatro primeiras vistas acima. Fourier, em1807, acreditava que funções periódicaspoderiam ser representadas como uma somaponderada de funções seno e cosseno.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 9: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

O Que é a Transformada de Fourier?

Sobre A Transformada de Fourier

A Transformada de Fourier (FT - Fourier Transform) é uma ferramenta(ou família de ferramentas) largamente empregada em processamento de

sinais (sons, imagens, etc).

A Transformada de Fourier decompõe um sinal em suas componenteselementares, seno e cosseno, com diferentes amplitudes, fase e frequência.

Para processarmos um determinado sinal, transformamos a informação domesmo para o domínio da frequência onde a sua avaliação é mais simples

e eficiente.

A Transformada Discreta de Fourier (DFT – Discrete Fourier Transform) é ummembro dessa família de ferramentas, sendo empregada em sinais discretizados.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 10: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Transformada de Fourier e Suas Aplicações

Algumas Aplicações da Transformada de Fourier

A Transformada Discreta de Fourier é aplicada em:

Métodos de Compressão

Métodos de Codificação

Filtragem

Realce e Suavização

Finalmente, como seriam as feições da Transformada de Fourier?

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 11: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Transformada de Fourier e Suas Aplicações

Algumas Aplicações da Transformada de Fourier

A Transformada Discreta de Fourier é aplicada em:

Métodos de Compressão

Métodos de Codificação

Filtragem

Realce e Suavização

Finalmente, como seriam as feições da Transformada de Fourier?

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 12: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Transformada Contínua Bidimensional de Fourier

Forma Direta e Inversa em Duas Dimensões

Forma Direta:

F(u, v) =∫ ∞−∞

∫ ∞−∞

f (x , y)e−j2π(ux+vy

)dxdy

Forma Inversa:

f (x , y) =∫ ∞−∞

∫ ∞−∞

F(u, v)e j2π(ux+vy

)dudv

Onde j representa a unidade imaginária, sendo j =√−1, as variáveis x e y

representam coordenadas espaciais e as variáveis u e v , por conseguinte,representam coordenadas espectrais. f (x , y) representa o sinal que serátransformado e F(u, v) a nossa Transformada Discreta de Fourier.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 13: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Transformada Discreta Bidimensional de Fourier

Forma Direta e Inversa em Duas Dimensões

Forma Direta:

F(u, v) = 1MN

M−1∑x=0

N−1∑y=0

f (x , y)e−j2π(

uxM + vy

N

)

Forma Inversa:

f (x , y) =M−1∑u=0

N−1∑v=0

F(u, v)e j2π(

uxM + vy

N

)

Onde j representa a unidade imaginária, sendo j =√−1, as variáveis x e y

representam coordenadas espaciais e as variáveis u e v , por conseguinte,representam coordenadas espectrais. M e N são as dimensões da imagemou sinal f (x , y) e F (u, v) a nossa Transformada Discreta de Fourier.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 14: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Transformada Discreta de Fourier - Algoritmo

Algoritmo da Transformada Discreta de Fourier� �1 /∗ D i s c r e t e F o u r i e r Transform Code − Assymptot i c Comp lex i t y : O(N^4) ∗/2 MyComplexMatrix MyD i s c r e t eFou r i e rT ran s f o rm : : f o rwa rd (MyDoubleMatrix& f )3 {4 uns i gned i n t N1 = f . rows ( ) ; un s i gned i n t N2 = f . c o l s ( ) ; // d imen s i on s o f complex mat r i x5 MyComplexMatrix myDFTMatrix ( N1 , N2 ) ; // d e c l a r a t i o n o f complex mat r i x67 f o r ( un s i gned i n t k1 = 0 ; k1 < N1 ; k1++) // beg in o f e x t e r n a l l o o p s8 {9 f o r ( un s i gned i n t k2 = 0 ; k2 < N2 ; k2++)

10 {11 Complex _tmp_sum (0 . 0 , 0 . 0 ) ; // temporary accumu la to r12 f o r ( un s i gned i n t n1 = 0 ; n1 < N1 ; n1++) // beg in o f i n t e r n a l l o o p s13 {14 f o r ( un s i gned i n t n2 = 0 ; n2 < N2 ; n2++)15 {16 doub le r e a l _ p a r t = cos ( −2 ∗ M_PI ∗ ( k1∗n1/N1 + k2∗n2/N2) ) ; // r e a l p a r t17 doub le imag_part = s i n ( −2 ∗ M_PI ∗ ( k1∗n1/N1 + k2∗n2/N2) ) ; // imag i n a r y pa r t18 _tmp_sum += f . at ( n1 , n2 ) ∗ Complex ( r e a l_pa r t , imag_part ) ; // accumu la t i on19 }20 }21 Complex sum ( (_tmp_sum . r e a l ( ) /(N1∗N2) ) , (_tmp_sum . imag ( ) /(N1∗N2) ) ) // sum r e s u l t22 myDFTMatrix . i n s e r t ( k1 , k2 , sum) ;23 }24 }25 r e t u r n myDFTMatrix ;26 }� �

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 15: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Transformada Discreta de Fourier - Algoritmo

Algoritmo da Transformada Inversa Discreta de Fourier� �1 /∗ I n v e r s e D i s c r e t e F o u r i e r Transform Code − Assymptot i c Comp lex i t y : O(N^4) ∗/2 MyComplexMatrix MyD i s c r e t eFou r i e rT ran s f o rm : : backward (MyComplexMatrix& F)3 {4 uns i gned i n t N1 = F . rows ( ) ; un s i gned i n t N2 = F . c o l s ( ) ; // d imen s i on s o f complex mat r i x5 MyComplexMatrix myIDFTMatrix ( N1 , N2 ) ; // d e c l a r a t i o n o f complex mat r i x67 f o r ( un s i gned i n t k1 = 0 ; k1 < N1 ; k1++) // beg in o f e x t e r n a l l o o p s8 {9 f o r ( un s i gned i n t k2 = 0 ; k2 < N2 ; k2++)

10 {11 Complex _tmp_sum (0 . 0 , 0 . 0 ) ; // temporary accumu la to r12 f o r ( un s i gned i n t n1 = 0 ; n1 < N1 ; n1++) // beg in o f i n t e r n a l l o o p s13 {14 f o r ( un s i gned i n t n2 = 0 ; n2 < N2 ; n2++)15 {16 doub le r e a l _ p a r t = cos ( 2 ∗ M_PI ∗ ( k1∗n1/N1 + k2∗n2/N2) ) ; // r e a l p a r t17 doub le imag_part = s i n ( 2 ∗ M_PI ∗ ( k1∗n1/N1 + k2∗n2/N2) ) ; // imag i n a r y pa r t18 _tmp_sum += F . at ( n1 , n2 ) ∗ Complex ( r e a l_pa r t , imag_part ) ; // accumu la t i on19 }20 }21 Complex sum ( (_tmp_sum . r e a l ( ) ) , (_tmp_sum . imag ( ) ) ) // sum r e s u l t22 myIDFTMatrix . i n s e r t ( k1 , k2 , sum) ;23 }24 }25 r e t u r n myIDFTMatrix ;26 }� �

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 16: Representing Images in Frequency Domain

A matriz complexa resultante da transformaçãoapresentará duas componentes de informação: a

real ou amplitude e a imaginária ou fase.

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Resultado da Transformação

O Resultado da Transformada é uma Matriz Complexa

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 17: Representing Images in Frequency Domain

A matriz complexa resultante da transformaçãoapresentará duas componentes de informação: a

real ou amplitude e a imaginária ou fase.

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Resultado da Transformação

O Resultado da Transformada é uma Matriz Complexa

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 18: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Transformada Discreta de Fourier: Componentes

Componentes da Transformada Discreta de Fourier

F (u, v) = R(u, v) + jI(u, v), F (u, v) ∈ C

R(u, v) : Representa os valores das componentes reais da transformada.

I(u, v) : Representa, por sua vez, os valores das componentes imaginárias.

Magnitude, Ângulo Fase e Potência do Espectro

|F (u, v)| =√

R(u, v)2 + I(u, v)2

φ(u, v) = tan−1[I(u, v)/R(u, v)]

P(u, v) = |F (u, v)|2 = R(u, v)2 + I(u, v)2

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 19: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Alguns Exemplos de Imagens Transformadas

Figure: Imagem original, parte real, parte imaginária, magnitude ou espectro, ângulofase e potência do espectro. Imagens em tons de cinza (8 bits) com 128x128 pixels.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 20: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Transformada de Fourier: Exemplo - Circle

Magnitude e Ângulo Fase do Exemplo Circle

Figure: Imagem original, magnitude ou espectro e ângulo fase. Imagem de teste em tons decinza (8 bits) com 128 pixels de largura por 128 pixels de altura. Resultados obtidos em umPentium Dual Core 2.00GHz, com 3.00 GB de memória principal (Ubuntu Linux 10.04 - Kernel2.6.32.38). Algoritmo implementado utilizado-se a biblioteca Magick++ e a linguagem C++.

Tempo necessário para obtenção da transformada, da representação do espectro e darepresentação do ângulo fase: 1m05.704s (média de tempo obtida após 50 execuções).

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 21: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Transformada de Fourier: Exemplo - Square

Magnitude e Ângulo Fase do Exemplo Square

Figure: Imagem original, magnitude ou espectro e ângulo fase. Imagem de teste em tons decinza (8 bits) com 128 pixels de largura por 128 pixels de altura. Resultados obtidos em umPentium Dual Core 2.00GHz, com 3.00 GB de memória principal (Ubuntu Linux 10.04 - Kernel2.6.32.38). Algoritmo implementado utilizado-se a biblioteca Magick++ e a linguagem C++.

Tempo necessário para obtenção da transformada, da representação do espectro e darepresentação do ângulo fase: 1m06.988s (média de tempo obtida após 50 execuções).

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 22: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Transformada de Fourier: Exemplo - Triangle

Magnitude e Ângulo Fase do Exemplo Triangle

Figure: Imagem original, magnitude ou espectro e ângulo fase. Imagem de teste em tons decinza (8 bits) com 128 pixels de largura por 128 pixels de altura. Resultados obtidos em umPentium Dual Core 2.00GHz, com 3.00 GB de memória principal (Ubuntu Linux 10.04 - Kernel2.6.32.38). Algoritmo implementado utilizado-se a biblioteca Magick++ e a linguagem C++.

Tempo necessário para obtenção da transformada, da representação do espectro e darepresentação do ângulo fase: 1m09.507s (média de tempo obtida após 50 execuções).

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 23: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Transformada de Fourier: Exemplo - Cross

Magnitude e Ângulo Fase do Exemplo Cross

Figure: Imagem original, magnitude ou espectro e ângulo fase. Imagem de teste em tons decinza (8 bits) com 128 pixels de largura por 128 pixels de altura. Resultados obtidos em umPentium Dual Core 2.00GHz, com 3.00 GB de memória principal (Ubuntu Linux 10.04 - Kernel2.6.32.38). Algoritmo implementado utilizado-se a biblioteca Magick++ e a linguagem C++.

Tempo necessário para obtenção da transformada, da representação do espectro e darepresentação do ângulo fase: 1m17.191s (média de tempo obtida após 50 execuções).

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 24: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Domínio da Frequência ou Espectral

Representação no Domínio da Frequência ou Espectral

Por que utilizar uma representação espectral?

I Algumas vezes, técnicas e procedimentos são melhor desempenhados em umoutro domínio qualquer do que no domínio espacial.

I A remoção de frequências indesejadas é uma tarefa menos árdua.I Certas operações (como a convolução) possuem um desempenho mais

atrativo no Domínio da Frequência/Espectral do que no Domínio Espacial.

Figure: Baboon ou Mandrill: Imagem, Representação no Domínio Espacial e Espectro de Fourier.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 25: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Aplicações da Transformada - Impressões Digitais

Reconhecimento de Digitais

Figure: A Comparação do espectro de Fourier de imagens de impressão digitalpodem levar ao reconhecimento de determinados indivíduos de maneira muitomais rápida. Esse método é executado através da comparação de cristas, queapresentam características semelhantes quanto à direção e freqüência.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 26: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Aplicações da Transformada - Fenótipos

Classificação de Fenótipos Baseada em Padrões

Figure: O olho da Drosophila é um grande exemplo de estrutura hexagonalcelular em formato de cristal. O valor absoluto da Transformada de Fourierdemostra a veracidade dessa estrutura. Assim como a Drosophila outrosanimais podem ser classificados utilizando a mesma técnica.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 27: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Aplicações da Transformada - Texturas

Detecção de Texturas em Imagens

Figure: Um problema comum e recorrente em Processamento de Imagens eVisão Computacional é a Detecção de Padrões de Repetição, que nomeamoscorriqueiramente como Textura. É um problema base, por exemplo, paraclassificação de determinados padrões de pelagem em animais. O que recainovamente no problema de classificação fenotípica.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 28: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Aplicações da Transformada - Ruído Periódico

Remoção de Ruído Periódico

Figure: Ruído causado por alguma interferência externa ou de alguma forma,pelo próprio aparelho de captação da imagem gerando padrões perceptíveis.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 29: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Aplicações da Transformada - Ruído Periódico

Remoção de Ruído Periódico

Figure: Ruído causado por alguma interferência externa ou de alguma forma,pelo próprio aparelho de captação da imagem gerando padrões perceptíveis.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 30: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Conclusões

Conclusões a Respeito dos Tópicos Apresentados

Transformada Discreta de Fourier

I Possui baixa complexidade de codificação.I Custo computacional acentuado : O(N4).I Gera subprodutos que auxiliam na análise de um determinado

conjunto transformado (som, imagem, etc):I espectro;I ângulo-fase;I espectro da potência.

Observação: A performance da DFT está sujeita a melhorias, casoseja usada sua forma rápida (FFT).

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 31: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Conclusões

Conclusões a Respeito dos Tópicos Apresentados

Transformada Discreta de Fourier

I Possui baixa complexidade de codificação.I Custo computacional acentuado : O(N4).I Gera subprodutos que auxiliam na análise de um determinado

conjunto transformado (som, imagem, etc):I espectro;I ângulo-fase;I espectro da potência.

Observação: A performance da DFT está sujeita a melhorias, casoseja usada sua forma rápida (FFT).

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 32: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Sugestões de Leitura

Algumas Sugestões de Leitura

Figure: Algumas sugestões de leitura que podem melhorar a compreensão sobre oassunto: Woods & Gonzalez, Bernd Jähne, Oge Marques e Thyagarajan. Além dessas,outras boas sugestões seriam os livros de Aura Conci, Computação Gráfica: Teoria ePrática e o livro Image Processing for Computer Graphics and Vision de autoria deLuiz Velho, Jonas Gomes e Alejandro Frery.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 33: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Agradecimentos

Grato Pela Atenção!

Michel Alves dos Santos - [email protected]

http://www.facebook.com/michel.alves.santos

http://www.linkedin.com/profile/view?id=26542507

https://twitter.com/Michel_Alves_

https://plus.google.com/110060332771581453284

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 34: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Referências Bibliográficas

Principais Referências Bibliográficas

A. Conci, E. Azevedo, and F. R. Leta.Computação Gráfica: Teoria e Prática, volume 2 of 1.Elsevier, Rio de Janeiro, Elsevier, 2008, 1 edition, 12 2008.ISBN 9788535223293.

R. C. Gonzalez and R. E. Woods.Digital Image Processing.Addison-Wesley, 3 edition, March 1992.ISBN 9780131687288.

B. Jahne.Digital Image Processing, volume 1.Springer, 5 edition.

K. Thyagarajan.Digital Image Processing with Application to Digital Cinema, volume 1.Focal Press, 1 edition.

L. Velho, J. Gomes, A. Frery, and S. Levy.Image Processing for Computer Graphics and Vision.Texts in Computer Science. Springer, 2 edition, 2008.ISBN 9781848001923.

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL

Page 35: Representing Images in Frequency Domain

Universidade Federal de Alagoas - UFAL - Campus A. C. Simões - Tabuleiro do Martins - Maceió - AL, CEP: 57072-970 - Instituto de Matemática (IM)

Representando Imagens no Domínio da Frequência :: Percepções Iniciais da Transformada Discreta Bidimensional de Fourier :: Palestra - Matfest 2012

Call for Students

Programa de Verão 2013

Instituto de Matemática da Universidade Federal de Alagoas(IM/UFAL)

I Iniciação CientíficaI Disciplina: Introdução à Computação Gráfica;

I MestradoI Disciplina: Computação Gráfica;

Mais informações em:I www.im.ufal.brI www.im.ufal.br/evento/verao

Michel Alves dos Santos: Bacharelando em Ciência da Computação Instituto de Matemática - Bloco 12 - Campus A. C. Simões - UFAL