Differential method of multidimensional signals
compression based on the adapted parameterized
interpolation algorithm
Aleksey Maksimov Mikhail Gashnikov
Samara National Research University Samara National Research University;
Samara, Russia Image Processing Systems Institute of RAS - Branch of the FSRC
aleksei.maksimov.ssau@gmail.com "Crystallography and Photonics" RAS
Samara, Russia
mih-fastt@yandex.ru
Abstract—In this paper, parameterized algorithms of sample f ( x ) is interpolated using the function R based on the
multidimensional signal interpolation are adapted for use as part
of differential compression methods. These methods are based on nearest processed (compressed and decompressed)
the efficient coding of quantized differences between the initial samples g ( x ) : , after which the difference
and interpolated signal samples during sequential signal
scanning. The proposed interpolators are based on the signal v x is calculated, which is then quantized by the
classification of signal samples and the use of various
interpolation formulas within the classes. The sample classifier function W to calculate the quantized difference signal w x :
and its training procedure and a set of interpolating functions for
the compression method are described. The results of
experimental research on real multidimensional signals confirm
that the use of an adapted parameterized interpolator leads to an R g ( x ) : ,
r x
increase in the efficiency of the differential compression method.
f x r x,
v x
Keywords—comparative study, compression, low-level
processing, filtering, enhancement, color mapping, remote sensing w x W v x ,
imagery, still images
where r x – is the interpolated signal, – is the array of
I. INTRODUCTION
Algorithms for interpolation of multidimensional signals reference sample displacements during interpolation. For
can be divided into two groups [1]: adaptive algorithms and quantization in this work, we used a quantizer with absolute
non-adaptive ones. The most common examples of non- error eabs control:
adaptive algorithms have relatively low computational
complexity due to the lack of use of local signal features. They W v x s ig n v x
are: rectangular interpolation from the nearest (or neighboring)
eabs
sample, as well as bilinear and bicubic interpolation [2].
2e
in t v x 2 eabs 1 ,
1
Adaptive algorithms, on the contrary, take into account the abs
features of the local neighborhood of each sample, which
usually allows improving accuracy. Examples of such where function int(...) calculates the integer part of a value, and
algorithms include DCCI [3], NEDI [4-5], super-resolution sign(...) calculates its sign.
algorithms based on neural networks [6-7], as well as many Then, restoration (decompression) of the current sample is
other algorithms [8-10]. In this paper, we consider adaptive performed, i.e. calculation of the reference value, which will is
parameterized interpolation algorithms [11] based on the calculated during decompression:
classification of signal samples using local features and the use
of a simple interpolating formula for each sample class.
g x w x r x
The goal of this research is to adapt the parametrized
interpolators for differential compression methods [2, 8] based The described feedback (interpolation not according to the
on interpolation of signal samples during sequential sweep and initial, but according to the decompressed values of the
compression of interpolation errors. samples) is necessary to ensure the identity of the interpolator
at the stages of compression and decompression (the source
II. DIFFERENTIAL COMPRESSION OF MULTIDIMENSIONAL signal is no longer available during decompression). The
SIGNALS
quantized difference signal
w x
is processed by a statistical
During differential compression, [2, 8] samples of a
encoder to reduce the amount of data and is sent to a
multidimensional signal f ( x ) are processed sequentially. Each
communication channel or archive data storage.
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
III. ADAPTATION OF THE PARAMETERIZED ALGORITHM FOR significantly different from others. We will estimate the
DIFFERENTIAL COMPRESSION significance via local feature ( x ) ,which can be calculated by
A. Parameterized interpolation algorithm for differential the following three rank filters:
compression
Before interpolating, we will classify the signal samples
1 ( x ) g 2 x g 1 x ,
based on a local feature ( x ) : g 1 x
2 (x) ,
C ( x ), ,
c x E g x : m 1, M
m
1(x)
3 (x)
where c x – is the number of sample’s class, a sample has
,
E g x g x : m 3 , M
m m 1
coordinates x , ( x ) – is the local feature, C ( x ) , –
where E performs averaging:
classifier, – classifier parameter, which is calculated for
g x : m 1, M M g x
M
1
each signal anew by the training procedure based on the E m m
optimization of some criterion. m 1
Each class with a number c x has its own interpolation
Classifier
C ( x ), is based on a thresholding
function R c , the interpolation procedure can be expressed in
the following way: function
C ( x ), 1 B in ( x ) and depends on
parameter . The function chooses one of the interpolation
r x R g(x ) : functions depending on the presence of artifact inside the
vicinity.
Rc g ( x ) : ,
C. Classifier optimization criterion
c C ( x ), . As the optimization criterion, we have decided to use an
entropy minimum criterion h of the quantized differential
During classifier C x training procedure decompressed
signal w x :
signal g x is used both as a training set and a test set.
w m ax
To adapt a parametrized interpolator to differential h w , w lo g 2 w , w m in ,
compression, the following elements of the interpolation w w m in
algorithm need to be specified: the classifier of samples, the w , w card w x : w x w
optimization criterion of the classifier, the optimization
procedure for the classifier, a set of interpolating functions.
where w , w is the number of values of quantized
differential signal w x which are equal w . Parameter
B. Sample classifier for parameterized interpolation.
We will classify the signal samples based on the severity of
the directed artifacts in the vicinity of the current sample, determines the choice of interpolating functions at each sample
which we will calculate using a set of partial derivative of the signal, thereby influencing the difference signal. The
choice of this criterion was made due to the fact that the
estimates
g m x , m 0 , M along different directions (M – entropy well approximates the size of the compressed data; this
makes the criterion the most suitable for the compression
is the number of directions), which is calculated using the basic problem.
samples g ( x ) : and neighboring processed samples
To solve the optimization task (7), the statistics W , c , w
(these estimates can be easily calculated based on discrete
differences of already processed samples). of quantized differential signal w x values for every
Let us sort the derivatives g m x in the ascending order class c x and every feature value x is obtained:
and rename them, creating the variation series W , c , w
g 1 x g 2 x ... g M x . We assume that there is a x : x ,
directed artifact in the vicinity, if the least derivative g 1 x is card
W f x R c x g ( x ) :
w
VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 21
Image Processing and Earth Remote Sensing
The number of w , w values for the minimum of ,
, ...,
(0) (9 )
equal m in , can be calculated as follows:
1 0 1 1 0
m ax
0 , 1 , 1 , 1 , 0 ,
w m in , w W , 2 , w
m in 0 0 0 0 1
0 1 1 0 0
since in this case the same interpolation function is used for all
samples. 1 , 0 , 1 , 1 , 1 .
1 1 0 1 1
Values w ,w for other values are calculated as
follows: Next, we will use the auxiliary difference of the processed
samples:
w , w w 1, w
x x x
W 1, 2 , w W 1,1, w . m
dm y g y g y
, m 0 , 9
z z z
After the calculation of the number of w , w values,
entropy h is calculated via expression (7) for every
on the basis of which it is possible to write abnormal estimates
parameter . Since there are not many of these values, brute of partial derivatives in directions
forcing among h values will give the result of
x x x 1 x 1
optimization task.
g 0 y d 0 y 1 d 0 y 1 d 0 y 1
D. Interpolation functions of the parameterized interpolator. z z z z
Classifier (4) based on the feature x allows determining
at each point whether an artifact exists in the vicinity. If there x x 1 x 1 x 1
is no artifacts, then averaging over the nearest reference
g 1 y d 1 y 1 d 1 y
d 1 y 1
samples interpolation is used:
z z z z
g (x )
R1 g ( x ) :
x x x 1 x 1
card g (x ) :
g 2 y d 2 y 1 d 2 y d 2 y 1
z z z z
If there is an artifact, then as the interpolated
value R 2 g ( x ) : the sample along the artifact
x x x 1 x 1
direction is. The direction is defined by the minimum value of
derivative g m x . The general interpolation function (5) will g 3 y d 3 y 1 d 3 y
d 3 y 1
z z z z
look as follows:
R
1 g ( x ) : , x
r x x
x 1
x
x 1
R2
g ( x ) : , x g 4 y d 4 y d 4 y 1 d 4 y 1
z z z z
g(x )
,
R1 g ( x ) :
card g(x ) : x x 1 x x 1
g 5 y d 5 y d 5 y 1 d 5 y 1
g ( x ) : g ( x
(k )
R2 ),
z z z z
k a r g m in g m
m
x,
x x 1 x 1 x
We specify the described interpolation functions for an
important special case when the signal dimension is three. The g 6 y d 6 y d 6 y 1 d 6 y 1
displacements of the reference samples in this case can be z z z z
written as follows:
VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 22
Image Processing and Earth Remote Sensing
x x 1 x 1 x 1
x x
g 7 y d 7 y d 7 y d 7 y 2
9
m
z z z 1 z 1
R y g y
10 ,
z m 0 z
x x 1 x x
x
g 8 y d 8 y 1 d 8 y 1 d 8 y 1 y
z z z z 1 z
x x x
k
x x 1 x x 1 r y R2 y g y
,
g 9 y d 9 y 2 d 9 y 1 d 9 y 1 z
z
z
z z z z
x
k a r g m in g m y ,
Then the general interpolation formula (12) takes the 0m 9
z
following form:
x
y
z
IV. AN EXPERIMENTAL STUDY
OF A PARAMETRIZED INTERPOLATOR
AS PART OF A DIFFERENTIAL COMPRESSION METHOD
In this work, the proposed parametrized interpolator was
examined on real multidimensional signals of the UAVSAR
hyperspectral array [12] (see the example in Fig. 1) as part of
the differential compression method. The compression
coefficient K was obtained using a parameterized interpolator
(with features 1 , 2 , 3 ), compression coefficient K was
obtained with the use of averaging interpolator. Their
ratio K K / K shows how the proposed method
outperforms the averaging one. The dependence of the
Fig. 1 Several contrasted signal channels of the test set.
compression coefficient on the absolute error
abs m a x f x g x and squared error 2 (normalized by
Fig. 2 Gain in compression ratio of the proposed interpolator over the
averaging one.
Fig. 3 Dependence of normalized MSE on compression ratio.
signal variance) were obtained.
VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 23
Image Processing and Earth Remote Sensing
ACKNOWLEDGMENT
As can be seen from the dependencies shown in figures.2-5, The reported study was funded by RFBR, project number
the use of the proposed interpolator gives a significant gain in 18-01-00667 (in parts III.A, III.B, III.C, III.D, IV, V), 18-07-
compression ratio. Best results were obtained for the feature 01312 (in part II) and by the Russian Federation Ministry of
2 , however its usage is significantly time consuming. In Science and Higher Education within a state contract with the
general, obtained results show that proposed algorithm "Crystallography and Photonics" Research Center of the RAS
outperforms averaging one. under agreement 007-ГЗ/Ч3363/26 (in part I).
V. CONCLUSIONS REFERENCES
[1] S.E. Vaganov and S.I. Khashin, “Comparison of Doubling the Size of
In this paper, the parametrized algorithms for interpolation Image Algorithms,” Modeling and Analysis of Information Systems,
of multidimensional signals were modified and adapted for use vol. 23, no. 4, pp. 389-400, 2016.
as part of differential compression methods based on the [2] V.A. Soifer, “Computer image processing, Part II: Methods and
efficient coding of quantized differences between the initial algorithms,” Saarbrücken, Germany: VDM Verlag, 2010.
and interpolating values of the samples during sequential signal [3] D. Zhou, X. Shen and W. Dong, “Image zooming using directional
sweep. The studied interpolators are based on the classification cubic convolution interpolation,” IET Image Processing, vol. 6, no. 6,
of signal samples and the use of various interpolation formulas pp. 627-634, 2012. DOI: 10.1049/iet-ipr.2011.0534.
within the classes. The classifier of readings and the procedure [4] X. Li and M.T. Orchard, “New Edge-Directed Interpolation,” IEEE
for its training are described, as well as a set of interpolating Transactions on Image Processing, vol. 10, no. 10, pp. 1521-1527, 2001.
functions for the differential compression under consideration. [5] M.V. Gashnikov, “Interpolation based on context modeling for
hierarchical compression of multidimensional signals,” Computer
Computational experiments on real multidimensional signals Optics, vol.42, no. 3, pp. 468-475, 2018. DOI: 10.18287/2412- 6179-
have confirmed that the use of an adapted parameterized 2018-42-3-468-475.
interpolator has led to an increase in the efficiency of the [6] C. Dong, C.C. Loy, K. He and X. Tang, “Image Super-Resolution Using
differential compression method. Deep Convolutional Networks,” IEEE Transactions on Pattern Analysis
and Machine Intelligence, vol. 38, no. 2, pp. 295-307, 2016.
[7] S. Vaganov, “Adaptive ANN-based method of constructing an
interpolation formula for doubling the image size,” Computer Optics,
vol. 43, no. 4, pp. 627-631, 2019. DOI: 10.18287/2412-6179-2019- 43-
4-627-631.
[8] R.C. Gonzalez and R.E. Woods, “Digital image processing,” Prentice
Hall, 2007, 976 p.
[9] M.V. Gashnikov, “Multidimensional signal interpolation based on
parametric space dimension reduction,” 7th International Symposium on
Digital Forensics and Security (ISDFS), vol. 8757491, 2019.
[10] Y.C. Eldar and G. Kutyniok “Compressed Sensing: Theory and
Applications and signal processing,” Cambridge University Press, 2012,
p. 558.
[11] M.V. Gashnikov, “Optimization of the multidimensional signal
interpolator in a lower dimensional space,” Computer Optics, vol. 43,
Fig. 4 Dependence of the compression ratio on the absolute error. no. 4, pp. 653-660, 2019. DOI: 10.18287/2412-6179-2019-43-4- 653-
660.
[12] A. Najafi, M.Hasanlou and V. Akbari “Land cover change detection in
polarimetric SAR data using Algebra, similarity, and distance based
methods,” The International Archives of the Photogrammetry, Remote
Sensing and Spatial Information Sciences, vol. XLII-4/W4, 2017. DOI:
10.5194/isprs-archives-XLII-4-W4-195-2017.
Fig. 5 Averaged time of processing of a test signal.
VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 24