A comparative analysis of the efficiency of correlation (cross-correlation, Tanimoto coefficient and Kendall's rank correlation coefficient) and information (mutual information of Tsallis and Shannon, F-information measure and entropy of the joint probability distribution) measures of image similarity for the synthesis of recursive estimation algorithms is presented for the problem of estimating parameters of spatial deformations of a sequence of images. Unbiased additive Gaussian noise was used as an interfering factor in the experimental studies. It is shown that the potentially high convergence rate of the estimated parameters and the smaller variance of the estimation error from the investigated correlation measures are ensured by the Tonimoto coefficient, and from the I-information of the F-information among the information measures. According to these criteria, the Kendall's rank correlation coefficient and the M-measure of F-information are inferior, respectively.
deformation parameters are corrected by a certain amount in the direction dαˆ , Zt [3]:
The detection and evaluation of spatial changes (deformations) in a sequence of images Z(n) , n 1, N 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 Z(n) z(jn) and Z(n1) z(jn1) , 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 αt 1 αˆ t Λt dt αˆ , Zt , ˆ (1) where Λt — a positively defined matrix (usually diagonal); t 1,T — iteration number.
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 [
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
Image Processing, Geoinformation Technology and Information Security / A.G. Tashlinskiy, A.V. Zhukova
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 [
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 h 0 50 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.
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.
r
ˆ zn ˆ zn1 jtt points in a CC (cross-correlation) [9] is one of the most popular similarity measures. CC can be defined as 1 ~z(n) M[Z~(n) ]z (n1) M[Z(n1) ], jt jt jtt z jt where — the number of subsample;
M[Z] — image mean estimation
Z ; ˆ2 z jtt z jt M[Z]2 — estimation of image Z variance. Correlation coefficient r changes between 1 and +1. The value r 1 means the full linear relation, r 1 ‒ negative linear relation. If r is different to 1 then the relation of corresponding pixels ~z (n) and z(n1) can be described as: z (jtn1) ˆ zn ~zj(tn) MZ~(n) MZn1 the measure of relation ˆ zn1 linearity between Z(n) and Z(n1) 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 [
~z(n) z (n1) ST jtt jt jt . (2)
jtt ~zj(tn) z (jtn1) jtt ~zj(tn) z (jtn1) 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
Image Processing, Geoinformation Technology and Information Security / A.G. Tashlinskiy, A.V. Zhukova 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 ~z j(n) and z(jn 1) are intensities of corresponding image pixels then for their differences ( ~z(n) ~z(n) ) and i j (z(n1) z(n1) ) i j when
i j there are two possible situations: concordance - when
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 of additive noise and multimodal images. Generalized Shannon MI can be defined in terms of entropy as:
J αˆ , Z~(n) , Z(n1) H Z~(n) H Z(n1) H Z~(n) , Z(n1) , (4) where H (Z) pz ( zi ) log pz ( zi ) ‒ image Z
i H ( Z~(n) , Z(n1) ) pzn ,zn1 (zi , zk ) log pzn ,zn1 (zi , zk ) ‒ joint entropy estimation;
i k intensities.
Tsallis MI is defined as [12]:
Rg S g ( Z~(n) )S g (Z(n1) )(1q)S g ( Z~(n) )S g (Z(n1) )Sq ( Z~(n) ,Z(n1) ), entropy estimation; pz ‒ marginal PDF estimation of the image sample; p zn ,zn1 ‒ joint PDF estimation of (5) (6) (7)
N N where Sg ( Z~(n) , Z(n1) ) g 111 pig, j ‒ Tsallis entropy of the order g , g - a real number. When g =1 Tsallis i0 j0 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:
I M -measure: -measure:
1 N N pi, j 1 i0 j0 pi p j 1
1,
N N 1 M i0 j0 pi, j pi p j ,
N N i0 j0 pi, j pi p j
. pi p j 1 I -measure is defined for 0 , 1 , and when 1 it approaches Shannon MI. M -measure is defiened for 0 1, and -measure – for 1 .
Exclusive F-information is related to entropy of JPD and Shannon MI:
D f (Z~ (n) , Z(n1) ) 2H Z~ (n) , Z(n1) H (Z~ (n) ) H (Z(n1) ).
two variables the smaller the entropy of JPD.
Image Processing, Geoinformation Technology and Information Security / A.G. Tashlinskiy, A.V. Zhukova
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 spatial deformation, so the critical value of the slope here is considered, in fact, as a c riterion 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.
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 P DF 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 q 0.07 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 ( q 0.15 ) 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 ( q 0.25 ), 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
Image Processing, Geoinformation Technology and Information Security / A.G. Tashlinskiy, A.V. Zhukova 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.
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.