This paper considers the problem of selecting a set of parameter values from a given parameter space, in order to perform rate-distortion optimization in the context of audio compression. Due to interdependencies between parameters, separate optimization of parameter values is inherently suboptimal, yet a straightforward brute-force joint search involves prohibitive computational complexity. This work proposes a new method for joint rate-distortion optimization, while accounting for interparameter dependencies. The optimal solution is achieved, at significantly reduced complexity as compared to a brute-force search, by employing a Viterbi search over a trellis. Two objective distortion metrics are specifically considered: the average, and the maximum noise-to-mask ratio. Subjective (AB/MOS) and objective (average/maximum noise-to-mask ratio) tests demonstrate considerable gains at low bit rates of 16 kbps per channel for a 44.1-kHz sampled audio signal using the proposed approach.

We propose two quantization techniques for improving the bit-rate scalability of compression systems that optimize a weighted squared error (WSE) distortion metric. We show that quantization of the base-layer reconstruction error using entropy-coded scalar quantizers is suboptimal for the WSE metric. By considering the compandor representation of the quantizer, we demonstrate that asymptotic (high resolution) optimal scalability in the operational rate-distortion sense is achievable by quantizing the reconstruction error in the compandor's companded domain. We then fundamentally extend this work to the low-rate case by the use of enhancement-layer quantization which is conditional on the base-layer information. In the practically important case that the source is well modeled as a Laplacian process, we show that such conditional coding is implementable by only two distinct switchable quantizers. Conditional coding leads to substantial improvement over the companded scalable quantization scheme introduced in the first part, which itself significantly outperforms standard techniques. Simulation results are presented for synthetic memoryless Laplacian sources with mu-law companding, and for real-world audio signals in conjunction with MPEG AAC. Using the objective noise-mask ratio (NMR) metric, the proposed approaches were found to result in bit-rate savings of a factor of 2 to 3 when implemented within the scalable MPEG AAC. Moreover, the four-layer scalable coder consisting of 16-kb/s layers achieves performance close to that of the 64-kb/s nonscalable coder on the standard test database of 44.1-kHz audio

This paper describes the construction of computationally efficient transforms which can significantly reduce the complexity of a video decoder without loss in compression efficiency. In particular, these inverse transforms can be implemented using purely 16-bit arithmetic with similar rate-distortion performance to a 32-bit or floating point transform. To allow for variable block size coding, four 2D transforms are considered: one each for 8&8, 8&4, 4&8 and 4&4 blocks respectively. The design criteria for a pure 16 bit arithmetic implementation of the inverse transform are introduced, and used to derive the only useful set of transforms under these conditions. These transforms have been used in the WMV9/VC-1 codec to achieve significant reduction in computational complexity.

Video standards make use of a video complexity verifier (VCV) to characterize and regulate the decoding complexity of a compliant bitstream. In previous VCV models, the minimum level of computational capacity required to decode a given bitstream is strictly related to the peak decoding complexity of an individual frame in the sequence. This contribution presents a new VCV model, which is more flexible than prior VCV models. The proposed VCV model permits the bitstream to be decoded by devices operating at significantly smaller levels of peak computational capacity. The trade-off is a slight increase in additional delay and memory. Simulation results illustrate these benefits of the new VCV model.

In video coding standards, a compliant bit stream must be decoded by a hypothetical decoder that is conceptually connected to the output of an encoder and consists of a decoder buffer, a decoder, and a display unit. This virtual decoder is known as the hypothetical reference decoder (HRD) in H.263 and the video buffering verifier in MPEG. The encoder must create a bit stream so that the hypothetical decoder buffer does not overflow or underflow. These previous decoder models assume that a given bit stream will be transmitted through a channel of a known bit rate and will be decoded (after a given buffering delay) by a device of some given buffer size. Therefore, these models are quite rigid and do not address the requirements of many of today's important video applications such as broadcasting video live or streaming pre-encoded video on demand over network paths with various peak bit rates to devices with various buffer sizes. In this paper, we present a new HRD for H.264/AVC that is more general and flexible than those defined in prior standards and provides significant additional benefits.

