Aplicação da Transformada de Fourier noPROCESSAMENTO DIGITAL DE IMAGENS

João Fonseca NetoAracaju- Se, novembro de 1999.e-mail: jfonseca@sergipe.com.br

Resumo - Este trabalho apresenta a aplicabilidade da Transformada de Fourier no processamento deimagens. 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 algumasde suas propriedades importantes.

Abstract -This paper presents the aplicability of Fourier Transform in the image processing. A simplified studyof Fourier's mathematical development for functions or signals: continuous or discretes in one or twodimensions, 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 nomedevidamente publicado. O autor não se responsabiliza por interpretações incorretas do conteúdo destetrabalho.

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. Sinais contínuos periódicos unidemensionais;2. Sinais contínuos não periódicos unidimensionais;3. Sinais contínuos periódicos bi-dimensionais;4. Sinais contínuos não periódicos bi-dimensionais;5. Sinais discretos periódicos unidimensionais;6. Sinais discretos não periódicos unidimensionais;7. Sinais discretos periódicos bi-dimensionais;8. 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. Convolução na freqüência de dois sinais contínuos unidimensional;3. Convolução de sinais discretos unidimensionais;4. Convolução de sinais contínuos bi-dimensionais;5. Convolução de sinais discretos bi-dimensionais;

• Funções de Correlação

1. Correlação cruzada entre sinais contínuos unidimensionais;2. Correlação cruzada entre sinais discretos unidimensionais;3. Correlação cruzada entre sinais contínuos bi-dimensionais;4. 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 áreasde 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 ysão coordenadas espaciais e o valor de f em um ponto qualquer (x,y) é proporcional ao brilho ou nível decinza da imagem naquele ponto. Uma imagem digital é uma imagem f(x,y) discretizada no espaço e naintensidade de brilho e pode ser considerada uma matriz, cujos elementos são chamados de "pixels" ("pictureelements").

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 dosproblemas de processamento digital de imagens (sinais bi-dimensionais) pois, muitas vezes, é conveniente amudança do domínio do tempo ou espaço (x,y) para o domínio da freqüência facilitando, assim, o seuprocessamento.

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 detransferência de um filtro (convenientemente de acordo com a aplicação)no entanto, muitas vezes, é maissimples "zerarmos" os coeficientes das componentes de freqüência que queremos filtrar e tomamos, emseguida, 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 defreqüê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ódicosou 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 nointervalo (-∞,∞); ou seja , podemos decompor f(t) em componentes senoidais e cossenoidais (ouexponenciais):

f t( ) = Fn n = -∞

∞

∑ ejnωot , (1)

onde

Fn = 1T

f(t)to

to+T

∫ e-jnωot dt , (2)

o período de f(t) é T = ωπ o

2, ωo = 2πfo é a freqüência fundamental em rad/s e fo é a freqüência fundamental

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 eintegrar no tempo (período):

f t( ) = Fn n = -∞

∞

∑ ejnωot , temos

to

to T+

∫ f(t) e-jnωot dt = Fnn=−∞

∞

∑to

to T+

∫ ejnωot e-jnωot dt

to

to T+

∫ f(t) e-jnωot dt = Fnn=−∞

∞

∑to

to T+

∫ dt = Fnn=−∞

∞

∑ T

to

to T+

∫ f(t) e-jnωot dt = Fn T, logo

Fn = 1T

f(t)to

to+T

∫ e-jnωot dt

4

Portanto, a expansão de uma função periódica em série de Fourier equivale a decomposição dafunção em termos de suas componentes de várias freqüências ou seja, um sinal periódico apresenta umespectro de freqüência discreto e infinito.

O espectro de freqüência discreto aparece em um gráfico como linhas verticais espaçadas, comalturas proporcionais ao coeficiente da componente de freqüência (Fn) correspondente. No entanto, se formosrigorosos, necessitamos de dois gráficos para representar, completamente, uma função periódica no domínioda freqüência: o espectro e amplitude e o espectro de fase; visto que, os coeficientes Fns, normalmente, sãocomplexos.

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 quenão satisfaz a condição de integrabilidade absoluta no intervalo (-∞, ∞) (condição suficiente, mas nãonecessária). Porém, a transformada existe no limite, ou seja a transformada de Fourier de uma funçãoperiódica é a soma das transformadas da Fourier das suas componentes individuais, obtidas pela sua série deFourier.

