Motion-compensated wavelet video coders have been shown to exhibit good coding efficiency over a large range of bit-rates, in addition to providing spatial and temporal scalability. While the rate-distortion performance provided by these coders is well understood, their complexity scalability behavior is not well studied. In this paper, we first analyze the complexity of such wavelet video coders, and determine what the critical components are and how they vary depending on the transmission bit-rates. Subsequently, we construct generic complexity models for the critical components of the scalable wavelet video decoders; such that optimal rate, distortion and complexity bitstreams can be created that fulfill not only various network constraints, but also resource constraints such as memory and power. The generic complexity metrics are independent of the hardware architecture and implementation details of the decoders and capture both the time varying video content characteristics and the corresponding encoding parameters. The generic complexity measures can be converted into real platform specific complexity measures like execution time with limited overhead at runtime. Preliminary results show that the proposed models can predict the complexity of the various components of wavelet video decoders with high accuracy.
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.