Aplicação da Transformada de Fourier no
PROCESSAMENTO DIGITAL DE IMAGENS
João Fonseca Neto
Aracaju- Se, novembro de 1999.
e-mail: [email protected]
Resumo - Este trabalho apresenta a aplicabilidade da Transformada de Fourier no processamento de
imagens. Faz-se um estudo simplificado do desenvolvimento matemático de Fourier para funções ou sinais:
contínuos ou discretizados em uma ou duas dimensões, periódicos ou não, apresentando e provando algumas
de suas propriedades importantes.
Abstract -This paper presents the aplicability of Fourier Transform in the image processing. A simplified study
of Fourier's mathematical development for functions or signals: continuous or discretes in one or two
dimensions, periodicals or not by showing and demonstrating some importants properties.
Atenção: Este trabalho pode ser usado livremente, desde que o autor seja identificado e tenha seu nome
devidamente publicado. O autor não se responsabiliza por interpretações incorretas do conteúdo deste
trabalho.
Attention: This paper can be used freely, once the author is identified and has his name properly published.
The author can not be held responsible for wrong interpretations regarding the content of the work
Sumário:
• Transformada de Fourier:
1.
2.
3.
4.
5.
6.
7.
8.
Sinais contínuos periódicos unidemensionais;
Sinais contínuos não periódicos unidimensionais;
Sinais contínuos periódicos bi-dimensionais;
Sinais contínuos não periódicos bi-dimensionais;
Sinais discretos periódicos unidimensionais;
Sinais discretos não periódicos unidimensionais;
Sinais discretos periódicos bi-dimensionais;
Sinais discretos não periódicos bi-dimensionais;
• Teorema da convolução:
1. Convolução no tempo de dois sinais contínuos unidimensional;
2
2.
3.
4.
5.
Convolução na freqüência de dois sinais contínuos unidimensional;
Convolução de sinais discretos unidimensionais;
Convolução de sinais contínuos bi-dimensionais;
Convolução de sinais discretos bi-dimensionais;
• Funções de Correlação
1.
2.
3.
4.
Correlação cruzada entre sinais contínuos unidimensionais;
Correlação cruzada entre sinais discretos unidimensionais;
Correlação cruzada entre sinais contínuos bi-dimensionais;
Correlação cruzada entre sinais discretos bi-dimensionais;
I - Introdução
O interesse em métodos de processamento digital de imagens vem principalmente de duas áreas
de aplicações: melhoria de informação (imagem) para interpretação humana, e processamento de dados
(imagens) em computador, e vem crescendo com aplicações no Programa Espacial, na Medicina,
Arqueologia, Física, Astronomia, Biologia, Indústria etc.
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").
A Transformada de Discreta de Fourier Bi-dimensional (Jean Baptiste Joseph Fourier,
matemático francês - 1768 a 1830) é uma ferramenta matemática de grande aplicabilidade na solução dos
problemas de processamento digital de imagens (sinais bi-dimensionais) pois, muitas vezes, é conveniente a
mudança do domínio do tempo ou espaço (x,y) para o domínio da freqüência facilitando, assim, o seu
processamento.
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.
II - Série e Transformada de Fourier de Sinais Contínuos: 1-D e 2-D.
3
Esta ferramenta matemática é muito aplicada no processamento de sinais analógicos periódicos
ou não, como apresentado nas seções 2.1, 2.2, 2.3.
2.1 - Representação de uma função periódica pela Série de Fourier no intervalo (-∞
∞ < t < +∞
∞ ).
Seja uma função periódica f(t) de período T, podemos representá-la pela Série de Fourier no
intervalo (-∞,∞); ou seja , podemos decompor f(t) em componentes senoidais e cossenoidais (ou
exponenciais):
∞
∑ Fn ejnω ot ,
f (t ) =
(1)
n = -∞
onde
1
Fn =
T
to+ T
∫ f(t) e-jnω ot dt ,
(2)
to
o período de f(t) é T =
ωo
, ωo = 2πfo é a freqüência fundamental em rad/s e fo é a freqüência fundamental
2π
em Hz;
n = 0, ±1, ±2, ...., ± ∞.
Para encontrar a expressão de Fn, basta multiplicar ambos os lados da equação (1) por e-jnω ot e
integrar no tempo (período):
∞
∑ Fn ejnω ot ,
f (t ) =
temos
n = -∞
to+ T
∫
∞
-jnω ot
f(t) e
dt =
to
to+ T
∫
-jnω ot
f(t) e
dt =
∑ Fn ∫
n= −∞
to
∞
to+ T
∑ Fn ∫
n= −∞
to
to+ T
ejnω ot e-jnω ot dt
∞
dt =
to
to+ T
∫
f(t) e-jnω ot dt = Fn T, logo
to
1
Fn =
T
to+ T
∫ f(t) e-jnω ot dt
to
∑ Fn T
n= −∞
4
Portanto, a expansão de uma função periódica em série de Fourier equivale a decomposição da
função em termos de suas componentes de várias freqüências ou seja, um sinal periódico apresenta um
espectro de freqüência discreto e infinito.
O espectro de freqüência discreto aparece em um gráfico como linhas verticais espaçadas, com
alturas proporcionais ao coeficiente da componente de freqüência (Fn) correspondente. No entanto, se formos
rigorosos, necessitamos de dois gráficos para representar, completamente, uma função periódica no domínio
da freqüência: o espectro e amplitude e o espectro de fase; visto que, os coeficientes Fns, normalmente, são
complexos.
2.2 - A transformada de Fourier de uma função periódica
Matematicamente, a transformada de Fourier de uma função periódica não existe, uma vez que
não satisfaz a condição de integrabilidade absoluta no intervalo (-∞, ∞) (condição suficiente, mas não
necessária). Porém, a transformada existe no limite, ou seja a transformada de Fourier de uma função
periódica é a soma das transformadas da Fourier das suas componentes individuais, obtidas pela sua série de
Fourier.
Seja a série de Fourier de f(t), periódica em T:
∞
f(t) =
∑ Fn ejnω ot , onde ωo =
n= −∞
ℑ[f(t)] = ℑ [
2π
rad. Tomando a transformada de Fourier em ambos os lados, temos:
T
∞
∑ Fn ejnω ot]
n= −∞
∞
=
∑ Fn ℑ[ejnω ot], como, [3], ℑ[ejnω ot] = 2πδ(ω - ωo), obtem-se:
n= −∞
∞
ℑ[f(t)] = 2π ∑ Fnδ (ω - n ω o)
(3)
−∞
A transformada de Fourier de um sinal periódico é formada por impulsos localizados nas
freqüências harmônicas do sinal e que o peso de cada impulso é 2π vezes o valor do coeficiente na série
exponencial de Fourier (Equação 2).
2.3 - Representação de uma função arbitrária (não periódica) em todo o intervalo(-∞
∞ ,∞
∞ ): A
Transformada de Fourier.
A transformada de Fourier, F(u), é a decomposição do sinal, f(x), de energia finita (não
periódico) em termos de sinais senoidais e cossenoidais (ou exponenciais).
∞
F(u) =
∫ f(x) e-j2πux dx ,
−∞
(4)
5
onde x e u são variáveis independentes nos domínios do espaço e freqüência respectivamente.
F(u) = F(u)  ejφ(u)
F(u) pode ser representado por um gráfico de amplitude, Espectro de Fourier, F(u) , um gráfico
de fase, φ(u), e a Função Densidade Espectral, potência, F(u) 2.
Neste caso, o espectro é contínuo e existe para todos os valores de freqüência, -∞<u<∞.
A transformada inversa é:
∞
f(x) =
∫ F(u) ej2πux du
(5)
−∞
Portanto, representamos uma função arbitrária f(x) em termos de funções exponenciais em todo o
intervalo (-∞< x < ∞).
Observação:
Quando a função é temporal (x = t) e a variável independente de freqüência é dada em rad/s (u =
1
ω), normalmente aparece um fator
multiplicando a integral; ou seja:
2π
1
f(t) =
2π
∞
∫ F(ω) ejω t dω,
−∞
o fator 2π na equação acima pode ser removido se a integração for realizada em função da freqüência em Hz
ao invés de ω:
ω = 2πf,
dω = 2πdf, logo
1
f(t) =
2π
∞
f(t) =
∞
∫ F( 2πf ) ej2πft 2π df
−∞
∫ F( 2πf ) ej2πft df
−∞
6
As equações apresentadas acima são normalmente conhecidas como par de transformadas de
Fourier. A Equação 4 é conhecida como transformada direta de Fourier de f(x) enquanto, a Equação 5 é
conhecida como transformada inversa de Fourier de F(u).
2.4 - Transformada de Fourier de uma Função Contínua 2-D
A Transformada de Fourier [1], [2] pode ser estendida para uma função de duas variáveis f(x,y).
Se f(x,y) é contínua e apresenta a condição de integrabilidade então, temos o par de transformadas:
∞ ∞
F(u,v) =
∫ ∫ f(x,y) e-j2π(ux+vy) dx dy
(6)
−∞ − ∞
∞ ∞
f(x,y) =
∫ ∫ F(u, v) ej2π(ux+vy) du dv
(7)
−∞ − ∞
onde "u" e "v" são variáveis independentes de freqüência.
Para o caso de uma dimensão, temos, também, o espectro de amplitude, fase e potência, e como,
normalmente F(u,v) é complexa, temos:
F(u,v) = R(u,v) +jI(u,v)
• Espectro de Amplitude
F(u, v) = [R2(u,v) + I2(u,v)]1/2 , onde R(u,v) é a parte real e I(u,v) é a parte imaginária.
• Espectro de Fase
 I(u, v) 
