Transformada discreta de wavelet

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 \N, j \in \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^jt-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\Z} e g=\{g_n\}_{n\in\Z}:

h_n=\langle\psi_{0,0},\,\phi_{1,n}\rangle e \psi(t)=\sqrt2 \sum_{n\in\Z} h_n\phi(2t-n)

e

g_n=\langle\phi_{0,0},\,\phi_{1,n}\rangle e \phi(t)=\sqrt2 \sum_{n\in\Z} g_n\phi(2t-n).

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

Bancos de filtros[editar | editar código-fonte]

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\Z} corresponde a um filtro passa-altas e o filtro g=\{g_n\}_{n\in\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\Z} é conhecido como aproximação e o sinal d(n) = \{d_n\}_{n\in\Z} como diferença ou detalhe.

Sub amostragem[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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).[1]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

  1. Estas relações valem apenas para o caso de filtros ortogonais, SALOMON, David. Data Compression: The Complete Reference. 2 ed. Nova Iorque: Springer, 2000.

Bibliografia[editar | editar código-fonte]

  • SALOMON, David. Data Compression: The Complete Reference. 2 ed. Nova Iorque: Springer, 2000.

Ver também[editar | editar código-fonte]