Convergence characteristics at stochastic estimation of image inter-frame deformations A G Tashlinskii1, A V Zhukova1 and D G Kraus1 1 Ulyanovsk State Technical University, Severnii Venetz, 32, Ulyanovsk, Russia, 432027 e-mail: kraus_bak@mail.ru Abstract. Several approaches to the numerical description of image inter-frame geometric deformations parameters estimates behavior at iterations of non-identification relay stochastic gradient estimation are considered. The probability density of the Euclidean mismatch distance of estimates vector is chosen as an argument of the characteristics forming the numerical values. It made it possible to ensure invariance of research to the set of parameters of the used inter-frame geometric deformations model. The mathematical expectation, the probability of exceeding a given threshold value of the convergence rate and the confidence interval of the Euclidean mismatch distance were investigated as characteristics. Probabilistic mathematical modeling is applied to calculate the probability density of the Euclidean mismatch distance. 1. Introduction The systems of information extraction with spatial apertures of signal sensors are widely spread. These systems form dynamic arrays of spatially correlated data represented by image sequence. This representation has the clarity, compactness, and information capacity. In this case, one of the important tasks is to estimate the geometric deformations parameters of the image sequence [1-5]. To solve this problem, non-identification stochastic estimation proved to be good [6], wherein the formation of vector estimate α of deformation parameters of reference {z j(1) } and deformed {z j( 2 ) } images (where {j = ( jx , j y ) } - pixel coordinates of z j(1) and z j( 2 ) ), can be described by the procedure T [7, 8]: αˆ t = αˆ t −1 − Λ t βt (Z t , αˆ t −1 ) , (1) where β(⋅) – stochastic gradient of an objective function, which characterizes the quality of evaluation (the mean square of the difference between the brightness of the reference and deformed images was used as the objective function to calculate examples); Λ t – gain matrix, determining a value of the estimates change at the t -th iteration; Z t – two-dimensional local sample of the reference and deformed images used to determine the stochastic gradient at the t -th iteration [9, 10]. The local sample size (LSS) largely determines the nature of estimates deformation convergence and the computational cost. The research direction is due to the fact that the problems of LSS optimization are not investigated enough. The paper discusses the possibilities of numerical description of vector estimates of geometric deformations parameters estimates behavior at iterations of non-identification relay stochastic gradient estimation. V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) Image Processing and Earth Remote Sensing A G Tashlinskii, A V Zhukova and D G Kraus As initial information for the numerical description of vector estimates behavior, the probability distributions of the estimates deformation parameters are chosen. The paper investigated the mathematical expectation, the probability of exceeding a given threshold value of convergence rate and the confidence interval as characteristics that form numerical values. When estimating one deformation parameter, these characteristics are directly applicable to its evaluation. If the set of parameters is estimated, then at the same iteration for each parameter different values of the optimal LSS can be obtained. Since one local sample is formed at each iteration, its value will be chosen corresponding to the maximum of the optimal volumes, which will lead to unreasonable computational costs. Therefore, in the paper, the probability distribution of the Euclidean mismatch distance (EMD) for the vector of deformation parameter estimates is chosen as the argument of the studied characteristics. This made possible to ensure the invariance of the study to the set of parameters of the deformation model used. 2. Choice of argument characteristics For definiteness, we assume that geometric deformations of the images are estimated and described by the model of similarity, which include parameters of parallel shift h = (hx , h y ) , rotation angle ϕ , T scale factor κ . In this case, we note that limitation of the parameter vector does not limit the following consideration. Let, after the (t − 1) -th iteration the vector of deformation parameters estimates has values ( ) T α t −1 = hˆx (t −1) , hˆy (t −1) , ϕˆt −1 , κˆt −1 . In addition, each estimate hˆx ( t −1) , hˆy ( t −1) , ϕˆt −1 and κˆt −1 has its own ( ) ( ) probability distribution: wt −1 hˆx , wt −1 hˆy , wt −1 (ϕ̂ ) and wt −1 (κˆ ) . Then, on the t -th iteration in the local sample the sample from resampled reference image with coordinates ( xa , yb ) will be taken for a couple with sample from deformed image with coordinates (a, b ) : xa = x0 + κˆt −1 ((a − x0 )cos ϕˆt −1 − (b − y0 )sin ϕˆt −1 ) + hˆx ( t −1) , (2) yb = y0 + κˆt −1 ((a − x0 )sin ϕˆt −1 + (b − y0 ) cosϕˆt −1 ) + hˆy ( t −1) , where ( x0 , y0 ) – the coordinates of the rotation center. The method for calculating the probability distribution of estimates of the image geometric deformations parameters was proposed in [11] and involves the sampling of the domain of parameter definition. Using the method it is possible to obtain discrete probability distributions (DPD) of the parameters for the selected deformation model: { ( )} { ( )} w(hx ) = plx = P hˆx = hlx , l x = 1, Lx , w(h y ) = pl y = P hˆy = hl y , l y = 1, Ly , { ( )} ( ) w(ϕ ) = plϕ = P ϕˆ = ϕ lϕ , lϕ = 1, Lϕ , w(κ ) = plκ = P κˆ = κ lκ , lκ = 1, Lκ , where P ( z ) - the probability of z ; Lx , L y , Lϕ и Lκ – the number of intervals for splitting the parameter space hx , hy , ϕ and κ . Then the coordinates (2) with the probability Pl x l y lϕ lκ = pl x pl y plϕ plκ take the values: ( ) xl x l y lϕ lκ = x0 + κ lκ (a − y0 )cos ϕ lϕ − (b − x0 )sin ϕ lϕ + hl x , yl x l y lϕ lκ = y + κ ((a − y )sin ϕ + (b − x ) cosϕ ) + h . 0 lκ 0 lϕ 0 lϕ ly l Thus, it is possible to calculate a probability distribution of distances between a point with coordinates (a, b ) on the deformed image and possible positions of the conjugate point on the reference image for current estimates of the deformation parameters, i.e. get DPD of the euclidean mismatch distance (EMD) wt (r ) at the t -th iteration. Let consider a few examples of the results for the calculation DPD of EMD. Let the images have a Gaussian autocorrelation function and a signal-to-noise ratio (ratio of the variances of image and V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 115 Image Processing and Earth Remote Sensing A G Tashlinskii, A V Zhukova and D G Kraus noise) equal to 14. For parameters estimation the stochastic procedure (1) of relay type with diagonal gain matrix λhx 0 0 0 0 λhy 0 0 Λ= 0 0 λϕ 0 0 0 0 λκ and constant elements: λhx = λhy = 0,05 , λϕ = 0,4 and λκ = 0,005 is used. The value of the gain matrix coefficients is selected based on the autocorrelation function of the image (the value of the correlation radius of this function). The same experimental conditions are used for the examples given below. Figure 1a and 1b show an example of the calculated DPD of estimates ϕ̂ and κˆ with µ =1 and the parameter mismatch hx = h y = 4 , ϕ = 15o and κ = 1,2 , after 60 iterations. Note that the probability distribution of estimates of all parameters are close to the Gaussian. Figure 1c shows DPD w60 (r ) of absolute value EMD after 60 iterations: rl x l y lϕ lκ = ( a − xl x l y lϕ lκ ) 2 + (b − yl x l y lϕ lκ ) 2 l l l In this case, the expectation value of the EMD is 1.9, and the variance is 4.0. a) b) c) Figure 1. Examples of DPD of deformation parameter estimates and EMD. Figure 2a shows an example calculation for sample size µ = 3 . In the general case, different points of the local sample plan correspond to different distribution of EMD. Totality of all local sample points corresponds to the total distribution. Examples of such distributions are shown in Figure 2. The local sample plan was formed as follows. At the t -th iteration of estimating the coordinate ( j x1 , j y1 ) of the first count on the deformed image were chosen randomly within a certain domain, and the other two according to the rule: ( jxi , j yi ) = (int [Ri sin φi ], int[Ri sin φi ]) , where i = 2, 3 ; int [z ] - integer part of z; φ2 = arctg (( j y1 − y0 ) ( jx1 − x0 )) − 120o , φ3 = arctg (( j y1 − y0 ) ( jx1 − x0 )) + 120o ; ( x0 , y0 ) - image center coordinates; Ri - random number. Another example of DPD of EMD after 65 iteration that estimates mismatch parameters hx = 4 , h y = 4 , ϕ = 150 and κ = 1 with the volume of the local sample µ = 2 is shown in the figure 2b. a) b) Figure 2. Examples DPD of EMD with µ > 1 . V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 116 Image Processing and Earth Remote Sensing A G Tashlinskii, A V Zhukova and D G Kraus The result shows that with increasing LSS the distribution of EMD is not normalized. This is due to that EDM has non-linear dependence on deformation parameters, with the result that different points of the local sample plan give statistically significantly different mathematical expectations and variances of EDM. 3. Characteristics of changes in the vector estimations Using the probability distribution of EMD we find the expression for the numerical description of image geometric deformations parameters estimates behavior at iterations of non-identification relay stochastic gradient estimation. As the characteristics that form the numerical values, we consider mathematical expectation, the probability of exceeding a given threshold value of the convergence rate and the confidence interval EMD. 3.1 Mathematical expectation of change EMD The mathematical expectation of EMD determines the average rate of convergence of the estimated parameters at the t -th iteration. At LSS µ = m , this characteristic can be found through a change in the distribution of EMD on adjacent iterations: ∞ M[∆r ] µ = m = ∫ r (wt −1 (r ) − wt (r ))dr . (3) 0 A positive value (3) corresponds to the improvement of the parameter estimates vector α̂ , a negative value corresponds to the deterioration. When using DPD the value M[∆r ] is determined by the ratio: Lr M[∆r ] µ = m = ∑ ri ( pi ,t −1 − pi ,t ) , i =1 where Lr is the number of intervals splitting the domain of definition EMD. Clearly, that the expectation value M[∆r (+ k )] of improving the vector of parameter estimates with increasing LSS by k can be found as: ( ) Lr M[∆r (+ k )] = ∑ ri pi ,t µ = m − pi ,t µ = m + k . i =1 For example, Figure 3a shows the dependence w60 (r ) − w61 (r ) on EMD, which calculated at µ = 1 for 61 iterations. This dependence describes parameter estimation vector changing for one iteration. In the given example for 61 iteration. Obviously, that with small EMD the probability differences are negative, for large ones they are positive. At the same time, the average value describes the integral change of the vector of estimates is positive (which indicates an improvement in the estimates) and equal to 0.017. The dependence numerically describe the improvement of the convergence estimates with increasing sample size is shown in Figure 3b. It shows the change of DPD of EMD after 60 iterations of the estimate when µ = 2 compared to the case µ = 1 . As in Figure 3a, for small EMD, the probability differences are negative, for large ones, they are positive. a) b) Figure 3. Examples of differences in the DPD of EMD on adjacent iterations (a) and different LSS (b). V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 117 Image Processing and Earth Remote Sensing A G Tashlinskii, A V Zhukova and D G Kraus However, the average value was 0.02, which indicates a significantly higher rate of convergence of estimates. 3.2. Probability of exceeding a given threshold value of EMD convergence rate Let us consider the possibility of using the probability of exceeding the given threshold value by the rate of convergence of the EMD to zero as a numerical characteristic of the convergence rate. It is necessary to determine the distribution wt (ν ) of the convergence rate ν at the iterations of estimation and then determine the probability. The probability that EMD convergence rate at the t –th iteration will exceed a given threshold ν tv is: v tv Pt = 1 − ∫ wt (ν )dν . (4) −∞ In this case, the distribution wt (ν ) can be found as the difference DPD of EDM on adjacent iterations: wt (ν ) = r (wt −1 (r ) − wt (r )) , conditionally accepting for a unit of time a dimensionless time between iterations. In this case, the convergence rate can be estimated as at each iteration, as after a certain number of k iterations: wt (ν ) = r (wt −1 (r ) − wt (r )) Figure 4a shows an example of the DPD convergence rate of the EDM at 60 iterations at µ = 1 . At the same time, threshold value ν tv is equal to 0.21 and the probability (4) of exceeding (shaded domain) is equal to 0.68. Figure 4b shows the dependence of probability exceeding the convergence rate of the EMD of the selected threshold value on LSS. Clearly, if you increase volume, then the probability increases, and reaches at µ = 5 value 0.99. a) b) Figure 4. DPD convergence rate and probability of exceeding the threshold value. 3.3. Confidence interval of the EMD The change in the boundaries of the confidence interval at adjacent iterations is used as the numerical value of the deformation estimates of the confidence interval of EMD for a given confidence probability: ∆rci = rlt − rl ( t +1) + rrt − rr ( t +1) , (5) where the indices “l” and “r” mean left and right limits of the confidence intervals, respectively. Ratio (6) explains figure 5, where lt and lt +1 are confidence intervals, respectively, in the t -th and (t + 1) -th iterations. Figure 5. Changing the boundaries of the confidence interval. V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 118 Image Processing and Earth Remote Sensing A G Tashlinskii, A V Zhukova and D G Kraus Similarly, through the boundaries of the confidence intervals, one can describe the change in the vector of estimates with increasing LSS from µ = m to µ = m + k : ∆rci (+ k ) = rlt µ = m − rlt µ = m + k + rrt µ = m − rrt µ = m + k . (6) Note that expressions (5) and (6) are written down with taking into account that the value of EMD cannot be non-negative. It is also necessary to take into account the mismatch signs of the current estimate α̂ t and the exact parameter values α , when analyzing the measurement of boundaries of the confidence intervals of individual deformation parameters (such as the angle of rotation, parallel shift, etc.), which can be equal to positive and negative values: ∆rci = (rlt − rl ( t +1) + rrt − rr ( t +1) ) sign (αˆ t − α ) , ∆rci (+ k ) = (rlt µ = m − rlt µ = m + k + rrt µ = m − rrt µ = m + k ) sign (αˆ t − α )t . 4. Conclusion The paper presented numerical description of image geometric deformations parameters estimates behavior at iterations of non-identification relay stochastic gradient estimation. As initial information for solving the problem, we consider the probability distribution of parameter estimates. As an argument of numerical characteristics that describe the convergence rate of estimates of geometric deformation parameters of images, the distribution of EMD probabilities is used. They form numerical values, which made it possible to ensure invariance to the set of parameters of the used inter-frame geometric deformations model. The mathematical expectation of EMD change, probability of exceeding the convergence rate of a given threshold value and confidence interval of EMD at a given confidence level are investigated as numerical characteristics. The investigated characteristics can be used to optimize the volume and plan of the local sample according to various criteria. In particular, when using the probability of exceeding a given threshold value of the convergence rate to optimize the LSS, and after calculating the DPD of EMD, the task is reduced to finding the LSS which ensures that probability (4) exceeds a given probability threshold. Results showed that the confidence interval is a less informative parameter in comparison with mathematical expectation of change and with probability of exceeding a given threshold value of the convergence rate EMD. This is due to the fact that the probability distribution of EMD significantly changes from iteration to iteration. Therefore, on adjacent iterations, the change in the limits of the confidence interval does not always characterize the improvement of the estimates vector. 5. References [1] Fursov V A, Gavrilov A V, Goshin Ye V and Pugachev K G 2017 Conforming identification of the fundamental matrix in the image matching problem Computer Optics 41(4) 559-563 DOI: 10.18287/2412-6179-2017-41-4-559-563 [2] Tashlinskii A G, Smirnov P V and Tsaryov M G 2017 Pixel-by-pixel estimation of scene motion in video International Archives of the Photogrammetry Remote Sensing and Spatial Information XLII-2/W4 61-65 [3] Maksimov A I and Gashnikov M V 2018 Adaptive interpolation of multidimensional signals for differential compression Computer Optics 42(4) 679-687 DOI: 10.18287/2412-6179-2018-42-4- 679-687 [4] Moritz P, Nishihara R and Jordan M 2016 A linearly-convergent stochastic L-BFGS algorithm Proc. of the 19th Int. Conf. on Artificial Intelligence and Statistics 249-258 [5] Dmitriev E A and Myasnikov V V 2018 Comparative study of description algorithms for complex-valued gradient fields of digital images using linear dimensionality reduction methods Computer Optics 42(5) 822-828 DOI: 10.18287/2412-6179-2018-42-5-822-828 [6] Tsypkin Ya Z 1995 Information theory of identification (Moscow: Fizmatlit) 336 (in Russian) [7] Tashlinskii A G 2003 Computational expenditure reduction in pseudo-gradient image parameter estimation Lecture Notes in Computer Science 2658 456-462 V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 119 Image Processing and Earth Remote Sensing A G Tashlinskii, A V Zhukova and D G Kraus [8] Tashlinskii A G 2007 Pseudogradient estimation of digital images interframe geometrical deformations Vision Systems: Segmentation and Pattern Recognition (Vienna: I Tech Education and Publishing) 25 465-494 [9] Tashlinskii A G 2008 Optimization of goal function pseudogradient in the problem of interframe geometrical deformations estimation Pattern Recognition Techniques, Technology and Applications (Vienna: I Tech Education and Publishing) 10 249-280 [10] Tashlinskii A G and Zhukova A V 2017 Effectiveness of correlation and information measures for synthesis of recurrent algorithms for estimating spatial deformations of video sequences CEUR Workshop Proceedings 1901 235-239 [11] Tashlinskii A G and Tichonov V O 2001 Methods for analyzing the error of pseudogradient measurement of the parameters of multidimensional processes Izvesyiya vuzov: Radioelectronika 44(9) 75-80 (in Russian) Acknowledgments The reported study was funded by RFBR and Government of Ulyanovsk Region according to the research project № 18-01-730006 and № 18-41-730009. V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 120