=Paper= {{Paper |id=Vol-2076/paper-03 |storemode=property |title=Image Models and Segmentation Algorithms Based on Discrete Doubly Stochastic Autoregressions with Multiple Roots of Characteristic Equations |pdfUrl=https://ceur-ws.org/Vol-2076/paper-03.pdf |volume=Vol-2076 |authors=Nikita A. Andriyanov,Yuliya N. Gavrilina }} ==Image Models and Segmentation Algorithms Based on Discrete Doubly Stochastic Autoregressions with Multiple Roots of Characteristic Equations== https://ceur-ws.org/Vol-2076/paper-03.pdf

Image Models and Segmentation Algorithms
Based on Discrete Doubly Stochastic
Autoregressions with Multiple Roots of
Characteristic Equations

Nikita A. Andriyanov1 and Yuliya N. Gavrilina1
1
Ulyanovsk State Technical University, Severny Venets, 32, 432027, Russia
nikita-and-nov@mail.ru,
WWW home page: http://tk.ulstu.ru

Abstract. One of the most important problems of image processing is
the problem of mathematical description of objects appearing on image’s
background. There are many algorithms for current imitation of images,
but unfortunately they have some drawbacks. Often, such models are not
able to describe images that are inhomogeneous in space, or they can de-
scribe only images with slowly changing properties. Therefore, a model is
proposed for describing sharp change in the properties of an image. How-
ever, due to the use of autoregression with multiple roots, the discrete
model will also contain objects with slowly changing brightness char-
acteristics. The paper is devoted to the development of images’ models
with variable parameters, which can take a limited number of values. We
propose methods for discretizing the obtained random parameter fields
by transforming the initial fields with a continuous distribution. Further-
more, the probabilistic properties of the proposed model are analyzed.
We also describe in details methods for simulating images containing a
given number of structures and investigate segmentation algorithms for
the proposed model of images.

Keywords: image processing, doubly stochastic models, random fields,
image modeling, image analysis, covariation functions, multiple roots,
characteristic equations, image segmentation

1 Introduction

Solutions to a number of important problems in various fields of science and
technology can be achieved by using the results of processing multidimensional
data sets. Among the image processing tasks, a special place is occupied by
problems of segmentation, detecting anomalies, reconstruction, and prediction.
One of the most important sources of such data arrays are various multidimen-
sional images. Examples of such images are various information signals, digital
photographs and video sequences, remote sensing data of the Earth (RS), etc.
20

The particular urgency of solving these problems is associated with wide
dissemination of methods for recording images of various objects including mul-
tispectral (up to 10 spectral ranges) and hyperspectral (up to 300 ranges) of
recording the Earth areas. As a result of such registration, multidimensional
arrays of information are obtained. Thus, there is an increase in the volume of
information received, and although significant amounts of processed information
potentially improve the quality of satellite material processing, new methods are
necessary for qualitative and quantitative analysis of aerospace observations as
a single multidimensional aggregate.
In addition, the problem of describing images can not be regarded as solved.
Despite the variety of random fields (RF) and random processes models [1–11],
most of them do not give a satisfactory description of real images and signals
due to a number of reasons. The main problem is presence on an image of several
objects having different nature, description of which is difficult for one model.
Digital image processing algorithms [11] can be synthesized for some particular
cases of mixed image models [7, 8]. In such models, auxiliary RFs are used to
implement the basic RF, which are also a set of model parameters.
In this article, we will consider modification of a doubly stochastic model [1,
3, 4, 7–9], which allows one to obtain a smooth change in the brightness properties
of an image, as well as the possibility of using a given number of correlation levels.
Finally, we show that the use of a countable number of correlation levels allows
one to perform effective segmentation of such images.

2 Doubly stochastic model of images based on Habibi
and autoregression with multiple roots of characteristic
equations models
The main drawbacks of the doubly stochastic model based on the Habibi model
or the usual first-order autoregressive (AR) model are its anisotropy, as well as
the use of only three neighboring elements to form a new element of the RF.
Indeed, it is obvious that the Habibi model is a special case of an AR model
with multiple roots of the characteristic equations [2, 6, 10]. The multiplicity
of such a model is (1,1). In addition, increasing the multiplicity of the model
can expand the number of links between the elements. We now form a doubly
stochastic model combining AR models with multiple roots.
The process of such model synthesis is analogous to the process considered in
[1], but it has its own peculiarities and is implemented in three stages. First, the
basic RFs are created. Secondly, the values of the obtained RFs are converted
into a set of correlation parameters {ρj , j ∈ (j1 , j2 , ..., jM )}, where M is the
dimension of the image being formed. These parameters characterize the con-
nection between the current pixel of the simulated image and the neighboring
image elements. Finally, the image is formed as a model of a RF with varying
correlation parameters ρj .
For simplicity, the basic RFs are simulated using the first order AR model
as well as the doubly stochastic RF model based on the Habibi model. After
21

the formation of two basic RFs, the brightness values of one of them should
be transformed into a set of correlation parameters {ρxij , i = 1, 2, ..., M1 , j =
1, 2, ..., M2 }, and the second RF should be transformed into correlation param-
eters {ρyij , i = 1, 2, ..., M1 , j = 1, 2, ..., M2 }.
We can write AR with multiple roots of characteristic equations of the second
order in the one-dimensional case as follows:

xi = 2ρxi−1 − ρ2 xi−2 + ξi . (1)

On the basis of formula (1), we can obtain a two-dimensional model

xi,j = 2ρx xi−1,j + 2ρy xi,j−1 − 4ρx ρy xi−1,j−1

−ρ2x xi−2,j − ρ2y xi,j−2 + 2ρ2x ρy xi−2,j−1 (2)

+2ρ2y ρx xi−1,j−2 − ρ2x ρ2y xi−2,j−2 + bξi,j ,

where b is the coefficient ensuring the equality of the variance of the simulated
RF to a given value.
It should be noted that model (2) is an eight-point model, i.e. in it we
use 8 previous pixels for the formation of the next element of the RF {x}.
Similarly, for the model multiplicity (3,3), we can obtain a 15-point model, for
the model multiplicity (4,4), we obtain a model consisting of 24 points from the
neighborhood.
Making coefficients of model (2) to be random with the help of the first-
order AR model leads to the obtaining of a doubly stochastic RF model based
on Habibi and AR with multiple roots of characteristic equations models.
Figure 1 shows examples of images generated by the doubly stochastic model
of a RF (Habibi – Multiple roots models) with different mean values of the
correlation coefficients.
Thus, using the doubly stochastic AR models, one can generate images and
their sequences adequate to real multi-zone images at relatively low computa-
tional costs. This allows us to use such models for statistical analysis of the
efficiency of image processing algorithms. In this case, it is possible to achieve
a smooth change in the brightness properties of the image due to models with
multiple roots of the characteristic equations.
22

Fig. 1. Images simulated by doubly stochastic RFs based on Habibi and AR with
multiple roots of characteristic equations models

3 Discrete doubly stochastic models of images
Consider the doubly stochastic AR model on the example of the RF based on
Habibi and AR with multiple roots of characteristic equations models
xi,j = 2ρxij xi−1,j + 2ρyij xi,j−1 − 4ρxij ρyij xi−1,j−1
−ρ2xij xi−2,j − ρ2yij xi,j−2 + 2ρ2xij ρyij xi−2,j−1 (3)
+2ρ2yij ρxij xi−1,j−2 − ρ2xij ρ2yij xi−2,j−2 + bij ξi,j .
In model (3), parameters ρxij and ρyij are not constant values, but by ap-
plication of two basic RFs, their brightness values are transformed into a set of
correlation parameters in accordance with the following relationships:
ρ̃xi,j = r1x ρ̃xi−1,j + r2x ρ̃xi,j−1 − r1x r2x ρ̃xi−1,j−1 + ςxi,j ,
ρ̃yi,j = r1y ρ̃yi−1,j + r2y ρ̃yi,j−1 − r1y r2y ρ̃yi−1,j−1 + ςyi,j , (4)
ρxij = ρ̃xi,j + mρx , ρyij = ρ̃yi,j + mρy ,
23

where ςxi,j and ςyi,j are two-dimensional RF of independent Gaussian random
2 2 2
variables with zero means and variances M {ςxi,j } = σςx , σςx = σρ2x 1 − r1x
2 2
1 − r2x ,
2 2
= σρ2y 1 − r1y
2 2
2
, σρx = M {ρ2xij } and σρ2y = M {ρ2yij },

M {ςyi,j } = σςy 1 − r2y
mρx and mρy define average correlation in row and column.

The correlation coefficients obtained from expression (4) are continuous random
variables and usually take different values at each point. To make the correlation co-
efficients of the basic RF (3) to take a countable number of values, it is necessary to
discretize expression (4) as follows:

ρxij L
ρ∗xij = round( ), (5)
max{ρxij } − min{ρxij }

where round() is the rounding operator, L is the number of sampling levels, max and
min are respectively the maximum and minimum values of the RF.

Then it is necessary to convert the obtained discrete RF (5) so that its minimum
value corresponds to the minimum value of the continuous RF, and the analogous
equality for the maximum values would be satisfied by using expression

(ρ∗xij − min{ρ∗xij })(max{ρxij } − min{ρxij })
ρ∗∗
xij = min{ρxij } + . (6)
max{ρ∗xij } − min{ρ∗xij }

Similar actions can be performed for the coefficients by column.

Figure 2 represents realization of model (3) and discrete model (3) taking into
account the correlation coefficients (4) and (6) with the following parameters: σx2 = 1,
mρx = 0.85, σρ2x = 0.0016, mρy = 0.9, σρ2y = 0.0016, r1x = r2x = 0.95, r1y = r2y = 0.8,
m = n = 320. Figure 2a corresponds to continuous RF; Figure 2b corresponds to RF
with L = 3; Figure 2c corresponds to RF with L = 6.

Figure 3 shows the cross sections of the covariance functions of the obtained models
in a row.

Thus, by varying the number of discretization levels L, it is possible even for iden-
tical model parameters to obtain its various implementations. We also can see that on
the graphs of Figure 3 the covariance relationships of discrete models decrease more
slowly than those in continuous ones.
24

Fig. 2. Images simulated by doubly stochastic model. From top to bottom: basic RF,
RF of correlation coefficients in a row, RF of correlation coefficients in a column.

Fig. 3. Covariance functions of doubly stochastic RF based on AR with multiple roots
of characteristic equations
25

4 Segmentation of images with varying correlation
properties
Now consider the segmentation algorithm for the generated images in the case where
the number of correlation levels is two. To select homogeneous areas, you need to build
a histogram of the image. To do this, all the values of the RF {ρxij } are written in the
vector of brightness values. It should be noted that all the values have before passed
the equalization procedure, and we also taking into account the average additive. So,
the result vector is written as follows:

L(k) = ρ̃xijeq , i = 1, 2, ..., M1 , j = 1, 2, ..., M2 , 1, 2, ..., M1 xM2 . (7)

Let us find the number of elements of the vector obtained after the transformation (7),
which corresponds to each gradation of brightness. We will use a histogram to find the
brightness value between its peaks. Since at this formation the histogram should have
two peaks, the threshold value of brightness can be found by the formula
Lmax1 + Lmax2
Lthr = , (8)
2
where Lmax1 and Lmax2 are the brightness values of the first and second maximum of
the histogram.
Let us transform the equalized image {ρ̃xijeq } with 256 gradations of brightness
into an image {Rxij } with 2 gradations of brightness. So the image {Rxij } is binary
image, which is obtained by the formula

Rxij = 0, if {ρ̃xijeq } < Lthr , Rxij = 255, else. (9)

Expression (9) in this case is a segmented image. Furthermore, the proportion of cor-
rectly assigned to the first or second area pixels is considered. This proportion is based
on the assumption that homogeneous zones are segmented on the binary image of the
basic RF. Then the percentage efficiency of segmentation can be found after comparing
the resulting image with the segmentation of the basic image.
Figure 4 shows histogram of an image simulated by doubly stochastic model with
possible parameter values ρx1 = ρy1 = 0.8 and ρx2 = ρy2 = 0.95.

Fig. 4. Histogram of the simulated image

Note that in this case we have the threshold value Lthr = 135.
26

It is clear that the best segmentation will be provided by combinational processing
of correlation parameters by row and column.
Figure 5 shows the result of the segmentation algorithm using the histogram: Figure
5a corresponds to basic RF; Figure 5b corresponds to nonhomogeneous image with
homogeneous regions; Figure 5c corresponds to binarization of the basic RF; Figure 5d
corresponds to segmentation of the nonhomogeneous image.

Fig. 5. Segmentation of simulated images

The percentage of the correspondence between Figure 5c and Figure 5d is quite
large, namely, 85.7%. Analysis of Figure 5 shows that it is possible to increase segmen-
tation efficiency if small objects are included in a larger neighboring area.
Nevertheless, the result obtained for simulated images allows us to reasonably hope
that in the case of applying more complex segmentation procedures in processing the
correlation parameter field, the segmentation algorithm found can be applied to real
images. Indeed, Figure 6 shows the results of 2-level segmentation (binarization) of a
satellite image by applying a combination of the proposed algorithm and the ISODATA
algorithm to the field of correlation parameters. In this case, Figure 6a is the original
image; Figure 6b shows the correlation parameter fields for the original image; Figure
6c shows the results of segmentation by correlation parameters jointly ISODATA al-
27

gorithm; and Figure 6d shows the results of applying the ISODATA algorithm to the
original image.

Fig. 6. Segmentation of satellite images

The gain for the presented case on segmentation accuracy was about 6%. However,
it is worth to note that the task of assessing the accuracy of segmentation when pro-
cessing real images is significantly complicated, since there is no predetermined correct
version, and most often, we have to use expert estimates.

5 Conclusion
Doubly stochastic models of images based on the AR with multiple roots of charac-
teristic equations are considered. The transition to the discrete case is carried out.
Probabilistic properties of the proposed models are analyzed. An algorithm for image
segmentation by correlation parameters is described. Gains are obtained when process-
ing images consisting of two structures. The gains are about of 6 –10% in comparison
with segmentation by the ISODATA algorithm.

Acknowledgements. The study was supported by RFBR, project 17-01-00179 A.

References
1. Vasiliev, K. K., Andriyanov, N. A.: Synthesis and analysis of doubly stochastic
models of images. REIT 2017. Proceedings of 2nd International Workshop on Ra-
dio Electronics and Information Technologies. CEUR Workshop Proceedings. Vol.
2005, 145–154 (2017)
2. Vasiliev, K. K., Andriyanov, N. A.: Analysis of autoregressions with multiple roots
of characteristic equations. Radiotekhnika. 6, 13–17. (2017)
3. Xin Xu, Deren Li, Hong Sun: Doubly stochastic MRF-based segmentation of SAR
images. Proceedings of SPIE 5095. Algorithms for Synthetic Aperture Radar Im-
agery X. 8–16 (2003)
4. Xin Xu, Hong Sun: Multiscale SAR image segmentation using a double Markov
random field model. Proceedings Seventh International Symposium on Signal Pro-
cessing and Its Applications. Vol. 1, 6–12 (2003)
28

5. Aykroyd, R. G.: Bayesian estimation for homogeneous and inhomogeneous Gaus-
sian random fields. IEEE Transactions on Pattern Analysis and Machine Intelli-
gence. Vol. 20, Iss. 5, 533–539 (1998)
6. Buynova, S. N.: Checking the presence of a single root in the autoregression pro-
cess by the correlation method. St. Petersburg (2010) http://www.statmod.ru/
_diploma/2010/2_01_buynova.pdf
7. Vasil’ev, K. K., Dement’ev, V. E., Andriyanov, N. A.: Application of mixed models
for solving the problem on restoring and estimating image parameters. Pattern
Recognition and Image Analysis. Vol. 26(1), 240–247 (2016)
8. Vasiliev, K. K., Dementiev, V. E., Andriyanov, N. A.: Filtration and restoration
of satellite images using doubly stochastic random fields. REIT 2017. Proceedings
of 1st International Workshop on Radio Electronics and Information Technologies.
CEUR Workshop Proceedings. Vol. 1814, 10–20 (2017)
9. Andriyanov, N. A., Vasiliev, K. K., Dementiev, V. E.: Anomalies detection on
spatially inhomogeneous polyzonal images. CEUR Workshop Proceedings. Volume
1901, 2017 International Conference Information Technology and Nanotechnology.
Session Image Processing, Geoinformation Technology and Information Security,
IPGTIS-ITNT 2017; Samara; Russian Federation, 10–15 (2017)
10. Vasiliev, K. K, Gavrilina, Yu. N., Andriyanov, N. A.: Efficiency of filtering an au-
toregressive model with multiple roots of characteristic equations. Modern prob-
lems of design, production and operation of radio engineering systems: a collection
of scientific papers. Tenth edition. UlSTU, Ulyanovsk. 130–133 (2016)
11. Gonzalez, R., Woods, R. Digital image processing. Edition 3rd, revised and en-
larged. Technosphere, Moscow. 1104 (2012)