Ludovic Guillemot

Yann Gaudeau

Saïd Moussaoui

Jean-Marie Moureaux

AN ANALYTICAL GAMMA MIXTURE BASED RATE-DISTORTION MODEL FOR LATTICE VECTOR QUANTIZATION

.

INTRODUCTION

In the field of transform coding, Lattice Vector Quantizers (LVQ) have proved for years their efficiency, as they can exploit statistical characteristics of vectors (i.e. blocks of source samples), while maintaining a low computational cost. However, to be competitive with scalar quantizers, practical realizations of LVQ must deal with the design of an appropriate codebook with respect to the distribution of data, as well as an efficient bit rate allocation process which is unavoidable in transform coding. A lot of works [START_REF] Chen | Lattice Vector Quantization of Generalized Gaussian Sources[END_REF][START_REF] Loyer | Lattice codebook enumeration for generalized gaussian source[END_REF][START_REF] Jeong | Uniform and piecewise uniform lattice vector quantization for memoryless Gaussian and Laplacian sources[END_REF] related to this topic have been done, but they have in common to assume i.i.d. signals while block-based signal processing methods (like LVQ) can take advantage of the non i.i.d. properties of real data (like clustering of wavelet coefficients for example). The best answer to these questions stands in a realistic model of the data. In this context, Fisher et al. for example, have proposed in [START_REF] Fischer | Geometric source coding and vector quantization[END_REF] the use of elliptical codebooks. However, this approach has a high complexity since it requires the computing of the orientation of the ellipsoid and a specific indexing methods [START_REF] Moureaux | Counting lattice points on ellipsoids -Application to Image Coding[END_REF]. Furthermore, these schemes exploit polarizations between samples which is a specific kind of dependance.

Here we aim at taking into account clustering effects within data and designing low cost algorithms. The key point of our approach stands in the modelling of the correlations within any vector by using a new prior on the joint distribution of source vectors based on a multidimensional mixture of generalized gaussian (MMGG) densities. We derive two main improvements to lattice quantizers: firstly, a new analytical Rate-Distortion (R-D) model (called R-D mixture model) which can be an efficient tool to solve the problem of bit allocation by outperforming classical R-D models under the i.i.d. assumption. Secondly, the MMGG prior provides a new theoretical framework to the design of codebooks better suited to the data. We have proposed in a previous work such a LVQ scheme based on the use of a vector dead zone (DZLVQ) [START_REF] Guillemot | A new fast bit allocation procedure for image coding based on wavelet transform and dead zone lattice vector quantization[END_REF][START_REF] Voinson | Image compression using Lattice Vector Quantization with code book shape adapted thresholding[END_REF] .

The paper is organized as follows. Section 2 is dedicated to the presentation of the MMGG model which is mainly based on a study of the L α norm of the source vectors. We show that, in the case of sparse and clustered signals, the norm distribution has a particular shape, and is close to a Gamma mixture. Thanks to a well stated property of the Gamma law, we deduce, in sub-section 2.2., that the joint distribution of the source vectors can be approximated by a mixture of multidimensional Generalized Gaussian densities (MMGG). Finally, the R-D mixture model is presented in section 3 and is also extended to our new class of LVQ with dead zone. The efficiency of our approach is illustrated by experimental results performed on wavelet coefficients using the 9-7 filter [START_REF] Antonini | Image coding using wavelet transform[END_REF].

VECTOR NORM AND SOURCE DISTRIBUTION MODELLING USING MIXTURE MODELS

Most popular lattice vector quantizers in source coding are based on the use of a product code. The basic principles are the following: In a first step, a source vector X is quantized within the lattice by Q(.), then this quantized vector Y = Q( X γ ), where γ is the scaling factor, is encoded by using a prefix code which associates to Y a unique pair (e, pos), where e = Y α α and pos stands for the position of Y on the shell of radius e [START_REF] Loyer | Lattice codebook enumeration for generalized gaussian source[END_REF]. The suffix pos is fixed-length coded while e is encoded using entropy coding. The total rate of the quantized source is then given by: R = -

