Transformada de Haar

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou se(c)ção não cita fontes fiáveis e independentes (desde Junho de 2012). Por favor, adicione referências e insira-as no texto ou no rodapé, conforme o livro de estilo. Conteúdo sem fontes poderá ser removido.
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 \phi(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).

Representação matricial[editar | editar código-fonte]

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}

Transformada rápida de Haar[editar | editar código-fonte]

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

Notas e referências[editar | editar código-fonte]

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

Bibliografia[editar | editar código-fonte]

  • (em inglês) SALOMON, David. Data Compression: The Complete Reference. 2. ed. Nova Iorque: Springer, 2000.

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

O Commons possui uma categoria contendo imagens e outros ficheiros sobre Transformada de Haar