The design of vector quantizers for diversity-based communication over two or more channels of possibly differing capacities and failure probabilities, is considered. The crucial dependence of current design techniques on initialization, especially of index assignment, is well recognized. Instead, we propose to pursue a deterministic annealing approach which is independent of initialization, does not assume any prior knowledge of the source density, and avoids many poor local minima of the cost surface. The approach consists of iterative optimization of a random encoder at gradually decreasing levels of randomness as measured by the Shannon entropy. At the limit of zero entropy, a hard multiple description (MD) quantizer is obtained. This process is directly analogous to annealing processes in statistical physics. Via an alternative derivation, we show that it may also be interpreted as approximating the minimum rate sums among points on the convex hull of the MD achievable rate-distortion region of El Gamal and Cover, subject to constraints on the sizes of the reproduction alphabets. To illustrate the potential of our approach, we present simulation results that show substantial performance gains over existing design techniques.

Let (X,Y) be a pair of random variables distributed over a finite product set V/spl times/W according to a probability distribution P(x,y). The following source coding problem is considered: the encoder knows X, while the decoder knows Y and wants to learn X without error. The minimum zero-error asymptotic rate of transmission is shown to be the complementary graph entropy of an associated graph. Thus, previous results in the literature provide upper and lower bounds for this minimum rate (further, these bounds are tight for the important class of perfect graphs). The algorithmic aspects of instantaneous code design are considered next. It is shown that optimal code design is NP-hard. An optimal code design algorithm is derived. Polynomial-time suboptimal algorithms are also presented, and their average and worst case performance guarantees are established.

The problem of separate zero-error coding of correlated sources is considered. Inner and outer single-letter bounds are established for the achievable rate region, and conditions for their coincidence are investigated. It is shown that successive encoding combined with time sharing is not always an optimal coding strategy. Conditions for its optimality are derived. The inner bound to the achievable rate region follows as a special case of the single-letter characterization of a generalized zero-error multiterminal rate-distortion problem. The applications of this characterization to a problem of remote computing are also explored. Other results include (i) a product-space characterization of the achievable rates, (ii) bounds for finite block length, and (iii) asymptotic fixed-length rates.

Let finite source and reproduction alphabets X and Y and a distortion measure d: X/spl times/Y/spl rarr/[0,/spl infin/) be given. We study the minimum asymptotic rate required to describe a source distributed over X within a (given) distortion threshold D at every sample. The problem is hence a min-max problem, and the distortion measure is extended to vectors as follows: for x/sup n//spl isin/X/sup n/, y/sup n//spl isin/Y/sup n/, d(x/sup n/, y/sup n/)=max/sub i/d(x/sub i/, y/sub i/). In the graph-theoretic formulation we introduce, a code for the problem is a dominating set of an equivalent distortion graph. We introduce a linear programming lower bound for the minimum dominating set size of an arbitrary graph, and show that this bound is also the minimum asymptotic rate required for the corresponding source. Turning then to the optimality of scalar coding, we show that scalar codes are asymptotically optimal if the underlying graph is either an interval graph or a tree.

Video coding standards require that a compliant bit stream be decodable by a hypothetical decoder that is conceptually connected to the output of an encoder and consists of a decoder buffer, a decoder, and a display unit. The encoder must create a bit stream so that the hypothetical decoder buffer does not overflow or underflow. Previous decoder models assume that a given bit stream will be transmitted through a channel of a given constant bit rate and will be decoded (after a given buffering delay) by a device of some given buffer size. Therefore, these models are quite rigid and do not address the requirements of many of today's important video applications such as broadcasting live video or streaming pre-encoded video on demand over network paths with various peak bit rates to devices with various buffer sizes. In this contribution, we present a new hypothetical reference decoder for JVT that is more general and flexible than those defined in prior standards and provides significant additional benefits.

This paper is concerned with adaptive and robust video streaming over lossy networks. A general system is described which is compatible with virtually all application settings. The delivery procedure is optimized within a rate-distortion framework with the aid of an efficient real-time end-to-end distortion estimation algorithm. The estimate fully accounts for the effects of (prior) quantization, packet loss and error propagation, as well as error concealment. It features high accuracy and low complexity, and requires a small amount of pre-computed side information. It is shown that various error-resilient schemes can be optimized within the proposed framework. In particular, unequal error protection through forward error control is employed in the simulations to demonstrate the achievable performance gains.

