Fandom

Students

LAPIS/Disciplinas/Processamento de Imagens:TransfWignerVille

< 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.

Implementação da Transformada de Hadamard

Felipe Augusto Rieck


Resumo Edit

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 Edit

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 Edit

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 Edit

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 Edit

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 HadamardEdit

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 Edit

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 Edit

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 Edit

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 Edit

Toma-se como exemplo a seguinte imagem:

Original

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

Transf

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

LogTransf

Conclusões Edit

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 Edit

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 Edit

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

Also on Fandom

Random Wiki