Introduction

The detection and evaluation of spatial changes (deformations) in a sequence of images

) (n Z , N n , 1 

is one of the key tasks of processing video sequences. Various approaches to the solution of this problem are implemented in the frequency [1] and in the spatial [2] domains.

In this case, the solution is usually based on the search for an extremum of some similarity measure (SM) between each pair of adjacent images

  ) ( ) ( n j n z  Z and   ) 1 ( ) 1 (    n j n z Z

, where j − coordinates of the nodes of the grid of samples on which the images are defined. With the assumed model of interframe spatial deformations of images, estimates are sought for the strain parameters α of one of the images at which the extremum of the SM is reached.

When recursively searching for the SM extremum at each iteration t of the estimation the current estimates α of the spatial deformation parameters are corrected by a certain amount in the direction   t Z , α d [3]:

  t t t t t Z , α d α α ˆ1 Λ    ,(1)

where t Λa positively defined matrix (usually diagonal); T t , 1  iteration number.

The direction    d is defined by the SM gradient estimated using a small subsample [4]   Z [5]. In order to improve the accuracy of parameters' estimates α ˆ we need to increase a number of points in the subsamples but it will lead to increase in computational time.

There are many SM for images [6]. The choice of a particular SM is determined by the conditions and requirements of the applied problem, the nature of the possible spatial deformations of the video sequence, the properties of the images and the interfering factors.

Problem formulation

The chosen SM largely determines the potential effectiveness of the recursive algorithms for estimating spatial deformations in a sequence of images synthesized on its basis. However, criteria that allow a priori evaluation of the potential efficiency of algorithms by SM are poorly investigated. A variant of the solution of this problem was considered in [7,8]. In this work several correlation correlations have been selected for the study: cross-correlation (the coefficient of interframe correlation) [9], the Tanimoto coefficient [10] the Kendall's rank correlation coefficient [11], and a number of informational SMs: Tsallis [12] and Shannon mutual information, F-information measures, and the entropy of the joint probability distribution [13]. Unbiased additive Gaussian noise was used as an interfering factor in the studies. The relation between SM characteristics and the probabilistic properties of estimates of the parameters of spatial deformations formed by recurrent algorithms synthesized on the basis of these measures was also investigated.

A method for calculating the probabilistic properties of estimates of the parameters of inter-frame spatial deformations of images for a finite number of iterations of recurrent estimation [14] was proposed in [16]. It is based on finding the probabilities of demolition at each iteration (the probabilities of changing the estimates of the investigated parameters α ˆ towards optimal values). With allowance for (1) the probability of demolishing of the estimates at the next iteration can be interpreted as the probability that the projection of the gradient of the SM gradient on the axis of this parameter will be negative. In [15] this characteristic was used to find the error in estimates of the parameters of inter-frame spatial deformations of images formed by relay procedures of the form (1). However, this approach can be used for recurrent procedures of other classes.

Since procedure (1) is based on the use of SM gradient estimates its capabilities are largely determined by the nature of the slope К of the SM used in the synthesis of the procedure. Fig. 1 shows examples of the dependence of the slope of the SMs chosen for the study on the magnitude of the parallel shift h of the images, where 50 0   h is the shift in the grid steps of the image counts. Curves of the curvature module of the SM for correlation measures are shown on the left graph, where curve 1 corresponds to the Kendall rank correlation coefficient, curve 2 -to the Tanimoto coefficient, curve 3 -to the interframe correlation coefficient (CC). The right graph shows the dependencies for information SMs, here curve 1 corresponds to Shannon MI, curve 2 -to Tsallis MI, curve 3 -to I-measure of F-information, curve 4 -to M-measure of F-information, curve 5 -to excluding F-information, curve 6 -the entropy of the joint probability distribution (JPD). The legend is the same for all other figures in this work.

Correlation measures

Information measures Fig. 1. Slope of the studied SM.

From Fig. 1 it can be seen that the nature of the slope of different SMs differs significantly, which must affect the potential characteristics of the recurrent evaluation procedures synthesized on their basis. A number of efficiency criteria based on an analysis of the nature of the SM slope was proposed in [8]. We will consider these criteria with reference to the correlation and information SMs chosen for the study. [9] is one of the most popular similarity measures. CC can be defined as

Studied image similarity measures

Probability-based measures CC (cross-correlation)               t t t t n n j n n j n n j z z z z r ] M[ ] M[ 1 ) 1 ( ) 1 ( ) ( ) ( 1 Z Z ,

where  -the number of points in a subsample;

     t t t j j z ] M[Z -image mean estimation Z ;          t t t j j z z 2 2 ] M[ ˆZ -        1 ) ( ) ( ) 1 ( M M 1         n n n j z z n j t n n t z z Z Z the measure of relation linearity between ) (n Z and ) 1 (  n Z

which allows us to efficiently use correlation coefficient in case of additive noise or linear intensity distortions. In terms of computational complexity, CC is very effective, as it requires a small number of additions and multiplications for each element in the subsample. It is in the order of  .

Tanimoto coefficient [10] between two images

) ( ~n Z and ) 1 (  n Z is defined as:                  t t t t t t t t t t t t j n j n j j n j n j j n j n j T z z z z z z S 2 ) 1 ( ) ( ) 1 ( ) ( ) 1 ( ) ( ~.

(2)

In comparison with CC in Tanimoto coefficient normalization of intensity multiplication with respect to their standard deviations is replaced by the normalization with respect to the sum of squared differences between corresponding sample counts, which effects in the same way. Using the inner product of intensities in the denominator of Tanimoto coefficient gives the same effect as the normalization with respect to mean values of images. Computational complexity of Tanimoto coefficient is on the same order as for correlation coefficient.

Kendall rank correlation coefficient [11]. If

) ( ~n j z and ) 1 (  n j z

are intensities of corresponding image pixels then for their differences )

