Analysis of linear prediction, coding, and spectral estimation fromsubbands

Linear prediction schemes make a prediction xˆ_i of a data sample x_i using p previous samples. It has been shown by Woods and O'Neil (1986) as well as Pearlman (1991) that as the order of prediction p→∞, there is no gain to be obtained by coding subband samples. This paper deals with the less well understood theory of finite-order prediction and optimal coding from subbands which are generated by ideal (brickwall) filtering of a stationary Gaussian source. We first prove that pth-order prediction from subbands is superior to pth-order prediction in the fullband, when p is finite. This fact adduces that optimal vector p-tuple coding in the subbands is shown to offer quantifiable gains over optimal fullband p-tuple coding, again when p is finite. The properties of subband spectra are analyzed using the spectral flatness measure. These results are used to prove that subband DPCM provides a coding gain over fullband DPCM, for finite orders of prediction. In addition, the proofs provide means of quantifying the subband advantages in linear prediction, optimal coding, and DPCM coding in the form of gain formulas. Subband decomposition of a source is shown to result in a whitening of the composite subband spectrum. This implies that, for any stationary source, a pth-order prediction error filter (PEF) can be found that is better than the pth-order PEF obtained by solving the Yule-Walker equations resulting from the fullband data. We demonstrate the existence of such a “super-optimal” PEF and provide algorithmic approaches to obtaining this PEF. The equivalence of linear prediction and AR spectral estimation is then exploited to show theoretically, and with simulations, that AR spectral estimation from subbands offers a gain over fullband AR spectral estimation     

Subband prediction using leakage information in image coding

This paper examines the potential uses of interband leakage in image coders based on subband decomposition. The approach taken is to use the lowpass subband to predict the signal behavior in the other bands. This information is then used to both inform the coder/decoder as to likely locations for significant energy in the highpass bands, and to form a difference signal that can be coded at a lower rate. These methods give significant gains for some image/filter combinations, but in general it seems that analysis filters producing low correlation should be used if possible     

Universal modeling and coding

The problems arising in the modeling and coding of strings for compression purposes are discussed. The notion of an information source that simplifies and sharpens the traditional one is axiomatized, and adaptive and nonadaptive models are defined. With a measure of complexity assigned to the models, a fundamental theorem is proved which states that models that use any kind of alphabet extension are inferior to the best models using no alphabet extensions at all. A general class of so-called first-in first-out (FIFO) arithmetic codes is described which require no alphabet extension devices and which therefore can be used in conjunction with the best models. Because the coding parameters are the probabilities that define the model, their design is easy, and the application of the code is straightforward even with adaptively changing source models.     

Universal noiseless coding

Universal coding is any asymptotically optimum method of block-to-block memoryless source coding for sources with unknown parameters. This paper considers noiseless coding for such sources, primarily in terms of variable-length coding, with performance measured as a function of the coding redundancy relative to the per-letter conditional source entropy given the unknown parameter. It is found that universal (i.e., zero redundancy) coding in a weighted sense is possible if and only if the per-letter average mutual information between the parameter space and the message space is zero. Universal coding is possible in a maximin sense if and only if the channel capacity between the two spaces is zero. Universal coding is possible in a minimax sense if and only if a probability mass function exists, independent of the unknown parameter, for which the relative entropy of the known conditional-probability mass-function is zero. Several examples are given to illustrate the ideas. Particular attention is given to sources that are stationary and ergodic for any fixed parameter although the whole ensemble is not. For such sources, weighted universal codes always exist if the alphabet is finite, or more generally if the entropy is finite. Minimax universal codes result if an additional entropy stability constraint is applied. A discussion of fixed-rate universal coding is also given briefly with performance measured by a probability of error.     

Universal space-time coding

A universal framework is developed for constructing full-rate and full-diversity coherent space-time codes for systems with arbitrary numbers of transmit and receive antennas. The proposed framework combines space-time layering concepts with algebraic component codes optimized for single-input-single-output (SISO) channels. Each component code is assigned to a "thread" in the space-time matrix, allowing it thus full access to the channel spatial diversity in the absence of the other threads. Diophantine approximation theory is then used in order to make the different threads "transparent" to each other. Within this framework, a special class of signals which uses algebraic number-theoretic constellations as component codes is thoroughly investigated. The lattice structure of the proposed number-theoretic codes along with their minimal delay allow for polynomial complexity maximum-likelihood (ML) decoding using algorithms from lattice theory. Combining the design framework with the Cayley transform allows to construct full diversity differential and noncoherent space-time codes. The proposed framework subsumes many of the existing codes in the literature, extends naturally to time-selective and frequency-selective channels, and allows for more flexibility in the tradeoff between power efficiency, bandwidth efficiency, and receiver complexity. Simulation results that demonstrate the significant gains offered by the proposed codes are presented in certain representative scenarios.     

