Graduate School and Research Center In communication systems

Lossy and lossless causal coding of vectorial signals

Mary, David

Thesis

The aim of source coding, or compression, is to reliably represent some information by means of bits, with the natural concern for using a small number of bits. If the information can be exactly recovered from these bits, the code is called lossless; otherwise it is lossy. Both lossy and lossless coding are of interest in this work. Compression allows one to save bandwidth for data transmission over communications channels, or memory space for information storage. The ``information" considered in this thesis will be represented by vectorial signals, which compose a wide class of signals, among which scalar and multichannel signals. Multichannel signals may be obtained as soon as scalar signals are, in the context of various applications, gathered together. If this signals present some dependencies, such as audio signals for example, one should code them jointly in order to achieve a more efficient compression. The initial idea of developping coding techniques for audio signals (the first results of this work were obtained in the framework of the french RNRT project COBASCA: COdage en Bande élargie avec partage Adaptatif du débit entre Source et CAnal pour Réseaux cellulaires de deuxième et troisième générations (UMTS).) motivated this choice of a vectorial representation. Though some applications will be presented for this kind of signals, the Gaussian assumption is often made since it allows one to derive closed form expressions, to compare, and possibly to prove the optimality of the considered coding schemes. The first part of this thesis presents lossy coding techniques for vectorial signals. In a transform coding framework firstly, we derive the optimal (linear) transform subject to the constraint of causality. This transform is shown to correspond to an LDU (Lower-Diagonal-Upper) factorization of the signal covariance matrix. This transform is then compared to the Karhunen-Lo\`eve Transform (KLT), which is the optimal unitary transform for Gaussian signals, and which is therefore traditionally used as a benchmark. One criterion of merit used for this comparison is the coding gain, corresponding to the ratio by which the distortion is decreased when using a particular transformation. Similarly to DPCM (Difference Pulse Code Modulation), we show that practical causal coding schemes should be implemented in closed loop around the quantizers. As in DPCM also, we show that for low rates a quantization noise feedback decreases the coding performances. For moderate to high rates however, the optimal causal transform yields the same coding gain as its unitary counterpart. The optimal causal transform presents furthermore several advantages with respect to the KLT, such as lower implementation and design complexities, and perfect reconstruction property in the case of quantization of the transform coefficients. In most of practical coding situations however, the data are nonstationary, which poses the problem of the adaptation of signal dependent transforms such as KLT or LDU. The main advantage of backward over forward adaptive coding schemes is to update the coding parameters with the data available at the decoder, avoiding thereby any excess bitrate. The coding performances of the two transformations are compared in this framework. This analysis allows one to quantitatively describe the influence of estimation and quantization noise as compared with the ideal case where the statistics of the signal are known. In the last chapter of this first part, the LDU transform is extended to (matricial) filtering. In this case, the optimal causal decorrelating scheme can be described by means of a prediction matrix whose entries are optimal prediction filters. The diagonal filters are scalar intrasignal prediction filters. The off-diagonal predictors are Wiener filters performing the intersignal decorrelation. By considering vectors of infinite size, one can obtain frequential expressions for the coding gains. We show that this decorrelating sheme leads to the notion of ``generalized" MIMO (Multiple Input Multiple Output) prediction, in which a certain degree of non causality may be allowed for the off-diagonal prediction filters. In the case of non causal intersignal filters, the optimal MIMO predictor is still lower triangular, and hence "causal", in a wider sense. The notion of causality may be generalized : the causality between channels becomes processing the channels in a certain order. Some signals may be coded using the coded/decoded versions of the ``previous" signals. We show that if the quantization noise feedback is taken into account, the triangular predictor is the more efficient. Moreover, the coding gain is maximized if the signals are decorrelated by order of decreasing variance. The second part of this work presents lossless coding techniques based on the previously introduced causal approaches. The decorrelation of the several quantized components of a block of signal can be efficiently performed by means of a lossless (integer-to-integer) implementation of the Karhunen-Loève Transform (KLT, unitary transform). We compare the integer-to-integer implementations of the KLT and LDU in this framework, called ``single-stage" lossless transform coding. We define the lossless coding gain for a transformation as the bitrate reduction operated by using the corresponding lossless coding scheme. In a first step, we show that the maximal achievable coding gain corresponds to the sum of the mutual information shared by the components of the vector. In a second step, we analyze the effects of the lossless constraint on the coding gains. A third step analyzes the effects of estimation noise uppon the coding gains : in this case, the transforms are based on an estimate of the covariance matrix of the quantized signals. We find that for stationary Gaussian signals, the coding gains are close to their maxima after a few tens of decoded vectors. Moreover, due to its triangular structure, the LDU based approach is shown to yield the highest coding gain. Orthogonal transforms are then compared with the causal transform in ``multi-stage"lossless transform coders. For internet browsing applications, or in the case of varying transmission bandwidth, this kind of schemes allows one to deliver in a first step a low resolution (lossy) version of the signal, and to transmit separately the error signal. In a two-stage lossless coder, each vector is transformed, quantized, and an error signal is generated by substraction to the original signal. We show that the causal approach allows one to code the data (almost) without causing any excess bitrate as compared with a single-stage coder. For orthogonal transforms, the cost of the multiresolution approach is a bitrate penalty of 0.25 bit per sample, which is caused by a ``Gaussianization" of the error signals. Also, the approach based on the causal transform allows one to easily switch between a single- or a multi-stage compressor, and to easily fix the distortion and rate for both the low resolution and the error signal of each channel. Any of the channels may, as a particular case, be chosen to be directly losslessly coded. Finally, we present lossless coding schemes based on the MIMO predictors described in the first part. In this framework, both intra- and inter-channel redundancies are removed by lossless prediction. The resulting signals are scalar entropy coded. We express the lossless constraint in terms of excess bitrate. The proposed coders may be used either as compressors, or as scalable lossless coders. In this case, multistage versions of the lossless coders based on ADPCM-like lossless prediction loops allow one to transmit the data by means of substreams, which represent different ``resolution" levels. We propose a strategy to fix the stepsizes of these quantizers so that the actual delivered rates approach some predetermined target rates.

Document Bibtex

Type:Thesis
Language:English
Date:
Department:Mobile Communications
Eurecom ref:1126
Copyright: © ENST Paris. Personal use of this material is permitted. The definitive version of this paper was published in Thesis and is available at :
Bibtex: @phdthesis{EURECOM+1126, year = {2003}, title = {{L}ossy and lossless causal coding of vectorial signals}, author = {{M}ary, {D}avid}, school = {{T}hesis}, month = {03}, url = {http://www.eurecom.fr/publication/1126} }