Algorithm for optimizing quantization scales by an arbitrary quality measure

Abstract

-This work deals with the task of constructing quantization scales optimal by an arbitrary criterion. Besides, these scales also satisfy the selected constraint. We consider a formal description of this optimization problem. We propose an algorithm for constructing quasi-optimal quantization scales that approximate optimal scales with the required precision, subject to the constraint. We formulate requirements for the optimization criterion and the restriction, ensuring the performance of the algorithm. We investigate the proposed quasi-optimal scales using computational experiments. The experimental results confirm the advantage of the constructed scales over the known ones.

Keywords

• quantization scale
• non-uniform quantization error
• quantizer optimization
• standard error

I. INTRODUCTION

Quantization [ 1 ] is the process of mapping input values from a large set to output values in a smaller set. In other words, quantization is rounding to a predetermined set of values.

You can use quantization to solve various problems: processing the phase space of the heart rhythm [ 2 ], normalizing the parameters of neural networks [ 3 ], embedding digital watermarks [ 4-5 ], processing spaces of semi-differentiable functions [ 6 ], and quantization of interpolation errors during compression [ 7-9 ], etc.

In this paper, we generalize the quantizer [ 10 ], proposed as part of the solution to the compression problem, for the case of an arbitrary quality measure and arbitrary restriction, which we use when optimizing the quantization scale. Besides, we also formulate requirements for this quality measure and this restriction. The fulfillment of these requirements allows us to ensure the performance of the optimization algorithm of the quantization scale.

II. THE MOST COMMON QUANTIZATION SCALES

We describe the most common quantization scales. We divide the set of input values into quantization intervals. We specify the quantization level within each quantization interval. We call the quantization scale the set of the quantization levels and the quantization intervals.

Quantization means that we replace all input values belonging to the quantization interval with the corresponding quantization levels. Therefore, the quantization scale ultimately determines the quantization result. Most often, we use a uniform scale in which the intervals are the same size, and the levels are at the centers of the intervals.

However, the use of uniform scales in many situations leads to an unacceptably significant error, in particular with a small number of levels. In these cases, we use non-uniform  scales. Lloyd-Max scales [7] are the most famous of the nonuniform quantization scales. We build these scales based on minimizing the root mean square error. The constraint is a given (fixed) number of quantization levels.

Despite the optimality of the error, the Lloyd-Max scales are not the best when solving many applied problems, since we often need to optimize not some error, but some other quality measure. Besides, the levels number of the quantization scale may not be known, which entails the need to use a different constraint when optimizing the scale, other than the constraint on the number of levels.

For example, we need to minimize the compressed data size with a fixed error in the compression problem [ 7-10 ]. We have to replace both the quality measure and the constraint to optimize the quantization scale for compression.

In this paper, we propose an algorithm for constructing a quantizer that is optimal by the required criterion. Besides, we take into account the required constraint when constructing this quantizer. We also describe the requirements for this criterion and the requirements for this constraint necessary for the operability of the proposed algorithm.

III. QUANTIZER OPTIMIZATION

A. Non-uniform scale quantizer

We describe a quantizer with a non-uniform [ 1, 8 ] scale. Let the input value x   L , R  be an integer (for simplicity). We consider the range  L , R  as the union of quantization intervals ( b j , b j 1 ] :

N  2 j  0  L , R   (b j , b j 1 ], b j  Z , b0  L  1, b N 1  R   where

N is the number of boundaries b j of the quantization intervals ( b j , b j 1 ] . We denote b the vector of the boundaries of the quantization intervals: b   b j   : b j  b j 1 , b0  L  1, b N 1  R , j   0 , N   

We specify the quantization levels c j  ( b j , b j 1 ] within the intervals ( b j , b j 1 ] . quantization levels:

We denote с the vector of

The quantization level c j belonging to the interval ( b j , b j 1 ] is the result of quantization of the input value x if x belongs to the interval ( b j , b j 1 ] :

 q  x   c j : x  (b j , b j 1 ]  where  q  x  is the quantization function.

Requirement 1. Let C ( b j , b j 1 ) there be a function that calculates the quantization level c j for the corresponding interval ( b j , b j 1 ]

c j  C ( b j , b j 1 ) 

Then, to set the quantization scale, it suffices to specify the vector b of the boundaries of the quantization intervals (and the number N of components of this vector). Therefore, we use the terms “quantization scale b ” and “quantization scale  b0 , ..., b N 1  ”.

B. Statement of the problem of quantizer optimization

We denote Q (b ) the quality measure that we optimize when constructing a quantization scale. We perform this optimization using a constraint metric E (b ) that should not exceed the limit value E m ax .

We need to calculate the number of quantization intervals N and the boundaries b of the intervals to build the scale. Thus, we write the task of the scale optimization in the form:          intervals. conditions:  E  E m ax K .

C. The forward procedure of the quantizer optimization algorithm