φ(u,v) = tg-1 

 R(u, v) 
• Espectro de Potência
P(u,v) = F(u, v) 2 = R2(u,v) + I2(u,v)
III - Sinais Discretizados: 1-D
A representação de uma seqüência periódica pela Série Discreta de Fourier, DFS 1-D, e a
representação de uma seqüência não periódica pela Transformada Discreta de Fourier, DFT 1-D, são
ferramentas matemáticas de grande utilidade no processamento de sinais digitais, como apresentado nas
seções 3.1, 3.2.
7
3.1 - Representação de uma Seqüência Periódica em Série Discreta de Fourier
Seja uma seqüência periódica f(x) = {xo, x1, ..., xN-1}, com período N, tal que f(x) = F(x+kN),
onde k é um número inteiro. Podemos representar f(x) em termos da Série Discreta de Fourier.
Diferentemente à série de Fourier para funções contínuas e periódicas, uma seqüência periódica
apresenta somente N exponenciais complexas. Isso ocorre devido a periodicidade da função ej2πkx/N em k
com período N:
Seja: ek(x) = ej2πxk/N , temos que e0(x) = eN(x), e1(x) = eN+1(x) , pois
para k =0:
e0(x) = e0 = 1;
para k = N:
eN(x) = ej2πxN/N = ej2πx = cos (2πx) + j sin (2πx) , para qualquer valor de x cos (2πx) = 1 e sin (2πx) = 0.
Logo:
e0(x) = eN(x).
Para k = 1:
e1(x) = ej2πx/N ,
para k = N+1:
eN+1(x) = ej2πx(N+1)/N = ej2πx . ej2πx/N , como já vimos o termo ej2πx é sempre igual a unidade para qualquer valor
de x inteiro. Logo:
e1(x) = eN+1(x)
Assim,
N −1
f(x) =
∑ F (u) ej(2πux/N) ,
u= 0
x = 0,1,2, ..., N-1 (número de amostras);
u = 0,1,2, ..., N-1 (variável independente de freqüência);
(8)
8
1
F(u) =
N
N −1
∑ f ( x ) e-j(2πux/N)
,
(9)
x= 0
As Equações 8 e 9 são o par de transformadas para representação de uma Série Discreta de
Fourier (DFS 1-D), onde F(u) e f(x) são periódicas de período N.
Nós podemos encontrar a expressão de F(u) da seguinte forma:
multiplicamos ambos os lados da equação 8 por e-j2πxu/N e efetuamos o somatório em x [0, N-1].
N −1
∑
f(x) e-j(2πux/N) =
x=0
N −1
∑
f(x) e-j(2πux/N) =
x=0
N −1
N −1
x=0
u= 0
∑ ∑ F (u) ej(2πux/N) e-j(2πux/N)
N −1
N −1
u= 0
x=0
, permutando os somatórios
∑ F (u) ∑ ej(2πux/N) e-j(2πux/N) ,
N
usando a propriedade dos somatórios:
∑K
n= 0
N
=K
∑
= KN, onde K é uma constante, e o somatório
n =0
N −1
∑ F (u) representa a seqüência periódica dos coeficientes da série de Fourier: F(0), F(1), F(2), ..., F(N-1),
u= 0
denotada por F(u). Temos, então:
N −1
∑
f(x) e-j(2πux/N) = F(u) N,
x=0
1
N
N −1
∑
f(x) e-j(2πux/N) = F(u)
x=0
3.2 - Representação de uma Seqüência de Duração Finita (não periódica) 1-D, Transformada
Discreta de Fourier (DFT -1D)
Seja uma seqüência de duração finita g(x) de comprimento N, tal que g(x) = 0 fora do intervalo
0≤ x ≤ N-1.
Para facilidade de análise, vamos considerar que g(x) é um período da seqüência periódica f(x)
apresentada no item 3.1, temos:
∞
f(x) =
∑ g(x
r = −∞
+ rN) ,
9
onde "r" é
um número inteiro.
A seqüência de duração finita, g(x), pode ser obtida da seqüência periódica f(x) pela extração de
um período:
 f (x), 0 ≤ x ≤ N - 1
