Multiscale recurrent pattern matching algorithms for image and video coding

Abstract

In this thesis we investigate new and efficient algorithms for image and video compression, based on a recently proposed generic lossy data compression method that uses the approximate pattern matching paradigm, called multidimensional multidimensional parser (MMP). MMP presents an excellent performance level when compared with traditional pattern matching algorithms for lossy image compression applications. When compared with the state-of-the-art transform-based methods, MMP is able to achieve significant gains for the compression of non-smooth images, like text and compound images, but has a compromising performance deficit for the compression of smooth, natural images. The techniques developed in this thesis overcome this limitation, improving the performance of MMP-based smooth image coding up to a state-of-the-art level, while maintaining its relevant performance gains for non-smooth image compression. The performance gains resulted from the use of adaptive predictive schemes, together with new dictionary design strategies. Experimental results show consistent PSNR performance gains over the original MMP algorithm, for all image types and compression ratios. When compared with the state-of-the-art, transform-based encoders, the proposed methods achieve relevant gains (up to 6 dB) for non-smooth images and a comparable performance for smooth images. A new MMP-based video compression algorithms was also investigated. The proposed method, referred to as MMP- Video, combines the hybrid video coding model with optimised multiscale adaptive pattern matching algorithms, in order to exploit the particular features of video signals. Experimental results show a general performance above the levels achieved by the current state-of-the-art H.264/AVC standard. These results show that, in spite of its higher computational complexity, the MMP paradigm can be regarded as a viable alternative to the traditional transform-quantisation-entropy coding-based methods.

O tema principal desta tese é o estudo de algoritmos eficientes de compressão de imagens e vídeo digitais baseados no paradigma da correspondência aproximada de padrões. Os métodos desenvolvidos são baseados num esquema de compressão recentemente proposto, denominado MMP (do original multidimensional multidimensional parser). Quando aplicado à compressão com perdas de imagens, o algoritmo MMP tem um desempenho acima do dos melhores codificadores baseados em aproximação de padrões. Quando comparado com os esquemas baseados em transformadas, o MMP consegue ganhos consideráveis para a compressão de imagens não suaves, mas apresenta perdas relevantes na compressão de imagens naturais. As técnicas propostas eliminam estas perdas, elevando o desempenho do algoritmo MMP para a compressão de imagens suaves para um nível semelhante ao dos melhores codificadores baseados em transformadas, ao mesmo tempo que mantêm, ou melhoram, os ganhos observados para as imagens não suaves. Estes ganhos resultam da utilização de métodos de codificação preditiva, utilizados em conjunção com novos esquemas associados ao processo de actualização do dicionário. Testes experimentais demonstram ganhos consideráveis na qualidade objectiva das imagens, quando comparamos as técnicas propostas com o algoritmo MMP original. Esquemas eficientes de compressão de sinais vídeo baseados no algoritmo MMP foram também investigados. O método proposto, denominado MMP-Video, combina a arquitectura híbrida de codificação de vídeo com um codificador baseado em MMP, optimizado de modo a explorar de uma forma eficiente as características dos sinais de vídeo digital. Testes experimentais revelam valores de desempenho, em termos de medidas de qualidade vs. taxa de compressão, acima dos atingidos pela mais eficiente norma de compressão de vídeo, a norma H.264/AVC. Os resultados apresentados demonstram a viabilidade do paradigma proposto, como alternativa aos esquemas tradicionais de compressão de imagens e vídeo, apesar do aumento da complexidade computacional verificado.