In this paper, a parameterization of the nonlinear interpolator invariant to four directions contours for the digital signals is described. The interpolator automatically selects one of the possible calculation methods for each signal sample based on the presence of the contour in a sample. Training procedure is performed to calculate the optimal value of the interpolator parameter. A criterion for minimizing the post-interpolation residues energy and a criterion for minimizing of the post-interpolation residues entropy are used to find the optimal value. The proposed interpolator is applied to the task of signal compression and the task of combining heterogeneous signals. In order to examine interpolators, computational experiments are carried out on a test set. The advantage in terms of the quadratic error of suggested interpolator over prototypes is shown.
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 [
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) [
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.
DPCM compression is the sequence of following procedures – interpolation, quantization, reconstruction, and coding. The generalization of this method is presented below.
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):
(̅ ) = (̅ ) − ̅(̅ ), where (, ) – is the original value of the signal.
3. The resulting differential signal is quantized (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.
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 [
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 [
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 [
− 1), > ; ̂ ( − 1, ), ≤ , 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. (1) (2) (5)
The interpolator invariant to the four directions contours [
The disadvantage of this interpolation method is the need for a preliminary training procedure to calculate the thresholds which allow switching between interpolation methods.
Quantization [
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 [
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 [
], 2 +1 where original one.
– is the maximum error.
The advantage this quantization scale is the level proportionality of the quantized signal and the
Intervals of Max quantization scale are not equal. Its levels are constructed on the basis of the
mean-square quantization error minimization criterion [
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.
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. ℰ2 = ∑−1 =0 ∫ +1 ( − )() , density. 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
Since the difference signal is discrete, (19) can be written as: (20). Expressions (21,22) for them are found by taking the partial derivatives of expression (20): To construct the Max scale, it is necessary to choose and which would minimize the error ℰ2 = ∑−1 =0 ∑+1 = ( − )()
.
= ∑ +1 ()
= ∑ +1 ()
= = −1+ 2 ̂ ( − 1, − 1 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 (̅ ) = ( , ).
The interpolation procedure for proposed interpolator can be represented as follows: ( ̂ ( − 1, ) + ̂(, − 1) ̂( − 1, − 1 ) + ̂( + 1, − 1 ))/4 , signal sample and the interpolated value) for which criterion equals : (23) (24) (25) (26) (27) (28) (29) ∑ ,∈ ( ) | (, ) − ∆(1, ) = { ̂( − 1, ), ̂ (, − 1 ), ̂( − 1, − 1 ), ̂( + 1, − 1)}| ∆(2, ) = ∑,∈() where Nq 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:
N(i,)q , i 1, 2, 0 Cmax . (36) Each element of N(i,)q 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 N(i,)q is used to calculate the amount of quantized post-interpolation residuals (18) Nq , with value q for all possible values of the threshold
Cmax 1 Nq 0 N(1,)q 0
, Nq 1, q Nq , q N(1,)q N(2,q) .
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 (Cmax 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
Thus, the optimization problem (35) is solved.
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. (35) (37) (38)
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-12)
interpolators. As a test signal set Waterloo Grayscale Set 1 [
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.
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.
The reported study was funded by RFBR according to the research projects № 18-01-00667, № 18-07-01312.