H.264/AVC entropy decoder complexity analysis and its applications

Context-based adaptive variable length coding (CAVLC) and universal variable length coding (UVLC) are two entropy coding tools that are supported in all profiles of H.264/AVC coders. In this paper, we investigate the relationship between the bit rate and the CAVLC/UVLC decoding complexity. This relationship can help the encoder choose the best coding parameter to yield the best tradeoff between the rate, distortion, and the decoding complexity performance. A practical application of CAVLC/UVLC decoding complexity reduction is also discussed.     

Mode-Dependent Templates and Scan Order for H.264/AVC-Based Intra Lossless Coding

In H.264/advanced video coding (AVC), lossless coding and lossy coding share the same entropy coding module. However, the entropy coders in the H.264/AVC standard were original designed for lossy video coding and do not yield adequate performance for lossless video coding. In this paper, we analyze the problem with the current lossless coding scheme and propose a mode-dependent template (MD-template) based method for intra lossless coding. By exploring the statistical redundancy of the prediction residual in the H.264/AVC intra prediction modes, more zero coefficients are generated. By designing a new scan order for each MD-template, the scanned coefficients sequence fits the H.264/AVC entropy coders better. A fast implementation algorithm is also designed. With little computation increase, experimental results confirm that the proposed fast algorithm achieves about 7.2% bit saving compared with the current H.264/AVC fidelity range extensions high profile.     

A jointly optimized subband coder

The mainstream approach to subband coding has been to partition the input signal into subband signals and to code those signals separately with optimal or near-optimal quantizers and entropy coders. A more effective approach, however, is one where the subband coders are optimized jointly so that the average distortion introduced by the subband quantizers is minimized subject to a constraint on the output rate of the subband encoder. A subband coder with jointly optimized multistage residual quantizers and entropy coders is introduced and applied to image coding. The high performance of the coder is attributed to its ability to exploit statistical dependencies within and across the subbands. The efficiency of the multistage residual quantization structure and the effectiveness of the statistical modeling algorithm result in an attractive balance among the reproduction quality, rate, and complexity.     

Index-compressed vector quantisation based on index mapping

The authors introduce a novel coding technique which significantly improves the performance of the traditional vector quantisation (VQ) schemes at low bit rates. High interblock correlation in natural images results in a high probability that neighbouring image blocks are mapped to small subsets of the VQ codebook, which contains highly correlated codevectors. If, instead of the whole VQ codebook, a small subset is considered for the purpose of encoding neighbouring blocks, it is possible to improve the performance of traditional VQ schemes significantly. The performance improvement obtained with the new method is about 3 dB on average when compared with traditional VQ schemes at low bit rates. The method provides better performance than the JPEG coding standard at low bit rates, and gives comparable results with much less complexity than address VQ     

Bit Rate Reduction of Digitized Speech Using Entropy Techniques

We present the results of a study to reduce the bit rate of speech that has been digitized with a continuously variable slope delta modulator (CVSD) operating at 16, 24, and 32 kbits/s. The theoretical reduction is found from the bit stream entropy. The actual reduction, via Huffman coding, is within 1-2 Percent of the theoretical value. The conditional entropy indicates that additional bit rate reduction can be achieved if we use a set of Huffman codes, conditioned on the past CVSD bits. A third technique, tandem coding, using a maximum likelihood predictor in tandem with run length and Huffman coding, is also investigated. Using these entropy techniques, bit rate reductions of 11-25 percent are achieved for the CVSD rates considered. The paper concludes with a study of the buffer requirements needed to support these entropy coders.     

Predictive Coding of Speech at Low Bit Rates

Predictive coding is a promising approach for speech coding. In this paper, we review the recent work on adaptive predictive coding of speech signals, with particular emphasis on achieving high speech quality at low bit rates (less than 10 kbits/s). Efficient prediction of the redundant structure in speech signals is obviously important for proper functioning of a predictive coder. It is equally important to ensure that the distortion in the coded speech signal be perceptually small. The subjective loudness of quantization noise depends both on the short-time spectrum of the noise and its relation to the short-time spectrum of the Speech signal. The noise in the formant regions is partially masked by the speech signal itself. This masking of quantization noise by speech signal allows one to use low bit rates while maintaining high speech quality. This paper will present generalizations of predictive coding for minimizing subjective distortion in the reconstructed speech signal at the receiver. The quantizer in predictive coders quantizes its input on a sample-by-sample basis. Such sample-by-sample (instantaneous) quantization creates difficulty in realizing an arbitrary noise spectrum, particularly at low bit rates. We will describe a new class of speech coders in this paper which could be considered to be a generalization of the predictive coder. These new coders not only allow one to realize the precise optimum noise spectrum which is crucial to achieving very low bit rates, but also represent the important first step in bridging the gap between waveform coders and vocoders without suffering from their limitations.     