g(x) = 
0 , fora
Por conveniência matemática, definimos uma seqüência retangular RN(x) tal que:
1, 0 ≤ x ≤ N - 1
RN = 
0, fora
Assim, podemos expressar a seqüência finita g(x0 da seguinte forma:
g(x) = f(x)RN(x)
Como já definido, os coeficientes, F(u), da DFS e a seqüência periódica, f(x), são periódicos
com período N.
Denotando por G(u) os coeficientes de Fourier para a seqüência finita g(x), temos:
G(u) = F(u)RN(u), como:
F(u) =
1
N
N −1
∑ f(x) e-j(2πux/N) ,
e
x=0
N −1
f(x) =
∑ F(u) ej(2πux/N) ,
u= 0
temos o par de Transformadas Discretas de Fourier: DFT 1-D
 1 N −1
 ∑ g(x) exp(-j2π ux / N) , 0 ≤ u ≤ N - 1
• G(u) =  N x = 0
0
, fora

 N −1
 ∑ G( u ) exp(j2π ux / N), 0 ≤ x ≤ N - 1
• g(x) =  u = o
0
, fora

(10)
(11)
10
onde "u" e "x" = 0,1,2,..., N-1
Observação: é importante ter em mente que sempre consideramos uma seqüência aperiódica como sendo um
período de uma seqüência periódica e a partir daí, efetuamos os cálculos para encontrar os coeficientes de
Fourier (DFT).
IV - Transformada Discreta de Fourier Bi-Dimensional
Esta ferramenta matemática é muito empregada no processamento de imagens e sinais bidimensionais, pela computação da convolução para filtragem; realce, restauração, decodificação etc.
4.1 - Série Discreta de Fourier Bi-Dimensional (DFS - 2D)
Seja uma seqüência periódica bi-dimensional f(x,y) = f(x+qM, y+rN), onde "M" é o período das
linhas, "N" é o período das colunas e "q" e "r" são números inteiros que podem ser positivos ou negativos.
A seqüência f(x,y) tem sua representação em série de Fourier como uma soma finita de
exponenciais complexas, de seguinte maneira:
M −1 N −1
f(x,y) = ∑ ∑ F(u, v) ej2π (ux/M + vy/N)
(12)
u= 0 v = 0
onde,
F(u,v) =
1
MN
M −1 N −1
∑ ∑ f(x, y) e-j2π (ux/M + vy/N)
(13)
x=0 y=0
onde,
F(u,v) e f(x,y) têm a mesma periodicidade;
"u" e "x" = 0,1,2,..., M-1;
"v" e "y" = 0,1,2,..., N-1.
4.2 - Transformada Bi-Dimensional Discreta de Fourier (DFT -2D)
Vamos, aqui, aplicar a mesma interpretação dado no caso da Tansformada em uma dimensão; ou
seja, uma seqüência de duração finita é considerada como sendo um período da seqüência periódica
correspondente.
Uma seqüência bi-dimensional não periódica g(x,y) que é zero fora do intervalo 0≤ x ≤ M-1, 0≤
y ≤ N-1 é referida como uma seqüência de área finita.
Analogamente a discussão do item anterior, temos:
11
G(u,v) = F(u,v)RN(u,v),
g(x,y) = f(x,y)RN(x,y),
como
1 , 0 ≤ x ≤ M - 1, 0 ≤ y ≤ N - 1
RN (x,y) = 
0 , fora
 1

G(u,v) =  NM
0

M −1 N −1
∑ ∑ g(x)exp(-j2π ux / M) exp(-j2π vy / N) , 0 ≤ x ≤ M - 1, 0 ≤ y ≤ N - 1
x=0 y=0
(14)
, fora

 M −1 N −1

∑ ∑ G(u, v)exp(j2π ux / M) exp(j2π vy / N), 0 ≤ x ≤ M - 1, 0 ≤ y ≤ N - 1
g(x,y) =  u = 0 v = 0


 0
, fora
(15)
Observação, uma opção para implantação de DFT 2-D é utilizar uma DFT 1-D para as linhas e
DFT 1-D para as colunas e vice-versa. A mesma interpretação é dada para o caso da DFT 2-D inversa
(propriedade da separabilidade, seção 5.1).
V - Algumas Propriedades Importantes da Transformada de Fourier
Temos duas maneiras de representar uma mesma função ou sinal: uma representação no domínio
do tempo ou do espaço e outra no domínio da freqüência.
A representação de um sinal no domínio do tempo está presente, naturalmente, no nosso dia a
dia. Contudo, certas operações, principalmente na engenharia, tornam-se muito mais simples e esclarecedoras
se trabalharmos no domínio da freqüência, domínio este, conseguido através das Transformadas de Fourier.
É muito importante observar o que ocorre em um domínio, quando efetuamos certas operações
no outro domínio.
Segundo [2], muitas propriedades das Transformadas de Fourier discutidas em uma dimensão
podem ser estendidas para sinais multi-dimensionais. Por isso, vamos demonstrar algumas propriedades das
Transformadas em 1D e estender os resultados ao caso bi-dimensional, que nos interessa no momento.
5.1 - Separabilidade
12
Esta propriedade nos mostra que o par de transformadas F(u,v) e f(x,y) pode ser obtido em dois
passos separados, considerando-se duas operações 1D. Em outras palavras, a função bi-dimensional F(u,v) é
obtida pela transformação em cada linha de f(x,y) e o resultado é multiplicado pelo número total das mesmas,
M, obtendo-se F(x,v). F(u,v) é obtida, agora, transformando-se F(x,v) coluna por coluna.
Demonstação:
Seja o gráfico representando uma imagem:
N-1
(0,0)
y
f(x,y)
M-1
x
temos que:
M −1 N −1
f(x,y) = ∑ ∑ F(u, v) ej2π (ux/M + vy/N) , onde x, y = 0,1, ..., N-1
u= 0 v = 0
F(u,v) =
1
MN
M −1 N −1
∑ ∑ f ( x , y)
e-j2π (ux/M + vy/N) , onde u,v = 0,1, ..., M-1
x = 0 y =0
Podemos desdobrar F(u,v) em duas operações:
F(x,v) = ℑ[f(x,y)x=cte], operação sobre as linhas.
F(u,v) = ℑ[F(x,v)y=cte], operação sobre as colunas.
Primeiramente, efetuando a transformação sobre as linhas de f(x,y):

 1
F(x,v) = M 
MN

M −1 N -1
∑∑
x = 0 y= 0
-j2πyv/N
f(x, y) e
-j2πux/M
e




x=cte
F(x,v) =
1
N
N −1
∑
y= 0
 M −1
f ( x, y ) e-j2πvy/N  ∑ exp( − j 2πux / M )
 x=0



x=cte
13
N −1
1
F(x,v) =
N
∑
f(x,y) e-j2πyv/N
y=0
Efetuando, agora, a transformação sobre as colunas:
1
F(u,v) =
MN
M −1
M −1
x=0
x=0
∑ ∑ F ( x , v ) e-j2πux/M e-j2πvy/N
y=cte
F(u,v) =
F(u,v) =
F(u,v) =
1
M
M −1
∑
x =0
1
MN
1
MN
1

N
N −1

y=0

∑ f ( x , y ) exp(-j2πvy / N e-j2πux/M
M −1 N −1
∑ ∑ f ( x , y ) e-j2πvy/N e-j2πuc/M
x=0 y=0
M −1 N −1
∑ ∑ f ( x , y ) e-j2π (ux/M + vy/N)
x=0 y=0
assim, concluímos que:
1
F(u,v) =
M
M −1
∑
-j2πux/M
e
x=0
1
N
N −1
∑ f (x , y ) e-j2πyv/N
y=0
CQD (como queríamos demonstrar)
5.2 - Translação
Esta propriedade mostra que a multiplicação de f(x,y) pela exponencial ej2π (uo x/M + vo y/N) resulta
num deslocamento na freqüência para o ponto (uo, vo).
De maneira análoga, se multiplicarmos a transformada F(u,v) pela mesma exponencial e
tomarmos a transformada inversa, efetuamos um deslocamento espacial da origem para o ponto (xo, yo).
Demonstração:
Mostrar que:
14
f(x,y) ⇔ F(u,v)
f(x,y)ej2π (uo x/M + vo y/N) ⇔ F(u-uo, v-vo)
1
MN
ℑ[f(x,y)ej2π (uo x/M + vo y/N)] =
=
M −1 N −1
∑ ∑ f(x, y) ej2π (uo x/M + vo y/N) e-j2π (ux/M +vy/N)
x=0 y=0
1
MN
1
=
MN
M −1 N −1
∑ ∑ f ( x , y) ej2π [(uo x - ux)/M + (vo y - vy)/N]
x = 0 y =0
M −1 N −1
∑ ∑ f ( x , y) ej2π [(uo - u)x/M + (vo - v)y/N]
x = 0 y =0
ℑ[f(x,y)ej2π (uo x/M + vo y/N)] = F(u-uo, v-vo)
CQD
Analogamente, podemos provar a transformada inversa.
5.3 - Periodicidade
Esta propriedade mostra que se f(x,y) é periódica, somente um período é necessário para
especificar completamente F(u,v) no domínio da freqüência. O mesma se aplica a f(x,y) no domínio espacial.
Demonstração:
Provar que F(u,v) = F(u+M, v+N), ou f(x,y) = f(x+M, y+N), onde < é o período das linhas e N
o período das colunas.
ℑ[f(x, y)] ⇔ F(u, v)
ℑ[f(x+M, y+N)] ⇔ F(u+M, v+N),
1
F(u, v) =
MN
M −1 N −1
∑ ∑ f ( x , y) e-j2π (ux/M + vy/N) ,
x = 0 y =0
15
substituindo "x" por "x+M"
"y" por "y+N"
temos
1
ℑ[f(x+M, y+N)] =
MN
=
M −1 N −1
∑ ∑ f ( x + M , y + N) e-j2π[u(x+M)/M e-j2πv(y+N)/N] =
x = 0 y =0
1
MN
1
=
MN
=
1
MN
M −1 N −1
∑ ∑ f ( x + M , y + N) e -j2π ux/M e-j2πuM/M e-j2πvy/N e-j2πvN/N
x = 0 y =0
M −1 N −1
∑ ∑ f ( x + M , y + N) e -j2π (ux/M +vN/N) e-j2πuM/M e-j2π vy/N
x = 0 y =0
M −1 N −1
∑ ∑ f ( x + M , y + N) e -j2π u(x+M)/M e-j2π v(y+N)/N
x = 0 y =0
ℑ[f(x+M, y+N)] = F(u+M, v+N) = F(u,v)
CQD
5.4 Rotação
Esta propriedade nos mostra que uma rotação em f(x,y) por ângulo α, produz a mesma rotação
em F(u,v) e vice-versa.
Nesta demonstração utilizamos uma função discreta de uma dimensão, para facilidade dos cálculos, sendo que
os resultados podem ser extrapolados para funções multi-dimensionais.
Demonstração:
Sejam as variáveis em coordenada polar
x = r cosθ e y = ω cosϕ,
temos:
F(u) =
1
N
N −1
∑ f (x ) e-j(2π ux/N)
x=0
16
Queremos demonstrar que: f(r cosθ) ⇔ F(ω cosϕ)
f[r cos(θ + α)] ⇔ F[ω cos(ϕ + α)]
1
F(ω cosϕ) =
N
r
∑ f ( r cosθ) e-j(2π ω cosϕ r cosθ)/N
x =0
Impondo um ângulo de giro a f(x, y) igual a "α", temos:
ℑ{f[r cos(θ + α)]} =
=
1
N
1
=
N
1
=
N
1
=
N
=
1
N
1
N
r
∑ f [r cos(θ + α ) e-j2π ω r/N [ cosϕ cos(θ + α)]
x =0
r
∑ f [r cos(θ + α ) e-j 2π ω r/N {cosϕ [cosθ cosα - sinθ sinα]}
x =0
r
∑ f [r cos(θ + α ) e
-j2π ω r/N{cosϕ
x =0
1
1
[cos(θ - α) + cos(θ + α)] [cos(θ - α) - cos(θ + α)]}
2
2
r
∑ f [r cos(θ + α ) e-jπ ω r/N{cosϕ [cos(θ - α) + cos(θ + α)] + [cos(θ - α) + cos(θ + α)]}
x =0
r
∑ f [r cos(θ + α ) e-jπ ω r/N{cosϕ [cos(θ + α)] + cos(θ + α)}
x =0
r
∑ f [r cos(θ + α ) e-j2π ω r/N[cosϕ cos(θ + α) ]
x =0
ℑ{f[r cos(θ + α)]} = F[ω cos(ϕ + α)]
CQD
5.5 - Teorema da Convolução
O teorema da convolução é, provavelmente, uma das ferramentas mais eficazes na análise em
freqüência.
Inicialmente, para facilidade de análise, desenvolveremos a convolução de duas funções contínuas de uma
dimensão f(x) e g(x) que é denotada por f(x) *g(x) e é definida pela integral:
17
∞
f(x)*g(x) =
∫ f(α ) g(x - α) dα ,
onde "α" é uma variável de integração.
−∞
A importância da convolução no domínio da freqüência consiste no fato que se f(x) tem a
transformada de Fourier F(u) e g(x) tem sua transformada de Fourier G(u) então f(x)*g(x) tem F(u)G(u) como
transformada, ou seja:
f(x)*g(x) ⇔ F(u)G(u)
O que mostra que a convolução no domínio espacial (x), pode ser obtida pela transformada
inversa do produto F(u)G(u).
O resultado pode ser estendido para o domínio da freqüência; ou seja:
f(x)g(x) ⇔ F(u)*G(u)
Demonstração:
• Teorema da convolução no tempo
Sejam: f(x) ⇔ F(u)
g(x) ⇔ G(u)
tal que
∞
∫ f (α )g(x
- α ) dα ⇔ F(u)G(u)
−∞
então, mostrar que f(x)*g(x) ⇔ F(u)G(u)
Demonstração:
∞ ∞
ℑ[f(x)*g(x)] =
∫ ∫ f(α )g(x -
−∞ − ∞
j2π u α
.
Logo:
∞
α ) dα e
-j2πux
dx =
∞
∫ f(α ) ∫ g(x -
−∞
α ) e-j2πux dxdα
-∞
Pela propriedade do deslocamento no espaço, verificamos que a segunda integral é igual a G(u)e-
18
∞
ℑ[f(x)*g(x)] =
∫ f(α ) e-j2πuα dα G(u) = F(u)G(u)
−∞
CQD
• Teorema da convolução na freqüência
Sejam: f(x) ⇔ F(u)
g(x) ⇔ G(u)
tal que
∞
f(x)g(x) ⇔
∫ F(α )G(u - α )dα
−∞
então, devemos mostrar que:
f(x)g(x) ⇔ F(u)*G(u)
Demonstração:
Seja
∞
F(u)*G(u) =
∫ F(α )G(u - α) dα
−∞
Pelo teorema do deslocamento na freqüência, temos que: G(u-α)= G(u)ej2πuα . Logo:
∞
F(u)*G(u) =
∫ F(α ) ej2πuα dα G(u),
−∞
∞
Segundo [4], substituindo-se G(u) por ℑ [G(u)] =
-1
∫ g( x )
e- j2πux dx, temos:
−∞
F(u)*G(u) =
∞
∞
∞
−∞
−∞
−∞
∫ F(α ) ej2πuα dα
∫ g( x ) e- j2πux dx =
F(u)*G(u) = ℑ[f(x(g(x)]
CQD
∫ f (x ) g (x ) e- j2πux dx
19
5.6 - Algumas Propriedades da Convolução
5.6.1 - Comutatividade
f(x)*g(x) = g(x)*f(x)
Demonstração:
Seja
∞
f(x)*g(x) =
∫ f(k)g(x - k) dk , permutando-se a variável "k" por (x-j), obtemos:
−∞
∞
f(x)*g(x) =
∫ f (x - j)g[x - (x - j)] d(x - j)
−∞
∞
=
∫ g(j)f(x - j) dj = g(x)*f(x)
−∞
CQD
5.6.2- Distributividade
f(x)*[g(x)+h(x)] = f(x)*g(x) + f(x)*h(x)
Demonstração:
Seja:
f(x)*[g(x)+h(x)] =
∞
∫ f(t)[g(x - t) +
∞
h(x - t)] dt =
−∞
∫ f(t)g(x - t) dt
-∞
∞
+
∫ f(t)h(x - t) dt
= f(x) * g(x) + f(x) * h(x)
-∞
CQD
5.6.3 - Associatividade
f(x)*[g(x)*h(x)] = [f(x)*g(x)]*h(x)
Demonstração:
20
Esta propriedade é melhor entendida do fato que:
f(x) ⇔ F(u)
g(x) ⇔ G(u)
h(x) ⇔ H(u)
ℑ{f(x)*[g(x)*h(x)]} = F(u)[G(u)H(u)] = [F(u)G(u)H(u)], logo:
ℑ-1{[F(u)G(u)]H(u)} = [f(x)*g(x)]*h(x)
CQD
5.6.2 - Convolução de Funções ou Sinais Discretizados e Uni-Dimensionais
Sejam as funções f(x) e g(x) discretizadas, tal que f(x) tem tamanho "A" e g(x) tem tamanho "B";
ou seja:
f(x) = {f(0), f(1), f(2), ..., f(A-1)}
g(x) = {g(0), g(1), g(2), ..., g(B-1)}
Como já visto, a transformada discreta de Fourier e sua transformada inversa são funções
periódicas com o mesmo período das funções discretas.
Assim, o teorema da convolução discreta, também, tem que ser consistente com a periodicidade das funções
discretas f(x) e g(x), tal que f(x) = f(x+M) e g(x) = g(x+M). Com isto, o resultado da convolução de f(x) com
g(x) é periódica de período, também, "M". O valor de "M" deve ser maior ou igual do que A+B-1 para evitar
erro de superposição.
Os detalhes do desenvolvimento descrito acima, encontra-se em [1].
Como f(x), g(x) e f(x)*g(x) devem ter o mesmo tamanho, é necessário estender f(x) e g(x) com
zeros até que ambas as funções fiquem com tamanhos iguais a "M".
Observação, quando estendemos uma seqüência com zeros, não alteramos (não há criação nem
desaparecimento de freqüências) no seu espectro de freqüências mas sim, apenas o espalhamos.
Estendendo as funções:
 f(x) , 0 ≤ x ≤ A - 1
fe(x) = 
0 , A ≤ x ≤ M - 1
g(x) , 0 ≤ x ≤ B - 1
ge(x) = 
, B ≤ x ≤ M -1
0
21
Assim, temos:
• fe(x)*ge(x) =
1
M
M −1
∑ fe(m)ge(x - m) ,
m= 0
para x = 0,1,2,3, ..., M-1. A função convolução é uma seqüência discreta periódica de comprimento "M".
O teorema da convolução discreta para o caso 1-D é:
fe(x)*ge(x) ⇔ Fe(u)Ge(u)
e
fe(x)ge(x) ⇔ Fe(u)*Ge(u)
5.6.3 - Teorema da Convolução para Funções ou Sinais Contínuos Bi-Dimensionais.
Sejam as funções ou sinais contínuos no domínio bi-dimensioanal espacial (x,y). Definimos a
convolução definimos a convolução de f(x,y) com g(x,y), como:
∞ ∞
f(x,y)*g(x,y) =
∫ ∫ f(α , β)g(x - α, y - β ) dα dβ
−∞ − ∞
O teorema da convolução em duas dimensões é, então, expresso pelas relações:
f(x,y)*g(x,y) ⇔ F(u,v)G(u,v)
e
f(x,y)g(x,y) ⇔ F(u,v)*G(u,v)
Observação, este teorema foi demonstrado para o caso unidimensional, sendo os resultados
válidos para qualquer dimensão, segundo [1].
5.6.4- Teorema da Convolução para Funções ou Sinais Discretos Bi-Dimensionais
A convolução discreta 2-D é formulada discretizando-se as funções contínuas f(x,y) e g(x,y) com
tamanhos AxB e CXD respectivamente.
Como no caso 1-D, estas seqüências devem ser periódicas de períodos "M"e "N" nas dimensões
"x"e "y" respectivamente.
Segundo [2], o erro de superposição da função de convolução é evitado tomando-se os períodos "M"e "N",
tais que:
22
M≥ (A+C) -1 e N≥ (B+D) -1.
As seqüências periódicas são formadas estendendo-se f(x,y) e g(x,y) da seguinte forma:
 f(x,y), 0 ≤ x ≤ A - 1 e 0 ≤ y ≤ B - 1
fe(x,y) = 
, A ≤ x ≤ M - 1 ou B ≤ y ≤ N - 1
0
e
g(x, y), 0 ≤ x ≤ C - 1 e 0 ≤ y ≤ D - 1
ge(x,y) = 
, C ≤ x ≤ M - 1 ou D ≤ y ≤ N - 1
0
Então, definimos a convolução discreta 2-D, como:
1
fe(x,y)*ge(x,y) =
MN
M −1 N −1
∑ ∑ fe(m, n)ge(x - m, y - n) ,
m = 0 n =0
para x = 0,1,2,...., M-1
y = 0,1,2,...., N-1
O teorema da convolução discreta para o caso 2-D, diz:
fe(x,y)*ge(x,y) ⇔ Fe(u,v)Ge(u,v)
e
fe(x,y)ge(x,y) ⇔ Fe(u,v)*G(u,v)
Portanto, concluímos que a convolução de duas funções ou sinais (segundo [1],
independentemente da dimensão ou se é discreto ou contínuo) no domínio do tempo ou espaço é equivalente
à multiplicação dos seus espectros no domínio da freqüência e que a multiplicação de duas funções ou sinais
no domínio do tempo ou espaço é equivalente à convolução dos seus espectros no domínio da freqüência.
6- Correlação
Uma das principais aplicações da correlação no processamento de imagens [1] é encontrar a
similaridade entre uma imagem desconhecida e um conjunto de imagens conhecidas.
6.1- Correlação Cruzada entre Funções ou Sinais Contínuos 1-D
A correlação cruzada entre duas funções ou sinais, contínuos ou discretos em uma ou mais
dimensões nos mostra quaisquer similaridade entre essas funções ou sinais e é denotado por:
23
∞
f(x)°g(x) =
∫ f * (α )g(x - α ) dα ,
−∞
onde f*(α) é o conjugado complexo de f(α).
6.2 - Correlação Cruzada entre duas Funções ou Sinais Discretos 1-D
A correlação entre duas funções ou sinais discretos f(x) e g(x) é definida por:
fe(x,y)°ge(x,y) =
1
M
M −1
∑ f * e(m)ge(x- m) ,
m= 0
para x = 0,1,2, ..., M-1.
Observação, os comentários feitos anteriormente sobre as funções ou sinais estendidos fe(x) e
ge(x), bem como sua periodicidade, são levados em consideração para o caso da correlação cruzada.
6.2 - Correlação Cruzada para Funções ou Sinais Contínuos Bi-Dimensionais
Similarmente, podemos estender [1] a correlação cruzada em uma dimensão para o caso bidimensional.
Sejam as funções f(x,y) e g(x,y) de variáveis contínuas, a correlação é definida como:
∞ ∞
f(x,y)°g(x,y) =
∫ ∫ f * (α, β )g(x - α, y - β ) dα dβ .
−∞ − ∞
O teorema da correlação para o caso das funções ou sinais contínuos bi-dimensionais:
f(x,y)°g(x,y) ⇔ F*(u,v)G(u,v)
e
f*(x,y)g(x,y) ⇔ F(u,v)G(u,v),
onde f*(x,y) é o conjugado complexo da função ou sinal f(x,y) e F*(u,v) é o conjugado complexo da
transformada de Fourier de f(x,y).
6.3 - Correlação Cruzada para Funções ou Sinais Discretos Bi-Dimensionais
24
Para o caso discreto, temos:
fe(x,y)°g(x,y) =
1
MN
M −1 N −1
∑ ∑ fe * (m,n)ge(x - m, y - n) ,
m = 0 n =0
Para x = 0,1,2,...,M-1 e
y = 0,1,2,...,N-1.
Como no caso da correlação discreta 1-D, fe(x,y) e ge(x,y) são funções ou sinais estendidos com
períodos "M" e "N" respectivamente, tal que não ocorra erro de superposição, no período, da função
correlação.
O teorema da correlação para o caso de funções ou sinais discretos 2-D
fe(x,y)°ge(x,y) ⇔ F*e(u,v)Ge(u,v)
e
f*e(x,y)ge(x,y) ⇔ Fe(u,v)°Ge(u,v),
onde fe(x,y) é a função ou sinal estendida de f(x,y); ge(x,y) é a função ou sinal estendido de g(x,y); Fe*(u,v) é o
conjugado complexo estendido da transformada de Fourier de fe(x,y); Ge*(x,y) é o conjugado complexo
estendido da transformada de Fourier de ge(x,y); Fe(u,v) é a transformada de Fourier de fe(x,y) e Ge(u,v) é a
transformada de Fourier de ge(x,y).
Novamente aqui, por facilidade, são demonstrados somente os casos em 1-D, pois segundo [1],
[2] os resultados podem ser estendidos para os casos multi-dimensionais.
Sejam f(x) e g(x) funções ou sinais contínuos unidimensionais. Queremos demonstrar que:
f(x)°g(x) ⇔ F*(u,v)G(u,v).
Demostração:
∞ ∞
ℑ[f(x)°g(x)]= ∫
∫ f * (α )g(x - α) d α . exp(-j2π ux) dx
−∞ − ∞
∞ ∞
=
∫ ∫ f * (α )g(x) . exp(-j2 π uα) dα . exp(-j2π ux) dx
−∞ − ∞
ℑ[f(x)°g(x)] = F*(u,v)G(u,v)
CQD
25
Sejam f(x) e g(x) funções ou sinais contínuos unidimensionais. Queremos demonstrar que:
f*(x)°g(x) ⇔ F(u,v)G(u,v).
Demonstração:
∞ ∞
ℑ[f*(x)°+g(x)] =
∫ ∫ f * *(α )g(x - α ) dα . exp(-j2 π ux) dx
−∞ − ∞
∞ ∞
=
∫ ∫ f(α )g(x) . exp(-j2 π uα ) dα . exp(-j2 π ux) dx
−∞ − ∞
ℑ[f*(x)°+g(x)] = F(u,v)G(u,v),
onde: f**(α) = f(α)
CQD
Um caso especial de correlação cruzada é quando f(x) e g(x) são iguais. Nesse caso, dizemos
que é uma autocorrelação e que fisicamente nos mostra a comparação de um sinal com ele mesmo deslocado
no tempo e é denotado por:
∞
f(t)°f(t0 =
∫ f * (τ ) f(t - τ ) dτ,
−∞
com grande aplicabilidade em processamento de imagens, por exemplo, de radares, equipamento de ultrasom etc.
Devemos ter sempre em mente que a função ou sinal f(t) pode se contínuo ou discreto de uma ou
mais dimensões, periódico ou não.
VII _ Conclusão
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
26
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.
VIII - Referências Bibliográficas
[1] Gonzales, R.C., Woods, R.E., Digital Image Processing, USA: Addison-Wesley Pubisshing
Company, 1993.
[2] Oppenheim, A .V., Schafer , R.W., Digital Signal Processing, New Jersey: Prentece Hall, 1975.
[3] Lathi, B.P., Sistema de Comunicação, Rio de Janeiro: Guanabara Dois, 1979.
[4] Carlson, A .B., Sistemas de Comunicação: uma introdução aos sinais e ruídos em comunicação elétrica,
São Paulo: McGraw-Hill do Brasil, 1981.
[5] Pratt, W.K., Digital Image Processing, USA: John Wiley & Sons, Inc., 1991.
[6] Apostol T., M., Cálculo, vol. I, Rio de Janeiro: Reverté Ltda, 1979.