=Paper=
{{Paper
|id=Vol-2210/paper7
|storemode=property
|title=Multidimensional signals interpolation based on NEDI for HGI compression
|pdfUrl=https://ceur-ws.org/Vol-2210/paper7.pdf
|volume=Vol-2210
|authors=Mikhail Gashnikov
}}
==Multidimensional signals interpolation based on NEDI for HGI compression==
<pdf width="1500px">https://ceur-ws.org/Vol-2210/paper7.pdf</pdf>
<pre>
Multidimensional signals interpolation based on NEDI
for HGI compression

                    M V Gashnikov1

                    1
                        Samara National Research University, Moskovskoe Shosse 34А, Samara, Russia, 443086


                    Abstract. Adaptive interpolation of multidimensional digital signals is considered. An
                    adaptive algorithm for digital signals interpolation is proposed, intended for hierarchical
                    compression. The prototype of the proposed interpolator is the NEDI (New Edge-Directed
                    Interpolation) algorithm. In this paper, the NEDI interpolation algorithm is modified for use on
                    special hierarchical grids, which are used for hierarchical signal compression. Experimental
                    researches of the proposed interpolator are performed with the hierarchical compression of
                    natural digital signals. Experiments confirm that the proposed adaptive interpolator allows
                    improving the efficiency of hierarchical compression of digital signals.



1. Introduction
Availability of digital information processing devices continues to increase. This entails an increase in
the data size of processed digital signals, and this problem can not be solved by increasing capacity of
storage devices. Moreover, multidimensional signals, including multi- and hyperspectral [1-3] remote
sensing data, as well as results of sensing by quadrocopters and other unmanned aerial vehicles, are
also becoming more accessible. This further exacerbates the problem of an excessively large size of
digital signal data. The only acceptable solution at the moment is compression of digital signals [4-5].
    To date, there are many [4-8] methods of compression of digital signals. The most popular of these
methods is the JPEG compression method [11], based on discrete cosine transform (DCT) [9] and
subsequent entropy coding [10] of transformants (DCT results). The more efficient [12] compression
method JPEG-2000 [13], which uses the discrete Wavelet transform [14], is much less widely used.
    These methods of the JPEG group are used very widely, due to wide variety of hardware devices in
which they are embedded. However, there are a number of problems that raise requirements for the
quality of compressed digital data. First of all, this is polygraphy and processing of remote sensing
data. In these areas, one has to deal with digital signals, which are unique. When compressing such
signals, strict quality control is necessary. In addition, such signals may also have a high bit capacity.
Moreover, such signals can have substantially more than three spectral bands (hyperspectral signals
often have hundreds of spectral bands). In other words, when compressing such signals, complexity
can arise already at the stage of processing data of specific formats.
    Fractal [15] compression methods, according to the author, currently have the largest compression
ratio. However, their propagation is difficult due to specific, in most cases unacceptable signal
distortions, as well as excessively high computational complexity.
    Also, it should be noted an important drawback, corresponding to all the above methods of signal
compression. This drawback follows from the need to transform the signal into a corresponding space
of transformation coefficients. Accordingly, it is not always possible to control the error in the
specified space of coefficients. For the mean-square error, such control is possible in a number of

IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)
Image Processing and Earth Remote Sensing
M V Gashnikov




cases due to Parseval's equality. But for more strong quality measures, for example for maximum
error, the specified error control for the above compression methods is usually impossible.
    In the author's opinion, using specific compression methods that do not require the transformation
to spectral (or any other) auxiliary spaces is promising in specific areas that raise high demands to the
quality of digital signals. In this paper, the method of hierarchical compression is chosen as such
method [16, 17]. This method is based on multiple non-redundant resampling of initial array of signal
samples and interpolation of signal samples based on the specified resampled arrays.
    Hierarchical compression methods have a number of important advantages, such as fast multiscale
access to fragments of compressed data, the ability to control the speed of formation of a compressed
data stream, the possibility of increasing noise immunity and the possibility of error control (including
the maximum error [18]). The task of research and further increasing the efficiency of hierarchical
compression methods of digital signals is certainly topical.
    An important step in hierarchical compression methods is an interpolator in which samples of more
