Upload
dinhhanh
View
217
Download
0
Embed Size (px)
Citation preview
Filtragem de Imagens no Domínio da Freqüência
35M34 – Sala 3D5Bruno Motta de CarvalhoDIMAp – Sala 15 – Ramal 227
DIM00972
Introdução Fourier formulou no início do século XVIII a
teoria de que qualquer função que se repete periodicamente pode ser representada como uma soma de senos e/ou cossenos de frequências diferentes, cada um multiplicado por um coeficiente próprio (Séries de Fourier)
Idéia foi recebida com ceticismo pelo meio científico da época
Mesmo funções nãoperiódicas podem ser representadas por integrais de senos e/ou cossenos, desde que a área sob a curva da função seja finita (Transformadas de Fourier)
DIM00973
Exemplo
Sinais com complexidade arbitrária (desde que sua integral seja finita) podem ser representados com precisão arbitrária através da soma de senoides
DIM00974
Transformada de Fourier
A transformada de Fourier, F(u), de uma função contínua de uma variável f(x) é
Dada F(u), f(x) pode ser obtida usandose
Juntas, essas funções formam o par de transformadas de Fourier, que em 2D são
F u =∫ f x e− j2 uxπ dx
f x =∫F u e j2 uxπ du
F u,v =∫∫ f x,y e− j2π ux+vy dxdy e f x,y =∫∫F u,v e j2π ux+vydudv
DIM00975
Transformada Discreta de Fourier Como estamos interessados em funções
discretas, iremos usar as DFTs, que são
Ao contrário do caso contínuo, as transformadas direta e inversa de Fourier sempre existem, desde que f(x) não possua valores infinitos
Usando a fórmula de Euler nós temos que
F u = 1M ∑x=0
M−1
f x e− j2 uxπ /M para u= 0,1 ,⋯,M−1 e
f x =∑u=0
M−1
F u e j2 uxπ /M para x= 0,1 ,⋯,M−1
e jθ=cos +jθ sinθ
F u = 1M ∑x= 0
M−1
f x [ cos2 uxπ /M− j sin2 uxπ /M ]
DIM00976
Transformada Discreta de Fourier O domínio (valores de u) de F(u) é chamado de
domínio da freqüência, porque u determina a freqüência dos componentes da transformada
Cada um dos termos de F(u) é chamado de componente de freqüência da transformada
Transformada geralmente é expressa em coordenadas polares usandose
F u =∣F u ∣e j u , onde ∣F u ∣=R2 u +I2 u e u =[ I u R u ]
DIM00978
Transformada Discreta de Fourier 2D No caso bidimensional as DFTs são
Deste modo, o especto de fourier, o ângulo de fase e o espectro de potência são, respectivamente
F u,v = 1MN ∑x=0
M−1
∑y=0
N−1
f x,y e− j2π ux /M+vy /N para u= 0,1 ,⋯,M−1,v= 0,1 ,⋯,N−1, e
f x =∑u=0
M−1
∑v=0
N−1
F u,v e j2π ux /M+vy /N para x= 0,1 ,⋯,M−1, y= 0,1 ,⋯,N−1
∣F u,v ∣=R2 u,v +I2 u,v
u,v =tan−1 [ I u,v R u,v ]
P u,v =∣F u,v ∣2=R2 u,v +I2 u,v
DIM00979
Transformada Discreta de Fourier É comum que se multiplique a função de entrada
f(x,y) por (1)x+y antes do cálculo da transformada de Fourier. Isso faz com que o origem da transformada de fourier seja movida para as coordenadas de freqüência (M/2,N/2), ou seja, o centro do retângulo de freqüência
O valor da transformada no ponto (u,v)=(0,0) é , ou seja, o valor da
transformada de Fourier de uma imagem no ponto (0,0) é a intensidade média da imagem
F 0,0 = 1MN ∑x=0
M−1
∑y=0
N−1f x,y
DIM009710
Transformada Discreta de Fourier O coeficiente de F(0,0) é geralmente chamado de
dc (direct current, corrente de freqüência zero) Se f(x,y) é real, nós temos que
Isto é, o espectro da transformada de Fourier é simétrico
Como no caso 1D, os relacionamentos entre as variáveis de amostragem nos domínios espacial e da freqüência são
F u,v =F¿ −u,−v e ∣F u,v ∣=∣F −u,−v ∣
u=Δ1
M xΔ e v=Δ1
N yΔ
DIM009712
Propriedades das DFTs Cada termo de F(u,v) contém todos os valores de
f(x,y), modificados pelos valores dos exponenciais, logo não é possível fazer associações umaum dos coeficientes com pixels
Entertanto podese falar em termos de carcterísticas da imagem. Por exemplo, o coeficiente de F(0,0) denota a intensidade média da imagem, coeficientes de baixos índices (freqüências) correspondem a componentes da imagem que variam pouco, enquanto que coeficientes de alta frequência são associados com variações brusacas de intensidade
DIM009713
Exemplo Note como as bordas
diagonais da imagem geram linhas diagonais na transformada de Fourier
DIM009714
Filtragem no Domínio da Freqüência A estrutura de uma aplicação que implementa
filtragem de imagens no domínio da freqüência é a seguinte
DIM009715
Filtros básicos Filtro notch remove
uma ou mais freqüências especificadas
Neste caso foi removida a freqüência F(0,0)
DIM009718
Exemplos de Filtros
Exemplos de filtros passabaixa e passaalta nos dois domínios
Máscaras usadas na filtragem nos dois domínios são aproximações discretas das funções mostradas aqui
DIM009719
Filtros de Suavização Filtro passabaixa “ideal” elimina completamente
coeficientes de freqüências acima de um limiar (threshold) escolhido
H u,v ={1 if Du,v ≤D0
0 if Du,v >D0 }
DIM009720
Exemplo Vários filtros passa
baixa ideais e percentuais da energia da transformada de Fourier retidas
DIM009721
Exemplo Aplicações dos filtros do slide
anterior Note os defeitos que aparecem
como ondas nas imagens processadas com os filtros com limiar menor (ringing artifacts)
DIM009722
Filtros Ideais Filtro espacial
correspondente a um filtro passabaixa ideal e sua aplicação a uma imagem
DIM009723
Filtro Butterworth O Filtro Butterworth
(BLPF) de ordem n e freqüência de corte D0 a partir da origem é definido por
H u , v= 1
1[D u ,v/D0 ]2n
Definese D0 como o ponto no qual a função H(u,v) está abaixo de uma certa fração de seu valor máximo (geralmente 0.5 ou 50%)
DIM009724
Filtro Butterworth Aplicações de filtros
Butterworth de ordem 2 com as freqüências de corte de 5, 15, 30, 80 e 230
Note que os defeitos que aparecem como ondas nas imagens processadas não aparecem mais
DIM009726
Filtros Gaussianos São definidos por Trocase σ2 por D0. Quando D(u,v)=D0, o filtro tem
0.607 do seu valor máximo A transformada inversa de Fourier de um filtro
Gaussiano é também uma Gaussiana, logo eles não produzirão ringing
H u,v =e−D2 u,v /2 2
DIM009727
Filtros Gaussianos Garantem a não
existência de artefatos de ringing
Menos controle na sua especificação que os Butterworth
DIM009728
Filtros Gaussianos Aplicações reais: • suavização de
documentos para posterior reconhecimento de padrões
• Retoque de imagens para publicações
• Remoção de ruídos ou eliminação de características não desejadas de imagens
DIM009730
Filtros Gaussianos
Valores de D0 diferentes podem ser usados na mesma imagem para diferentes fins
DIM009731
Filtros PassaAlta O objetivo dos filtros
passaalta é exatamente o inverso dos filtro passabaixa, logo temos a relação
Agora nós vamos ver os filtros passaalta referentes aos filtros passabaixa vistos na aula passada (ideal, Butterworth e Gaussiano)
DIM009732
Filtros PassaAlta Representação
espacial dos filtros podem ser obtidas multiplicandose H(u,v) por (1)u+v, calculandose a IDFT, e multiplicandose a parte real do resultado por (1)x+y
DIM009733
Filtros PassaAlta De modo similar aos filtros passabaixa, os filtros
passaalta ideal, Butterworth e Gaussiano são representados respectivamente por
H u,v ={0 if Du,v ≤D0
1 if Du,v >D0 }H u,v =1
1[D0 /D u,v ]2n
H u,v =1−e−D2u,v /2D0
2
DIM009734
Filtros PassaAlta Devido ao relacionamento com o filtro ideal
passabaixa, é esperado que o filtro ideal passaalta exiba o mesmo artefato de ringing
Mais uma vez os filtros Butterworth podem ser vistos como um meio termo entre os filtros ideias e os Gaussianos
Isto pode ser visto nos exemplos do próximo slide, onde as transições nas bordas de pequenos objetos são detectadas de forma mais clara quando os filtros Gaussianos são usados
DIM009736
O Laplaciano no Domínio da Freqüência Usandose as propriedades da Transformada de
Fourier, nós temos que
Em 2D nós temos que
Ou seja, o resultado é o Laplaciano no domínio da freqüência, e o mesmo pode ser implementado usando o filtro
ℑ[ dn f x dx n ]= ju n F u
ℑ[∂2 f x,y ∂ x2
∂2 f x,y ∂ y2 ]= ju 2 F u,v jv 2 F u,v =−u2+v2 F u,v
H u,v =−u2+v2
DIM009737
O Laplaciano no Domínio da Freqüência Como estamos multiplicando f(x,y) por (1)x+y
antes de aplicar a Transformada de Fourier, o Laplaciano em uma janela de freqüência MxN é
Assim temos a relação
Geralmente combinase o Laplaciano com a adição a imagem original em um único filtro, gerando
H u,v =[−u−M /2 2v−N /2 2 ]
∇2 f x,y ⇔ [−u−M /2 2v−N /2 2 ]F u,v
g x,y ⇔ [1u−M /2 2v−N /2 2 ]F u,v
DIM009738
O Laplaciano no Domínio da Freqüência
Ao lado temos o filtro Laplaciano no domínio da freqüência mostrado em um plot 3D e em uma imagem, e sua representação espacial, após usar a transformada inversa
Note a semelhança com o filtro espacial definido anteriormente
DIM009739
Exemplo Exemplo usando
mesma imagem que no caso do Laplaciano no domínio espacial
Efeitos de realce obtidos pelos dois filtros são praticamente iguais
DIM009740
Filtros HighBoosting Como no caso do domínio espacial, podese
atenuar e não eliminar as baixas freqüências, usando filtros highboosting
Como filtros passabaixa e passaalta são complementares, podemos reescrever f como
Logo, podemos obter um filtro highboost usandof hp x,y =f x,y − f lp x,y
f hb x,y =Af x,y − f lp x,y f hb x,y = A−1 f x,y +f x,y − f lp x,y = A−1 f x,y +f hp x,y
DIM009741
Exemplo Se A=1, o filtro de
highboosting se reduz a um filtro passaalta
A medida que A>1 aumenta, aumentam as contribuições da imagem original na imagem filtrada
DIM009742
Ênfase de Altas Freqüências
Em alguns casos, é interessante que se aumente a contribuição dos componentes de alta freqüência de uma imagem para melhorar o contraste
Neste caso, o filtro é definido por uma constante (b) que multiplica um filtro passaalta somado a uma outra constante (a), que faz com que as baixas freqüências são sejam totalmente eliminadas
Quando a=(A1) e b=1, este filtro se reduz ao highboosting
Hhfeu,v =a+bHhpu,v , onde a≥0 e b>a
DIM009743
Exemplo
Filtro de ênfase de altas freqüências mantém características de baixa freqüência da imagem original
Imagem filtrada foi equalizada para melhoria do contraste
DIM009744
Aspectos de Implementação Algumas propriedades da Transformada de
Fourier 2D sãoTranslação:
logo temos
Distributividade e redimensionamento:
f x,y ej2π u0 x /M+v0 y /N
⇔F u−u0 ,v−v0 e
f x−x 0 ,y−y0⇔F u,v e− j2π u0 x /M+v0 y /N
f x,y −1 x+y ⇔F u−M /2,v−N /2 ef x−M /2, y−N /2 ⇔F u,v −1 u+v
ℑ [ f 1 x,y +f 2 x,y ]=ℑ [ f 1 x,y ]ℑ [ f 2 x,y ] , e geralmenteℑ [ f 1 x,y ⋅f 2 x,y ]≠ℑ [ f 1 x,y ]⋅ℑ [ f 2 x,y ]af x,y ⇔aF u,v e f ax,by ⇔1
ab F u/a,v /b
DIM009745
Propriedades da FT 2DRotação: Se usarmos coordenadas polares,
temos e logo
Periodicidade:
Simetria conjugada:
F u,v =F u+M,v =F u,v+N =F u+M,v+N ,f x,y =f x+M,y =f x,y+N =f x+M,y+N
F u,v =F −u,−v ,∣F u,v ∣=∣F −u,−v ∣
x=r cos , y=r sin , u=cos , v= sin ,f x , y f r , e F u , vF , ,f r ,0⇔F ,0
DIM009747
Propriedades da FT 2DSeparabilidade: a Transformada discreta de
Fourier 2D pode ser expressa na forma separada do seguinte modo
F u,v =1M ∑
x=0
M−1
e− j2 uxπ /M 1N ∑y=0
N−1
f x,y e− j2 vyπ /N
=1M ∑
x=0
M−1
F x,v e− j2 uxπ /M
onde F x,v =1N ∑y=0
N−1
f x,y e− j2 vyπ /N
DIM009748
Padding Transformada de
Fourier assume periodicidade das funções
Funções devem ser preenchidas com zeros (padded) para que seu tamanho seja P≥ A+B1, onde A e B são os suportes das funções
DIM009749
Padding
Após padding, resultado esperado é obtido quando convolução é implementada no domínio da freqüência
DIM009750
Padding Funciona do mesmo
modo no caso 2D, onde imagens devem ter dimensões de P≥ A+C1 e Q≥ B+D1
Resultado é uma imagem quatro vezes maior que as originais
Imagens resultado são extraídas destas imagens PxQ
DIM009752
Correlação A correlação entre duas
funções é definida por
Como nós lidamos com funções reais (nãocomplexas), f*=f, e a correlação é bastante parecida com a convolução (note a troca de sinais)
f x,y °h x,y = 1MN ∑m=0
M−1
∑n=0
N−1
f m,nh x+m,y+n
f x , y°h x , y⇔F∗ u ,vH u , vf ∗ x , y°h x , y⇔F u ,v°H u ,v
DIM009758
Translação
Translação da imagem no domínio espacial muda somente a fase da Transformada de Fourier, logo não há alterações nas imagens que mostram a magnitude da FT
DIM009759
FFT
F u =1M ∑
x=0
M−1
f x W Mux onde W M =e− j2π /M
e M= 2n , logo M= 2K
F u =12K ∑
x= 0
2K−1
f x W 2Kux
=12 [1K ∑x=0
K−1
f 2x W 2Ku 2x
1K ∑x=0
K−1
f 2x1W 2Ku2x1]
DIM009760
FFTComo W 2K
2ux =W 2Kux
F u =12 [1K ∑x=0
K−1
f 2x W Kux
1K ∑x=0
K−1
f 2x1 W Kux W 2K
u ]Definindo F paru =
1K ∑x=0
K−1f 2x W K
ux e
F imparu =1K ∑x= 0
K−1f 2x1WK
ux
temos F u =12 [F paru +F imparu W 2K
u ]
DIM009761
FFT
Assim podemos calcular F(u+K) a partir dos valores que calculamos para F(u)
Como W Mu+M =W M
u e W 2Mu+M=−W 2M
u
temos F u+K =12 [F paru −F imparu W 2K
u ]
DIM009762
FFT Exemplo F( 0,1,2,...,15 ) = F( xxxx_2 ) | | | | F( par ) F( impar ) = F( 0,2,4,...,14) = F( 1,3,5,...,15 ) = F( xxx0_2 ) = F( xxx1_2 ) | | | | | | | | F( 0,4,8,12 ) F( 2,6,10,14 ) F( 1,5,9,13 ) F( 3,7,11,15 ) = F( xx00_2 ) = F( xx10_2 ) = F( xx01_2 ) = F( xx11_2 ) | | | | | | | | | | | | | | | |F( 0,8 ) F( 4,12 ) F( 2,10 ) F( 6,14 ) F( 1,9 ) F( 5,13 ) F( 3,11 ) F( 7,15 )= F( x000_2 ) = F( x100_2 ) = F( x010_2 ) = F( x110_2 ) = F( x001_2 ) = F( x101_2 ) = F( x011_2 ) = F( x111_2 ) | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |F(0) F(8) F(4) F(12) F(2) F(10) F(6) F(14) F(1) F(9) F(5) F(13) F(3) F(11) F(7) F(15)0000 1000 0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 0111 1111
DIM009763
FFT
Apesar de ter uma estrutura recursiva, a FFT geralmente é implementada iterativamente, por questões de eficiência
Ordem dos coeficientes não é a desejada e deve ser reorganizada
DIM009764
Ordenação da FFT
SaídadaFFT OrdemDesejadah0+h1=F0 000 F 0 000 h0−h1=F 4 100 F1 001 h2+h3 =F2 010 F2 010 h2−h3=F6 110 F3 011 h4+h5=F1 001 F4 100 h4−h5=F 5 101 F5 101 h6+h7 =F3 011 F6 120 h6−h7=F7 111 F 7 111
DIM009765
FFT x DFT Tabela mostra fatores
de aceleração da execução do cálculo da FT usando o método tradicional (DFT) e o FFT
DFT – O(M2) FFT – O(M logM)
DIM009766
Exemplo (Filtro Notch) Nos filtros notch,
frequências eliminadas não aparecem na imagem final
Adequado para remover ruídos periódicos que as vezes afetam sensores de aquisição de imagens
DIM009768
Trabalhos Acessem a página da disciplina e acessem os links
no item Trabalhos Vocês devem baixar o programa PDI, e os arquivos
para desenvolver programas em Qt, caso necessário
As operações definidas nos trabalhos devem ser incorporadas ao programa PDI, inserindo novas janelas de interface quando preciso
Implementações devem ser testadas nas imagens que estarão disponíveis na página
DIM009769
Trabalhos
As operações a serem implementadas são:Equalização de histogramas (deve mostrar
janelas com o histograma antes e depois de equalizado)
Filtros de suavização Butterworth e da mediana (3x3, 5x5, 7x7 e 9x9)
Deteção de bordas (Sobel e laplaciano)Realce de imagens interativa no domínio da
frequência (filtros notch)