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

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[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 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[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:

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 (2000). Data Compression. The Complete Reference 2 ed. Springer [S.l.] 

Bibliografia[editar | editar código-fonte]

  • SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Springer [S.l.] 

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