where N (r) is the population of the shell of radius r (i.e. the cardinal of the set of vectors of norm equal to r), P the discrete law of the radius and rT the truncation radius of the codebook.

The efficiency of LVQ stands mainly in the entropy coding of norm of vectors1 , particularly in the case of correlated and sparse source samples like wavelet coefficients. As illustrated in figure 2 for the L 1 case, the vector norm distribution has a mode close to zero because of clustering of small samples which leads to a large amount of vectors with a low norm. In addition, the density has an heavy tail corresponding to clusters of high magnitude samples. In most of works, the modelling of the norm is deduced from the distribution of source samples which is often assumed independent and identically distributed (i.i.d.). This hypothesis leads to simple analytical developments but does not yield a good description of the norm properties (and obviously cannot take into account sample dependencies). For example, under the assumption of an i.i.d. generalized gaussian distribution the value of the mode is only linked to the standard deviation. A large standard deviation yields a mode far from zero and thus often involves a non reliable model of the norm.

Here, our approach is inverse: we propose a flexible model for the norm which allows to modelling the joint distribution of source vectors.

Vector norm modelling

A distribution with a mode near zero and a heavy tail naturally leads to a model consisting in a mixture of densities. Since the norm of vectors is sparse and non-negative, the mixture of Gamma densities seems to be a good candidate. Recall that a random variable ε which is Gamma distributed (in the sequel, ε represents the norm of blocks) has the following probability density function (pdf):

G(ε; a, b) = b a Γ(a) ε a-1 exp[-b ε] Iε>0, (2)
where Γ(a) is the Gamma function, Iε>0 is the indicator function and the parameters (a > 0, b > 0) allow to adjust the shape of the Gamma density (denoted G(ε; a, b)). As shown in figure 1, for 0 < a < 1 the distribution has a sharp shape, which is well suited to sparse signals, and for a > 1, the distribution has a mode in (a -1)/b and is heavy tailed. Assuming that the norm of vectors ε belongs to Nmix classes S k of weight c k = P (ε ∈ S k ), we obtain the following mixture model:

p(ε; a, b) = N mix k=1 c k G(ε; a k , b k ), (3)
with a = [a1, ..., aN mix ], b = [b1, ..., bN mix ].
In the framework of our application, the norm of vectors is assumed to belong to two classes: low and high norm states, denoted S1 and S2. The parameters (c1, c2) are estimated by using a Monte Carlo Markov chain algorithm [START_REF] Peel | Finite Mixture Models[END_REF], where the Gamma parameters a and b are simulated using the algorithm given in [START_REF] Moussaoui | Separation of Non-negative Mixture of Nonnegative Sources using a Bayesian Approach and MCMC Sampling[END_REF]. Figure 2 shows that the two Gamma mixture fits well the norm distribution, i.e. the peak and the heavy tail. Furthermore, the good performances of the mixture model emphasizes the fact that a joint distribution which leads to a gamma mixture distribution of the norm could be a good candidate to modelling of the source distribution. This point is adressed in the following subsection.

Source distribution

According to the vector norm distribution expressed by the gamma mixture model ( 3), the joint distribution f of the random vector X representing the source is given by:

f (X) = N mix k=1 c k f (X| X α α ∈ S k ) (4)
where f (X| X α α ∈ S k ) is the distribution of the random vector X conditionally to the state S k .

The choice of the distributions f (X| X α α ∈ S k ) is motivated by a well stated theoretical property of the Gamma mixture model: If we consider a vector X = (x1, ..., xn), whose components x k are GG distributed, it can be shown that its norm, ε = n k=1 |x k | α , is Gamma distributed with parameters a = n/α and b = 1/β α , where α and β are the power and shape parameters of the GG density, which is expressed by:

GG(xi; α, β) = α β 1/α 2Γ(1/α) exp[-βx α i ].
According to this property and under the condition that the components of each vector are identically distributed, the Gamma mixture model of the norm leads to a model of MMGG densities for the joint distribution (4) of the source vectors. By assuming that the Nmix class of vectors are Generalized Gaussian distributed the joint distribution of X conditionally to the state S k is then:

