Transformada discreta de wavelet
A transformada wavelet discreta é a transformada correspondente à transformada contínua de wavelet para funções discretas. Esta transformada é utilizada para analisar sinais digitais, e também na compressão de imagens digitais. A forma mais simples dessa transformada, conhecida como transformada de Haar foi criada em 1909.
A transformada discreta de wavelet consiste em identificar os parâmetros e , da equação:
onde e são as funções conhecidas respectivamente como wavelet pai (do inglês father wavelet) e wavelet mãe (ver wavelet para mais detalhes sobre a função wavelet mãe). A wavelet pai é na verdade uma função de escala, que depende da wavelet mãe. Das funções e podemos calcular as seqüências e :
- e
e
- e .
Estas duas seqüências são a base da transformada discreta de wavelet.
Bancos de filtros
A maneira mais comum de se calcular a transformada discreta de wavelet é através da aplicação de bancos de filtros onde o filtro determinado pelos coeficientes corresponde a um filtro passa-altas e o filtro a um filtro passa-baixas (conforme imagem ao lado).
Os filtros e são operadores lineares, que podem ser aplicados no sinal digital de entrada como uma convolução:
e
O sinal é conhecido como aproximação e o sinal como diferença ou detalhe.
Sub-amostragem
O operador é o operador de sub-amostragem (do inglês downsampling). Este operador aplicado a uma função discreta (uma seqüência) reduz o seu número de elementos pela metade, recuperando apenas os elementos em posições pares:
O uso de filtros ortogonais nos permite recuperar o sinal original (reconstrução perfeita do sinal) apesar da perda de dados devido à sub-amostragem. Filtros bi-ortogonais também são capazes de reconstruir perfeitamente o sinal mesmo após a sub-amostragem.
Encadeamento de bancos de filtros
A decomposição com o filtro acima decompõe o sinal em apenas duas faixas de freqüência. Podemos encadear uma série de bancos de filtros, usando a operação de sub-amostragem para proporcionar a divisão da freqüência de amostragem por 2 (como visto na figura ao lado) a cada novo banco de filtros encadeado.
Assim, temos um sinal de detalhe específico para cada faixa de freqüência na nossa etapa de análise do sinal.
Transformada inversa
A transformada discreta inversa de wavelet consiste em aplicar os filtros inversos no sinal decomposto, e juntar novamente as duas (ou mais) bandas de freqüência do sinal. No caso dos filtros ortogonais, os filtros inversos e podem ser obtidos como:
- o filtro é o reverso do filtro (filtro com os coeficientes invertidos):
- o filtro é igual ao filtro com os sinais dos elementos pares invertidos:
- [1]
Antes de se recompor o sinal, entretanto, é necessário aplicar o operador de super-amostragem nas seqüências decompostas e .
Super-amostragem
O operador de super-amostragem (do inglês upsampling) que usamos na transformada inversa corresponde simplesmente a acrescentar zeros nas posições que foram eliminadas pela sub-amostragem:
Exemplo de implementação
Abaixo um exemplo de implementação em python da transformada discreta de wavelet usando bancos de filtros:
#!/usr/bin/python # coding: utf-8 import math # Coeficientes dos wavelets de Daubechies. D6=[4.70467210E-01,1.14111692E+00,6.50365000E-01,-1.90934420E-01,-1.20832210E-01,4.98175000E-02] D6 = [x/math.sqrt(2.0) for x in D6] sq3 = math.sqrt(3.0) D4 = [1 + sq3, 3+sq3, 3-sq3, 1-sq3] D4 = [x/(4*math.sqrt(2)) for x in D4] D2 = [1.0/math.sqrt(2), 1.0/math.sqrt(2)] def make_filters(h0): """ Deriva os filtros passa alta e os filtros reversos a partir do filtro passa baixa. """ f0 = reverse(h0) f1 = mirror(h0) h1 = reverse(f1) return (h0, h1, f0, f1) def reverse(h): """ Inverte os elementos de um vetor """ return reversed(h) def mirror(h): """ Troca o sinal dos elementos em posições ímpares. """ return [x * (-1)**i for i,x in enumerate(h)] def downsample(h): """ Retira o segundo elemento de cada dois. """ return h[::2] def upsample(h): """ Intercala o número 0 entre os valores de um vetor. """ ret = [] for x in h: ret.extend([x, 0]) return ret def add(v1, v2): """ soma os elementos de dois vetores. """ return (a+b for a,b in zip(v1, v2)) def rotate_left(v, size): """ Usado para compensar o desvio temporal do banco de filtros """ return v[size:] + v[:size] def convolution(filter, data): """ Calcula uma convolução discreta de dois vetores. """ return [sum(data[(i-j) % len(data)] * filter[j] for j in range(len(filter))) for i in range(len(data))] def dwt(data, filter): """ Decompõe um sinal usando a transformada discreta de wavelet aplicada recursivamente (encadeamentode bancos de filtros) conforme visto em: http://pt.wikipedia.org/wiki/Transformada_discreta_de_wavelet """ (h0, h1, f0, f1) = make_filters(filter) alfa = list(data) beta = [] while len(alfa) > len(filter): tmp = downsample(rotate_left(convolution(h1, alfa),len(filter)-1)) alfa = downsample(rotate_left(convolution(h0, alfa),len(filter)-1)) beta = tmp + beta return alfa + beta def idwt(data, filter): """ Recompõe o sinal decomposto pela DWT, conforme: http://pt.wikipedia.org/wiki/Transformada_discreta_de_wavelet """ (h0, h1, f0, f1) = make_filters(filter) size = 1 while size < len(filter): size *= 2 size /= 2 ret = list(data) while size < len(data): alfa = convolution(f0, upsample(ret[:size])) beta = convolution(f1, upsample(ret[size:2*size])) ret = add(alfa, beta) + ret[2*size:] size *= 2 return ret filter = D6 (h0, h1, f0, f1) = make_filters(filter) data = [53,75,97,29,11,33,44,66,88,130,62,33,674,45,36,67] ret = dwt(data, filter) print ret ret = idwt(ret, filter) print ret
Referências
- ↑ Estas relações valem apenas para o caso de filtros ortogonais, SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer
Bibliografia
- SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer
Ver também
- Wavelet
- Transformada Z
- Transformada discreta de Fourier
- Compressão de dados
- JPEG2000
- DCT