International Journal of Scientific & Engineering Research Volume 6, Issue Ř, Ž‹›žŠ›¢-2015

ISSN 2229-5518


Satellite Image Matching using Kalman Filter and a cross correlation technique

Wafaa Rajaa DRIOUA1, Nacèra BENAMRANE1, Noureddine KHELOUFI

Abstract— In this paper, we propose a method for evaluating the displacement and deformation fields for pair of multi temporal images, one before and one after deformation; based on a matchning technique of cross correlation. First, according to the noise present in the images and the long computation time, a denoising based on the Kalman filter and a multi-resolution analysis of effiient optimization scheme are proposed to improve the quality and speed time calculation. Second, an algorithm for matching based on the gray levels cross correlation is intoduced to improve the efficiency on matching. Our method was tested on satellite images and the results are encouraging.

Index Terms— Matching images, cross-correlation, displacement, deformation, satellite images.

—————————— ——————————


ptical techniques have opened up a wide field of applica- tions in remote monitoring environments, mobile robotics, control or measurement. The objective of this paper is to develop a method to measure the displacement and defor- mation fields using the cross-correlation technique in gray lev- els. The general principle is based on matching images in com-
puter vision. Two steps are required for any measure:

The matching between the two multi temporal images is to de-

termine a set of homologous pixels corresponding to the same physical point.

The extent of the displacement field and the calculation of the

deformation field between the two images (reference state and deformed state).
Several authors Vincent L., [1] Chambon S., [2] presented a classification of matching methods. The criteria used are gener- ally the nature and dimension of attributes (constituting ele- ments) to match, the field (local or global), the problem to solve, the constraints used, the measurement of similarity measure...
In recent years digital image correlation given by Peters
W.H. et al [3] Chu T.C. et al [4] has become increasingly im- portant. Many authors use the correlation Crouzil A. et al [5]. Zhao, F. et al [6] presented a method based on normalized cross-correlation that can effectively manage a pair of images
with a big change and Rziza M. et al [7] presented algorithms for estimating disparity, based on the method of estimating a


1 Departement of computer sciences, university of sciences and technology

Mouhamed Boudiaf, Oran, Algeria.,
dense disparity map by using higher order statistics and robust correlation method. Due to the size of the data, matching can be very large, which is why several methods use a hierarchical of scheme matching like Qin, X. et al [8] who used a pyramid im-
age and Fookes, C. et al [9] who presented extensions of the ste- reo matching based on mutual information and a approach with two hierarchical levels in order to increase the robustness of the algorithm. Also Hu Hao et al [10] presented a method of automatic vision to measure the deformation of surfaces. This method is based on image correlation and binocular stereovi- sion. Pablo J. et al [11] proposed using a new method to meas- ure the correlation of the deformation field. Finally, Guérin C. et al [12], use the digital surface models (DSMs) that create a geo-localized map of elevation changes of an urban scene from a set of couple images.


Ttwo images are used, the first is known as the reference im- age, the second is distorted. The steps of our approach are summarized in figure.1

2.1 Denoising by the Kalman filter

We will start by denoising step. The KALMAN filter Némesin
V. [13] is a recursive estimator. It has two distinct phases:
A phase of prediction using the estimated state of the previ-
ous time to produce an estimate of the current state, the phase
of updating the current observation of the state that is used to
correct the predicted state in order to obtain a more accurate estimate.

For i=1 to nb_iteration do

Kalmani,j = predictioni,j/(valredictioni,j - bruiti,j); Correctioni,j = gain*predictioni,j + (1-gain) * observa-

tioni,j + kalmani,j *(observationi,j - predictioni,j); Correction_vari,j = prediction_vari,j * (1- kalmani,j);

Prediction_vari,j = correction_vari,j; Predictioni,j = Correctioni,j;


IJSER © 2015

International Journal of Scientific & Engineering Research Volume 6, Issue Řǰȱ Ž‹›žŠ›¢-2015

ISSN 2229-5518


MOR  2( f1 f1 )  ( f 2 f 2 )


f1 f1


f 2 f 2

f i with i= 1,2 are vectors containing the pixel gray level of im- ages 1 and 2.

f i with i= 1,2 are the means.

After testing different window size correlations, we chose a window [7x7] with a search box dimension [17x17].

2.3.2 Correlation algorithm

Mi: the points of the first image.
Mj: the points of the second image.
F1: window of correlation centred on each point of the first
F2: window of correlation sliding on the second image
For each point Mi of image1 do
Center the window F1 on the point Mi
Choose an area of research in image2
For each point Mj of the search ZONE do:
Center the window F2 on the point Mj
Calculate correlation scores associated with the pixel
Mi (Either by measurement or normalized cross-correlation
centred or MORAVEC measurement).
Test the coefficient of maximum score
(The point Mi corresponding to Mj is one for which the

score is greater).

Fig. 1. Different steps of the approach

2.2 The Multi Resolution

