Interpolation of multidimensional signals using the reduction of the dimension of parametric spaces of decision rules

Abstract

In this paper, we consider the interpolation of multidimensional signals problem. We develop adaptive interpolators that select the most appropriate interpolating function at each signal point. Parameterized decision rule selects the interpolating function based on local features at each signal point. We optimize the adaptive interpolator in the parameter space of this decision rule. For solving this optimization problem, we reduce the dimension of the parametric space of the decision rule. Dimension reduction is based on the parameterization of the ratio between local differences at each signal point. Then we optimize the adaptive interpolator in parametric space of reduced dimension. Computational experiments to investigate the effectiveness of an adaptive interpolator are conducted using real-world multidimensional signals. The proposed adaptive interpolator used as a part of the hierarchical compression method showed a gain of up to 51% in the size of the archive file compared to the smoothing interpolator.

1. Introduction

Currently, the need to use multidimensional digital signals is becoming more acute [1]. It is primarily about such areas as remote sensing [2-3], processing of multispectral and hyperspectral signals [4], as well as video processing.

Now we know a large number of interpolation and approximation algorithms for such signals [116], and the high-performance requirements often do not allow us to use trivial linear, bilinear or bicubic interpolators [1]. In other words, there is a tendency to the more and more widespread use of more complex interpolation methods, such as the support vector method [5], locally optimal welladapted basis functions [6], approximation by multidimensional orthogonal polynomials [7], multidimensional approximation and interpolation [8] etc.

However, the presence of a large number of well-developed solutions did not stop research in the development and modification of interpolation and approximation algorithms for multidimensional signals. The approximation based on Kronecker bases [9], splines [10], and tensors [11] continues to be improved. Artificial neural networks [7,12] are also increasingly used for interpolating signals. Even the well-known least squares method (OLS) continues to be modified [13] in recent years. In the foreign literature, special attention is paid to the sparse approximation method [14], which is the basis for the “compressed sensing” approach [15–16].

All the above algorithms have a sufficiently high accuracy in solving the corresponding applied problems. However, these algorithms have high computational complexity. In this paper, we propose fast interpolation algorithms for multidimensional signals that are adaptive due to automatic switching between interpolating functions at each point of the signal. This adaptability makes it possible to ensure high interpolation accuracy with low computational complexity, due to the simplicity of the interpolating functions used.

The proposed interpolators are parameterized. Therefore, we can optimize them according to various criteria, the choice of which is determined by the specifics of the applied problem being solved. Optimization of adaptive interpolators is carried out in the space of their parameters. The complexity of this optimization is substantial if resources are limited. In this paper, we propose an algorithm for reducing the complexity of optimization due to the dimension reduction of the interpolator parametric space. 2. Adaptive interpolation of multidimensional signals Let C  x  be a multidimensional digital signal, and x be the vector of arguments. Let an arbitrary count C(x) be necessary to interpolate using the nearest reference samples Cˆk  x  . Let Pi Cˆk  x  be the set of interpolation functions used. Thus, for the current sample C(x) several interpolating values can be calculated: . ( 1 )

The parameterized decision rule R performs the choice of the interpolating value for each signal sample:

Pi  x   Pi Cˆk ( x)

P  x   Pi  x , i  R  х , lim , ( 2 ) ( 3 ) ( 4 ) where f  x  are post-interpolation residues.

The criterion for minimizing the energy of post-interpolation residues can be used, in particular, when solving the problem of matching [17-18] of heterogeneous signals that differ in resolution, number of components, etc.

In this paper, we propose to use the criterion for minimizing the entropy [19] of post-interpolation residues. This criterion is more suitable for the problem of signal compression than the criterion considered above. When using the criterion for minimizing entropy, one should take into account that post-interpolation residues are quantized before statistical coding in many compression methods, for example, in differential [20-21] and hierarchical [22-23] compression methods. In this paper, the quantizer with a uniform [19] scale is used to calculate quantized post-interpolation residues q  x  : q  x    f  x   max  2max  1 sign  f  x  where .. means the selection of the integer part of the number, max is the maximum error [20] when quantizing.

