Algorithms for transform selection in multiple-transform video compression

With a proper transform, an image or motion-compensated residual can be represented quite accurately with a small fraction of the transform coefficients. This is referred to as the energy compaction property. When multiple transforms are used, selecting the best transform for each block that leads to the best energy compaction is difficult. In this paper, we develop two algorithms to solve this problem. The first algorithm, which is computationally simple, leads to a locally optimal solution. The second algorithm, which is more computationally intensive, gives a globally optimal solution. We discuss the algorithms and their performance. Two-dimensional discrete cosine transform (2D-DCT) and direction-adaptive one-dimensional discrete cosine transforms (1D-DCTs) are used to evaluate the performance of our algorithms. Results obtained are consistent with their coding performance. As an application example of this paper, we apply our algorithm to evaluate the performance of a potential video compression system based on a very large number of transforms.