Seja a série de Fourier de f(t), periódica em T:

f(t) = Fnn=−∞

∞

∑ ejnωot , onde ωo = 2 Tπ

rad. Tomando a transformada de Fourier em ambos os lados, temos:

ℑ[f(t)] = ℑ [ Fnn=−∞

∞

∑ ejnωot]

= Fnn=−∞

∞

∑ ℑ[ejnωot], como, [3], ℑ[ejnωot] = 2πδ(ω - ωo), obtem-se:

ℑ[f(t)] = 2π Fn ( - n o)δ ω ω−∞

∞

∑ (3)

A transformada de Fourier de um sinal periódico é formada por impulsos localizados nasfreqüências harmônicas do sinal e que o peso de cada impulso é 2π vezes o valor do coeficiente na sérieexponencial de Fourier (Equação 2).

2.3 - Representação de uma função arbitrária (não periódica) em todo o intervalo(-∞∞ ,∞∞): ATransformada de Fourier.

A transformada de Fourier, F(u), é a decomposição do sinal, f(x), de energia finita (nãoperió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áficode 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 ointervalo (-∞< x < ∞).

Observação:Quando a função é temporal (x = t) e a variável independente de freqüência é dada em rad/s (u =

ω), normalmente aparece um fator 1

2π multiplicando a integral; ou seja:

f(t) = 1

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 Hzao invés de ω:ω = 2πf,dω = 2πdf, logo

f(t) = 1

2πF( )2πf

−∞

∞

∫ ej2πft 2π df

f(t) = F( )2πf−∞

∞

∫ ej2πft df

6

As equações apresentadas acima são normalmente conhecidas como par de transformadas deFourier. 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

φ(u,v) = tg-1 I(u, v)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 arepresentação de uma seqüência não periódica pela Transformada Discreta de Fourier, DFT 1-D, sãoferramentas matemáticas de grande utilidade no processamento de sinais digitais, como apresentado nasseçõ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ódicaapresenta somente N exponenciais complexas. Isso ocorre devido a periodicidade da função ej2πkx/N em kcom 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 valorde x inteiro. Logo:

e1(x) = eN+1(x)

Assim,

f(x) = Fu

N

(u)=

−

∑0

1

ej(2πux/N) , (8)

x = 0,1,2, ..., N-1 (número de amostras);u = 0,1,2, ..., N-1 (variável independente de freqüência);

8

F(u) = 1N

f xx

N

( )=

−

∑0

1

e-j(2πux/N) , (9)

As Equações 8 e 9 são o par de transformadas para representação de uma Série Discreta deFourier (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].

x

N

=

−

∑0

1

f(x) e-j(2πux/N) = x

N

=

−

∑0

1

Fu

N

(u)=

−

∑0

1

ej(2πux/N) e-j(2πux/N) , permutando os somatórios

x

N

=

−

∑0

1

f(x) e-j(2πux/N) = Fu

N

(u)=

−

∑0

1

x

N

=

−

∑0

1

ej(2πux/N) e-j(2πux/N) ,

usando a propriedade dos somatórios: Kn

N

=∑

0

= K n

N

=∑

0

= KN, onde K é uma constante, e o somatório

Fu

N

(u)=

−

∑0

1

representa a seqüência periódica dos coeficientes da série de Fourier: F(0), F(1), F(2), ..., F(N-1),

denotada por F(u). Temos, então:

x

N

=

−

∑0

1

f(x) e-j(2πux/N) = F(u) N,

1N x

N

=

−

∑0

1

f(x) e-j(2πux/N) = F(u)

3.2 - Representação de uma Seqüência de Duração Finita (não periódica) 1-D, TransformadaDiscreta de Fourier (DFT -1D)

Seja uma seqüência de duração finita g(x) de comprimento N, tal que g(x) = 0 fora do intervalo0≤ 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 + rN)r =−∞

