=Paper=
{{Paper
|id=Vol-2391/paper16
|storemode=property
|title=Convergence characteristics at stochastic estimation of image inter-frame deformations
|pdfUrl=https://ceur-ws.org/Vol-2391/paper16.pdf
|volume=Vol-2391
|authors=Alexander Tashlinskii,Alena Zhukova,Dmitrii Kraus
}}
==Convergence characteristics at stochastic estimation of image inter-frame deformations ==
https://ceur-ws.org/Vol-2391/paper16.pdf
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