Fast multiplierless approximations of the DCT with the lifting scheme

We present the design, implementation, and application of several families of fast multiplierless approximations of the discrete cosine transform (DCT) with the lifting scheme called the binDCT. These binDCT families are derived from Chen's (1977) and Loeffler's (1989) plane rotation-based factorizations of the DCT matrix, respectively, and the design approach can also be applied to a DCT of arbitrary size. Two design approaches are presented. In the first method, an optimization program is defined, and the multiplierless transform is obtained by approximating its solution with dyadic values. In the second method, a general lifting-based scaled DCT structure is obtained, and the analytical values of all lifting parameters are derived, enabling dyadic approximations with different accuracies. Therefore, the binDCT can be tuned to cover the gap between the Walsh-Hadamard transform and the DCT. The corresponding two-dimensional (2-D) binDCT allows a 16-bit implementation, enables lossless compression, and maintains satisfactory compatibility with the floating-point DCT. The performance of the binDCT in JPEG, H.263+, and lossless compression is also demonstrated.

I. Introduction

The discrete cosine transform (DCT) [1], [2] is a robust approximation of the optimal Karhunen-Loève transform (KLT) for a first-order Markov source with large correlation coefficient. It has satisfactory performance in terms of energy compaction capability, and many fast DCT algorithms with efficient hardware and software implementations have been proposed. The DCT has found wide applications in image/video processing and other fields. It has become the heart of many international standards such as JPEG, H.26x, and the MPEG family [3] [4] [5].