Wavelet image coding using variable blocksize vector quantization with optimal quadtree segmentation

In this paper, we propose an image coding scheme by using the variable blocksize vector quantization (VBVQ) to compress wavelet coefficients of an image. The scheme is capable of finding an optimal quadtree segmentation of wavelet coefficients of an image for VBVQ subject to a given bit budget, such that the total distortion of quantized wavelet coefficients is minimal. From our simulation results, we can see that our proposed coding scheme has higher performance in PSNR than other wavelet/VQ or subband/VQ coding schemes.     

Exploiting quantization and spatial correlation in virtual-noise modeling for distributed video coding

Aiming for low-complexity encoding, video coders based on Wyner–Ziv theory are still unsuccessfully trying to match the performance of predictive video coders. One of the most important factors concerning the coding performance of distributed coders is modeling and estimating the correlation between the original video signal and its temporal prediction generated at the decoder.One of the problems of the state-of-the-art correlation estimators is that their performance is not consistent across a wide range of video content and different coding settings. To address this problem we have developed a correlation model able to adapt to changes in the content and the coding parameters by exploiting the spatial correlation of the video signal and the quantization distortion.In this paper we describe our model and present experiments showing that our model provides average bit rate gains of up to 12% and average PSNR gains of up to 0.5 dB when compared to the state-of-the-art models. The experiments suggest that the performance of distributed coders can be significantly improved by taking video content and coding parameters into account.     

Vector-quantised transform coder for speech coding at 9-6 kbit/s and below

The transform approach to speech coding has been established for some time, and has been shown to be very efficient in controlling the bit allocation and the shape of the noise spectrum. Various transform coders have been reported which produce high-quality digital speech at around 16 kbit/s. Although these coders can maintain good quality down to about 9.6 kbit/s, they perform poorly at lower bit rates. Here we discuss how vector quantisation (VQ) can be used to improve the quality of transform coders. We describe one specific design of vector-quantised transform coder (VQTC) which follows on from earlier work, and which is capable of producing good-quality speech at as low as 4.8 kbit/s.     

A Rate-Distortion Function for Vector Quantization with a Variable Block-Size Classification Model

In this paper, a rate-distortion function (RDF),R(D), is presented for a variable block-size classification (VBSC) model. We obtain a theoreticalR(D) bound on the performance of vector quantization (VQ) based on the VBSC model. It is theoretically proved that theR(D) bound of the VBSC model is lower than those of the Gaussian model and the fixed block-size classification (FBSC) model for the bit rates of interest. In the comparison tests of VBSC model-based VQ and FBSC model-based VQ, which were carried out by using a monochrome still image, it was seen that the former technique outperforms the latter technique, subjectively as well as objectively. We also experimentally evaluate a RDF for the VBSC model and compare this with the theoretical RDF. There is a gap of 0.07–0.1 bpp between the theoretical RDF and the experimental RDF in VQ coding without entropy coding. We have reduced the gap to 0.02–0.03 bpp by subsequently employing a Huffman coder for entropy coding. It is expected that the theoretical bound can be approached more closely by the experimental RDF by using a modified asymptotic RDF.     

Bit allocation for dependent quantization with applications tomultiresolution and MPEG video coders

We address the problem of efficient bit allocation in a dependent coding environment. While optimal bit allocation for independently coded signal blocks has been studied in the literature, we extend these techniques to the more general temporally and spatially dependent coding scenarios. Of particular interest are the topical MPEG video coder and multiresolution coders. Our approach uses an operational rate-distortion (R-D) framework for arbitrary quantizer sets. We show how a certain monotonicity property of the dependent R-D curves can be exploited in formulating fast ways to obtain optimal and near-optimal solutions. We illustrate the application of this property in specifying intelligent pruning conditions to eliminate suboptimal operating points for the MPEG allocation problem, for which we also point out fast nearly-optimal heuristics. Additionally, we formulate an efficient allocation strategy for multiresolution coders, using the spatial pyramid coder as an example. We then extend this analysis to a spatio-temporal 3-D pyramidal coding scheme. We tackle the compatibility problem of optimizing full-resolution quality while simultaneously catering to subresolution bit rate or quality constraints. We show how to obtain fast solutions that provide nearly optimal (typically within 0.3 dB) full resolution quality while providing much better performance for the subresolution layer (typically 2-3 dB better than the full-resolution optimal solution).     

