Introduction

Recently, systems in which the initial information is a dynamic data array represented in the form of images have become widespread because such a presentation has visibility, compactness and information capacity.

The methods of image parameters estimation are based, as a rule, on four approaches. This is a comparison of image fragments, spatial-temporal filtering, morphological analysis [1], and analysis of the optical flow. For large-scale images, processing with stochastic gradient algorithms (SGA) [2][3][4][5],

based on the analysis of the optical flow, is effective. In this case, the vector of estimates  of the investigated parameters  is formed iteratively:

  1 ˆˆβQ t t t t    Λ , (1)

where t Λ -gain matrix, β tstochastic gradient of the objective function Q of the estimation quality, 1, tT  iteration number; 0 initial approximation of parameters. The algorithms are recurrent, have good accuracy characteristics and high speed of execution, do not require a preliminary evaluation of the images parameters, applicable to images with smoothly varying heterogeneity. The parameters estimated by the algorithm converge to the optimal values under rather weak conditions [6] and are resistant to impulse noise [7].

The study of the temporal dynamics of images requires analysis of the parameters of sequences of image frames, in particular, interframe geometric deformations of, for example, images  

1 Z   (1) j z  and   2 Z   (2) j z 

, where j  ,  -samples grid. As the objective function is chosen the mean square of the interframe difference in the estimation of interframe deformations under conditions when it is possible to neglect the brightness distortions, or the sampling coefficient of interframe correlation at interframe brightness distortions close to linear [8].

The key problem is to increase the speed of the SGA. Various approaches are being explored to solve this problem. In particular, in [9] a procedure for stochastic gradient optimization of the second order in a linear time was proposed, in [10] to accelerate the optimization process using algorithms based on stochastic gradient descent the Nesterov moment method is applied, in [11] a convolutional neural network is used to estimate the geometric mismatch parameters between two images in accordance with a given geometric model (the affine model and the thin-plate spline transformation are studied), in [12] the acceleration of the stochastic gradient descent is achieved by taking into account the probability of smoothness of separate areas of the image. Also one of the approach is to reduce the volume  of a two-dimensional local sample  

,

t jt jt Z z z  .

It is used at each iteration of the estimation to find the stochastic gradient   βQ of the objective function, where (2)

jt z    2 Z ,(1)

(1) jt z  Z ; (1) Zoversampled image   1 Z using the current estimates 1 ˆt   of the interframe deformations parameters. But in so doing, the possibilities of a priori and a posteriori optimization of the local sample volume according to various optimality criteria have been poorly investigated. In this paper we consider the possibility of a priori optimization of the local sample volume by the criterion of minimum computational costs when estimating one parameter.

Optimizing the local sample volume

Suppose that, in accordance with the given error in the estimation of the parameter  , the mismatch Consider the possibility of minimizing the computing costs of the SGA by optimizing the volume of the local sample for each iteration of the estimation for the given conditions. We use the following optimality criterion.

At each t -th iteration of the stochastic gradient estimation, we will search for such a volume t  of the local sample that provides the minimum of the computational cost per the conditional unit of the mathematical expectation of an parameter estimate

t   improvement   min , 1, 2, ... t gk t kk     ,(2)

where   gkthe computational cost of implementation by the algorithm of the t -th iteration for a local sample volume equal to k ;   t gk   characterizes the computational costs, normalized to the conditional unit of the mathematical expectation  t  of an estimate improvement (an expression for the calculation  t  using relay type of stochastic gradient estimate sets out later in this paper).

Because at the estimation iterations the parameter mismatch consistently changes from max  to min  , then for the T iterations the proposed criterion will provide the minimum total computational costs  

1 T t t Gg     , (3)

where Tthe number of iterations required to perform the condition min  T  ;

T  -the mismatch of the parameter estimate  and its exact value at the T -th iteration.

A detailed analysis of computational costs requires consideration not only the features and structure of the calculated ratio, but also many other influencing factors. These include the sampling time and conditions of images, the class of computing device, the time spent on the operations of addition, multiplication, division, access to memory, move data, and other auxiliary operations. Many of these factors depend on the specific image recording devices and the computers used. Therefore, in this paper, the computational cost components will not be concretized. However, we will assume that the computational costs   t g  of performing the SGA t -th iteration contain two components:

  t g  = Zt g + o g ,(4)

where Zt g -computational cost for the formation of a local sample; o g -other computing costs. In this case, the cost of forming a local sample will be considered proportional to the volume  of the local sample: Zt gg  , where g  -computational costs for the formation of a local sample of a unit volume. Then

  t g  =   1 t gc    ,(5)

where o  c g g -the coefficient characterizing the proportion of the o g when the volume of the local sample increases by one.

For relay SGA, the mathematical expectation of the improvement in the estimation t   of the parameter under study by the t -th iteration can be found [13] by using the drift probability of the estimates [14]

        1 M                    o t t t t t t t t t t             ,(6)

where   -the probability that, for a given mismatch  , the estimate  will change toward the exact value of the parameter ( sign

t  1 sign t  



);   -the probability that, for a given mismatch  , the estimate  will change away from the exact value of the parameter, that is

1 sign ( ) sign t t      ;

o  -the probability that the estimate will not change ( 0 t   ). Obviously, these probabilities constitute exhaustive events:

1 o        .

We also note that, in the strict sense, the drift probability   characterizes not the probability of improving the estimate, but the probability of changing the estimate in the "right" direction.

0  t 1 , ,     k t k t 1   t t 0  k k t     t μ ,        t t t g μ , μ       t t k t g μ μ ,     yes 1   k k 1    k t t t t       1 no yes | | | | min    t no start stop max 0   

Examples of calculating of the local sample volume

An example of computation results of optimal value of the local sample volume as a function of the mismatch is shown in figure 2. An interframe parallel image shift was evaluated. The value of the parameter c is chosen equal to 5%. Curve 1 corresponds to the noiseless images, and curve 2 corresponds to the signal-to-noise ratio 22 10

x   . It is assumed that the noise model of the For the conditions corresponding to curves 1 and 2, the table 1 shows the results of the experiment. They show the loss in computing costs when using а constant volume of local sample ( const  

researched images   1 Z и  

) in comparison with the case of using the optimal volume of local sample. When specifying in SGA const   , the value of  corresponded to the average value avg  of the optimal sample size, and

Conclusion

The approach to increasing the rate of algorithms for stochastic gradient estimation of image parameters is considered on the example of inter-frame deformations estimation. The purpose is achieved by optimizing the size of the two-dimensional local sample used at each iteration of the estimation to determine the stochastic gradient. A priori optimization based on the criterion of minimum computational costs for the case of estimating one parameter is used. At the same time at each iteration of the estimation, the local sample size providing a minimum of computational costs for the conventional unit of the mathematical expectation of the parameter estimate improvement is determined. It is shown that, as the number of iterations increases, the mismatch modulus of the estimate and the exact value of the parameter decreases, the proposed approach provides a minimum of total computational costs. To determine the mathematical expectation of an improvement of the studied parameter estimate, the probabilities of drift estimates (the probability of changing the estimates towards the exact value of the parameter and from it) are used. The carried out modeling for one of the possible algorithms realizing the proposed approach confirmed the set purpose. So, for the given example of results, the gain in computational costs in comparison with the situation of using the constant volume of the local sample amounted to no less than 3.9% in the absence of noise, and not less than 1.8% for a signal-to-noise ratio equal to 10 (in variance). Thus, the proposed approach for algorithms of stochastic gradient estimation of image parameters makes it possible to determine the optimal size of the local sample for each estimation iteration, which ensures the minimization of computational costs.