∞

∑ ,

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 deum período:

g(x) = f (x), 0 x N -1

, fora

≤ ≤0

Por conveniência matemática, definimos uma seqüência retangular RN(x) tal que:

RN = 1

0

, 0 x N -1

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ódicoscom 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) = 1N

f(x)x

N

=

−

∑0

1

e-j(2πux/N) , e

f(x) = F(u)u

N

=

−

∑0

1

ej(2πux/N) ,

temos o par de Transformadas Discretas de Fourier: DFT 1-D

• G(u) = 1

00

1

N x

N

g(x) exp(-j2 ux / N) , 0 u N -1

, fora

π ≤ ≤

=

−

∑ (10)

• g(x) = G u

u o

N

( )exp(j2 ux / N), 0 x N -1

, fora

π ≤ ≤

=

−

∑1

0 (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 umperíodo de uma seqüência periódica e a partir daí, efetuamos os cálculos para encontrar os coeficientes deFourier (DFT).

IV - Transformada Discreta de Fourier Bi-Dimensional

Esta ferramenta matemática é muito empregada no processamento de imagens e sinais bi-dimensionais, 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 daslinhas, "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 deexponenciais complexas, de seguinte maneira:

f(x,y) = F(u, v)v

N

u

M

=

−

=

−

∑∑0

1

0

1

ej2π (ux/M + vy/N) (12)

onde,

F(u,v) = 1

MNf(x,y)

y

N

x

M

=

−

=

−

∑∑0

1

0

1

e-j2π (ux/M + vy/N) (13)

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; ouseja, uma seqüência de duração finita é considerada como sendo um período da seqüência periódicacorrespondente.

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

RN (x,y) = 1

0

, 0 x M -1, 0 y N -1

, fora

≤ ≤ ≤ ≤

G(u,v) =

1

00

1

0

1

NM y

N

x

M

g(x)exp(-j2 ux / M) exp(-j2 vy / N) , 0 x M -1, 0 y N -1

, fora

π π ≤ ≤ ≤ ≤

=

−

=

−

∑∑ (14)

g(x,y) =

Gv

N

u

M

(u, v)exp(j2 ux / M) exp(j2 vy / N), 0 x M -1, 0 y N -1

, fora

π π ≤ ≤ ≤ ≤=

−

=

−

∑∑0

1

0

1

0

(15)

Observação, uma opção para implantação de DFT 2-D é utilizar uma DFT 1-D para as linhas eDFT 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 FourierTemos 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 esclarecedorasse 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çõesno outro domínio.

Segundo [2], muitas propriedades das Transformadas de Fourier discutidas em uma dimensãopodem ser estendidas para sinais multi-dimensionais. Por isso, vamos demonstrar algumas propriedades dasTransformadas 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 doispassos 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:

f(x,y) = F(u, v)v

N

u

M

=

−

=

−

∑∑0

1

0

1

ej2π (ux/M + vy/N) , onde x, y = 0,1, ..., N-1

F(u,v) = 1

MNf x y

y

N

x

M

( , )=

−

=

−

∑∑0

1

0

1

e-j2π (ux/M + vy/N) , onde u,v = 0,1, ..., M-1

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):

F(x,v) = M

1

0

1

MN x

M

y=0

N -1

f(x, y)∑∑=

−

e-j2πyv/N e-j2πux/M

x=cte

F(x,v) = 1

0

1

Nf x y

y

N

( , )=

−

∑ e-j2πvy/N x

M

j ux M=

−

∑ −

0

1

2exp( / )π

x=cte

13

F(x,v) = 1

0

1

N y

N

=

−

∑ f(x,y) e-j2πyv/N

Efetuando, agora, a transformação sobre as colunas:

F(u,v) = 1

0

1

MN x

M

=

−

∑ F x vx

M

( , )=

−

∑0

1

