A fast multiplication-free algorithm for the inverse discrete cosine transform (IDCT) is developed. This algorithm is an approximation to the IDCT and is applicable in implementations of compression standards such as JPEG, MPEG-1, MPEG-2 H.263. The proposed algorithm is 32% faster than its exact counterpart. For low bit-rate video codecs, the quantization effects introduced by the multiplier-free approach is considerably lower than the distortion introduced by the quantizer settings of the video codec and thus the overall PSNR loss is well within 1 dB for the proposed multiplier-free approach. If DCT data sparseness is taken into account, compared with other recently developed fast approximate DCT and IDCT methods, the proposed scheme provides significant reductions in computation complexity. The approach described here can be easily adapted for the forward DCT.

Digital video is becoming widely available in compressed form, such as a motion JPEG or MPEG coded bitstream. In applications such as video browsing or picture-in-picture, or in transcoding for a lower bit rate, there is a need to downscale the video prior to its transmission. In such instances, the conventional approach to generating a downscaled video bitstream at the video server would be to first decompress the video, perform the downscaling operation in the pixel domain, and then recompress it as, say, an MPEG, bitstream for efficient delivery. This process is computationally expensive due to the motion-estimation process needed during the recompression phase. We propose an alternative compressed domain-based approach that computes motion vectors for the downscaled (N/2xN/2) video sequence directly from the original motion vectors for the N/spl times/N video sequence. We further discover that the scheme produces better results by weighting the original motion vectors adaptively. The proposed approach can lead to significant computational savings compared to the conventional spatial (pixel) domain approach. The proposed approach is useful for video severs that provide quality of service in real time for heterogeneous clients.

We present a new technique for sharpening compressed images in the discrete-cosine-transform domain. For images compressed using the JPEG standard, image sharpening is achieved by suitably scaling each element of the encoding quantization table to enhance the high-frequency characteristics of the image. The modified version of the encoding table is then transmitted in lieu of the original. Experimental results with scanned images show improved text and image quality with no additional computation cost and without affecting compressibility.

For direct manipulation in the compressed domain, we develop a DCT domain convolution theorem which besides exploiting the sparseness of the DCT domain representation also exploits the orthogonality and symmetry in the DCT domain representation. These properties lead to efficient compressed domain based processing methods unlike their spatial domain counterparts, where such properties are not available. This theorem can be used in a variety of image and video editing functions when the image and video data are available only as a JPEG or MPEG bitstream. We illustrate the use of these DCT domain convolution theorems in a typical video editing application such as video bluescreen editing.

Several compressed-domain based processing methods such as video downscaling, filtering, inverse motion compensation, etc. have been developed for MPEG compressed digital video. These processing methods assume that the underlying MPEG video was coded in only one mode, namely, frame or field mode. In order to support both frame and field-mode coded video, in this paper, we present a fast algorithm for converting a sequence of DCT blocks in the field mode to a sequence of blocks whose DCT's represent frame-mode coding. A multiplier-free implementation for this algorithm is also developed in this paper. In a typical coding setup, used in MPEG-2, simulations indicate that the image quality degradations resulting from the multiplier-free implementation is around 0.5-1.0 dB; however, a factor of two speedup is obtained compared with a traditional spatial-domain approach.

Conventional processing of JPEG or MPEG compressed image or video data involves first decompressing the data and applying the desired processing function, and then the processed data are recompressed for the purposes of transmission or storage. We propose an alternate processing pipeline which involves direct manipulation of the JPEG or MPEG compressed domain representation to achieve the desired spatial domain processing. For direct manipulation in the compressed domain, we develop a discrete cosine transform (DCT)-domain convolution theorem which besides exploiting the sparseness of the DCT-domain representation also exploits the orthogonality and symmetry in the DCT-domain representation. These properties lead to efficient compressed domain-based processing methods unlike their spatial domain counterparts, where such properties are not available. This theorem can be used in a variety of image and video editing functions when the image and video data are available only as a JPEG or MPEG bitstream. We illustrate the use of the DCT-domain convolution theorem in a typical video editing application such as video bluescreen editing.

Video coding standards use the block-matching algorithm (BMA) and motion-compensated prediction to reduce temporal redundancies present in image sequences. Block matching is used since it is computationally efficient and produces a minimal representation of the motion field that is transmitted as side information. In order to build a robust coder the motion-estimation technique must be able to track motion in a noisy source. The approach presented in this paper uses spatio-temporal motion prediction, providing an accurate motion estimate even in the presence of noise. With this approach, noisy sources can be compressed efficiently and robustly in standard video coders (e.g., MPEG-1, MPEG-2, H.261, and H.263) with little increase in complexity.

