Aproximações de baixa complexidade para transformadas discretas multidimensionais

Abstract

A presente tese de doutorado aborda aproximações de baixa complexidade computacional para transformadas discretas multidimensionais com aplicações em diferentes contextos. Por proporcionarem algoritmos livres de multiplicação, aproximações para transformadas discretas vêm sendo objeto de pesquisa nos últimos anos. Neste trabalho, é objetivado propor: aproximações para a 2D DTT baseadas na abordagem pruning (aproximações podadas), em que coeficientes de alta frequência são descartados de modo a reduzir o custo computacional, com aplicações em padrões de imagem e vídeo; aproximações multidimensionais para a DCT baseadas no formalismo de tensores com aplicações em codificação tridimensional de vídeo e rastreamento visual de objetos; e aproximações para a DHT e 3D DHT visando codificação de imagens médicas. Os métodos aproximados podados propostos para a 2D DTT mostraram reduções de complexidade entre 50% e 80% em relação ao método usual, com uma perda de desempenho em compressão tipo JPEG na faixa de 3% a 6%, em média. As versões aproximadas para a 3D DCT apresentaram 100% de redução de complexidade multiplicativa e entre 17% e 52% de redução de complexidade aditiva a uma perda de desempenho em compressão de vídeo 3D menor que 7%. Por sua vez, as aproximações propostas para a 3D DHT apresentaram 100% de redução de complexidade multiplicativa, embora custos aditivos iguais ou superiores ao dos métodos exatos, com redução de desempenho em compressão de imagens médicas menor que 2%. De forma geral, as simulações de compressão de imagem e vídeo e a análise de complexidade computacional sugerem que os métodos propostos apresentam um trade-off favorável entre custo computacional e desempenho de compressão, proporcionando um leque de ferramentas que atende à crescente demanda por sistemas com restritos custo computacional e autonomia energética.