Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source
A simple and complete asymptotical analysis of an optimal piecewise uniform quantization of two-dimensional memoryless Laplacian source with the respect to distortion (D) i.e. the mean-square error (MSE) is presented. Piecewise uniform quantization consists of L different uniform vector quantizers....
Gespeichert in:
| Datum: | 2004 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут проблем реєстрації інформації НАН України
2004
|
| Schriftenreihe: | Реєстрація, зберігання і обробка даних |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/50641 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source / Zoran H. Peric, Ivana Lj. Tosic // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 1. — С. 20-33. — Бібліогр.: 11 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-50641 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-506412013-11-06T18:54:10Z Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source Perić, Z.H. Tosic, I.L. Математичні методи обробки даних A simple and complete asymptotical analysis of an optimal piecewise uniform quantization of two-dimensional memoryless Laplacian source with the respect to distortion (D) i.e. the mean-square error (MSE) is presented. Piecewise uniform quantization consists of L different uniform vector quantizers. Uniform quantizer optimality conditions and all main equations for optimal number of output points and levels for each partition are presented (using rectangular cells). The optimal granular distortion Doptg (i) for each partition in a closed form is derived. Switched quantization is used in order to give higher quality by increasing signal-to-quantization noise ratio (SQNR) in a wide range of signal volumes (variances) or to decrease necessary sample rate. Представлен простой и полный асимптотический анализ оптимального, кусочно-равномерного квантования двумерного лапласовского источника без запоминания относительно искажения (D), т.е. среднеквадратическая ошибка (СКО). Кусочно-равномерное квантование состоит из L различных векторных квантователей с равномерным шагом. Представлены с использованием прямоугольных элементов оптимальные условия для квантователей с равномерным шагом и все основные уравнения для оптимального количества выходных точек и уровней при каждом разделении. Получено оптимальное искажение, обусловленное зернистостью изображения Doptg (i), для каждого разделения в замкнутом виде. Квантование с переключением используется для достижения более высокого качества путем увеличения отношения сигнал/шум квантования (SQNR) в широком диапазоне уровней сигнала (колебаний) или уменьшения необходимой частоты выборки. Наведено простий і повний асимптотичний аналіз оптимального, кусково-рівномірного квантування двомірного лапласівського джерела без запам’ятовування відносно викривлення (D), тобто середньоквадратичної помилки (СКП). Кусково-рівномірне квантування складається з L різноманітних векторних квантувателів з рівномірним шагом. Наведено з використанням прямокутних елементів оптимальні умови для квантувателів із рівномірним шагом і всі основні рівняння для оптимальної кількості вихідних точок і рівнів для кожного розподілення. Отримано оптимальне викривлення, що обумовлене зернистістю зображення Doptg (i), для кожного розподілення у замкнутому вигляді. Квантування з перемиканням використовується для досягнення більш високої якості шляхом збільшення відношення сигнал/шум квантування (SQNR) у широкому діапазоні рівнів сигналу (коливань) або зменшення необхідної частоти вибірки. 2004 Article Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source / Zoran H. Peric, Ivana Lj. Tosic // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 1. — С. 20-33. — Бібліогр.: 11 назв. — англ. 1560-9189 http://dspace.nbuv.gov.ua/handle/123456789/50641 004.93 en Реєстрація, зберігання і обробка даних Інститут проблем реєстрації інформації НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Математичні методи обробки даних Математичні методи обробки даних |
| spellingShingle |
Математичні методи обробки даних Математичні методи обробки даних Perić, Z.H. Tosic, I.L. Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source Реєстрація, зберігання і обробка даних |
| description |
A simple and complete asymptotical analysis of an optimal piecewise uniform quantization of two-dimensional memoryless Laplacian source with the respect to distortion (D) i.e. the mean-square error (MSE) is presented. Piecewise uniform quantization consists of L different uniform vector quantizers. Uniform quantizer optimality conditions and all main equations for optimal number of output points and levels for each partition are presented (using rectangular cells). The optimal granular distortion Doptg (i) for each partition in a closed form is derived. Switched quantization is used in order to give higher quality by increasing signal-to-quantization noise ratio (SQNR) in a wide range of signal volumes (variances) or to decrease necessary sample rate. |
| format |
Article |
| author |
Perić, Z.H. Tosic, I.L. |
| author_facet |
Perić, Z.H. Tosic, I.L. |
| author_sort |
Perić, Z.H. |
| title |
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source |
| title_short |
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source |
| title_full |
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source |
| title_fullStr |
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source |
| title_full_unstemmed |
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source |
| title_sort |
piecewise uniform switched vector quantization of the memoryless two-dimensional laplacian source |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2004 |
| topic_facet |
Математичні методи обробки даних |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/50641 |
| citation_txt |
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source / Zoran H. Peric, Ivana Lj. Tosic // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 1. — С. 20-33. — Бібліогр.: 11 назв. — англ. |
| series |
Реєстрація, зберігання і обробка даних |
| work_keys_str_mv |
AT periczh piecewiseuniformswitchedvectorquantizationofthememorylesstwodimensionallaplaciansource AT tosicil piecewiseuniformswitchedvectorquantizationofthememorylesstwodimensionallaplaciansource |
| first_indexed |
2025-07-04T12:24:58Z |
| last_indexed |
2025-07-04T12:24:58Z |
| _version_ |
1836719170674229248 |
| fulltext |
Математичні методи обробки даних
20
UDC 004.93
Zoran H. Peric, Ivana Lj. Tosic
Faculty of Electronic Engineering, University of Nis, Serbia, Yugoslavia
e-mail: peric@elfak.ni.ac.yu
Piecewise uniform switched vector quantization
of the memoryless two-dimensional Laplacian source
A simple and complete asymptotical analysis of an optimal piecewise
uniform quantization of two-dimensional memoryless Laplacian source with
the respect to distortion (D) i.e. the mean-square error (MSE) is presented.
Piecewise uniform quantization consists of L different uniform vector quan-
tizers. Uniform quantizer optimality conditions and all main equations for
optimal number of output points and levels for each partition are presented
(using rectangular cells). The optimal granular distortion opt
gD (i) for each
partition in a closed form is derived. Switched quantization is used in order
to give higher quality by increasing signal-to-quantization noise ratio
(SQNR) in a wide range of signal volumes (variances) or to decrease neces-
sary sample rate.
Key words: piecewise uniform quantization, switched quantization, distor-
tion
Introduction
The use of digital representation for audio, speech, images and video is rapidly
growing with the extending use of computers and multimedia computer applications. To
provide a more efficient representation of data, many compression algorithms have been
developed, and in the basis of all these algorithms is quantization. The concept of quan-
tization is a mapping of a large set of amplitudes of infinite precision to a smaller finite
set of values, as shown in the Fig. 1(a). Vector quantization is simply an extension of
the scalar quantization to multidimensional spaces; that is, a vector quantizer operates
on vectors (blocks of samples) instead on scalars.
The quantizers play an important role in the theory and practice of modern signal
processing. The asymptotic optimal quantization problem, even for the simplest case —
uniform scalar quantization, is very actual nowadays [1, 2]. They do consider the prob-
lem of finding the optimal maximum amplitude, so-called, support region for scalar
quantizers by minimization of the total distortion D, which is a combination of granular
© Zoran H. Peric, Ivana Lj. Tosic
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 1 21
(Dg) and overload (Do) distortion, og DDD += . Extensive results have been obtained
on scalar quantization but more on vector quantization. The simplest vector quantization
is two-dimensional vector quantization.
Fig. 1. Illustration of (a) scalar and (b) vector quantization
The analysis of vector quantizer for arbitrary distribution of the source signal is
given in paper [3]. The authors derived the expression for the optimum granular distor-
tion and optimum number of output points. However, they did not prove the optimality
of the proposed solutions. Also, they did not define the partition of the multidimensional
space into subregions. In paper [4], the expressions for the optimum number of output
points are derived, however the proposed partitioning of the multidimensional space for
memoryless Laplacian source does not consider the geometry of the multidimensional
source. In paper [5], vector quantizers of Laplacian and Gaussian sources are analyzed.
The proposed solution for the quantization of memoryless Laplacian source, unlike in
[5], takes into consideration the geometry of the source, however, the proposed vector
quantizer design procedure is too complicated and unpractical.
In this paper we give a systematic analysis of piecewise uniform vector quantizer
(PUQ) of Laplacian memoryless source. We give a general and simple way to design a
piecewise uniform vector quantizer. We derive the optimum number of output points
and the optimality of the proposed solutions is proved. The goal of this paper is to solve
a quantization problem in a case of PUQ and to find corresponding support region. It is
done by analytical optimization of the granular distortion and numerical optimization of
the total distortion. If the distortion is measured by a squared error, D becomes the mean
squared error (MSE). The distortion mean-squared error (MSE i.e. quantization noise) is
used as a criterion for optimization.
The MSE of a two-dimensional vector source ),( 21 xxx = , where ix are zero-mean
statistically independent Laplacian random variables of variance 2s , is commonly used
for the transform coefficients of speech or imagery. The first approximation to the long-
time-averaged probability density function (pdf) of amplitudes is provided by Laplacian
0
1
2
3
4
real numbers
unquantized samples
0
1
2
3
4
integers
quantized samples
(a)
0
1
2
3
4
block into vectors
unquantized samples
codevector
indicies
000 100001 010 011
codevectors
codebook with 2-D codevectors
(b)
Zoran H. Peric, Ivana Lj. Tosic
22
model [7, p. 32]. The waveforms are sometimes represented in terms of adjacent-sample
differences. The pdf of the difference signal for an image waveform follows the Lapla-
cian function [7, p. 33]. The Laplace source is a model for speech [8, p. 384]. Consider
two independent identically distributed Laplace random variables (x1, x2) with the zero
mean and unity variance. To simplify the vector quantizer, the Helmert transformation
is applied on the source vector giving contours with constant probability densities. The
transformation is defined as: ( )212
1 xxr += , ( )212
1 xxu -= . In this paper, quan-
tizers are designed and analysed under additional constraint — each scalar quantizer is a
uniform one.
PUQ consists of L optimal uniform vector quantizers. More precisely, our quantizer
divides the input plane into L partitions and every partition is further subdivided into iL
( Li ££1 ) subpartitions. Every concentric subpartition can be subdivided in four equiva-
lent regions, i.e. The j-th subpartition in signal plane is allowed to have ijp
( iLjLi ££££ 1,1 ) cells. We perform two-step optimization: 1) distortion optimiza-
tion ( iD ) in every partition under the constraint i
L
j
ij Np
i
=å
=1
4 and 2) optimization of the
total granular distortion å
=
=
L
i
ig DD
1
which achieves the optimal number of points iN
on each partition under the constraint å
=
=
L
i
i NN
1
.
In this work we design a piecewise uniform vector quantizer for optimal compres-
sion function. We perform analytical optimisation of the granular distortion and
numerical optimization of the total distortion using rectangular cells.
The switching quantization aims are to improve the quality of the signal-to-noise
ratio in the wide range of the signal average power (i.e. variance) or to decrease the
sample rate. The switching quantization is adaptive quantization for memoryless
sources and it is aplicable only if adaptation is performed on the basis of the signal
average power, what was just done in this paper. As an input source, we will consider
memoryless Laplacian source.
Basic notes on VQ
The conceptual notion of VQ is illustrated in Fig. 1(b). These blocks of samples are
represented by code vectors and stored in a codebook — a process called encoding. A
block diagram of the encoder is shown in Fig. 2. The encoder e performs a mapping
from k-dimensional space kR to the index set I , and the decoder D maps the index set
I into the finite subset C , which is the codebook. The codebook has a positive integer
number of code vectors (denoted by iy ) that defines the codebook size, denoted by N.
The bit rate R associated with the VQ depends on N and the vector dimension k. Since
the bit rate is the number of bits per sample,
kNR /)(log 2= . (1)
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 1 23
In contravention to basic scalar quantization which is fixed-rate, for VQ is natural
to have fractional bit rates such as ½, ¾, etc. The decoding process is very simple and
requires only a table (codebook) lookup, but the encoding procedure is complex and in-
volves finding a best matching code vector, using a distortion measure as a criterion.
The most common distortion measure is mean squared error, given by:
å
=
-=--=
k
l
t lylxyxyxyxd
1
2])[][()()(),( , (2)
where ][lx and ][ly are the elements of the vector x and y , respectively.
Fig. 2. Block diagram of a VQ encoder and decoder
It is convenient to view the operation of a vector quantizer geometrically, using our
intuition for the case of two- or three-dimensional space. Thus, a 2-dimensional quan-
tizer assigns any input point in the plane to one of a particular set of N points or loca-
tions in the plane. The plane is divided into N partition cells, as shown in the Fig. 3(a),
and the dots represent code vectors, one in each cell. A unique partitioning of the space
is defined by the encoding procedure, and optimized for a given input source, to give
the best performance. Now consider the quantizing of our fictional input source with
scalar quantization at an equivalent bit rate. The cells implying the use of a scalar quan-
tizer for the input source are shown in Fig. 3(b). Notice that each cell is should to be
rectangular, and some cells are forced to be placed in regions where the input source
may not be significantly populated. These observations lead to two immediately recog-
nizable advantages of VQ over scalar quantization. First, VQ provides greater freedom
to control the shapes of the cells to achieve more efficient tilings of the space. This
property is often called cell shape gain. Second, VQ allows a greater number of cells to
be concentrated in the regions where the source has the greatest density, which reduces
the average distortion.
000
001
010
111
i
searchx output index
i
000
001
010
111
i
lookupx x y=
ENCODER DECODER
E DI
encoder
codebook
decoder
codebook
reconstructed
vector
indices
codevectors
y
Zoran H. Peric, Ivana Lj. Tosic
24
Fig. 3. Illustration of the partition cell associated with VQ and scalar quantization:
a) partition cells for a 2D VQ; b) partition cells corresponding to scalar quantization
Piecewise uniform vector quantizer design
Joint pdf function of two independent, identically distributed Laplace random
variables (x1 , x2 ) with zero mean is given with the following expression
( )
( )
s
s
212
2212,1 2
1,
xx
exxf
+
-
= . (3)
After applying the Helmert transformation [9, 10]
( )212
1 xxr += , ( )212
1 xxu -= (4)
we get the probability density function
s
s
r
eurf
2
22
1),(
-
= . (5)
In the two-dimensional ru system the pdf function given by equation (5) represents
a square line. The square surface (0, maxr ) representing dynamic range of a two-
dimensional quantizer, can be partitioned into L concentric domains as shown in Fig. 4.
In the case of nonuniform vector quantization, these concentric domains are of unequal
width. The number of output points in each domain is denoted by iN , where
å =
=
L
i iNN
1
represents the total number of output points. Every concentric domain can
be further partitioned into iL concentric subdomains of equal width. Every subdomain
is divided into four regions each containing jip , rectangular cells. An output point is
placed in the centre of each cell. Coordinates of the k-th output point in j-th subregion of
the i-th region in the ru coordinate system are ( )kjiji um ,,, € , .
(a) (b)
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 1 25
Fig. 4. Two-dimensional space partitioning
The initial expression for granular distortion is
( ) ( )[ ] drdueuumrD
rL
i
L
j
p
k
r
r
u
u
kjijig
i ji ji
ji
kji
kji
s
s
2
2
1 1 1
2
,,
2
, 2
1€4
, 1,
,
1,,
,,
-
= = =
ååå ò ò
+ +
×-+-= . (6)
The otput point coordinates are given by the equations
2
,1,
,
jiji
ji
rr
m
+
= + and
2
€ 1,,,,
,,
++
= kjikji
kji
uu
u . (7)
Rectangular cell dimensions are:
iii rr -=D +1 ,
i
i
i L
D
=D¢ and
ji
jiji
ij p
rr
,
1,, ++
=D ; (8)
iiji jrr D×+=, , Li ,,0 K= , iLj ,,0 K= . (9)
The range of the quantizer is maxr . To determine the boundary values of every
concentric domain, denoted as ir , for the case of nonuniform vector quantization we
perform the segmentation and linearization of the optimal compress function, given by
the following expresion
1
1)(
max2
1
2
1
max
-
-
=
-
-
r
r
e
errh
s
s
. (10)
The method for linearization of compression function, named the first derivate
segmentation, was selected based on the analysis performed in [11]. The principle used
( )kjiji um ,,, €,
u
r
r
ir
i
r
i
r
i,j+1
r
i,j
m
i,j
r
i+1
u
ijk
u
i, j,k+1
D
i,j
(i)
2m
i,j
kjiji um ,,, €,
Zoran H. Peric, Ivana Lj. Tosic
26
in this method is to do a uniform segmentation of the first derivate of compression func-
tion, and find corresponding ir points by substituting uniformly distributed h¢ values in
the inverse first derivate function.
The total number of output points is
å
=
=
L
i
iNN
1
, (11)
where iN is the number of output points in the i-th domain. We can also write:
(12)
Equation (12) can be written as
),(
1
iDD
L
i
gg å
=
= (13)
where )(iDg is
( ) ( ) ( )[ ] drdueuumriD
rL
j
p
k
r
r
u
u
kjijig
i ji ji
ji
kji
kji
s
s
2
2
1 1
2
,,
2
, 2
1€4
, 1,
,
1,,
,,
-
= =
åå ò ò
+ +
×-+-= . (14)
After integration over u and reordering equation (14) becomes
( ) ( ) ( ) ( )
ú
ú
û
ù+
ê
ê
ë
é
++-= òå ò
++
-+
=
-
+
1,
,
1,
,
2
22
,
3
,1,
1
2
2,1,
2
,
2
12
2 ji
ji
i ji
ji
r
r
r
ji
jiji
L
j
r
r
r
jijijig dre
p
rr
drerrmriD ss
ss
. (15)
From equation (7) it follows that jijiji mrr ,,1, 2=++ . When we substitute this in
equation (15) we get
( ) ( )
ú
ú
û
ù
ê
ê
ë
é
+-= òå ò
++ -
=
- 1,
,
1,
,
2
2,2
,
2
,
1
2
2,
2
,
14
3
14
ji
ji
i ji
ji
r
r
r
ji
ji
ji
L
j
r
r
r
jijig drem
p
m
dremmriD ss
ss
. (16)
We will now assume that ( )s/2exp r- is constant over iD . In that case we can
substitute ( )s/2exp r- with ( )s/2exp , jim- . Equation (16) can be now written as:
41
,
i
L
j
ji
N
p
i
=å
=
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 1 27
( ) ( )å òò
=
-
ú
ú
û
ù
ê
ê
ë
é
+-=
++i ji
ji
ji
ji
jiL
j
r
r ji
ji
r
r
ji
m
jig dr
p
m
drmremiD
1
2
,
2
,2
,
2
2,
1,
,
1,
,
,
3
14 s
s
=
å
=
-
ú
ú
û
ù
ê
ê
ë
é
D+
D
=
i jiL
j
i
ji
jii
m
ji p
m
em
1
2
,
2
,
32
2, 312
14
,
s
s
= (17)
( )å
=
×
ú
ú
û
ù
ê
ê
ë
é
+
D
=
iL
j
ji
ji
jii
ji mP
p
m
m
1
,2
,
3
,
2
, 3
2
12
2 .
where ( )jimP , denotes the probability
( ) ( ) s
s
jim
ijiiji emfmP
,2
2,,
2 -
D=D= . (18)
Function ( )jimf , is defined as
( ) s
s
jim
ji emf
,2
2,
2 -
= . (19)
By using the Langrangian multipliers we can obtain the optimum number of cells
in one region jip , , which yields the minimum granular distortion defined by the
equation (17). Because we are designing an optimal quantizer for one value of variance
0s , in calculating jip , we will use 0s instead of s . We will start from the following
equation
(20)
After differentiating J with respect to jip , , and equalizing the derivate with zero we
get
( ) 0
3
4
0 ,03
,
3
,
,
=+-Þ=
¶
¶
lji
ji
ji
ji
mP
p
m
p
J . (21)
From the preceding equation we can write the following:
( ) ( )
3 ,0
,
3
,0
3
,
, 3
4
3
4
ll
iji
jiji
ji
ji
mf
mmP
m
p
D
== . (22)
( ) å
=
+=
iL
j
jig piDJ
1
,l
Zoran H. Peric, Ivana Lj. Tosic
28
If we substitute jip , from equation (22) in equation (12)
( )
43
4
1
3 ,0
,
i
L
j
iji
ji
Nmf
m
i
=
D
å
= l
, (23)
we can eliminate l by substituting
( )å
=
D=
iL
j
ijiji
i
mfm
N 1
3
,0, 443l (24)
in equation (22):
( )
( )å
=
=
iL
k
kiki
jijii
ji
mgm
mgmNp
1
3
,0,
3
,0,
, 4
, (25)
where ( )jimg ,0 denotes the function
( ) 0
,2
2
0
,0
1 s
s
jim
ji emg
-
= . (26)
If we multiply numerator and denominator with iD , we can approximate the sum
by the integral
( )
( )ò
+
×
D×
=
1
4
3
0
3
,0,
, i
i
r
r
ijijii
ji
drrgr
mgmNp . (27)
By substituting jip , from equation (27) in equation (17) we get
( ) åå
==
D¢¢
D
+D¢
D
=
ii L
j
i
ji
ji
ji
ii
i
L
j
ijiji
i
i
g mg
mg
miI
N
Lmgm
L
iD
1
3/2
,0
,
,
2
022
2
1
,0,2
2
)(
)(
)(
3
64
)(
3
. (28)
After approximating the sum by the integral, we can rewrite (28) as
( ) ( ) ( ) )(
3
64
3
2
022
2
2
2
iIiI
N
LiI
L
iD
i
i
i
g ¢¢
D
+
D
= . (29)
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 1 29
The functions ( )iI0¢ , )(iI ¢ and ( )iI are defined as:
( ) ( )
( )
( ) ( ) .
;
)(
)(
;
1
1
1
3/2
0
3
00
ò
ò
ò
+
+
+
×=
×=¢
×=¢
i
i
i
i
i
i
r
r
r
r
r
r
drrgriI
dr
rg
rgriI
drrgriI
(30)
After differentiating Dg from equation (29) with respect to Li, and for 0s , we
obtain the optimum number subdomains in i-th domain
( )
( )
4 3
0
2
0
64 iI
NiIL i
iopt ¢
D= , (31)
where )(0 iI is defined as
( ) ( )ò
+
×=
1
00
i
i
r
r
drrgriI . (32)
Substituting the expression for Li from equation (31) in equation (29), Dg(i)
becomes
( ) ÷
÷
ø
ö
ç
ç
è
æ
¢×
¢
+×
¢
¢= )(
)(
)(
)(
)(
)(
)(8
0
0
0
0
0 iI
iI
iIiI
iI
iIiI
N
iD
i
g . (33)
The optimum number of output points in the ith subdomain is obtained using
Lagrangian multipliers
(34)
After differentiating (33) with respect to Ni, and for 0s we get:
( ) ( ) ( )
l3
16 000 iIiIiI
N i
¢¢
= . (35)
Using the condition (11) we can eliminate l from the equation (35)
( ) å
=
+=
L
i
iig NNDJ
1
l
Zoran H. Peric, Ivana Lj. Tosic
30
( ) ( )[ ]
( ) ( )[ ]å
=
¢
¢
= L
k
i
kIkI
iIiINN
1
41
0
3
0
41
0
3
0
. (36)
Finally, after substituting the expression for optimum number of output points from
equation (36) into equation (33) we can write
( ) ( )[ ]
( ) ( )[ ] ÷
÷
ø
ö
ç
ç
è
æ
¢×
¢
+×
¢
×¢
¢
¢
=
å
= )(
)(
)(
)(
)(
)(
)(
3
8)(
0
0
0
0
041
0
3
0
1
41
0
3
0
iI
iI
iIiI
iI
iIiI
iIiI
kIkI
N
iD
L
k
g . (37)
Now, we can calculate the optimum granular distortion of uniform piecewise vector
quantizer as
( ) [ ] ååå
=== ú
ú
û
ù
ê
ê
ë
é
¢×÷÷
ø
ö
çç
è
æ
¢
+×÷÷
ø
ö
çç
è
æ ¢
×¢==
L
i
L
i
L
i
gg iI
iI
iIiI
iI
iIiIiI
N
iDD
1
4/1
0
0
4/3
0
0
1
4/1
0
3
0
1
)(
)(
)(
)(
)(
)(
)()(
3
8 .(38)
We can calculate the overload distortion as
( ) ( )[ ] drdueuumrD
rp
j r
u
u
jLLL
LLL jL
jL
L
s
s
2
2
1
2
,
2
,0 2
1 €4
,
max
,
,
-
=
¥
å ò ò -+-= . (39)
After some calculation, we get
( )[
.
3
2
22
422
2
,
2
,2
,,
3
,
2
max
2
max
2
2
,
max
ú
ú
û
ù
++-+
+-+=
-
L
L
LL
L
L
LL
LL
LLLL
LL
r
LL
o
p
m
mm
mrre
m
D
ssss
sss
s
s
(40)
From equations (31) and (33), we can calculate the total distortion for one dimen-
sion as
)(
2
1
og DDD += . (41)
Numerical results
The results are shown in Fig. 5 for two values of 0s (two different quantizers):
0dB and –10dB, and for bit rate of R = 7,5. For comparison, dash-dotted lines show
SQNR for scalar quantization for R = 8, for a compression function given with
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 1 31
n
n
-
-
-
-
=
e
errf
r
r
1
1)(
max
max , (42)
where n is a compression factor, with a critical value for 0s
0
max
3
2
s
n
r
c = . (43)
Fig. 5. SQNR for scalar (bit rate = 8) and
vector (bit rate = 7,5) quantization with
two optimal quantizers designed for
different values of 0s
SQNR is a signal-to-quantization noise ratio, given with:
Duk
dBSQNR
2
log10][ s
= . (44)
We can see from this figure that there is a 0,5 bits gain in the case of vector quanti-
zation. In Fig. 6 we have changed bitrate to R = 4.
Fig. 6. SQNR for scalar and vector (bit
rate = 4) quantization with two optimal
quantizers designed for different
values of 0s
-40 -35 -30 -25 -20 -15 -10 -5 0 5 10
-10
0
10
20
30
40
50
variance
S
Q
N
R
[d
B
]
vector (variance=-10dB, 0dB), R=7.5
scalar (v=5,20)
R=8
-40 -35 -30 -25 -20 -15 -10 -5 0 5 10
-20
-15
-10
-5
0
5
10
15
20
25
30
variance
S
Q
N
R
[d
B
]
vector (variance=-10dB, 0dB)
scalar
(v=5, 20)
R=4
Zoran H. Peric, Ivana Lj. Tosic
32
In Table, as an illustration of the previous analysis, the number of rectangular cells
in each of four regions in a particular subdomain, denoted as jip , , is given. The optimal
number of subdomains in every domain ( ioptL ) is calculated for L = 4 concentric do-
mains and bit rate R = 4, giving the value 2.
Number of rectangular cells for R = 4
L = 4 jip ,
1 2 3 4
1 1 6 9 13
2 3 7 11 13
For nonstationary inputs a logical scheme is switched quantization; this consists in
providing a bank of B fixed quantizers, and switching among them as appropriate, in
response to changing input statistics. This scheme is used for two designed quantizers,
as shown in Fig. 7.
Fig. 7. Block diagram of switched quantization
Conclusion
The optimization of two-dimensional Laplace source piecewise nonuniform vector
quantization is carried out. A simple expression for granular distortion, a number of
subdomains and а number of output points in closed form is obtained. The results ob-
tained by using two vector quantizers optimized for two different values of s (vari-
ance) demonstrate the significant performance gain over the uniform scalar quantiza-
tion, giving a 0,5 bits/sample gain. Memoryless Laplacian source is used, considering
the possible application of this quantizer. The transform coefficients of DCT (discrete
cosine transform) encoding of speech or imagery are often modeled as Laplacian, ex-
cept for the DC coefficient of imagery. By using switched quantization, with two quan-
tizers in this case, necessary rate is decreased by 0,5 bits per sample, with compliance of
Q ( )1 ·
Q ( )2 ·
Q ( )B ·
·
·
·
x(n)
CONDITIONAL
ESTIMATOR
Piecewise uniform switched vector quantization of the memoryless two-dimensional Laplacian source
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 1 33
the appropriate standard. With a larger set of quantizers we could increase this sample
rate even more, thus giving a better compression quality with higher SQNR.
1. Hui D., Neuhoff D.L. Asymptotic Analysis of Optimal Fixed-Rate Uniform Scalar Quantization //
IEEE Trans. — 2001. — IT-47(3). — Р. 957–977.
2. Na S., Neuhoff D.L. On the Support of MSE-Optimal, Fixed-Rate Scalar Quantizers // IEEE
Trans. Inform. Theory. — 2001. — IT-47(6). — Р. 2972–2982.
3. Kuhlmann F., Bucklew J.A.. Piecewise Uniform Vector Quantizers // IEEE Trans. — 1988. —
IT-34(5). — Р. 1259–1263.
4. Swaszek P.F. Unrestricted Multistage Vector Quantizers // IEEE Trans. — 1992. — IT-38(3). —
Р. 1169–1174.
5. Jeong D.G., Gibson J. Uniform and Piecewise Uniform Lattice Vector Quantization for Memory-
less Gaussian and Laplacian Sources // IEEE Trans. — 1993. — T-39(3). — Р. 786–804.
6. Gray R.M., Neuhoff D.L. Quantization // IEEE Trans. — 1998. —IT-44(6). — Р. 2325–2384.
7. Jayant N.S.and Noll P. DIGITAL CODING OF WAVEFORMS Principles and Applications to
Speech and Video. — New Jersey: Prentice-Hall, 1984.
8. Gersho A. and Gray R.M. Vector Quantization and Signal Compression. — Kluwer: Aca-
dem.Pub, 1992.
9. Zoran H. Peric, Jelena D. Jovkovic, Zoran J. Nikolic. Two-Dimensional Laplas Source
Quantization // IEEE Сonf. TELSIKS-2001. — Nis (Serbia). — Р. 33–37.
10. Peter F. Swaszek. A vector Quantizer for the Laplas Source // IEEE Trans. Inform. Theory. —
1991. — Vol. 37, N. 5, Sept.
11. Ivana Tosic, Divna Djordjevic. Analysis of Various Linearization Methods for Two-
Dimensional Laplaces Source // TELFOR. — 2002. — Р. 683–686.
Received 23.10.2003
UDC 004.93
UDC 004.93
UDC 004.93
UDC 004.93
UDC 004.93
Zoran H. Peric, Ivana Lj. Tosic
© Zoran H. Peric, Ivana Lj. Tosic
Basic notes on VQ
|