Universal prediction

This paper consists of an overview on universal prediction from an information-theoretic perspective. Special attention is given to the notion of probability assignment under the self-information loss function, which is directly related to the theory of universal data compression. Both the probabilistic setting and the deterministic setting of the universal prediction problem are described with emphasis on the analogy and the differences between results in the two settings     

Side information estimation and new symmetric schemes for multi-view distributed video coding

This paper deals with distributed video coding (DVC) for multi-view sequences. DVC of multi-view sequences is a recent field of research, with huge potential impact in applications such as videosurveillance, real-time event streaming from multiple cameras, and, in general, immersive communications. It raises however several problems, and in this paper we tackle two of them. Based on the principles of Wyner–Ziv (WZ) coding, in multi-view DVC many estimations can be generated in order to create the side information (SI) at the decoder. It has been shown that the quality of the SI strongly influences the global coding performances. Therefore, this paper proposes to study the contribution of multiple SI estimations (in the temporal and view directions) to the global performances. Moreover, we propose new symmetric schemes for longer group of pictures (GOP) in multi-view DVC and show that we can further exploit the long-term correlations using a new kind of estimation, called diagonal. For such schemes, several decoding strategies may be envisaged. We perform a theoretical study of the temporal and inter-view dependencies, and confirm by experiments the conclusion about the best decoding strategy.     

Predictive block-matching motion estimation for TV coding. II. Inter-frame prediction

For pt.I, see ibid., vol.37, no.3, p.97-101 (1991). A predictive block-matching motion estimation scheme was implemented for efficient video code design. The scheme is based on the so-called inertia effect of natural video scenes and takes advantage of the motion vectors obtained in the previous frames. The benefits from this prediction process are threefold. First, the searching area is greatly reduced, and so is the computational complexity. Second, the motion vector overhead information is reduced since motion vectors are decorrelated by the prediction process. Finally, the motion vectors estimated from this procedure are more realistic since it reflects the real physical phenomena. These advantages were also demonstrated by simulation results including the coded data rate, displaced frame difference entropy, motion vectors, and reconstructed signal-to-noise ratio. Only a simple prediction model was implemented; further results in more general autoregressive (AR) modes are still under study.<>     

Minimum error entropy estimation and entropic prediction filtering: An optimal predictive coding scheme

The minimum error entropy (MEE) estimation problem on discrete, finite, or countably infinite ensembles of arbitrary statistical nature is considered. A combinatorial approach is taken to solve the minimization problem. The solution is obtained in algorithmic form. The numerical complexity of the MEE algorithm is analyzed. An entropic prediction filtering (EPF) coding scheme that utilizes the MEE algorithm to minimize the per symbol error entropy is introduced. Simulation has shown that the EPF can effectively be used to reduce the average codeword length required to encode data. Other applications of the MEE algorithm in signal interpolation and extrapolation are also discussed.     

Universal coding for multiple access channels

The problems of universal coding and decoding for multiple-access channels are examined. The hypothetical mutual information functions are used to prove that rate vectorsR=(R_{1},R_{2})in a subregionhat{cal C}of the capacity regioncal Care universally achievable in the sense that there exist codes of rateRthat are asymptotically optimum for all multiple-access channels with finite fixed input alphabetsX_{1},X_{2}, and output alphabetY.     

Universal coding of integers and unbounded search trees

In this paper we study universal coding problems for the integers, in particular, establish rather tight lower and upper bounds for the Elias omega code and other codes. In these bounds, the so-called log-star function plays a central role. Furthermore, we investigate unbounded search trees induced by these codes, including the Bentley-Yao search tree. We will reveal beautiful recursion structures latent in these search trees as well as in these codes. Finally, we introduce the modified log-star function to reveal the existance of better prefix codes than the Elias omega code and other known codes     

Universal regularizers for robust sparse coding and modeling

Sparse data models, where data is assumed to be well represented as a linear combination of a few elements from a dictionary, have gained considerable attention in recent years, and their use has led to state-of-the-art results in many signal and image processing tasks. It is now well understood that the choice of the sparsity regularization term is critical in the success of such models. Based on a codelength minimization interpretation of sparse coding, and using tools from universal coding theory, we propose a framework for designing sparsity regularization terms which have theoretical and practical advantages when compared with the more standard l(0) or l(1) ones. The presentation of the framework and theoretical foundations is complemented with examples that show its practical advantages in image denoising, zooming and classification.     

