Trasnformada de Haar

O que é Wavelet?

Wavelet, um termo referido em 1909 por Alfred Haar, é definido como uma função matemática que divide qualquer tipo de dados, no domínio das frequências e do tempo, hierarquicamente em componentes de frequência, para que cada componente possa ser analisado em diferentes escalas conforme a sua resolução. Essa decomposição é chamada de Transformada de Wavelet e o seu princípio é semelhante ao das outras transformadas, sendo comparada regularmente com a Transformada de Fourier, que explicita que qualquer função pode ser expressa como a soma de funções sinusoidais multiplicadas por coeficientes.

Para proceder à análise das Wavelets, o procedimento passa por escolher uma função protótipo, chamada por Wavelet mãe (Mother Wavelet). É então feita uma análise temporal com uma versão de frequências altas da função protótipo e uma análise de frequências com uma versão de frequências baixas da mesma função.

Como o sinal ou função original pode ser representada pela combinação linear das funções Wavelet usando os coeficientes, quaisquer operações podem ser feitas sobre os coeficientes Wavelet correspondentes. Caso as funções Wavelet sejam bem escolhidas para representar os dados originais, pode resultar numa representação escassa mas precisa dos dados. Esta representação escassa é que faz com que este método seja muito útil na compressão de dados.

As Transformadas Wavelet aplicadas à compressão de imagens (JPEG 2000 por exemplo) normalmente possuem ambos os modos de compressão (compressão sem perdas e com perdas).

O algoritmo da “Transformada de Haar”

A transformada de Haar aplicada à compressão de imagens pode-se subdividir em duas partes, a transformada de Haar para uma dimensão e duas dimensões. Como a transformada para duas dimensões é na realidade uma generalização da transformada para uma dimensão faz sentido começar por esta última.

o modo de funcionamento da transformada de Haar passa por decompor os dados em funções base. Para isso as imagens poderão ser consideradas como um conjunto de funções constantes no intervalo [0,1). Então uma imagem de um pixel é apenas uma função constante, no qual existe um espaço vectorial V0 por exemplo, em todo o intervalo [0,1). Uma imagem de dois pixels será então duas funções constantes, uma entre [0,1/2) e a outra entre [1/2,1), contidas no espaço vectorial V1­­. Se continuarmos no fim irá existir um espaço vectorial Vj contendo todas as funções constantes duma imagem com 2j pixels.

Agora será necessário encontrar as funções base para os espaços Vj. A estas funções é dado o nome de funções de escalamento (scaling functions) e serão definidas pelo símbolo Φ. Uma função de escalamento para Vj será então:

Φ ij(x) = Φ (2jx-i),                   Φ =0,1,…,2j-1

Onde, Φ (x) = 1, se 0 <= x <1

Φ (x) = 0, para todo o restante

haar1

Figura 1

A figura 1 mostra as quatro funções de escalamento que servem de base para V2.

O passo seguinte será definir um novo espaço vectorial Wj que serve de complemento ortogonal de Vj em Vj+1. As funções linearmente independentes que geram Wj são então chamadas de Wavelets e servem basicamente para representar as partes das funções em Vj+1 que não podem ser representadas em Vj. Elas são definidas pela expressão:

ψij(x) = ψ(2jx-i),                      i=0,…,2j-1

Onde, ψ (x) =1, para 0 <= x <½

ψ (x) =-1, para ½ <= x < 1

ψ (x) = 0, para restante.

Estas funções são, finalmente, as funções de base das Wavelets Wj, também chamadas por Wavelets Haar.

Figura 2 – Wavelets de Haar para W1

Figura 2 – Wavelets de Haar para W1

 

Em termos de descodificação, as transformadas Wavelet possuem uma característica chamada condição de admissibilidade para poderem ser utilizadas na análise de sinais, o que permite a existência da transformada inversa Wavelet. É também utilizada a transformada de Fourier no processo de descodificação.

 

Codificação

Na prática, quando aplicado a uma imagem, o algoritmo da Transformada de Haar, recursivamente, agrupa os pixels dois a dois, calcula a média entre eles e posteriormente calcula a diferença dos pixels originais para as médias, também chamada de coeficientes de detalhe. No final irá restar, no primeiro pixel uma média de todos os pixels, e nos restantes os coeficientes de detalhe.

 

