Adaptation of parameterized interpolation algorithms of multidimensional signals for hierarchical and interpolation compression methods

Abstract

-We adapt parameterized multidimensional signal interpolators for hierarchical compression methods and interpolation compression methods based on the coding of quantized post-interpolation residues. The considered interpolators automatically select the most appropriate interpolating function at each point of the signal using a parameterized decision rule. We propose a set of interpolation functions for these compression methods. We select the optimization criterion for the proposed interpolator. The optimization criterion is based on minimization the entropy of the quantized post-interpolation residues. We solve the optimization problem of the adaptive parameterized interpolator according to this criterion. We perform computational experiments to study the proposed interpolators in natural multidimensional signals. The experimental results confirm that the use of the adaptive interpolators can significantly increase the effectiveness of the mentioned methods of multidimensional signals compression.

Keywords

• multidimensional signal
• heterogeneous signals
• adaptive interpolation
• decision rule
• interpolation error

-

I. INTRODUCTION

A large number of signal compression algorithms are known [ 1-10 ]: methods based on wavelet transform [ 2 ] (including JPEG-2000 [ 3 ]), fractal methods [4], DOP methods (including JPEG [ 5 ] based on DCT [ 6 ]), etc. This work deals with interpolation methods [ 7-8 ] and hierarchical methods [910] of multidimensional signals compression.

Interpolation compression methods [ 7-8 ], as their name implies, are based on the interpolation of signal samples from other (reference) samples of the same signal and the subsequent efficient coding [ 11-12 ] of post-interpolation residues.

Hierarchical compression methods [ 9-10 ] are based on a hierarchical (pyramidal) signal representation, which allows us to interpolate more down-sampled levels of the signal samples “pyramid” from less down-sampled levels. Then we encode for the errors of this interpolation.

The most important step in the last two compression methods is the interpolation algorithm. One of the most promising interpolators is the adaptive algorithm [ 13-14 ], which selects an interpolating function at each signal point using a parameterized decision rule. In this paper, we perform the adaptation of such algorithm for hierarchical methods and interpolation methods of multidimensional signals compression. II. ADAPTATION OF THE PARAMETRIZED ALGORITHM

FOR INTERPOLATION COMPRESSION METHODS A. Adaptive interpolator of multidimensional signal

We interpolate a multidimensional signal sample x ( n ) based on reference samples  x k  n  .

We select an interpolating function U i    x k  n   for each sample with coordinates n . We select the function U i  for each sample using the parameterized rule P, depending on the vector parameter t : u  n   U i    x k  n   , i  P  f  n  , t  ,   where u  n  is the interpolating value, t is the vector of parameters, f  n  is the vector of local features. We calculate these local features based on the same reference samples  x k  n  .

B. Interpolation compression methods

Interpolation compression methods work as follows. We select a reference samples set  x k  n  from the set  x ( n ) of all signal samples. We interpolate the remaining (intermediate) samples of the signal based on the reference samples:

Then we calculate the difference signal (post-interpolation residuals):

Then we quantize a quantization function Q : the difference signal using u  n   U   x k  n      n   x  n   u  n    

Then we encode the post-interpolation residues q  n  with some statistical encoding algorithm and put the encoded signal into the communication channel or archive file.

To adapt the parameterized interpolator to interpolation methods of signal compression, it is necessary to specify the following elements of this interpolator:

1) optimization criterion;

2) local features and decision rule;

3) optimization procedure for the parametrized interpolator;

4) interpolating functions.

C. Adaptive interpolator optimization criterion for compression

The criteria [ 11-12 ] based on the interpolation error minimization are usually used to optimize the interpolators. However, this work deals with a criterion more suitable for the compression problem. This criterion is based on minimization of the compressed data size. We use the unnormalized entropy of the quantized post-interpolation residuals as an estimate of this compressed data size:  where N q  t  is the number of quantized postinterpolation residues equal to q for a fixed parameter t of the adaptive interpolator.

D. Decision rule and local features

Averaging (smoothing) interpolator [ 7-8 ] is the simplest for interpolation compression: u  n   1 N

 x k  n   N k 1  where N is the number of reference samples.

