This paper addresses the problem of reconstructing a compressively sampled sparse signal from its lossy and possibly insufficient measurements. The process involves estimations of sparsity pattern and sparse representation, for which we derived a vector estimator based on the Maximum a Posteriori Probability (MAP) rule. By making full use of signal prior knowledge, our scheme can use a measurement number close to sparsity to achieve perfect reconstruction. It also shows a much lower error probability of sparsity pattern than prior work, given insufficient measurements. To better recover the most significant part of the sparse representation, we further introduce the notion of bit-plane separation. When applied to image compression, the technique in combination with our MAP estimator shows promising results as compared to JPEG: the difference in compression ratio is seen to be within a factor of two, given the same decoded quality.

A new architecture design for motion estimation using binary matching criterion is proposed to achieve low power and bus bandwidth efficiency. Low power and high bus bandwidth efficiency are the two key issues for portable video applications. To address such issues, we first study an efficient algorithm called all binary motion estimation (ABME), and analyze its architecture issues in operational flow and bus access. Then, we propose an architecture for ABME with four new features: (1) macroblock level pre-processing; (2) efficient binary pyramid search structure; (3) parallel processing of 8 x 8 and 16 x 16 block searches; (4) parallel processing of bi-directional search. Such architecture leads to a superior performance in bus access, speed, and power. Our experiments show that the power consumption is as low as 763 mu W for IPPPP CIF 30 frames/s and 896 muW for IPBPB CIF 30 frames/s. The bus bandwidth savings are 54.3% for P-frame search and 67.1% for B-frame search.

In this paper, we perform the design space exploration for an H.264/AVC video embedding transcoder. Specifically, the design space is pruned for the sub-modules including inverse transform, inter and intra prediction, and deblocking filter with various microarchitecture designs, processing order, memory hierarchy, and granularity of synchronization. In addition, we propose an efficient deblocking filter suitable for 8x8 block pipeline. Compared to the traditional designs, our proposed deblocking filter reduces memory requirement, processing latency, and access frequency to the local memory. The synthesized logic gate count is only 8K using the 0.18 um technology with the maximum frequency of 162 MHz. For rapid exploration, all the design alternatives are simulated with higher level of abstraction using the transaction level modeling to explore 160 design combinations. Our simulation results provide an extensive tradeoff analysis among processing speed, cost, and utilization. Besides, the cost-normalized hardware utilization where the cost of each sub-module weights its associated utilization assists the system designers to keep a balance across different modules.

In this paper, we propose a system architecture for H.264/AVC video embedding transcoder (VET). In addition, the proposed platform-based design can seamlessly combine the MW-VET and decoder such that it can be dynamically configured to perform video decoding and transcoding alternatively or simultaneously. Furthermore, we perform the pruned design space exploration on the design of inter/intea prediction and the on-chip data bus width. Our proposed architecture provides a better tradeoff among execution cycles, hardware cost, resource utilization, and video quality because of the reconfigurable processing modules and the hybrid pipelining. As compared to the cascaded pixel domain transcoder that has the highest complexity, our hardware efficient VET can significantly reduce the hardware cost while maintaining similar rate-distortion performance. Finally, the proposed architecture is verified at system level using transaction level modeling (TLM) technique. From the simulation results, the proposed architecture with the best tradeoff configuration can achieve a transcoding rate up to 358 frames per second for SD video source while clocking at 162MHz.

In this paper, we will investigate the performance of scalable video streaming services in mobile WiMAX systems. We will show that for each user the implementation of multiple connections with feedback information of the available transmission bandwidth is critical for supporting H.264/AVC-based scalable video streaming in which the transmission packets can be further separated into multiple levels of importance. Based on a mobile WiMAX simulation platform including both the video encoder/decoder server and IEEE 802.16e MAC controls, the MAC performance evaluation and subjective test are used to quantify the visual performance between two-connection and one-connection scenarios.