Algoritmo da codificação em Pseudo-Código:

Function Haar_Calc (INPUT, SIZE)
		For I=0, J=0 to I &lt; SIZE, I step+2
	A [J]  (INPUT [I] + INPUT [I+1])/ 2
	C [J]  (INPUT [I] – INPUT [I+1])/ 2
K  0
While COEF [K] &lt;&gt; ‘\0’
	K++
COEF [K]  C [J]
If length (A) = 1
	FIN  A [0]
Else
	FIN  Haar_Calc (A,length (A))
Return FIN

O algoritmo da Transformada de Haar quando aplicado a duas dimensões no fundo é igual. Na verdade, aplica-se o algoritmo a todas as linhas de pixels e depois faz-se o mesmo para todas as colunas, a que se dá o nome de decomposição ‘Standard’. O resultado será um único coeficiente médio global e tudo o resto será coeficientes de detalhe.

Uma das propriedades das Wavelets, que é desejável na compressão de imagem, é a possibilidade das funções base serem normalizadas, ou seja, uma função será normalizada se o seu produto interno for 1. Para aplicar este conceito às funções base wavelet será preciso modificar as expressões indicadas anteriormente para as seguintes:

Φij(x) = 2j/2 Φ(2jx-i)

ψij(x) = 2j/2 ψ(2jx-i)

O facto de as funções base serem normalizadas, possui duas vantagens principais. A primeira deve-se ao facto desta normalização tornar as funções ortogonais, o que por sua vez facilita a transformada inversa em termos de rapidez. A segunda vantagem relaciona-se com a compressão de imagens, na qual a transformada normalizada duma imagem tem tendência a ser mais próxima da imagem original, como se pode verificar nas figuras 3 e 4.

Figura 3 e 4

Figura 3 e 4

Para aplicar a normalização aos algoritmos serão precisas as seguintes rotinas:

Procedure DecompositionStep(FIN,SIZE)
For I=1 to SIZE/2
		TEMP [I]  (C [2I-1] + C [2I]) / sqr(2)
		TEMP [SIZE/2+I]  (C [2I-1] + C [2I]) / sqr(2)
	FINTEMP
	Return
      
      Procedure Decomp(FIN,SIZE)
	FIN  FIN/sqr (SIZE)
	While SIZE > 1
		DecompositionStep(FIN,SIZE)
		SIZE  SIZE/2
	Return

Descodificação

O algoritmo de descodificação da Transformada de Haar acaba por ser mais complexo que a codificação. Mas basta apenas fazer o inverso da transformada, ou seja, para chegar a cada conjunto de dois pixels, calcula-se a soma e a subtracção do coeficiente médio com o respectivo coeficiente de detalhe, para o primeiro e segundo pixel respectivamente.

Algoritmo da descodificação em pseudo-código:

Procedure Inverse ()
VEC1  0
For J=0 to length (FIN)
	A1 2J
	A2 2J+1
	If A2 < length (FIN)
		TEMP  FIN [A1]
		FIN [A1]  TEMP + COEF [VEC1]
		FIN [A2]  TEMP – COEF [VEC1]
		VEC1++
	Else Return

Exemplo de aplicação

Dois exemplos distintos para demonstrar o funcionamento das partes de codificação e descodificação da Transformada de Haar.

  • O primeiro exemplo, mais simples, será a codificação e descodificação de uma string de valores numéricos para demonstrar o funcionamento da transformada 1D e para ter a noção dos coeficientes resultantes dos algoritmos acima explicados.
  • O segundo exemplo será uma imagem , em que apenas se vai tentar aplicar a transformada de Haar uma vez para cada componente espacial, horizontal e vertical, de modo a demonstrar o efeito que a transformada tem numa imagem, mostrando assim as zonas de maior visibilidade e os pixels ou blocos de pixels que através de quantificação acabariam por ser descartados, dependendo do algoritmo de quantificação a ser usado. Este exemplo acabará por ser uma aplicação não ‘Standard’ da Transformada de Haar.

O exemplo dois acaba por ser semelhante ao primeiro exemplo, no sentido em que cada pixel irá ser convertido num valor numérico, relativo à sua profundidade de cor, acabando por se tornar numa matriz de valores numéricos.

