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.

In this paper, the redundancy of both variable and fixed rate Slepian-Wolf coding is considered. Given any jointly memoryless source-side information pair {(Xi, Yi)}i=1 infin with finite alphabet, the redundancy Rn(isinn) of variable rate Slepian-Wolf coding of X1 n with decoder only side information Y1 n depends on both the block length n and the decoding block error probability isinn, and is defined as the difference between the minimum average compression rate of order n variable rate Slepian-Wolf codes having the decoding block error probability less than or equal to isinn, and the conditional entropy H(X|Y), where H(X|Y) is the conditional entropy rate of the source given the side information. The redundancy of fixed rate Slepian-Wolf coding of X1 n with decoder only side information Y1 n is defined similarly and denoted by RF n(isinn). It is proved that under mild assumptions about isinn, Rn(isinn) = dvradic-log isinn/n + (oradic-log isinn/n) and RF n(isinn) - dfradic-log isinn/n + o(radic-log isinn/n), where df and dnu are two constants completely determined by the joint distribution of the source-side information pair. Since dv is generally smaller than df, our results show that variable rate Slepian-Wolf coding is indeed more efficient than fixed rate Slepian-Wolf coding.

To maximize rate distortion performance while remaining faithful to the JPEG syntax, the joint optimization of the Huffman tables, quantization step sizes, and DCT indices of a JPEG encoder is investigated. Given Huffman tables and quantization step sizes, an efficient graph-based algorithm is first proposed to find the optimal DCT indices in the form of run-size pairs. Based on this graph-based algorithm, an iterative algorithm is then presented to jointly optimize run-length coding, Huffman coding, and quantization table selection. The proposed iterative algorithm not only results in a compressed bitstream completely compatible with existing JPEG and MPEG decoders, but is also computationally efficient. Furthermore, when tested over standard test images, it achieves the best JPEG compression results, to the extent that its own JPEG compression performance even exceeds the quoted PSNR results of some state-of-the-art wavelet-based image coders such as Shapiro's embedded zerotree wavelet algorithm at the common bit rates under comparison. Both the graph-based algorithm and the iterative algorithm can be applied to application areas such as web image acceleration, digital camera image compression, MPEG frame optimization, and transcoding, etc.

In this paper, it is shown that each Slepian-Wolf coding problem is related to a dual channel coding problem in the sense that the sphere packing exponents, random coding exponents, and correct decoding exponents in these two problems are mirror-symmetrical to each other. This mirror symmetry is interpreted as a manifestation of the linear codebook-level duality between Slepian-Wolf coding and channel coding. Furthermore, this duality, in conjunction with a systematic analysis of the expurgated exponents, reveals that nonlinear Slepian-Wolf codes can strictly outperform linear Slepian-Wolf codes in terms of rate-error tradeoff at high rates. The linear codebook-level duality is also established for general sources and channels.

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.

Rate-distortion optimization (RDO) is widely applied in video coding, which aims at minimizing the coding distortion at a target bitrate. Conventionally, RDO is performed independently on each individual frame to avoid high computational complexity. However, extensive use of temporal/spatial predictions result in strong coding dependencies among neighboring frames, which make the current RDO be non-optimally used. To further improve video coding performance, it would be desirable to perform global RDO among a group of neighboring frames while maintaining approximately the same coding complexity. In this paper, the problem of global RDO is studied by jointly determining the quantization parameters (QPs) for a group of neighboring frames. Specifically, an adaptive frame-level QP selection algorithm is proposed for the H.265/HEVC random access coding by taking into account the inter-frame dependency. To measure the inter-frame dependency, a model based on the energy of prediction residuals is first established. With the help of the model, the problem of global RDO is then analyzed for the hierarchical coding structure in H.265/HEVC. Finally, the QP and the corresponding Lagrangian multiplier for each coding frame are determined adaptively by considering the total impact of its coding distortion on that of future frames in the encoding order. Experimental results show that in comparison with HM-16.0, the proposed algorithm reduces, on average, the BD-rate by 3.49% with negligible increase of encoding time. In addition, the quality fluctuation of the coded video by the proposed algorithm is lower than that by HM-16.0.