Nov 98 I.T., Aveiro 1 Maria Joana Soares Departamento de Matemática Universidade do Minho Instituto...

1I.T., AveiroNov 98

Maria Joana Soares

Departamento de Matemática

Universidade do Minho

Instituto de Telecomunicações

Aveiro, Novembro 98

Nov 98 I.T., Aveiro 2

Notações

• Transformada de Fourier

)()( 2 RLtf dttgtfgf

)()(,

ti

ti

ef

dtetffFf

,

)()(ˆ)}({

Nov 98 I.T., Aveiro 3

Localização tempo-frequência

• Transformada de Fourier com janela g

dtetgtffF tig

)()(:),}({

,,),}({ gffFg

tietggg )(:,

Nov 98 I.T., Aveiro 4

Transformada de Fourier com janela

Janela

-2 -1 1 2

0.2

0.4

0.6

0.8

1

Janela ondas Transladada

-2 -1 1 2

-0.5

0.5

1

-2 -1 1 2

-1

-0.5

0.5

1

2 3 4 5

-1

-0.5

0.5

1

Nov 98 I.T., Aveiro 5

Transformada contínua com ôndula

•A janela já oscila (onda)

Nov 98 I.T., Aveiro 6

Transformada contínua com ôndula

A onda é expandida ou contraída e transladada

Nov 98 I.T., Aveiro 7

Transformada contínua com ôndula

a

t

aa

1

:,

,,),}({ afafW

dta

ttf

aafW

)(

1:),}({

Nov 98 I.T., Aveiro 8

Transformada contínua com ôndula

• Quando a aumenta, a função alarga

-10 -5 5 10

-1

-0.5

0.5

1

-10 -5 5 10

-0.4

-0.2

0.2

0.4

)(t

)2(t

-10 -5 5 10

-2

-1

1

2

• Quando a diminui, a função estreita

)2( t

Nov 98 I.T., Aveiro 9

Plano tempo-frequência

Transformada de Fourier com janela

Transformada contínua com ôndula

Nov 98 I.T., Aveiro 10

Transformada contínua com ôndula

dC0

2|)(ˆ|

•Ser bem localizada (pequena)•Satisfazer condição de admissibilidade

A função deve :

0)(0)0(ˆ dtt (onda)

Nov 98 I.T., Aveiro 11

Transformada contínua com ôndula

da

daafW

Ctf a 2,

0

),}({1

)(

Fórmula de inversão

Reconstrução

da

daf

Ctf aa 2,

0

,,1

)(

Decomposição

Nov 98 I.T., Aveiro 12

Transformada discreta. Ôndulas ortogonais

• Transformada contínua é altamente redundante.

• Restringir valores dos parâmetros:ja 2 Zkjkj ,;2

Zkjktjjkj ,;22: 2/

,

)( de o.n. base}{ortogonal ôndula 2, RLkj

jkkj

jkff ,

,

Nov 98 I.T., Aveiro 13

Transformada discreta. Ôndulas ortogonais

• Existem tais bases?– Base de Haar (Base de Haar (19101910))

– StrömbergStrömberg– MeyerMeyer– Battle; LemariéBattle; Lemarié

)1,2/1[)2/1,0[)( tH

Nov 98 I.T., Aveiro 14

Análise de Resolução Múltipla (ARM)

0

1

2

2101

de o.n. base}:)({5.

)2()(4.

}0{.3

)(2.

.1

VZkkt

VtvVtv

V

RLV

VVVV

jj

j

j

Nov 98 I.T., Aveiro 15

Análise de Resolução Múltipla (ARM)

Exemplo: (ARM de Haar)Exemplo: (ARM de Haar)

)1,[ intervalo cada em constantes funções0 kkV

))1(2,2[ intervalo cada em constantes funções kkV jjj

)1,0[

Nov 98 I.T., Aveiro 16

Análise de Resolução Múltipla (ARM)

jjj

jk Vkt de base22 2/

10 VV 0V

)2(2)( kthtk

k Equação de dilataçãoou

de dupla escala

Filtro}{ kh

Nov 98 I.T., Aveiro 17

Análise de Resolução Múltipla (ARM)

• Dada como surge a base o. n. de ôndulas?} ), {( j V

jjjjj VWWVV ,1

Espaços de detalhe jW

jjjjjj WWVWVV 111

jZjWRL

)(2

Nov 98 I.T., Aveiro 18

Análise de Resolução Múltipla (ARM)

0 de n. o. base)(: Wkt

jjk WZk de base }:{

)( de base },:{ 2 RLZkjjk

ôndula ortogonal

Nov 98 I.T., Aveiro 19

Análise de Resolução Múltipla (ARM)

ARM }),{( jV existe!

)2(2)( ktgtk

k

)2(2)( kthtk

k

kk

k hg 1)1(

Equação de ôndula

Nov 98 I.T., Aveiro 20

Análise de Resolução Múltipla (ARM)

)2(2)( ktgt k )2(2)( kthtk

k

kk

k hg 1)1(ARM de HaarARM de Haar

2

210 hh

2

2,

2

210 gg

Nov 98 I.T., Aveiro 21

Transformadas Rápidas com Ôndulas

kkc }{ 0 00 )()( Vktctf

kk

1110 WWVWVV JJ

jjk V de base jjk W de base

jk

J

j k

jkJk

k

Jk dcf

1

Nov 98 I.T., Aveiro 22

Transformadas Rápidas com Ôndulas

• Da equação de dilatação obtém-se facilmente

jn

nkn

jk chc 21

jn

nkn

jk cgd 21

• Da equação de ôndula vem

Nov 98 I.T., Aveiro 23

Transformadas Rápidas com Ôndulas

• Cálculo recursivo das sequências

121 Jccc

1d 2d Jd

Jc 0c Input

Output

1 Jd

Nov 98 I.T., Aveiro 24

• Pode ser invertida facilmente

121 Jccc

1d 2d Jd

Jc 0c Output

Input

1 Jd

n

jnnk

jnnk

jk dgchc 1

21

2

Transformadas Rápidas com Ôndulas

Nov 98 I.T., Aveiro 25

Transformdas Rápidas com Ôndulas

• Utilizam apenas o filtro

• Fáceis de implementar (cálculo recursivo)• Sequências e filtros finitos (truncados)

– Várias formas de lidar com as fronteiras (periodização, reflexão,...; ôndulas no intervalo)

• Algoritmos rápidos: número de operações O(N)

• Generalizam-se facilmente para várias variáveis

}{ kh

Nov 98 I.T., Aveiro 26

Ôndulas e Bancos de Filtrosj

nn

knj

k chc 21

kk hh ~

jn

nnk

jk chc 21 ~

2]~

[1 jj chc2]~[1 jj cgd

)2][()2][( 11 jjj dgchc

n

jnnk

jnnk

jk dgchc 1

21

2

Nov 98 I.T., Aveiro 27

Ôndulas e Bancos de Filtros

22

22 22

22h~

g~ g

h

jcjc

Decomposição Reconstrução

Esquema de filtragem de duas bandas com capacidade de reconstrução perfeita

Nov 98 I.T., Aveiro 28

Ôndulas e Bancos de Filtros

)2(2)( kthtk

k

No espaço de FourierNo espaço de FourierNo espaço físicoNo espaço físico

)2/(̂)2/()(̂ H

ki

kk ehH

2

1)(

Função de transferência

kjjtkt )(),( 1)()(22 HH

Nov 98 I.T., Aveiro 29

Ôndulas e Bancos de Filtros

1)0( H

)(2 RLV j 1)0(ˆ

Filtro passa-baixo

No espaço físicoNo espaço físico No espaço de FourierNo espaço de Fourier

kjjtkt )(),( 1)()(22 GG

00 WV 0)()()()( HGHG

0)0( GFiltro passa-alto

0)( H

1)( G

Nov 98 I.T., Aveiro 30

Ôndulas e Bancos de Filtros

1)()(22 HH

1)()(22 GG

0)()()()( HGHG

)()(

)()(

GH

GH

matriz unitária

H e G par de filtros de quadratura conjugada

(CQF)

Nov 98 I.T., Aveiro 31

Ôndulas e Bancos de Filtros

• ARM H filtro CQF

?

• Impor propriedades a escolhendo adequadamente o filtro?

• Importância, na prática, das propriedades

de ?

,

,

,

Nov 98 I.T., Aveiro 32

Ôndulas e Bancos de Filtros

4ˆ422ˆ2)(ˆ HHH

H ( ) 2periódica, regular

1)()(22 HH

1)0( H

0)(inf]

2,

2[

H

)2()(ˆ1

k

kH

função escala de ARM

11

2)0(ˆ2k

k

k

k HH

Nov 98 I.T., Aveiro 33

Ôndulas e Bancos de Filtros• Impor propriedades a escolhendo o filtro {hk} de

forma adequada?

Exemplo: Famíla das Ôndulas de Daubechies– Suporte compacto número finito de hk´s FIR.

– Certo número de momentos nulos (máximo permitido pelo tamanho do suporte)

– Regularidade aumentando linearmente com tamanho do suporte.

1,,0;0)(:

Nkdtttm kk

.1,,0;0)()( NkH k

Nov 98 I.T., Aveiro 34

Ôndulas de Daubechies

Nov 98 I.T., Aveiro 35

Ôndulas e Bancos de Filtros

• Importância, na prática, das propriedades de

– Regularidade: importante na síntese (imagens, p. ex.).

Erro “suave” é menos perceptível. Regularidade óptima?

– Número de momentos nulos:

Coeficientes associados a (com j grande) são quase

nulos onde a função é suave. Há apenas necessidade de

“reter” tais coeficientes onde a função é irregular.

Importante em algoritmos de análise numérica (baseados

em compressão de operadores) e em supressão de ruído.

jk

Nov 98 I.T., Aveiro 36

Ôndulas e Bancos de Filtros

– Localização na frequência:

mais importante em sinal audio do que em processamento de

imagem; “aliasing” é mais relevante no primeiro caso.

Nov 98 I.T., Aveiro 37

Generalizações

• Ôndulas de várias variáveis - várias abordagens.

• Ôndulas bi-ortogonais - filtro de síntese dual do filtro de análise. (Mais flexibilidade)

• Referenciais de ôndulas- redundância. (Importante, por exemplo, na redução do erro de reconstrução)

Nov 98 I.T., Aveiro 38

Generalizações

• “Wavelet-packets” - bancos de filtros com estrutura em árvore arbitrária; pavimentações mais gerais do plano tempo-frequência.

Mais escolha ! Algoritmo da melhor base

$$$$

Nov 98 I.T., Aveiro 39

Generalizações

• Transformadas trigonométricas locais - senos e

co-senos definidos em intervalos finitos e “ligados” de forma suave.

• Multiwavelets -várias funções escala e ôndulas-mãe.

Nov 98 I.T., Aveiro 40

Referências

• I. Daubechies, Ten Lectures on WaveletsTen Lectures on Wavelets

SIAM, Philadelphia, 1992

• B. B. Hubbard, The World According to WaveletsThe World According to Wavelets Prentice-Hall, 1995

Nov 98 I.T., Aveiro 41

Referências

• A. Akansu, R. Haddad,

Multiresolution Signal DecompositionMultiresolution Signal Decomposition

Academic Press, 1993

• S. Mallat,

A Wavelet Tour of Signal ProcessingA Wavelet Tour of Signal Processing

Academic Press, 1998

Nov 98 I.T., Aveiro 42

Referências

• G. Strang, T. Nguyen,

Wavelets and Filter BanksWavelets and Filter Banks

Wellesley-Cambridge Press, 1996

• M. Vetterli, J. Kovacevic,

Wavelets and Subband CodingWavelets and Subband Coding

Prentice-Hall, 1995

Nov 98 I.T., Aveiro 43

Software

• Mathematica Wavelet ExplorerMathematica Wavelet Explorer, Wolfram Research

• Wavelet Toolbox for use with MATLABWavelet Toolbox for use with MATLAB, Toolbox do MATLAB

• WaveLabWaveLab : (para usar com MATLAB)

– ftp://playfair.stanford.edu/pub/wavelab

• Ver também: http://www.wavelet.org