Transformada de Hartley
Carla Belarmino
Resumo[]
Este trabalho apresenta a Transforma (Discreta) de Hartley (DHT), com as equações, aplicações que foi desenvolvidas a partir dela. Será desenvolvido sua implementação na linguagem Python e com alguns resultados aplicados em imagens.
Introdução[]
A Transformada Discreta de Hartley (DHT) é uma versão discretizada da transformada integral formulada por Hartley em 1942 e definida por Bracewell em 1983. Tendo como aplicações iniciais o cálculo eficiente da Transformada de Fourier (DFT) e em óptica (interferometria). A transformada de Hartley foi utilizada em diversas aplicações como por exemplo [1]:
- Compressão de imagens biométricas
- Sistemas de comunicação utilizando multiportadora (OFDM) e acesso múltiplo (CDMA).
- Modems ADSL.
Nas próximas subseções serão descritos alguns trabalhos científicos que utilizaram a DHT.
Um algoritmo Bifuncional para Avaliação dos Espectros de Hardamard e Hartley[]
Neste trabalho realizado por Cintra [2] introduz um algoritmo para o calculo das transformadas discretas de Hartley e de Hadamard, realizando sua implementação em hardware utilizando somadores em paralelo [1].
Algoritmo para Criptografia de Voz implementado em Tempo real em processador de sinais[]
No trabalho realizado por Nascimento e Toscano [3], é implementado um sistema de criptografia de voz baseado em permuta pseudo-aleatória de bandas de freqüências no domínio transformado. Optou utilizar a DHT em vez da DFT, pelo fator que a primeira é mais eficiente computacionalmente e com similaridade no que diz respeito às propriedades.
Organização do trabalho[]
Este trabalho está organizado da seguinte forma:
- Seção 3: Apresentação da DHT
- Subseção 3.1: contem o pseudocódigo da DHT
- Seção 4: Será mostrada uma aplicação que utilizada a DHT
- Seção 5: Apresentação dos resultados da aplicação da DHT em varias imagens.
Transformada de Hartley[]
A Transformada Discreta de Hartley mapeia uma seqüência real de comprimento N amostras em uma outra seqüência também real e de comprimento N no domínio das freqüências [Bracewell, 1983 apud Nascimento, 2004]. Analogamente a Transformada Discreta de Fourier que pode ser implementada por meio de algoritmo rápido conhecido como FFT (do inglês, Fast Fourier Transform) a Transformada Discreta de Hartley também pode ser implementada via algoritmo rápido conhecido com FHT (do inglês, Fast Hartley Transform). Como a FFT a FHT é uma ferramenta matemática/computacional para analise de freqüências de sinais, porém é uma operação linear. A FHT possui um esforço computacional proporcional a NlogN como a FFT [Nascimento, 1990 apud Nascimento, 2004], porém, envolve somente operações reais.
A DHT relaciona dois vetores 
e é definido por [Bracewell, 1986 apud Sobral Cintra, 2002]:
onde 
. Está formula pode ser escrita também na forma de matriz:
onde HN é a matriz de Hartley, cujos elementos hk,i são da forma 
.
Implementação[]
A implementação da DHT foi realizada de duas formas, de acordo com as duas formulas descrita na seção 3. A primeira foi realizada pelo método linear, ou seja, transformando a matriz da imagem em um vetor, e em cima deste vetor aplicando a formula 1. O segundo método de implementação foi pela formula descrita em forma de matriz, ou seja, foi calculado a matriz HN e em seguida multiplicada pela imagem, resultando na imagem transformada.
#Implementação por vetores
def hartley(f):
from Numeric import *
from ia636 import *
#Primeiro transforma-se a matrix(imagem f) em um vetor
f_v = ravel(f)
#Declara-se uma variavel N com numero total de posicoes do vetor
N = f_v.shape[0]
#Cria-se o vetor V da Transformada de Hartley
V = zeros(f_v.shape)
#Variveis que auxiliam no calculo de V
v_soma = 0.0
cas = 0.0
#Para cada posição de V calcula-se o somatorio de f_v[i]
#multiplicando cada f_v[i] pelo coseno e seno de ((2*pi*k*i)/N)
Para k=0 até N: #armazena no vetor V
Para i até N: #somatoria de toda imagem
cas = cos((2*pi*k*i)/N) + sin((2*pi*k*i)/N)
v_soma = v_soma + (f_v[i] * cas)
V[k] = v_soma
#retorna o vetor V, com o resultado da transformada
return V
#Implementação por matrizes
def hartley_m(f):
from Numeric import *
from ia636 import *
#Declaração de N sendo como total de pixels da imagem
N = f.shape[0]*f.shape[1]
#Declarão de uma matrix H do tamanho da imagem
H = zeros(f.shape)
#Declaração de uma matrix V igual a H
V = H
#Para cada H[k,i] calcula-se cos((2*pi*k*i)/N) + sin((2*pi*k*i)/N)
Para k=0 até f.shape[0]:
Para i=0 até f.shape[1]:
H[k,i] = cos((2*pi*k*i)/N) + sin((2*pi*k*i)/N)
#Multiplica-se a matrix H com a imagem f
V = f * H
#Retorna a imagem resultade da transformada
return V
Aplicação[]
Ilustração de ao menos uma aplicação que utiliza esta transformada...
Resultados[]
A Transformada de Hartley foi aplicada em duas figuras, ou seja, na primeira figura foi aplicado em forma de vetores e na segunda em forma de matrizes.
DHT vetorial[]
Na figura abaixo foi aplicado a DHT vetorial, como pode ser visto, no primeiro quadro tem-se a imagem original, no segundo tem-se a DHT da imagem.
DHT matricial[]
Na figura abaixo foi aplicado a DHT vetorial, como pode ser visto, no primeiro quadro tem-se a imagem original, no segundo tem-se a matriz de Hartley (H) e no ultimo tem-se o resultado da multiplicação da imagem original f pela matriz H.
Conclusões[]
A Transformada Discreta de Hartley é semelhante à Transformada Discreta de Fourier, ou seja, uma ferramenta matemática/computacional para analisar as freqüências de sinais. Além disso, com relação os pontos positivos/negativos deste trabalho, a implementação poderia ser melhor desenvolvida, pelo fator do tempo de processamento (levando em consideração o tamanho da imagem). Os resultados encontrados com a implementação foram satisfatórios.
Referências[]
[1] Bracewell, R.N.; The Hartley Transform, Oxford, 1986.
[2] Bracewell, R.N.; Discrete Hartley Transform. Opt. Amer, vol 73, no. 12, pp.1832-1835, Dec. 1983.
[3] Nascimento, F.A. O.; Toscano, R. G. Algoritmo para Criptografia de Voz Implementado em Tempo Real em Processador de Sinais. IV Congresso Brasileiro de Computação – CBComp 2004.
[4] Nascimento, F.A. & Malvar; Sarmento H. Computer Program for DHT - Appendice A.6 of Discrete Cossine Transform – Algorithms and Applications, R. K. Rao & P. Yio, Academic Press, 1990, pp. 417-421.
[5] Sobral Cintra, R. J. de; Oliveira, H.M. de; Campello de Souza, R.M.; Um Algoritmo Bifuncional dos Espectros de Hadamard e Hartley. Grupo de Pesquisa em Comunicações (CODEC), Universidade Federal de Pernambuco, Recife, 2002.
[6] Sobral Cintra, R. J. de; Oliveira, H.M. de; Campello de Souza, R.M.; Kauffman, A. N. A Transformada Aritmética de Hartley. Grupo de Pesquisa em Comunicações (CODEC), Universidade Federal de Pernambuco, Recife, 2000.
Anexo[]
#Implementação vetorial
def hartley(f):
'''
Entrada:
f -> imagem em niveis de cinza
Saida:
g -> DHT da imagem
'''
from Numeric import *
from ia636 import *
#transformando a matrix(imagem f) em um vetor
f_v = ravel(f)
#qtde de linhas e colunas da imagem f
linhas = f.shape[0]
colunas = f.shape[0]
#numero total de posicoes do vetor
N = f_v.shape[0]
#criação do vetor V da Transformada de Hartley
V = zeros(f_v.shape)
v_soma = 0.0
cas = 0.0
#calculo de cada posição de V com relação f_vetor
for k in range(N): #armazena no vetor V
for i in range(N): #somatoria de toda imagem
cas = cos((2*pi*k*i)/N) + sin((2*pi*k*i)/N)
v_soma = v_soma + (f_v[i] * cas)
V[k] = v_soma
return V
#Implementação matricial
def hartley_m(f):
'''
Entrada:
f -> imagem em niveis de cinza
Saida:
g -> DHT da imagem
'''
from Numeric import *
from ia636 import *
N = f.shape[0]*f.shape[1]
H = zeros(f.shape)
V = H
for k in range(f.shape[0]): #linhas
for i in range(f.shape[1]): #colunas
H[k,i] = cos((2*pi*k*i)/N) + sin((2*pi*k*i)/N)
iashow(H)
V = f * H-1
return V