Let  E be a small step in the value of the constraint metric (algorithm parameter). We split the range [ 0 ..E m ax ] of the constraint metric into K sub-ranges of the equal sizes 

Step number 1. Construction of optimal scales of two quantization intervals.

We build optimal scales at all intervals [ L , r ], r  [ L  1, R ] . These scales must satisfy the following conditions:  a) The scale consists of two quantization intervals.

We write the quantization intervals of these scales in the form:

We can write the constraint metric of the scale of two intervals similarly:  b0 , b1    L , d  ,  b1 , b2    d , R  , L  d  r   where d is the only interval boundary that we need to choose for each desired scale.

We can write the quality measure of the scale of two intervals through the quality measure at intervals: q (1) ( r , d )  Q  L , d   Q  d , r    e (1) ( r , d )  E ( L , d )  E ( d , r )    Q (b )  m in  N ,b   E (b )  E m ax  d  [ L , r ) in the matrix B (1) :

Then we can put the optimal value of the boundary Requirement 2. There must be a way to calculate the quality measure of the scale  b0 , ..., b N 1  through the quality measures of the subscale  b0 , ..., b N  2  and the subscale  b N  2 , b N 1  . For simplicity, we further assume that we can simply summarize the quality measures of such scales (we can use this algorithm also for more sophisticated ways of calculating quality measures):

Q  b0 , ..., b N 1   Q  b0 , ..., b N  2   Q  b N  2 , b N 1   

Requirement 3. Let the similar requirement also be true for the constraint (the ability to calculate the constraint for the scale through the corresponding subscales): B r(1,k)  a rg m in  q (1) ( r , d ) : e (1) ( r , d )  k  E  ,

L  d  r r  [ L  1, R ], k  [ 0 , K  1]  

Each element B r(1,k) contains the boundary d  [ L , r ) of the scale of two intervals. This scale is optimal in the range [ L , r ], r  [ L  1, R ] . The constraint metric of this scale E (b )  k  E , k  [ 0 , K  1] .

Besides, we put the corresponding values of the scale quality measure in the matrix Q (1) :

Q r(1,k)  q (1) ( r , B r(1,k) ), r  [ L  1, R ], k  [ 0 , K  1]  Step number j. Construction of optimal scales of  j  1  E  b0 , ..., b N 1   E  b0 , ..., b N  2   E  b N  2 , b N 1   

We can see that the formulated requirements are quite weak, as they are true in most practical situations.

We build optimal scales at all intervals [ L , r ], r  [ L  1, R ] . These scales must satisfy the following a) The scale consists of  j  1  quantization intervals.

We found all the optimal scales of j quantization intervals during the previous step of the algorithm. These scales are optimal at intervals [ L , d ] , d  [ L  j  1, r ) . The constraint metric of these scales is equal E (b )  k  E  E ( d , r ) . Then we can consider scales that satisfy the following conditions: a) The scale is in the interval [ L , r ], r  [ L  1, R ] . b) The scale consists of  j  1  quantization intervals. c) The scale contains the optimal subscale of j intervals. d) Scale constraint metric E (b )  k  E , k  [ 0 , K  1] .

We can write the quality measure of all these scales in the following form:

We calculate the boundaries of the remaining intervals of the optimal scale using the following recursive procedure:   N  2   b j  B v(,jw) , v  b j 1 , w    E m ax   E (bi , bi 1 )   E     i  j 1   j  N  3, N  2 , ...,1

This completes the construction of the scale. The constructed scale is quasi-optimal (asymptotically optimal for  E tending to zero). The constraint metric of the constructed scale is in the range  E m ax  N  E , E m ax  since the deviation of the constraint metric of the constructed scales from the constraint metric of the optimal scale increases no more than  E at each step of the algorithm.

IV. EXPERIMENTAL STUDY

OF THE QUANTIZER OPTIMIZATION ALGORITHM   Q r(,jk)  q ( j ) ( r , B r(,jk) ), r  [ L  1, R ], k  [ 0 , K  1]    

The forward procedure of the quantizer optimization algorithm stops at step number R  L  1 . Then the reverse procedure of the quantizer optimization algorithm starts. D. The reverse procedure of the quantizer optimization algorithm

The one-dimensional array Q  j   Q R( ,j K) 1 , 0  j  R  L contains the quality measure of the scales of  j  1  quantization intervals. These scales are optimal in the range  L , R  with the constraint metric E (b )   K  1   E .

The minimum by j in the array Q  j  corresponds to the step number at which we built the desired optimal scale. The number of quantization levels of this scale is two more than this step number:

N  2  a rg m in Q  j   2  a rg m in 0  j  R  L 0  j  R  L

Q R( ,j K) 1 

We know the first b0  L and last b N 1  R boundaries of the quantization intervals of this optimal scale. We get the penultimate boundary b N  2 of this scale from the matrix B :   k  E  E ( d , r )   q ( j ) ( r , k , d )  Q d( ,jt1)  q  d , r  , t       E 