Sample-adaptive product quantization: asymptotic analysis andexamples

Vector quantization (VQ) is an efficient data compression technique for low bit rate applications. However the major disadvantage of VQ is that its encoding complexity increases dramatically with bit rate and vector dimension. Even though one can use a modified VQ, such as the tree-structured VQ, to reduce the encoding complexity, it is practically infeasible to implement such a VQ at a high bit rate or for large vector dimensions because of the huge memory requirement for its codebook and for the very large training sequence requirement. To overcome this difficulty, a structurally constrained VQ called the sample-adaptive product quantizer (SAPQ) has recently been proposed. We extensively study the SAPQ that is based on scalar quantizers in order to exploit the simplicity of scalar quantization. Through an asymptotic distortion result, we discuss the achievable performance and the relationship between distortion and encoding complexity. We illustrate that even when SAPQ is based on scalar quantizers, it can provide VQ-level performance. We also provide numerical results that show a 2-3 dB improvement over the Lloyd-Max (1982, 1960) quantizers for data rates above 4 b/point     

Coding isotropic images

Rate-distortion functions for 2-dimensional homogeneous isotropic images are compared with the performance of five source encoders designed for such images. Both unweighted and frequency weighted mean-square error distortion measures are considered. The coders considered are a) differential pulse code modulation (DPCM) using six previous samples or picture elements (pels) in the prediction--herein called 6-pel DPCM, b) simple DPCM using single-sample prediction, c) 6-pel DPCM followed by entropy coding, d)8 times 8discrete cosine transform coding, and e)4 times 4Hadamard transform coding. Other transform coders were studied and found to have about the same performance as the two transform coders above. With the mean-square error distortion measure, 6-pel DPCM with entropy coding performed best. Next best was the8 times 8discrete cosine transform coder and the 6-pel DPCM--these two had approximately the same distortion. Next were the4 times 4Hadamard and simple DPCM, in that order. The relative performance of the coders changed slightly when the distortion measure was frequency weighted mean-square error. FromR = 1to 3 bits/pel, which was the range studied here, the performances of all the coders were separated by only about 4 dB.     

Unequal error protection for MPEG-2 video transmission over wireless channels

This paper proposes an unequal error protection (UEP) method for MPEG-2 video transmission. Since the source and channel coders are normally concatenated, if the channel is noisy, more bits are allocated to channel coding and fewer to source coding. The situation is reversed when the channel conditions are more benign. Most of the joint source channel coding (JSCC) methods assume that the video source is subband coded, the bit error sensitivity of the source code can be modeled, and the bit allocations for different subband channels will be calculated. The UEP applied to different subbands is the rate compatible punctured convolution channel coder. However, the MPEG-2 coding is not a subband coding, the bit error sensitivity function for the coded video can no longer be applied. Here, we develop a different method to find the rate-distortion functions for JSCC of the MPEG-2 video. In the experiments, we show that the end-to-end distortion of our UEP method is smaller than the equal error protection method for the same total bit-rate.     

SNR and temporal scalable coding of 3-D mesh sequences using singular value decomposition

A signal-to-noise ratio (SNR) and temporal scalable coding algorithm for 3-D mesh sequences using singular value decomposition (SVD) is proposed in this work. The proposed algorithm employs SVD to represent a mesh sequence with a small number of basis vectors, and encodes those basis vectors with a bit plane coder. We analytically derive the contribution of each bit plane to the reconstructed mesh quality, and transmit the bit planes in the decreasing order of their amounts of contribution. As the decoder receives more bit planes, it reconstructs higher quality mesh sequences progressively. Moreover, we develop a temporal prediction mode to improve the rate–distortion (R–D) performance further, which also supports temporal scalability. Simulation results demonstrate that the proposed algorithm yields significantly better R–D performance than conventional SVD-based coders.     

Generalized-cost-measure-based address-predictive vectorquantization