We derive an asymptotically optimal multi-layer coding scheme for entropy-coded scalar quantizers (SQ) that minimizes the weighted mean-squared error (WMSE). The optimal entropy-coded SQ is non-uniform in the case of WMSE. The conventional multi-layer coder quantizes the base-layer reconstruction error at the enhancement-layer, and is sub-optimal for the WMSE criterion. We consider the compander representation of the quantizer, and propose to implement scalability in the compressed domain. We show that such a multi-layer coding system achieves the operational rate-distortion bound given by the non-scalable entropy-coded SQ, at the limit of high resolution. Simulation results for a synthetic memoryless Laplace source with /spl mu/-law companding are presented for various values of layer rates. Substantial gains are also achieved on the "real-world" sources of audio signals, when the optimal multi-layer approach is applied to a two-layer scalable MPEG-4 Advanced Audio Coder.

We address the issue of optimizing side information rate for efficient audio coding. In coders such as the MPEG-4 AAC, at rates around 16 kbps to 48 kbps, the side information rate forms a substantial part of the total rate. The parameter search procedure in the verification model optimizes each band separately and results in poor performance at low rates. We propose to jointly optimize the encoding parameter of all the bands. The near-optimal solution using a brute force search has drastic computational complexity. However, the same solution is obtained at a much reduced complexity using a Viterbi search through a trellis. The search procedure is developed and evaluated for two objective measures, the average and the maximum noise-mask ratio. For both the measures, the trellis-based search yields substantially better solutions. In particular, trellis-based optimization of maximum noise-mask ratio greatly improves the performance of AAC at low rates. The resulting bit stream is standard-compatible, and the additional complexity due to the proposed optimization is only incurred at the encoder.

In standard predictive video coders, intra-mode coding of macroblocks (MBs) provides packet loss resilience, at the cost of reduced compression efficiency. Conventional mode selection algorithms are "greedy" as they focus on minimization of distortion of current MB, while ignoring the effect of this selection on subsequent frames. This paper proposes an algorithm for prescient mode selection: the coding modes of MBs are chosen while taking into account the distortion of subsequent frames. The problem is formulated as one of joint selection of MB coding modes, for a group of pictures, so as to minimize the rate-distortion cost. The straightforward solution based on dynamic programming requires enormous computational complexity. We propose an iterative algorithm which obtains a locally optimal solution at feasible complexity. The total decoder distortion is computed using recursive optimal per-pixel estimate (ROPE) which accurately accounts for the effects of quantization, packet loss, error propagation, and error concealment. Simulation results show consistent improvement over our previous "greedy" ROPE-RD mode selection, and substantial gains over other (non-ROPE) mode selection schemes.

The basic vector quantization (VQ) technique employed in video coding belongs to the category of predictive vector quantization (PVQ), as it involves quantization of the (motion compensated) frame prediction error. It is well known that the design of PVQ suffers from fundamental difficulties, due to the prediction loop, which have an impact on the convergence and the stability of the design procedure. We propose an approach to PVQ design that enjoys the stability of open-loop design while it ensures ultimate optimization of the closed-loop system. The method is derived for general predictive quantization, and we demonstrate it on video compression at low bit rates, where it provides substantial improvement over standard open and closed loop design techniques. Further, the approach outperforms standard DCT-based video coding.

A method is proposed for efficient scalability in predictive coding, which overcomes known fundamental shortcomings of the prediction loop at enhancement layers. The compression efficiency of an enhancement-layer is substantially improved by casting the design of its prediction module within an estimation-theoretic framework, and thereby exploiting all information available at that layer for the prediction of the signal, and encoding of the prediction error. While the most immediately important application is in video compression, the method is derived in a general setting and is applicable to any scalable predictive coder. Thus, the estimation-theoretic approach is first developed for basic DPCM compression and demonstrates the power of the technique in a simple setting that only involves straightforward prediction, scalar quantization, and entropy coding. Results for the scalable compression of first-order Gauss-Markov and Laplace-Markov signals illustrate the performance. A specific estimation algorithm is then developed for standard scalable DCT-based video coding. Simulation results show consistent and substantial performance gains due to optimal estimation at the enhancement-layers.

