# On Optimal Bit Allocation for Classification-Based Source-Dependent Transform Coding

Authors: David Akopian
Journal: Research Letters in Signal Processing
 (2008)

---

## Abstract

An optimal bit allocation is presented for
classification-based source-dependent transform coding. A vector
of transform coefficients is considered to have been produced by
a mixture of processes. The available bit resource is distributed
optimally in two stages: (1) bit allocation is performed for each
class of coefficient vectors, and (2) bit allocation is performed for
each vector coefficient. The solution for low bit rates imposing
nonnegative bit resource is also presented. The rate-distortion
bound of the classification-based source coding is
derived.


---

## Body

## 1. Introduction

Source coding techniques are used to reduce data in
digital systems to meet realistic transmission and storage constraints. In many
such systems, data is reduced using quantizers and bit allocation methods which
encode quantizer outputs for further processing. Quantizers apply to original
or transformed data and their outputs can be compactly represented for
communication or storage. Popular compressed image formats such as JPEG
[1] and JPEG2000
[2] employ such
techniques to reduce data sizes.Particularly, in the so-called lossy transform/subband
coding techniques [1–20], original signal
data are transformed to a vector source, that is, a set of coefficients. Then
each coefficient is quantized to a symbol which is encoded using certain number
of bits. Coarse quantization outputs are encoded with a fewer number of bits,
but the reconstruction error (distortion) will be higher.The bit allocation problem for the vector source has
been widely addressed in the literature and many different strategies have been
proposed. [9] contains
an extensive overview of various bit allocation approaches in the context of
transform/subband coding methods.The early transform coders were based on i.i.d models
of transform coefficients and bit allocation was performed in proportion to
their importance as defined by the variance of their distributions [4, 5, 8]. In [4], all of the quantizers are described by the same
exponential quantizer function (QF). The method may result in negative bit rates,
which may be corrected using an iterative procedure. In [5], the QF is the same for all
of the quantizers and is strictly convex, although it is not assumed to be
exponential. In addition, a constraint on the nonnegativity of bit rates is
imposed. Both methods are described by closed-form solutions. More general
approaches have been suggested in [6, 7] with an optimal bit allocation strategy found for an
arbitrary set of quantizers and integer bit allocation constraint, but the
solutions are not closed-form.The performance of these coders was later improved by
more accurate modeling of coefficients. One approach simply assumes that the
vector source may come from a finite set of several possible processes with
different distributions
[10–19]. The coder decides to which distribution the
coefficients belong using a classification process and encodes them properly.
The classification process may include additional
transformations [10–14] and may be optimized for
signals of interest, not just typical ones. The classification approach in
[10] improves the
compression ratio twice at a fixed distortion, while up to 2 dB improvement in
reconstruction quality is reported for another approach [13].Practical still image compression
techniques [1–3] rely on simple quantizers,
but finely allocate bit resources adaptively for each transformed image
fragment in an “input-by-input" manner [9], as opposed to a
classification approach described above. Each image fragment is coded in a
deterministic way with coder parameters optimized for that particular input and
not for the ensemble of inputs. Input-by-input or the realization-adaptive
approach is not well explained by classical rate distortion theory as many
practical encoders operate in the low bit rate or high distortion region.Eventhough the realization adaptive approach is in
general superior for still image compression, the extensions of classical
bit-allocation and classification techniques have been successfully applied in
various applications [15–20].In this paper, bit allocation technique is presented
for classification-based methods. In Section2, we systematize the presentation
of our results in [13, 14] which were later rederived in [17, 18] in another context. Then in
Section 3 we extend this solution by imposing the nonnegativity constraint on
bit rates for low rate coding and estimate the rate-distortion boundary for the
classification approach (Section 3).


## 2. Bit Allocation for Classification-Based Method

