This paper revisits the problem of rate distortion optimization (RDO) with focus on inter-picture dependence. A joint RDO framework which incorporates the Lagrange multiplier as one of parameters to be optimized is proposed. Simplification strategies are demonstrated for practical applications. To make the problem tractable, we consider an approach where prediction residuals of pictures in a video sequence are assumed to be emitted from a finite set of sources. Consequently the RDO problem is formulated as finding optimal coding parameters for a finite number of sources, regardless of the length of the video sequence. Specifically, in cases where a hierarchical prediction structure is used, prediction residuals of pictures at the same prediction layer are assumed to be emitted from a common source. Following this approach, we propose an iterative algorithm to alternatively optimize the selections of quantization parameters (QPs) and the corresponding Lagrange multipliers. Based on the results of the iterative algorithm, we further propose two practical algorithms to compute QPs and the Lagrange multipliers for the RA(random access) hierarchical video coding: the first practical algorithm uses a fixed formula to compute QPs and the Lagrange multipliers, and the second practical algorithm adaptively adjusts both QPs and the Lagrange multipliers. Experimental results show that these three algorithms, integrated into the HM 16.20 reference software of HEVC, can achieve considerable RD improvements over the standard HM 16.20 encoder, in the common RA test configuration.

Soft decision quantization (SDQ) is an efficient tool for video coding to achieve coefficient-level rate-distortion optimized quantization (RDOQ) with a 6%-8% bit rate saving. However, the software and hardware implementations of SDQ suffer from either high complexity or low throughput capacity due to complex Viterbi trellis search and sequential processing in context-adaptive binary arithmetic coding. In this paper, a fast SDQ algorithm is proposed to decrease the number of trellis stages to decrease the complexity and to break the data dependency in optimal SDQ. First, preselection is performed according to hard decision quantization results by intelligent coding cost estimation and comparison, during which some coefficients are judged to be safely excluded from trellis search, resulting in considerable complexity reduction. Second, a dynamic trellis graph with flexible structure is constructed according to the unsafe nonzero coefficients to accelerate the remaining partial Viterbi search. Third, a dynamic threshold selection model is proposed for adaptive thresholding to increase the probability of right preselection under a constraint on a predefined maximal probability of wrong preselection. The experimental results show that compared with optimal SDQ, the proposed algorithm can at least reduce the computation complexity by 50%-80%, memory accesses by 75%-82%, and the sequential processing latency in hardware implementation by 87.25%, with less than 0.4% Bjøntegaard bit rate increment when a maximum of three unsafe coefficients are kept for trellis search in one block. This paper is suitable for high-throughput hardware and computation-sensitive software implementations for SDQ and RDOQ for H.264/Advanced Video Coding and High Efficiency Video Coding standards.

The distributions of discrete cosine transform (DCT) coefficients of images are revisited on a per image base. To better handle, the heavy tail phenomenon commonly seen in the DCT coefficients, a new model dubbed a transparent composite model (TCM) is proposed and justified for both modeling accuracy and an additional data reduction capability. Given a sequence of the DCT coefficients, a TCM first separates the tail from the main body of the sequence. Then, a uniform distribution is used to model the DCT coefficients in the heavy tail, whereas a different parametric distribution is used to model data in the main body. The separate boundary and other parameters of the TCM can be estimated via maximum likelihood estimation. Efficient online algorithms are proposed for parameter estimation and their convergence is also proved. Experimental results based on Kullback-Leibler divergence and χ(2) test show that for real-valued continuous ac coefficients, the TCM based on truncated Laplacian offers the best tradeoff between modeling accuracy and complexity. For discrete or integer DCT coefficients, the discrete TCM based on truncated geometric distributions (GMTCM) models the ac coefficients more accurately than pure Laplacian models and generalized Gaussian models in majority cases while having simplicity and practicality similar to those of pure Laplacian models. In addition, it is demonstrated that the GMTCM also exhibits a good capability of data reduction or feature extraction-the DCT coefficients in the heavy tail identified by the GMTCM are truly outliers, and these outliers represent an outlier image revealing some unique global features of the image. Overall, the modeling performance and the data reduction feature of the GMTCM make it a desirable choice for modeling discrete or integer DCT coefficients in the real-world image or video applications, as summarized in a few of our further studies on quantization design, entropy coding design, and image understanding and management.

