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 $c_{k}$ e $d_{j,k}$,$k\in \mathbb {N} ,j\in \mathbb {N}$ da equação: $f(t)=\sum _{k=-\infty }^{\infty }{c_{k}\phi (t-k)}+\sum _{k=-\infty }^{\infty }{\sum _{j=0}^{\infty }{d_{j,k}\psi (2^{j}t-k)}},$

onde $\phi (t)$ e $\psi (t)$ 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 $\phi (t)$ e $\psi (t)$ podemos calcular as seqüências $h=\{h_{n}\}_{n\in \mathbb {Z} }$ e $g=\{g_{n}\}_{n\in \mathbb {Z} }$:

$h_{n}=\langle \psi _{0,0},\,\phi _{1,n}\rangle$ e $\psi (t)={\sqrt {2}}\sum _{n\in \mathbb {Z} }h_{n}\phi (2t-n)$

e

$g_{n}=\langle \phi _{0,0},\,\phi _{1,n}\rangle$ e $\phi (t)={\sqrt {2}}\sum _{n\in \mathbb {Z} }g_{n}\phi (2t-n)$.

Estas duas seqüências são a base da transformada discreta de wavelet.

Bancos de filtros

Banco de filtros da transformada discreta de wavelet.

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 $h=\{h_{n}\}_{n\in \mathbb {Z} }$ corresponde a um filtro passa-altas e o filtro $g=\{g_{n}\}_{n\in \mathbb {Z} }$ a um filtro passa-baixas (conforme imagem ao lado).

Os filtros $h$ e $g$ são operadores lineares, que podem ser aplicados no sinal digital de entrada $x$ como uma convolução:

$c(n)=\sum \limits _{k}g(k)x(n-k)=g\star x$

e

$d(n)=\sum \limits _{k}h(k)x(n-k)=h\star x.$

O sinal $c(n)=\{c_{n}\}_{n\in \mathbb {Z} }$ é conhecido como aproximação e o sinal $d(n)=\{d_{n}\}_{n\in \mathbb {Z} }$ como diferença ou detalhe.

Sub-amostragem

O operador $(\downarrow 2)$ é 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:

$(\downarrow 2)x(n)={x_{0},x_{2},x_{4},...}.\,$

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

Encadeamento de bancos de filtros com sub-amostragem.

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 $h'$ e $g'$ podem ser obtidos como:

• o filtro $g'$ é o reverso do filtro $g$ (filtro $g$ com os coeficientes invertidos):

$g'=(g'_{1},g'_{2},...,g'_{N})=(g_{N},g_{N}-1,...,g_{1}).$

• o filtro $h'$ é igual ao filtro $g$ com os sinais dos elementos pares invertidos:

$h'=(h'_{1},h'_{2},...,h'_{n},...,h'_{N})=(g_{1},-g_{2},...,(-1)^{n+1}g_{n},...,(-1)^{N+1}g_{N}).$

Antes de se recompor o sinal, entretanto, é necessário aplicar o operador de super-amostragem $(\uparrow 2)$ nas seqüências decompostas $h'$ e $d'$.

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:

$(\uparrow 2)s=(s'_{1},s'_{2},s_{3},...,s'_{2N-1},s'_{2N})=(s_{1},0,s_{2},...,s_{N},0)$

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

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