Aproximações de baixa complexidade para a transformada discreta de Hartley

Abstract

As transformadas discretas ganharam destaque nas últimas décadas com a evolução dos sistemas digitais. A comunidade de processamento de sinais direcionou esforços ao desenvolvimento de algoritmos rápidos capazes de implementar as transformadas de modo mais eficiente do que na forma direta. A vasta pesquisa nessa área tem resultado em algoritmos com complexidade multiplicativa próxima da cota mínima teórica. Assim, as transformadas aproximadas surgiram como um artifício matemático para evitar operações de multiplicação em seu cômputo. A presente dissertação aborda aproximações de baixa complexidade para uma transformada ainda pouco explorada neste sentido, a transformada discreta de Hartley (DHT). Dois métodos de busca baseados na parametrização da matriz da DHT são propostos e implementados. O Método I utiliza a representação matricial da DHT em sua forma não fatorada, enquanto o método II faz uso das fatorações de Winograd e Cooley-Tukey para derivar aproximações já na forma de algoritmos rápidos. As aproximações são obtidas por meio da solução de um problema de otimização que avalia três funções objetivo. Essas funções são métricas de similaridade entre as aproximações e a transformada exata. Duas das funções objetivo são conhecidas na literatura: erro de energia total e desvio de ortogonalidade; e a terceira métrica, denominada erro de involução, é proposta neste trabalho. Os métodos de busca derivam, no total, 44 novas aproximações de comprimento N = 3, 5, 7, 8, 16, 32. Uma aplicação de reconhecimento facial utilizando filtros MACE no domínio de Fourier foi adaptada para o domínio de Hartley. As dezoito aproximações de comprimento N = 32 obtidas foram submetidas ao sistema de verificação facial e comparadas com a transformada da DHT exata. As aproximações apresentaram uma média de taxa de erro entre 0,32% e 0,50%, tendo algumas superado a DHT exata, a qual obteve média de taxa de erro de 0,36%.