Introduction

During recent years, the size of processed multidimensional digital signals has been expanding faster than the storage capacities. That is why compression methods nowadays are in a great demand.

Today, a large number of compression methods have been developed. JPEG method [1] is, perhaps, the most common of them. It uses statistical coding [2,3] of transformants obtained by the twodimensional discrete cosine transform [4]. Other popular compression methods are based on twodimensional orthogonal transformations [5], fractals [6] and wavelets [7].

The listed methods have one common flaw -they are resource-intensive, which makes it difficult to use them in real-time systems, for example, in on-board imaging systems of satellites, drones and other aircrafts. These systems need compression methods that have little computational complexity. Methods which perform signal processing in a spatial domain, without transitioning to spectral components will be perfect for such application.

Methods based on differential pulse-code modulation (DPCM) [7][8][9][10] satisfy these requirements. Decorrelation of the signal in DPCM compression is achieved via the use of difference representation. However, the scope of DPCM is not limited to real-time systems, for example, DPCM acts as a stage in other compression methods. For example, JPEG algorithm uses DPCM compression at one of the stages of operation. Thus, the task of enhancement of DPCM and increasing its efficiency is topical. In this paper, we propose a new parameterized interpolator that makes it possible to increase the efficiency of DPCM compression by switching between different interpolation methods for each processed sample, depending on the presence of a contour in the vicinity of it.

The work is arranged in the following way. First, a general differential pulse-code modulation method, main types of DPCM interpolators and quantizers are presented. The next paragraph outlines the interpolation and training procedures of proposed interpolator. The third paragraph shows the results of experimental study of proposed interpolator.

Differential pulse-code modulation

DPCM compression is the sequence of following procedures -interpolation, quantization, reconstruction, and coding. The generalization of this method is presented below.

General DPCM compression

Let 𝐶(𝑣̅ ) be the original (compressible) multidimensional digital signal where 𝑣̅ is the vector of its arguments. Differential pulse-code modulation can be represented as the following sequential procedure:

1. First, a reference value 𝐶 ̅ (𝑣̅ ) is interpolated; 2. Then, the differential signal 𝑓(𝑣̅ ) is calculated as the difference between reference and original value of the signal (1):

𝑓(𝑣̅ ) = 𝐶(𝑣̅ ) − 𝐶 ̅ (𝑣̅ ),(1)

where 𝐶(𝑛, 𝑚) -is the original value of the signal.

3. The resulting differential signal is quantized (2):

𝑓 𝑞 (𝑣̅ ) = 𝑄(𝑓(𝑣̅ )),(2)

where 𝑄 -is the quantization function.

4. The reconstructed signal value 𝐶 ̂(𝑣̅ ) id calculated as the sum of the quantized differential signal and the reference value. The reconstructed value (3) is used to further interpolation:

𝐶 ̂(𝑣̅ ) = 𝐶 ̅ (𝑣̅ ) + 𝑓 𝑞 (𝑣̅ );

(3) 5. After processing the entire signal, the quantized differential signal𝑓 𝑞 (𝑛, 𝑚) is statistically encoded.

DPCM compression: Interpolation

High DPCM compression ratio is achieved when the difference signal is close to zero. Thus, it is necessary to interpolate the reference value as close to the reference one as possible. There are three main types of DPCM interpolators: averaging [8], nonlinear [9] and adaptive [10].

Averaging (linear) interpolators calculate the reference value the average over several previous signal samples. The simplest linear interpolator is the one that chooses the previous sample as the reference value. Let us describe the work of interpolators for the case of a two-dimensional original (compressible) signal 𝐶(𝑣̅ ) = 𝐶(𝑛, 𝑚).

Figure 1 shows the work of the interpolator, averaging over the two previous samples [8]. The interpolated value in this case is formed as follows:

𝐶 ̅ (𝑛, 𝑚) = [ 𝐶 ̂(𝑛−1,𝑚)+𝐶 ̂(𝑛−1,𝑚)+𝐶 ̂(𝑛−1,𝑚−1)+𝐶 ̂(𝑛+1,𝑚−1)

4

].

(4) Interpolators of this type are robust to noise, since they use averaging over several samples, but they can have a huge error on the contours.

Non-linear interpolators have a small error on the contours. The main idea of such interpolators is to interpolate the value of the signal "along" the contour using the values of the previous signal samples.

Graham interpolator [9] is a non-linear one. It is able to interpolate "along» horizontal and vertical contours. As the reference value the sample corresponding to the smallest of the following differences (5,6,7) is taken:

