LAPIS/Disciplinas/Processamento de Imagens:TransfWignerVille

Implementação da Transformada de Hadamard

Felipe Augusto Rieck

Resumo

Este trabalho visa apresentar um estudo sobre a transformada de Hadamard e especificar um modelo de implemtenação para a linguagem Python. A implementação apresentará também o algorítmo para a geração das matrizes de Hadamard, muito úteis em diversas utilizações desta transformada.

Introdução

Também conhecida como transformada de Walsh-Hadamard, transformada de Walsh ou transformada de Walsh-Fourier, a transformada de Hadamard é uma classe genérica derivada das Transformadas Rápidas de Fourier (FFT). Segundo [Transformadas 3], esta transformada fornece uma maneira de medir o "bitwise" não linerar existente entre funções cujo domínio é uma representação de bits.

Criada pelo matemático francês Jacques Hadamard, esta transformada executa uma operação ortogonal, simetrica, involutária e linear em números reais de $2^m$ (ou em números complexos, embora as matrizes por ela geradas sejam puramente reais).

Esta transformada é comumente utilizada para:

• Compressão de imagens;
• Processamento de sinais;
• Entre outros.

Além dessas aplicações, a transformada de Hadamard pode ser utilizada para gerar números aleatórios pertencentes ao conjunto da distribuição Gaussiana. Além disso, esta transformada pode ser utilizada através de uma série de permutações randômicas a fim de causar ruido Gaussiano nos dados [Hadamard Transform 4].

Vantagens

Na transformada de Hadamard, a transformada e a sua inversa são inerentemente idênticas, facilitando assim a implementação de um algorítmo que retorne à imagem original. Assim, segundo [2], um algorítmo que calcule $H(u,v)$ (a transformada de Hadamard de uma imagem) é o mesmo que pode ser utilizado para calcular $f(x, y)$ (a imagem originante de uma transformada de Hadamard).

Além disso, a transformada de Hadamard é muito simples de computar já que necessita apenas de formulações matemáticas imples, como adição e subtração, e depois da divisão por N, que freqüentemente é uma potência de 2.

Desvantagens

Quando aplicada ao processamento de sinais, faz-se necessário ordenar a matriz de transformação utilizada pela transformada de Hadamard, pois esta desordenação pode acarretar em problemas na análise destes sinais.

Organização do trabalho

Este trabalho está organizado da seguinte forma: Na seção 3 é apresentada a transformada através de sua formulação matemática. Na seção 4 é abordada a aplicação desta transformada, e na seguite seção são verificados os resultados obtidos aravés da computação da transformada de Hadamar. Em seguida, na seção 6 é concluido este trabalho.

Transformada de Hadamard

A diferença da transformada de Fourier para a transformada de Hadamard, é a de que a primeira utiliza a trigonometria, enquanto a segunda consiste em uma série de funções básicas cujos valores são +1 ou -1.

A transformada de Hadamard, $H(u,v)$, de uma imagem $f(x, y)$ de dimensões $N x N$ onde $N=2^k$ é dada pela fórmula:

$H(u,v) = \frac{1}{N}\sum^{N-1}_{x=0}\sum^{N-1}_{y=0} f(x,y)(-1)^{\sum^{i=0}_{k-1}b_i(x)b_i(u)+b_i(y)b_i(v)}$

onde $u=0,1,...,N-1$, $v=0,1,...,N-1$ e $bj(z)$ é o j-ézimo bit da representação binária de z, ou seja, quando $z=45$, sua representação binária é $101101$ e o quinto número é 1 ($b_5(45) = 1$).

Como citado anteriormente a transformada inversa é exatamente igual a transformada normal, apenas trocando de lugar os itens $H(u,v)$ com $f(x, y)$, vindo a ficar:

$f(x,y) = \frac{1}{N}\sum^{N-1}_{x=0}\sum^{N-1}_{y=0} H(u,v)(-1)^{\sum^{i=0}_{k-1}b_i(x)b_i(u)+b_i(y)b_i(v)}$.