A multi resolution approach was adapted; the model is based on a multi resolution wavelet decomposition obtained by Daubechies wavelets. Each multi temporal image is decom- posed into three levels of resolution; we apply our approach on the level of coarsest resolution. Coupling with a multi resolu- tion analysis allows a computational optimization while ap- proaching the performance of the original method.

2.3 Image Matching

The principle of the digital image correlation is shown in fig2. Two images are not taken under the same lighting conditions, or with identical cameras. It is therefore necessary to achieve more than one simple correlation of gray levels.

2.3.1 Similarity Measure based on Correlation

The cross-correlation coefficient is used to calculate a normal- ized correlation factor, which comes down to not comparing the levels of gray but rather the way in which these levels of gray vary. In our approach, we use the MORAVEC measure (robust

Fig. 2. Search for a match by correlation

The accuracy of displacement measurements depend on the performance of the correlation technique. Given the coordi- nates of the points in the original image and the coordinates of these physical points of the distorted image, obtained by cross- correlation technique, the displacement field and strain can be calculated.

2.4 The Measurement of the Displacement Fields

The deformations are estimated by a post treatment from dis- placement measure. After matching pairs of homologous points, the displacements are measured by subtracting the co- ordinates of the initial points and deformed.
to noise) and the centred normalized cross correlation measure
ZNCC (less expensive in computation time) Lane R A. et al [14].

ZNCC  ( f1 f1 )  ( f2 f2 )

x* x  x

 y* y  y

x x* x

 

y y* y


f1 f1

2 2

. f2 f2

Thus, the displacement is represented by

 x

( x)   

IJSER © 2015

 y


International Journal of Scientific & Engineering Research Volume 6, Issue Řǰȱ Ž‹›žŠ›¢-2015

ISSN 2229-5518


In our method disparity at the point x is represented by the norm displacement vector at the point x (Euclidean distances).

2.5 The Calculation of the Deformation Fields

Now we describe the deformation model used. The state of de-

x2 F11.x2 F12 .y2


 y2 F21 .x2 F22 .y2

After solving the system

x* F .x F .y

1 11 1 12 1


formation can be described by a tensor of deformation defined



F21.x1 F22 .y1

to any point. We talk of a deformation field. To deduce the de-
formation at a point, two approaches are used

2.5.1 Averaging of deformation of triangular elements in the vicinity:

x2 F11.x2 F12 .y2


y2 F21.x2 F22 .y2

y .x* y .x*

F 2 1 1 2

11 x .y

x .y

The deformations of the considered point correspond to the av-
erage value of distortion of the triangular elements. There are
two approaches as illustrated in figure. 3. The coefficients as-

1 2 2 1

( x .x* )  x .x*

F 2 1 1 2

signed to the elements of figure. 3 correspond to the value of the

12 x .y

x .y

deformation of the triangular element.

1 2 2 1

y .y * y .y *

F 2 1 1 2

21 x .y

x .y


1 2 2 1

( x .y * )  x .y *

F 2 1 1 2

22 x .y

x .y


1 2 2 1

From the deformation gradient tensor [F] the Cauchy-Green tensor is defined as:



(a) (b)

In contrast to [F] which can be non-symmetric [C] is a symmet- ric tensor such that:

Fig. 3. (a) Localized structure, (b) diagonal structure 2 2

Principle of calculati on of the deformat ion of a tri an-

gular element :

Calculations of deformations are made on triangular elements,

C11 F11 F12

C12 C21 F11.F21 F12 .F22

C22 F21 F22

(13) (14)

2 2

assuming that each triangle submitted a homogeneous defor-
A change of reference must be effected in order to express the
The Green-Lagrange tensor is given from [C] by



coordinates of the triangle points (x0 x1 x2 ) . Changes in the refer-

ence are effected so that the point whose deformation we are

[E] 

.([F ].[F ]T  [I ])


2 2

trying to calculate is the origin of referee x0, x1 is on the x-axis

and x2 is on vertical axis. A point of initial coordinates

(x1 , y1 ) , in a homogeneous deformation will be coordinated

( x* , y* ) .



F11 F21  1


F11.F12 F22 .F21



1 1


F11.F12 F22 .F21


F is a second order tensor called deformation gradient such



F 2 F 2  1



E22  2

F   11




The principal deformations are given by:

Components ( x* , y* ) and ( x* , y* ) can be written as follows:

I  ln(E11 E22

(E11 E22 )

 (2.E12 )

)  1


x *

1 1 2 2

F11.x1 F12 .y1


 ln(E11




) 2  (2.E

) 2 )  1


 y * F .x F .y

So deformations along the normal and tangent are represented

IJSER © 2015

International Journal of Scientific & Engineering Research Volume 6, Issue Řǰȱ Ž‹›žŠ›¢-2015

ISSN 2229-5518


by the vector I .


The deformations at the point x are represented by the norm of the deformation vector at point x (Euclidean distances).

2.5.2 Centred finite differences