Address-predictive vector quantization (APVQ) exploits the interblock dependency by jointly encoding the addresses of the codewords associated with spatially close blocks. It profiles the same image quality as memoryless VQ for a much lesser bit rate (BR) and the same computational complexity. In the generalized-cost-measure-based APVQ, the two steps of the encoding process, namely, VQ and predictive address encoding, are carried out jointly by minimizing a generalized cost measure, which takes into account both the BR and the distortion. Computer simulations show that a significant improvement can be obtained with respect to APVQ in terms of both BR and distortion. Compared with memoryless VQ, a bit-rate reduction of almost 60% is obtained for the same image quality.     

Combining speech coders and entropy coders to reduce the bit rate in the compression of speech

The combination of speech coders and entropy coders is investigated, for bit rate reduction. Three speech coders of the celp (code excited linear prediction) type are considered and the residual correlation in lsp (line spectrum pairs) coefficients and gains in a speech frame is exploited. The lossless entropy coders use Huffman, Lzw (lempel ziv welch) and gzip (LZ-Huffrnan) techniques. The greatest efficiency is provided by the adaptive Huffman approach, with a 15 % gain in each type of compressed parameter and an overall average bit rate reduction of 7 % for the FS1016 coder and 5 % for the Tetra and lbc coders.     

Classified Vector Quantization of Images

Vector quantization (VQ) provides many attractive features for image coding with high compression ratios. However, initial studies of image coding with VQ have revealed several difficulties, most notably edge degradation and high computational complexity. We address these two problems and propose a new coding method, classified vector quantization (CVQ), which is based on a composite source model. Blocks with distinct perceptual features, such as edges, are generated from different subsources, i.e., belong to different classes. In CVQ, a classifier determines the class for each block, and the block is then coded with a vector quantizer designed specifically for that class. We obtain better perceptual quality with significantly lower complexity with CVQ when compared to ordinary VQ. We demonstrate with CVQ visual quality which is comparable to that produced by existing coders of similar complexity, for rates in the range 0.6-1.0 bits/pixel.     

Digital television on ATM networks: optimum chain for coding andtransmission

This paper presents a global optimization of the transmission chain for video on asynchronous transfer mode (ATM) channels. This optimum control includes compression, transmission, and decoding. First, the gain in statistical multiplexing is put forward to demonstrate that transmitting at variable rates on asynchronous multiplexing links is more efficient than exploiting the constant rate on synchronous links. The joint optimization relies on both the entropy rate and the end-to-end image quality. This requires the characterization of the video sources as entropy generators, and the development of the entropy rate-distortion functions in the coder and the transmission channel. Quantizers and variable-length entropy coders in coding, traffic, and queues in transmission multiplexing each lead to performance functions expressing quality in terms of entropy rate. The objective measures of quality are, respectively, the PSNR in terms of the output data rate and the cell loss in terms of the network loads. The main advantage of transmitting on variable bit-rate channels is to permit the generation of image sequences at constant subjective quality on the coding side, and the saving of transmission bandwidth through a gain in statistical multiplexing on the network side. Mirrored control actions are described for coding and multiplexing; they lead to a unique global optimum of the transmission chain. Since the decoders are generally slaved to the coding and transmission performances, they are restricted to perform independent optimum signal reconstruction     

Kronecker-product gain-shape vector quantization for multispectraland hyperspectral image coding

This paper proposes a new vector quantization based (VQ-based) technique for very low bit rate encoding of multispectral images. We rely on the assumption that the shape of a generic spatial block does not change significantly from band to band, as is the case for high spectral-resolution imagery. In such a hypothesis, it is possible to accurately quantize a three-dimensional (3-D) block-composed of homologous two-dimensional (2-D) blocks drawn from several bands-as the Kronecker-product of a spatial-shape codevector and a spectral-gain codevector, with significant computation saving with respect to straight VQ. An even higher complexity reduction is obtained by representing each 3-D block in its minimum-square-error Kronecker-product form and by quantizing the component shape and gain vectors. For the block sizes considered, this encoding strategy is over 100 times more computationally efficient than unconstrained VQ, and over ten times more computationally efficient than direct gain-shape VQ. The proposed technique is obviously suboptimal with respect to VQ, but the huge complexity reduction allows one to use much larger blocks than usual and to better exploit both the statistical and psychovisual redundancy of the image. Numerical experiments show fully satisfactory results whenever the shape-invariance hypothesis turns out to be accurate enough, as in the case of hyperspectral images. In particular, for a given level of complexity and image quality, the compression ratio is up to five times larger than that provided by ordinary VQ, and also larger than that provided by other techniques specifically designed for multispectral image coding.