Transformada 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\leq t<0.5\\-1,&0.5\leq 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^{j}t-k)}},$ onde $\phi (t)$ é a função de escala definida por $\phi (t)={\begin{cases}1,&0\leq 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\leq t<0.5\\3,&0.5\leq 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\neq 0,m\neq 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)$ .

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\leq x\leq 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}}}\leq x<{\tfrac {q-1/2}{2^{p}}},\\-2^{p/2},&{\tfrac {q-1/2}{2^{p}}}\leq 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\leq p\leq n-1,\ q=0{\mbox{ ou }}1$ para $p=0$ , e $1\leq q\leq 2^{p}$ para $p\neq 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}}$

Transformada 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}$ :