Robustness to packet loss is a critical requirement for video communication over packet switched networks. Intra-coding is an important tool to mitigate the effects of packet loss by limiting error propagation. This work proposes an algorithm for intra/inter coding mode selection, while utilizing the feedback channel that carries acknowledgement information about received packets. The overall distortion in frame reconstruction at the decoder due to quantization, error concealment (after packet loss) and error propagation is estimated at pixel-level precision, and is dynamically refined based on the feedback information. The estimate is then integrated into a rate-distortion (RD) framework for optimal selection of coding mode for each macroblock. Simulation results demonstrate that precise distortion estimation enables the coder to achieve substantial and consistent gain in PSNR over known state-of-the-art feedback-based mode selection modes.

This work is concerned with the design of multiple description (MD) compression systems with emphasis on video coding. Although inter-frame prediction is critical to the performance of video coders, the problem of efficient prediction in MD systems has not been satisfactorily resolved. We focus on quantizer based MD coding and propose an estimation theoretic (ET) approach to prediction and reconstruction. The advantage of ET prediction is two fold: (1) It takes into account all the information available at each decoder for an optimal estimate; (2) It mitigates the degradation due to quantization in the prediction feedback loop. The ET approach is first shown to achieve significant gains in the simpler setting of predictive MD coding of synthetic Gauss-Markov and Laplace-Markov processes. We then present performance results for MD compression of video sequences and demonstrate consistent and substantial PSNR gains over conventional techniques.

This work introduces two complementary techniques to improve the packet loss resilience of scalable video coding systems. First, a "switch per-pixel" error concealment (SPEC) scheme is proposed, which allows the decoder to exploit information from both the current base layer and previous enhancement-layer frame for the reconstruction of missing enhancement-layer blocks. Based on the packet loss history and the quantized base-layer data, the algorithm switches per pixel between the two information sources. SPEC is shown to consistently outperform standard concealment methods. The second main contribution is concerned with encoder decision optimization. Enhancement layer prediction modes are selected so as to minimize the overall decoder reconstruction distortion, which is due to quantization, packet loss and error propagation. The distortion computation uses a recursive optimal per-pixel estimate (ROPE) to accurately account for the effects of error concealment as well as spatial and temporal error propagation. Simulation results show that ROPE-based mode selection substantially outperforms conventional prediction mode selection schemes. Finally, the combination of SPEC at the decoder and ROPE-based mode selection at the encoder is shown to achieve significant additional performance gains.

Resilience to packet loss is a critical requirement in predictive video coding for transmission over packet-switched networks, since the prediction loop propagates errors and causes substantial degradation in video quality. This work proposes an algorithm to optimally estimate the overall distortion of decoder frame reconstruction due to quantization, error propagation, and error concealment. The method recursively computes the total decoder distortion at pixel level precision to accurately account for spatial and temporal error propagation. The accuracy of the estimate is demonstrated via simulation results. The estimate is integrated into a rate-distortion (RD)-based framework for optimal switching between intra-coding and inter-coding modes per macroblock. The cost in computational complexity is modest. The framework is further extended to optimally exploit feedback/acknowledgment information from the receiver/network. Simulation results both with and without a feedback channel demonstrate that precise distortion estimation enables the coder to achieve substantial and consistent gains in PSNR over known state-of-the-art RD- and non-RD-based mode switching methods.

A new method is proposed for efficient SNR scalability in predictive video coding. It is of low complexity, and it is applicable to standard DCT-based video compression with motion compensation. Information that is only available to the enhancement layers is exploited to improve the quality of their frame prediction without compromising the usefulness of the compressed data provided by the base layer(s). More specifically, the next frame prediction for use by an enhancement-layer decoder is obtained by combining, or switching between transform coefficients from: i) the reconstructed base-layer frame; and ii) the predicted enhancement-layer frame. The combining rule depends on the compressed residual of the base layer, and on the parameters used for this compression. The method is applied to standard DCT-based predictive video coding, and preliminary simulation shows consistent, substantial improvement in the performance of enhancement layers. The proposed method may be easily combined with known temporal scalability methods to provide further improvement of the performance of enhancement layers over a wide range of bit rates.