Optimization of this function by d allows us to calculate the penultimate boundary of the desired optimal scale. We put this boundary in the matrix B ( j ) : B r(,jk)  a rg m in q ( j ) ( r , k , d ), r  [ L  1, R ], k  [ 0 , K  1] 

L  d  r

We also put the appropriate quality measure in the matrix Q ( j ) :

We performed computational experiments to study the  effectiveness of the proposed quantizer optimization algorithm. We investigated the problem of constructing quantization scales that are optimal for the compression problem with a controlled error [ 7-12 ]. These scales allow us to minimize the compressed size data with a fixed error.

We used the quality measure equal to the entropy H (b ) [7] of the quantized values since this entropy approximates  well the compressed data size. We also used the scale constraint metric equal to the variance  M2 SE ( b ) of the quantization error [ 12 ]. Therefore, we solved the optimization problem (6) in the form:  N  2  Q ( b )  H ( b )    P ( b j , b j 1 ) lo g 2 P ( b j , b j 1 )  m in  j  0 N ,b  E ( b )   M2 SE ( b )  Nj02 xbjb1j f ( x )  x  C  b j , b j 1   2   m2 ax  

Here f ( x ) is the probability density of the input value x equal to the interpolation error of the compressible signal samples.

We describe the probability P (l , r ) of falling x into the interval  l , r  and the function C (l , r ) of calculating the quantization level from the quantization interval (l , r ) as follows:

r P ( l , r )   x  l 1

r f ( x )  C (l , r )   x f ( x ) x  l 1 r  x  l 1 f ( x )  

Here, the quantization level C (l , r ) is equal to the local  average over the quantization interval (l , r ) .

We used the distribution density f ( x )  e x p   x  /  2  . This type of distribution density is natural for the interpolation error of differential [ 11 ],  3 ,6 2 ,9 5 2 ,3 1 ,6 5  1 , 5 1 , 3 5 1 , 2 1 , 0 5

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. hierarchical [ 9 ], and methods.

many other [ 7, 12 ] compression

We used uniform quantization scales and non-uniform Lloyd-Max scales [7] as a basis for comparison. We built the Lloyd-Max scales based on minimizing the root mean square (RMS)

error  2 ( b ) quantization levels N  N m ax : while limiting the number

We show a graph of the dependence of the entropy of quantized interpolation errors on the RMS interpolation error in Fig. 1. You can see that the proposed algorithm allows you to build scales that have an advantage in the “error-entropy” coordinates over uniform scales and Lloyd-Max scales.

The proposed quantizer provides a smaller compressed data size with the same error. Accordingly, this quantizer provides a smaller error with the same compressed data size. This advantage increases with the increase in the quantization error.

O p tim a l s c a le s U n ifo rm s c a le s

L lo y d -M a x s c a le s 0 2 4 6

We formulated requirements for the optimization criterion and the constraint, ensuring the operability of the optimization algorithm of the quantization scale. We performed computational experiments to construct quasioptimal scales. The obtained experimental results confirmed the advantage of the constructed quantization scales over the known ones.

ACKNOWLEDGMENT

The reported study was funded by RFBR according to the research projects 18-01-00667 (sections II, III.B, III.C, III.D,  IV, V), 18-07-01312 (section III.A), and the RF Ministry of Science and Higher Education within the state project of FSRC “Crystallography and Photonics” RAS under agreement 007-GZ/Ch3363/26 (section I).

References

[1] A. Oppenheim and R. Schafer , “Digital Signal Processing,” Litres, 2018 , 1048 p.

[2] A. Kudinov , S. Mikheev , V. Tsvetkov and I. Tsvetkov , “ Quantization of the phase space of an instantaneous heart rate , ” International conference “Mathematical biology and bioinformatics” , vol. 7 , e15 , 2019 .

[3] D. Kolesnikov and D. Kuznetsov , “ Optimal uniform quantization of parameters of convolutional neural networks,” Questions of radio 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 the QIM method with a variable quantization step in the frequency domain,” Bulletin of the Tomsk polytechnic university of engineering georesources , vol. 330 , no. 8 , pp. 155 - 162 , 2019 .

[5] A. Egorova and V. Fedoseev , “ A classification of semi-fragile 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.

[6] A. G. Sergeev , “ Quantization of the Sobolev space of halfdifferentiable functions II,” Russian Journal of Mathematical Physics , vol. 26 , no. 3 , pp. 401 - 405 , 2019 .

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.

[9] V. Sergeyev , N. Glumov and M. Gashnikov , “ Compression method for real-time systems of remote sensing,” 15th international 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 .

[11] A. Maksimov and M. Gashnikov , “ Adaptive interpolation of multidimensional signals for differential compression ,” Computer Optics , vol. 42 , no. 4 , pp. 679 - 687 , 2018 . DOI: 10 .18287/ 2412 -6179- 2018-42-4- 679 -68.

[12] K. Sayood , “Introduction to data compression,” The Morgan Kaufmann series in multimedia information and systems , 2012 , 743 p.