𝐶 ̅ = { 𝐶 ̂(𝑛, 𝑚 − 1), 𝑖𝑓 𝜆 𝑛 > 𝜆 𝑚 ; 𝐶 ̂(𝑛 − 1, 𝑚), 𝑖𝑓 𝜆 𝑛 ≤ 𝜆 𝑚 ,(5)

here

𝜆 𝑛 = |𝐶 ̂(𝑛, 𝑚 − 1) − 𝐶 ̂(𝑛 − 1, 𝑚 − 1)|,(6)𝜆 𝑚 = |𝐶 ̂(𝑛 − 1, 𝑚) − 𝐶 ̂(𝑛 − 1, 𝑚 − 1)|,(7)

where 𝜆 𝑛 -is the horizontal difference; 𝜆 𝑚 -is the vertical difference. Figure 2 shows, how this interpolator works.

The interpolator invariant to the four directions contours [10] is the enhancement of Graham interpolator. It is able to interpolator "along" horizontal, vertical and two diagonal contours. To select the reference value, 12 differences between the 8 previous samples are calculated. The interpolation is performed as follows :

𝐶 ̅ = { 𝐶 ̂(𝑛,𝜆 − = |𝐶 ̂(𝑛 − 1, 𝑚 − 1) − 𝐶 ̂(𝑛 − 1, 𝑚 − 2)| + |𝐶 ̂(𝑛 − 1, 𝑚) − 𝐶 ̂(𝑛 − 1, 𝑚 − 1)| +|𝐶 ̂(𝑛 − 1, 𝑚 + 1) − 𝐶 ̂(𝑛 − 1, 𝑚)|, ((9)) 𝜆 / = |𝐶 ̂(𝑛, 𝑚 − 1) − 𝐶 ̂(𝑛 − 1, 𝑚)| + |𝐶 ̂(𝑛 − 1, 𝑚) − 𝐶 ̂(𝑛 − 2, 𝑚 − 1)| +|𝐶 ̂(𝑛 − 1, 𝑚 − 1) − 𝐶 ̂(𝑛 − 2, 𝑚)|, (10) 𝜆 \ = |𝐶 ̂(𝑛, 𝑚 − 1) − 𝐶 ̂(𝑛 − 1, 𝑚 − 2)| + |𝐶 ̂(𝑛 − 1, 𝑚) − 𝐶 ̂(𝑛 − 2, 𝑚 − 1)| +|𝐶 ̂(𝑛 − 1, 𝑚 + 1) − 𝐶 ̂(𝑛 − 2, 𝑚)|,11

where 𝜆 | -is the vertical difference; 𝜆 − -is the horizontal difference; 𝜆 / -is the 45° angle diagonal difference; 𝜆 \ -is the 135° angle diagonal difference. Since nonlinear interpolators do not use averaging, they are subject to noise. Adaptive interpolators use the advantages of both averaging and non-linear interpolators. The adaptive interpolator at each point switches between the averaging and nonlinear method of interpolation of the reference value depending on the local features of the signal. To select an interpolation method, a criterion is chosen whose value at each point determines the choice of the interpolation method. Each interpolation method is meant to be used when it produces the smallest interpolation error -the averaging interpolator on the "smooth" sections of the signal, the nonlinear one -on the contours. The work of this interpolator is shown in Figure 3.

Adaptive Graham interpolator [10] is an example of adaptive interpolators. In each processed sample, the difference of the differences from formulas ( 6) and ( 7) is calculated. The calculated criterion is compared with the thresholds that are set for each processed signal by the preliminary training procedure. The interpolation procedure can be written as follows :

𝐶 ̅ = { 𝐶 ̂(𝑛, 𝑚 − 1), 𝑖𝑓𝜆 < 𝜆 − ; 𝐶 ̂(𝑛, 𝑚 − 1) + 𝐶 ̂(𝑛 − 1, 𝑚), 𝑖𝑓 𝜆 ∈ [𝜆 − , 𝜆 + ]; 𝐶 ̂(𝑛 − 1, 𝑚), 𝑖𝑓𝜆 > 𝜆 + ,(13)−𝐶 𝑚𝑎𝑥 ≤ 𝜆 − ≤ 0 ≤ 𝜆 + ≤ 𝐶 𝑚𝑎𝑥 , (14) here 𝜆 𝑛 = |𝐶 ̂(𝑛, 𝑚 − 1) − 𝐶 ̂(𝑛 − 1, 𝑚 − 1)|,(15)𝜆 𝑚 = |𝐶 ̂(𝑛 − 1, 𝑚) − 𝐶 ̂(𝑛 − 1, 𝑚 − 1)|, (16) 𝜆 = 𝜆 𝑛 − 𝜆 𝑚 , (17)

where 𝜆 is the contour criterion; 𝜆 − is the lower threshold for switching between interpolation methods; 𝜆 + is the upper threshold for switching between interpolation methods; 𝐶 𝑚𝑎𝑥 is the maximum value of the signal. Figure 4 shows the work of adaptive Graham interpolator. The disadvantage of this interpolation method is the need for a preliminary training procedure to calculate the thresholds which allow switching between interpolation methods.

DPCM compression: Quantization

Quantization [8,11] is the process of dividing the signal value range into a finite number of ranges, each of which is represented by one specific value.

Quantization allows increasing the compression ratio of the processed signal by introducing an error in it. The quantization of the difference signal has a special feature -a small number of quantization levels, therefore, they should be chosen thoroughly. In the present study, two quantization scales are used -uniform [12] and Max [13] quantization scales.

All intervals of the uniform quantization scale are equal, its representative values are located in the middle of the intervals and at equal distances from each other. The uniform quantization scale is a scale with a controllable error [14]. The maximum error introduced into the quantized signal is determined by the width of the scale interval. Uniform scale quantization can be written as follows:

𝑓 𝑞 (𝑣̅ ) = 𝑠𝑖𝑔𝑛(𝑓(𝑣̅ )) × [ |𝑓(𝑣 ̅)|×𝐸 𝑚𝑎𝑥 2𝐸 𝑚𝑎𝑥 +1 ],(18)

where 𝐸 𝑚𝑎𝑥 -is the maximum error.

The advantage this quantization scale is the level proportionality of the quantized signal and the original one.

Intervals of Max quantization scale are not equal. Its levels are constructed on the basis of the mean-square quantization error minimization criterion [13]. With a known distribution density of the difference signal, expression (19) for the standard-mean quantization error can be written as follows:

ℰ 𝑞 2 = ∑ ∫ (𝐶 − 𝑟 𝑙 )𝑝(𝐶) 𝑑 𝑙+1 𝑑 𝑙 𝐿−1 𝑙=0 𝑑𝐶,(19)

where ℰ 𝑞 2 -is the quantization root-mean-square error; 𝐿 -is the number of quantization levels; 𝑑 𝑙 -is the border value; 𝑟 𝑙 -is the representative value; 𝑝(𝐶)is the differential signal distribution density.

Since the difference signal is discrete, (19) can be written as:

ℰ 𝑞 2 = ∑ ∑ (𝐶 − 𝑟 𝑙 )𝑝(𝐶) 𝑑 𝑙+1 𝐶=𝑑 𝑙 𝐿−1 𝑙=0

.

(20) To construct the Max scale, it is necessary to choose 𝑑 𝑙 and 𝑟 𝑙 which would minimize the error (20). Expressions (21,22) for them are found by taking the partial derivatives of expression (20):

𝑟 𝑖 = ∑ 𝐶𝑝(𝐶) 𝑑 𝑖+1 𝐶=𝑑 𝑖 ∑ 𝑝(𝐶) 𝑑 𝑖+1 𝐶=𝑑 𝑖 , (21) 𝑑 𝑗 = 𝑟 𝑗−1+ 𝑟 𝑗 2 .

(22) In practice, Max scale is constructed from the uniform one iteratively. Its border values are calculated with the use of its representative values, and vice versa. The resulting Max scale levels are more frequent on the signal value area where the values most often appear.

Parameterization of the nonlinear interpolator invariant to four directions contours

We propose a new adaptive interpolator. It is a parameterization of the interpolator invariant to the four directions contours. Interpolation and trainig procedures are developed for proposed interpolator.

During training procedure a preliminary pass through the original signal is required to calculate the threshold value, upon which the interpolation method is chosen.

The contour criterion for the given parameterized interpolator is the difference module between the reference values obtained by means of the interpolator averaging over the four previous readings (4) and the interpolator invariant to the four directions contours (8). If the difference absolute value between the averaging and nonlinear methods is small, averaging interpolation is chosen, since it is noise-resistant. If the difference absolute value is large, then a contour is detected and nonlinear interpolation is chosen. Let us describe the work of interpolator for the case of a two-dimensional original signal 𝐶(𝑣̅ ) = 𝐶(𝑛, 𝑚).

Interpolation procedure

The interpolation procedure for proposed interpolator can be represented as follows: ],

(28) where Λ -is the interpolation threshold. Figure 5 shows the work of proposed interpolator. The procedure for calculation of the threshold value Λ is described in the next section of the article.

Post-interpolation residues energy minimization-based training procedure

To determine the value of the threshold Λ used for switching interpolation methods, it is necessary to solve the following optimization problem (29):

𝛿(Λ) = ∑ |𝐶(𝑛, 𝑚) − 𝐶 ̂(𝑛, 𝑚)| (𝑚,𝑛)∈𝜔 → 𝑚𝑖𝑛 Λ .

(29) where 𝛿 -is the interpolation error (the energy of post-interpolation residues); 𝜔 -is the set of signal samples coordinates.

To solve this problem, a preliminary signal pass is required during which the matrix ∆ (30-32) is filled. Its elements contain the total interpolation error (the sum of the difference modules between the signal sample and the interpolated value) for which criterion equals 𝜆:

∆(1, 𝜆) = ∑ |𝐶(𝑛, 𝑚) − 𝑚𝑖𝑛 𝜆 {𝐶 ̂(𝑛 − 1, 𝑚), 𝐶 ̂(𝑛, 𝑚 − 1) 𝑚,𝑛∈𝑤(𝜆)

,𝐶 ̂(𝑛 − 1, 𝑚 − 1),𝐶 ̂(𝑛 + 1, 𝑚 − 1)}|, (34) After this operation, the value of the threshold Λ can be found from expression (29). This vector contains 𝐶 𝑚𝑎𝑥 + 1 elements so one can find the required threshold value by a simple search. Thus, the optimization problem (29) is solved.

It should be noted that the proposed interpolator, including the described optimization procedure, can be used not only for compression, but also for other signal processing tasks, for example, for solving the problem of combining heterogeneous signals which have different resolution, number of components, etc.

Post-interpolation residues entropy minimization-based training procedure

When solving the compression problem, instead of (29), it is also worth considering a criterion for minimizing the amount of compressed data. In this paper we consider the quantized post-interpolation residues entropy of (18) as an estimation of the amount of compressed data:

      max max ln min C qq qC H N N         (35)

where   q N  is the amount of the quantized post-interpolation residuals with a value q. To solve the optimization problem (35), a three-dimensional matrix is used:

  () , max , 1,2 , 0 i q iC      N .

(36) Each element of () , i q  N contains the amount of quantized post-interpolation residues (18) with a value q, given the feature value (24)  and interpolator number i, which is taken from (23). i =0 means that the first row of (23) is taken as the interpolator, for i =1 all other rows of (23) are taken as interpolator.

Matrix () , i q  N is used to calculate the amount of quantized post-interpolation residuals (18)   q N  with value q for all possible values of the threshold    max 1

(1) , 0 0

C qq N      N ,    (1)

(2) ,, 1, ,

q q q q N q N q        NN . (37)

The number of values of the quantized post-interpolation residues (18) equal to q makes it possible to calculate a one-dimensional array of entropy values (35) for all possible values of the threshold . The length of this array is small (C max of the elements, i.e. equal to the maximum value of the signal). The number of the minimum entropy value (35) can be found by the direct search:

    arg min H     . (38

) Thus, the optimization problem (35) is solved.

Experimental study of DPCM interpolators

For the developed interpolator based on criterion (29) a series of computational experiments was carried out, during which the dependencies of the root-mean-square error (RMS) on the compression ratio of the quantization scale were obtained. The uniform (18) and the Max scale (21, 22) were used. The mathematical expression for the root-mean-square is as follows:

ℰ = 1 𝛿 𝐶 ∑ √(𝐶(𝑣̅ ) − 𝐶 ̃(𝑣̅ )) 2 𝑣 ̅∈𝑉 ,(39)

where 𝛿 𝐶 -is the original signal variance; 𝑉is the set of signal samples; 𝐶(𝑣̅ ) -is the original signal values; 𝐶 ̃(𝑣̅ ) -is the processed (decompressed) signal values.

The results obtained for the developed interpolator were compared with the others. For comparison, prototypes on the basis of which a parameterized interpolator was developed were taken. They are averaging over the four previous samples (4) and invariant to the contours of the four directions (8)(9)(10)(11)(12) interpolators. As a test signal set Waterloo Grayscale Set 1 [15] was used. Figure 6 shows the test set. The computational experiment was carried out in the following way: the test signals were DPCMcompressed [16] and decompressed with a constant compression ratio of a uniform quantization scale and a selected interpolator, after which the error was calculated. The results for the selected interpolator were averaged over all test set. Then the procedure was repeated for the next compression ratio of the scale. Thus, the dependencies of the root-mean-square error on the compression ratio of a uniform quantization scale were constructed for all three interpolators. A similar series of experiments was carried out for the Max scale. Figures 7 and 8 show the results of the computational experiments. As can be seen from the presented dependencies, the developed parameterization outperforms its prototypes. During computational experiments, the type of signal was found, with which the developed parameterization gives the least RMS. This result is shown in Figures 9 and 10.

Conclusions

This article presents a new adaptive interpolator for DPCM-signal compression, based on the parameterization of the interpolator, which is invariant to four directions contours. Its interpolation and training procedures are presented. Training procedure includes a preliminary pass through the signal.

A series of computational experiments was carried out. The developed parameterization outperformed its prototypes. During the computational experiments, the type of signals on which the proposed interpolator shows the best results was determined.