When describing a real image using a mathematical model, the problem of model parameters identification is of importance. In this case the identification itself is easier to perform when a particular type of model is known. In other words, if there is a number of models characterized by different properties, then if there is a correspondence with the type of suitable images, then the model to be used can be determined in advance. Therefore, in this paper, we do not consider the criteria for model selection, but perform the identification of parameters for autoregressive models, including those with multiple roots of characteristic equations. This is due to the fact that the effectiveness of identification is verified by the images generated by this model. However, even using this approach where the model is known, one must first determine the order of the model. In this regard, on the basis of YuleWalker equations, an algorithm for determining the order of the model is investigated, and the optimal parameters of the model are also found. In this case the proposed algorithm can be used when processing real images.
Mathematical modeling is used in many areas of science and technology, including image processing. In particular, methods focused on the description of images using models of random fields (RF), allow the development of algorithms for parameter estimation, filtering, detection of anomalies in the background of images and analyze them for a large number of simulated images.
There exist many images that are characterized by a smooth change in brightness [1,2]. Usually such images have a slowly decreasing correlation function (CF) in a certain given neighborhood. The first-order autoregressive (AR) image models [3,4] do not provide a strong correlation between pixels, since its CF decreases exponentially. Meanwhile, separable RFs that can be generated by onedimensional autoregression with multiple roots of characteristic equations [5-6] are known. An important feature of ARs with multiple roots is their considerable simplicity compared to arbitrary high-order ARs. Also doubly stochastic models are used to describe real images [7-10]. However, if the structure of the described image is not so complicated, then it is better to use simpler models. This is due to the fact that the computational complexity of a double-stochastic model is much higher than, for example, a model with multiple roots, for which the AR of any order can be described using a single parameter.
At the same time, when describing images, for example, satellite images using mathematical models, it is necessary to identify parameters of the model. At the same time, the model should be selected in such a way that a compromise is found between its complexity and the similarity of the simulated image with the real one. The paper discusses the solution of the problem of the parameters identification for AR models with multiple roots of characteristic equations, which, owing to the separability of the CF, can significantly simplify this task. It should be noted that the application of the parameter identification approach based on Yule-Walker equations to determining the order and correlation parameters of AR models with multiple roots has a scientific novelty.
At present, the identification task for AR processes, the moving average (MA) and autoregression with moving average model (ARMA) by single-channel observations without noise is the most wellstudied. Especially many methods have been developed for estimating the parameters of such processes. The estimation methods are based either on the direct use of observations, or on the initial calculation of the sample statistical characteristics (autocorrelations, spectral densities) from these observations, and then using them to determine parameter estimates. The first group of methods includes the least squares method (LSM) for the AR process [10,11], the maximum likelihood method (ML) for the AR, MA, and ARMA processes, and various types and modifications of these methods [12-14]. The second group is the Yule-Walker method for the AR process [13], the Box and Jenkins correlation methods for the ARMA, MA [13] processes, the Lindberger method for the AR, MA, and ARMA processes [15], the Durbin method for the MA process [16] , the Cleveland inverse autocorrelation method for the ARMA process [17] and other methods [18]. In both groups, there are methods in which parameter estimates are calculated by linear algorithms by solving a certain system of linear equations for example, LSM and Yule-Walker method for the AR process, as well as methods that use nonlinear methods for calculating estimates, which are reduced to numerical minimization algorithms for a certain function of the parameters, for example, the ML method and the Lindberger method for the APMA processes. The methods for determining the class of processes that can be AR, MA, and ARMA are much less developed [19]. In the work of Kitler and Whitehead [20], the problem of class determination is reduced to the problem of determining the order of the ARMA process. Therefore, the solution of the determination order and class of the model task is of interest. In the simplest case, such a task is reduced to a problem when it is necessary to determine its order using the selected model of AR. So optimal identification is very important for satellite image processing [21,22].
Using AR models with multiple roots of characteristic equations, it is possible to obtain realizations of RFs that will be close in their properties to real images. In this case an important property of the generated RF will be its quasi-isotropy. The general formula for models of different multiplicities can be written as follows
N1 N2 xi, j = βξ i, j − ∑ ∑α i1, j1 xi−i1, j− j1 , i1=0 j1=0 β =
σσ ξx β xβ y , where N1 and N 2 characterize the multiplicity of the model; coefficients α i1, j1 (α 0,0 = 0) are the products of the corresponding coefficients of one-dimensional AR along the axes x and y α i1, j1 = α xi1α yj1 .
The coefficients of one-dimensional AR (
n! α xi1 (ρ x , N1 ) = (−1)i1+1 C Ni11 ρ xi1 ,α yj1 (ρ y , N 2 ) = (−1) j1+1 C Nj12 ρ yj1 , (
When identifying parameters, let’s approximate the CF of the initial data by the most appropriate model. In order to obtain the CF models of arbitrary orders, it is necessary to use expressions for onedimensional CF of AR with multiple roots of characteristic equations [22]
m−1 ρ 2(m−l−1)
Bx (k ) = σ x2 ∑ g(m, l, k ) , (
l=0 (1− ρ 2 ) 2k −l−1 (m + k − 1)!(2m − l − 2)! where g(m,l, k ) = l!(m − 1)!(m − l − 1)!(m + k − l − 1)! . The variance of independent random values ξ i , i = 1, 2,..., n , can be found for a given variance of simulated RF Bx (0) = σ 2 x σ ξ2 = σ x2 (1 − ρ 2 ) 2m−1
. m−1 ∑ (C ml−1ρ l )2 l=0
Thus, for spatial AR equation with characteristic roots of multiplicities (m1,m2) the expression for CF can be written as
Bxy (k1 , k 2 ) = σ x2 m∑1−1 g (m1 , l, k1 ) l=0 ρ 2(m1 −l−1) m2 −1
x ∑ g (m2 , l, k 2 ) (1 − ρ x 2 ) 2k1 −l−1 l=0 ρ 2(m2 −l−1)
y (1 − ρ y 2 ) 2k2 −l−1 .
However, in the case of a model with multiple roots it is possible to separately carry out the
identification of parameters by row and column, using formula (
To solve the problem of identification, we will use AR models of arbitrary order
xi = ρ 1 xi−1 + ρ 2 xi−2 + ... + ρ m xi−m + ξ i , i = 1,2,..., M , where m is order of AR model.
Choosing parameters ρ 1 , ρ 2 ,..., ρ m it is possible to get a Gaussian RF {xi }, i = 1,2,..., M
with a
variety of correlation properties. In this case to write values of CF you can use the following
expression
(
Rx (k ) = ρ 1Rx (k − 1) + ρ 2 Rx (k − 2) + ... + ρ m Rx (k − m) , k > 0 .
CF of models with multiple roots for different roots zν , ν = 1, 2,..., m, of characteristic equations described by expression
z m − ρ 1 z m−1 − ρ 2 z m−2 − ... − ρ m = 0 , under the condition of stability zν < 1 , v = 1,2,..., m , are represented by the following sum
Rx (k ) = A1 z1k + A2 z2k + ... + Am zmk . (
Substitution in (
The solution of this system allows you to find the coefficients ρ1 , ρ 2 ,..., ρ m of equation (
We will perform parameter identification for models with multiple roots of characteristic equations of 1-4th orders. In this case the order can be identified if we take into account only the coefficients that make some contribution to the model. Table 1 presents the results of identification of the correlation parameters for the values of CF of AR with multiple roots. By rows, the actual multiplicity is presented, by columns — estimated parameters are presented. We assume ρ = 0.8 for models of all orders. In the left column – the values found, in the right column - the real values. m=1 m=2 m=3 m=4
Analysis of table 1 shows that the values of the correlation coefficients are estimated the more accurately, the higher the multiplicity is. If the estimated multiplicity exceeds the real value, then the additional coefficients are either 0 or very close to it. Thus, the process of the model order identification can be carried out first for some large multiplicity. If the resulting coefficients do not have zero coefficients, then the calculation should be carried out at a higher multiplicity until we get zero coefficients. If there are zero coefficients, the order corresponds to the number of the last significant coefficient.
A similar relationship between correlation coefficients and CF values can also be obtained for the
two-dimensional case, i.e. images. The relation for CF values corresponding to expression (
R(k1 , k2 ) = ρ 10 R(k1 − 1, k2 ) + ρ 01R(k1 , k2 − 1) + ρ 11R(k1 − 1, k2 − 1), k1 > 0, k2 > 0. (
l=0 k =0 where { xi, j } is RF implementation or simulated image; ρ kl are correlation coefficients for elements lagging behind each other along the axes i and j by k and l pixels respectively; {ξ i, j } is twodimensional RF of independent Gaussian random variables with zero mean M {ξ i, j } = 0 and variance mj mi M {ξ i2, j } = σ ξ2 = [1 − ∑ ∑ ρ kl R(k , l) + ρ 00 R(0,0)]σ x2 ; mi and mj are orders of the model; M1 and M2 l=0 k=0 are the image size.
The number of components of the model, taking into account the random increment will be equal
to (mi + 1) × (m j + 1) . Using formulas (
m j mi
R(k1 , k2 ) = ∑ ∑ ρ kl R(k1 − k , k2 − l) − ρ 00 R(k1 , k2 ) , k1 > 0, k 2 > 0 . (
The expression (
Let us identify the parameters of the model based on the proximity of the CF model and the given
data. In the first case, we will consider the AR with a separable CF and separately calculate the
coefficients for the row and column. In the second case, we use equations based on the expression
(
Let there be a real image represented as I (i, j),i ∈1,..., M 1 , j ∈1,..., M 2 . Then its CF can be expressed as follows
RI (k1 , k 2 ) =
1 M1 M 2 σ 2 ∑ ∑ (I (i, j) − mI )(I (i − k1 , j − k 2 ) − mI ) ,
I i=k1 +1 j=k2 +1
(
Figure 1a and Figure 1b show the image to be investigated and its CF, respectively. Identification is performed for the 4th order AR model.
- for RF having separable ρ10 = 1.098;ρ 20 = −0.39;ρ 30 = 0.364;ρ 40 = −0.082;
ρ 01 = 0.828; ρ 02 = 0.0047; ρ 03 = 0.111; ρ 04 = 0.038 ; ε = (Rˆ − R)2 = 0.387.
- for RF having non-separable ρ10 = 0.998;ρ 20 = −0.514;ρ 30 = 0.43;ρ 40 = −0.133; ρ 02 = −0.174; ρ 12 = 0.309; ρ 22 = −0.265; ρ 32 = 0.217; ρ 42 = −0.097; ρ 03 = −0.048; ρ 13 = 0.186; ρ 23 = −0.205;
ρ 01 = 0.185;ρ11 = 0.152;ρ 21 = −0.194,ρ 31 = 0.142;ρ 41 = −0.092; ρ 33 = 0.153,ρ 43 = −0.079;ρ 04 = −0.122;ρ14 = 0.267;ρ 24 = −0.242;ρ 34 = 0.22;ρ 44 = −0.102; ε = (Rˆ − R)2 = 0.014 .
a) b) Figure 1. The image (a) for which the adjustment of the parameters is carried out and its CF (b).
Analysis of the obtained values of the error variances shows that the use of the model with an nonseparable CF provides a greater proximity between the modeled and the real CF. This is explained by the fact that for this model 24 correlation parameters were calculated, while for a model with a separable CF only 8 parameters. At the same time, a sufficient proximity of the CF is provided, especially in the neighborhood of zero. Therefore, it is advisable to use such models to reduce computational costs. Figure 2 shows the CF cross sections for the original image (presented by solid line), as well as for the RF with separable CF (presented by dash-dotted line) and the RF with nonseparable CF (presented by dashed line).
Analysis of the presented curves shows that as k increases the discrepancy between the real and simulated CF also increases. It is possible to achieve greater proximity by increasing the order of the AR, but this leads to higher computational costs. Similar research was conducted with a sample of 100 images. Analysis of the results shows that the use of non-separable CF models provides the proximity of CF to 10-15 times more than the use of separable CF models in 85% of cases. However, in 15% of cases separable models were successfully used to describe the real image, which made it possible to significantly reduce computational costs of image processing.
However, if a model with multiple roots is used, it is sufficient to calculate only the first correlation
coefficient, then calculate the correlation parameter using the first correlation coefficient and use
correlation parameter to find the remaining correlation coefficients according to the expression (
For example, if ρ 1 = 3.6 and N=4 then it is easy to calculate parameter of the AR with multiple roots of characteristic equations from the following equation
3.6 = (−1)1+1 С41ρ 1 , → ρ = 0.9 . (
So it is quite a simple task to perform identification of parameters in this case.
In this paper a brief overview of the methods used to identify the parameters of the AR processes is presented. Models with multiple roots and a method for determining the order of the model based on the Yule-Walker equations are considered. It is shown that the proposed method enables to determine the order of the model for simulated images with sufficient accuracy. A comparative analysis of the identification of the parameters of models with a separable and non-separable CF of the real image is performed. The analysis shows that models with a non-separable CF require more computational costs at the same order of a model, however, they provide greater proximity of the CF in comparison with separable CF models. The identification results may be used to describe real satellite images and for the processing of such images.