Quadros, representações redundantes e

adaptativas

Hilton de Oliveira Mota

Introdução● Na aula anterior: DWT → bases ortogonais/biortogonais de suporte

compacto.

– Ortogonalidade → máxima compactação, sem redundância.

– Suporte compacto → atuação localizada.

– Análise multiresolução → processamento do “todo” ou das partes.

● Somente vantagens? Algum problema?

– Representações “rígidas” → decomposição e reconstrução únicas.

– Variantes à translação!

● Nesta aula, estenderemos o conceito a representações mais flexíveis:

– Quadros justos (“tight frames”) → representações sobrecompletas, infinitas formas de reconstrução, representações canônicas.

– Ladrilhamento tempo-frequência adaptativo → pacotes de wavelets.

– Transformada de wavelets estacionária.

– Wavelets direcionais, Ridgelets, Curvelets, Contourlets.

Pacotes de wavelets

● STFT → ladrilhamento constante → resolução tempo-frequência constante.

● WT → ladrilhamento variável com área constante → resolução tempo frequência variável, mas fixa!

Pacotes de wavelets● Pacotes de wavelets (WP) → generalização da DWT:

– Ladrilhamento mais flexível → definido pelo usuário.

– Gera um “frame” justo → representação redundante → infinitas reconstruções.

– Proporciona algoritmos adaptativos!

Ladrilhamento da DWT Ex.: um dos possíveis ladrilhamentos de WP

Pacotes de wavelets

● WPs baseiam-se no mesmo algoritmo da DWT → decomposição piramidal.

– Mas tanto as aproximações quanto os detalhes são decompostos em cada nível!

DWT decomposition bank Wavelet packets decomposition bank

*Obs.: a reconstrução canônica de WP é similar à reconstrução da DWT.

Decomposição por pacotes de wavelets

Decomposição da DWT Decomposição por WP

Decomposição final: vetor 1xN

Decomposição final: matriz MxN.Qualquer combinação de caixas destamatriz permite reconstruir o sinal!

Adaptativo!

Funções de pacotes de wavelets

● Funções (átomos) de WP são obtidos das wavelets ortogonais ou biortogonais.

● Ex.: átomos de WP de Daubechies 3.

Funções de pacotes de wavelets

Funções de pacotes de wavelets

Ladrilhamento do plano tempo-escala

Vão se tornando maislargos no tempo(diminui resolução temporal)

Vão se tornando mais estreitos na frequência(aumenta resolução em frequência).

Cada nível corresponde a um ladrilhamento comretângulos de mesmotamanho

Ladrilhamento do plano tempo-escala● Vários ladrilhamentos podem ser utilizados:

– Dependendo de quais “pacotes” o usuário mantém.

– Desde que o plano seja completamente coberto.

● Exemplos:

Pacotes originais da DWT Ladrilhamento tempo-frequência

Ladrilhamento do plano tempo-escala

Outros pacotes: Ladrilhamento correspondente:

Obs.: como seriaa reconstruçãocanônica?

Notar que:

O eixo do tempo deve ser completamente coberto.

Não pode haver sobreposição no tempo.

Pode haver sobreposição na frequência.

Raciocínio: quais frequências são melhores em cada intervalo?

Bases de pacotes de wavelets● Bases de pacotes de wavelets → seleção dos

“melhores” pacotes (ladrilhamento) com base em algum critério (“best basis”).

● Uma forma (largamente usada) → entropia de Shannon [1].

S ( p)=−∑i

pi log p i

onde p é uma função densidade de probabilidade (PDF) normalizada (energia do pacote).– Maior entropia → informação mais espalhada.

– Baixa entropia → informação concentrada em poucos coeficientes.

● Portanto → encontre o conjunto de pacotes que resulte na menor entropia → representação mais esparsa.

[1] R. R. Coifman and M. V. Wickerhauser, “Entropy-based algorithms for best basis selection,” IEEE Trans. Inf. Theory, vol. 38, no. 2, pp. 713–718, 1992.

Bases de pacotes de wavelets

● Seleção de bases de WP com entropia.

– Analise a matriz de WP de baixo para cima.

– Compare a entropia de um par de “pacotes-filhos” com a entropia do “pacote-pai”.

– Se a entropia dos filhos for maior → descarte os filhos.

– Se a entropia dos filhos for menor → mantenha os filhos, atribua a sua entropia ao pai.

– Suba para o nível superior e repita até o 1o nível.

● Lembre-se → esta é apenas uma das formas de se selecionar os pacotes:

– Pode-se usas outros critérios → “matching pursuit”, “basis pursuit”, etc...

Bases de pacotes de wavelets

1.

2.

4.

3.

5.

Ex.: decomposição por WP3 level WP decomposition WP tree

Ex.: decomposição por WPWP tree DWT tree Best entropy WP tree

Ex.: decomposição por WPBest entropy WP tree Corresponding coefficients

Ex.: decomposição por WPReconstruction from the best tree

Árvores de pacotes de wavelets

● Árvores admissíveis → árvores em que em cada nó há somente zero ou duas filhas.

2N /2⩽B J⩽25N /8

● Qualquer árvore admissível gera uma base ortogonal para o espaço original.

● Uma decomposição por WP completa, até o J = log2 N, possui BJ árvores admissíveis, portanto BJ bases ortogonais, onde

Considerações:● A WP sofre os mesmos efeitos de bordas da DWT.

– Lembre-se: periodization, zero padding, smoothing window, etc...

