A Fast DCT Domain Inverse Motion Compensation algorithm based on Shared Information in a Macroblock

The ability to construct intra-coded frame from motion-compensated inter-frame coded directly in the compressed domain is important for efficient video manipulation and composition. In the context of motion-compensated DCT-based coding of video as in MPEG video, this problem of {\em DCT domain inverse motion compensation\/} has been studied in \cite{chang95} and fast algorithm based on factorization of the DCT matrix is proposed in \cite{merhav96}. These schemes, however, treat each $8 \times 8$ block as a fundamental unit, and do not take into account the fact that in MPEG, a macrolock consists of several such blocks. In this paper, we show how shared information within a macroblock such as motion vector and common blocks can be exploited to yield substantial speedup in computation. Compared to the brute-force approach in \cite{chang95}, our algorithms yield about 47~\% improvement. Our technique is independent of the underlying computational or processor model, and thus can be implemented on top of any optimized solution. We demonstrate an improvement by about 19~\% in the worst case on top of the optimized solutions presented in \cite{merhav96}.