=Paper=
{{Paper
|id=Vol-2391/paper13
|storemode=property
|title=Adaptive interpolation of multidimensional signals for compression on board an aircraft
|pdfUrl=https://ceur-ws.org/Vol-2391/paper13.pdf
|volume=Vol-2391
|authors=Nikolay Glumov,Mikhail Gashnikov
}}
==Adaptive interpolation of multidimensional signals for compression on board an aircraft ==
https://ceur-ws.org/Vol-2391/paper13.pdf
Adaptive interpolation of multidimensional signals for
compression on board an aircraft
N I Glumov1,2, M V Gashnikov1,2
1
Samara National Research University, Moskovskoe Shosse 34А, Samara, Russia, 443086
2
Image Processing Systems Institute of RAS - Branch of the FSRC "Crystallography and
Photonics" RAS, Molodogvardejskaya street 151, Samara, Russia, 443001
e-mail: mgash@smr.ru
Abstract. We consider the compression of multidimensional signals on the aircraft board. We
describe the data of such signals as a hypercube, which is "rotated" in a special way. To
compress this hypercube, we use a hierarchical compression method. As one of the stages of
this method, we use an adaptive interpolation algorithm. The adaptive algorithm automatically
switches between different interpolating functions at each signal point. We perform
computational experiments in real-world multidimensional signals. Computational experiments
confirm that the use of proposed adaptive interpolator allows increasing (up to 31%) the
compression ratio of the “rotated” hypercube corresponding to multidimensional hyperspectral
signals.
1. Introduction
The growing interest in applied problems in the field of processing multidimensional signals [1-4]
determines the relevance of research in this area. One of the main issues is the data size corresponding
to the multi-dimensional signals. For example, data of hyperspectral remote sensing [1, 3], as one of
the types of multidimensional signal, contain up to several hundred large-sized components of high bit
depth. With airborne compression, this information needs to be transmitted through a limited
communication channel. In this situation, the use of compression [5-8] is the only possible solution.
Currently, there are many methods of compression: wavelet [9], spectral [10], fractal [11], etc.
However, all of them are very limited in airborne compression due to the high computational
complexity and complexity of error control in the spatial domain. Besides, when a hyper-spectral data
is received, a hypercube of a multidimensional signal is often “rotated” (see Figure 1-2) in a specific
way: the first component (band) contains the first lines of the source bands; the second band includes
the second lines, etc. We can see that this leads to the appearance of anisotropic correlation
peculiarities in the signal cross-sections.
In the described conditions, the method of multidimensional signal compression based on
hierarchical grid interpolation [12–13] has proven itself well. The most difficult stage of this
compression method, which largely determines the efficiency of the method as a whole, is an
interpolator of a multidimensional signal. In this paper, an adaptive interpolator based on hybrid
technology is proposed for interpolation of specifically “rotated” multidimensional signals
corresponding to hyperspectral remote sensing data. This technology combines the autoregressive
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019)
Image Processing and Earth Remote Sensing
N I Glumov, M V Gashnikov
prediction of the signal cross-sections and adaptive parameterized interpolation within the cross-
sections, which makes it possible to use the above-described correlation anisotropy of the
multidimensional signal effectively.
Figure 1. Cross-sections No. 10, 100, 120 of an Figure 2. An example of a “rotated” cross-
“un-rotated” hyperspectral cube corresponding section of hyperspectral cube corresponding
to the “natural” state of a multidimensional to a multidimensional signal compressed
signal that can be processed and visualized in the on board.
data repository.
To study the proposed multidimensional interpolator, computational experiments are performed on
natural multidimensional signals.
2. Autoregressive prediction of cross-sections of multidimensional signal
Consider a multidimensional (D-dimensional) signal
X = {x ( d 0 , d1 ,.., d D −1 )} . (1)
This signal can also be considered as a set of (D–1) dimensional cross-sections:
= X t {x t=( d1 ,.., d D −1 )} {x ( t , d1 ,.., d D −1 )}, 0 ≤ t < T . (2)
Often these cross-sections are highly correlated (see Figures 1-2), for example, when processing
hyperspectral data of remote sensing (for a hyperspectral signal of this type D = 3, and T coincides
with the number of spectral bands). To account for the interdependency of the components, we use the
linear autoregressive model:
= P t k1 X t −1 + k2 X t − 2 + ... + k N X t − N , (3)
where P is the predicted cross-section of the multidimensional signal X, ki are regression coefficients,
N is the number of reference cross-sections used for the prediction. These coefficients are found from
the condition of minimizing the quadratic error between the original and predicted components:
N
2
t
= 2
εt E X −
ki X ∑
t − i
→ min .
{ }
(3)
k
i =1
i
Consider also the differential cross-section of the signal
( d1 ,.., d D −1 ) X t ( d1 ,.., d D −1 ) − P t ( d1 ,.., d D −1 ) , 1 ≤ t < T .
Rt = (4)
t
The variance of differential cross-section R is usually much smaller than the variance of the
original cross-section Xt, and the probability distribution is much less uniform. Therefore, the
differential cross-sections (4) are much more preferable for some types of processing, for example for
compression.
3. Hierarchical compression of multidimensional signals
The difference cross-sections (4) are decorrelated, so that they can be processed independently. In this
paper, these difference components are compressed using a hierarchical compression method [12–13],
{ }
which uses a non-redundant hierarchical representation of a multidimensional signal X = x ( d ) as a
set of L scale levels X l :
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 98
Image Processing and Earth Remote Sensing
N I Glumov, M V Gashnikov
{x ( d ) : d ∈ I } ,
L −1
X = =
Xl , Xl l (5)
l =0
where Il is the set of sample indices for scale level X l :
{ } { 2l d } \ { 2l +1d }, 0 ≤ l < L .
= 2 L −1 d , I l
I L −1= (6)
(L – 1)
The scale level number (L – 1) is the resampled “grid” of signal samples with the step of 2
along each of the coordinates, and any other level (number l) is the grid of samples with the step of 2l,
from which all samples with doubled step are excluded.
During compression, the scale levels are compressed sequentially in order of decreasing their
numbers. At the same time, more resampled levels are interpolated based on samples of less resampled
levels. Since peculiarities of post-interpolation residues are similar to peculiarities of differences (4),
their coding is much more efficient than coding sources samples.
4. Adaptive interpolation of multidimensional signals during compression
The most critical step of hierarchical compression is the interpolator. In this work, differential cross-
sections (4) are compressed. The dimension of these differential cross-sections is one less than the
dimension of the original signal. Thus, for three-dimensional remote sensing, the interpolator will
work with two-dimensional data. Therefore, further, to simplify the presentation, we describe a two-
dimensional version of the adaptive interpolator.
To ensure low computational complexity of hierarchical compression, we often use trivial
interpolation procedures, based on averaging over the nearest samples of more resampled scale levels.
Here is an example of an interpolation procedure:
xl(1) ( 2m + 1,2n =
+ 1)
1
4
( )
x l +1 ( m, n ) + x l +1 ( m + 1, n ) + x l +1 ( m, n + 1) + x l +1 ( m + 1, n + 1) , (7)
where x l +1 ( m, n ) are samples of a more resampled scale level, which have already passed
compression and decompression.
This scheme is straightforward, but does not take into account local signal characteristics, for
example, the oblong structures of onboard remote sensing data [14-16] (see Figure 2). Therefore, in
this work, an adaptive interpolator is used to compress such remote sensing data. Besides function (7)
this adaptive interpolator, uses two more interpolating functions that increase interpolation accuracy of
oblong structures by averaging “along” them
xl(0) ( 2m + 1,2= n + 1)
1
2
( )
x l +1 ( m, n ) + x l +1 ( m + 1, n + 1) (8)
xl(2) ( 2m + 1,2= n + 1)
1
2
( )
x l +1 ( m + 1, n ) + x l +1 ( m, n + 1) (9)
The choice of the interpolating function for each signal sample is carried out by the parameterized
decision rule:
0, µ l ( m, n ) < α ;
xl ( m=
( j)
) , j 1, α ≤ µl ( m, n ) ≤ β ;
, n ) xl ( m, n =
2, µ ( m, n ) > β;
l
where α, β are parameters of the decision rule (thresholds for switching between interpolating
functions). These parameters are calculated automatically based on minimization of interpolation error
or entropy of quantized post-interpolation residues; µ l ( m, n ) is a feature describing the magnitude and
direction of the elongated structure in the local neighborhood of the current signal sample:
µ l ( 2m + 1,2n + 1=
) xl +1 ( m, n ) − xl +1 ( m + 1, n + 1) − xl +1 ( m, n + 1) − xl +1 ( m + 1, n ) . (10)
The large absolute values µ l ( 2m + 1,2n + 1) of the feature (10) describe to the samples
corresponding the stable oblong structures. In these situations, interpolation (8-9) “along” these
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 99
Image Processing and Earth Remote Sensing
N I Glumov, M V Gashnikov
structures is preferred. Small values of the attribute (10) correspond to the signal samples located in
relatively uniform signal areas. In these areas, the “averaging” interpolation (7) works more precisely
by averaging a noise.
The optimization of the adaptive interpolator according to the parameters α, β is performed
separately [17] for each signal realization (more precisely, separately for each hierarchical signal
level).
5. Experimental study of the adaptive interpolator
The proposed hybrid interpolator, including an intercomponent approximator and an intracomponent
adaptive interpolator, was implemented by software and built into the hierarchical compression
method. Based on this software, we performed an experimental study of the proposed interpolator
effectiveness in nature multidimensional signal sets, “rotated” in a specific way to airborne
compression (see the example in Figure 2). We used the following signal sets:
• signals [14] of hyper-spectrometer AVIRIS (224 bands);
• signals [15] of «TokyoTech» hyperspectral dataset (31 bands);
• signals [16] of hyper-spectrometer SpecTIR (360 bands, see Figure 1).
As a measure of the proposed interpolator efficiency, we used the gain G in the archive size (in %),
which was provided by replacing the averaging interpolator (7) with the proposed hybrid interpolator
in the frame of hierarchical compression method:
G = 100% ⋅ ( Snew − Sbase ) Sbase , (11)
where Sbase , Snew are the archive sizes when using averaging and proposed interpolators, respectively.
We estimated the dependence of gain (11) on the quadratic error ε2 introduced during compression.
Typical results are shown in Tables 1-9. We can see that the proposed hybrid interpolator provides
a noticeable gain (up to 31%) for the averaging interpolator.
Table 1. The gain of the adaptive interpolator for the averaging interpolator in the test signal
“Agriculture & Vegetation” of SpecTIR hyper-spectrometer.
ε2
0.00 0.67 2.00 9.80 33.74 118.02 249.83
G,% 5.74 7.57 8.45 9.69 11.44 10.36 9.07
Table 2. The gain of the adaptive interpolator for the averaging interpolator in the test signal
“Cuprite” of AVIRIS hyper-spectrometer.
ε2
0.00 0.66 1.99 9.81 34.82 126.82 271.50
G,% 13.09 17.95 20.98 24.95 25.05 22.72 19.67
Table 3. The gain of the adaptive interpolator for the averaging interpolator in the test signal “Cloth-
2” of “TokyoTech” hyperspectral dataset.
ε2
0.00 36.23 813.24 3068.88 6470.68 10730.59 15513.49
G,% 5.22 9.94 13.96 3.43 -3.16 -6.81 -9.16
Table 4. The gain of the adaptive interpolator for the averaging interpolator in the test signal “Gulf of
Mexico Wetland” of SpecTIR hyper-spectrometer.
ε2
0.00 0.67 1.99 9.52 31.98 111.70 232.48
G,% 5.22 6.84 7.67 8.84 8.67 5.76 2.83
Table 5. The gain of the adaptive interpolator for the averaging interpolator in the test signal “Doll” of
“TokyoTech” hyperspectral dataset.
ε2
0.00 36.20 780.62 2874.67 6064.38 10200.76 15172.86
G,% 8.87 13.93 5.22 0.19 -2.49 -4.21 -5.49
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 100
Image Processing and Earth Remote Sensing
N I Glumov, M V Gashnikov
Table 6. The gain of the adaptive interpolator for the averaging interpolator in the test signal “Low
Altitude” of AVIRIS hyper-spectrometer.
ε2 0.00 0.67 2.00 9.99 36.25 132.80 282.44
G,% 5.95 8.02 9.27 11.25 11.10 8.24 5.23
Table 7. The gain of the adaptive interpolator for the averaging interpolator in the test signal “T-
shirts” of “TokyoTech’ hyperspectral dataset.
ε2 0.00 36.21 818.07 3152.23 6664.50 11060.42 16190.09
G,% 9.49 14.41 7.23 1.70 -1.31 -3.27 -4.87
Table 8. The gain of the adaptive interpolator for the averaging interpolator in the test signal “Moffett
Field” of AVIRIS hyper-spectrometer.
ε2 0.00 0.66 1.99 9.74 34.55 125.98 270.11
G,% 14.49 19.26 21.87 27.52 30.81 28.98 27.40
Table 9. The gain of the adaptive interpolator for the averaging interpolator in the test signal “Urban
and Mixed Environment” of SpecTIR hyper-spectrometer.
ε2 0.00 0.67 2.00 9.94 35.77 131.16 280.30
G,% 7.24 9.44 10.40 11.38 11.90 13.01 12.25
6. Conclusion
We considered the compression of multidimensional signals, which are described by the hypercube,
«rotated» in a manner specific for onboard processing. To compress this hypercube, we used the
hierarchical compression method. As one of the stages of this method, we used the adaptive
interpolation algorithm based on automatic switching between different interpolating functions at each
point of the signal. We confirmed computational experiments in natural multidimensional signals,
which confirmed that the use of proposed adaptive interpolator allows increasing (up to 31%)
the compression ratio of the «rotated» hypercube corresponding to multidimensional hyperspectral
signals.
7. References
[1] Chang C 2013 Hyperspectral data processing: Algorithm design and analysis (Wiley & Sons)
[2] Dajion D and Mercero R 1988 Digital processing of multidimensional signals (M: Mir)
[3] Schowengerdt R 2007 Remote sensing: models and methods for image processing (Academic
Press)
[4] Woods J 2011 Multidimensional Signal, Image, and Video Processing and Coding (Academic
Press)
[5] Rehman M, Sharif M and Raza M 2014 Image compression: A survey Research Journal of
Applied Sciences, Engineering and Technology 7 656-672
[6] Bookstein A and Klein S 1990 Compression, information theory and grammars: a unified
approach ACM Trans. Inf. Systems 8 27-49
[7] Soifer V 2009 Computer Image Processing, Part II: Methods and algorithms (VDM Verlag)
[8] Woods E and Gonzalez R 2007 Digital Image Processing (Prentice Hall)
[9] Fouad M 2015 A Lossless Image Compression Using Integer Wavelet Transform with a
Simplified Median-edge Detector Algorithm International Journal of Engineering &
Technology 15 68-73
[10] Plonka G and Tasche M 2005 Fast and numerically stable algorithms for discrete cosine
transforms Linear Algebra and its Applications 394 309-345
[11] Muruganandham A and Banu R 2010 Adaptive fractal image compression using PSO Procedia
Computer Science 2 338-344
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 101
Image Processing and Earth Remote Sensing
N I Glumov, M V Gashnikov
[12] Sergeev V, Gashnikov M and Glumov N 1999 The Informational Technique of Image
Compression in Operative Remote Sensing Systems RAS Samara Research Center Bulletin 1
99-107
[13] Maksimov A I and Gashnikov M V 2018 Adaptive interpolation of multidimensional signals for
differential compression Computer Optics 42(4) 679-687 DOI: 10.18287/2412-6179-2018-42-4-
679-687
[14] URL: http://aviris.jpl.nasa.gov/data/free_data.html
[15] URL: http://www.ok.sc.e.titech.ac.jp/res/MSI/ MSIdata31.html
[16] URL: http://www.spectir.com/free-data-samples
[17] Gashnikov M V 2017 Minimizing the entropy of post-interpolation residuals for image
compression based on hierarchical grid interpolation Computer Optics 41(2) 266-275 DOI:
10.18287/2412-6179-2017-41-2-266-275
Acknowledgments
The reported study was funded by: RFBR according to the research projects 18-01-00667, 18-07-
01312; the RF Ministry of Science and Higher Education within the state project of FSRC
“Crystallography and Photonics” RAS under agreement 007-GZ/Ch3363/26.
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 102