Capacity, mutual information, and coding for finite-state Markovchannels

The finite-state Markov channel (FSMC) is a discrete time-varying channel whose variation is determined by a finite-state Markov process. These channels have memory due to the Markov channel variation. We obtain the FSMC capacity as a function of the conditional channel state probability. We also show that for i.i.d. channel inputs, this conditional probability converges weakly, and the channel's mutual information is then a closed-form continuous function of the input distribution. We next consider coding for FSMCs. In general, the complexity of maximum-likelihood decoding grows exponentially with the channel memory length. Therefore, in practice, interleaving and memoryless channel codes are used. This technique results in some performance loss relative to the inherent capacity of channels with memory. We propose a maximum-likelihood decision-feedback decoder with complexity that is independent of the channel memory. We calculate the capacity and cutoff rate of our technique, and show that it preserves the capacity of certain FSMCs. We also compare the performance of the decision-feedback decoder with that of interleaving and memoryless channel coding on a fading channel with 4PSK modulation     

Universal variable length coding for an integrated approach to image coding

We propose a new entropy coding scheme, denoted in this paper as the UVLC (universal variable length coding). It is universal in the sense that its efficiency is close to one for a large class of images. The UVLC, when it is applied to block orthogonal transforms, processes groups of blocks at the bit level, using universal codes designed for binary memoryless sources. It can be used for every video coding application, from high definition TV (HDTV) to high quality videotelephony (above 2 Mbit/s) for transform or subband coding. Last but not least, its implementation is very regular and can be realized in a single chip for the encoding oftv at theccir 601 format.     

Sequential motion estimation using luminance and chrominance information for distributed video coding of Wyner-Ziv frames

Proposed is a novel side information refinement technique for Wyner-Ziv video frames in distributed video coding using sequential motion compensation with luminance and chrominance information for a given bit plane to update the side information for the next bit plane. Simulation results show that over 3 dB PSNR gain can be obtained with the proposed algorithm over the best available pixel domain Wyner Ziv codec from the literature [Natario et al.] at the same bit rate.     

Side information refinement using motion estimation in dc domain for transform-based distributed video coding

The key to good decoding performance in distributed video coding systems lies in the efficient prediction of frames using side information. Previously, this process has been performed without considering the progressive nature of the synthesis of the final frame. Observing the fact that incorrectly predicted areas of the current frame can be detected at different levels of final frame synthesis, an algorithm is proposed for refinement of side information synthesis based on an additional stage of motion estimation. The additional stage is performed on correctly decoded DC frames and is used to significantly improve the motion prediction of the final resolution frames, which leads to enhanced performance of the overall system.     

Universal prediction of individual sequences

The problem of predicting the next outcome of an individual binary sequence using finite memory is considered. The finite-state predictability of an infinite sequence is defined as the minimum fraction of prediction errors that can be made by any finite-state (FS) predictor. It is proven that this FS predictability can be achieved by universal sequential prediction schemes. An efficient prediction procedure based on the incremental parsing procedure of the Lempel-Ziv data compression algorithm is shown to achieve asymptotically the FS predictability. Some relations between compressibility and predictability are discussed, and the predictability is proposed as an additional measure of the complexity of a sequence     

Universal perceptual weighted zerotree coding for image and videocompression

A universal representation for the perceptual weighted zerotree coding algorithm is developed, in which the perceptual weighted zerotree coding is decomposed into two separate parts, i.e. visual weighting and zerotree representation, which can be realised independently. Prior to zerotree processing, the extracted full-tree is weighted by using a visual weighting matrix. Any zerotree algorithm like EZW, SPIHT and zerotree space-frequency quantisation can be used to encode the weighted coefficients of the wavelet transform. In other words, any previous algorithm without perceptual weighting can be easily extended to form a new perceptual coder using the proposed framework. Several examples of visual weighting matrices are given to show the effect of the new method     

Hybrid picture coding with wavelet transform and overlappedmotion-compensated interframe prediction coding

A novel video coding scheme using an orthonormal wavelet transform is proposed. The wavelet transform is used in a motion compensated interframe coder in which a blockless motion compensation technique is employed to increase efficiency of wavelet transform coding. A new scanning method for wavelet coefficients is also proposed which is rather different from subband coding. Simulation work is carried out to evaluate the proposed coding method. Significant improvement in subjective quality is obtained over that obtained with conventional hybrid coding methods that use blockwise motion compensation and DCT. Some improvement has also been realized in the signal to noise ratio. Although wavelet coding is still in its early stages of development, it appears to hold great promise for motion picture coding