We propose a low-complexity error resilience method which is compatible with the emerging H.263 standard. The proposed method, which corrects one slice of lost information exactly or partially, is specifically suited to the packet networks such as the Internet where the majority of the errors are due to packet losses. The proposed method is simple and to decode the overhead information no extra software or hardware is required. The amount of generated overhead is minimal as is the delay to reconstruct lost information. Using this method, it is possible to easily trade-off bits between the source and protection data, hence achieving a simple adaptation method to the current status of the channel.

The visual quality of scanned color documents suffers because of inherent limitations in color scanners. In cases where the scanned documents will also be compressed using the JPEG standard, we present a new technique that sharpens the compressed images in the DCT domain. Sharpening is achieved by suitably scaling each element of the encoding quantization table to enhance the high-frequency characteristics of the image. Experimental results show improved text and image quality with no additional computation cost.

Digital video is becoming widely available only in the compressed form. In applications such as video browsing or picture-in-picture or transcoding for a lower bit rate, there is a need to downscale the video before transmission. In such instances, the conventional approach of generating a downscaled video bitstream at the video server is to first decompress the video, perform the downscaling operation in the pixel domain and then recompress it for efficient delivery. This process is computationally expensive due to the motion-estimation process needed during the recompression phase. We propose an alternative compressed domain based approach that computes the motion vectors for the downscaled (N/2/spl times/N/2) video sequence directly from the original motion vectors residing in the N/spl times/N video sequence. Furthermore, the downscaling of the DCT information is also done in the DCT domain. The proposed approach can lead to significant computational savings compared to the conventional spatial domain approach.

An algorithm is proposed for efficiently splicing two MPEG-coded video streams. The algorithm only processes the portion of each video stream that contains frames affected by the splice and it operates directly on the DCT coefficients and motion vectors of those frames. The algorithm achieves good visual performance with very low computational complexity, and incorporates rate control to prevent buffer underflow and overflow. If additional processing power is available, it can be used to further improve the quality of the spliced stream.

A new 16-bit integer MPEG-1 layer II audio decoding algorithm is introduced, this algorithm incorporates a scaled Chen (1977) discrete cosine transform (DCT) instead of a generic DCT in the matrixing block, the use of a scaled DCT reduces the DCT multiply count by 28%. This 16-bit integer decoder is compliant with the Moving Picture Expert Group (MPEG) standard.

Straightforward techniques for spatial domain processing of compressed video via decompression and recompression are computationally expensive. We describe an alternative approach wherein the compressed stream is processed in the compressed, discrete cosine transform (DCT) domain without explicit decompression and spatial domain processing, so that the output compressed stream, corresponding to the output image, conforms to the standard syntax of 8/spl times/8 blocks. We propose computation schemes for downsampling and for inverse motion compensation that are applicable to any DCT-based compression method. Worst case estimates of computation savings vary between 37% and 50% depending on the task. For typically sparse DCT blocks, the reduction in computations is more dramatic. A by-product of the proposed approach is improvement in arithmetic precision.

We present an algorithm and a hardware architecture for block-based motion estimation that involves transforming video sequences from a multibit to a one-bit/pixel representation and then applying conventional motion estimation search strategies. This results in substantial reductions in arithmetic and hardware complexity and reduced power consumption, while maintaining good compression performance. Experimental results and a custom hardware design using a linear array of processing elements are also presented.

One of the important tasks of a multiuser video network server is to composite compressed video streams from several sources into a single compressed video stream. A great deal of the computational load can be saved if this composition is performed directly in the compressed domain rather than using the brute-force approach of converting back to the uncompressed domain, compositing pixel-by-pixel in the spatial domain, and re-compressing the composite stream. We propose a fast algorithm that converts motion compensated compressed video into a sequence of DCT-domain blocks corresponding to the spatial domain blocks of the current frame alone, without prediction based on other frames, i.e., removing the inter-frame element of the compression-decompression. This step enables video compositing in the DCT compressed domain as well as several compositing operations, e.g., scaling, overlapping, translation, filtering, etc. The proposed algorithm saves about 47% of the computations compared to the brute-force approach even without assuming sparseness of the DCT blocks. For typical sparse DCT blocks, where only the top-left 4/spl times/4 quadrant is nonzero, the reduction in computational complexity is about 68%.

Straightforward techniques for spatial domain scaling of compressed video via decompression and re-compression are computationally expensive. We describe an alternative approach wherein the compressed stream is processed in the compressed, DCT domain without explicit decompression and spatial domain scaling, so that the output compressed stream corresponds to a down-sampled image and it conforms the standard syntax of 8/spl times/8 blocks. We propose computation schemes for scaling factors of 2, 3 and 4 that are applicable to any DCT-based compression method. Worst-case estimates of computation savings very between 37% and 50% depending on the scaling factor. For typically sparse DCT blocks, the reduction in computations can be as much as 80%. A byproduct of the proposed approach is improvement in arithmetic precision.