Thus, when using the specified "entropy" optimization criterion for the interpolator, it is necessary to minimize the entropy H of the quantized post-interpolation residues q  x  : Rule R uses a local feature vector  х  , which is calculated based on the nearest reference samples Ck  x  . Let the decision rule be parameterized, i.e. depends on the parameter lim . The value of this parameter is determined by optimizing a specific criterion, which depends on the applied task. This criterion can be, for example, the criterion for minimizing the energy of post-interpolation residues: lim    f  x   min x lim , f  x   C  x   P  x  ,

H lim   

M 1  qM 1

Nq lim  ln Nq lim   min , lim

M  max C  x  , x where Nq lim  is the number of quantized post-interpolation residues equal to q, and M is the maximum value of the original signal. 3. Reduction of the parametric space dimension With significant constraints on computational complexity, interpolation algorithms are often used [1,4], which use “smoothing” (averaging) over some a set of nearest reference samples: P  x   1 N

Cˆk  x  N k1 , where Cˆk  x are the nearest reference samples, N is the number of these samples.

The specific of the interpolator application determines the arrangement of these reference samples. This arrangement can be quite non-trivial (see below) for some tasks related, for example, to the use of some image compression methods.

As mentioned above, the use of such simple interpolation algorithms is typical in situations where it is necessary to minimize the computational complexity. In particular, interpolators of this type are used in differential [20-21] and hierarchical [22-23] compression methods for multidimensional signals.

The “smoothing” interpolation algorithm is sufficiently accurate on smoothly varying signal regions since averaging reduces noise. However, the “smoothing” interpolator is always characterized by an increase in the interpolation error at the boundaries of the indicated smoothly varying regions (i.e., at the boundaries). To interpolate such boundaries, we can use algorithms that use the so-called interpolation "along the border". For a two-dimensional signal, in particular, Graham's nonlinear interpolation algorithm [20] works in this way.

When using this algorithm, the Interpolated value is equal to the reference signal sample to which the local boundary is directed. However, this algorithm, for obvious reasons, has less accuracy on smoothly varying parts of the signal.

In this article, we propose an adaptive parameterized interpolation algorithm that combines the advantages of both the described approaches: "smoothing" approach and "boundary" approach. The proposed interpolation algorithm is based on the approach described in Section 2. The proposed algorithm automatically switches between “smoothing” and “boundary” interpolators, depending on how sharp the boundary is in the local neighborhood of the processed sample.

Next, we describe the proposed adaptive interpolator. We also specify the interpolating functions ( 1 ) and decision rule ( 2 ). Denote by Nc the number of boundary directions taken into account. Let i  x : 0  i  Nc be the set of averaged absolute values of differences between the reference samples Cˆk  x in each of the directions under consideration: i  x  Cˆt  x  Cˆ  x  ( 5 ) ( 6 ) ( 7 ) where t and  are the indices of the reference samples.

The differences i  x determine the presence and intensity of the boundary in the local neighborhood of the current signal sample. We can use several thresholds ilim to decide on the presence and direction of the boundary. We compare the described differences i with these threshold values ilim . If there is no boundary in the neighborhood of the current signal sample, then we use a “smoothing” interpolating function of the form ( 6 ):

1 N P  x   P1  x   Cˆk  x , if i  ilim ,i 0, Nc 

N k1 . ( 8 )

If there is a boundary in the local neighborhood, then for interpolation we use the average value C j (x) of the two nearest reference samples located in the direction of the local boundary: P  x   P2  x   C j  x , if i  ilim,i 0, Nc  . ( 9 )

Thus, we need to solve an optimization problem in a Nc -dimensional parametric space to find the best thresholds ilim .

The application determines the dimension Nc of the parameter space ilim . As we show below, in the problem of hierarchical compression [22-23] Nc  2 for a two-dimensional signal, Nc  4 for a three-dimensional signal (in the simplest case), and then Nc grows rapidly with increasing signal dimension. However, the search for parameters can be an overly time-consuming task during compression even when Nc  2 .

In this paper, we propose to reduce the dimension of the parameter space ilim to reduce the computational complexity of finding these parameters. For this, we propose to use not the absolute values of the differences i , but their ratio during interpolation. If there is no boundary (or the boundary is weak) in the neighborhood of the current sample, all differences have close values. If there is a clear boundary in this neighborhood, then the smallest difference  j corresponds to the direction of this boundary: j  x   arg mini  x  i .