This interpolator is quite precise inside smoothly changing areas of the signal, since averaging filters noise a little. However, the error of the averaging interpolator almost always increases substantially at the boundaries of these smooth regions. However, the error of the averaging interpolator usually increases substantially at the boundaries of these smooth areas.

To interpolate these boundaries, nonlinear algorithms implementing interpolation “along” the boundaries are more efficient. For example, the Graham interpolator [ 12 ] works exactly in this way in the two-dimensional case. There are also modifications of this interpolator to the case of more than two directions [ 8 ]. However, nonlinear interpolators lose accuracy within smoothly varying areas of the signal.

We suggest using the adaptive interpolator described above for interpolation compression methods. This algorithm combines the advantages of averaging and non-linear approaches to interpolation. The adaptive interpolator can u  n   U  2   n   x j  n  , if  i  ti , i   0 , N c    Therefore, we describe decision rule (1) by expressions (8-9). We need to solve the optimization problem (5) in the parametric space of ti of dimension N c to calculate the parameters ti of this decision rule.

The compression task often imposes restrictions on computing resources, and the complexity of the interpolator optimization in the N c -dimensional parametric space of the decision rule can become a source of problems even in the case of a three-dimensional or even two-dimensional signal.

We propose using a reduced-dimensional parametric space for the interpolator optimization as part of interpolation compression methods. In this case, the decision rule instead of differences  i uses relies on their ratio. We describe these relations by a variational series [ 8 ]   0   n    1  n     2   n   ..    N c 1  n  , in which  i  are renumbered differences  i .

If there are no boundaries of smooth regions in the neighborhood of the current signal point, then all difference  i s have similar values. If the boundary is present, then the difference corresponding to the direction of this boundary is minimal. Besides, this difference is at the initial (zero) position   0  of the variational series. automatically select the “averaging” or “nonlinear” interpolating function depending on the direction and the severity of the boundary of smoothly changing regions in the neighborhood of each processed sample.

Denote by Nc the number of possible directions of the regions boundaries. Let  i  n  : 0  i  N c  be the set of differences  i  n   x  n   x  n  between the reference samples x  n  , x  n  in the considered directions. This set of differences  i  n  describes the severity (and the fact of presence) of the boundary of the regions in the neighborhood of the current reference with coordinates n .

We detect the boundary and calculate its direction by means of a decision rule depending on the vector parameter t . This parameter consists of several threshold values ti. The decision rule compares the differences  i  n  with these thresholds. If there is no border at a current signal point, then the decision rule selects the “averaging” interpolating formula of the form (6): u  n   U 1  n   1 N

 x k  n , if  i  ti , i   0 , N c  

N k 1  

If there is a boundary at the current point, then the decision rule selects the average value x  n  of the nearest reference samples located “along” the boundary: q  n   Q    n    

The remaining differences have similar meanings. The difference   0  in this case differs significantly from the other differences  1 ..  N c 1 . Therefore, we can calculate the feature f  n  of the severity and direction of the boundary at the current signal point by means of the rank filter: f  n    1  n     0   n   

We use this characteristic as the feature of the decision rule (1) to select the interpolating function at each signal point.

If the feature f  n  is less than the threshold t, then there is no boundary at this signal point, i.e. you can use the "averaging" formula (8). Otherwise, we apply interpolation (9) “along” the boundary corresponding to the minimum difference  i :

N U 1  n    x k  n , f  n   t  u  n    k 1 U  2   n   x j  n  , j  a r g m in  i  n  , f  n   t  i

Thus, the described adaptive interpolator depends on the single scalar parameter t, and the problem of its optimization becomes one-dimensional.

E. Optimization of adaptive interpolator

We first fill out the three-dimensional auxiliary array N (fi ),q  of number of quantized post-interpolation residues (4) to optimize entropy (5): N (fi ),q    n : f  n   f , q i  n   q  , i  1, 2 , 0  f   Q ,  Q  q   Q , Q  m a x  q  n   n  

