Forward adaptive transform coding requires a codebook of transform matrices from which the best transform can be chosen for each macroblock in an image. Codebook construction involves designing a vector quantizer for a sample set of KarhunenLoeve transform (KLT) matrices. While several approaches to designing such matrix codebooks have been proposed in previous work [1] , [2] , these non-parametric methods carry out matrix quantization in very high dimensional spaces which can suffer from the curse of dimensionality. Furthermore, the resulting transform matrices are not scalable - if multiple transform block sizes are to be used, such as in video compression, a separate matrix codebook must be designed for each block size.

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 for adaptive transform coding of still images and video inter-frame prediction residuals, comparing the transforms designed using the proposed method and a number of other content-adaptive transforms recently reported in the literature.

We present a novel algorithm for designing a transform codebook for adaptive transform coding a non-stationary source, where the codebook contains a set of or-thonormal transform matrices. The non-stationary source is modeled by a block-wise (locally) stationary process so that all vectors in a given block can be coded using a single transform-matrix chosen from the codebook. The transform-matrix codebook is designed such that the mean-square error (MSE) of coding locally stationary blocks, averaged over the ensemble of blocks (AMSE) is minimized. First, a sequence of training vectors from the non-stationary source (such as blocks of pixels extracted from images) is segmented into locally stationary blocks of vectors. Our design algorithm starts with an initial codebook and iteratively updates the codebook for the training set, similar to the well-known generalized Lloyd algorithm for vector quantizer design. Each iteration consists of two steps: 1) the training set is partitioned into subsets by encoding the training set using the current transform codebook, and 2) the code-book is updated by computing a centroid transform-matrix for each subset. A major difference compared to the standard Lloyd algorithm however is the requirement to enforce an orthonormality constraint on the matrices in the codebook during the computation of centroids. This is accomplished by mapping the constrained problem in Euclidean space to an unconstrained problem on the Stiefel manifold. Gradient-descent on the Stiefel manifold is then used to compute the centroids. Essential to the implementation of manifold gradient-descent is an expression for the AMSE which is differentiable with respect to the transform matrix. Towards this end, we present two expressions whose matrix derivatives can be analytically obtained: 1) an approximate high-rate expression assuming Gaussian distributed source vectors, and 2) an exact finite-rate expression assuming Laplace distributed transform coefficients.