Moreover, if there is a boundary in the neighborhood, this difference is significantly different from all other differences, including the nearest difference r : r  x   arg mini  x  i: i j .

Based on this reasoning, in this article the feature of the boundary direction is defined as the difference between the two smallest differences i :  x  r  x    j  x  . ( 10 )

When interpolating each sample, the feature  x  is compared with a threshold lim . If the feature  x  is small enough (less than the threshold lim ), then it is considered that there is no boundary in the neighborhood of the current sample. Therefore, a “smoothing” interpolation of the form ( 8 ) is used:

P  x   P1  x   1 N

Cˆ  xk , if  x   lim N k1 . ( 11 )

The difference from ( 8 ) is that now this interpolation is one-parameter. If the feature  x  is larger than the threshold lim , then interpolation of the form ( 9 ) “along the boundary” is performed: P  x   P2  x   Cˆ j  x , j  arg mini, if  x   lim.

i ( 12 )

Thus, by reducing the dimension of the parameter space, we reduce the multiparameter optimization problem to a one-parameter one, in which the only parameter is lim . An automatic optimization procedure similar to [23] is used to calculate this parameter. 4. Multidimensional adaptive interpolator in the problem of hierarchical compression The proposed multidimensional adaptive interpolator can be used in various signal processing tasks. In particular, in this paper, we consider the use of this interpolator in the problem of compression. As an example of the compression method, we consider the hierarchical compression method [22-23].

This method uses a unique hierarchical non-redundant representation (see Figures 1-2) of the original multidimensional signal C  C  x  as a set of L scale levels Cl :

C 

L1 l0

Cl , Cl  Cl  x  C  x : x  Il  , ( 17 ) where Il is the set of sample indices of the corresponding scale level Xl :

IL1   2L1 x , Il   2l x \  2l1 x, 0  l  L . ( 18 )

Thus, the most resampled scale level CL1 is a “grid” of signal samples with step of 2(L – 1), and all other scale levels with the numbers l = (L-1),(L-2),..,1,0 are grids of signal samples with the step of 2l, of which samples are removed with the step of 2l+1.

With hierarchical compression, the scale levels of the signal are compressed sequentially, from the most resampled level CL1 to the least resampled level C0 . In this case, samples of more resampled levels are used for interpolation of samples of less resampled levels. 3 1 2 1 3 Differences i ( 7 ) in this case take the form: l(0) 2m  1, 2n 1, 2k 1  Cl1 m 1, n 1, k 1  Cl1 m, n, k  l( 1 ) 2m 1, 2n 1, 2k 1  Cl1 m, n 1, k 1  Cl1 m 1, n, k  l( 2 ) 2m  1, 2n 1, 2k 1  Cl1 m, n, k 1  Cl1 m 1, n 1, k  l( 3 ) 2m 1, 2n 1, 2k 1  Cl1 m 1, n, k 1  Cl1 m, n 1, k  . ( 23 )

Thus, the adaptive three-dimensional interpolator allows us to automatically switch between smoothing interpolation ( 19 ) and interpolation along the boundary of one of the four directions shown in Fig. 3. In other words, at each point of the signal we can use the interpolating value ( 19 ) or one of the following four interpolating values:

V (0) 2m  1, 2n  1, 2k  1  1 l 2 Cl1 m  1, n  1, k  1  Cl1 m, n, k  . , ( 19 ) ( 20 ) ( 21 ) ( 22 ) ( 24 )

Vl( 1 ) 2m  1, 2n  1, 2k  1  12 Cl1 m, n  1, k  1  Cl1 m  1, n, k  , Vl( 2 ) 2m  1, 2n  1, 2k  1  12 Cl1 m, n, k  1  Cl1 m  1, n  1, k  ,

Vl( 3 ) 2m  1, 2n  1, 2k  1  12 Cl1 m  1, n, k  1  Cl1 m, n  1, k  .

The “boundary” interpolating function ( 12 ) in this situation takes the form: P( 2 ) 2m  1, 2n  1, 2k 1  Vl( j) 2m 1, 2n 1, 2k 1, j  arg mini 2m 1, 2n 1, 2k 1 l i .

( 25 ) (26) (27) (28)