This paper aims to tackle theoretical modeling and dimension reduction, two fundamental issues in large scale image/video data processing, together, by proposing a transparent composite model (TCM) for transformed image/video data. Specifically, to handle the heavy tail phenomenon commonly seen in Discrete Cosine Transform (DCT) coefficients of image/video data, a TCM first separates the tail of a sequence of DCT coefficients from the main body of the sequence. Then, a parametric distribution is used to model the main body while a uniform distribution is used to model the tail. Efficient online algorithms for establishing a TCM are proposed and proved to converge exponentially fast, which suits large-scale image/video data processing. It is also demonstrated that a TCM has an inherent non-linear data reduction capability - DCT coefficients of an image in the heavy tail identified by a TCM reveal some unique global features of the image while being insignificant statistically. This, together with its fast convergence, makes the proposed model a desirable choice for modeling DCT coefficients in large-scale image/video applications, such as online quantization design, entropy coding design, and image/video analytics in Big Data.

High Efficiency Video Coding (HEVC) is the next-generation video coding standard currently under development, which has demonstrated substantial bit savings (rate reduction by approximately half) compared to H.264/AVC. This paper presents the multiple sign bits hiding scheme that was adopted into the committee draft of HEVC at the 8th JCT-VC meeting. In HEVC, the quantized transform coefficients are entropy-coded in groups of 16 coefficients for each transform unit. With multiple sign bits hiding, for coefficient groups that satisfy certain conditions, the sign of the first non-zero coefficient along the scanning path is not explicitly transmitted in the bitstream and instead is inferred from the parity of the sum of all non-zero coefficients in that coefficient group at the decoder. To ensure the matching between the hidden sign and the parity of the sum of all non-zero coefficients, a parity adjustment method is employed at the encoder based on rate-distortion optimization or distortion minimization. Compared with conventional video coding schemes where quantization and coefficient coding are separately designed, the multiple sign bits hiding scheme in HEVC represents a joint quantization and coefficient coding design and provides consistent rate-distortion performance gains for all standard test sequences under standard test conditions.

This paper considers the problem of downsampling H.264 compressed video, where a full-resolution compressed video sequence conforming to H.264 is transcoded into another compressed video sequence conforming to H.264 at a lower target resolution. A transcoding framework that makes efficient use of full-resolution information is proposed. In this framework, residuals and motion vectors at the target resolution are first predicted from their full-resolution counterparts. These predicted residuals and motion vectors are then applied to optimize the actual rate-distortion (RD) performance. Experimental results show that, compared against the benchmark system, which cascades an H.264 decoder, a spatial downsampler, and an H.264 encoder, and is generally regarded having the best possible RD performance, the proposed framework, surprisingly, provides consistently superior RD performance with up to 0.7 dB gain. Furthermore, the framework has the desired feature of being configurable to strike the right balance between rate-distortion performance and computational complexity according to application requirements.

This paper studies the design and analysis of multiresolution vector quantization (MRVQ) for broadcast channels. Given a broadcast system with MRVQ, a random index assignment, and a coded broadcast channel, we first obtain a closed-form formula for the weighted end-to-end distortion (EED) of the system. Based on the formula, an iterative algorithm is then proposed for designing optimal MRVQ for the broadcast system. Experimental results demonstrate that multiresolution quantizers jointly designed with channel conditions by the proposed algorithm significantly reduce the weighted EED in comparison with multiresolution quantizers designed without reference to channel conditions.

This paper studies the design of vector quantization on noisy channels and its high rate asymptotic performance. Given a tandem source-channel coding system with vector quantization, block channel coding, and random index assignment, a closed-form formula is first derived for computing the average end-to-end distortion (EED) of the system, which reveals a structural factor called the scatter factor of a noisy channel quantizer. Based on this formula, we propose a noisy-channel quantization design method by minimizing the EED. Experiments and simulations show that quantizers jointly designed with channel conditions significantly reduce the EED when compared with quantizers designed separately without reference to channel conditions, which reveals a practical and effective design for noisy-channel quantization as to simplify the channel model by considering a random index assignment. Furthermore, we have presented the high rate asymptotic analysis of the EED for the tandem system, while convergence analysis of the iterative algorithm is included in the Appendix.

Quantization in H.264 is achieved in the DCT domain using scalar quantizers, which assume a sum distortion constraint and often produce considerably larger distortions on block boundaries than inside a block in the pixel domain. This biased distortion distribution degrades the rate distortion (RD) performance of H.264 intra coding whose prediction is exclusively based on boundary pixels. This paper considers the problem of designing balanced distortion quantizers (BDQs) in the DCT domain, which, in addition to the sum distortion constraint, require evenly distributed distortions in the pixel domain. In a special case where DCT coefficients are independent Gaussian, the problem is solved as a convex optimization problem. Using this approach, we design BDQs and apply them to improve H.264 intra coding. Experimental results on typical frames show that the improved intra coding scheme consistently outperforms its counterpart in H.264 main-profile, averaging 5–9% rate reduction for QCIF frames, and 7–12% for CIF frames with aligned distortions.

