Filtration and Restoration of Satellite Images Using Doubly Stochastic Random Fields Konstantin K. Vasiliev1 , Vitaliy E. Dementiev1 , and Nikita A. Andriyanov1 Ulyanovsk State Technical University, Ulyanovsk, Russia vkk@ulstu.ru,dve@ulntc.ru,nikita-and-nov@mail.ru Abstract. The paper is devoted to filtering algorithms of satellite im- ages. Inadvisability of applying the simplest mathematical models of ran- dom fields with non-uniform filtering material is shown. We consider the comparative analysis of effectiveness of the filtering and calculate the gain of the proposed algorithm. In addition, we have sufficient by ad- equate enough satellite image restore when applying doubly stochastic models. Restoration algorithm that can easily be implemented from dif- ferent positions of the image is described. Dispersion values for recovery errors were found under using different models. We also have received the gain in image restoration by providing adequate description of satellite images unlike in application of autoregression (AR) models. Keywords: Image processing, image filtration, Kalman filter, param- eters estimation, image restoration, doubly stochastic models, random fields 1 Introduction In many cases, transfer of multidimensional data with errors shadowing images or badly damaged them by noise arises the problem of recovering the missing fragments of images [1–3, 8] or filtering [4–6]. The white noise filtering is possible in the case of using the well-proven Kalman filter, which allows one of the reasonably accurate estimation without requiring significant computing expenditures. One of the methods of restoration, essentially is in an image replacement by some model in the damaged area. However, in real-world images the damaged area can contain any objects, description of which is possible using inhomoge- neous models. Therefore, to use this method, we must find adequate model. Most of the existing models [2, 7] are unable to provide adequate replacement of dam- aged areas due to some reasons. However, we can use the combination-mixed models of the images. Quite a common option of such models is doubly stochastic ones [3, 5, 9] or models, which vary its parameters from pixel to pixel. Another important feature of the filtering and restoration results is the need for their use in solving problems of signal detection in images [10, 11]. 11 Thus, the purpose of this work is to improve effectiveness of the image filtering and restoration by applying models of images with varying parameters. Note that a comparison will be made on the criterion of minimum error dispersion. 2 Images filtration Although signal detection is very important, effectiveness of the work of all algorithms significantly depends on the source material, and usually images are distorted versions of the raw data. So, received images may have different shifts, shading, as well as, be quite noisy nuisance. Moreover, strong interference leads to almost total loss of information at the site of exposure. Therefore, the most important stage of preprocessing is filtration. We consider the following doubly stochastic model of random fields: xi,j = ρxi,j xi−1,j + ρyi,j xi,j−1 − ρxi,j ρyi,j xi−1,j−1 + ξi,j , (1) where ρxi,j = ρ̃xi,j + mρx are the row correlation parameters field; ρyi,j = ρ̃yi,j + mρy is the column correlation parameters field; mρx and mρy are the average values of correlation parameters random field for row and column respectively; ξi,j is the random field of independent Gaussian random values having  average  2 M {ξi,j } = mξi,j = 0 and dispersion M {ξi,j } = σξ2i,j = σx2 1 − ρ2xi,j 1 − ρ2yi,j ; σx2 is the base random field dispersion. The random fields that describe changes in the correlation coefficients are described as follows: ρ̃xi,j = r1x ρ̃xi−1,j + r2x ρ̃xi,j−1 − r1x r2x ρ̃xi−1,j−1 + ςxi,j , (2) ρ̃yi,j = r1y ρ̃yi−1,j + r2y ρ̃yi,j−1 − r1y r2y ρ̃yi−1,j−1 + ςyi,j , where r1x , r2x , r1y , r2y are the constant correlation parameters of the internal random fields; ςxi,j and ςyi,j are the independent Gaussian random values with 2 2 zero average and dispersions M {ςxi,j } = σςx = σρ2x 1 − r1x 2 2 1 − r2x 2 , M {ςyi,j }= 2 2 2  2  2 2 σςy = σρy 1 − r1y 1 − r2y ; σρx and σρy define the dispersions of the basic ran- dom fields of correlation parameters for the row and column, respectively. Thus, in order to solve the problem of parameter estimation, it is necessary to estimate random fields ρxi,j and ρyi,j in model (1). It should be noted that for the case of doubly stochastic models the important property is the ability to apply recurring evaluation procedure [2] that would only slightly increase the computational expenditures. Suppose that the input signal of a monitoring system at the entrance is the sum of the useful signal (1) and additive white Gaussian noise {ni,j } with average mn = 0 and dispersion σn2 zi,j = xi,j + ni,j . (3) We shall use the vector nonlinear Kalman filter to make the filtering process of the flat image. Therefore, we must obtain a vector of the image line items that can be written as follows: 12 xi = (xi1 , xi2 , . . . , xiN ) . (4) In this case, we write a generalized expression model for the flat image in accordance in the following form: xi = diag (ρxi ) xi−1 + ϑ (ρxi , ρyi ) ξi , ρxi = r1x ρxi−1 + ϑρx ξxi , (5) ρyi = r1y ρyi−1 + ϑρy ξyi ,   where diag (ρxi ) is the diagonal matrix with elements ρxi1 , ρxi2 , . . . , ρxiN . Finally, expression for the process of line-by-line estimation is written as follows: ∂ΦT x̂pi = x̂epi + Pi (z i − x̂epi ) . (6) ∂xpi It should be noted that application of the nonlinear vector Kalman filter is possible if the signal model is known. Thus, to make signal model known, it is necessary to have information about coefficients r1x , r2x , r1y , and r2y and, in addition, the statistical characteristics of the model such as mρx , mρy , and 2 2 σρx , σρy , σx2 . If the receiving part has no a priori information tagged with pa- rameters, we must perform a preliminary assessment, for which it is proposed to use the algorithm for pseudogradient search [3, 7]. In addition to filter (6), we will explore a number of filtering algorithms both for AR models and doubly stochastic ones. 1) Vector Kalman filter for the AR model with ρxi,j =const and ρyi,j =const. 2) Wiener filter for AR model with the covariance function B (l, k) = σx2 m|l| |k| ρx mρy . 3) Vector Kalman filter for the AR model with reverse swing (interpolation). 4) Vector Kalman filter for the doubly stochastic model with reverse swing (interpolation), for which   x̂i,j  ρ̂xi,j  = Φ (xe , ρxe , ρye , Vn ) . ρ̂yi,j Figure 1 presents filtering error dispersion dependencies on noise dispersion. We can see that if the image is close to identical and similar only in certain segments, we have effective filtration by only the fourth algorithm. As for the gain (Figure 2), note that the maximum gain is achieved at low values of the noise dispersion, and then we get the stabilization of the gains. We note that for a single noise dispersion, algorithm of the Kalman filter with vector interpolation works almost 2 times more precisely than the Kalman and Wiener filters with interpolation configured for the AR model. Furthermore, the gain compared to Kalman without interpolation is much larger. 13 Fig. 1. Filtration efficiency of the heterogeneous image. Fig. 2. Gain when heterogeneous images are filtered. 14 Fig. 3. Filtration efficiency of image with changes in brightness. Fig. 4. Gain when images with brightness variations are filtered. 15 Obviously, the heterogeneous image filtering with variations in brightness (Figure 3) can not be used without analysis of correlation parameters. So, here, there is the fourth algorithm that is also applied more accurately. However, in terms of gains (Figure 4), such algorithm provides smaller indicators since the main image has the heterogeneity of the sharp variations in brightness. Thus, filtering algorithm based on the doubly stochastic model provides the best results for real images. 3 Images restoration Consider restoring the square area on the image using a model with variable parameters. Let the brightness values of the image representing the random field be {Zi,j ;i = 1, 2,. . . , M1 ;j = 1, 2,. . . , M2 }. There is the damaged area starting at the point (i0 , j0 ) of the c × c-dimension. Denote this area as D. We introduce the following restoration model [12]    Zi,j , if (i,j)∈D /  Xi,j = ρ1i,j (Xi−1,j − Xi,j ) + ρ2i,j (Xi,j−1 − Xi,j ) − , (7) −ρ1i,j ρ2i,j (Xi−1,j−1 − Xi,j ) + Xi,j + ξi,j , if (i,j)∈D   where ρ1i,j , ρ2i,j are the estimations of the correlation coefficients for row and column at the point (i, j); Xi,j is the estimation of the average value at the point is the Gaussian random field with average M {ξi,j } = 0 and dispersion (i, j); ξi,j q 2  2 σξ = σi,j 1 − ρ21i,j )(1 − ρ22i,j , where σi,j is the estimation of the dispersion at the point (i, j). It is advisable to assess parameters in the sliding window excluding the points that lay in the damaged area. Model (7) is a Habibie one with variable parameters in the area D. For the window with N × N -size, estimates are determined by the formulas P N2 P N2 Xi,j = N12 u=− N q=− N Zi+u,j+q 2 2 2 1 P N2 P N2 2 σi,j = N 2 u=− N q=− N (Zi+u,j+q − Xi,j ) 2 P N2 2 P N2 (8) ρ1i,j = σ2 1N 2 u=− N q=− N (Zi+u,j+q − Xi,j ) (Zi+u−1,j+q − Xi,j ) i,j 2 2 N N ρ2i,j = σ2 1N 2 u=− P P 2 N 2 q=− N (Zi+u,j+q − Xi,j ) (Zi+u,j+q−1 − Xi,j ) i,j 2 2 To restore the damaged area, we shall make an assessment in neighbourhood of the area D. In addition, to ensure greater heterogeneity, we divide area D into sub-areas, onto each of which we shall expand the model with the estimated parameters (8). Evaluation system (8) gives estimates based on the motion of the window from left to right and from top to bottom, i.e., the model unfolds from the top left corner of the area D. You can get similar expressions for motion of the 16 window from other corners. It is clear that the estimates for different starting points of evaluation will vary. This is due to the fact that the basic values of the model implementation will depend on intact neighborhood, and it, in the turn, is determined by its position on the image. Thus, the nearest surroundings will change when the starting point for deployment model changes. To assess the performance of the proposed algorithm, we shall implement restoration method on the different images. When we do this we compare restora- tion (7) with the restoration by the model of Habibie that can be written:    Zi,j , if (i,j)∈D /  Xi,j = ρˆ1 (Xi−1,j − X) + ρˆ2 (Xi,j−1 − X) − , (9) −ρˆ1 ρˆ2 (Xi−1,j−1 − X) + X + ξi,j , if (i,j)∈D   where ρˆ1 , ρˆ2 are the estimation of correlation parameters for the row and col- umn; X is the average value estimation; ξi,j q is the Gaussian random field with 2 2  average M {ξi,j } = 0 and dispersion σξ = σ 1 − ρˆ1 )(1 − ρˆ2 , where σ 2 is the 2 estimation of the dispersion. So, the restoration algorithm with the Habibie model (9) requires only one assessment of the image parameters. Figures 5-7 show the different damaged images and the result of their recov- ery: a) damaged image, b) restore from the upper left corner, c) restore from a right corner, d) restore from the left bottom corner, e) restore from a right corner, f) restore based on the Habibie model from the upper-left corner. Fig. 5. Restoration of the area of the image on the border of two dissimilar surfaces. 17 Dispersions of the restoration error (Figure 5) are the following: b: 0.046, c: 0.060, d: 0.045, e: 0.043, f: 0.335. Fig. 6. Restoration of the image area close to uniform. Dispersions of the restoration error (Figure 6) are the following: b: 0.031, c: 0.040, d: 0.035, e: 0.034, f: 0.043. Analysis of the errors for restoration in Figure 6 shows that in the case of a homogeneous area of the image, results in the implementation of algorithms are close enough regardless the initial point. However, slight variation of the dispersion values of the error may be due to the fact that the implementation of a model uses a random field. Consequently, the value of the restored pixel brightness is accidental. It also should be noted that the image selected in Fig- ure 6 consists the inhomogeneities. Such structure also affected the calculation of variance of the restoration error. However, the restoration results in Figure 6b — e are significantly better than restoration results in Figure 6f. Firstly, it is due to the fact that the model with variable parameters is better suited for the description of the original image. Secondly, implementation of the Habibie model leads to using the constant correlation coefficients, although the connection be- tween the real image pixel does not correspond to this description. Finally, we consider the restoration of the image area when the neighborhood is different from different sides, i.e., there are either diverse objects at the corners of the damaged section or there is a difference in the brightness values. 18 Fig. 7. Restoration of the image area limited by different structures. Dispersions of the restoration error (Figure 7) are the following: b: 0.005, c: 0.003, d: 0.006, e: 0.008, f: 0.015. An error dispersion investigation for the Figure 7 revealed that when the damaged area is bounded on different sides of the pixels with different brightness, it is a very important factor what side is basic for restoration. Indeed, restoration from the right upper corner of the neighborhood is based on the dark area closest to the brightness of the damaged portion. Further, the order of similarity of the neighborhood brightness coincides exactly with the order of increasing error variance. Therefore, when the brightness of the vicinity parts is closer to the brightness of the damaged area, we have the better restoration results. Thus, for Figure 7, restoration algorithm using the Habibie model is considerably inferior to the algorithm based on the use of complex (doubly stochastic) models. This is primarily due to the heterogeneity of the original image. The size of the damage is c = 40 for all images. The images sizes are the following: Figure 5 290 × 290, Figure 6 330 × 330, Figure 7 440 × 440. Dispersions of the error were calculated from relations for dispersion of the images. The analysis shows that restoring (7) is better suited to heterogeneous im- ages. Restoration using the Habibie model looks much worse even in visual per- ception. In addition, the value of the error restoring dispersion in the cases examined also depends on the ratio of size of the damage to the image size. Obviously, if it is smaller, then the accuracy is higher. It should be noted that application of the doubly stochastic model allows one to have information on the undamaged neighborhoods in the form of parameter 19 fields that provides better restoration. Analysis of the results shows that the efficiency of restoring depends on the starting position of the model implemen- tation that makes it possible to increase the efficiency of the restoration of the damaged area due to splitting into the smaller subareas. For these subareas, we choose the best neighborhood, in which estimation is made. Thus, considered restoring algorithm based on the use of models with varying parameters unlike the Habibie model restoration is able to restore the hetero- geneity areas and is generally superior to the latter. 4 Conclusion Comparative analysis of four algorithms of filtering was described in details. Researches were performed for the different images. It was found that the gain of the vector Kalman filter stabilizes with noise dispersion increasing. The vector Kalman filter for the doubly stochastic models with reverse swing provides the significant gain (40 — 50%) for the actual images that cannot be adequately described by the AR models of random fields. The algorithm of restoring damaged areas on images based on mathematical modeling was suggested. Analysis of the results obtained shows that to restore satellite images, it is appropriate to use models with varying parameters. Improvement of efficiency of the algorithm in future can be obtained by aggregation of the restoration results obtained for different directions. Acknowledgements. This work was partly supported by the Russian Educa- tion Ministry, project Goszadanie no. 2014/232. References 1. Larionov, I.B.: Clustering matrices with gaps as a method of recovery of graphical information. J. Mathematical structures and modelling vol. 20. pp. 97-106 (2009) 2. Vasil’ev, K.K., Krasheninnikov, V.R.: Statistical analyses of multidimensional im- ages. 170 p. Ulyanovsk: UlGTU (2007). 3. 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. J. Pattern Recognition and Image Analysis (Advances in mathematical theory and applica- tions). vol. 26(1). pp. 240-247 Springer. Pleiades Publishing, Ltd. (2016). 4. Andriyanov, N.A, Vasiliev, K.K, Dementiev, V.E.: Development of software for the solution of the problems of the random fileds filtration. In: International scientific- practical conference on Modern trends in science, technology and education. Pro- ceedings in 3 parts. Part 1, pp. 40-41. (2016) 5. Vasil’ev, K.K., Dement’ev, V.E., Andriyanov, N.A.: Parameter estimation of doubly stochastic random fields . J. Radiotechnika, v. 7, pp. 103-106 (2014) 6. Gonzalez, R., Woods, R., Eddins, S.: Digital Image Processing using MATLAB. Pearson Education. ISBN 978-81-7758-898-9 (2004) 20 7. Vasil’ev, K.K., Tashlinskiy, A.G., Krasheninnikov V.R.: Statistical analyses of mul- tidimensional images sequences. J. Naukoemkie technologii, v. 5. pp. 5-11 Moscow (2013) 8. Schowengerdt, R.: Remote sensing. Models and methods for image processing. Translated by Kiryushin A., Demyanikov A. (eds), 589 P. M.: Technosfera (2013) 9. Vasil’ev, K.K., Dement’ev, V.E., Andriyanov, N.A.: Doubly stochastic models of images. J. Pattern Recognition and Image Analysis (Advances in mathematical theory and applications). V. 25(1). pp. 105-110. Springer. Pleiades Publishing, Ltd. (2015) 10. Vasil’ev K.K., Dement’ev V.E.: An extended anomalies detecting on multispectral images. J. Naukoemkie technologii,, v. 3, - pp. 3-14. Moscow (2007) 11. Vasiliev. K.K, Dementiev V.E, Andriyanov, N.A.: Detection of extended signals on doubly stochastic images background. J. Radiotechnika. v. 9. pp. 23-27. (2016) 12. Vasiliev, K.K, Demetiev, V.E., Andriyanov, N.A.: The Satellite images restoration and estimation of parameters by complex structure models. In: the I International Conference May 5-6, 2016 - Ekaterinburg. Computer Image Analysis: Intelligent solutions for industrial networks. pp. 155-160. Publishing UPI UMTS. (2016)