We present a strategy for block-based motion estimation that involves transforming video sequences from a multibit to a one-bit/pixel representation, and then applying conventional motion estimation search strategies. This results in substantial reductions in arithmetic and hardware complexity, and reduced power consumption, while maintaining good compression performance. Experimental results and a custom hardware design are also presented.

Encoding noisy data is a challenging problem in data compression. Recent results show that data compression and filtering are closely related. Exploiting these ideas, we propose a simple technique for vector quantization (VQ) coding of noisy images, based on pre-filtering only the training set prior to codebook design. We find that our technique results in significant improvement in image quality, comparable to that obtained by the computationally more expensive approach of pre-filtering both the training set and the images to be encoded. A preliminary justification of our results from the theory of Occam filtering is also provided.

We present a fast approximate algorithm for scaling down an image by a factor of two, when the input and output streams are both in the form of 8/spl times/8 discrete cosine transform (DCT) transform blocks, as with JPEG coded images. Roughly speaking, the algorithm requires 80% fewer operations than the naive algorithm of inverting the transform, scaling in the spatial domain, and transforming the resulting image.

Traditional video decoders require use of specially designed video decompression processors. We present novel algorithmic and architectural enhancements that allowed for the first time the real-time decompression of MPEG-1 video and audio streams on a low-end, general purpose RISC processor. For video decompression, efficient algorithmic implementations were derived by examining the Huffman decoder, the inverse quantizer and the inverse DCT as a single system. For audio decompression, a new DCT based implementation of the subband filtering operation yields 30% speed improvement in the audio decoding process and 17% speed improvement in overall audio and video decoding. Besides algorithmic enhancements, a new set of "multimedia" instructions and minor changes in the design of a traditional RISC ALU allowed increased parallelism of pixel-based operations with minimal design and control overhead. Experimental results show that with the synergistic combination of algorithmic and architectural enhancements a multimedia-enhanced RISC processor can achieve higher decoding rates than generic RISC and CISC processors, even when these processors operate at higher clock rates and have larger instruction and data caches.>

We present a non-linear filtering technique for digital video to enable improved nearly lossless compression. In contrast to preprocessing techniques, our technique uses the compression algorithm for both filtering and compression in one step, by exploiting the property that random noise is hard to compress.>

The authors explore compression using an optimal algorithm for the approximation of waveforms with piecewise linear functions. They describe a modification of the algorithm that is provably good, but simple enough for the associated hardware implementation to be presentable.>

An adaptive approach to two-dimensional tree encoding of images is presented based upon the use of spatial masking concepts. Specifically, we make use of an adaptive encoding filter of the smoothing variety whose smoothing action is controlled by the local visibility of the encoding noise. The approach is an attempt to obtain an optimum compromise between slope overload and granular noise characteristics associated with existing two-dimensional tree encoding schemes. We demonstrate that this adaptive approach can provide improved overall image coding performance, both objectively and subjectively, compared to existing tree encoding schemes at a reduced order of complexity. The subjective improvements are clear and striking to the eye.

A class of robust two-dimensional (2-D) tree coding procedures are described for efficient encoding of monochrome images. The encoding filter is designed on the basis of ensemble properties of a particular class of stochastic random fields which have been shown to provide a useful model for typical imagery data. We make use of the (M; K', L') algorithm in instrumenting the 2-D tree search. Results are demonstrated for both synthetic images and a number of head-and-shoulders images. These results demonstrate the effectiveness of 2-D tree encoding using fairly moderate search intensities and the inherent robustness of 2-D tree encoding more generally. In particular, it is demonstrated that, by logical design of the encoding filter under an appropriate stochastic modeling assumption, the 2-D tree encoder provides relatively efficient performance for a rather wide range of real-world imagery.

The performance and complexity of tree encoding of images in the presence of channel errors is considered. We demonstrate that a variation of the(M, L)algorithm yields performance close to the rate-distortion bound in the absence of channel errors for synthetic images modeled as two-dimensional autoregressive random fields. Trade-offs in optimizing the choice of tree search parameters are described, and experimental results on real-world images are presented. Simple tree search procedures are shown to provide signal-to-noise improvements in excess of 5 dB over conventional two-dimensional DPCM at the important rate of one bit/pixel; the effect is clear and striking to the eye. Channel error effects are treated by computer simulation and demonstrate signal-to-noise ratio improvement as high as 8 dB using tree encoding. Finally, a combined source-channel coding approach is described that exploits the significant trade-offs between source quantization accuracy and vulnerability to channel errors.