Globally Optimal Algorithms for Transform Selection in Multiple-Transform Signal Compression

Recent studies have shown that there may be a significant improvement in thecompression of a signal when multiple-transforms are used to exploit local characteristics [1]. By choosing an appropriate transform from a set of transforms, we can have a significant encoding improvement. In this paper, our objective is to find which transform is optimal for each block of a given signal, and to determine how many coefficients we should allocate in each block, from an energy compaction perspective, as defined in [2]. Two algorithms were proposed in [2] to solve this problem. The first algorithm, called Algorithm A, is an iterative method, that converges to a locally optimal solution. The second algorithm, called Algorithm B, first considers an alternate metric based on rate distortion and uses convex optimization techniques.We propose two new methods to solve this problem [3]. The first method, called Algorithm C, uses thresholding to solve the rate-distortion optimization problem. We threshold the magnitude-squared of the transform coecients by the rate-distortion parameter for all transforms, and choose the best transform. The second method, called Algorithm D, uses dynamic programming to find the best transform and coefficient allocation for the current block based on that of all the previous blocks. This method solves the problem of finding the best transform and coecient allocation in terms of energy compaction. In comparing these methods, Algorithm A is the fastest, although only locally optimal. Algorithm C is faster than Algorithm B. Both Algorithm B and Algorithm C solve only the rate-distortion problem. Algorithm D solves the original energy compaction problem, but is the slowest among the four methods.