PostScript (599 KB)Doctoral Dissertation
Dynamic Rate Shaping of Compressed DigitalVideo
Abstract
We introduce the concept of Dynamic Rate Shaping (DRS), a technique to adapt the rate of compressed video bitstreams (e.g., MPEG-1, MPEG-2, H.261, JPEG) to dynamically varying rate constraints by operating directly in the compressed signal domain. Such a scheme is shown to be critical for multimedia communication systems, since it can guarantee universal interoperability between encoders/decoders and networks with widely different (and even time-varying) quality of service guarantees. The concept is shown to evolve naturally by considering first the operation of an actual multimedia communication system, in the form of the "Xphone" testbed that we have developed. It is shown that a key technique for enabling video communication using a system based on a best-effort operating system and network is, among others, adaptive rate control of the bit rate of video (JPEG in this case).
A natural extension of the adaptive rate control approach in Xphone is Data Partitioning. This scheme splits a compressed bitstream into two parts, and achieves robustness by transmitting them over channels with different quality of service guarantees. This provides the first critical step in detaching the manipulation of the rate from the encoder. An analysis of optimal data partitioning is provided using an operational rate-distortion context, and several algorithms are proposed. The DRS concept then arises by eliminating the second bitstream and allowing the rate constraints to vary over time.
DRS provides an interface between the encoder and the network, with which the encoder's output can be perfectly matched to the network's quality of service characteristics. In essence, DRS bridges the gap between constant and variable bit rate video, providing a continuum of possibilities between the two. The problem of optimal DRS is analyzed, and a family of optimal and fast algorithms is described. We also show that Data Partitioning is a special case of "clustered constrained" DRS. Some of the fast DRS algorithms perform extremely close to optimal; their low complexity allows even purely software-based real-time implementation, thus making them attractive candidates for incorporation in actual multimedia communication systems.