Subsequently in the paper, we operate on blocks
(vectors) of data to be quantized. Our purpose here is to present results for
transform coders where quantization is applied to the transformed coefficients.
However, the method could be applied to other vector sources as well.The classical bit allocation techniques assume the
same number of bits allocated to different blocks, and they address optimal bit
resource allocation between coefficients. In our model, the blocks of data may
come from different sources, and the goal is to optimally distribute the bits
among the blocks and block coefficients [13, 14].LetR be the average number of bits per sample. If       Ri⁢(i=0,…,M−1) bits are allocated to the ith coefficient, then the quantization error in
the output of an optimal quantizer can be modeled as (1)σqi2=ϵ22−2Riσi2,where ϵ is the coefficient which depends on the pdf of
the input signal, σi2 is the variance of the input to quantizer i. By definition ∑i=0M−1Ri=M⋅R.
The following optimal classical bit allocation minimizes the overall
distortion:(2)Ri=R+12log⁡2σi2[∏j=0M−1σj2]1/M.LetR be the average number of bits per sample, Rk is the average number of bits per sample for a
vector (block) belonging to a class k,⁢k∈{0,…,K−1}, Rk,i is the number of bits assigned to coefficient i of the vector from class k.
Let wk be the probability of a vector (block) from
class k.
The probabilities can be estimated based on the block classification approach
used. For example, it can be estimated using a training signal, and no
constraints are imposed on the classification approach.The bit allocation problem is a two-stage process. The
first stage: the average bit resourceR is distributed among the classes so that ∑k=0K−1wkRk=R.
The second stage: for blocks assigned to each class k,
find the optimal bit allocation strategy among the quantized coefficients with
the overall bit resource Rk.For the second stage, the bit allocation is simply the
classical solution:(3)Rk,i=Rk+12log⁡2σk,i2[∏j=0M−1σk,j2]1/Mwith the resulting
distortion:(4)Dk=ϵ22−2Rk[∏j=0M−1σk,j2]1/M=Ak2−2Rk,where(5)Ak=ϵ2[∏j=0M−1σk,j2]1/M.Average distortion over all
classes:(6)D=∑k=0K−1wkDk.An optimal bit-allocation for
the first stage can now be formulated as(7)min⁡R0,…,RK−1Dundertheconstraint∑k=0K−1wkRk=R.Observe that the resulting
distortion for the whole block (4) is similar to the distortion function in the
output of a single quantizer (1) with the difference that Rk represents the average number of bits per  sample for blocks from class k. One can expect that the optimization problem will result in the
classical log-variance rule and this is indeed the case. We use the method of
Lagrange multipliers to solve this problem [14]:
(8)∂∂Rk[D−λ(R−∑l=0K−1wlRl)]=0;k=0,1,…,K−1,−2⁡ln⁡2Ak2−2Rkwk+λwk=0,k=0,1,…,K−1,from which we find expressions
for Rk:  (9)Rk=−12⁡log⁡2⁢λ2⁡ln⁡2+12⁡log⁡2⁡Ak=Λ+12log⁡2Ak,k=0,1,…,K−1.From the constraint ∑l=0K−1wlRl=R,
and the condition ∑l=0K−1wl=1, one can obtain(10)Λ=R−∑l=0K−1wl2⁡log⁡2⁢Al,Rk=R−∑l=0K−1wl2⁡log⁡2⁢Al+12⁡log⁡2⁢Ak,and finally(11)Rk=R+12log⁡2Ak∏l=0K−1[Al]wl.If the quantization is performed in the transform
domain and inverse orthogonal transform is used to reconstruct data, then the
average distortion in output is equal to the distortion produced by quantizers
in the transform domain. The bit allocation rule obtained above applies. In
certain cases, the distortion of the reconstructed source is not equal to the
distortion introduced by quantizers. This is, for example, the case when
additional weighting is applied prior to quantization to account for the human
visual system or when the inverse transformation/filterbank is not orthogonal.
In such scenarios, weighting factorsγi,k are multiplied to the variances σk,i2 and in our solutions σk,i2→γk,iσk,i2.
More details for filterbanks can be found in our earlier work [13].


## 3. Bit Allocation for a General Quantization Function and Low Bit Rates