f (X| X α α ∈ S k ) = n j=1 GG(xj; α k , β k ). ( 5
)
Before showing in the next section the efficiency of the MMGG model by computing accurate R-D models for LVQ, let us remark some important issues:

• The MMGG model is different from that consisting in a mixture of scalar Generalized Gaussian distributions with independent labels because it enables to account samples dependencies.

• The sample dependencies are estimated in a simple manner since the MMGG model is deduced from the parameters of the gamma mixture model with independent labels representing the vector norm distribution. • As it will be shown in the following, our approach allows to reuse works related to the classical i.i.d. assumption thanks to advantageous mathematical properties:

The coordinates of vectors are assumed identically distributed, the conditional distributions are separable and, finally, the i.i.d. generalized Gaussian (GG) density is a wide spread assumption in LVQ.

LATTICE VECTOR QUANTIZATION BASED ON THE MMGG MODEL

In source coding, the knowledge of the source statistics is of interest for both the design of an efficient quantizer and the estimation of the R-D function of the quantized source. In this section we first design under the MMGG assumption an accurate R-D model for LVQ schemes. Then, we present our LVQ scheme with a codebook shape adapted to the MMGG model, the dead zone LVQ (DZLVQ). R-D models dedicated to DZLVQ are then computed.

LVQ Rate distortion models

The key point of the design of a R-D model based on the MMGG prior (R-D mixture model) stands in the fact that it only requires R-D model in the i.i.d. case.

Problem statement

The distortion model Dmix associated to a mixture of densities is given by:

Dmix = N mix k=1 c k D k (6)
where D k is the distortion of the k th distribution of the mixture and Nmix the number of densities. Furthermore, according to (1), the rate model Rmix is given by:

Rmix = - r T r=0
Pmix(e = r) log 2 Pmix(e = r) -⌈log 2 (N (r))⌉ [START_REF] Loyer | Lattice codebook enumeration for generalized gaussian source[END_REF] where Pmix (e = r) = N mix k=1 c k P k (e = r) is the discrete distribution of the radius of the mixture, and P k the probability of the k th class S k .

Experimental results

Experimental results are performed using a pyramidal LVQ scheme on lattice Z n which is a good trade-off between coding performances and complexity. Classical modelling of R-D curves in the pyramidal case are computed under the i.i.d. Laplacian assumption [START_REF] Raffy | Distortion-Rate Models for Entropy-Coded Lattice Vector Quantization[END_REF]. We are going to show that the R-D model based on a multidimensional mixture of laplacian densities gives significantly more accurate results. Table 1 allows to compare the mean relative error (RE) and the maximum RE between the R-D functions estimated by the two models and the real R-D function 2 performed on the vertical sub images of level 2 of images "Boat", "Peppers" and "Lena". As we can see the mixture assumption gives a much more realistic R-D model that the i.i.d. assumption. This efficiency is also illustrated in figure 3 where the mixture model fits 2

Definitions of the mean and the maximum RE are given in appendix A

precisely the real R-D curve whereas the curve corresponding to the i.i.d. Laplacian assumption diverges. Finally, note that tests have also been performed on all other sub images which lead to the same results.

Lena

Lattice quantizers with adapted codebook shape

Previous experimental results emphasize the fact that classical LVQ designed in an i.i.d. framework can be improved by taking into account the statistical dependencies within vectors. As it has be previously mentioned, one of the main properties of a block mixture distributed signal is the high amount of low norm vectors. We have proposed in [START_REF] Guillemot | A new fast bit allocation procedure for image coding based on wavelet transform and dead zone lattice vector quantization[END_REF][START_REF] Voinson | Image compression using Lattice Vector Quantization with code book shape adapted thresholding[END_REF] a new LVQ quantizer based on the use of a vector dead zone, called dead zone lattice vector quantizer (DZLVQ), which takes benefit from the pick density by increasing the amount of null vectors, putting thus more bits on significant vectors.

