Fandom

Students

LAPIS/Disciplinas/Processamento de Imagens:TransfHaar

< LAPIS | Disciplinas

1,331pages on
this wiki
Add New Page
Talk0 Share

Transformada de Haar

Ana Paula Cristofolini


Resumo Edit

Este trabalho descreve sobre a Transformada de Haar, sua transformada rápida, seu algoritmo e alguns resultados obtidos.

Introdução Edit

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 Edit

A transformada de Haar é baseada nas funções de Haar, h_c(z), 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 = 2^n) (GONZALEZ e WOODS, 2003).

Funcao1
Funcao2

O inteiro k descrito pode ser decomposto como sendo k = 2^p + q - 1 onde 0\leq p\leq n-1, q=0 ou 1 para p=0, 1\leq q \leq^p para outros valores de p (GONZALEZ e WOODS, 2003).

Por exemplo, para uma matriz 4x4 :

Matriz

Temos a seguinte estruturação:

MatrizA

Sendo que para cada um dos valores da matriz se aplica a seguinte equação:

Formula1

e a tabela de valores de k, p e q é:

Tabela1

Então:
A_{11} = h_0 (0/4) = 1/\sqrt4*1
A_{12} = h_0 (1/4) = 1/\sqrt4*1
A_{13} = h_0 (2/4) = 1/\sqrt4*1
A_{14} = h_0 (3/4) = 1/\sqrt4*1
A_{21} = h_1 (0/4) = 1/\sqrt4*1
A_{22} = h_1 (1/4) = 1/\sqrt4*1
A_{23} = h_1 (2/4) = 1/\sqrt4*(-1)
A_{24} = h_1 (3/4) = 1/\sqrt4*(-1)
A_{31} = h_2 (0/4) = 1/\sqrt4*\sqrt2
A_{32} = h_2 (1/4) = 1/\sqrt4*(-\sqrt2)
A_{33} = h_2 (2/4) = 0
A_{34} = h_2 (3/4) = 0
A_{41} = h_3 (0/4) = 0
A_{42} = h_3 (1/4) = 0
A_{43} = h_3 (2/4) = 1/\sqrt4*\sqrt2
A_{44} = h_3 (3/4) = 1/\sqrt4*(-\sqrt2)



E tendo como resultado final a seguinte matriz:

Matrizfinal

Que deve ser multiplicada a imagem original, da seguinte forma (GONZALEZ e WOODS, 2002):

T = HFH

onde H é a matriz encontrada acima, e F a imagem original.

Transformada Rápida de Haar Edit

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

s = (a + b)/2

e a diferença é baseada na amostra a, com a seguinte equação (REIGOTA, 2007):

d = a - s

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

a = s + d

b = s - d

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.

Figura1

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.

Figura2

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.

Figura3


Algoritmo Edit

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 Edit

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 Edit

A transformada de Haar é aplicada, principalmente para a compressão de imagens, para transmissão ou armazenamento.


Resultados Edit

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.

Transformada

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.

TransformadaInversa


Conclusões Edit

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 Edit

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.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.