resampled signal are used to interpolate samples of less resampled signal. The most common
algorithm of hierarchical interpolation is simple averaging [19-20] from the nearest signal samples of
more resampled hierarchical levels of the signal. However, the averaging interpolator is not effective
enough, because it is not adaptive (it performs in the same way, regardless of local signal
characteristics).
    One of the ways to take into account the local characteristics of a digital signal is context modeling
[21-23], which has become widespread, in particular, in statistical coding [7]. In the simplest case, the
context for a next encoded symbol is the previous symbol (or several previous symbols), and the
context model is the estimation of conditional probability distribution of the encoded symbol. Taking
into account the context, that is, using the conditional probability distribution instead of the
unconditioned distribution makes it possible to increase the algorithm adaptability to variable
statistical properties of the signal, which leads to an increase in the efficiency of the compression
method as a whole.
    In this paper, context modeling is used for the development of adaptive interpolation algorithms
that are part of a compression method based on hierarchical grid interpolation (HGI). The proposed
adaptive interpolators allow increasing the efficiency of the hierarchical compression method.
    For the hierarchical method of signal compression, an interpolator based on the NEDI algorithm
[24] using context modeling is proposed. When developing this interpolation algorithm, a set of
surrounding signal samples is considered as a context for each signal sample.

2. Hierarchical compression of multidimensional signals
Hierarchical grid interpolation (HGI) [16, 25-26] is based on special hierarchical representation of an
                                                                
                                                      r
integer nonnegative multidimensional signal X  x c in the form of a set of hierarchical levels Xl:
                             L 1

                                                                             
                                                 r                             r         r
                         X  UX l , X L1  xL1 c , X l                   xl c \ xl 1 c , l  L  1 ,
                              l 0


                                                                  
                                                     r                                         r
where L is the number of hierarchical levels Xl, {xl c } is the signal resampled with step 2l, c is the
vector of multidimensional signal arguments.
   With hierarchical compression, the hierarchical levels Xl are compressed sequentially, from the
highest (most resampled) level XL–1 to the lower levels. The proportion of data size of the highest
level XL–1 is sufficiently small already for L  4 , so the compression algorithm of this level does not
matter. So, only compression algorithm of any "non highest" hierarchical level Xl, l<L–1 is described.
   Stage No. 1. Interpolation.
   Interpolation of samples of the current signal level Xl is based on the samples {x k  m, n  , k  l} of
already processed hierarchical levels { X k , k  l } :




IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)                     48
Image Processing and Earth Remote Sensing
M V Gashnikov




                                               ) r           L1     
                                               xl ( c )  P  U X k  ,                              (1)
                                                             k l 1 
        ) r
where xl ( c ) is interpolating value, P(..) is a function that defines a certain interpolator. Further,
interpolators are considered in detail.
    Stage No. 2. Calculation of difference signal.
                                                     
                                             r                          ) r
    The differences between the initial xl c and interpolating xl ( c ) (1) values of the current level
samples are calculated:
                                                                          
                                                              r      r ) r
                                                          f l c  xl c  xl c .                                              (2)
    Stage No. 3. Quantization.
    The difference signal (2) is quantized by the quantifier with a uniform scale ([..] is the integer part
of a number):
                                                                              
                                    r              r          r
                                ql (c)  sign f l (c)  f l (c)  max  2max  1 ,                (3)
                                                                                    
allowing to control the maximum error [19] max:
                                                                 
                                                r        r       r
                                            f l c  x c  x c  max .                                  (4)
    The quantized signal (3) is then compressed by an entropy encoder and stored in an archive.
    Stage No. 4. Recovering.
    The restored values of the signal samples are calculated (already during compression):
                                                            
                                            r   ) r                     r
                                        x l c  xl c  1  2max  ql (c) ,                                                 (5)
which are necessary for interpolation (1) of the following (more resampled) hierarchical
levels { X k , k  l } of signal.

