Uma aproximação escalada para DCT de comprimento 16

Abstract

A transformada discreta do cosseno (DCT, discrete cosine transform) é uma ferramenta central em processamento digital de imagens devido a sua capacidade de descorrelacionar dados modelados por processos markovianos de tipo I, como é o caso de imagens naturais. Algoritmos rápidos reduzem este custo computacional de O(N²) para O(N logN). Entretanto, em contextos de extrema escassez de recursos energéticos e computacionais, como em redes baseadas em Internet of Things, os algoritmos rápidos tradicionais não reduzem a complexidade suficientemente. Uma abordagem para redução significativa da complexidade computacional é fornecida por meio de aproximações matriciais. Uma aproximação matricial de baixa complexidade é uma matriz cujos elementos são multiplicandos triviais, e.g., elementos do conjunto {0,±1,±2}. Assim, o problema de aproximar a matriz de transformação da DCT consiste em obter uma matriz de baixa complexidade computacional que preserve a propriedade de descorrelação de dados. Trata-se de um problema de otimização discreta sujeito a restrições sobre um espaço de busca finito, mas extremamente vasto. Neste trabalho, adotamos uma variação da abordagem descrita anteriormente. Em particular, a restrição de ortogonalidade é relaxada e a etapa de permutação de linhas é substituída pela ordem natural das linhas das matriz. O ângulo entre vetores é mantido como distância entre linhas exatas e linhas aproximadas. Adicionalmente, introduzimos uma novidade ao método descrito. Para cada linha, são separadas as linhas-candidatas mais próximas da linha ótima num erro máximo de 0.1 rad, resultando em matrizes candidatas. Foram adotados o erro médio quadrático (MSE), como função objetiva a ser minimizada; e, secundariamente, a eficiência de transformação (η), a ser maximizada.