Image Coding with Data-driven Fast Transforms Based on Approximate Givens Factorizations

In image compression, adaptive transform coding with optimal linear transforms computed from data being coded has been shown to outperform the widely used two-dimensional discrete cosine transform (2D-DCT). However, unlike the 2D-DCT for which fast computation algorithms exist, data-driven transforms are random matrices with no particular structure that can be exploited for fast computations. We present an approach to low-complexity data-driven image coding using structured orthonormal transform matrices constructed from approximate Givens factorizations optimized for transform coding. These Givens factorization-based fast transforms (GFFTs) are optimized by a tree-search algorithm on the orthonormal matrix manifold to minimize the mean square error of high-rate transform coding. Experimental results obtained with an adaptation of the baseline JPEG algorithm are presented which show that, for many images, the GFFTs outperform the 2D-DCT at comparable or lower computational complexity, with peak signal-to-noise ratio (PSNR) improvements as high as 6 dB in some cases.