3. Averaging interpolation for hierarchical signal compression
For reasons of computational complexity of interpolation under hierarchical compression, we
usually [19-20] use trivial averaging over the nearest already restored signal samples of more
resampled hierarchical levels. To simplify the algorithm description, the averaging interpolator is
                                                             
                                               r
considered for a two-dimensional signal X  x c  x  m, n  .
    Let’s consider two types of interpolated samples: "type I" with indices of the form  2m  1,2n  1
and "type II" with indices of the form xl 2m  1,2n  and xl  2m,2n  1 . Let’s consider the simplest way
of processing samples of both samples types when using the averaging interpolator. Interpolation is
performed based on the restored samples of previous (more resampled) hierarchical level:
                               )
                                                              
                               xl  2m  1,2n    x l 1  m, n   x l 1  m  1, n  2 ,
                                                                                                     
                                                                                                                              (6)
            )
                                                                                                                    
           xl  2m  1,2n  1   1  x l 1  m, n   x l 1  m  1, n   x l 1  m, n  1  x l 1  m  1, n  1 4 (7)
                                                                                                                           
   This averaging interpolation algorithm has low computational complexity. But this algorithm has
insufficiently high efficiency, since it does not take into account any local signal characteristics.

4. Context modeling for data compression
Application of context modeling approaches [21-23] for data compression is based on the «modeling
and coding» idea proposed by Rissanen and Langdon [21]. In accordance with this idea, the
compression procedure consists of two steps: modeling and coding.
   By modeling, we mean the construction of model of information source that generates compressed
data. By coding, we mean the process of reducing data size based on the results of modeling. So,
the "coder" creates a compressed stream, which is a compact form of the processed data, based on the
information supplied by the "modeler".


IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)                                        49
Image Processing and Earth Remote Sensing
M V Gashnikov




    Let the probability of the symbol si be p( si ) . From Shannon's theorem [7] on coding the source of
messages, it is known that the symbol si is best represented by  log2 p( si ) bits. Often the source
structure is unknown or complex, so it is necessary to build a source model that allows you to find an
estimate of the probability p( si ) of each symbol si.
    Estimation of the symbol probability during the simulation is performed on the basis of known
(or estimated) symbols statistics and, possibly, a priori assumptions. Therefore they speak about
statistical modeling. In other words, the "modeler" predicts the probability of each symbol.
    At the stage of statistical coding, the symbol si is replaced by a code with a length of  log2 p( si )
bits. The more accurate the estimation of the signals probability, the more effective the codes are, and
the more effective the compression as a whole.

5. Signal interpolation based on NEDI
In the initial setting, context modeling is used for entropy coding, but we use context modeling for
interpolating signals. In particular, in terms of context modeling, the New Edge-Directed Interpolation
(NEDI) [24] can be described.
    Let’s describe the interpolation algorithm NEDI. Let X  {x  m, n } be the original signal of
size WxH. We need to calculate a signal Z  {x  m, n } of size 2Wx2H with twice the best resolution.
If we use the NEDI, this signal is calculated as follows. Signal samples with even indices are equal
to samples of the original signal:
                                             z(2m,2n)  x(m, n) .                                  (8)
    The signal samples with indices (2m  1,2n  1) are calculated (see Figure 1) as follows:
                                                                  1    1
                                            z(2m  1,2n  1)  2i  j x(m  i, n  j ) ,                (9)
                                                                 i 0 j 0

where i , i  0..3 are local interpolation coefficients.
   So the missing signal samples are calculated as a weighted sum of the four nearest reference signal
samples. In this case, it is necessary to calculate the optimal local weighting coefficients i , i  0..3 .
These coefficients are calculated by the optimization of the quadratic error:
                                      2   ( x(i, j )  z(i, j ))2  min ,                           (10)
                                                                                  0 ,1 ,2 ,3
                                                    i , jD

where D is area of interpolation coefficients estimation. This area includes N signal samples.




                    Figure 1. Location of reference signal samples for NEDI interpolation
                                                                             r
   We place the samples x(i, j ) from the estimation area D into the array Y  [ y0 , y1 ,..., y N 1 ]T . The
                       r
