Transformadas e Decomposição de Sub-banda

Transformadas e Decomposição de Sub-

banda

Joaquim MacedoDepartamento de Informática da Universidade do Minho &

Faculdade de Engenharia da Universidade Católica de Angola

Sumário Tranformada Unitária 1-D Transformada Discreta de Fourier 1-D Transformada Discreta do Coseno 1-D Filtragem Digital e Análise de sub-banda

Filtros Digitais Análise de sub-banda Transformadas e Filtragem Digital

Transforma Discreta Wavelet 1-D Tranformada Unitária 2-D Transformada Discreta de Fourier 2-D Transformada Discreta do Coseno 2-D Transforma Discreta Wavelet 2-D

Transformada Unitária 1-D

unitária ada transformda matriz a é

)1,1(......)0,1(

............

............

)1,0(......)0,0(

e ada transformda escoeficient de matriz a é )(

10 ),()(,

como se-define l)(ortonorma unitária madaA transfor

onalunidimensi sequência uma ,10),( Seja

1

0

NNuNu

Nuu

kFF

Nk f(n)nkUkFfUF

Nnnf

N

n


Ude base

vectoresos asconsiderad saõ Ude colunas ,10),,(

sequência da

sériespor çãorepresenta a aconsideradser pode acima equaçãoA

a transpostmatriz a e complexa oconjungaçã significam T e *

10 ),()()(,

como se-define inversa aunitári madaA transfor

*T*

1

0

**

Nnnku

f(n)

NnnkukFnfFUfN

n

T


0k se 0

0k se 1)(

unitário impulso de discreta função a é )( Onde

)(),(),(

)(),(),(

condições seguintes as cumprirem se se unitária é matrizA

1

000

*

1

000

*

k

k

nnnkunku

kknkunku

N

k

N

n

Transformada Discreta de Fourier 1-D

1

0

1 N

n

knNWnf

NkF

nf - sequência discreta periódica com N amostras por período.

10 Nk DFT

IDFT10 Nn

kF - k-ésimo coeficiente DFT

1

0

1 N

k

knNWnF

Nnf

N

knjkn

N eW2


N

kjkn

NT

N

kjkn

N

eN

WN

knunkuUU

eN

WN

nkuU

2***1

2

11)},({)},({

por dadaFourier de inversa ada transformda Matriz

11)},({

por dadaFourier de ada transformda Matriz

Transformada Discreta de Fourier 1-DExemplo 5.1

Considere uma sequência de 4 pontos f={2,5,7,6}. Calcule os correspondentes coeficientes DFT. Reconstrua a sequência de entrada a partir dos coeficientes DFT e das funções de base DFT


Transformada Discreta de Fourier 1-DPar alternativo

Definição do DFT alternativa Usada por muitas concretizações (MATLAB)

Diferença apenas de escala Ortogonal mas mas não ortonormal ou

unitária

1

0

N

n

knNWnfkF

1

0

1 N

k

knNWnF

Nnf

10 Nk

10 Nn

Propriedades da DFT Convulsão

Rapidez da concretização Conservação da Energia e

Compactação

frequência da domínio no Convulsão )()()()(

tempodo domínio no Convulsão )()()()(

KGkFngnf

KGkFngnf

21

0

21

0

)()(

N

k

N

n

kFnf

Convolução

)()()()( kGkFngnf

)()()()( kGkFngnf

Convolução Circular

Fast Fourier Transform

Os coeficientes da DFT de N pontos podem ser calculados multiplicando a matriz de transformação 2D pela matriz 1D O cálculo directo da DFT 1D para uma sequência de N-pontos requer N*N operações onde 1 operação = 1 multiplicação complexa + 1 adição complexa.

Há disponíveis algoritmos especiais com uma complexidade muito menor para calcular a DFT. Esses algoritmos são conhecidos como Fast Fourier Transform (FFT).

NN1N

2N

Diferentes algoritmos FFT

Radix-2

Radix-4

Split-Radix

Winograd

Prime Factor

Foram propostos na literatura vários algoritmos FFT. Alguns dos mais populares são os seguintes:

Algoritmo Radix-2

Radix-2 é um algoritmo popular para FFT.

Para transformada de N pontos a complexidade computaciona é borboletas

onde 1 borboleta = multiplicação complexa + 2 adições complexas

O algoritmo FFT usa um arranjo dos dados que parece uma borboleta.

NN 2log)2/(

Complexidade FT versus FFT

N N2

(FT Directo)

N log2 N (FFT)

Ganhos Computacionais N2/N log2 N

32 1024 160 6.4

256 65536 2048 32

1024 1048576 10240 102

8192 67108864

106496 630

Conservação da Energia

A Transformada de Fourier preserva a energia do sinal.

A energia do sinal no domínio do tempo ou pixel é idêntica à energia no domínio da frequência.

1

0

21

0

2)()(

N

k

N

n

kFnf

Embora a energia total não mude no domínio de Fourier, a energia é redistribuída entre os coeficientes de Fourier.

Exemplo 5.2 Construa um sinal unidimensional dos

valores de pixel da linha #100 da figura da Lena a preto e branco. Para evitar o componente DC torne o sinal com média 0 (substraia o valor da média de cada pixel). Calcula a DFT e a energia total nos 20

primeiros coeficientes de Fourier. Compare com a energia total do sinal.

Compactação de energia com a DFT

Linha horizontal (line# 100) da imagem da lena

Espectro de Amplitude

Transformada Discreta do Coseno 1-D A Transformada Discreta do Coseno (DCT)

unidimensional para a sequência de entrada f(n) é definida pelo seguinte par:

10 para

0 para

/2

/1)(

10 para )(2

)12(cos)()(

10 para 2

)12(cos)()()(

1

0

1

0

Nk

k

N

Nk

NnkFN

knknf

NkN

knnfkkF

N

k

N

n

Matriz da Transformada

)3(

)2(

)1(

)0(

)8/21cos()8/15cos()8/9cos()8/3cos(

)8/14cos()8/10cos()8/6cos()8/2cos(

)8/7cos()8/5cos()8/3cos()8/cos(

2/12/12/12/1

2

1

)3(

)2(

)1(

)0(

u

u

u

u

v

v

v

v

DCT 4 pontos

Matriz da Transformada Inversa

)3(

)2(

)1(

)0(

)8/21cos()8/14cos()8/7cos(2/1

)8/15cos()8/10cos()8/5cos(2/1

)8/9cos()8/6cos()8/3cos(2/1

)8/3cos()8/2cos()8/cos(2/1

2

1

)3(

)2(

)1(

)0(

v

v

v

v

u

u

u

u

V.B.: Vectores de Base

V.B.-1 V.B.-2 V.B.-3V.B.-0

Exemplo 5.3

Considere uma sequência de 4 pontos f={2,5,7,6}. Calcule os correspondentes coeficientes DCT. Reconstrua a sequência de entrada a partir dos coeficientes DCT.

Exemplo 5.3

Fig 5.3,pag. 92

Propriedades do DCTEnergia da CompactaçãoA DCT tem um excelente desempenho de compatação de energia. Isto é demonstrado com um exemplo.

Exemplo 5.4Considere a linha de varrimento da imagem do Exemplo 5.2. Calcule o DCT e a energia total nos primeiros 20 coeficientes de Fourier. Compare-a com a Energia total do sinal. Compare o desempenho de compactação da energia da DCT e DFT.

Compactação da Energia com a DCT

A DCT tem um excelente desempenho na compactação da energia

512 pixels: energia total = 5103.11

Primeiros 20 coeficientes DFT capturam 76% daa energiaPrimeiros 20 coficientes DCT capturam s 83% da energia

Relações com a DFT Embora as funções de base da DCT sejam funções discretas de coseno a DCT não é a parte real da DFT.Contudo está relacionada com a DFT. A DCT da sequência Nx1

está relacionada com a seguinte sequência DFT

Existe uma transformada DCT rápida com uma complexidade computacional de ordem

Segundo, devido à simetria par da sequência equivalente DFT, o sinal recosntruído dos coeficientes DCT quantificados terão uma melhor representação das variações bruscas.

)}1(),.....1(),0({ Nfff

)}1(),.....0(),0(),1(),....2(),1({ NffffNfNf

)log( 2 NNO

Filtragem Digital e Análise de sub-banda As transformadas unitárias

São muitos úteis para análise do contéudo de frequência dum sinal

Métodos alternativos para análise de frequência de sinais multimédia Filtragem Digital Análise de sub-banda

Filtragem Digital

Filtro Um filtro é um componente que atenua

ou amplifica frequências particulares Fácil de visualizar no domínio da

frequência, onde a filtragem é uma multiplicação:

Onde F é o espectro da função, G é o espectro do filtro e H é a função filtrada. A multiplicação é ponto a ponto.

)()()( GFH

Parâmetros de Filtros

Banda de passagem

Banda de paragem

Banda de transição

Ondulação

(Ripple)

Frequência

Atenuação na stopband

Parâmetros do Filtro

Banda de Passagem: Os componentes da banda de frequência aos quais é permitido a passagem.

Banda de Paragem: Os componentes da banda de frequência que são suprimidos.

Banda de Transição: a banda de frequência entre a banda passagem e a de paragem onde o sinal varia de alto para baixo ou vice-versa

Ondulação: a máxima variação do ganho nominal permitida na banda de passagem ou de paragem.

Atenuação da Banda de Paragem: atenuação mínima dos componentes na banda de paragem.

Tipos de Filtros

cccc

2c1c 2c1c2c 1c1c2c

Lowpass(Passa-Baixo)

Highpass(Passa-Alto)

Bandpass(Passa-Banda)

Bandstop(Para-Banda)

Filtros ideais: 4 tipos básicos

Tipo de Filtros

Função: F Filtro: G

=

=

=

Resultado: H

Passa-Baixo

Passa-Alto

Passa-Banda

Tipos de Filtros

Filt

er G

ain

Frequency

Bandpass Filter

Frequency

Bandstop Filter

Filt

er G

ain

Frequency

Highpass Filter

Filt

er G

ain

Frequency

Transition Band

Passband

Stopband

Filt

er G

ain

Lowpass Filter

Filt

er G

ain

Frequency

Bandpass Filter

Filt

er G

ain

Frequency

Bandpass Filter

Frequency

Bandstop Filter

Filt

er G

ain

Frequency

Bandstop Filter

Filt

er G

ain

Frequency

Highpass Filter

Filt

er G

ain

Frequency

Highpass Filter

Filt

er G

ain

Frequency

Transition Band

Passband

Stopband

Filt

er G

ain

Lowpass Filter

Frequency

Transition Band

Passband

Stopband

Filt

er G

ain

Lowpass Filter

Tipos de Filtros Digitais

Nou 0a(k):k Response) Impulse teIIR(Infini

N ek 0,a(k) Response) Impulse FIR(Finitefiltros de categorias

prévias saídas M as com actual amostra da

saída da adependênci a expressam que escoeficient)(

prévias entradas N as com actual amostra da

saída da adependênci a expressam que escoeficient-)(

)()()()()(

digital filtro dum saída e entrada ),( )(

00

ka

kb

knykaknfkbny

nyenfM

k

N

k


Filtros FIR (Finite Impulse Response)

Filtros IIR(Infinite Impulse response)

Os filtros FIR são constituídos por funções de resposta com número finito de pulsos que são fáceis de concretizar devido ao seu comprimento finito.

Os filtros IIR requerem uma resposta com um número infinito de pulsos que tornam a forma em convulsão difícil. Contudo, estes filtros são realizáveis.

Filtros FIR e IIR

Filtros Finite Impulse Response (FIR) Filters um númro finito de impulsos na sua resposta de impulso. Relação típica entre entrada e saída:

Os filtros Infinite Impulse Response (IIR) têm um número infinito de impulsos na sua resposta de impulso. Relação pica entre entrada e saída:

M

k

N

k

knykaknfkbny10

)()()()()(

N

k

)kn(f)k(b)n(y0

Os filtros IIR têm geralmente um elemento de feedback

outputinput


Frequência: pulso Tempo: sinc


Fig. 5.6, pag. 95

Resposta de Impulso do Filtro Passa baixo

Truncagem

A resposta de impulso do FPB ideal tem um número infinito de impulsos

Janelas Rectangular & Hamming

0 50 100 150 200 2500

0.2

0.4

0.6

0.8

1

1.2

Janela Rectangular M=35

1,...,1,0 Mn

10 Mn

Para outros valores de n

,0

,1nw

• Janela Rectangular • Janela Hamming

Nnnw 2cos46.054.0

0 5 10 15 20 25 30 350

0.5

1

1.5Janela "Hamming" M=35

Ganho de Resposta dos filtros P.B.

Ganho da resposta em dB

Concretização de Filtros com o MatLabPassa Alto e Passa Baixo

Concretize um filtro P.F e P.A. com uma frequência de cortye de 3200 Hz para um sinal de áudio amostrado ao ritmo de 8000 amostras/seg.

Frequência de corte = 3200/8000 or 0.4.

filter_lowpass = fir1(8,0.4) ; % 8ª ordem, i.e. 9 implusos

filter_highpass = fir1(8,0.4,’high’) ;

Concretização de Filtros com o MATLABPassa Banda e Pára Banda

Concretize um filtro passa banda e outro para banda com frequências de corte normalizadas de 0.4 e 0.8.

filter_bandpass = fir1(8,[0.4 0.8])

filter_bandstop = fir1(8,[0.4 0.8],’stop’)

Exemplo de Filtros

Exemplos de filtros digitais FIR com 9 impulsos A frequência de corte dos filtros passa alto e baixo é 0.4 As frequências de corte dos filtros para e passa banda são [0.4,0.8]

Filtro Coeficientes

Passa-baixo

[-0.0061 –0.0136 0.0512 0.2657 0.4057 0.2657 0.0512 –0.0136 –0.0061]

Passa-alto [-0.0060 0.0133 -0.0501 -0.2598 0.5951 -0.2598 0.0501 0.0133 0.0060]

Passa-banda

[0.0032 0.0478 -0.1802 -0.1363 0.5450 - 0.1363 0.1802 0.0478 0.0032]

Para-banda [-0.0023 -0.0354 0.1336 0.1011 0.6061 0.1011 0.1336 -0.0354 -0.0023]

Características de Ganho na Frequência

Fitros de 9 Impulsos

Os filtros não têm ganhos com características escarpadas

Características de Ganho na Frequência

Filtros de 101-impulsos

Os filtros têm características de ganho escarpadas

Análise de sub-banda

Análise e síntese de sub-banda

Banco de

Filtros de

Análise

Banco de

Filtros de

Síntese

Processamento/Codificação/ Extracção de características

Sinal deEntrada

Sinal deSaída

Sub-bandas Sub-bandas1 1

2 2

N N

Banco de Filtros de 2 bandas

+

Processamento

)(nX )(^

nX

)(0 nx

)(1 nx

)(^

0 nX

)(^

1 nX

)(^

0 nx

)(^

1 nx

FPB

FPA

FPB

FPA

)(0 nv

)(1 nv

2

2

2

2

2

)(~

nh

)(~

ng

)(nh

)(ng

QMF: Quadrature Mirror Filter

0

Lowpass band Highpass band

4/SF 2/SF

Filte

r ga

in

0

Lowpass band Highpass band

4/SF 2/SF

Filte

r ga

in

Características do Ganho de Frequência do QMF

Categorias de Bancos de Filtros Reconstrução do Sinal

Reversível (Irreversíveis) a sequência de entrada (não)pode ser

perfeitamente reconstruída com os coeficientes não quantificados e o banco de filtros de síntese

Para-unitários A matriz de transformação num sentido é a

inversa da matriz de transformação no sentido contrário

Similar a uma transformada ortonormal

Condições de Para-Unitários

)()2()(1

0

kknhnhN

n

)(~)1()( 1 ngnh n

)1(~

)1()(~ 1 nNhng n

)(~

)1()( nhng n

Um banco de filtros de 2 bandas é chamado para-unitário se forem satisfeitas as 4 condições seguintes:

Se se encontrar que satisfaça Eq. (5.24), , , podem ser calculadas com as equações seguintes.

)(nh )(~

nh)(~ ng)(ng

……..(5.24)

……..(5.25)

……..(5.26)

……..(5.27)

Bancos de FiltrosCondições para para-unitários

)()1()(

)1()1()(

)()1()(

)()2()(

~

~1

~

~1

1

0

nhng

nNhng

ngnh

Kknhnh

n

n

n

N

n

Exemplo 5.5

Considere o filtro passa-baixo :

Os outros filtros obtêm-se da forma seguinte:

]1294.0 ,2241.0 ,8365.0 ,4830.0[)( nh

]1294.0 ,2241.0- ,8365.0 ,4830.0[)(~ ng

)0(~)0( gh )1(~)1( gh )2(~)2( gh )3(~)3( gh

Filtro passa-alto de análise

Exemplo 5.5 (..cont.)

]1294.0 ,2241.0- ,8365.0 ,4830.0[)(~ ng

)3(~

)1(~

)0(~ hNhg )2(~

)1(~ hg

)1(~

)2(~ hg )0(~

)3(~ hg

] 0.4830 ,8365.0 ,2241.0 ,1294.0[)(~

nhEntão

] 0.4830- ,8365.0 ,2241.0 ,1294.0[)( ng

)0(~

)0( hg )1(~

)1( hg )2(~

)2( hg )3(~

)3( hg

Então

Filtro passa alto de síntese

Filtro passa baixo de análise

Exemplo 5.6

Considere o filtro passa baixo:

Os outros filtros podem ser obtidos da seguinte forma:

]7071.0 ,7071.0[2/1 2/1)( nh

]7071.0- ,7071.0[)(~ ng

]7071.0 ,7071.0[)(~

nh

]7071.0 ,7071.0[)( ng

Filtro Passa alto de análise :

Filtro Passa baixo de análise

Filtro passa alto de síntese

Cálculo da saída de banco de filtrosExemplo 5.7

Considere o banco de filtros do Exemplo 5.6. Calcule a saída dos vários estágios do banco de filtros para a entrada:

]5 ,4 ,1 ,8 ,7 ,5 ,2 ,1[)( nx

Após o primeiro nível de filtros :

4.2426] 6.3640 3.5355 6.3640 10.6066 8.4853 4.9497 2.1213[

)(~

)()(0 nhnxnx

)(~)()(1 ngnxnx

2.8284] 0.7071- 2.1213- 4.9497 0.7071- 1.4142- 2.1213- -0.7071[

1213.27071.027071.01)0(0 x2426.47071.017071.05)7(0 x

Exemplo 5.7 (..cont)

Depois da dizimação:

6.3640] 6.3640 8.4853 2.1213[2)()( 00 nxnv

0.7071]- 4.9497 1.4142- -0.7071[2)()( 11 nxnv

Depois da sobre-amostragem

0.0] 6.3640 0.0 6.3640 0.0 8.4853 0.0 2.1213[)(ˆ0 nx

0.0] 0.7071- 0.0 4.9497 0.0 1.4142- 0.0 -0.7071[)(ˆ1 nx

Exemplo 5.7 (..cont)

Após filtro de síntese

4.500] 4.500 4.500 4.500 6.000 6.000 1.500 1.500[

0.500] 0.500- 3.500- 3.500 1.00 1.00- 0.50 -0.50[

)()(ˆ)( 00 nhnxnx

)()(ˆ)( 11 ngnxnx

Saída reconstruída

]5 ,4 ,1 ,8 ,7 ,5 ,2 ,1[)()()(ˆ 10 nxnxnx

Transformadas e Filtragem Digital As transformadas unitárias fornecem

coeficientes para diferentes frequências Os coeficientes de sub-banda também

disponibilizam coeficientes para as diferentes bandas idealmente não sobrepostas no domínio da frequência

Pode ser mostrado que as transformadas de bloco são um caso especial de banco de filtros

Transformadas e Filtragem Digital

Uma transformada de N-pontos pode ser calculada usando um banco de filtros de N bandas Cada filtro corresponde ao conjugado

complexo de uma função de base A saída de cada filtro é dizimada por N

Por cada conjunto de N amostras de entrada há uma saída para cada um dos N filtros

Essas saídas são basicamente os coeficientes da transformada.

Exemplo 5.8Relação entre transformada e filtragem

digital Considere a sequência de 12

pontos [{2,5,7,6},{1,3,9,4},{6,8,5,7}] Calcule os coeficientes DCT de

segunda ordem para cada bloco de 4 coeficientes

Pode-se concretizar o DCT como banco de filtros?

Exemplo 5.8 (cont.)

Usando Eq. (5.18), os coeficientes de 2da ordem de cada bloco podem

ser calculados como de cada bloco podem ser calculados como

{-3.1543, -3.5834, -0.6069, 0.1585}. Sim, os coeficientes DCT podem também ser concretizados usando um

banco de filtrosOs coeficientes de segunda ordem podem ser calculados passando a

sequência de entrada através dum filtros digital com a resposta de

impulso h = [cos(pi/8), cos(3*pi/8), cos(5*pi/8), cos(7*pi/8)] que é a

função de base de segunda ordem Observe que quando o filtro digital está em operação cada bloco de 4

amostras de entrada produzirá uma amostra à saída do filtros de

segunda ordem.

Transformadas wavelet

Limitações da Transformada de Fourier e derivadas

Têm funções de base com muitos impulsos É ineficiente para muitas aplicações

Fraco desempenho para análise de sinais não estacionários

Dificuldade de estimação das caraterísticas no tempo ou do espaço a partir da amplitude do espectro

Más características de flltragem Boa decomposição de sub-banda

Só para dados discretos Características unitárias não disponíveis à

partida

Porquê que funções de base longas podem ser indesejáveis?

As funções de base para FT contínuas são infinitamente longas.

As funções de base para a transformada discreta de Fourier não são infinitas mas são longas. -- Por exemplo, para a DFT de 256 pontos há 256 funções de base cada uma como 256 impulsos.

Em muitas aplicações tal como compressão do sinal, essas funções base longas não são desejáveis. -- Para representar um pequeno pulso rectangular são necessários uma série de componentes na frequência, o que pode degradar a taxa de compressão

FT longas e curtasFunções de base de Fourier (suporte infinito)

Funções de base de Fourier de tempo curto (suporte finito)

Resolução Tempo-Frequência

time time

frequência frequência

(a) (b)

STFT Wavelets

Funções de base de STFT e Wavelets

Transformada Discreta Wavelet 1-D

Transformada Wavelet Ferramenta potente e recente

Diversas aplicações em ciências e engenharia Melhores técnicas de transformada e

decomposição em sub-banda Pode ser considerada uma transformada ou

técnica de decomposição em sub-banda Não tem conjunto único de funções de base

Funções de base concebidas de acordo com a aplicação

Transformada Discreta Wavelet Directa

Uma dada transformada wavelet dyadic é definida de forma única por um filtro FIR passa-baixo e um FIR passa-alto .

Considere uma sequência discreta de N pontos

Os coeficientes DWT são calculados recursivamente usando as equações seguintes

[.]h [.]g

kc ,0 10 Nk

]2[,,1 kmhccm

mjkj

]2[,,1 kmgcdm

mjkj

12/0 1 jNk

Escala Localização

Passa-baixo

Passa-Alto

Decomposição Wavelet

Há uma série de observações a fazer:

A sequência de entrada pode ser considerada como os coeficientes DWT de escala 0 pode ser obtido pela convulsão de com e dizimando a saída da convulsão por 2 (devido ao factor 2k) pode ser obtido pela convulsão de com e dizimando a saída da convulsão por 2 A decomposição continua recursivamente. Apenas os coeficientes passa baixo são decompostos.

kc ,1 mc ,0 ][ nh

k,d1 mc ,0 ][ ng

Algoritmo em árvoreCálculo dos coeficientes da DWT

][ nh

][ nh

][ ng

][ ng

2

2

2

2jc

1jc

2jc

1jd

2jd

Decomposição de sinal com filtros de análise

Decomposição DWT usando matriz

j,7

j,6

j,5

j,4

j,3

j,2

j,1

j,0

1,3j

1,3j

1,2j

1,2j

1,1j

1,1j

1,0j

1,0j

c

c

c

c

c

c

c

c

h[2]-h[3]

h[1]h[0]

h[0]-h[1]h[2]-h[3]

h[3]h[2]h[1]h[0]

h[0]-h[1]

h[3]h[2]

h[0]-h[1]

h[3]h[2]

h[0]-h[3]

h[1]h[0]

h[0]-h[1]h[2]-h[3]

h[3]h[2]h[1]h[0]

d

c

d

c

d

c

d

c

A decomposição pode ser feita através duma multiplicação de matrizes A DWT duma sequência de 8 pontos pode ser calculada com filtros

passa-baixo e passa-alto de 4 implusos com a seguinte multiplicação de

matrizes :

Transformada Inversa DWTSíntese

Utilizando uma abordagem similar à decomposição em wavelet Os coeficientes duma dada escala

podem ser reconstruídos com coeficientes de escala superior

]2[]2[ ,1,1, l

ljk

kjmj lmgdkmhcc

Transformada Wavelet Inversa

Os coeficientes wavelet duma duma escala podem ser reconstruídos usando os coeficientes de escalas mais altas.

Os coeficientes reconstruídos podem ser expressos como se segue:

Os coeficientes wavelet duma da escala são sobreamostrados de 2 (i.e inserir um zero entre coeficientes consecutivos) Os coeficientes sobreamostrados são passados por um conjunto de filtros passa-baixo e passa-alto e a seguir adicionados para obter os coeficientes wavelet da escala de resolução superior seguinte.

]2[]2[ ,1,1, lmgdkmhccl

ljk

kjmj

Algoritmo em árvoreCálculo dos coeficientes da DWT

][nh

][ng

2

jc

1jc

1jc1jd

jd

Reconstrução de sinal com filtros de síntese

][nh

][ng

2

2

2

Matriz de Transformada Inversa

3,1

3,1

2,1

2,1

1,1

1,1

0,1

0,1

7,

6,

5,

4,

3,

2,

1,

0,

]2[]1[

]3[]0[

]0[]3[

]1[]2[]2[]1[

]3[]0[

]0[]3[

]1[]2[]2[]1[

]3[]0[

]0[]3[

]1[]2[]0[]3[

]1[]2[

]2[]1[

]3[]0[

j

j

j

j

j

j

j

j

j

j

j

j

j

j

j

j

d

cd

cdc

d

c

hh

hh

hh

hhhh

hh

hh

hhhh

hh

hh

hhhh

hh

hh

hh

c

cc

ccc

c

c

A DWT inversa de uma sequência de 8 pontos pode ser calculada com

filtros passa-baixo e passa-alto de 4 impulsos usando a seguinte

multiplicação de matrizes:

Wavelet 1-D: Decomposição e Síntese

)(~ ng

)(~

nh

)(0 nx

)(1 nx

)(0 nv

)(0̂ nx

2

2 2

2 )(nh

)(ng

)(1̂ nx)(1 nv

LPF LPF

)(ˆ nx)(nx

)(1 nx

)(0 nx

)(~ ng

)(~

nh

)(0 nx

)(1 nx

)(0 nv

)(0̂ nx

2

22 2

2 )(nh

)(ng

)(1̂ nx)(1 nv

FPB

FPA

FPB

FPA

Processamento

)(ˆ nx)(nx

)(1 nx

)(0 nx

Wavelets Daubechies de fase mínima

# Imps

n h[n]

N=2L=1

01

0.707106780.70710678

N=4L=2

0123

0.4829629131440.8365163037370.224143868042-0.129409522551

N=8L=4

01234567

0.2303778133080.7148465705520.630880767939-0.027983769416-0.187034811710.0308413818350.032883011666-0.010597401785

# Imps

n h[n]

N=12L=6

01234567891011

0.1115407433500000.4946238903980000.7511339080210000.315250351709000-0.226264693965000-0.1297668675670000.0975016055870000.027522865530000-0.0315820393180000.0005538422010000.004777257511000-0.001077301085000

DWT: Exemplo 5.9

Considere uma sequência de 4 pontos f=[2,5,7,6]. Decomponha a sequência com auxílio da wavelet de dois impulsos dada na tabela 5.3 (Wavelet Haar). Reconstrua a sequência de entrada a partir dos coeficientes de Haar.

Exemplo 5.9 (cont.)

O coeficientes de Haar do 1º estágio (i.e., escala 1) podem ser calculdoscom:

71.0

19.9

12.2

95.4

6

7

5

2

707.0707.000

707.0707.000

00707.0707.0

00707.0707.0

]0[]1[00

]1[]0[00

00]0[]1[

00]1[]0[

3,0

2,0

1,0

0,0

1,1

1,1

0,1

0,1

c

c

c

c

hh

hh

hh

hh

d

c

d

c

Na segunda iteração da recursividade são usados apenas os coeficientes passa baixo

3

10

19.9

95.4

707.0707.0

707.0707.0

]0[]1[

]1[]0[

1,1

0,1

0,2

0,2

c

c

hh

hh

d

c

Exemplo (..cont)

Após rearranjos os coeficientes de Haar ficam

,,,[ 0,10,20,2 ddc ]1,1d = [10 -3 -2.12 0.71]

Reconstrução do sinal

19.9

95.4

3

10

707.0707.0

707.0707.0

]0[]1[

]1[]0[

0,2

0,2

1,1

0,1

d

c

hh

hh

c

c

6

7

5

2

71.0

19.9

12.2

95.4

707.0707.000

707.0707.000

00707.0707.0

00707.0707.0

]0[]1[00

]1[]0[00

00]0[]1[

00]1[]0[

1,1

1,1

0,1

0,1

3,0

2,0

1,0

0,0

d

c

d

c

hh

hh

hh

hh

c

c

c

c

Funções de base para a Wavelet Haar

Fig. 5.13, pag 108

Transformadas 2D

Transformada Unitária 2-D Transformada 1-D

Útil para análise de sinal 1-D Transformada 2-D

Necessária para análise de sinais 2-D Exemplo: imagens Baseada na extensão dos conceitos 1-D


1

0

1

0

),(),;,(),(N

m

N

n

nminmlklk

1

0

1

0

),(),;,(),(N

k

N

l

lklknmnmi

A transformada directa e inversa 2-D são definida com

),( nmiI onde

(.)(.)

= Imagem NxN

= Núcleo da t.directa

= Núcleo da t.inversa

Exemplo: Fourier Cosine Wavelet Hadamard Haar

Transformada Unitária 2-DPropriedades Conservação da Energia

Soma dos erros quadráticos

Imagens de Base separáveis

221

0

1

0

21

0

1

0

2),(),(

IlknmiN

m

N

n

N

m

N

n

1

0

1

0

2^1

0

1

0

2^

),(),(),(),(N

m

N

n

N

m

N

n

lklknminmi

T

T

I

I

*

*

Propriedades da Transforma 2-DConservação da energia

Pode ser mostrado que os coeficientes da transformada 2D unitária satisfazem a relação de Parseval’s, i.e. A energia total no domínio da frequência é igual à energia total no domínio do tempo

1

0

1

0

21

0

1

0

2),(),(

N

k

N

l

N

m

N

n

lknmi

A transformada unitária preserva a energia do sinal ou de forma equivalente o comprimento no espaço vectorial N-dimensional.

Pode ser considerada simplesmente como uma rotação do vector no espaço vectorial N-dimensional. Por outras palavras, a transformada unitária roda as coordenadas de base e os componentes (coeficientes da transformada) são as projeções no novo sistemas de coordenadas.

Soma dos quadrados de erros

Assuma que valor de algun(s) dos coeficientes da tarsnformada

muda durante o processamento. Esta mudança pode ocorrer na

transmissão ou compressão de dados.Se recosntruímos a imagem claculando a transformada inversa

usando os coeficientes mudados, a imagem reconstruída é

diferente da original. Pode-se mostrar a seguinte igualdade é sempre verdadeira para

transformadas unitárias

1

0

1

0

21

0

1

0

2),(ˆ),(),(ˆ),(

N

k

N

l

N

m

N

n

lklknminmi

Pixéis Píxeis Coeficientes Coeficientes originais Reconstruídoss originais mudados

Imagens de base separáveis

Alguns núcleos 2-D podem ser expressos como o produto de 2

funções ortogonais de base 1-D.

Se o operador de transformada 1-D for designado por as

transformadas directas e inversas podem ser expressas como

TI *

* TIUma transformada separável pode ser concretizada em 2 passos: -- Calcular a transformada unitária de cada fila da matriz da imagem .-- Calcular a transformada unitária de cada coluna dos coeficientes transformados intermédios .

Definição da DFT 2D

1,m0 W W),(1

),(

1lk,0 W W),(1

),(

por definido é 2D unitário DFTpar O

1

0

1

0

ln-N

km-N

1

0

1

0

lnN

kmN

NnlkN

nmi

NnmiN

lk

N

k

N

k

N

m

N

n

N

jWN

2exp

onde

Exemplo DFT 2D

Calcular a DFT e desenhar o espectro de amplitude da seguinte image 32x32.

otherwise 0

248&171615 1),(

nnmi

Observe que a imagem é basicamente um paralelepípedo rectangular. A transformada de Fourier duma função rectangular 1-D é a função sinc. Portanto, a transformada de Fourier duma função rectangular 2-D é a função sinc 2-D.

Exemplo DFT 2D (cont.)

Por clareza, o espectro (sinc 2D) foi centralizado (a frequência DC no meio). Observe que o rectângulo tem uma largura maior na horizontal quena vertical. Isto reflecte-se no espectro. O espectro tem melhor resolução de frequência na horizontal..

Propriedades da DFT 2D A maior parte das propriedades da

DFT 1D podem ser extendidas para a DFT 2D Convolução Correlação Conservação da Energia Soma mínima do erro quadrático

Propriedades da DFT 2DSeparabilidade

Pode ser mostrado que a DFT 2D é separável O cálculo da DFT para uma imagem pode

ser feito em dois passos simples Calcular a DFT 1D de cada fila da imagem

A fila é substituída pelos respectivos coeficientes DFT

Calcular a DFT 1D de cada coluna da imagem A coluna é substituída pelos respectivos

coeficientes DFT

Propriedades da DFT 2DSeparabilidade

m

n(0,0)

u(m,n)

N-1

N-1

m

l(0,0)

v´(m,l)

N-1

N-1

k

l(0,0)

v(k,l)

N-1

N-1

Transformada das filas

Transformada das colunas

Exemplo

Usando a abordagem de separação, calcular a DFT 2D para a imagem seguinte:

4172

3942

8251

7432

3183114

74718

31103116

4612468

2

1

jj

jj

jj

jj

Transformada da Fila

Transformada de fila dosCoeficientes

Imagem original

Transformada de coluna

3183114

74718

31103116

4612468

2

1

jj

jj

jj

jj

jjjj

jj

jjjj

jj

lkF

71921637210

3110314

37216719210

31263156

4

1),(

Transformada deFila dos coeficientes

Coeficientes DFT 2D depois da transformadade coluna

Conjugado simétrico dos dados Reais

Se a imagem é real, os coeficientes DFT satisfazem as propriedades desimetria seguintes

),(),( * lNkNlk

jjjj

jj

jjjj

jj

71921637210

3110314

37216719210

31263156

4172

3942

8251

7432

Compactação da Energia

A DFT disponibiliza uma compactação de energia significativa para a maioria das imagens.

Observa-se que a maior parte da energia está concentrada nos quatro cantos da imagem que representam as baixas frequências.

Coeficientes deBaixa Frequência

Espectro DFT

Definição da DCT 2D

1

1

0

1

0,m0 ),(

2

1)l(2ncos

2

1)k(2mcos )()(),(

11

0

1

0lk,0

2

1)l(2ncos

2

1)k(2mcos ),()()(),(

por definido é 2D NxN DCTpar O

NN

k

N

lnlk

NNlknmi

NN

m

N

n NNnmilklk

Imagens de base para DCT 2D

Figura 5.17, pag. 116

Propriedades da DCT 2D As propriedades da DCT 1D podem

ser prontamente expandidas para a 2D Compactação da energia na região de

baixas frequências A DCT 2D é separável

Os coeficientes podem ser calculados usando as transformadas de fila e de coluna

DCT 2D: Exemplo 5.12 Usando a abordagem da

separabilidade calcular a DCT 2D da imagem

4172

3942

8251

7432

Separabilidade

4172

3942

8251

7432

4.4132.07

99.2429

85.3176.38

92.5537.14Row Transform

08.464.169.016.0

76.45.335.23

81.227.558.123.2

62.55.041.314

Column Transform

2-D DCTCoefficients

Energy Compaction

As in the 1-D case, the 2-D DCT can compact energy of typical images very efficiently.

DCT Coeff. of Lena image

Most of the energy is concentrated in the low frequency region (upper left corner). It has been shown that DCT provides near optimal energy compaction performance for most natural images. As a result, it has been accepted as the transform kernel for most existing image and video coding standard.

Propriedades da DCT 2DCompactação da energia

Figura 5.18

DCT e DFT duma Imagem

DFT

DCT

Definição da DWT 2D Tal como na 1D não há um único núcleo de

transformação Há DWT 2D unitárias e outras que não

Wavelets bi-ortogonais (não unitárias) populares na compressão de imagens

Há DWT 2D separáveis e outras que não A maioria das DWT 2D são dyadic e separáveis

Na DWT 1D, cada nível de decomposição corresponde a 2 bandas de dados(alta e baixa resolução)

Na DWT 2D cada nível produz 4 bandas Baixa, bandas altas verticais, horizontais e diagonais

Wavelets 2D Separáveis

(1,1) b

a

f(x,y)

(1,1) b

a

(1,1) b

aF(x,v)

L H

LH

LL HL

HHF(u,v)

Row

Transform

Column

Transform

2-D

Image

HH

HL

LH

LL

2-D DWT(1 Stage)

HorizontalEdges

VerticalEdges

DiagonalEdges

(1,1) b

a

f(x,y)

(1,1) b

a

(1,1) b

aF(x,v)

L H

LH

LL HL

HHF(u,v)

Row

Transform

Column

Transform

2-D

Image

HH

HL

LH

LL

2-D DWT(1 Stage)

HorizontalEdges

VerticalEdges

DiagonalEdges

Wavelets 2-D

2-D

Image

HH

HL

LH

LL

2-D DWT(1 Stage)

Row

Transform

Column

Transform

HL LL HL

LH HH

2-D

Image

HH

HL

LH

LL

2-D DWT(1 Stage)

2-D

Image

HH

HL

LH

LL

2-D DWT(1 Stage)

Row

Transform

Column

Transform

HL LL HL

LH HH

Row

Transform

Column

Transform

HL LL HL

LH HH

Decomposição Wavelet da Imagem da Lena

Informacão Espacial e de Frequência

Todas as sub-bandas disponibilizam informação espacial e de

frequência

A estrutura espacial da imagem é visível em todas as sub-bandas.

Pode ser observada uma imagem na banda de mais baixa resolução.

As bandas de alta frequência disponibilizam as informação detalhada

(arestas) nas várias escalas.

Representação Multi-Resolução

A decomposição wavelet disponibiliza uma representação multi-

resolução da imagem.

Uma imagem grosseira é disponibilizada na banda de baixa

frequência.

Pode-se obter uma imagem de resolução mais alta calculando a

tarnsformada inversa das 4 sub-bandas de menor resolução.

A imagem com resolução total obtém-se calculando a transformada

inversa das 7 sub-bandas

Compactação de energia

As Wavelets têm um excelente desempenho na compactação da

energia. Os coeficientes de sub-bandas altas têm pequena magnitude.Assim pode ser conseguida uma maior compactação das imagens

quantificando os coeficientes wavelet.

530.4

3.45.4

8.4

11.315.7

26.4530.4

3.45.4

8.4

11.315.7

26.4

DWT 2D: Exemplo 5.13 Considere a imagem da Lena do Ex. 5.2.

Calcule A transformada wavelet de dois estágios

usando a wavelet de Daub com 4 impulsos Coeficientes da transformada Para os pixels das diferentes bandas calcule a

raiz da energia quadrática média

Documents

Transformadas e Decomposição de Sub-banda