The JPEG-2000 standard demonstrated that state-of-the-art coding performance can be obtained in still-image compression with a coding architecture that enables a rich set of features for the compressed bitstream, such as a precise rate-control mechanism and multiple qualities and resolutions of the same picture based on selective decoding of portions of the compressed bitstream. This is a natural consequence of the use of a scalable image compression algorithm based on the wavelet decomposition and embedded coding. In this dissertation we investigate the extension of wavelet-based scalable coding to video signals. This problem appears to be of particular importance today, when ubiquitous video communication and video streaming takes place through unreliable (IP-based) wired and wireless media, and among terminals with different display and implementation capabilities. In the first part of our work, we examine algorithmic aspects of wavelet-based scalable video coding systems. In particular, novel algorithms are proposed for wavelet-domain (in-band) open-loop and closed-loop motion-compensated prediction. Our choice of deviating from the conventional temporal prediction in the spatial-domain representation (i.e. motion estimation and compensation using the original video signal) is motivated by the fact that, in this way, the multiresolution features of the discrete wavelet transform (DWT) can be exploited in order to provide an improved hierarchical representation of the video content across resolutions. One significant problem of our approach relates to the shift-variance of the DWT that hinders the performance of motion-compensated prediction in the wavelet domain. In fact, until recently, this has prevented the related research community from investigating in-band video coding. In this thesis, based on prior work, we attack the problem of shift-variance in a systematic way by proposing a new transform, termed the Complete-to-Overcomplete Discrete Wavelet Transform (CODWT), which effectively provides a shift-invariant (overcomplete) representation from the DWT, useful for in-band motion estimation. Several symmetry properties are proven for the CODWT and fast calculation algorithms are proposed that suit the application framework of in-band video coding. Although motion estimation is utilizing the overcomplete DWT representation of the reference frame, motion compensation is always performed in the critically-sampled DWT. Hence the subsequently produced error-frames remain critically-sampled. This enables the possibility for existing state-of-the-art embedded wavelet coders to be employed for the coding of the error frames. Our extensive experimental evaluation reveals that the proposed systems provide comparable quality to the equivalent systems operating in the spatial domain, while at the same time a substantially-improved multiresolution decoding capability is achieved. In order to improve the prediction efficiency of the proposed video coding architectures, an advanced motion estimation algorithm is proposed that incorporates multihypothesis variable block-size prediction. Moreover, in the case of open-loop motion-compensated temporal filtering, we couple the proposed advanced prediction schemes in the wavelet-domain with in-band motion-compensated update schemes, thereby proposing a novel system that performs advanced in-band motion-compensated temporal filtering. This architecture is fully-scalable in quality, resolution and frame-rate and, at the same time, compares favourably with the state-of-the-art in video coding. The second part of this dissertation is devoted to complexity-modeling aspects of wavelet-based scalable video coding. Two models for predicting the complexity of video coding algorithms under realistic conditions are proposed. The two proposals target different aspects of complexity; in particular, the first presents a model for the cache-behaviour of the two-dimensional DWT, which targets implementation platforms where the memory bottlenecks are expected to dominate the execution of data-dominated signal processing tools such as the DWT. The analysis in that section is based on analyzing the algorithmic flow and expressing the expected cache misses in analytical formulations. The second topic proposes a novel framework for complexity modeling of motion-compensated video decoders, which is based on a generic decomposition of the arithmetic (and potentially the memory) profile of these systems into a set of basis functions, without specific regard to the details of the algorithms involved. In each case, the models are experimentally validated by using real-life video coding tools and systems.