elements of the array Y are assigned to signal samples from the estimation area D, starting from the
upper left corner and then according to the progressive scan of area (see Figure 2). Also consider the
matrix
                                                c0,0 ... c0,3 
                                                                      
                                           C   ... ... ...  .                                           (11)
                                                cN 1,0 ... cN 1,3 



IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)                      50
Image Processing and Earth Remote Sensing
M V Gashnikov




   Each row of this matrix consists of reference signal samples, which are used to interpolation of the
samples of the estimation area (see Figure 2).
                                             c0,0                c0,1

                                                        y0        y1        y2

                                             c0,2                c0,3       yk                  Area D
                                                                                                of estimation
                                                                                                of interpolation
                                                                            0       1         coefficients

                                                                            2       3
            Figure 2. Estimation area D of the interpolation coefficients of the NEDI algorithm.

    So criterion (10) is represented as:
                                                                                            r
                                                                2   ( yk  Ck )2  min
                                                                                        r ,                                                                        (12)
                                                                                                          
                                                                         kD
                                                       r
where Ck is the row number k of the matrix C,   0 , 1 , 2 , 3  is the vector of unknown
                                                                        T


interpolation coefficients.
    To solve the optimization problem (12), we equate to zero the following partial derivatives:
                  2
                   ( y0  (0c0,0  1c0,1  2 c0,2  3c0,3 ))  c0,0  ...  ( y N 1  (0cN 1,0  1cN 1,1  2 cN 1,2  3cN 1,3 ))  cN 1,0  0
                 0
                  2
                  ( y0  (0c0,0  1c0,1  2 c0,2  3c0,3 ))  c0,1  ...  ( y N 1  (0cN 1,0  1cN 1,1  2 cN 1,2  3cN 1,3 ))  cN 1,1  0
                 1
                 2
                   ( y  ( c   c   c   c ))  c  ...  ( y  ( c   c   c   c ))  c  0
                  2    0     0 0,0    1 0,1    2 0,2     3 0,3       0,2             N 1     0 N 1,0     1 N 1,1    2 N 1,2     3 N 1,3       N 1,2

                 2
                 
                   ( y0  (0c0,0  1c0,1  2 c0,2  3c0,3 ))  c0,3  ...  ( y N 1  (0 cN 1,0  1cN 1,1  2 cN 1,2  3cN 1,3 ))  cN 1,3  0
                 3
    The solution of this system of equations:
                                                                        r                           r
                                                                          (C T C )1  (C TY ) , (13)
    This expression allows us to calculate the optimal interpolation coefficients i , i  0..3 . The
advantage of considered context NEDI algorithm is the adaptability to local signal characteristics, the
disadvantage is high computational complexity. By context, in this case, we mean the set of
surrounding reference samples that constitute the area of parameters estimation. By context modeling,
in this case, we mean the local estimation of interpolation coefficients.

6. NEDI-based interpolation algorithm for hierarchical signal compression
In this paper, we propose a modification of the NEDI interpolation algorithm for non-redundant
hierarchical sample grids, which are used for hierarchical signal compression. At each "non-highest"
hierarchical level Xl , 0  l  L  2 , an estimation area D is chosen for interpolation of each sample of
hierarchical level. This area D consists of already restored samples of previous (more resampled)
                                                                         r
hierarchical levels Xk , l  1  k  L  1 , which are stored into array Yl . The "own" matrix Cl (see the
previous section) corresponds to each element of this array.
                                                            r
   In Figure 3, for two hierarchical levels, the array's Yl samples are shown in light color, the matrix
elements belonging to the hierarchical level X1 are shown in dark color (the interpolated sample
belongs to the hierarchical level X0).




IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)                                                                              51
Image Processing and Earth Remote Sensing
M V Gashnikov




                                                                              Area D
                                                                              of estimation
                                                                              of interpolation
                                                                              coefficients

                                                                              Interpolated
                                                                              pixel




             Figure 3. Estimation area D of the NEDI interpolation coefficients for hierarchical
                                               compression.

    Estimation of local interpolation coefficients is performed in the same way as expression (13),