This paper presents a noise-to-masking-ratio (NMR) optimized MPEG-2/4 AAC low-complexity (LC) transcoder, called as fast rate-distortion optimized transcoder (FRDOT). The FRDOT searches for the optimal scale factors under the NMR criterion according to the magnitudes of quantized input coefficients and the target bitrate. The computation of NMR difference is replaced by the derivation of signal-to-noise-ratio (SNR) difference since the audible masking thresholds of the original and transcoded bitstreams are identical. The SNR value is further converted to a noise-to-signal-ratio (NSR) to represent distortion energy of audio signals. With the NSR values, a table lookup technique is used to speed up the search of the optimal scalefactor increment. To further reduce the execution time, a bandwidth limiter is used to remove the iterative rate-distortion optimization of a frame. In addition, a bitrate control module is proposed to make the averaged bitrate of output bitstream close to the target bitrate. The results show that the FRDOT has smaller NMR values than the cascaded transcoder (CT) by 0.5-3.0 dB at different bitrates with 6-7 times speedup on the average.

To provide better QoS of scalable streaming services in mobile WiMAX systems, this paper proposes a cross-layer design between the streaming server and mobile WiMAX base station. We will show that the implementation of multiple connections with feedback information of the available transmission bandwidth is critical for supporting scalable video streaming in which the transmission packets can be further separated into multiple levels of importance. To quantify the performance, a mobile WiMAX simulation platform including both the video encoder/decoder server and IEEE 802.16e MAC controls is developed.

Video streaming is one of the killer applications for cellular communications. The MPEG-4 fine-granularity scalability video coding technique can adapt to bandwidth variation and random packet errors. In this paper, to explore the impacts of cellular channel characteristics on the tolerance of buffer performance and quality of service, a novel statistical model-based adaptive media playout (AMP) is proposed by utilizing the statistical assumptions of both arrival and departure processes for a better decision on the dynamic threshold adjustment and frame-rate adjustment. Based on third-generation cellular transmission environment, simulation results will demonstrate that as compared to other AMP schemes, the proposed AMP control provides better visual quality with lower complexity.

In this paper, we propose a lossless, graceful, and arbitrary-shaped region-of-interest (ROI) functionality for the scalable video coding in MPEG-4 Part 10 Amd. 1. Specifically, we propose a prioritized block coding scheme and a layer remapping technique. Within an enhancement layer, the prioritized block coding reshuffles the transform coefficients for ROI. Moreover, the layer remapping technique prioritizes different ROI among enhancement layers. For graceful and arbitrary-shaped properties, additional syntax are coded at the levels of slice, layer, and macroblock. To minimize overhead, an efficient representation for priority information is proposed. Experimental results show that our schemes can offer the ROI functionality over a wide range of bit rates while maintaining coding efficiency.

This paper presents a unified systolic architecture for inter and intra predictions in H.264/AVC decoder. To increase hardware utilization and minimize cost, we combine inter and intra predictions by a reprogrammable FIR filter, which is further implemented using systolic array. For intra prediction, the boundary pixels are reshuffled before feeding into the systolic array. For inter prediction, the 2-D interpolation is conducted through separable 1-D filtering. As compared with the state-of-the-art approaches, our architecture provides higher performance while maintaining relatively lower cost and input bandwidth. Specifically, up to 4x throughput improvement has been achieved. Moreover, the input bandwidth is significantly reduced. Further, combining inter and intra predictions saves the cost by 22~88%.

In this paper, we propose a context adaptive bit-plane coding (CABIC) with a stochastic bit reshuffling (SBR) scheme to deliver higher coding efficiency and better subjective quality for fine granular scalable (FGS) video coding. Traditional bit-plane coding in FGS algorithm suffers from poor coding efficiency and subjective quality. To improve coding efficiency, our CABIC constructs context models based on both the energy distribution in a block and the spatial correlations in the adjacent blocks. Moreover, it exploits the context across bit-planes to save side information. To improve subjective quality, our SBR reorders the coefficient bits by their estimated rate-distortion performance. Particularly, we model transform coefficients with Laplacian distributions and incorporate them into the context probability models for content-aware parameter estimation. Moreover, our SBR is implemented with a dynamic priority management that uses a low-complexity dynamic memory organization. Experimental results show that our CABIC improves the PSNR by 0.5/spl sim/1.0 dB at medium and high bit rates. While maintaining similar or even higher coding efficiency, our SBR improves the subjective quality.