Thus, in the introduced notation, the three-dimensional adaptive interpolator is described by the expression:

Pl( 1 ) 2m  1, 2n  1, 2k  1,if l 2m  1, 2n  1, 2k  1  llim Pl 2m  1, 2n  1, 2k  1   Pl( 2 ) 2m  1, 2n  1, 2k  1,if l 2m  1, 2n  1, 2k  1  llim (29) where, for each scale level, the feature l 2m 1, 2n 1, 2k 1 is calculated according to expressions ( 8-10 ), and compared with threshold lim for each level.

In the two-dimensional case, the smoothing interpolator ( 6 ) can be written in the form: P( 1 ) 2m  1, 2n  1  1 Cl1 m, n  Cl1 m  1, n   Cl1 m,n  1  Cl1 m  1,n  1 l 4 Differences i ( 7 ) in this case take the form: l(0) 2m 1, 2n 1  Cl1 m, n  Cl1 m 1, n 1 , l( 1 ) 2m 1, 2n 1  Cl1 m, n 1  Cl1 m 1, n .

The corresponding interpolating values are written as follows:

Vl(0) 2m  1, 2n  1  12 Cl1 m  1, n  1  Cl1 m, n , (33)

Vl( 1 ) 2m  1, 2n  1  12 Cl1 m, n  1  Cl1 m  1, n . (34)

For the interpolation itself in the two-dimensional case, it is more appropriate to use a twoparameter adaptive interpolation function: V (0) 2m  1, 2n  1, if l 2m  1, 2n  1  llim()  l Pl 2m  1, 2n  1  Pl( 1 ) 2m  1, 2n  1, if lim()  l 2m  1, 2n  1  llim()

l V ( 1 ) 2m  1, 2n  1, if l 2m  1, 2n  1  llim()  l where l m, n is the feature of boundary direction.

l m, n  l(0) m, n  l( 1 ) m, n (36) At each signal point, the feature l m, n is compared with two thresholds llim() , lim() , because l optimization by these parameters can be done separately. (30) (31) (32) (35) 5. Experimental study of the adaptive interpolator for real-world multidimensional signals The proposed adaptive interpolator (30-36) was implemented programmatically in C++ and built into the hierarchical compression method. This software implementation was used in this article to study the effectiveness of the proposed interpolator. To this end, computational experiments were performed in real-world multidimensional signals (see Figure 4-5) of two signal sets: set no. 1 - TokyoTech hyperspectral dataset [24] (signal sizes 500x500x31 samples, 13 bits) set no. 2 - AVIRIS hyper-spectrometer [25] (signal sizes 1086x614x224 samples, 16 bits).

A measure of the effectiveness of the proposed interpolator was the relative gain in the archive size, which was achieved by replacing the smoothing interpolator with an adaptive interpolator in the frame of hierarchical compression method:    Kadapt Ksmooth 1 100% , (37) where Ksmooth , Kadapt are the compression ratios of the hierarchical compression method when using a smoothing and adaptive interpolator, respectively. Typical results of computational experiments are shown in Fig. 6-7 and Table 1. The adaptive interpolator has a gain of up to 51% in the size of the archive file compared to the smoothing interpolator.

6. Conclusion

We proposed interpolation algorithms for multidimensional signals based on automatic switching between simple interpolating functions at each point of the signal. We described the parameterized decision rules that perform this switch. We optimized the parameters of these decision rules on the criteria for the minimum energy of post-interpolation residues and criteria of the minimum entropy of quantized post-interpolation residues. We proposed a method for reducing the dimension of the parametric space of decision rules. We performed computational experiments to study the proposed interpolators on real-world multidimensional signals. We experimentally proved that using the adaptive interpolator instead of a smoothing one can significantly improve the efficiency of hierarchical signal compression. Butterfly2 Butterfly3 Butterfly4 Butterfly5 Butterfly6 Butterfly7 Butterfly Butterfly8 cd Character Chart24 ChartRes Cloth2 Cloth3 Cloth4 Cloth5 Cloth colorchart color doll fan2 fan3 fan flower2 flower3 flower party tape2 tape Tshirts2 Tshirts Cuprite-1 Cuprite-2 Low Altitude Moffett Field set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.1 set no.2 set no.2 set no.2 set no.2 8,00 6,00 4,00 2,00 0,00 , % 0 50 100

