Transformada de Haar
Ana Paula Cristofolini
Resumo[]
Este trabalho descreve sobre a Transformada de Haar, sua transformada rápida, seu algoritmo e alguns resultados obtidos.
Introdução[]
A transformada de Haar é uma wavelet que foi desenvolvida em 1910 por Alfred Haar para a construção de bases para representar funções integráveis quadraticamente (REIGOTA, 2007).
A Transformada de Haar é uma transformada simples, geralmente usada em algoritmos de compressão de imagens digitais (SILVA; BOGGIONE; FONSECA, 2007).
Transformada de Haar[]
A transformada de Haar é baseada nas funções de Haar, , que são definidas em intervalos contínuos z pertencente a [0,1], e para k = 0, 1, 2, ... N – 1 (sendo para uma matriz de tamanho N x N e N = ) (GONZALEZ e WOODS, 2003).
O inteiro k descrito pode ser decomposto como sendo onde , q=0 ou 1 para p=0, para outros valores de p (GONZALEZ e WOODS, 2003).
Por exemplo, para uma matriz 4x4 :
Temos a seguinte estruturação:
Sendo que para cada um dos valores da matriz se aplica a seguinte equação:
e a tabela de valores de k, p e q é:
Então:
E tendo como resultado final a seguinte matriz:
Que deve ser multiplicada a imagem original, da seguinte forma (GONZALEZ e WOODS, 2002):
onde H é a matriz encontrada acima, e F a imagem original.
Transformada Rápida de Haar[]
A transformada rápida consiste na decomposição da imagem em duas componentes: uma de média e outra referente à diferença (SENDBERG, 2006 apud SILVA; BOGGIONE; FONSECA, 2007).
Para duas amostras a e b (vizinhas) é aplicada uma transformada linear para gerar os valores s (média) e d (diferença), sendo que a média é representada pela equação (REIGOTA, 2007):
e a diferença é baseada na amostra a, com a seguinte equação (REIGOTA, 2007):
A generalização para uma imagem digital se dá com o cálculo das duas componentes citadas, para cada par de pixels da imagem (SILVA; BOGGIONE; FONSECA, 2007).
Quanto às componentes obtidas, pode-se dizer que os valores de média representam as componentes de baixa freqüência da imagem e os valores obtidos como diferença, isolam as componentes de alta freqüência (detalhes da imagem) (SILVA; BOGGIONE; FONSECA, 2007).
A Transformada Inversa de Haar é responsável pela reconstrução da imagem original onde, para os pixels descritos anteriormente, a e b, obtém-se através das seguintes equações (REIGOTA, 2007):
sendo que s e d são passados como parâmetro para a reconstrução.
A figura abaixo mostra a transformada de Haar para um vetor de 8 posições, que representam os pixels de uma imagem. A área em vermelho representa a média para o vetor original e o restante a diferença entre os termos.
Enquanto que a figura abaixo mostra a transformada inversa do vetor resultante mostrado anteriormente, partindo das médias e das diferenças e reconstruindo o vetor original.
Com base nos passos descritos anteriormente, pode-se representar a transformada rápida de Haar, como sendo a decomposição da imagem original em média e diferença, representada na figura abaixo.
Algoritmo[]
O algoritmo da Transformada de Haar pode ser esquematizado da seguinte forma para um vetor de n elementos, sendo n uma potência de 2 (n = 2^x) (REIGOTA, 2007):
1. Calcular a média de cada par (xi, xi+1) de amostras;
2. Calcular a diferença de xi e a média encontrada no passo 1;
3. Preencher a primeira metade do vetor com os valores de média;
4. Preenche o restante do vetor com as diferenças;
5. Chame a função novamente para a metade do vetor (correspondente aos valores de média.
Implementação[]
O código implementado foi o da transformada rápida de Haar, com os códigos de compactação (transformadaRapidadeHaar) e descompactação (transformadaInversaRapidadeHaar), desenvolvidos em Python.
#faz a transformada de haar para um nivel def transformadaRapidadeHaar(f): g = [] #vetor resultante sendo que a primeira metade eh a media #e a segunda a distancia for i in range(0, len(f)/2): #varre ate a metade de imagem s = (f[(2*i)] + f[(2*i+1)])/ 2.0 #calcula a media para os pares xi e xi+1 g = g + [s] #coloca no vetor for i in range(0, len(f)/2): #varre ate a metade de imagem d = f[2*i] - g[i] #calcula a diferenca de xi para a media encontrada g = g + [d] #coloca no vetor return g #faz a transformada inversa de haar para um nivel def transformadaInversaRapidadeHaar(g): f = [] #vetor que vai retornar a imagem resconstruida for i in range(0, len(g)/2): #varre ate a metade de imagem a = g[i] + g[(len(g)/2)+i] #calcula o primeiro valor usado #para obter a media e a diferenca f = f + [a] #coloca no vetor b = g[i] - g[(len(g)/2)+i] #calcula o segundo valor usado #para obter a media e a diferenca f = f + [b] #coloca no vetor return f
Aplicação[]
A transformada de Haar é aplicada, principalmente para a compressão de imagens, para transmissão ou armazenamento.
Resultados[]
Os resultados obtidos para o processo de compressão através da transformada rápida de Haar são mostradas na figura abaixo, sendo que a primeira imagem é a original e as seguintes são sucessivas chamadas a função de compressão, separado a parte descrita nas seções seguintes como média na parte em que a imagem se mantem e no restante a diferença.
A imagem original pode ser reconstruida, como mostra a figura abaixo, através da transformada inversa rápida de Haar, mostrando para sucessivas reconstruções a imagem original como resultado final.
Conclusões[]
Foi apresentada neste trabalho a transformada de Haar, utilizada principalmente para compressão de imagens, que possui como vantagens em relação as outras transformadas de wavelet a facilidade de implementação e o baixo custo computacional e que pode ser utilizada para reconstrução da imagem em várias resoluções diferentes.
Referências[]
1 GONZALEZ, Rafael C.; WOODS, Richard E. Processamento de Imagens Digitais. 2003.Editora Edgard Blücher LTDA.
2 GONZALEZ, Rafael C.; WOODS, Richard E. Digital Image Processing. 2002. Prentice Hall, New Jersey, 2ª edição.
[3] REIGOTA, Nivalda S., Comparação da Transformada Wavelet Discreta e da Transformada do Cosseno, para compressão de imagens de impressão digital, Dissertação (Mestrado em Engenharia Elétrica) - Universidade de São Paulo, São Carlos, 2007.
[4] SANDBERG, K. The Haar wavelet transform. University of Colorado at Bourder. Dept of Applied Mathematics.