This paper introduces a cross-layer design framework for robust and efficient video multicasting over IEEE 802.16 (also known as WiMAX) networks in metropolitan areas. In the framework, multiple description coding (MDC) on scalable video bitstreams at the source for achieving multiresolution robustness is jointly designed with superposition coding (SCM) on multicast signals at the channel to overcome multiuser channel diversity in wireless multicast. The coded multicast signals under the proposed framework can cope with multiuser channel diversity and mitigate the impact due to short-term channel fluctuations, which are the two most challenging issues in achieving robust and efficient video multicasting in metropolitan areas. We formulate the proposed framework and analyze its video quality performance in terms of the total receivable/ recoverable bitstreams by a receiver. A heuristic methodology is developed for system parameter selection and performance optimization that can be applied to practical scenarios of video multicasting for IPTV services in WiMAX. Simulation is conducted based on actual standard video sequences to verify the proposed methodology on parameter selection and performance optimization. Performance gains of the proposed cross-layer design framework in the presence of fading channel diversity are demonstrated.

In this paper, we study the rate-distortion (RD) optimization of the H.264 main profile encoding. Specifically, a soft decision quantization (SDQ) algorithm is developed based on the context adaptive binary arithmetic coding (CABAC) method in the H.264 main profile. Given motion prediction and quantization step sizes, the proposed SDQ algorithm is proved to achieve near-optimal SDQ for residual coding in the sense of minimizing the true RD cost when the weak adjacent block dependency utilized in CABAC is ignored for optimization. The SDQ algorithm is then used in conjunction with a general RD optimization framework to jointly design motion prediction and residual coding for H.264 main profile coding given previously coded reference frames. Experiments have been conducted based on the reference encoder JM82 of H.264 main profile. Comparative studies show that the joint design method achieves on average 10% rate reduction at the same PSNR when compared with the RD method in the H.264 main-profile reference software, with half of the reduction coming from the proposed SDQ algorithm, and 20% rate reduction at the same PSNR when compared with the RD method in the H.264 baseline-profile reference software.

This paper proposes a designing framework for down-sampling compressed images/video with arbitrary ratio in the discrete cosine transform (DCT) domain. In this framework, we first derive a set of DCT-domain down-sampling methods which can be represented by a linear transform with double-sided matrix multiplication (LTDS) in the DCT domain and show that the set contains a wide range of methods with various complexity and visual quality. Then, for a preselected spatial-domain down-sampling method, we formulate an optimization problem for finding an LTDS to approximate the given spatial-domain down-sampling method for a trade-off between the visual quality and the complexity. By modeling LTDS as a multiple layer network, a so-called structural learning with forgetting algorithm is then applied to solve the optimization problem. The proposed framework has been applied to discover optimal LTDSs corresponding to a spatial down-sampling method with Butterworth low-pass filtering and bicubic interpolation. Experimental results show that the resulting LTDS achieves a significant reduction on the complexity when compared with other methods in the literature with similar visual quality.

This paper proposes a designing framework for downsampling compressed images/video frames with arbitrary ratio in the discrete cosine transform (DCT) domain. We first derive a set of DCT-domain down-sampling methods which can be represented by a linear transform with double-sided matrix multiplication (LTDS) in the DCT domain, and show that the set contains a wide range of methods with various complexity and visual quality. Then, based on a pre-selected spatial- domain method, we formulate an optimization problem for finding an LTDS to approximate the given spatial domain method for achieving the best trade-off between the visual quality and the complexity. By selecting a spatial-domain reference method with the popular Butterworth lowpass filtering and bicubic interpolation, the proposed framework discovers LTDSs with better visual quality and lower computational complexity as saving 20%~70% execution time when compared with state-of-the-art methods in the literature.

This paper studies the design of vector quantization (VQ) on noisy channels and its asymptotic performance analysis. Given a tandem source-channel coding system with VQ and block channel coding, we derive a closed-form formula of the average end-to-end distortion (EED), which reveals a structural factor called the scatter factor for noisy channel quantizers. Based on this formula, an iterative algorithm is developed for jointly designing optimal quantizers with channel conditions. Simulations show that quantizers that are jointly designed with channel conditions significantly reduce the EED when compared with quantizers that are designed separately from channel conditions. Indeed, our asymptotic analyses show that the infimum of the mean squared EED over all possible quantizers with joint quantization design is perrsigma2, where perris the average transmission error probability of the channel and sigma2is the component variance of the source. This is 4.77dB better than that with separate quantization design for an i.i.d. Guassian source.