Each element N (fi ),q  contains the number of quantized post-interpolation residues q i  n  (12), equal q  , with the value of feature (11), equal f  .

We use the array N (fi ,)q in the recursive procedure for calculating the number N q  t  of quantized post-interpolation residues (4) equal to q for all threshold values t:

M 1 N q  0    f  0

N (f1,)q ; N q  t  1   N q  t   N t(1,q)  N t(,2q)   where  q i  n   Q  x  n   U  i   n      x  2  n 0  1   i ,0  , ..., 2  n D 1  1   i , D 1    , i   0 , 2 D 1 

Then we can write the adaptive interpolator (12), which selects one of the described interpolating functions at each point of the signal: F. Interpolation functions of the adaptive interpolator during compression

We write the interpolating functions for the interpolation method of compression D-dimensional signal x  n   x  n 0 , ..., n D 1  . Let the samples x  2 n  with even numbers be the reference. First, we specify the differences  i  2 n  1  , i   0 , D  between the reference samples:  i  2 n  1   x  2  n 0   i ,0  , ..., 2  n D 1   i , D 1    x  2  n 0  1   i ,0  , ..., 2  n D 1  1   i , D 1   , i   0 , 2 D 1      

U 1  2 n  1  

1 2 D 1 1 2 D 1 d 0

1 2 D 1 1 2 D 1 d 0 1 2 

Here, the matrix  i , d defines all possible offsets of the reference samples relative to the interpolated sample, satisfying the condition   i , d  2 D 1 .

d

Next, we write the first interpolating function, averaging the neighborhood reference samples: x  2  n 0   i ,0  , ..., 2  n D 1   i , D 1     x  2  n 0  1   i ,0  , ..., 2  n D 1  1   i , D 1  

Then we write the averaging in the directions: u i 2   2 n  1    x  2  n 0   i ,0  , ..., 2  n D 1   i , D 1   

The number of quantized post-interpolation residues N q  t  allows us to calculate the entropy H  t  of quantized post-interpolation residues for all thresholds t U 1  n  , f  n   t  u  n    u j2   n  , j  a r g m in  i  , f  n   t i   III. ADAPTATION OF THE PARAMETERIZED INTERPOLATOR

FOR HIERARCHICAL COMPRESSION METHODS

Hierarchical compression methods use a redundant pyramidal representation of a multidimensional signal X   x  n  in the form of a set of L scale levels X l :   

L 1 l  0 X 

X l , X l   X l  n    X  n  : n  I l  , I L 1   2 L 1 n  , I l   2 l n  \  2 l 1 n  , 0  l  L  

Here, each set Il contains the coordinates of the samples of the corresponding scale level X l .

We compress the scale levels X l one by one, in order X L 1 , X L  2 , ..., X 1 , X 0 . We interpolate samples of each scale level X l , based on samples of less down-sampled scale levels X l  m . Then we quantize and encode the interpolation errors.

We use samples of all scale levels X l  m to interpolate samples of each scale level X l , since scale levels X l  m together compose the regular D-dimensional grid of signal samples with the step 2 l 1 :  x l 1  n    x  2 l 1 n  

X l 1 

 L 1

Therefore, the hierarchical compression of each scale level is reduced to the interpolation compression of the signal by the signal described in the previous section. Thus, we optimize the decision rule twice for each scale level with hierarchical compression.

Thus, we reduce the hierarchical compression of each scale level X l to the interpolation compression of the signal x  l   n  by the signal x  l 1  n   x  l   2 n  described in the previous section. Therefore, we optimize the decision rule twice for each scale level during hierarchical compression. IV. EXPERIMENTAL STUDY OF THE ADAPTIVE INTERPOLATOR

DURING COMPRESSION

We performed experimental studies of the adaptive interpolator as part of the hierarchical method and interpolation method of multidimensional signals compression.

We used a uniform scale with step  2  1  to quantize (4) the post-interpolation residues   n  in both of these compression methods. We describe the quantizer Q and the dequantizer Q  1 when using this scale as follows:      n   Q    n    in t   s ig n    n    2  1   