Problem Statement

A vector dead zone of radius RDZ enables to threshold source vectors according to their L α norm. Thus, any source vector X is quantized by the following way:

• if X α α ≤ RDZ , then X is replaced by a null vector; • if X α α > RDZ , then X is scaled within the codebook (by a parameter called scale factor γ) and quantized using usual fast lattice quantization algorithms (here in Z n ). The comparison of figures 4 (A) and 4 (B) show the importance of these properties on the coder performances: The first one shows that the distribution of the norm in the case of an i.i.d. source (here on a Laplacian distribution) is not as sharp as the second one (a realistic signal of equal variance). Figure 5 allows to compare, the signal to noise ratio (SNR) of DZLVQ and LVQ (both with a pyramidal shape) performed on a structured and sparse signal (here the vertical sub image (level 3) of "Lena" produced with the 9-7 filter). These curves show that DZLVQ outperforms LVQ [START_REF] Voinson | Image compression using Lattice Vector Quantization with code book shape adapted thresholding[END_REF][START_REF] Guillemot | A new fast bit allocation procedure for image coding based on wavelet transform and dead zone lattice vector quantization[END_REF]. Compared to classical schemes, the rate allocation of DZLVQ requires the tuning of an additional parameter, the dead zone radius RDZ . Thus, the need of an analytical R-D model is crucial for the design of a practical realization of DZLVQ. As it has been explained in paragraph 3.1, our approach only requires to compute R-D models under the i.d.d. generalized gaussian assumption.

The rate model is deduced from the classical radius law by substituting in formula [START_REF] Loyer | Lattice codebook enumeration for generalized gaussian source[END_REF] the probability of the null vector by the probability to belong to the vector dead zone of radius RDZ : Pmix (e = 0) =

N mix k=1 c k P k ( X α α < RDZ )
. This formula only depends on the knowledge of the repartition function of the law of X α α . In the case of a GG distribution an analytical expression is given in [START_REF] Chen | Lattice Vector Quantization of Generalized Gaussian Sources[END_REF].

The distortion model for DZLVQ can be obtained using the following proposition.

Proposition 1: Under the high resolution assumption outside the dead zone, the distortion as a function of the dead zone radius RDZ and the scale factor γ is given by:

D (RDZ , γ) = 1 n DDZ (RDZ ) + nγ 2 12
(1 -Fn (RDZ )) [START_REF] Peel | Finite Mixture Models[END_REF] where DDZ (RDZ ) is the distortion within the vector dead zone, Fn the repartition function of the law of X α α and n the dimension of X.

The high resolution approximation in formula ( 8) is justified by the fact that the MMGG density decreases slowly outside the dead zone.

The formula of DDZ (RDZ ) is given by3 :

DDZ (RDZ ) = n |x| α <R DZ x 2 GG(x)Fn-1 (RDZ -|x| α ) dx (9)
The proof is given in appendix B.

Finally, the R-D mixture model is given by substituting formula [START_REF] Peel | Finite Mixture Models[END_REF] in [START_REF] Jeong | Uniform and piecewise uniform lattice vector quantization for memoryless Gaussian and Laplacian sources[END_REF].

Experimental results

The proposed mixture R-D model is tested under the assumption of a mixture of multidimensional Laplacian densities. The analytical expression of the dead zone distortion in the case of an Laplacian i.i.d. source of standard deviation σ is given in [START_REF] Guillemot | A distortion model for dead zone lattice vector quantization[END_REF] and is equal to:

DDZ (RDZ ) = n J -2λe -λR DZ R 3 DZ 2 k=0 (λRDZ ) k (k + 3)! (10) with J = -e -λR DZ R 2 DZ + 2 λ RDZ + 2 λ 2 + 2 λ 2 , λ = √ 2
σ . The corresponding rate model for pyramidal DZLVQ is given in [START_REF] Voinson | Image compression using Lattice Vector Quantization with code book shape adapted thresholding[END_REF]. In the same manner as in paragraph 3.

CONCLUSION