Deformations are calculated from displacement measure at 3 and 5 points.
Centred finite differences at 3 points:

Fig. 5. Disparity map using our method (a) with CCNC (b) with measure-

U n1 U n1



ment of MORAVEC.

Centred finite differences at 5 points:

n 2 n1 n1 n2


Where s is a constant representing the difference in position of
adjacent points, and U i
their displacement.


We present an experimental result to see the deformation achieved in a multi temporal image pair.

(a) (b)

(c) (d)

Fig. 4. The pair of original images (a,b), the pair of approximate images after the wavelet analysis (c,d).

Fig. 6. Deformation field calculated by centred finite differences.

Fig.7. The deformation field calculated by the average strain of triangular elements of the localized structure.

IJSER © 2015

International Journal of Scientific & Engineering Research Volume 6, Issue Řǰȱ Ž‹›žŠ›¢-2015

ISSN 2229-5518



In this paper, we have presented a new method for matching based on the conservation of optical flow using a cross-correla- tion technique. These contributions are demonstrated and these performances are evaluated on real data.
We use a framework for effective minimization of both multi resolution and denoising. This efficient optimization scheme offers new perspectives for image matching applica- tions. The multi resolution reduces the computation time wi- thout degrading the estimation of deformation since our ap- proach is based on a dense matching technique.
We can draw multiple conclusions from this work:
 The correlation is an attractive means as it is accurate and
sensitive, but the correlation coefficients require a very large computation time for their estimation; for this rea- son, a multi-resolution scheme was adopted.
 The approach allows both matching and an estimation of
deformation at each point using a technique of dense mat- ching.
 The analysis of the deformation field is used to detect and
characterize changes.
 The deformations have been calculated according to the
results of the correlation, based on the conservation of op- tical flow.
 Our method is suitable for finding the deformations in-
cluding changes that are due to shots of the same scene spaced in time.
 Follow up in the use of this method will consist of work
to be carried out at multiple resolution levels.

Offsets andFault -Trace Mapping Using Phase Correlation of IRS Satellite Im- ages: The 1999 Izmit (Turkey) Earthquake,” IEEE Transactions on geosciences and remote sensing, vol. 48, pp. 2242-225, 2010.

[12] Guérin C., Binet R. and Pierrot-Deseilligny M., “Détection des changements

d’élévation d’une scène par imagerie satellite stéréoscopique,” Article pub- lished in "RFIA (Pattern Recognition and Artificial Intelligence) Lyon, France,


[13] Némesin V., “Estimation robuste du filtre de Kalman couple,” GSM Team, Fresnel Institute (UMR 6133). Saint Jérôm University, 2007.

[14] Lane R A., Thacker N A. and N L Seed., “Stretch-correlation as a real-time al- ternative to feature-based stereo matching algorithms,” Image and Vision Computing, vol. 12, pp. 203-212.


[1] Vincent, L., “Gestion des occultations en réalité augmentée,” doctoral thesis, Honri Poincaré University. Nancy I, 2001.

[2] Chambon, S., “Mise en correspondence stéréoscopique d'images couleur en présence d'occultations,” doctoral thesis. University of Toulouse III, 2005.

[3] Peters W. H. and Ranson W. F.,“ Digital imaging techniques in experimental stress analysis,” Opt. Eng, vol. 21, pp. 427-431, 1982.

[4] Chu T. C., Ranson W. F. and Sutton M. A.,“Applications of digital image-cor- relation techniques to experimental mechanics,” Exp. Mech, pp. 232-245, 1985.

[5] Crouzil A., Chambon S., “Mesures de corrélation pour des images couleur,” Institute for Research in Computer Science of Toulouse. Paul Sabatier Univer- sity, 2005.

[6] Zhao F., Huang H., Gao W., “Image matching by normalized cross-correla- tion,” IEEE ICASSP, vol. 2, pp. 729-732, 2006.

[7] Rziza M., Aboutajdine D., Mrin L. and Tamtaoui A., “Schèma multi résolution d’un champ de disparité dense sous contrainte epipolaire pour les images bruitées,” Colloques sur le Traitement du Signal et des Images GRETSI, 2001.

[8] Qin X., Li Li. And Tian, S., “A new image matching algorithm with modified greedy algorithm for remote sensing imagery,” ISPRS Workshop on Service and Application of Spatial Data Infrastructure, Hangzhou, China, 2003.

[9] Fookes C., Bennaoun A. and Lammna A., “Improved stereo image matching using mutual information and hierarchical prior probabilities,” IEEE Pattern Recognition, vol. 2, pp. 937-940, 2002.

[10] Hu Hao, Liang Jin, Liu Jianwei, Xiao Zhenzhong and Tang Zhengzong, “Three-dimensional Deformation Measuring System Based on Vision Method,” International Conference on Mechanical and Electrical Technology (ICMET), 2010.

[11] Pablo J., González M., Stramondo S. and Fernández J., “Coseismic Horizontal

IJSER © 2015