e-j2πux/M e-j2πvy/N

y=cte

F(u,v) =1 1

0

1

0

1

M Nf x y

x

M

y

N

=

−

=

−

∑ ∑

( , ) exp(-j2 vy / Nπ e-j2πux/M

F(u,v) =1

0

1

0

1

MNf x y

y

N

x

M

( , )=

−

=

−

∑∑ e-j2πvy/N e-j2πuc/M

F(u,v) =1

0

1

0

1

MNf x y

y

N

x

M

( , )=

−

=

−

∑∑ e-j2π (ux/M + vy/N)

assim, concluímos que:

F(u,v) =1M

x

M

=

−

∑0

1

e-j2πux/M 1N

f x yy

N

( , )=

−

∑0

1

e-j2πyv/N

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) resultanum deslocamento na freqüência para o ponto (uo, vo).

De maneira análoga, se multiplicarmos a transformada F(u,v) pela mesma exponencial etomarmos 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)

ℑ[f(x,y)ej2π (uo x/M + vo y/N)] = 1

MNf(x,y)

y

N

x

M

=

−

=

−

∑∑0

1

0

1

ej2π (uo x/M + vo y/N) e-j2π (ux/M +vy/N)

= 1

MNf x y

y

N

x

M

( , )=

−

=

−

∑∑0

1

0

1

ej2π [(uo x - ux)/M + (vo y - vy)/N]

= 1

MNf x y

y

N

x

M

( , )=

−

=

−

∑∑0

1

0

1

ej2π [(uo - u)x/M + (vo - v)y/N]

