Scalable wavelet video coders based on Motion Compensated Temporal Filtering (MCTF) have been shown to exhibit good coding efficiency over a large range of bit-rates, in addition to providing spatial, temporal and SNR scalabilities. However, the complexity of these wavelet video coding schemes has not been thoroughly investigated. In this paper, we analyze the computational complexity of a fully-scalable MCTF-based wavelet video decoder that is likely to become part of the emerging MPEG-21 standard. We model the change in computational complexity of various components of the decoder as a function of bit-rate, encoding parameters such as filter types for spatial and temporal decomposition and the number of decomposition levels, and sequence characteristics. A key by-product of our analysis is the observation that fixed-function hardware accelerators are not appropriate for implementing these next generation fully scalable video decoders. The absolute complexity of the various functional units as well as their relative complexity varies depending on the transmission bit-rate, thereby requiring different hardware/software architecture support at different bit-rates. To cope with these variations, a preliminary architecture comprising of a reconfigurable co-processor and a general purpose processor is proposed as an implementation platform for these video decoders. We also propose an algorithm to utilize the co-processor efficiently.
