Fandom

Students

LAPIS/Disciplinas/Processamento de Imagens:TransfHaar

< LAPIS | Disciplinas

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

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.

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.

Also on Fandom

Random Wiki