taking into account the described specificity of estimation areas:r
                                              r
                                              l  (Cl T Cl )1  (Cl TYl ) .                        (14)
    First, the algorithm described above is applied to interpolation of samples with indices of the form
(2i+1, 2j+1), then the interpolation coefficients for the remaining samples are computed (similarly, the
entire situation is rotated by 45 degrees).
     The advantage of the proposed interpolation algorithm is its adaptability to a context (local
characteristics of the signal in a small neighborhood of current sample). This increases the accuracy of
interpolation of the signal sample. The disadvantage of the algorithm is high computational
complexity of calculating the interpolation coefficients.
    It should be noted that it is not always possible to compute an inverse matrix to the matrix Cl T Cl ,
since matrix Cl T Cl can be ill-conditioned. A feature of ill-conditioning is the situation when the
number of conditionality of the matrix Cl T Cl exceeds a certain “conditioning threshold” T (parameter
of proposed interpolation algorithm). In this situation, instead of NEDI interpolation, averaging
interpolation (6-7) is used. The “conditionality threshold” T affects the efficiency of compression,
because this threshold affects the interpolation algorithm. However, the proportion of signal samples
for which the situation of ill-conditionality arises is quite small.

7. Experimental research of adaptive interpolation algorithm
We developed a software implementation of the proposed adaptive context interpolator based on
NEDI. We built this interpolation algorithm into the hierarchical compression method. To research the
effectiveness of the proposed interpolator, computational experiments were performed in natural test
signals. Some of these test signals are shown in Figure 4.
    As a measure of interpolator efficiency, the relative gain in the archive file size was used, that is
achieved through the use of the proposed interpolator (9-14) instead of the averaging (6-7) interpolator
within the framework of the hierarchical compression:
                                                   S standart  S new
                                                                     100% ,
                                                        S standart
where S standart , S new are archive files sizes when signal compressing by the hierarchical method using
the averaging and proposed interpolators, respectively.
    In each computational experiment, we selected the best (by the compression ratio) threshold values
T of the condition number of the matrix C T C for a fixed number L of hierarchical levels and fixed
size N of the estimation area. Some typical results are shown in Figure 5.
    From the received experimental results it is clear, that the proposed algorithm provides the gain (up
to 2%) on the archive size.



IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)                 52
Image Processing and Earth Remote Sensing
M V Gashnikov




                                                 (a)                          (b)
                                            Figure 4. Examples of natural test signals.

    From the results of the computational experiments it can be seen that the proposed adaptive
interpolator provides a noticeable (up to 8%) gain on the archive size. This gain increases when the
maximum compression error and the size of the interpolation coefficient estimation area are increased.

8. Conclusion
An approach based on context modelling was used to develop an adaptive interpolator for hierarchical
signal compression. Based on this approach, a context interpolator based on the NEDI algorithm is
proposed. The proposed interpolator is implemented as software and is built into the hierarchical
method of signal compression. Computational experiments were conducted to research the
effectiveness of the proposed contextual interpolator in natural test signals. It is shown that use of the
proposed context interpolator instead of the average interpolator is noticeable (up to 8%) increases the
efficiency of hierarchical signal compression.
                       Δ, % 9
                            8
                               7
                               6
                               5
                               4
                               3
                               2
                               1
                               0                                                                    εmax
                                       1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
                                                 L=4 N=16 T=179                  L=4 N=36 T=360
                                                 L=4 N=64 T=619                  L=5 N=64 T=371

                    Δ, % 7
                           6

                           5

                           4

                           3

                           2

                           1

                           0
                                   1    2   3   4   5   6   7   8   9 10 11 12 13 14 15 16 17 18 19 20   εmax
                                                L=4 N=16 T=112                   L=4 N=36 T=198
                                                L=4 N=64 T=255                   L=5 N=64 T=290
           Figure 5. Gain  of the proposed context interpolator over the averaging interpolator
                                 as a function of the maximum error max .




IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)                          53
Image Processing and Earth Remote Sensing
M V Gashnikov




9. References
[1] Chang C 2007 Hyperspectral data exploitation: theory and applications (New York: Wiley-
      Interscience) p 440