150

Cuprite-2

200

Cuprite-1

250 max

Acknowledgments

The work was partly funded by RFBR according to the research project 18-01-00667 in parts of «2 Adaptive interpolation of multidimensional signals» – «5 Experimental study of the adaptive interpolator for real-world multidimensional signals» and by the Russian Federation Ministry of Science and Higher Education within a state contract with the "Crystallography and Photonics" Research Center of the RAS under agreement 007-ГЗ/Ч3363/26 in part of «1 Introduction».

References

[1] Woods J 2011 Multidimensional Signal , Image, and Video Processing and Coding (Academic Press) p 211

[2] Jensen J 2007 Remote sensing of the environment: an Earth resource perspective (Prentice Hall ) p 619

[3] Campbell J 2002 Introduction to remote sensing (Guilford Press) p 667

[4] Borengasser M , Hungate W and Watkins R 2007 Hyperspectral remote sensing: Principles and applications (CRC Press) p 128

[5] Vapnik V 1998 Statistical Learning Theory (John Wiley & Sons)

[6] Vasin Y and Neymark Y 1978 Adaptive compression recurrent algorithms using well-adapted local restoring functions Mathematical software for CAD: Interuniversity collection 13

[7] Gulakov K 2013 The choice of neural network architecture for solving the problems of approximation and regression analysis of experimental data Bulletin of Bryansk State Technical University 2 95 - 105

[8] Bakhvalov Y 2007 The method of multidimensional interpolation and approximation and its applications (M: Sputnik+ ) p 108

[9] Caiafa C 2016 Computing Sparse Representations of Multidimensional Signals Using Kronecker Bases Neural Computation Volume 25 186 - 220

[10] Butyrsky E , Kuvaldin I and Chalkin V 2010 Approximation of multidimensional functions Scientific instrument-making 20 82 - 92

[11] Cobanu M and Makarov D 2014 Compression of images by tensor approximation Problems of development of promising micro- and nanoelectronic systems 109-112

[12] Gulakov K 2016 Modeling multidimensional objects on the basis of cognitive maps with neural network identification of parameters Thesis for Ph .D

[13] Cohen A , Davenport M and Leviatan D 2013 On the stability and accuracy of least squares approximations Comput . Math. 13 819 - 834

[14] Sahnoun S , Djermoun E , Brie D and Comon P 2017 A simultaneous sparse approximation method for multidimensional harmonic retrieval Signal Processing 131 36 - 48

[15] Donoho D 2006 Compressed sensing IEEE Trans. Inform. Theory 52 1289 - 1306

[16] Bigot J , Boyer C and Weiss P 2016 An analysis of block sampling strategies in compressed sensing IEEE Trans . Inform. Theory 62 2125 - 2139

[17] German E 2014 Algorithms for combining heterogeneous images in on-board visualization systems PhD Thesis

[18] Muratov E and Nikiforov M 2014 Methods to reduce the computational complexity of algorithms for combining heterogeneous images Cloud of Science 1

[19] Sayood K 2012 Introduction to Data Compression (The Morgan Kaufmann Series in Multimedia Information and Systems) p 743

[20] Gonzalez R and Woods E 2007 Digital Image Processing (Prentice Hall) p 976

[21] Maksimov A I and Gashnikov M V 2018 Adaptive interpolation of multidimensional signals for differential compression Computer Optics 42 679 - 687 DOI: 10.18287/ 2412 -6179-2018-42-4- 679 -687

[22] 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

[23] Gashnikov M V 2018 Interpolation based on context modeling for hierarchical compression of multidimensional signals Computer Optics 42 ( 3 ) 468 - 475 DOI: 10.18287/ 2412 -6179-2018-42- 3- 468 -475

[24] TokyoTech 31-band Hyperspectral Dataset URL: http://www.ok.sc.e.titech.ac.jp/res/ MSI/MSIdata31.html ( 03 . 11 . 2018 )

[25] AVIRIS Data - Ordering Free AVIRIS Standard Data Products Jet Propulsion Laboratory URL : http://aviris.jpl.nasa.gov/data/free_data. html (03.11 . 2018 )