Forward adaptive transform coding of images requires a codebook of transform matrices from which the best transform can be chosen for each macroblock. Codebook construction is a problem of designing a quantizer for Karhunen-Lóeve transform (KLT) matrices estimated from sample image blocks. We present a novel method for KLT matrix quantization based on a finite-lattice non-causal homogeneous Gauss-Markov random field (GMRF) model with asymmetric Neumann boundary conditions for blocks in natural images. The matrix quantization problem is solved in the GMRF parameter space, simplifying the harder problem of quantizing a large matrix subject to an orthonormality constraint to a low-dimensional vector quantization problem. Typically used GMRF parameter estimation methods such as maximum-likelihood (ML) do not necessarily maximize the coding performance of the resulting transform matrices. To this end we propose a method for GMRF parameter estimation from sample image data, which maximizes the high-rate transform coding gain. We also investigate the application of GMRF-based transforms to variable block-size adaptive transform coding.

This paper proposes a novel data-driven approach to designing orthonormal transform matrix codebooks for adaptive transform coding of any non-stationary vector processes which can be considered locally stationary. Our algorithm, which belongs to the class of block-coordinate descent algorithms, relies on simple probability models such as Gaussian or Laplacian for transform coefficients to directly minimize with respect to the orthonormal transform matrix the mean square error (MSE) of scalar quantization and entropy coding of transform coefficients. A difficulty commonly encountered in such minimization problems is imposing the orthonormality constraint on the matrix solution. We get around this difficulty by mapping the constrained problem in Euclidean space to an unconstrained problem on the Stiefel manifold and leveraging known algorithms for unconstrained optimization on manifolds. While the basic design algorithm directly applies to non-separable transforms, an extension to separable transforms is also proposed. We present experimental results showing that adaptive coding with our transform codebook designs outperform the commonly used discrete cosine transform (DCT) in many regions of natural images and motion-compensated prediction error images of video frames. According to these results, the proposed codebook designs slightly outperform those found by a common alternative approach, the sparsity-based optimization.