In this section, we generalize the results from
[5] for a
classification-based approach to account for a general quantizer function and
low bit rates, for which the result of Section 2 may produce negative bit
allocations. Assume that Q(R) is a quantizer function defining the average
distortion on the quantizer output as a function of the allocated bits, defined
for unit variance input. The distortion that results from quantizing the input
with variance σ2 is σ2Q(R).
Let Q(R) be strictly convex with a continuous first
derivative Q′(R), Q′(∞)=0,
and let h(⋅) be the inverse function of Q′(⋅).
Let us denote R as the average rate per sample, and Rk,j as the number of bits assigned to the jth component of the quantized block belonging
to a class k.
Similarly, σk,j is the variance of the component j from class k.
Then the allocation of bits that will minimize the average total distortion per
block: (12)D=∑k=0K−1∑j=0M−1wkσk,j2Q(Rk,j).Subject to constraints (13)∑k=0K−1wk∑j=0M−1Rk,j=MR,Rk,j≥0,k=0,…,K−1,j=0,…,M−1,is given by(14)Rk,j={Rk,j*=h(θ*σk,j2Q′(0)),if0<θ*<σk,j20,ifθ*≥σk,j2, where θ* is the unique root of the equation: (15)∑k,j:σk,j2≥θ*wkh(θ*σk,jQ′(0))=M⋅R,and the value of minimum
distortion is (16)D*(θ*)=∑k,j:σk,j2≥θ*wkσk,j2Q(Rk,j*)+∑k,j:σk,j2<θ*σk,j2.Proof.
This allocation rule follows from
[5, Proposition 2.1].
Let us consider the joint quantization of large number (N) of transform coefficient blocks. The vector
is now of larger size, and let us apply the classical bit allocation to this
extended vector. Then the problem is to minimize the total distortion:(17)Dt=∑n=0N−1∑j=0M−1σj2Q(Rn,j). Subject to constraints(18)∑n=0N−1∑j=0M−1Rn,j=N⋅M⋅R,Rn,j≥0.
According to
[5, Proposition 2.1], the solution to this
problem is(19)Rn,j={Rn,j*=h(θ*σn,j2Q′(0)),if0<θ*<σn,j20,ifθ*≥σn,j2,where θ* is the unique root of the equation: (20)∑n,j:σn,j2≥θ*h(θ*σn,jQ′(0))=N⋅M⋅R,and the value of the minimum
overall distortion is (21)Dt*(θ*)=∑n,j:σn,j2≥θ*σn,j2Q(Rn,j*)+∑n,j:σn,j2<θ*σn,j.2
Recall that there are onlyK possible classes. Let the blocks from the same
classes be grouped together and denote the number of blocks belonging to class k as  Nk,k=0,…,K−1.
Then (20),
(21) will become (22)∑k,j:σk,j2≥θ*NkN⋅h(θ*σk,jQ′(0))=M⋅R,Dt*(θ*)N=∑k,j:σk,j2≥θ*NkN⋅σk,j2Q(Rk,j*)+∑k,j:σk,j2<θ*NkN⋅σk,j2.For an ensemble of realizations, Nk/N→wk is the probability of the transformed block
belonging to a class k.
The bit allocation (19) applies here as well. This concludes the proof of the
above statement.Remark on
rate-distortion bound for the classification-based source-dependent
quantization. The rate-distortion
bound for a unit variance source is given by the formula R(D)=⁡(1/2)log⁡(1/D),D≤1 with Q(R)=2−2R, Q′(R)=−2⋅2−2B⋅⁡ln⁡2 and h(x)=(1/2)⁡log⁡2[−2⁡ln⁡2/x],⁢x<0 [5]. For the classification-based source-dependent
quantization, the bit allocation rule described above and k=0,…,K−1, j=0,…,M−1, are
(23)Rk,j=max⁡(0,12log⁡2σk,j2θ*),where θ* is obtained from(24)∑k,jwk⁢⁡max⁡(0,12log⁡2σk,j2θ*)=M⋅R,and the minimum distortion
is(25)D*=∑k,j:θ*≤σk,j2wkθ*+∑k,j:θ*>σk,j2wkσk,j2=∑k,jwk⁡min⁡(θ*,σk,j2).The side information is bounded by entropy and the
minimum rate for a lossless compression isRside=−wk⁡log⁡2⁢wk,
which is counted per transformed block. The overall rate (per sample) is
counted as(26)R=1MRside+1M∑k=0K−1∑j=0M−1wkRk,j.Figure1 presents a simulation example. The input
signal is assumed to have blocks of 16 samples from four stationary
unit-variance, first-order, zero-mean, Markov processes with covariance
function r(n)=ρ|n|.
Blocks of data are transformed by discrete cosine transform (DCT). The
parameters (ρk) and probabilities (wk) for these processes are (0.95, 0.7), (0.75,
0.1), (0.65, 0.1), and (0.55, 0.1). For rate-distortion bound estimation it is
assumed that an ideal classification is performed and a comparison is made with
conventional bit allocation, which is derived for a single-process assumption.
The rate-distortion figure demonstrates that, at equal quantization
distortions, the bit rate bound achieved with the source classification method
is lower for most of the rates. When the bit rate approaches zero, the
rate-distortion characteristics are occasionally worse than with the
conventional quantization due to the side information. The reason for this
effect lies in the fact that some of the classes are not assigned any bits due
to coarse quantization.Figure 1
Example of rate-distortion bound improvement
for source-dependent quantization. Data are assumed from 4 different sources,
transformed by discrete cosine transform (DCT). Ideal classification after the
DCT transform prior to quantization. Class probabilitieswk are 0.7, 0.1, 0.1, and 0.1. Original sources
are stationary unit variance, zero mean, first-order, Markov processes with ρk from the set {0.95,0.75,0.65,and0.55}.


## 4. Conclusion

This paper presents an optimal bit allocation
technique for compression methods using the classification of vector sources.
First, we generalized the well-known log-variance rule using the exponential
quantizer function. The quantizer function is often approximated more
accurately with other functions and the log-variance rule may produce negative
bit quotas at low bit rates. For this reason, the solution for a more general
quantizer function and low bit rates is also presented. The rate-distortion
bound is calculated for the model of source-dependent quantization, and it
illustrates improvement in coding performance.



---

*Source: 421650-2008-03-26.xml*