=Paper=
{{Paper
|id=Vol-2210/paper36
|storemode=property
|title=Use autoregressions with multiple roots of the characteristic equations to image representation and filtering
|pdfUrl=https://ceur-ws.org/Vol-2210/paper36.pdf
|volume=Vol-2210
|authors=Nikita Andriyanov,Konstantin Vasiliev
}}
==Use autoregressions with multiple roots of the characteristic equations to image representation and filtering==
https://ceur-ws.org/Vol-2210/paper36.pdf
Use autoregressions with multiple roots of the characteristic
equations to image representation and filtering
N A Andriyanov1 and K K Vasiliev1
1
Ulyanovsk State Technical University, Severny Venets str. 32, Ulyanovsk, Russia, 432027
Abstract. The article describes probabilistic properties of autoregressive models with multiple
roots of characteristic equations as well as the results of such properties investigation.
Particular attention is paid to the study of covariance functions. However, we investigate only
such models of different orders that provides equal intervals of correlation in row and column.
So the multiplicity of such models by row and column is the same. Asymptotic graphs of
covariance functions cross-sections are constructed. It is shown that the cross-sections tend to
ellipses when model orders are improving. We also describe in detail the problem of filtering
images generated by autoregressions with multiple roots. Dependences of variances of filtering
errors on the correlation parameter are obtained. The efficiency of filtering at various signal
noise ratios and various orders of models is investigated. The effectiveness and expediency of
applying autoregressions with multiple roots are shown in comparison with other
autoregressions of high orders.
1. Introduction
A lot of real images is characterized by a smooth change in brightness. It means that real images have
rather strong correlation links in some neighborhood. The known autoregressive (AR) image models
[1-3] either do not adequately describe the nature of such images even at high values of the correlation
coefficient in case of first order model.
However, the use of higher order models requires complex operations to calculate the set of
correlation parameters. Meanwhile, there are models of AR random field (RF), that generated by the
characteristic equations in image processing and representation literature [4-6,12]. Such models are
called AR with multiple roots. In this case, the application of algorithms based on such models, when
processing real signals and in various applied problems, can contribute to improving the efficiency of
solving such problems. In recent years, particular interest is caused by the processing of satellite
images [13-15].
A lot of tasks connecting with preliminary processing are known, but the important task is to
suppress noise or filter images [7,8]. The advantage of models with multiple roots is the possibility of
applying recurrent filtration procedures [9]. The article deals with the problem of image modeling on
the basis of such models as well as problems of analysis of probability properties and optimal filtering
of random fields generated by such models.
2. Autoregressions with multiple roots of characteristic equations
The widely known class of image models is the AR model of RF [1-3]. One of the main reasons for
the spread of AR models is the efficient mathematical apparatus developed for modeling random
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)
Image Processing and Earth Remote Sensing
N A Andriyanov and K K Vasiliev
sequences. The AR class of RF models can be obtained on the basis of linear stochastic difference
equations of the following form:
xi j xi j i i , (1)
jD
where X {xi , i } is modeled RF defined on the N-size grid
{i (i1 , i2 ,...,iN ) : {ik 1...M k }, k 1...N} ; { j , , j D} are coefficients of the model;
{ i , i } is a random variable with Gaussian distribution; D is a causal region of local states.
The choice of a normally distributed RF with independent components is convenient and simple
enough to describe some brightness properties of the image by the model. In this case, the RF X will
also obey the Gaussian distribution. As an example, let us consider the formation of a two-dimensional
RF using of the first order AR model known also as Habibie model:
xi , j x xi1, j y xi , j 1 x y xi1, j 1 i , j , i 1...M 1 ; j 1...M 2 , (2)
where x and y are coefficients of correlation of neighboring elements in row and column,
respectively; { i , j } is a two-dimensional field of independent Gaussian random variables with zero
mean M { i , j } 0 and variance 2 M { i2, j } (1 x2 )(1 y2 ) x2 ; x2 M {xi2, j } ; M 1 M 2 is
the size of the image that we imitate.
Due to the specifics of this way to generate the image, the process of estimating the parameters of
the AR model can be performed without special difficulties. Nevertheless, such models are not good
enough for describing real images, since they provide only small regions of local states. And this is an
important factor in modeling multi-zone images. Therefore, if it is necessary to use the AR equation,
we must increase the order of the model for the expansion of local states. So this fact entails an
inevitable growth of computational costs. Sometimes the image can be so difficult that it is required to
perform imitation in a class other than AR. Otherwise, to achieve adequate replacement of the image is
unlikely to succeed.
In addition, the weakness of such models is that they are not suitable for an adequate description of
isotropic RFs, for example, with a covariation function (CF) of the form
R(k ) R(k k12 k 22 ... k N2 ) . To overcome this drawback, one can use the characteristic equations
[10]. In work [6] models based on the generalization of one-dimensional ARs to the multidimensional
case were proposed. For example, if we take an AR with multiple roots of characteristic equations of
the second order
xi 2xi1 2 xi2 i
, (3)
then it is possible to obtain on its basis a model of a two-dimensional second-order RF
xij 2 x xi 1, j 2 y xi , j 1 4 x y xi 1, j 1
x2 xi 2, j y2 xi , j 2 2 x2 y xi 2, j 1
2 y2 x xi 1, j 2 x2 y2 xi 2, j 2 b ij ,
(4)
where b is normalizing coefficient, which makes it possible to obtain a stationary RF with a given
variance.
It can be noted that the model (4) is an eight-point model, i.e in it to form the next element of the
RF {x} we use 8 preceding elements from the neighborhood. Similarly, for the multiplicity model
(3.3), we can obtain a 15-point model, for the multiplicity model (4.4), we obtain a 24-point model.
Figure 1(a) shows an image formed from the values of RF (4) with model parameters x 0.9 and
y 0.7 . Figure 1(b) shows the implementation of an RF based on AR with multiple roots of
characteristic equations having model parameters x 0.95 and y 0.95 with multiplicity (3,3).
The size of images is 640×480 pixels.
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 274
Image Processing and Earth Remote Sensing
N A Andriyanov and K K Vasiliev
(а) multiplicity (2;2) (b) multiplicity (3;3)
Figure 1. Implementation of models having different multiplicities.
Thus, using a model with multiple roots of characteristic equations when imitating images, it is
possible to simply obtain such implementations of RF that will be close to real images. In this case, an
important property of the generated RF will be their quasi-isotropy property. A general formula for
models of different multiplicities can be written in the form:
N1 N 2
xi , j i , j i1 , j1 xi i1 , j j1
, i1 0 j1 0
(5)
where N1 and N 2 characterize the multiplicity of the model; coefficients i , j ( 0,0 0) are products of 1 1
the corresponding coefficients of one-dimensional AR along the axes x and y :
i , j xi y j1 . 1 1 1 (6)
The coefficients of one-dimensional AP (6) can be obtained from the expression
xi ( x , N1 ) (1)i 1 C Ni xi 1 1 1
1 1
(7)
y j ( y , N 2 ) (1) j 1 C Nj xj
1
1 1
2
1
n!
where Сn
m
m!(n m)! is number of combinations of n by m ; x , y are parameters of the model.
Finally, the two-dimensional model coefficient is the normalized product of the corresponding
coefficients of one-dimensional ARs along the axes x and y :
x
. (8)
x y
These coefficients can be found from the following formulas
x
1 2 2 N1 1
x
, y
1 . 2 2 N 2 1
y (9)
C C
N1 1 N 2 1
i i 2 i i 2
N1 1 x N 2 1 y
i 0 i 0
So we can use expressions (5) - (9) to show, for example, that the AR model of the first order (2)
can be represented by a model with multiple roots of multiplicity (1,1), and the eight-point model (4)
can be represented by a model with multiple roots with multiplicities (2,2).
Thus, it is possible to construct models of arbitrary multiplicity, obtaining images with slow
varying brightness properties. It should be noted that speed of properties change will depend on
parameters and orders of models.
3. Covariance functions of autoregressive random fields with multiple roots
In order to construct AR models of images with multiple roots of characteristic equations having given
statistical characteristics, we perform an analysis of the data of the characteristics of the considered
models. An important task arising in the course of statistical analysis of the mathematical model of an
RF is to determine the type of its CF.
An important property of models with multiple roots is the factorizability of CF. For example, the
RF generated by the model (1) is anisotropic, and its covariance CF, by virtue of anisotropy, is a
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 275
Image Processing and Earth Remote Sensing
N A Andriyanov and K K Vasiliev
generalization of the CF of a one-dimensional first order AR to a two-dimensional case. It can be
shown [4] that it is described by the following expression:
B(k1 , k 2 ) x2 x|k | |yk | ,
1 2
(10)
where x2 is the variance of the RF X ; x and y are parameters of the model; k1 and k 2 are the
distances between the elements of the RF X along the axes x and y.
The use of the model (4) provides an increase in the links in the AR model due to the expansion of
the range of significant preceding states and the type of CF changes. For model (4), the CF
significantly differs from the CF of the first order AR model and it takes the following form [4]:
1 x2 1 y2
B(k1 , k 2 ) x2 (1 | k |)(1 | k 2 |) x|k1| |yk 2| , (11)
1 x2 1 y2
1
where x2 is variance of the RF X ; x , y are correlation parameters of the model; k1 and k 2 are
the distances between the elements of the RF X along the axes x and y.
In order to obtain the CF of models with arbitrary orders, one can use expressions for one-
dimensional CF of AR with multiple roots of the characteristic equations
m1
2( ml 1) ,
Bx (k ) x2 g (m, l , k ) (12)
l 0 (1 2 ) 2 k l 1
(m k 1)!(2m l 2)!
where g (m, l , k ) . The variance of RF i , i 1,2,..., n can be found
l !(m 1)!(m l 1)!(m k l 1)!
by using condition Bx (0) x2
m1
2 x2 (1 2 )2m1 (Cml 1 l )2 . (13)
l 0
Correspondingly, if the AR multiplicity is (m1,m2) then the expression for the CF can be written as
the product of the RF variance and expressions of the form (12) for one-dimensional CF
m1 1
x 2( m l 1) m 1
1
y 2( m l 1)
2
Bxy (k1 , k 2 ) g (m1 , l , k1 ) g (m2 , l, k 2 ) (1 2 ) 2k l 1 .
2
2
(14)
(1 x ) 2 k l 1 l 0
x 2 1 2
l 0 y
The obtained relations completely determine the CF and the parameters of the RFs generated by the
AR with multiple roots of the characteristic equations of multiplicity (m1,m2).
For analysis, an interesting case is when the correlation coefficients of the model provide the same
correlation intervals on row and column for models of different orders, i.e.
x2
Bm1 ( x1 , y 2 , k0 , k0 ) Bm2 ( x 2 , y 2 , k0 , k0 ) ... Bmn ( xn , yn , k0 , k0 ) ... . (15)
e
For simplicity, we will assume that the multiplicity of the AR for each of the axes is the same, and
the parameter is also the same for both axes. Then we can reduce condition (15) to the following
form
Bmn ( , k 0 ) x . (16)
e
This simplification makes it possible to obtain a set of parameters that ensure the same correlation
intervals, analogous to the one-dimensional case [5]. Table 1 presents the dependences between the
correlation parameter and correlation interval k 0 .
Analysis of the data presented in Table 1 shows that in order to ensure equal correlation interval, it
is necessary to decrease the value of the parameter . Furthermore, it is possible to single out the
dependence of expression m 2(1 m )k0 . The parameter m tends to 1 if m 1 . Figure 2 shows
dependence of parameter m on correlation interval k 0 .
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 276
Image Processing and Earth Remote Sensing
N A Andriyanov and K K Vasiliev
Тable 1. Results of numerical calculations of parameters for different correlation intervals.
k0 1 10 20 50 100 500 1000 10000
m1 0,606 0,9048 0,9512 0,9672 0,9802 0,99004 0,99502 0,9994998
m2 0,338 0,7657 0,8737 0,9137 0,9472 0,9732 0,98653 0,998644
m3 0,2345 0,685 0,8257 0,8797 0,926 0,96225 0,98093 0,998077
m4 0,1795 0,6275 0,7895 0,854 0,9095 0,9536 0,97653 0,99763
Figure 2. Dependence of the correlation characteristics for models of different orders.
Analysis of the curves in Figure 2 shows that the parameter m tends to a constant value for large
k 0 . At the same time, the greater the multiplicity of the model, then the greater the parameter m .
Figure 3 shows CF of different order models providing a correlation interval k0 10 . Figure 3(a)
shows the model of multiplicity (1,1), figure 3(b) shows the model of multiplicity (2,2), Figure 3(c)
shows the model of multiplicity (3,3), figure 3(d) shows the model of multiplicity (4,4).
(a) (b) (c) (d)
Figure 3. CF of the AR RF with multiple roots of the characteristic equations.
Figure 4 shows the CF cross-sections for the models of the 1st order (solid line) and the 2nd order
(dashed line) with the correlation interval k0 15 . Figure 5 shows CF cross-sections for models of
different orders with the same value of the parameter 0.8615 .
As can be seen from Figure 4, the second order CF model has a "bell-shaped" vertex, and the
correlation links between the RF elements generated by such models are stronger within the
correlation interval.
Fig. 5 shows that the CF cross-sections tend to ellipsoids with increasing multiplicities AR.
However, with a significant increase in the orders, the CF decreases much more slowly than when
using the first and second order ARs.
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 277
Image Processing and Earth Remote Sensing
N A Andriyanov and K K Vasiliev
Figure 4. CF cross-sections with the same correlation interval.
Figure 5. CF cross-sections with the same correlation parameter.
Thus, the correlation properties of AR with multiple roots of the characteristic equations ensuring
equal correlation intervals are investigated. Dependences of the correlation parameter of such ARs on
the correlation interval are obtained.
4. Covariance functions of autoregressive random fields with multiple roots
Let us consider the case when against a background of white noise, it is necessary to perform a
filtration of an RF simulated by the AR with multiple roots of the characteristic equations
zij xij nij , (17)
where white noise has zero mathematical expectation and variance n2 .
We will use the following simple algorithm for image filtering. At the first stage, we perform line
by line filtering of all the elements in each row. Then the same procedure applies to each column.
Finally, we get the total estimation of each element as the average between the estimates for the row
and the column. So, to filter a string, you can use the following algorithm [5]. We introduce the
extended state vector:
xi ( xi xi1...xim1)T . (18)
Then the observation model will be written as:
zi Cxi ni , i 1,2,..., (19)
where C (1 0...0) .
The equation of state of a string is also can be written in the vector-matrix form:
xi xi1 i , i 1,2,..., (20)
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 278
Image Processing and Earth Remote Sensing
N A Andriyanov and K K Vasiliev
11 12 ... 1m
... 0 ; 1 j (1) Cm ; i (i 0...0) ; V M{ii }.
j 1 j j T T
where 1 0
0 1 ... 0
0 0 ... 1
After the transformations, we use the standard Kalman linear filter equations to find the optimal
estimates of the information RF [11]:
1 1
xˆi xˆ эi Pi C T 2 ( zi Cxˆ эi ), Pi Pэi ( E 2 C T CPэi ) 1 ,
n n (21)
where Pэi Pi1 V ; xˆэi xˆi1 .
T
m
At the every i-th estimation step we build the optimal forecast xˆ эi 1 j xˆi j based on previous
j 1
estimates xˆ i j , j 1,2,...,m and we find the best estimate (in the sense of the minimum variance of
the error) P11i M xi xˆi
2
1
xˆi xˆ эi P11i ( zi xˆ эi ) , (21)
n2
P
where P11i Pэ11i 1 э11i 2 . The remaining components of the vector x̂i are calculated on the
n
basis of interpolation of previous estimates taking into account the next observation z i and the mutual
covariance of estimation errors.
Figure 6 shows the variances of filtering errors obtained for models of different multiplicity and for
different ratios of signal to noise q x2 n2 . It is worth noting that the variance estimate of the filter
error was averaged over five processed images of size 150×150.
Figure 6. The filtration efficiency of two-dimensional ARs with multiple roots of characteristic
equations.
Figure 7 shows the results of the proposed algorithm for the models with multiplicities (1;1) and
(2;2). The filtering parameters are following: q 1 , k0 15 , image size is 300×300. From the top
down we show the original images, noisy images, images obtained after filtering.
An analysis of the results shows that the use of AR of higher orders, firstly, makes it possible to
obtain smoother fields, and secondly, it provides a greater filtration efficiency (on average 32% for 1-
st and 2-nd order models with q=1).
5. Conclusion
Thus, RF models based on AR with multiple roots of characteristic equations are presented. The
equality of correlation interval is the interesting property of investigated models. For such models,
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 279
Image Processing and Earth Remote Sensing
N A Andriyanov and K K Vasiliev
dependencies between correlation properties and multiplicities are found. An effective quasi-optimal
filtering algorithm for such RFs is proposed. It is shown that the use of high-order models makes it
possible to obtain gains in the case of filtering in the case of identical correlation intervals.
Figure 7. The results of filtering simulated images.
6. References
[1] Sage E and Mels J 1976 The theory of estimation and its application in communication and
management (Moscow: Communication) p 496
[2] Bulinsky A V and Shashkin A P 2008 Limit theorems for associated random fields and related
systems (Moscow: FIZMATLIT) p 480
[3] Glazov G N and Kostevich A G 2002 Modeling discrete Gaussian random fields Intelligent
Systems in Control, Design and Education 2 19-27
[4] Vasiliev K K and Krasheninnikov V R 2015 Statistical analysis of images (Ulyanovsk: UlSTU)
p 214
[5] Vasiliev K K and Andriyanov N A 2017 Analysis of autoregressions with multiple roots of
characteristic equations Radiotekhnika 6 13-17
[6] Vasiliev K K, Dragan Ya P and Kazakov V A 1995 Applied theory of random processes and
fields (Ulyanovsk: UlSTU) p 256
[7] Gonzalez R, Woods R 2005 Digital image processing (Moscow: Technosphere) p 1072
[8] Vasiliev K K, Dementiev V E and Andriyanov N A 2017 Filtration and restoration of satellite
images using doubly stochastic random fields Proceedings of the 1st International Workshop on
Radio Electronics and Information Technologies 10-20
[9] Andriyanov N A, Vasiliev K K, Dementiev V E 2017 Anomalies detection on spatially
inhomogeneous polyzonal images CEUR Workshop Proceedings 1901 10-15
[10] Vasiliev K K 2014 Autoregressions with multiple roots of characteristic equations
Radiotekhnika 11 74-78
[11] Vasiliev K K 2016 Optimal signal processing in discrete time (Moscow: Radio Engineering) p
288
[12] Andriyanov N A and Gavrilina Yu N 2018 Image Models and Segmentation Algorithms Based
on Discrete Doubly Stochastic Autoregressions with Multiple Roots of Characteristic Equations
3rd International Workshop on Radio Electronics and Information Technologies CEUR
Workshop Proceedings 2076 19-29
[13] Denisova A Yu and Sergeev V V 2015 Impulse response identification for remote sensing
images using GIS data Computer Optics 39(4) 557-563 DOI: 10.18287/0134-2452-2015-39-4-
557-563
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 280
Image Processing and Earth Remote Sensing
N A Andriyanov and K K Vasiliev
[14] Fursov V A, Goshin Ye V and Kotkov A P 2016 The hybrid CPU/GPU implementations of the
computational procedure for digital terrain models generation from satellite images Computer
Optics 40(5) 721-728 DOI: 10.18287/2412-6179-2016-40-5-721-728
[15] Afanasyev A A and Zamyatin A V 2017 Hybrid methods for automatic landscape change
detection in noisy data environment Computer Optics 41(3) 431-440 DOI: 10.18287/2412-
6179-2017-41-3-431-440
Acknowledgments
The study was supported by RFBR, project № 17-01-00179.
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 281