Transformada discreta de wavelet

Origem: Wikipédia, a enciclopédia livre.

A transformada discreta de wavelet é a transformada correspondente à trasformada 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 $φ(t)$ e $ψ(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 $φ(t)$ e $ψ(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)$

$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.

Índice

1 Bancos de filtros
- 1.1 Sub amostragem
- 1.2 Encadeamento de bancos de filtros
2 Transformada inversa
- 2.1 Super-amostragem
3 Exemplo de implementação
4 Referências
5 Bibliografia
6 Ver também

[editar] 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\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 um operador linear, que pode ser aplicado no sinal digital de entrada $x$ como uma convolução:

$c(n) = \sum\limits_k g(k)x(n-k) = g \star x$

$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.

[editar] 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.

[editar] 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.

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

^[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'$ .

[editar] 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)$

[editar] 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
    """
    ret = [h[x] for x in range(len(h)-1,-1,-1)]
    return ret
 
def mirror(h):
    """
        Troca o sinal dos elementos em posições
        ímpares.
    """
    ret = [(h[x] * ((-1)**x)) for x in range(0, len(h))]
    return ret
 
def downsample(h):
    """
        Retira o segundo elemento de cada dois.
    """
    ret = [h[x] for x in range(0, len(h), 2)]
    return ret
 
def upsample(h):
    """
        Intercala o número 0 entre os valores de um vetor.
    """
    ret = []
    for i in range(0, len(h)):
        ret = ret + [h[i], 0]
    return ret
 
def add(v1, v2):
    """
        soma os elemntos de dois vetores.
    """
    ret = [v1[i] + v2[i] for i in range(0, len(v1))]
    return ret
 
def rotate_left(v, size):
    """
        Usado para compensar o desvio temporal do
        banco de filtros
    """
    ret = v[size:] + v[0:size]
    return ret
 
def convolution(filter, data):
    """
        Calcula uma convolução discreta de dois vetores.
    """
    ret = [0 for x in range(0,len(data))]
    for i in range(0, len(data)):
        for j in range(0, len(filter)):
            pos = i-j
            if pos >= 0 and pos < len(data):
                ret[i] = ret[i] + data[pos] * filter[j]
            elif pos < 0:
                ret[i] = ret[i] + data[len(data)+pos] * filter[j]
            elif pos >= len(data):
                ret[i] = ret[i] + data[pos-len(data)] * filter[j]
    return ret
 
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 = [x for x in 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 = size*2
    size = size/2
    ret = [x for x in data]
    while size < len(data):
        alfa = convolution(f0, upsample(ret[0:size]))
        beta = convolution(f1, upsample(ret[size:2*size]))
        ret = add(alfa, beta) + ret[2*size:]
        size = 2*size
    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

[editar] Referências

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

[editar] Bibliografia

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

[editar] Ver também

Categorias: Processamento de sinais | Compressão de dados

See also ebooksgratis.com: no banners, no cookies, totally FREE.