A cross-layer design (CLD) framework for robust and efficient video multicasting over IEEE 802.16 (or WiMAX) is introduced. In the framework, multiple description coding on scalable video bitstreams at the source for achieving multi-resolution robustness is jointly designed with superposition coding (i.e., multi-resolution modulation) on multicast signals at the channel to overcome the channel diversity problem in wireless multicast. The resulting cross-layer coded multicast signals enable us to recover some lost bitstreams in high quality layers, which is not possible if multi-resolution modulation is used alone for multicasting as in previous works. Simulation results show that indeed our joint design outperforms the scheme using only superposition coded multicast by achieving better video quality for users under multi-user channel diversity.

Motivated by the wide adoption of H.264 and the demand of universal multimedia data access over the expanding network with diverse devices, this paper studies H.264-based video transcoding with spatial resolution conversion. First, a practical solution for efficiently determining a reference frame is proposed to take advantage of the new feature of multiple references in H.264. Then, a motion vector estimation algorithm based on a multiple linear regression model is proposed to utilize the motion information in the original scenes for efficiently predicting motion vectors in the down-scaled scene. Experimental results show that, compared with a benchmark solution, the proposed method significantly reduces the transcoding complexity by 16 times while maintaining comparable rate distortion performance with a decrease of 0.06 dB in PSNR and 4% increase in the bit rate.

Rate distortion (RD) optimization for H.264 interframe coding with complete baseline decoding compatibility is investigated on a frame basis. Using soft decision quantization (SDQ) rather than the standard hard decision quantization, we first establish a general framework in which motion estimation, quantization, and entropy coding (in H.264) for the current frame can be jointly designed to minimize a true RD cost given previously coded reference frames. We then propose three RD optimization algorithms--a graph-based algorithm for near optimal SDQ in H.264 baseline encoding given motion estimation and quantization step sizes, an algorithm for near optimal residual coding in H.264 baseline encoding given motion estimation, and an iterative overall algorithm to optimize H.264 baseline encoding for each individual frame given previously coded reference frames-with them embedded in the indicated order. The graph-based algorithm for near optimal SDQ is the core; given motion estimation and quantization step sizes, it is guaranteed to perform optimal SDQ if the weak adjacent block dependency utilized in the context adaptive variable length coding of H.264 is ignored for optimization. The proposed algorithms have been implemented based on the reference encoder JM82 of H.264 with complete compatibility to the baseline profile. Experiments show that for a set of typical video testing sequences, the graph-based algorithm for near optimal SDQ, the algorithm for near optimal residual coding, and the overall algorithm achieve on average, 6%, 8%, and 12%, respectively, rate reduction at the same PSNR (ranging from 30 to 38 dB) when compared with the RD optimization method implemented in the H.264 reference software.

Using soft decision quantization rather than the conventional hard decision quantization, this paper studies a joint rate distortion design of motion prediction, quantization and entropy coding for the H.264 main profile encoding. Specifically, a soft decision quantization algorithm is proposed based on the context adaptive binary arithmetic coding method in H.264. The proposed algorithm is proved to achieve optimal soft decision quantization for a block with given motion prediction and quantization step size in the sense of minimizing the true rate distortion cost. It is then used in jointly designing motion prediction and residual coding for H.264 main profile coding. Experiments have been conducted based on the reference encoder JM82 of H.264. Comparative studies show that the proposed joint design method achieves an average 10% rate reduction while maintaining the same quality over the rate distortion method in the reference software of H.264

The paper presents a framework for jointly designing motion compensation, quantization and entropy coding in a hybrid video coding structure to minimize a rate distortion cost. Given motion compensation, a soft decision-based quantization algorithm is first designed to reduce the rate distortion cost by adapting quantization outputs to the baseline entropy coding method in the newest standard H.264. Motion compensation is then optimized by searching for a prediction to reduce the rate distortion cost further based on given quantization outputs. By alternating these two steps, an iterative method is then proposed. The proposed algorithms have been implemented based on the reference encoder of H.264 with complete baseline decoder compatibility. Comparative studies show that the baseline-based iterative optimization method achieves coding performance comparable, or sometimes superior, to that afforded by the main profile encoder.