Os núcleos da transformada de Hadamard são simétricos divisíveis (podem ser separados), e são definidos por:

$H(u,v) = \sum^{N-1}_{y=0}(\sum^{N-1}_{x=0} g(x,u)f(x,y))g(y,v)$

onde $g(z,w) = \frac{1}{\sqrt{N}}(-1)^{\sum^{k-1}_{i=0}b_i(z)b_i(w)}$. Dessa forma, para se calcular a transformada de Hadamard bidimensional pode-se calcular duas verzes consecutivas a transformada de Hadamard unidimensional dada por:

$H(u,v) = \frac{1}{N}\sum^{N-1}_{x=0}f(x)(-1)^{\sum^{i=0}_{k-1}b_i(x)b_i(u)}$.

Matriz de transformação

Além do cálculo direto citado acima, a transformada de Hadamard pode ser obtida através do cálculo de sua matriz de transformação.

A menor matriz de transformação é a matriz $H_2$, dada por:

$H_2 = \begin{pmatrix}\begin{array}{rr} 1 & 1 \\ 1 & -1 \end{array}\end{pmatrix}$.

Dessa forma, através de métodos recursivos é possivel determinar uma matriz de transformação $H_{2N}$, para $N=2^n$ (valores múltiplos de 2). Uma matriz $H_4$ por exemplo é dada por:

$H_4 = \begin{pmatrix}\begin{array}{rr} H_2 & H_2 \\ H_2 & -H_2 \end{array}\end{pmatrix}$

Ou seja, de forma genérica, uma matriz $H_{2N}$ é definida por:

$H_{2N} = \begin{pmatrix}\begin{array}{rr} H_{N/2} & H_{N/2} \\ H_{N/2} & -H_{N/2} \end{array}\end{pmatrix}$.

Assim, através desta matriz (a), aplica-se a fórmula:

$T = AFA$

e obtém-se a transformada de Hadamard (T) da imagem F.

Implementação

Neste trabalho será mostrado o cálculo de dois arrays de valores, um correspondente à própria transformada e outro correspondente à matriz de Hadamard entretanto somente será mostrada a implementação para transformada de Hadamard sem utilização das matrizes. Para a criação desta matriz, como visto anteriormente, se fa necessário utilizar uma função recursiva que calcula as matrizes até chegar à menor matriz possível: $H_2$. Este cálculo é feito da seguinte forma:

def geraMatrizHadamard(N):
    ret = ones((N,N))
    if N == 2:
        ret[0][0] = 1
        ret[0][1] = 1
        ret[1][0] = 1
        ret[1][1] = -1
        return ret

    aux = geraMatrizHadamard(N/2)

    dx = 0
    dy = 0
    
    for x in range(N):
        for y in range(N):
            if x >= N-N/2 and y >= N-N/2:
                ret[x][y] = -aux[x%(N/2)][y%(N/2)]
            else:
                ret[x][y] = aux[x%(N/2)][y%(N/2)]
            
    return ret

Esta função gera a matriz de forma recursiva tendo como base de entrada seu tamanho.

Para a implementação da transformada de Hadamard é necessário a implementação de uma função que calcule o j-ézimo bit de um valor fornecido, feito por:

def calculaB(i,z):

    resp = 0
    a = z
    b = 2

    for j in range(i+1):
        if a >= b:
            resp = a%b
            a = int(a/b)
        else:
            return a

    return resp

onde:

i: é o j-ézimo bit; e,

z: é o valor que será transformado em binário.

Assim fica possível definir a função que calcula a transformada com base nas funções auxiliares acima e as fórmulas citadas acima:

