=Paper=
{{Paper
|id=Vol-2665/paper7
|storemode=property
|title=Algorithm for optimizing quantization scales by an arbitrary quality measure
|pdfUrl=https://ceur-ws.org/Vol-2665/paper7.pdf
|volume=Vol-2665
|authors=Nikolay Glumov,Mikhail Gashnikov
}}
==Algorithm for optimizing quantization scales by an arbitrary quality measure ==
https://ceur-ws.org/Vol-2665/paper7.pdf
Algorithm for optimizing quantization scales
by an arbitrary quality measure
Nikolay Glumov Mikhail Gashnikov
Department of GIS and ITsec Department of GIS and ITsec
Samara National Research University; Samara National Research University;
MMIP laboratory MMIP laboratory
Image Processing Systems Institute of RAS - Branch of the FSRC Image Processing Systems Institute of RAS - Branch of the FSRC
"Crystallography and Photonics" RAS "Crystallography and Photonics" RAS
Samara, Russia Samara, Russia
nglu@smr.ru mih-fastt@yandex.ru
Abstract—This work deals with the task of constructing scales. Lloyd-Max scales [7] are the most famous of the non-
quantization scales optimal by an arbitrary criterion. Besides, uniform quantization scales. We build these scales based on
these scales also satisfy the selected constraint. We consider minimizing the root mean square error. The constraint is
a formal description of this optimization problem. We propose a given (fixed) number of quantization levels.
an algorithm for constructing quasi-optimal quantization
scales that approximate optimal scales with the required Despite the optimality of the error, the Lloyd-Max scales
precision, subject to the constraint. We formulate are not the best when solving many applied problems, since
requirements for the optimization criterion and the restriction, we often need to optimize not some error, but some other
ensuring the performance of the algorithm. We investigate the quality measure. Besides, the levels number of the
proposed quasi-optimal scales using computational quantization scale may not be known, which entails the need
experiments. The experimental results confirm the advantage to use a different constraint when optimizing the scale, other
of the constructed scales over the known ones. than the constraint on the number of levels.
Keywords—quantization scale, non-uniform scale, For example, we need to minimize the compressed data
quantization error, quantizer optimization, standard error size with a fixed error in the compression problem [7-10].
We have to replace both the quality measure and the
I. INTRODUCTION constraint to optimize the quantization scale for compression.
Quantization [1] is the process of mapping input values In this paper, we propose an algorithm for constructing
from a large set to output values in a smaller set. In other a quantizer that is optimal by the required criterion. Besides,
words, quantization is rounding to a predetermined set of we take into account the required constraint when
values. constructing this quantizer. We also describe the
You can use quantization to solve various problems: requirements for this criterion and the requirements for this
processing the phase space of the heart rhythm [2], constraint necessary for the operability of the proposed
normalizing the parameters of neural networks [3], algorithm.
embedding digital watermarks [4-5], processing spaces of
III. QUANTIZER OPTIMIZATION
semi-differentiable functions [6], and quantization of
interpolation errors during compression [7-9], etc. A. Non-uniform scale quantizer
In this paper, we generalize the quantizer [10], proposed We describe a quantizer with a non-uniform [1, 8] scale.
as part of the solution to the compression problem, for the Let the input value x L , R be an integer (for simplicity).
case of an arbitrary quality measure and arbitrary restriction,
which we use when optimizing the quantization scale. We consider the range L , R as the union of quantization
Besides, we also formulate requirements for this quality intervals ( b j , b j 1 ] :
measure and this restriction. The fulfillment of these
requirements allows us to ensure the performance of the N 2
optimization algorithm of the quantization scale. L, R ( b j , b j 1 ], b j Z , b 0 L 1, b N 1 R
j0
II. THE MOST COMMON QUANTIZATION SCALES
We describe the most common quantization scales. We where N is the number of boundaries bj of the
divide the set of input values into quantization intervals. We
specify the quantization level within each quantization quantization intervals ( b j , b j 1 ] . We denote b the vector of
interval. We call the quantization scale the set of the the boundaries of the quantization intervals:
quantization levels and the quantization intervals.
Quantization means that we replace all input values b b j : b j b j 1 , b 0 L 1, b N 1 R , j 0 , N
belonging to the quantization interval with the corresponding
quantization levels. Therefore, the quantization scale We specify the quantization levels c j ( b j , b j 1 ] within
ultimately determines the quantization result. Most often, we
use a uniform scale in which the intervals are the same size, the intervals ( b j , b j 1 ] . We denote с the vector of
and the levels are at the centers of the intervals. quantization levels:
However, the use of uniform scales in many situations
leads to an unacceptably significant error, in particular with a c c j : b j c j b j 1 , j [ 0 , N 2 ]
small number of levels. In these cases, we use non-uniform
Copyright © 2020 for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
Image Processing and Earth Remote Sensing
The quantization level c j belonging to the interval C. The forward procedure of the quantizer optimization
algorithm
(b j , b j 1 ] is the result of quantization of the input value x if
Let E be a small step in the value of the constraint
x belongs to the interval ( b j , b j 1 ] :
metric (algorithm parameter). We split the range [ 0 .. E m a x ] of
the constraint metric into K sub-ranges of the equal sizes
q x c j : x ( b j , b j 1 ]
E E m ax K .
where q x is the quantization function. Step number 1. Construction of optimal scales of two
quantization intervals.
Requirement 1. Let C ( b j , b j 1 ) there be a function that
We build optimal scales at all intervals
calculates the quantization level c j for the corresponding [ L , r ], r [ L 1, R ] . These scales must satisfy the following
interval ( b j , b j 1 ] conditions:
a) The scale consists of two quantization intervals.
c j C ( b j , b j 1 )
b) Scale constraint metric E ( b ) k E , k [ 0 , K 1] .
Then, to set the quantization scale, it suffices to specify We write the quantization intervals of these scales in the
the vector b of the boundaries of the quantization intervals form:
(and the number N of components of this vector). Therefore,
we use the terms “quantization scale b ” and “quantization b 0 , b1 L , d , b1 , b 2 d , R , L d r
scale b 0 , ..., b N 1 ”.
where d is the only interval boundary that we need to
B. Statement of the problem of quantizer optimization choose for each desired scale.
We denote Q ( b ) the quality measure that we optimize We can write the quality measure of the scale of two
when constructing a quantization scale. We perform this intervals through the quality measure at intervals:
optimization using a constraint metric E ( b ) that should not
exceed the limit value E m a x . q
(1 )
( r , d ) Q L , d Q d , r
We need to calculate the number of quantization
We can write the constraint metric of the scale of two
intervals N and the boundaries b of the intervals to build the
intervals similarly:
scale. Thus, we write the task of the scale optimization in the
form:
e
(1 )
( r , d ) E ( L , d ) E ( d , r )
Q ( b ) m in
N ,b
Then we can put the optimal value of the boundary
(1 )
E ( b ) E d [ L , r ) in the matrix B
:
m ax
Requirement 2. There must be a way to calculate the B r , k a rg m in q (r, d ) k E ,
(1 ) (1 ) (1 )
(r, d ) :e
quality measure of the scale b 0 , ..., b N 1 through the quality Ld r
r [ L 1, R ], k [ 0 , K 1]
measures of the subscale b 0 , ..., b N 2 and the subscale
b N 2 , b N 1 . For simplicity, we further assume that we can Each element B r(1, k) contains the boundary d [ L , r ) of
simply summarize the quality measures of such scales (we the scale of two intervals. This scale is optimal in the range
can use this algorithm also for more sophisticated ways of [ L , r ], r [ L 1, R ] . The constraint metric of this scale
calculating quality measures): E ( b ) k E , k [ 0 , K 1] .
Q b 0 , ..., b N 1 Q b 0 , ..., b N 2 Q b N 2 , b N 1 Besides, we put the corresponding values of the scale
quality measure in the matrix Q (1 ) :
Requirement 3. Let the similar requirement also be true
for the constraint (the ability to calculate the constraint for Q r ,k q ( r , B r , k ), r [ L 1, R ], k [ 0 , K 1]
(1 ) (1 ) (1 )
the scale through the corresponding subscales):
Step number j. Construction of optimal scales of j 1
E b 0 , ..., b N 1 E b 0 , ..., b N 2 E b N 2 , b N 1
intervals.
We can see that the formulated requirements are quite We build optimal scales at all intervals
weak, as they are true in most practical situations. [ L , r ], r [ L 1, R ] . These scales must satisfy the following
conditions:
a) The scale consists of j 1 quantization intervals.
VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 30
Image Processing and Earth Remote Sensing
b) Scale constraint metric E ( b ) k E , k [ 0 , K 1] . b N 2 B R , K 1
(N 2)
We search through the penultimate boundary
d [ L j 1, r ) of each of these scales.
We calculate the boundaries of the remaining intervals of
the optimal scale using the following recursive procedure:
We found all the optimal scales of j quantization
intervals during the previous step of the algorithm. These N 2
b j B v , w , v b j 1 , w E m ax E ( bi , bi 1 ) E
( j)
scales are optimal at intervals [ L , d ] , d [ L j 1, r ) . The
i j 1
constraint metric of these scales is equal
j N 3, N 2 , ...,1
E ( b ) k E E ( d , r ) . Then we can consider scales that
satisfy the following conditions:
This completes the construction of the scale. The
a) The scale is in the interval [ L , r ], r [ L 1, R ] . constructed scale is quasi-optimal (asymptotically optimal
for E tending to zero). The constraint metric of the
b) The scale consists of j 1 quantization intervals.
constructed scale is in the range E m a x N E , E m a x since the
c) The scale contains the optimal subscale of j intervals. deviation of the constraint metric of the constructed scales
from the constraint metric of the optimal scale increases no
d) Scale constraint metric E ( b ) k E , k [ 0 , K 1] . more than E at each step of the algorithm.
We can write the quality measure of all these scales in the
following form: IV. EXPERIMENTAL STUDY
OF THE QUANTIZER OPTIMIZATION ALGORITHM
We performed computational experiments to study the
k E E (d , r )
q d ,r , t
effectiveness of the proposed quantizer optimization
( j 1)
( r , k , d ) Q d ,t
( j)
q
E
algorithm. We investigated the problem of constructing
quantization scales that are optimal for the compression
Optimization of this function by d allows us to calculate problem with a controlled error [7-12]. These scales allow us
the penultimate boundary of the desired optimal scale. We to minimize the compressed size data with a fixed error.
put this boundary in the matrix B ( j ) : We used the quality measure equal to the entropy H ( b )
[7] of the quantized values since this entropy approximates
B r , k a rg m in q ( r , k , d ), r [ L 1, R ], k [ 0 , K 1] well the compressed data size. We also used the scale
( j) ( j)
Ld r
constraint metric equal to the variance M2 S E ( b ) of the
We also put the appropriate quality measure in the matrix quantization error [12]. Therefore, we solved the
( j) optimization problem (6) in the form:
Q :
N 2
Q r ,k q
( j) ( j)
( r , B r , k ), r [ L 1, R ], k [ 0 , K 1]
( j)
Q ( b ) H ( b ) P ( b j , b j 1 ) lo g 2 P ( b j , b j 1 ) mN in
,b
j0
N 2 b j 1
The forward procedure of the quantizer optimization E (b ) 2 (b )
2
f ( x ) x C b j , b j 1 m ax
2
algorithm stops at step number R L 1 . Then the reverse M SE
j0 xbj
procedure of the quantizer optimization algorithm starts.
D. The reverse procedure of the quantizer optimization Here f ( x ) is the probability density of the input value x
algorithm equal to the interpolation error of the compressible signal
samples.
The one-dimensional array Q j Q R( ,j K) 1 , 0 j R L
We describe the probability P ( l , r ) of falling x into the
contains the quality measure of the scales of j 1
quantization intervals. These scales are optimal in the range interval l , r and the function C ( l , r ) of calculating the
L , R with the constraint metric E ( b ) K 1 E . quantization level from the quantization interval ( l , r ) as
follows:
The minimum by j in the array Q j corresponds to the
r r r
step number at which we built the desired optimal scale. The f ( x ) C (l , r ) f (x)
number of quantization levels of this scale is two more than
P (l , r ) x f (x)
x l 1 x l 1 x l 1
this step number:
Here, the quantization level C ( l , r ) is equal to the local
N 2 a rg m in Q j 2 a rg m in Q R , K 1
( j)
average over the quantization interval ( l , r ) .
0 j R L 0 j R L
We used the distribution density
We know the first b 0 L and last b N 1 R boundaries
f ( x ) e x p x / 2 . This type of distribution density
of the quantization intervals of this optimal scale. We get the
penultimate boundary b N 2 of this scale from the matrix B : is natural for the interpolation error of differential [11],
VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 31
Image Processing and Earth Remote Sensing
hierarchical [9], and many other [7, 12] compression We formulated requirements for the optimization
methods. criterion and the constraint, ensuring the operability of the
optimization algorithm of the quantization scale. We
We used uniform quantization scales and non-uniform performed computational experiments to construct quasi-
Lloyd-Max scales [7] as a basis for comparison. We built the optimal scales. The obtained experimental results confirmed
Lloyd-Max scales based on minimizing the root mean square the advantage of the constructed quantization scales over the
(RMS) error 2 ( b ) while limiting the number of known ones.
quantization levels N N m a x :
ACKNOWLEDGMENT
The reported study was funded by RFBR according to the
2 N 2b j 1
2
(b ) f ( x ) x C b j , b j 1
research projects 18-01-00667 (sections II, III.B, III.C, III.D,
m in
j0 xbj
b
IV, V), 18-07-01312 (section III.A), and the RF Ministry of
Science and Higher Education within the state project of
N N m ax FSRC “Crystallography and Photonics” RAS under
agreement 007-GZ/Ch3363/26 (section I).
We show a graph of the dependence of the entropy of
quantized interpolation errors on the RMS interpolation error REFERENCES
in Fig. 1. You can see that the proposed algorithm allows you [1] A. Oppenheim and R. Schafer, “Digital Signal Processing,” Litres,
to build scales that have an advantage in the “error-entropy” 2018, 1048 p.
coordinates over uniform scales and Lloyd-Max scales. [2] A. Kudinov, S. Mikheev, V. Tsvetkov and I. Tsvetkov, “Quantization
of the phase space of an instantaneous heart rate,” International
The proposed quantizer provides a smaller compressed conference “Mathematical biology and bioinformatics”, vol. 7, e15,
data size with the same error. Accordingly, this quantizer 2019.
provides a smaller error with the same compressed data size. [3] D. Kolesnikov and D. Kuznetsov, “Optimal uniform quantization of
This advantage increases with the increase in the parameters of convolutional neural networks,” Questions of radio
quantization error. electronics, vol. 8, pp . 99-103, 2018.
[4] O. Evsyutin, A. Kokurina and R. Meshcheryakov, “Steganographic
embedding of additional data in Earth remote sensing images using
O p tim a l s c a le s the QIM method with a variable quantization step in the frequency
3 ,6 U n ifo rm s c a le s
domain,” Bulletin of the Tomsk polytechnic university of engineering
georesources, vol. 330, no. 8, pp. 155-162, 2019.
L lo y d -M a x s c a le s
[5] A. Egorova and V. Fedoseev, “A classification of semi-fragile
2 ,9 5 watermarking systems for JPEG images,” Computer Optics, vol. 43,
no. 3, pp. 419-433, 2019. DOI: 10.18287/2412-6179-2019-43-3-419-
433.
2 ,3
[6] A. G. Sergeev, “Quantization of the Sobolev space of half-
differentiable functions II,” Russian Journal of Mathematical Physics,
1 ,6 5 vol. 26, no. 3, pp. 401-405, 2019.
0 2 4 6 8 M SE [7] W. Pearlman and A. Said, “Digital signal compression: principles and
practice,” Cambridge university press, 2011, 419 p.
[8] V. Soifer, “Computer image processing, Part II: Methods and
algorithms,” Saarbrücken: VDM Verlag, 2010, 584 p.
1 ,5
[9] V. Sergeyev, N. Glumov and M. Gashnikov, “Compression method
for real-time systems of remote sensing,” 15th international
1 ,3 5 conference on pattern recognition, vol. 3, pp. 232-235, 2000.
[10] M. Gashnikov, “Optimal quantization in the task of digital signal
compression,” Computer Optics, vol. 21, pp. 179-184, 2001.
1 ,2
[11] A. Maksimov and M. Gashnikov, “Adaptive interpolation of
multidimensional signals for differential compression,” Computer
1 ,0 5 Optics, vol. 42, no. 4, pp. 679-687, 2018. DOI: 10.18287/2412-6179-
2018-42-4-679-68.
10 12 14 16 18 M SE
[12] K. Sayood, “Introduction to data compression,” The Morgan
Fig. 1. The study of the algorithm for constructing optimal quantization Kaufmann series in multimedia information and systems, 2012, 743 p.
scales.
V. CONCLUSION
We considered the problem of constructing quantization
scales that are optimal by a given criterion and satisfy the
chosen constraint. We considered the precise formulation of
such an optimization problem. We proposed an algorithm for
constructing quasi-optimal quantization scales approximating
optimal scales with a given precision, subject to the
constraint.
VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 32