We present a line-based adaptive lossless video compression (LALVC) algorithm for interactive multimedia applications that demand low complexity and low latency. Communications between high-resolution display and storage devices require high bandwidth for exchanging raw data. To reduce cost of video transmission without losing data accuracy, lossless video compression is necessary. Considering low complexity and low delay, LALVC adopts a simple and efficient architecture that adopts one-pass, raster-scan, transform-free coding process and a simple predictor. For low latency, zero-motion prediction and one-frame buffer are used to reduce temporal redundancy. In addition, to maximize the coding efficiency for both natural and computer-generated video sequences, LALVC adaptively selects the best coding mode for each line of a frame. The entropy coding of each line is based on Golomb code that can enhance coding efficiency with less computation load and is easy for hardware realization. The simulation results show that temporal preprocessing and line-based mode decision of LALVC can increase compression ratio with properly increased complexity as compared to that of JPEG-LS.

The work presents a novel and fast transcoding scheme with PIP (picture-in-picture) functionality, based on the H.264/AVC standard. We seamlessly achieve significant speedup and maintain identical video quality for the composite video content using two H.264 bitstreams. The proposed partial re-encoding transcoder (PRET) method, based on the intra-prediction refinement, inter-prediction refinement and rate-distortion optimization, has sped up by 8 times compared with rate-distortion (R-D) based optimization alone. In addition, the performance of the PRET is better than that of the R-D re-encoding algorithm.

A subsampling structure, an N-Queen lattice, for spatially decimating a block of pixels is presented. Despite its use for many applications, we demonstrate that the N-Queen lattice can be used to speed up motion estimation with nominal loss of coding efficiency. With a simple construction, the N-Queen lattice characterizes the spatial features in the vertical, horizontal, and diagonal directions for both texture and edge areas. Especially in the 4-Queen case, every skipped pixel has the minimal and equal distance of unity to the selected pixel. It can be hierarchically organized for variable nonsquare block-size motion estimation. Despite the randomized lattice, we design compact data storage architecture for efficient memory access and simple hardware implementation. Our simulations show that the N-Queen lattice is superior to several existing sampling techniques with improvement in speed by about N times and small loss in peak SNR (PSNR). The loss in PSNR is negligible for slow-motion video sequences and is less than 0.45 dB at worst for high-motion estimation sequences.

We present a novel technique, N-queen lattice, to spatially subsample a block of pixels. Although this lattice is pertinent to many applications, we present an application to speed up motion estimation with minimal loss of coding efficiency. The N-queen lattice is constructed to characterize spatial features in all directions. It can be hierarchically organized for motion estimation with variable nonsquare block size. Despite the randomized lattice structure, we demonstrate that it is possible to achieve compact data storage architecture for efficient memory access and simple hardware implementation. Our simulations show that the N-queen lattice is superior to several existing sampling techniques with improvement in speed by about N times and small loss in peak SNR.