In this paper, we have proposed new rate distortion statistical models related to lattice vector quantization allowing to take into account clustering and sparsity properties of signals. It is based on the modelling of the norm of vectors using a mixture of Gamma densities which leads to assuming a mixture of multidimensional generalized Gaussian densities for the joint distribution of the source vectors themselves. From this property, we have derived a blockwise R-D model which can be simply deduced from classical model in the i.i.d. case. Experimental results in the case of a pyramidal lattice vector quantizer under the assumption of a Laplacian mixture show the accuracy of the model. This last point confirms that the multidimensional mixture is a prior well suited to signals like wavelet coefficients. Furthermore, in a previous work we have proposed a LVQ codebook shape adapted to these statistics. It is based on the use of a vector dead zone whose radius is tuned according to the target rate. The need of an accurate analytical model is of importance to minimize the complexity of such an algorithm. The efficiency of the proposed R-D model dedicated to DZLVQ shows that the complexity of this new scheme does not increase compared to classical LVQ schemes.

Future works concern the design of a fast rate allocation procedure deduced from the R-D model. Finally, the accuracy of the MMGG model and its well stated mathematical properties are promising to apply this statistical tool to other areas of source coding or signal processing like, for example, denoising.

A. MEASURE OF THE ACCURACY OF THE R-D MODELS

The mean and the maximum relative error between a R-D model of distortion D and the real R-D curve of distortion D real using Ntest test values are given by: mean RE = 1 Ntest

B. COMPUTING OF THE DEAD ZONE DISTORTION

The analytical expression of the dead zone distortion DDZ is calculated using some noticeable properties of the pdf. We have: DDZ (RDZ ) = The bracketed integral is the repartition function Fn-1 of the radius law for a GG distribution of dimension n -1.

P

  (e = r) log 2 P (e = r) -log 2 N (r)

Figure 1 :

 1 Figure 1: Typical shapes of the Gamma distribution.

Figure 2 :

 2 Figure 2: Histogram of the norm of vectors (size 8) of the vertical wavelet sub-image of Lena (level 3) and the corresponding estimated two Gamma mixture density with parameters a = [5.12, 1.49], b = [0.92, 0.03] and c = [0.24, 0.76].

  D with block mixture distribution Theoretical R-D with i.i.d. Laplacian distribution

Figure 3 :

 3 Figure 3: LVQ R-D functions (level 2 vertical sub image of Lena image): real data, proposed mixture model and i.i.d. Laplacian model.

Figure 4 :

 4 Figure 4: Histogram of the norm of vectors after DZLVQ on: (A) Laplacian source (zero mean and standard deviation equals to 7.7) (B): Level 3 vertical orientation wavelet coefficients of Lena image. Parameters of DZLVQ are identical for both (A) and (B).

Figure 5 :

 5 Figure 5: SNR as a function of the bit rate for DZLVQ and LVQ applied on the vertical sub image of Lena (level 3).

  D with block mixture distribution Theoretical R-D with i.i.d. Laplacian distribution

Figure 6 :

 6 Figure 6: DZLVQ R-D functions (level 2 vertical sub image of Lena image): real data, proposed mixture model and i.i.d. Laplacian model.

  ) -D real (i)| D real (i) max RE = max i=1,...,N test |D(i) -D real (i)| D real (i)

2 f 1 <

 21 (x1, ..., xn) dx1...dxn = X α α <R DZ x 2 1 + ... + x 2 n GG(x1)...GG(xn)dx1...dxn.X being i.i.d:DDZ (RDZ ) = n i=1 X α α <R DZx 2 i GG(x1)...GG(xn)dx1...dxn DDZ (RDZ ) = n x1)...GG(xn)dx1...dxnWe denote A = {|x2| α + ... + |xn| α < RDZ -|x1| α }.Then we have:DDZ (RDZ ) = n |x| α <R DZ x 2 GG(x) RDZ = {|x1| < RDZ } ∩ A

For sake of simplicity we still call norm the norm at power α.

For sake of simplicity GG(x; α, β) is replaced here by GG(x)