Video compression algorithms are being used to compress digital video for a wide variety of applications, including video delivery over the Internet, advanced television broadcasting, video streaming, video conferencing, and video storage and editing. The impressive performance of modern compression algorithms, combined with the growing availability of video encoders and decoders and low- cost computers, storage devices, and networking equipment, makes it evident that between video capture and video playback, video will be handled in compressed video form. The resulting end-to-end compressed digital video systems motivate the need to develop efficient algorithms for handling compressed digital video. Compute- and memory-efficient, quality- preserving algorithms for handling compressed video streams are called compressed-domain processing (CDP) algorithms. CDP algorithms are useful for a number of applications. For example, a video server transmitting video over the Internet may be restricted by stringent bandwidth requirements. In this scenario, a high-rate compressed bitstream may need to be transcoded to a lower-rate compressed bitstream prior to transmission; this can be achieved by lowering the spatial or temporal resolution of the video or by more coarsely quantizing the MPEG data. Another application may require MPEG video streams to be transcoded into streams that facilitate video editing functionalities such as splicing or fast-forward and reverse play; this may involve removing the temporal dependencies in the coded data stream. Finally, in a video communication system, the transmitted video stream may be subject to harsh channel conditions resulting in data loss; in this instance it may be useful to create a standard-compliant video stream that is more robust to channel errors and network congestion. This chapter focuses on developing CDP algorithms for bitstreams that are based on video compression algorithms that rely on the block discrete cosine transform (DCT) and motion-compensated prediction, which includes a number of predominant image and video coding standards including JPEG, MPEG-1, MPEG-2, MPEG-4, H.261, H.263, and H.264/MPEG-4 AVC. These CDP algorithms achieve efficiency by using techniques that exploit the coding structures used in the original compression process; these techniques are discussed in detail. Two classes of CDP algorithms are presented-- compressed-domain transcoding algorithms that change the video format and compression format of compressed video streams and compressed-domain editing algorithms that perform video processing and editing operations on compressed video streams. 35 Pages