Recently, the MPEG-4 committee has approved the MPEG-4 fine granularity scalability (FGS) profile as a streaming video tool. We propose novel techniques to improve further the temporal prediction at the enhancement layer so that coding efficiency is superior to the existing FGS. Our approach utilizes two parameters, the number of bitplanes, /spl beta/ (0/spl les//spl beta//spl les/maximal number of bitplanes), and the amount of predictive leak, /spl alpha/ (0/spl les//spl alpha//spl les/1), to control the construction of the reference frame at the enhancement layer. Parameters /spl alpha/ and /spl beta/ can be selected for each frame to provide tradeoffs between coding efficiency and error drift. Our approach offers a general and flexible framework that allows further optimization. It also includes several well-known motion-compensated FGS techniques as special cases with particular sets of /spl alpha/ and /spl beta/. We analyze the theoretical advantages when /spl alpha/ and /spl beta/ are used, and provide an adaptive technique to select /spl alpha/ and /spl beta/, which yields an improved performance as compared to that of fixed parameters. An identical technique is applied to the base layer for further improvement. Our experimental results show over 4 dB improvements in coding efficiency using the MPEG-4 testing conditions. Removal of error propagation is demonstrated with several typical channel transmission scenarios.

We present a fast motion estimation algorithm using only binary representation, which is desirable for both embedded system and hardware implementation with parallel architectures. The key algorithm distinction is that only the high-frequency spectrum is used. Our experimental results show that it provides excellent performance at both low and high bit rates. Because of its binary-only representation, the proposed algorithm offers low computational complexity and low memory bandwidth consumption. For multimedia-embedded system design, we further investigated specific implementation techniques for several well-known hardware platforms including Intel x86 processors, single-instruction multiple-data processors, and systolic array circuit design. The systolic array architecture requires only single memory access for both the reference and current frames from the on-chip memory. Such an implementation provides an optimized solution with great throughput, while the quality is maintained. Finally, we show that our binarization methods are closely coupled to the accuracy of binary motion estimation algorithms. The binarization and coding efficiencies can be improved using various filters and binarization methods.

In this paper, we summarize several encoding tools that were introduced by the video group of the MPEG-4 committee. The review the key features of these algorithms. The original proposers in the MPEG-4 committee have implemented these algorithms in the reference software. We used the most recent reference software to generate a sample set of results. A profiling was performed on a Pentium 233 MHz PC to understand the complexity aspect of an MPEG-4 encoder.

This paper presents a scalable rate control (SRC) scheme based on a more accurate second-order rate-distortion model. A sliding-window method for data selection is used to mitigate the impact of a scene change. The data points for updating a model are adaptively selected such that the statistical behavior is improved. For video object (VO) shape coding, we use an adaptive threshold method to remove shape-coding artifacts for MPEG-4 applications. A dynamic bit allocation among VOs is implemented according to the coding complexities for each VO. SRC achieves more accurate bit allocation with low latency and limited buffer size. In a single framework, SRC offers multiple layers of controls for objects, frames, and macroblocks (MBs). At MB level, SRC provides finer bit rate and buffer control. At multiple VO level, SRC offers superior VO presentation for multimedia applications. The proposed SRC scheme has been adopted as part of the International Standard of the emerging ISO MPEG-4 standard.

A novel fast binary pyramid motion estimation (FBPME) algorithm is presented in this paper. The proposed FBPME scheme is based on binary multiresolution layers, exclusive-or (XOR) Boolean block matching, and a N-scale tiling search scheme. Each video frame is converted into a pyramid structure of K-1 binary layers with resolution decimation, plus one integer layer at the lowest resolution. At the lowest resolution layer, the N-scale tiling search is performed to select initial motion vector candidates. Motion vector fields are gradually refined with the XOR Boolean block-matching criterion and the N-scale tiling search schemes in higher binary layers. FBPME performs several thousands times faster than the conventional full-search block-matching scheme at the same PSNR performance and visual quality. It also dramatically reduces the bus bandwidth and on-chip memory requirement. Moreover, hardware complexity is low due to its binary nature. Fully functional software MPEG-2 MP@ML encoders and Advanced Television Standard Committee high definition television encoders based on the FBPME algorithm have been implemented. FBPME hardware architecture has been developed and is being incorporated into single-chip MPEG encoders. A wide range of video sequences at various resolutions has been tested. The proposed algorithm is also applicable to other digital video compression standards such as H.261, H.263, and MPEG4.

With the success of the Internet and flexibility of MPEG-4, transporting MPEG-4 video over the Internet is expected to be an important component of many multimedia applications in the near future. Video applications typically have delay and loss requirements, which cannot be adequately supported by the current Internet. Thus, it is a challenging problem to design an efficient MPEG-4 video delivery system that can maximize the perceptual quality while achieving high resource utilization. This paper addresses this problem by presenting an end-to-end architecture for transporting MPEG-4 video over the Internet. We present a framework for transporting MPEG-4 video, which includes source rate adaptation, packetization, feedback control, and error control. The main contributions of this paper are: (1) a feedback control algorithm based on the Real Time Protocol (RTP) and the Real Time Control Protocol (RTCP); (2) an adaptive source-encoding algorithm for MPEG-4 video which is able to adjust the output rate of MPEG-4 video to the desired rate; and (3) an efficient and robust packetization algorithm for MPEG video bit-streams at the sync layer for Internet transport. Simulation results show that our end-to-end transport architecture achieves good perceptual picture quality for MPEG-4 video under low bit-rate and varying network conditions and efficiently utilizes network resources.

It is a challenging problem to design an efficient MPEG-4 video delivery system that can machine the perceptual quality while achieving high resource utilization. This paper addresses this problem by presenting an architecture of transporting MPEG-4 video over the Internet, which includes an end-to-end feedback control algorithm and a source encoding rate control algorithm. Our feedback control algorithm is capable of estimating the available bandwidth in the network based on the feedback information from the receiver, while our source encoding rate control algorithm is able to adjust the encoding rate of MPEG-4 video to the desired rate. Simulation results demonstrate that our architecture achieves good perceptual picture quality under low bit-rate and varying network conditions while efficiently utilizing network resources.

A mechanism for dynamically varying the frame rate of pre-encoded video clips is described. An off-line encoder creates a high quality bitstream encoded at 30 fps, as well as separate files containing motion vectors for the same clip at lower frame rates. An on-line encoder decodes the bitstream (if necessary) and re-encodes it at lower frame-rates in real-time using the pre-computed, stored motion information. Dynamic Frame Rate Control, used in conjunction with dynamic bit-rate control, allows clients to solve the rate mismatch between the bandwidth available to them and the bit-rate of the pre-encoded bitsream. It also provides a means for implementing Fast Forward control for video streaming without increasing bandwidth consumption.

This paper addresses the issue of hierarchical coding of digital television. A two-layer coding scheme is presented to provide compatibility of standard-definition television (SDTV) and high-definition television (HDTV). The scheme is based on a spatio-temporal pyramid coding technique. We address the problem of interlaced-to-interlaced two-layer compatible coding where both layers are interlaced. The resolution translation is important for the visual quality of the SDTV layer and for the performance of the HDTV layer. A motion-compensated up/down deinterlacing scheme is used to improve the performance. A spatio-temporal averaging technique is used to give a better compatible prediction so that the HDTV layer has a high compression performance. To offer an improved prediction, systematic analysis of the remaining statistical redundancy of the enhancement signal is conducted. Based on an autoregressive model of the difference signal, a Kalman statistical filtering is used to exploit such a redundancy. We combine a recursive filtering and discrete cosine transform (DCT) coding using QR decomposition, where Q is an orthonormal matrix and R is an upper triangular matrix. The error accumulation is cancelled in the DCT frequency domain. The results show peak signal-to-noise-ratio improvements over simulcast as high as 1.2 dB. The new technique, which is referred to as spatial scalability using a Kalman filter (SSKF), achieves a comparable or better picture quality than that of a nonscalable approach for high-quality video coding. The near optimal performance is demonstrated by the white Gaussian noise property of the residual signal.

This paper presents a scalable rate control scheme (SRC) based on three new concepts: (1) a more accurate rate distortion model, (2) a sliding window method, and (3) an adaptive selection criterion of data points. The SRC scheme achieves a more accurate target bit allocation under the constraints of low latency and limited buffer size. In addition to the picture-level rate control, the SRC scheme is also applicable to the macroblock-level rate control for finer bit allocation and buffer control, and multiple video objects (VOs) rate control for better video object presentation in different applications. The proposed SRC scheme has been adopted in verification model (VM) 5.0 and VM 8.0 of the emerging ISO MPEG-Q standard.

In this demonstration session, we will demonstrate several examples of the state-of-the-art video compression standards MPEG-2, MPEG-4 and H.263. These demonstrations captured some of the recent work developed in the Digital Video Communications group at Sarnoff. For the MPEG-2 demonstration, the compression process uses standards compliant syntax with Sarnoff's proprietary algorithms to select the encoding parameters. For the MPEG-4 demonstration, we show the encoding results of the Verification Model including Sarnoff's contribution in scalable rate control and texture coding mode. In addition, we show the encoding results of a video streaming technology using H.263 and Sarnoff's proprietary technologies.

A global motion compensation (GMC) scheme is described and implemented for low bitrate coding. Experiments show that GMC gives excellent coding results. When coupled with the H.263 low bitrate video coding standard, GMC is capable of achieving up to 27% bitrate saving (or 1.8 dB gain in PSNR) for a high motion sequence such as Stefan. For a moderate motion sequence such as Cost-guard, we obtained an 8% bitrate saving over H.263 at the same quality using GMC.

A new rate control scheme is used to calculate the target bit rate for each frame based on a quadratic formulation of the rate distortion function. The distortion measure is assumed to be the average quantization scale of a frame. The rate distortion function is modeled as a second-order function of the inverse of the distortion measure. We present a closed form solution for the target bit allocation which includes the MPEG-2 TM5 rate control scheme as a special case. The model parameters are estimated using statistical linear regression analysis. Since the estimation uses the past encoded frames of the same picture prediction type (I, P, B pictures), the proposed approach is a single pass rate control technique. Because of the improved accuracy of the rate distortion function, the fluctuations of the bit counts are significantly reduced by 20-65% in the standard deviation of the bit count while the picture quality remains the same. Thus, the buffer requirement is reduced at a small increase in complexity. This technique has been adopted by the MPEG committee as part of VM5.0 in November 1996.

This paper describes a hybrid motion-compensated wavelet transform coder designed for encoding video at very low bit rates. The coder and its components have been submitted to MPEG-4 to support the functionalities of compression efficiency and scalability. Novel features of this coder are the use of overlapping block motion compensation in combination with a discrete wavelet transform followed by adaptive quantization and zerotree entropy coding, plus rate control. The coder outperforms the VM of MPEG-4 for coding of I-frames and matches the performance of the VM for P-frames while providing a path to spatial scalability, object scalability, and bitstream scalability.

A new rate control scheme is used to calculate the target bit rate for each frame based on a quadratic formulation of the rate distortion function. The distortion measure are assumed to be either the average quantization scale of a frame or mean square error. The rate distortion function is modeled as a second order function of the inverse of the distortion measure. We presented a closed form solution for the target bit allocation which applies to both the digital storage media (DSM) applications (e.g., MPEG-2) and very low bit rate (VLBR) applications (e.g., MPEG-4). We perform experiments on a wavelet-based coder to demonstrate the versatility of our scheme. Model parameters are estimated using statistical linear regression analysis. Since the estimation uses the past encoded frames of the same picture prediction type (I, P and B pictures), the proposed approach is a single pass rate control technique. For the MPEG-2 coder the fluctuations of the bit counts are significantly reduced by 20 percent to 65 percent in the standard deviation of the bit count while the picture quality remains the same. For the MPEG-4 VM coder, the PSNR is improved by almost one dB as compared to the best MPEG-4 VM rate control using exhaustive combinations of quantization scale parameters.

In this paper, we discuss the coding strategy when a two-layer digital HDTV service is considered. We propose to use-three different strategies in performing compression to yield the best quality based on the respective requirements on bandwidth, picture quality and efficiency. These three modes are as follows. Strategy A: if the bandwidth for the enhancement layer is not sufficient to achieve high quality, the base layer encoder should perform the compression at a reduced spatial resolution using the combined bandwidth. The top layer video signal will be obtained from upsampling the base layer. Strategy B: if the bandwidth is sufficient to support quality requirements at both layers, the typical two-layer spatial scalable coding scheme is used. Strategy C: if the quality requirement at the top layer is critical, a single layer compression at a full spatial resolution is used. To receive the low resolution signal, certain bit stream scaling can be used to get a usable quality signal. A theoretical qualitative analysis gives an insight of our experimental results. Such a strategy is useful in designing future HDTV services for television sets with different capabilities, resolutions and complexities. The results are also applicable to the problem of HDTV/standard TV compatibility.

A two-layer coding approach with a spatial pyramid to achieve compatibility has been known to have several advantages. The first layer can have optimal performance. Rate control can be distributed between layers. However, the compression performance and the overall complexity at the high resolution layer suffer because of the requirement of compatibility. Therefore, good compatibility prediction is a crucial factor for a spatial scalability approach. In the paper, the authors focus on obtaining the best compatibility prediction, assuming that a spatially upsampled block and a motion compensated block are available. A spatio-temporal averaging technique has been shown to provide improvement. With a linear regression analysis, further improvement in prediction is shown. Better compatibility prediction can be obtained by assigning the spatio-temporal weights adaptively for individual pixels. The authors found that a pel-adaptive recursive estimation using Kalman filters gives a good compatibility prediction. The new difference signal has the statistical property of white Gaussian noise. The additional complexity is moderate and the bits for sending side information is insignificant. The resultant picture quality of the approach approximates the picture quality of the noncompatible single-layer approach.>