The method of image compression based on differential pulse-code modulation (DPCM) with an adaptive extrapolator is investigated. This extrapolator automatically adapts to local features of contours (boundaries) in the image. The issue of the negative effect of quantization on the result of optimizing the adaptive extrapolator is investigated. It is experimentally proved that, despite this effect, the adaptive extrapolator has the advantage over prototypes. Also, an experimental research of the considered method is carried out as a whole; a comparison is made with the JPEG method with respect to the maximum error in a half-tone Waterloo set of natural images.
Then, an extrapolated value xˆ m, n is subtracted from the original pixel value x m, n to calculate the difference signal f m, n . Then, the difference signal f m, n is quantized Q f , the result of this quantization is a quantized difference signal f m, n . This signal is encoded and transmitted through a communication channel or sent to an archive file. The quantized signal f m, n is immediately used to calculate the corresponding recovered pixel value x m, n : f m, n x m, n xˆ m, n ,
f m, n Q f m, n , x m, n f m, n xˆ m, n .
The restored pixel value x m, n is used to extrapolate (
The requirement of low computational complexity makes it necessary to apply in DIKM only the simplest [16] extrapolators
of the form:
xˆ(0) m, n x m 1, n ,
xˆ(
,
xˆ(
xˆ(0) m, n , if m (m, n) n (m, n); xˆG m, n
xˆ(
These linear extrapolators work worst on contours (object boundaries). As an answer to this problem, extrapolators that are
invariant to contours are considered, for example Greham's extrapolator [3], which is invariant to vertical and horizontal
contours:
xˆ m, n P x i, j : i m or i m and j n .
(
n m, n x m 1, n x m 1, n 1 .
The smaller difference from the differences (
The advantages of the "contour" extrapolator (
Image Processing, Geoinformation Technology and Information Security / M.V. Gashnikov
extrapolation (
The parameters () , () are automatically calculated before the actual DPCM processing for each particular image. A special optimization procedure for the adaptive extrapolator is used for this (see below). Then the parameters () , () are placed in the archive, because they are also necessary for decompression.
Optimization of the adaptive extrapolator (search of parameters () , () ) is based on minimizing the sum of the absolute values of extrapolation errors over the set {m, n } of coordinates of all image pixels:
The error (
x m, n xˆ m, n m,n min .
() ,() () , () () () (0) () ()
. 2rel 2 Dx 1 2
x m, n x m, n ,
MNDx m,n where () ()
m,n() x m, n xˆ m, n , (0)
m,n(0) x m, n xˆ m, n , () ()
m,n() x m, n xˆ m, n , ( ) (0)
( ) , () m, n : m, n 0, (0) m, n : m, n 0, () m, n : m, n 0.
As a result, the two-parameter optimization problem (
To solve these problems, a special matrix is filled in the preliminary pass through the image i,
m,n
x m, n xˆ i m, n , 0 i 2 , xmax xmax .
Each element i, of this matrix contains the sum of extrapolation errors of extrapolator number i (
xmax () xmax 1,xmax , () () 1 2, 1, , 0 xmax .
0
The computational complexity of this procedure does not depend on the image size. Optimal value ( ) can be found in this array ( ) (( ) ) by an exhaustive search (the length of this array is only xmax+1). Analogously () is calculated.
For quantization in DPCM, the Max scale [5-6] is usually used, which provides the minimum relative root-mean-square error
where x m, n is the original image, x m, n is the restored (decompressed) image, Dx is the image variance, MхN are
image sizes.
(
Image Processing, Geoinformation Technology and Information Security / M.V. Gashnikov
For unique data, more strong error control [17] is necessary. For example, it is necessary for compression of hyperspectral images [18-20]. In this case, a quantizer with a uniform scale [3] can be used for DPCM. This quantizer provides maximum error control:
It should be noted an important nuance that occurs when optimizing an adaptive extrapolator. The optimization procedure described above for the adaptive extrapolator can be performed only in the absence of quantization (when the quantizer is "switched off"). In this case, the original x m, n and recovered x m, n values of the image pixels are equal, the difference f m, n and quantized difference f m, n signals are also equal. The "activation" of the quantizer at the stage of extrapolator optimization would lead to the impossibility of calculating the restored values of the pixels, since they, through the chain of transformations, depend on the parameters () , () of the extrapolator, which at this stage are still unknown.
Thus, the general scheme of DPCM compression with an adaptive extrapolator is as follows. First, to optimize the extrapolator, a preliminary pass through the image with the "switched off" quantizer (i.e., zero-error) is performed. In this case, the extrapolator parameters () , () are calculated. After that, the DPCM-compression itself is made, in which the quantizer is "switched on" again, and the parameters () , () found on the preliminary pass are used for extrapolation.
As a result, the parameters of the extrapolator, optimal by criterion (
The investigation was carried out for one-parameter problems (
The dependence of the total error () on the extrapolator parameter ( ) is shown in Fig. 1. The value of the second parameter () was fixed (it was chosen in the optimal way). Then the same research was performed for total error () . The dependence of the total error () on the extrapolator parameter () is shown in Fig. 2. Thus, accordingly, the value of the parameter ( ) was fixed.
(+) 3.5 2.5 1.5 (-) 3.5 2.5 ( ) for a fixed () 19 (the vertical line shows the position of the minimum of the estimative total error). parameter () for a fixed ( ) 7 (the vertical line shows the position of the minimum of the estimative total error).
These researches allow drawing the following conclusions: Estimative total error Total extrapolation error for uniform quantizer Total extrapolation error for Max’s quantizer 0 32 64 96
Image Processing, Geoinformation Technology and Information Security / M.V. Gashnikov Quantization affects the results of optimization of the adaptive extrapolator, since the minimum of the true total error and the minimum of the estimative total error may not be equal When using the Max quantizer, the values found for the parameters of the adaptive extrapolator are closer to the optimum.
It is necessary to carry out a research of the extrapolator's efficiency for estimating the effect of a mismatch between the optimums of the true total error and estimative total error. 7.
To evaluate the effectiveness of the adaptive extrapolator for compression, this extrapolator was compared with other extrapolators. The comparison was produced by the entropy Hq of the quantized difference signal. This entropy is a good estimate of compressed data size. The results are shown in Fig. 3-4. Conclusions: 1. The adaptive extrapolator has the advantage over prototypes over the entropy of the quantized signal. 2. Consequently, the negative influence of the quantizer described in the previous section does not have a determining value (at least for small extrapolation errors). 3. With increasing maximum error, the negative influence of the quantizer on the efficiency of the adaptive extrapolator increases. With a maximum error of more than six, adaptive extrapolator loses the advantage.
To evaluate the efficiency of the image compression method based on DPCM with the adaptive extrapolator, it was compared with method JPEG in the coordinates "error-compression ratio" on the set of images "Waterloo" [21], which is traditionally used for comparison of compression methods. The results obtained, averaged over all images of the set, are shown in Fig. 5. The results of the experiments demonstrate a significant gain (up to two times) of DPCM with an adaptive extrapolator for the JPEG method with respect to the maximum error.
JPEG DPCM with uniform quantizer DPCM with Max’s quantizer 2.1 2.9 3.7 4.5
Kc
The significant influence of quantization on the optimization of the parameters of the adaptive extrapolator is described and experimentally confirmed. It has been shown experimentally that, despite this negative effect of quantization, the adaptive extrapolator within the DPCM compression method still has an advantage over prototypes with a small error. Also, computational experiments were carried out to research the efficiency of the DPCM compression method with an adaptive extrapolator and showed its advantage over the JPEG compression method with respect to the maximum error. Based on the obtained results, it can be concluded that the considered method is promising for image compression systems and image transmission systems.
Further research will be aimed at eliminating the need for a preliminary pass through the image when optimizing the adaptive extrapolator, which is necessary to simplify the use of the method of image compression for real-time systems, including onboard systems. The possibility of such an improvement is based on the admissibility of estimating the distribution of extrapolation errors during the actual DPCM processing. The question of the quality of such a "consistently refined" assessment requires additional investigation.
The work was funded by the Russian Science Foundation, grant No. 14-31-00014.