Q  1    n    q  n   2  1    m a x x  n   y  n 

n decompressed y  n  signals. 6 3 0 3 2 1 0 4 3 2 1 0 6 3 0

We used natural test video signals from the dataset “Dynamic scenes data set” [15] (see the example in Fig. 1). We calculated the relative gain D K  1  K K   1 0 0 % in the compression coefficient, achieved by replacing the averaging interpolator (6) with the adaptive interpolator (here K , K are the compression coefficients with averaging or adaptive interpolator, respectively).

We show the dependence of the gain D K on the maximum error  for several test signals in Fig. 2-3. The graphs confirm that the adaptive interpolator can significantly (up to 17%) increase the efficiency of hierarchical methods and interpolation methods of multidimensional signals compression.

V. CONCLUSION

We have adapted parameterized algorithms for interpolating multidimensional signals for hierarchical compression methods and interpolation compression methods based on the coding of quantized post-interpolation residues.

We proposed interpolation functions based on interpolation along the most preferred directions. We have chosen the criterion for decision rule optimization based on minimizing the entropy of the quantized post-interpolation residues. We have solved the problem of optimizing the decision rule by this criterion.

We performed computational experiments in natural multidimensional signals. These experiments confirmed the significant increase in the effectiveness of the considered compression methods using parameterized interpolators.

ACKNOWLEDGMENT

The reported study was funded by RFBR according to the research projects 18-01-00667 (in parts II.A, II.C, II.D, II.E, II.F, III, IV, V), 18-07-01312 (in part II.B), 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 (in part I).

References

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

[2] V. Gupta , V. Sharma and A. Kumar , “ Enhanced image compression using wavelets,” International journal of research in engineering and science (IJRES) , vol. 2 , no. 5 , pp. 55 - 62 , 2014 .

[3] J. Li , “ Image compression: the mathematics of JPEG- 2000 ,” Modern signal processing , vol. 46 , pp. 185 - 221 , 2003 .

W. Woon , A. Ho , T. Yu , S. Tam , S. Tan and L. Yap , “ Achieving high data compression of self-similar satellite images using fractal,” IEEE international geoscience and remote sensing symposium (IGARSS), pp. 609 - 611 , 2000 .

[5] G. Wallace , “ The JPEG still picture compression standard,” Communications of the ACM , vol. 34 , no. 4 , pp. 30 - 44 , 1991 .

[6] G. Plonka and M. Tasche , “ Fast and numerically stable algorithms for discrete cosine transforms,” Linear algebra and its applications , vol. 394 , no. 1 , pp. 309 - 345 , 2005 .

[7] D. Vatolin , A. Ratushnyak , M. Smirnov and V. Yukin , “ Data compression methods. The device of archivers, image and video compression ,” M: Dialog-Mephi , 2002 , 384 p.

[8] V. Soifer , “Methods of computer image processing,” M: Fizmatlit, 2003 , 784 p.

[9] V. Sergeev , N. Glumov and M. Gashnikov , “ Information technology for image compression in online remote sensing systems,” Bulletin of the Samara scientific center of the Russian Academy of Sciences , vol. 1 , pp. 99 - 107 , 1999 .

[10] М . Gashnikov, “ Interpolation based on context modeling for hierarchical compression of multidimensional signals,” Computer Optics , vol. 42 , no. 3 , pp. 468 - 475 , 2018 . DOI: 10 .18287/ 2412 -6179- 2018-42-3- 468 -475.

[11] J. Woods , “ Multidimensional signal, image, and video processing and coding,” Academic press, 2011 , 616 p.

[12] R. Gonzalez and R. Woods , “Digital image processing,” NJ: Prentice Hall, 2007 , 976 p.

[13] A. Maksimov and M. Gashnikov , “ Adaptive interpolation of multidimensional signals for differential compression ,” Computer

[14] A. Maksimov and M. Gashnikov , “ Parameter space dimension reduction for multidimensional signals differential pulse-code modulation interpolator,” 7th International symposium on digital forensics and security (ISDFS) , vol. 8757494 , 2019 .