Para o primeiro exemplo será usada a seguinte matriz:

 [21 13 30 5 19 18 49 7]

No segundo exemplo, será usada uma imagem genérica de dimensões 256×256 pixels e onde será aplicada a transformada apenas uma vez a cada componente espacial, de modo a demonstrar as zonas em que encontram as médias, que são as zonas mais sensíveis ao olho humano, e as zonas dos coeficientes de detalhe. As zonas que se notam mais nos coeficientes de detalhe são as zonas onde existem mudanças bruscas na imagem original (as diferenças vão ser elevadas).

Codificação

Passando a uma explicação mais detalhada do algoritmo de codificação, vai-se analisar ao pormenor a codificação do primeiro algoritmo.

Primeiro são criados dois arrays, cada um com metade do valor do array inicial de entrada na função haar_calc. Depois é iniciado um ciclo For para processar cada valor do array inicial. Dentro do ciclo são calculadas a soma, guardada no primeiro array, e a diferença, guardada no segundo array, de cada grupo de dois valores. Por fim adiciona-se os valores calculados das diferenças a um vector para posteriormente trabalhar com os coeficientes separadamente. Este processo é então, novamente, repetido mas desta vez para o primeiro array criado, o array que contém as médias, e isto mantém-se até haver apenas uma média situada na primeira posição do array das médias.

Array inicial: [21, 13, 30, 5, 19, 18, 49, 7]

Array após primeira iteração: [17, 17.5, 18.5, 28 | 4, 12.5, 0.5, 21]

Array final: [20.25 | -3, -0.25, -4.75, 4, 12.5, 0.5, 21]

Descodificação

No que toca à descodificação, seguindo o exemplo 1 já codificado, o primeiro passo será inverter os coeficientes previamente guardados no vector, pois eles são gerados do vector com o coeficiente maior (maior frequência) para o vector com menor coeficiente (menor frequência). No entanto tanto a transformada inversa como a apresentação dos dados comprimidos precisa dos coeficientes ordenados ao contrário.

Após inverter será necessário converter a dimensão do array final numa potência de dois, no caso de terem sido eliminados alguns valores na quantificação. Inicia-se então um ciclo For para processar os dados todos novamente. Faz-se então a escolha de dois valores com base em potências de dois e calcula-se a soma e a subtracção entre a média e o coeficiente respectivo. Tal como na compressão este processo é feito até ao fim do array, acabando por fim por ter os valores com que se iniciou o exemplo.

Array a descomprimir: [20.25 | -3, -0.25, -4.75, 4, 12.5, 0.5, 21]

Array após primeira iteracção: [17.25, 23.25 | -0.25, -4.75, 4, 12.5, 0.5, 21]

Array final: [21, 13, 30, 5, 19, 18, 49, 7]

Implementação do algoritmo da Transformada de Haar

Função para inverter os coeficientes wavelet:

private void reverseCoef() {
        int size = coef.size();
        Object tmp;

        for (int i = 0, j = size-1; i < j; i++, j--) {
            tmp = coef.elementAt(i);
            coef.setElementAt(coef.elementAt(j), i);
            coef.setElementAt(tmp, j);
        }
     }

public static int power2( byte n)
    {
        int rslt = 0x1 << (n & 0x1f); return rslt; } public static byte log2(int val ) { byte log; for (log = 0; val > 0; log++, val = val >> 1)
        ;
        log--;
        return log;
    }

Estas duas últimas funções, servem de auxiliares na descodificação, para ordenar os arrays dos coeficientes em potências de dois.

Trabalho desenvolvido no âmbito da disciplina de Multimédia II da Licenciatura em Engenharia Informática, lecionada pelo Prof. Doutor Nuno Magalhães Ribeiro da Faculdade de Ciência e Tecnologia da UFP.

Texto da autoria de Ricardo Monteiro (16732) e revisto por Nuno Magalhães Ribeiro.

Site planeado, desenhado, desenvolvido e programado por Daniel Dias Lima Mendes, Diogo Emanuel Lamas e Silva, Nelson José Santos Almeida no âmbito do Projeto de final de Licenciatura realizado na Unidade Curricular de Laboratório de Projeto Integrado sob a orientação técnica do Prof. Doutor Nuno Magalhães Ribeiro.