( ) ( ) ( n j n i z z  and ) ( ) 1 ( ) 1 (    n j n i z z when j i 

there are two possible situations: concordance -when

) ( sign ) ( sign ) 1 ( ) 1 ( ) ( ) (      n j n i n j n i z z z z and mismatch -when ) ( sign ) ( sign ) 1 ( ) 1 ( ) ( ) (       n j n i n j n i z z z z . If

Z

and the number of concordances is greater than the number of mismatches then we can conclude that image intensities are bounded. Let assume that from 2  pixel pairs are concordances and d N are mismatches then Kendall correlation coefficient can be defined as follows [9]:

    . 1 2       d c N N (3)

Kendal correlation coefficient is one of the most complex measures in terms of computational complexity. It requires concordance and mismatch computations for  

2 1   

corresponding pixel pairs. Therefore, its computational complexity of  is on the order of 2  operations.

Information measures

Shannon mutual information (MI) is one of the most widely used similarity measure in image registration [12,13] as it provides an extremely high accuracy when images have linear and non-linear intensity distortions, occlusions and also in case additive noise and multimodal images. Generalized Shannon MI can be defined in terms of entropy as:

       , , , , α Ĵ ) 1 ( ) ( ) 1 ( ) ( ) 1 ( ) (       n n n n n n H H H Z Z Z Z Z Z(4)

where ), ,

   i i z i z z p z p H ) ( log ) ( ) (Z -image Z entropy estimation; z p -marginal PDF estimation of the image sample;       i k k i z z k i z z n n z z p z z p H n n n n ) ,( log ) , ( ) , ( 1 1 , , ) 1 ( ) ( Z( ) ( ) ( ) 1 ( ) ( ) ( ) 1 ( ) ( ) 1 ( ) ( ) 1 ( ) (         n n q n g n g n g n g g S S S q S S R Z Z Z Z Z Z(5)

where

                 N i N j g j i n n g p g S 0 0 , 1 ) 1 ( ) ( 1 1 ) , ( Z Z

-Tsallis entropy of the order g , g -a real number. When g =1 Tsallis entropy approaches Shannon entropy.

F-information measures are based on divergence or distance between joint probability distributions and multiplication of marginal distribution of image pair. A class of divergence measures that uses MI is the F-information measures. F-information measures are [13]:

I -measure:     , 1 1 1 0 0 1 ,                      N i N j j i j i p p p I M -measure:   , 0 0 1 ,          N i N j j i j i p p p M (6)  -measure:   . 0 0 1 ,            N i N j j i j i j i p p p p p I -measure is defined for 0   , 1   , -measure -for 1   .

Exclusive F-information is related to entropy of JPD and Shannon MI:

  ). ( ) ( , 2 ) , ( ) 1 ( ) ( ) 1 ( ) ( ) 1 ( ) (       n n n n n n f H Z H Z H Z D Z Z Z (7)

Entropy of JPD is defined as:

, 0 0 2 ,      N i N j j i p E (8)

where

j i p

,an element of JPD which can be estimated, for example using histograms. The stronger the relationship between two variables the smaller the entropy of JPD.

Effectiveness analysis of similarity measures

Effectiveness criteria

As already noted, a number of criteria for the effectiveness of SM's use in the synthesis of recurrent procedures for estimating spatial deformations of images were proposed in [8]. They are based on an analysis of the slope of SM dependening on the Euclidean mismatch distance [16]. Among the characteristics that determine efficiency, the maximum slope max К in the area of interest of the parameters being evaluated, the effective range of the parameters P , and the region of curvature growth S can be attributed. It is shown that the maximum slope of SM corresponds to the maximum probability of improving the estimates of the parameters of interframe spatial deformations toward optimal values, and this extremum determines the potential rate of convergence of the estimation vector [7].

The effective range in this work refers to as subdomain of the domain of definition of registration parameters in which the required accuracy values are attained under given constraints, e.g. computational complexity, number of iteration etc. A condition under which a point of the space of estimated parameters falls into the effective range is that the slope of the SM at this point should exceed a certain critical value which does not guarantee the required convergence rate of the estimate vector α any longer. Note that the actual effective range also depends on many other factors, in particular, the parameters of the estimation algorithm, the type of deformation, so the critical value of the slope here is considered, in fact, as a criterion for determining the range of values of the discrepancies of the estimated parameters, for which the probabilitie of demolition of estimates exceeds the specified threshold value.

Experimental results

For SM efficiency analysis it is reasonable to use simulated images whose intensity PDF and correlation function can be priori defined during their synthesis. In conducted experiments simulated images based on wave model [17] with intensity PDF and correlation function close to Gaussian were used. In addition, an unbiased white noise was used as a disturbing factor.

For example, Fig. 2 -Fig. 3 show the graphs of the dependence of the above efficiency indicators on the noise/signal ratio q (in terms of variances), where the left graph corresponds to the data for the correlation ones, and the right graph for the information SMs. As a mismatch, for simplicity, a parallel image shift was selected. We also note that the choice of parallel shift of images as frame-wise deformations doesn't weakens the generalization of the examination, since for any set of strain parameters the result of their effect on each point of the image can be recalculated through the Euclidean mismatch distance [16] into the vector of its shift relative to the initial position. That is, the result of any deformations can be represented by the PDF of such shifts. Analysis of fig. 2 shows that by the criterion of the maximum slope among the correlation SM the best result is provided by the Tonimoto coefficient whose maximum slope decreases most slowly with increasing noise intensity. The next by the result is the Kendall coefficient. CC at large noise is much inferior to them, however, with 07 . 0  q the maximum slope CC exceeds the max К of Kendall coefficient. Investigations of information SMs showed that the potentially high convergence rate of the parameters being evaluated is provided by the I-measure of the F-information. The next most effective M-measure of Finformation, which in large noises is more effective than the I-measure. Shannon and Tsallis MI, as well as the entropy of the JPD give close characteristics. Essentially they are inferior to the excluding F-information.

According to the effective range criterion (fig. 3), the best results among the correlation SMs also gave the use of the Kendall rank correlation coefficient. Then, with a margin of up to 40%, the coefficient of Tanimoto and CC, respectively. Among the information measures for small noise ( 15 .

 q

) the best results were shown by the I-measure of the F-information and the netropy of the joint JPD. This is followed by Tsallis and Shannon MI and the M-measure of F-information. For large noise ( 25 .

 q

), the M-measure and the I-measure of the F-information provide a larger effective range. Approximately the same parameters show the entropy of the JPD, Shannon and Tsallis MI. We note that the slope of the I-measure of the F-information decreases significantly more rapidly with increasing noise than in the M-measure of the F-information. The worst results were shown by the excluding F-information.

Correlation measures

Information measures Fig. 3. Effective range of SM.

Conclusion

There are many SM of images on the basis of which recursive algorithms for estimating spatial deformations in a sequence of images can be synthesized. However, criteria that allow a priori evaluation of the potential efficiency of algorithms by the SM function are not well studied. A number of correlation (CC, Tanimoto coefficient and Kendall rank correlation coefficient) and informational (Tsallis and Shannon mutual information, F-information measures and joint probability distribution energy) SM are investigated based on the criteria of maximum slope that determines the potential rate of convergence of deformation parameter estimates and effective range, which refers to the subdomain of the domain of deformation parameters, in which the required indicators of accuracy and reliability of estimation are provided.

Studies have shown that, according to the criterion of maximum slope from correlation SM, the best result is provided by the Tonimoto coefficient, the maximum slope of which decreases most slowly with increasing noise intensity, and among the information I-measure of F-information. The worst results were shown by the CC and the excluding F-information, respectively.

By the criterion of the effective range, the best results among the correlation SMs were provided by the Kendall rank correlation coefficient. Then, respectively, the Tanimoto and CC coefficients. Among the information measures, the I-measure and the M-measure of the F-information showed greater resistance to noise. In this case, the slope of the I-measure of the Finformation decreases significantly faster with increasing noise than in the M-measure.