We propose a method of line-by-line prediction in the problem of lossy compression of images within the framework of the so-called structural approach. At the first stage, a partition of each row of the image into non-intersecting fragments with the help of recursive algorithm of peak fragmentation, the result of which is to partition each row of the image into non-intersecting fragments, the boundaries of which are points of local extrema which satisfy the specified requirements. As a result, an array of boundaries of the fragments of image lines is formed. At the second stage, the task of reducing the number of fragments on the basis of the prediction method is set. To do this, a criterion is introduced, which depends on the partitioning of lines into groups and the number of fragments in the group (based on the first line in the group the prediction error for the other lines is found; for line prediction errors the partitioning into fragments is found). To find the partition into groups and the number of fragments in each group, algorithms have been developed that deliver both global and local minimum to the selected criterion. The dynamic programming method is used for global minimization.
1. Introduction
1At carrying out of a number of technical
and natural-science researches there is a
problem of compression of images in
connection with necessity of transfer and the
subsequent storage of large volumes of the
data. So, for example, at remote sensing of the
earth the transmitted images contain millions
and tens millions pixels that demands
application of procedures of compression of
images allowing loss of information at
insignificant decrease in quality of images [
To date, there are many works [
A comparative analysis of the efficiency of
blockwise discrete orthogonal transformations
of images was carried out in [
Methods of image compression based on
contour extraction [
The works [
We propose a procedure consisting of two stages. At the first stage there is a partitioning of each line of the image into an unknown number of non-overlapping "same-type" fragments, using the so-called peak fragmentation of images. Then, based on the obtained partitions, algorithms for line-by-line prediction are developed. 2. Recursive algorithm for peak image fragmentation
The proposed recursive algorithm of peak fragmentation consists in splitting the image string into non-intersecting fragments, so that on the boundaries of fragments the corresponding pixel takes a local minimum or maximum. Such a pixel will be called a peak and denoted by pij. We will consider that a peak is pij=xij a local maximum if: xi, j−1 ≤ xij > xi, j+1 ∪ xi, j−1 < xij ≥ xi, j+1 , (2.1) and a local minimum if xi, j−1 ≥ xij < xi, j+1 ∪ xi, j−1 > xij ≤ xi, j+1 . (2.2)
Definitions (2.1), (2.2) take into account the presence of so-called "plateaus" in the image, i.e. the presence of a sequence of pixels with the same value.
The operation of the fragmentation algorithm is based on the concept of a sector. A sector is an array of pixels (xin,xi,n+1,…,xim) and two peaks piq, pis, which are one to the left and one to the right of the pixel array in question,q<n<m<s. The peaks, which when the algorithm works, will be in a certain state are considered as fragment boundaries, their value and position in the string are stored in the array of fragment boundaries.
At the beginning of the algorithm, the sector is the whole string. Then we analyze the sector, search for peaks within the sector, and divide the sector into subsectors according to the peaks found, with the peaks that are in the defined state being stored in the array of fragment boundaries.
For each subsector the sector processing procedure is repeated, new subsectors are defined, and so on. Such recursive procedure continues until further partitioning into subsectors becomes impossible. The array of fragment boundaries formed as a result of the procedure contains the required fragment boundaries.
The procedure converges in a finite number of steps, because each iteration divides the sector into several subsectors or reduces the number of pixels in the sector.
As a result of the described fragmentation algorithm, the following array of image line splits is formed: (L0 =1 < L1i < Li2 < ... < Lij < ... < Liri =M ), i = 1, 2,..., N ,
Where Lij and ri– are the boundary j-th fragment and the number of fragments for the i-th line of the image, respectively; the pixel values on the boundaries of the resulting partitions are memorized: xi,Lij , i =2,..., 1, N , j
=0,..., ri .
The compression ratio of the fragmentation N algorithm is equal to the ratio (N ⋅ M ) / ∑ 2ri . i=1
Comparison operations are used and the number of operations is proportional to 2N
Next, a line-by-line prediction procedure is performed based on the descriptions obtained at the fragmentation stage.
prediction with line-by-line
Li (ri ) =(L0 =1 < L1i < Li2 < ... < Lij < ... < Liri =M ) i-th line of the original image. Let us connect the pixels located on the borders of the fragments with straight lines and discretize the function thus constructed. As a result, we will get an array X i = (xi1, xi2 ,..., xiM ) , built for i-th line, which we will call a prediction line.
Consider the l-th line and calculate 1st group kth group sth group Xl = Xl − X i = (xl1, xl2 ,...xlj ,..., xlM ), xlj =xlj − xij ,
Let's call X l the string-error prediction of l-th string. Let us apply the fragmentation
procedure to X l . Denote by L(i,l)– the partition obtained after fragmentation, r(i,l)– the number of fragments of the partition L(i,l).
The compression coefficient that can be obtained as a result of applying the prediction procedure to the string on the l basis of the ith string, given by the corresponding partitions, is the ratio rl/r(i,l).
Consider splitting image lines into nonoverlapping groups, where the first element of the group is the prediction line, the rest of the group's lines are the lines to which the prediction is applied (an illustration of such a division is shown in the Figure 1). Let us introduce a criterion equal to the number of fragments counted for the entire image, with a fixed division of lines into groups and using the prediction method described above:
s Gk+1 −1 Q =∑r(Gk ) + ∑ r(Gk , l) , (3.1)
k =1 l=Gk +1 wheres – number of groups, Gk– number of prediction line k-th group (the first line in the group),r(Gk)=rGk – number of prediction line Gk, r(Gk,l)–number of prediction line partitioning fragments l-th for k-th group. It is required to find such a partitioning into groups that criterion (3.1) takes minimal value.
- prediction line G1=1 - G2-1 - prediction line Gk - Gk+1-1 - prediction line Gs - Gs+1-1=N Figure 1: Splitting image lines into non-intersecting groups, with the first element of the group being the prediction line, the rest of the group lines being the lines to which the prediction is applied.
Qb =(Gkk++11,...,Gss−−11 Qb / Gk ) k
=
Criterion (3.1) has the following property.
Denote by Gkk=Gk+1-1 – the number of the last
k row in the k-group. Fix the position of G k.
Then optimal position of lines G11,…,Gk-1k-1 of fragment groups 1,…,k-1 obtained by minimization (3.1) only on G11,…,Gk-1k-1 do not depend on position of lines Gk+1k+1, …, Gss of fragment groups k+1, …, s. Really, criterion (3.1) can be presented as a sum of two nonnegative values: Q=Qa+Qb, where
Qa =(G11,...,Gkk−−11 Qa / Gkk )
k Gj+1−1 =∑r(G j ) + ∑ r(G j ,l) , j=1 l=Gj +1
s Gj+1−1 =∑r(G j ) + ∑ r(G j ,l)
j = k +1 l =+1 Gj
aGr11g,...m,Gkki−−n11 Q = aGr11g,...m,Gkki−−n11 Qa
It follows from this property that if Gk – is the optimal position of the last line in the kgroup, then the optimal position of the lines G11,…,Gk-1k-1 of the fragment groups 1, …, k-1, obtained by minimizing (3.1) only on G11,…,Gk-1k-1, are also optimal.
The considered property of criterion (3.1)
allows to use the dynamic programming
procedure [
Further, a description of the corresponding procedure is given, taking into account that the number of rows in each group does not exceed the given valueNG, and, therefore, the minimum number of groups smin=M/NG. The maximum number of groups is assumed smax to be given.
Denote by R(i,j)– the number of fragments defined in the group of linesi,i+1,…,j, where the i-th line is the prediction line, the other lines are prediction liness. If i=j, then the group consists of only one line, the prediction line, R(i,j)=ri. In these notations criterion (3.1) can be written in the form:
s Q =R(Gk ∑ , Gk +1 −1) , G1 =1, Gs+1 −1 =M . (3.2) k =1 P1.s=1. Calculated by l = s,..., min [sNG, M ] , (3.3) Where v=l-1 at l≤(s-1)∙NG+1, and v=(s-1)∙NG otherwise. =
Ts (l) = argmin Qs (l) .
j= s−1,...,v
P3. If s=smax, the transition to Otherwise – to P2.
P4.
P4. We find the number of groups s*, criterion (3.2): s* = argmin Qs (M ) .
s=smin ,...,smax
P5. By a reverse move we find the optimal position of the predictor lines:
G * s =(M), T * Gs* −1 s
=(Gs* Ts* −1 ),..., G2 = T2 (G3 ) G * s =G* +1, Gs* −1 s =Gs* −1 +1,..., .
G2 =G2 +1
The proposed procedure makes it possible to find a partitioning into groups, which delivers the global minimum to criterion (3.1) under the restriction on the number of rows in the groups. As a disadvantage of the algorithm we can note a relatively large amount of calculations.
For real images, the correlation of two lines, as a rule, decreases with increasing distance between them. Taking this circumstance into account, we propose a partitioning procedure delivering a local minimum to criterion (3.1).
Let the predictor string with number Gk<M-1 (G1=1) be defined. Then we defineGk+1.
If Gk=M-1, then Gk+1=M. Otherwise, a prediction-error string is sequentially formed l=Gk+1,Gk+2,… for the l-th prediction string X l on the basis of the prediction string Gk, the partition and the number L(Gk,l) of fragmentsr(Gk,l), are determined , compared with r(Gk,l) с rl.
If for some l* line r(Gk,l*)≥λrl, (λ≤1) – algorithm parameter, allows to take into account a relatively significant decrease in the number of fragments when predicting), then further we check whether this event is random. To do this, more linesp are looked through (p=min[M-l*-1,p0], p0 - set) and for each current line the andl calculated s1 =r(Gk ,l∗ ) + r(Gk ,l∗ + 1) + ... + r(Gk ,l) and s2 =rl∗ + rl∗ +1 +,..., rl .
If for somel○ condition s1<λ∙s2, the procedure is resumed from the linel○. If for allp liness1<λ∙s2, then it is takenGk+1=l*.
Then a local optimization of the criterion is carried out. For this purpose the following iterative algorithm is proposed.
Let at the i-th iteration the partitioning of all image lines into groupssis found: G(i) =[Gk (i), Gk +1(i) −1], k =1,2,..., s; G1(i) =1.
Then the partition G(i+1) at (i+1) iteration is found as follows. Consistently for all k=2,3,…,s predictor strings except for Gk(i) and is determined Gk(i+1). For this purpose, the local minimum of the criterion in the range [max(Gk −1(i) + 1,Gk (i) − q) ≤ Gk ≤ min(Gk (i) + q,Gk +1(i) −1)] (q - a given number) is searched for. In other words, the position of the k-th predictor string is found such that on the adjacent groups and [Gk −1 (i), Gk −1] and [Gk , Gk +1 (i) −1] the number of fragments is minimal. predictor string Gk∗ is Gk (i +1) .
The procedure ends at iteration i∗ , when either the partitioning is the same as in the previous iteration ( G(i∗ ) =G(i∗ −1) ), or i∗ = i ( i – a given maximum number of iterations).
The compression coefficient resulting from the line prediction procedure is determined by the formula: The resulting M s ∑ ri / ∑ r(Gk ) + i=1 k =1
Gk+1−1 ∑ r(Gk ,l) .
l=Gk +1
The advantage of this formula is that it represents a failure analytical expression that allows you to speculatively estimate the possible values of the compression ratio.
The paper considers a method of line-byline prediction in the problem of lossy compression of images within the framework of the so-called structural approach and consisting of two stages. At the first stage (fragmentation stage), a fast recursive algorithm for peak line-by-line fragmentation of images is proposed. As a result of the algorithm's work, the partition of each line of the image into non-intersecting fragments, the boundaries of which are the points of local extremums that satisfy the specified requirements, is found. The high performance of the algorithm is achieved by the fact that in it the comparison operation is the main one.
At the second stage (the prediction stage), based on the partitioning of image lines into fragments obtained at the first stage, the task of reducing the number of fragments of the whole image based on the prediction method is set. For this purpose, a criterion dependent on the partitioning of image lines into groups and the number of fragments in the groups is introduced, and algorithms for its minimization, which deliver both global and local minimum to the selected criterion, are proposed.
We propose to use the developed algorithms for image processing, which allow preserving the structural features of the image without significant loss in the visual quality of the image.