Using 4x4 DCTs and moving 4x4 blocks for software-only video decompression
Roger J. Wilson · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1994
4 X 4 inverse DCTs are computationally twice as efficient as 8 X 8 inverse DCTs. In addition they have less register pressure, making the implementation more efficient for most processors. This extra computational efficiency places more pressure on improving the other components of the video decompression system. This paper describes a coding scheme for the quantized components which has an efficient decompression algorithm. The implementation of the inverse DCT is examined in detail, including removing all multiplication operations and replacing them with single CPU cycle shift-and-add operations. The data flow through a complete 4 X 4 DCT is described such that the results of intermediate 1 X 4 DCTs are written to and read from memory as efficiently as possible. A set of quantizers for the 4 X 4 DCT are presented which allow the decompression process to use shift-and-add instead of multiply. Efficient DCTs by themselves are not enough: the paper discusses the effects of changing the search area (in particular to being non-square) and shows a coding scheme suitable for fast decompression. It also discusses how to organize the block matching and that good results can be obtained if some pixels are allowed to match worse than the nominal value.