Transformada de Haar

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

Wavelet de Haar.

A Transformada de Haar é um transformada matemática discreta usada no processamento e análise de sinais, na compressão de dados e em outras aplicações de engenharia e ciência da computação. Ela foi proposta em 1909 pelo matemático húngaro Alfred Haar. A transformada de Haar é um caso particular de transformada discreta de wavelet, onde o wavelet é um pulso quadrado definido por:

$\psi(t) = \begin{cases} 1, & 0 \le t < 0.5 \\ -1, & 0.5 \le t < 1. \\ 0, & \mbox{para outros valores de } t \end{cases}$

Na figura vemos ilustrada a wavelet de Haar. Apesar de ter sido proposta muito antes do termo wavelet^[1] ser cunhado, a wavelet de Haar é considerada como um caso particular das wavelets de Daubechies, conhecida por isso como wavelet de Daubechies D2.

A transformada de Haar pode ser usada para representar um grande número de funções $f (t)$ como sendo o somatório:

$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)$ é a função de escala definida por $\phi(t) = \begin{cases} 1, & 0 \le t < 1 \\ 0, & \mbox{para outros valores de } t, \end{cases}$ e $c k$ e $d j, k$ são parâmetros a serem calculados.

Por exemplo, a função degrau definida por:

$f(t) = \begin{cases} 5, & 0 \le t < 0.5 \\ 3, & 0.5 \le t < 1, \end{cases}$

pode ser representada como $f(t) = 4\phi(t) + \psi(t) \,$ . O seja os parâmetros $c 0 = 4$ e $d 0,0 = 1$ , e $c n = 0$ e $d n, m = 0$ para $n \ne 0, m \ne 0$ . O vetor $(4,1)$ equivale a transformada discreta de Haar da função f(t), que pode ser representada também na forma vetorial como $(5,3)$ .

Índice

1 Representação matricial
2 Trasformada rápida de Haar
- 2.1 Exemplo de Implementação
3 Notas e referências
4 Bibliografia
5 Ver também

[editar] Representação matricial

Como vimos acima, a transformada de Haar em sua forma discreta pode ser expressa como uma multiplicação matricial. No exemplo citado acima temos:

$(5,3) A 2 = (4,1)$ dando a matriz $A 2$ como sendo:

$A_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

E assim a transformada inversa de Haar se torna:

$(4, 1)A_{2}^{-1} = (5, 3)$

Entretanto a matriz $A_{2}^{-1}$ é difícil de ser calculada, mas sabemos que se a matriz $A 2$ for ortonormal sua inversa é igual a sua transposta. Assim podemos utilizar a matriz:

$A_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

para a a transformada de Haar discreta, sendo sua inversa $A_2^{-1} = A_2^{T}$ .

Assim, a transformada discreta de Haar em sua forma matricial pode ser expressa por uma matriz $A N$ de tamanho $N \times N$ onde os elementos $A_{N_{i,j}}$ são definidos como

$A_{N_{i,j}} = h_{i-1} \left (\frac{j-1}{N} \right )$ onde

$h_0(x) \overset{\underset{\mathrm{def}}{}}{=} h_{00}(x) = \frac{1}{\sqrt{N}},\mbox{ para } 0 \le x \le 1,$

$h_k(x) \overset{\underset{\mathrm{def}}{}}{=} h_{p,q} = \frac{1}{\sqrt{N}} \begin{cases} 2^{p/2}, & \tfrac{q-1}{2^p} \le x < \tfrac{q-1/2}{2^p}, \\ -2^{p/2}, & \tfrac{q-1/2}{2^p} \le x < \tfrac{q}{2^p}, \\ 0, & \mbox{para outros valores de } x \in [0,1]. \end{cases}$

e $k = 2 p + q - 1,$ onde $N = 2 n$ , $0 \le p \le n-1,\ q = 0 \mbox{ ou } 1$ para $p = 0$ , e $1 \le q \le 2^p$ para $p \ne 0$

Assim, a matriz $A 2$ do nosso exemplo passa a ser:

$A_2 = \begin{pmatrix} h_0(0/2) & h_0(1/2) \\ h_0(1/2) & h_1(1/2) \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

[editar] Trasformada rápida de Haar

Na prática a transformada de Haar consiste em calcular a soma e a diferença entre os elementos de um vetor dois a dois. Assim, definimos a transformada rápida de Haar de um vetor $S_n = (s_1, s_2, ..., s_n) \,$ como os dois vetores $M_{n/2} = (m_1, m_2, ..., m_{n/2} ) = \left ( \tfrac{s_1+s_2}{\sqrt{2}}, \tfrac{s_3+s_4}{\sqrt{2}}, ..., \tfrac{s_{n-1}+s_n}{\sqrt{2}}\right)$ e $D_{n/2} = (d_1, d_2, ..., d_{n/2}) = \left ( \tfrac{s_1-s_2}{\sqrt{2}}, \tfrac{s_3-s_4}{\sqrt{2}}, ..., \tfrac{s_{n-1}-s_n}{\sqrt{2}}\right)$ .

A transformada inversa simplesmente recalcula os valores originais a partir da média e das diferenças. A transformada inversa recebe então os vetores $M n / 2$ e $D n / 2$ devolve um vetor $S' n = S n$ :

$S'_n = \left ( m_1 + d_1, m_1 - d_1, m_2 + d_2, m_2 - d_2, ..., m_{n/2} + d_{n/2}, m_{n/2} - d_{n/2} \right ).$

[editar] Exemplo de Implementação

O trecho de código python abaixo exemplifica esse cálculo:

#!/usr/bin/python
# coding: utf-8
import math
def haar_transform(S):
    M = []
    D = []
    for i in range(0, len(S), 2):
        m = (S[i] + S[i+1]) / math.sqrt(2)
        d = (S[i] - S[i+1]) / math.sqrt(2)
        M = M + [m]
        D = D + [d]
    return (M, D)
 
def haar_inverse(M, D):
    S = []
    for i in range(0, len(M)):
        s1 = M[i] + D[i]
        s2 = M[i] - D[i]
        S = S + [s1, s2]
    return S
 
S = [5,3]
(M,D) = haar_transform(S)
print M, D
print haar_inverse(M, D)
S = [1,0,2,9,3,8,4,7,5,6]
(M,D) = haar_transform(S)
print M, D
print haar_inverse(M, D)

[editar] Notas e referências

↑ A transformada foi proposta por Alfred Haar em 1909 e o termo Wavelet só viria mais tarde. (ver en:Haar wavelet)

[editar] Bibliografia

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

[editar] Ver também

Categoria: Processamento de imagem

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

Transformada de Haar

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

Índice

[editar] Representação matricial

[editar] Trasformada rápida de Haar

[editar] Exemplo de Implementação

[editar] Notas e referências

[editar] Bibliografia

[editar] Ver também

Views

Navegação

colaboração

Busca

Outras línguas