[2] Borengasser M 2004 Hyperspectral Remote Sensing – Principles and Applications (CRC Press)
      p 128
[3] Chang C 2013 Hyperspectral Data Processing: Algorithm Design and Analysis (New York:
      Wiley Press) p 1164
[4] Vatolin D, Ratushnyak A, Smirnov M and Yukin V 2002 Data compression methods. Archive
      program architecture, image and video compression (Moscow: Dialog-MIFI Publisher) p 384
[5] Sayood K 2012 Introduction to Data Compression (The Morgan Kaufmann Series in
      Multimedia Information and Systems) p 743
[6] Woods E and Gonzalez R 2007 Digital Image Processing (New Jersey: Prentice Hall) p 976
[7] Salomon D 2007 Data Compression. The Complete Reference (Springer-Verlag) p 1118
[8] Pratt W 2007 Digital image processing (New York: Wiley Press) p 807
[9] Plonka G and Tasche M 2005 Fast and numerically stable algorithms for discrete cosine
      transforms Linear Algebra and its Applications 394(1) 309-345
[10] Lidovski V 2004 Information theory: Tutorial (Moscow: Kompania Sputnik+) p 111
[11] Wallace G 1991 The JPEG Still Picture Compression Standard Communications of the ACM
      34(4) 30-44
[12] Ebrahimi F, Chamik M and Winkler S 2004 JPEG vs. JPEG2000: An Objective Comparison of
      Image Encoding Quality Proc. of SPIE Applications of Digital Image Processing XXVII 5558
      300-308
[13] Li J 2003 Image Compression: The Mathematics of JPEG-2000 Modern Signal Processing 46
      185-221
[14] Gupta V, Sharma A and Kumar A 2014 Enhanced Image Compression Using Wavelets
      International Journal of Research in Engineering and Science (IJRES) 2 55-62
[15] Woon W M, Ho A T S, Yu T, Tam S C, Tan S C and Yap L T 2000 Achieving high data
      compression of self-similar satellite images using fractal Proc. of IEEE Int. Geoscience and
      Remote Sensing Symposium (IGARSS) 609-611
[16] Gashnikov M V, Glumov N I and Sergeyev V V 2000 Compression Method for Real-Time
      Systems of Remote Sensing Proc. 15th Int. Conf. on Pattern Recognition 3 232-235
[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
[18] Lin S 2004 Error Control Coding: Fundamentals and Applications, second edition (New
      Jersey: Prentice-Hall) p 1260
[19] Efimov V M and Kolesnikov A N 1997 Effectiveness estimation of the hierarchical and line-by-
      line lossless compression algorithms Proc. of the III conf. Pattern recognition and image
      analisys 1 157-161
[20] Gashnikov M V 2016 Interpolation for hyperspectral images compression CEUR Workshop
      Proc 1638 327-333
[21] Rissanen J J and Langdon G G 1981 Universal modeling and coding IEEE Transactions on
      Information Theory 27(1) 2-23
[22] Cleary J G and Witten I H 1984 Data compression using adaptive coding and partial string
      matching IEEE Transactions on Communications 3(4) 396-402
[23] Bloom C 2015 California Institute of Technology: Solving the problems of context modeling
      (Access mode: http://www. cbloom.com/papers/ppmz.zip)
[24] Li X and Orchard M T 2001 New Edge-Directed Interpolation IEEE Trans. Image Process 10
      1521-1527
[25] Gashnikov M V and Glumov N I 2016 Development and Investigation of a Hierarchical
      Compression Algorithm for Storing Hyperspectral Images Optical Memory and Neural
      Networks 25(3) 168-179


IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)         54
Image Processing and Earth Remote Sensing
M V Gashnikov




[26] Gashnikov M V and Glumov N I 2015 Hyperspectral images repository using a hierarchical
     compression Posters proc. of 23 Int. Conf. on Computer Graphics, Visualization and Computer
     Vision 1-4

Acknowledgments
This paper was funded by RFBR according to the research projects 18-01-00667, 18-07-01312.




IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)        55

</pre>