masterThesis
Projeto e implementação de transformadas discretas de baixa complexidade para codificação de imagens e vídeos
Autor
OLIVEIRA, Raíza dos Santos
Institución
Resumen
O custo computacional da implementação de transformadas discretas pode ser significativo quando se considera a enorme quantidade de dados que as tecnologias contemporâneas exigem e/ou a demanda por dispositivos de baixa potência. O uso de algoritmos rápidos reduz os custos aritméticos de computação das transformadas e o consumo de energia sem eliminar a necessidade por aritmética em ponto flutuante. Neste sentido, as aproximações matriciais de baixa complexidade são uma alternativa para o cômputo das transformadas. Neste trabalho, é introduzido um método baseado em uma heurística gulosa e na distância angular entre vetores para obtenção de aproximações matriciais. Introduzimos metodologias para a aplicação efetiva do método proposto para aproximar as matrizes das transformadas discretas de Fourier, Hartley e do cosseno (DCT). O método é utilizado para obtenção de novas aproximações para a DCT de comprimento 8. Treze novas aproximações foram obtidas, das quais cinco apresentam resultados melhores que os da DCT em termos do índice de similaridade estrutural em experimentos de compressão de imagens. Uma das aproximações obtidas foi selecionada para análises mais aprofundadas. Aproximações de comprimentos 16 e 32 para as simulações de vídeo foram obtidas escalando, por meio do algoritmo de Jridi-Alfalou-Meher, a aproximação de comprimento 8 selecionada. O codec de vídeo utilizando as aproximações propostas apresentou resultados muito próximos aos do codec original, tendo uma perda máxima de 0.55dB nos testes realizados. Para a aproximação selecionada, foi também realizada a implementação em FPGA. Quando comparada à implementação de outras aproximações da literatura, a implementação da transformada proposta mostrou capacidade de operar numa frequência até 19% maior. FACEPE The computational cost of implementing discrete transforms can be significant when considering the massive amount of data that contemporary technologies require and/or the demand for low–power devices. The use of fast algorithms substantially reduces arithmetic costs without eliminating the need of floating-point arithmetic. In this sense, low-complexity matrix approximations appear as an alternative way to compute these transforms. In this work, a greedy algorithm based on the angular distance between vectors for obtaining low-complexity approximations from a given matrix is proposed. We introduce methodologies for the effective application of the proposed method to approximate the discrete Fourier, Hartley, and cosine (DCT) transforms. The method is employed to derive new approximations for the 8-point DCT. Thirteen new approximations for the 8-point DCT were obtained; five of them outperformed the DCT in terms of the structural similarity index on the image compression experiments. One of the proposed approximations was chosen for further analysis. Approximations for the 16- and 32-point DCT were derived by means of the Jridi–Alfalou–Meher scaling method based on the previously selected 8-point approximation. Such scaled matrices were submitted to video experiments. The encoded video resulted from the approximate transforms performed very closely to the standard video encoding: the maximum loss was 0.55dB in video compression experiments. The selected approximation was also implemented on a FPGA. When compared to implementations of other two approximations in literature, the proposed method was shown to be able to operate at a 19% higher frequency.