def Hadamard(f):
    if f.shape[0] != f.shape[1]:
        if f.shape[0] < f.shape[1]:
            f = f[0:f.shape[0]][0:f.shape[0]]
        else:
            f = f[0:f.shape[1]][0:f.shape[1]]

    N = f.shape[0]

    H = zeros((N,N))

    for u in range(N):
        for v in range(N):
            soma = 0.0
            for x in range(N):
                for y in range(N):
                    somaExp = 0.0
                    for i in range(log2(N)):
                        somaExp = somaExp + (calculaB(i,x)*calculaB(i,u) + calculaB(i,y)*calculaB(i,v))
                    soma = soma + f[x][y]*(pow(-1,somaExp))
            H[u][v] = soma
    return H

Aplicação

As aplicações são inúmeras especialmente as voltadas para o processamento de sinais digitais, entre eles o som. Para esta pesquisa não foram encontradas aplicações voltadas diretamente ao processamento de imagens, exceto para compactação de images. Entretanto é interessante mostrar os resultados obtidos após a aplicação desta transformada.

Resultados

Toma-se como exemplo a seguinte imagem:

Após a aplicação da transformada, conforme citado acima, a imagem resultante fica:

Entretanto, para melhor visualização é feita a normalização logarítmica, obtendo, finalmente, a seguinte imagem:

Conclusões

A transformada de Hadamard se mostrou como uma ótima opção para ser aplicada como transformada (inclusive como possível substituta da transformada de Fourier). Sua simplicidade torna-a de fácil implementação inclusive em sistemas embarcados, uma vez que utiliza formulamentos matemáticos simples, como adição e multiplicação de valores. Entretanto, seu nível computacional avançado (excesso de for's) foi um dos grandes fatores que dificultaram a implementação desta em linguagens iunterpretadas, como o Python.

Referências

Coloque todas as referências citadas no texto...

[1] Guia de edição/formatação

[2] GONZALES, R. C., WOODS, R. E. Processamento de Imagens Digitais, Edgard Blücher, São Paulo SP.

[3] Transformadas (Núcleo de Processamento Digitial de Imagens)

[4] Hadamard Transform

Anexo

from ia636 import *
from Numeric import *

def geraMatrizHadamard(N):
    ret = ones((N,N))
    if N == 2:
        ret[0][0] = 1
        ret[0][1] = 1
        ret[1][0] = 1
        ret[1][1] = -1
        return ret

    aux = geraMatrizHadamard(N/2)

    dx = 0
    dy = 0
    
    for x in range(N):
        for y in range(N):
            if x >= N-N/2 and y >= N-N/2:
                ret[x][y] = -aux[x%(N/2)][y%(N/2)]
            else:
                ret[x][y] = aux[x%(N/2)][y%(N/2)]
            
    return ret

def numeroBits(z):
    resp = 1
    a = z
    b = 2

    while(1):
        if a >= b:
            resp = resp+1
            a = int(a/b)
        else:
            return resp 

    return resp

def calculaB(i,z):

    resp = 0
    a = z
    b = 2

    for j in range(i+1):
        if a >= b:
            resp = a%b
            a = int(a/b)
        else:
            return a

    return resp

def log2(x):
    valor = x
    soma = 0
    while 1 != valor:
        valor = valor / 2.0
        soma = soma + 1
    return soma

def Hadamard(f):
    if f.shape[0] != f.shape[1]:
        if f.shape[0] < f.shape[1]:
            f = f[0:f.shape[0]][0:f.shape[0]]
        else:
            f = f[0:f.shape[1]][0:f.shape[1]]

    N = f.shape[0]

    H = zeros((N,N))

    for u in range(N):
        for v in range(N):
            soma = 0.0
            for x in range(N):
                for y in range(N):
                    somaExp = 0.0
                    for i in range(log2(N)):
                        somaExp = somaExp + (calculaB(i,x)*calculaB(i,u) + calculaB(i,y)*calculaB(i,v))
                    soma = soma + f[x][y]*(pow(-1,somaExp))
            H[u][v] = soma
    return H