In this paper, we propose a bit-stream packetization approach to make the MPEG-4 still texture bit-stream robust to channel degradation. Our approach does not affect the spatial/quality scalability features of the still texture algorithm, and it has limited effect on coding efficiency. Also, this packetization approach requires minimal changes to the syntax and a small overhead. Finally, the proposed technique is shown to provide good error robustness over a wide range of error conditions.

We attack the problem of robust and efficient image compression for transmission over noisy channels. To achieve the dual goals of high compression efficiency and low sensitivity to channel noise we introduce a multimode coding framework. Multimode coders are quasi-fixed length in nature, and allow optimization of the tradeoff between the compression capability of variable-length coding and the robustness to channel errors of fixed length coding. We apply our framework to develop multimode image coding (MIC) schemes for noisy channels, based on the adaptive DCT. The robustness of the proposed MIC is further enhanced by the incorporation of a channel protection scheme suitable for the constraints on complexity and delay. To demonstrate the power of the technique we develop two specific image coding algorithms optimized for the binary symmetric channel. The first, MIC1, incorporates channel optimized quantizers and the second, MIC2, uses rate compatible punctured convolutional codes within the multimode framework. Simulations demonstrate that the multimode coders obtain significant performance gains of up to 6 dB over conventional fixed length coding techniques.

We attack the problem of designing robust image compression schemes for transmission over noisy channels. To achieve the dual goals of high compression efficiency and low sensitivity to channel noise, we introduce a multimode coding framework. Multimode coders are quasi-fixed length in nature, and this enables optimal tradeoff between the compression capability of variable-length coding and the robustness of fixed length coding. The framework lends itself to a natural incorporation of conventional source-channel coding mechanisms, and thus provides a joint design methodology for the source and channel coding components. We first derive a general Lagrangian based algorithm to design the multimode coder which optimizes the overall rate-distortion performance. We then apply our framework to develop multimode image coding (MIC) schemes for noisy channels. We demonstrate the benefits of the multimode approach by developing two specific image compression algorithms in conjunction with the following source-channel coding mechanisms: (i) channel optimized quantizers, and (ii) transmission energy allocation. Simulations demonstrate that substantial gains of up to 7 dB can be achieved by MICs over conventional approaches.

Motion compensation is formulated as quantization of the true motion field and optimized within an overall rate-distortion framework. The desired accuracy in motion estimation is achieved by designing the codebook of the motion quantizer for the target rate. We propose an iterative algorithm for the codebook design which optimizes the compression performance of the coder by directly minimizing the overall rate-distortion cost. A multistage structure is imposed on the codebook to obtain a practical motion quantization scheme, which is optimized through a joint design of the stages. Simulation results on video sequences are presented which demonstrate that RD optimized motion vector quantization outperforms conventional motion compensation and can achieve significant gains of 1.3 dB in the PSNR of the reconstructed picture. Further, the multiresolution nature of multistage motion quantization makes it applicable for scalable video coding applications.

We focus on the design of robust video compression schemes for transmission over noisy channels. A multimode video coding framework is introduced, which enables optimizing the tradeoff between the conflicting objectives of high compression efficiency and error resilience. The starting point is a simple block-based predictive coder, with no motion compensation, for which we develop the robust multimode video compression scheme. The proposed iterative design algorithm for multimode video coders directly minimizes the overall rate-distortion cost. We show that several conventional joint source-channel coding mechanisms can be incorporated within a multimode scheme to further enhance the video coder performance. Simulation results of compressing benchmark video sequences for transmission over noisy channel conditions are presented. They demonstrate that multimode coders outperform conventional fixed length approaches and can achieve substantial gains of more than 6 dB in PSNR of the reconstructed picture.