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