– O tipo de tratamento afeta o número de coeficientes em cada nível → BE CAREFUL!

● Para sinais de comprimento N = 2M e tratamento por periodização:

– O máximo número de níveis é J = log2 N.

– A decomposição completa gera N log2 N coeficientes.

2D wavelet packets

● Caso mais simples → wavelets ortogonais, mesma escala ao longo de x1 e x2.

● Lembrando: 2D-DWT.

1 – Horizontal2 – Vertical3 – Diagonal

● No caso da 2D-WP → cada submatriz de aproximações e detalhes é completamente decomposta.

● Conhecido como “Wavelet Packets Quad-trees”.

Wavelet packets quad-trees

● Quad-trees admissíveis → quad-trees cujos nós têm zero ou quatro filhas.

● Qualquer quad-tree admissível corresponde a uma base ortogonal para sinais 2D.

● Uma decomposição por WP-2D com N1 = N2 = 2N até o nível máximo J = log2 N gera BJ árvores admissíveis, onde

2N4 ⩽BJ⩽2

4948N4

Bancos de filtros para 2D Wavelet packets

● Bancos de filtros de 2D-WP são iguais a 2D DWT.

– A única diferença tanto aproximações quanto detalhes são decompostos.

Decomposition Reconstruction

Ex.: decomposição de imagens

...

Ex.: compressão de imagens com WP

Original image Reconstruction with 10% largest best basis coefficients

Reconstruction with 10% largest DWT coefficients

A transformada de wavelets estacionária (SWT)

● Transformadas de wavelets ortogonais e biortogonais têm êxito em algumas aplicações.

– Ex.: padrão de compressão de imagens JPEG 2000 com wavelets biortogonais.

● Para outras aplicações podem não ser tão boas.

– Eliminação de ruídos.

– Desconvolução e deblurring.

– Extração de características.

● Geralmente →signais corrompidos por interferências → informação distorcida ou incompleta.

A transformada de wavelets estacionária

● Ortogonal ou biortogonal → variantes à translação → dizimação por 2 em cada nível de decomposição.

● Para um sinal de comprimento N → N decomposições diferentes (uma para cada rotação).

● Perda de dados dependendo do processamento realizado.

● “Pseudo-Gibbs” próximo às descontinuidades do sinal.

A transformada de wavelets estacionária● Possíveis soluções:

– Trabalhe com transformada de wavelet contínua.

● Altamente redundante, computacionalmente custosa, problemas com reconstruções aproximadas, etc...

– Retire a dizimação→ transformada de wavelet ESTACIONÁRIA*.

*A SWT também é conhecida como “translation-invariant wavelet transform” (TI-WT), “undecimated wavelet transform” (UWT), “ε-decimated WT” e algorithme à trous.[1] G. P. Nason and B. W. Silverman, “The stationary wavelet transform and some statistical applications,” in Lecture notes in statistics 103 - waveelets and statistics, A. Antoniadis and G. Oppenheim, Eds. New York: Springer-Verlag, 1995, pp. 281–300.[2] R. R. Coifman and D. L. Donoho, “Translation-Invariant De-Noising,” in Lecture notes in statistics 103 - wavelets and statistics, A. Antoniadis and G. Oppenheim, Eds. Springer-Verlag, 1995, pp. 125–150.

am+1, n=1

√2∑k

l k−2nam,k

dm+1,n=1

√2∑k

hk −2nam, k

DWT decomposition UWT decomposition

am+1, n=1

√2∑k

l k−nam,k

dm+1,n=1

√2∑k

hk −nam, k

Decomposição por SWT

● Decomposição em cada subnível é realizada separando-se coeficientes indexados por pares e ímpares.

– Cada subvetor é decomposto separadamente.

Note that:c0

c1→[c1e , c1

o]

c2→[c2,1 , c2,2]→[[c2,1e , c2,1

o] , [c2,2

e , c2,2o

] ]

c3→[c3,1, c3,2 , c3,3 , c3,4 ]→

⋮→[[c3,1

e , c3,1o

] , [c3,2e ,c 3,2

o]] ,

[[c3,3e , c3,3

o] , [c3,4

e , c3,4o

]]

N samples

N samples

N samples

Obs.: “filtro” de separação (não é dizimação).

Reconstrução da SWT

● Reconstrução canônica → recombinação das partes pares e ímpares seguida do filtro de reconstrução.

Realizações eficientes

● Algorithme à trous.

– Insira 2j – 1 zeros entre cada coeficiente dos filtros ou

– Amostre o nível anterior com passos de 2j e deslocamentos simples.

Realizações eficientes

● WT invariante à translação (TI-WT).

– Sinais de comprimento finito N → faça deslocamentos circulares em cada nível de decomposição.

– Execute o algoritmo piramidal em cada versão deslocada.

– Recombine os coeficientes de forma a obter a SWT.

● Sinal de comprimento N → matriz com N x N coeficientes.

● A matriz contém as DWTs de todas as versões circulares do sinal.

● Reconstrução canônica → média de cada 2 aproximações.

● Sinais 2D → mesmo procedimento.

Ex: TI-table e Stat-table

Ex.: decomposição de imagens por SWT

Ex.: comparação de denoising por DWT and SWT

DWT hard-thresholding SWT hard-thresholding

Ex.: denoising de imagens por SWT e DWT

Original image Corrupted image

Denoised by SWT Denoised by DWT

Ex.: denoising por SWT máximos de wavelets

Linhas e máximos de SWT “Cycle Spinning”

Ex.: denoising por SWT máximos de wavelets