ℑ[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 paraespecificar 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 No período das colunas.

ℑ[f(x, y)] ⇔ F(u, v)

ℑ[f(x+M, y+N)] ⇔ F(u+M, v+N),

F(u, v) = 1

MNf x y

y

N

x

M

( , )=

−

=

−

∑∑0

1

0

1

e-j2π (ux/M + vy/N) ,

15

substituindo "x" por "x+M" "y" por "y+N"

temos

ℑ[f(x+M, y+N)] = 1

MNf x M

y

N

x

M

( ,+=

−

=

−

∑∑ y + N)0

1

0

1

e-j2π[u(x+M)/M e-j2πv(y+N)/N] =

= 1

MNf x M

y

N

x

M

( ,+=

−

=

−

∑∑ y + N)0

1

0

1

e -j2π ux/M e-j2πuM/M e-j2πvy/N e-j2πvN/N

= 1

MNf x M

y

N

x

M

( ,+=

−

=

−

∑∑ y + N)0

1

0

1

e -j2π (ux/M +vN/N) e-j2πuM/M e-j2π vy/N

=1

MN f x M

y

N

x

M

( ,+=

−

=

−

∑∑ y + N)0

1

0

1

e -j2π u(x+M)/M e-j2π v(y+N)/N

ℑ[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çãoem F(u,v) e vice-versa.Nesta demonstração utilizamos uma função discreta de uma dimensão, para facilidade dos cálculos, sendo queos 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) = 1N

f xx

N

( )=

−

∑0

1

e-j(2π ux/N)

16

Queremos demonstrar que: f(r cosθ) ⇔ F(ω cosϕ) f[r cos(θ + α)] ⇔ F[ω cos(ϕ + α)]

F(ω cosϕ) = 1N

fx

r

( r cos )θ=

∑0

e-j(2π ω cosϕ r cosθ)/N

Impondo um ângulo de giro a f(x, y) igual a "α", temos:

ℑ{f[r cos(θ + α)]} = 1N

f rx

r

[ cos(θ α + )=

∑0

e-j2π ω r/N [ cosϕ cos(θ + α)]

= 1N

f rx

r

[ cos(θ α + )=

∑0

e-j 2π ω r/N {cosϕ [cosθ cosα - sinθ sinα]}

= 1N

f rx

r

[ cos(θ α + )=

∑0

e-j2π ω r/N{cosϕ 12

[cos(θ - α) + cos(θ + α)] - 12

[cos(θ - α) - cos(θ + α)]}

=1N

f rx

r

[ cos(θ α + )=

∑0

e-jπ ω r/N{cosϕ [cos(θ - α) + cos(θ + α)] + [cos(θ - α) + cos(θ + α)]}

=1N

f rx

r

[ cos(θ α + )=

∑0

e-jπ ω r/N{cosϕ [cos(θ + α)] + cos(θ + α)}

= 1N

f rx

r

[ cos(θ α + )=

∑0

e-j2π ω r/N[cosϕ cos(θ + α) ]

ℑ{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 emfreqüência.Inicialmente, para facilidade de análise, desenvolveremos a convolução de duas funções contínuas de umadimensã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 atransformada 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) comotransformada, 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 transformadainversa 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 - ) 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-

j2π u α.

Logo:

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 ℑ-1[G(u)] = g x( ) −∞

∞

∫ e- j2πux dx, temos:

F(u)*G(u) = F( )α−∞

∞

∫ ej2πuα dα g x( ) −∞

∞

∫ e- j2πux dx = f x g x( ) ( )−∞

∞

∫ e- j2πux dx

F(u)*G(u) = ℑ[f(x(g(x)]

CQD

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çõesperió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çõesdiscretas 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) comg(x) é periódica de período, também, "M". O valor de "M" deve ser maior ou igual do que A+B-1 para evitarerro 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 nemdesaparecimento de freqüências) no seu espectro de freqüências mas sim, apenas o espalhamos.

Estendendo as funções:

fe(x) = f(x) , 0 x A -1

0 , A x M -1

≤ ≤≤ ≤

ge(x) = g(x) , 0 x B -1

0 , B x M -1

≤ ≤≤ ≤

21

Assim, temos:

• fe(x)*ge(x) = 1

0

1

M m

M

fe(m)ge(x - m)=

−

∑ ,

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)efe(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 aconvoluçã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 resultadosvá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) comtamanhos 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:

fe(x,y) = f(x,y), 0 x A -1 e 0 y B -1

, A x M -1 ou B y N -1

≤ ≤ ≤ ≤≤ ≤ ≤ ≤

0

e

ge(x,y) = g(x,y), 0 x C -1 e 0 y D -1

, C x M -1 ou D y N -1

≤ ≤ ≤ ≤≤ ≤ ≤ ≤

0

Então, definimos a convolução discreta 2-D, como:

fe(x,y)*ge(x,y) = 1

0

1

0

1

MNfe

n

N

m

M

(m,n)ge(x - m,y - n)=

−

=

−

∑∑ ,

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 sinaisno 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 asimilaridade 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 maisdimensõ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

0

1

M m

M

f *e(m)ge(x- m)=

−

∑ ,

para x = 0,1,2, ..., M-1.

Observação, os comentários feitos anteriormente sobre as funções ou sinais estendidos fe(x) ege(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 bi-dimensional.

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 datransformada 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

0

1

0

1

MN n

N

m

M

fe* (m,n)ge(x - m, y - n) ,=

−

=

−

∑∑

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 comperíodos "M" e "N" respectivamente, tal que não ocorra erro de superposição, no período, da funçãocorrelaçã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) é oconjugado complexo estendido da transformada de Fourier de fe(x,y); Ge*(x,y) é o conjugado complexoestendido da transformada de Fourier de ge(x,y); Fe(u,v) é a transformada de Fourier de fe(x,y) e Ge(u,v) é atransformada 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, dizemosque é uma autocorrelação e que fisicamente nos mostra a comparação de um sinal com ele mesmo deslocadono 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 ultra-som etc.

Devemos ter sempre em mente que a função ou sinal f(t) pode se contínuo ou discreto de uma oumais 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 evelocidade de processamento, o processamento Digital de Imagens tem sido cada vez mais utilizado paraanálise e diagnósticos.

Uma das ferramentas mais utilizada neste processamento é a transformada de Fourier, a qual nospermite ter uma visão da imagem a ser analisada no domínio da freqüência, facilitando sobremaneira estaaná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 umamaneira 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.