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.

Recent research indicates that data-driven transforms can outperform the widely used separable two-dimensional discrete cosine transform (2D-DCT) in applications such as video coding. However, unlike the 2D-DCT, data-driven transforms are random matrices with no structure and do not lend themselves to fast computations. In this paper, we investigate a new approach to construct low-complexity data-driven transforms by exploiting a connection between the Givens rotation matrices and coordinate descent on the orthonormal matrix manifold. We propose a multi-path coordinate descent algorithm which is observed to produce better transform matrices than the simple coordinate descent. Our experiments with many images showed that the proposed algorithm can be used to design fast data-driven transforms which achieve a higher coding gain than the 2D-DCT in some image blocks.

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.

Summary form only given. Channel optimized vector quantization (COVQ) has received considerable attention as an approach to joint source-channel coding. COVQ for hidden Markov channels was studied, with application in wireless communication over fading channels. The optimal VQ decoding was considered for finite state channels when the channel state is not explicitly observed at the receiver. A hidden Markov model (HMM) with a continuous observation space is constructed for the channel by assuming both channel input and channel state are first-order Markov process. A recursive-decoding algorithm is derived for computing the minimum mean square error (MMSE) optimal estimate for the source vector, based on the observed channel output sequence. In simulation experiments, the performance of a communications system based on the proposed quantizer is investigated for a Gauss-Markov signal source and a frequency non-selective Rayleigh fading channel. The results indicate that for fading channels, proposed soft-decoding based COVQ can results in a substantial improvement of performance over detection based COVQ.