A Journal of Software Engineering and Applications, 2013, 6, 6-10
doi:10.4236/jsea.2013.65B002 Published Online May 2013 (http://www.scirp.org/journal/jsea)
Robust Performance of Scene Matching Algorithm*
Zhaohui Xia, Xiaogang Yang, Fei Meng, Shicheng Wang
Xi’an Research Inst. of High-tech, Xi’an, China.
Received 2013
ABSTRACT
Performance analysis is very important in the study and design of scene matching algorithm. Based on the analysis of
the common performance parameters, robustness of scene matching algorithm is defined, including the definitions of
robust stability and robust performance, and the corresponding evaluation parameters matching margin and matching
adaptability are given. With application of these robustness parameters on 8 scene matching algorithms, quantitative
analysis results of algorithm robustness are obtained. The paper provides an important theoretical reference to the per-
formance evaluation of scene matching algorithm.
Keywords: Scene Matching; Matching Algorithm; Performance Parameters; Robustness; Performance Evaluation
1. Introduction
Scene matching guidance technology is not only an im-
portant way in precision-guided positioning of the air-
craft, but also an advanced and effective guidance ap-
proach proved by a series of missile weapons in several
actual combats [1,8]. The performance of the matching
algorithm is a key factor to determine the matching reli-
ability and accuracy of the scene matching system. Over
the years, domestic and foreign researchers have made
unremitting efforts in this area, and many scene matching
algorithms with superior performance were proposed
[1-8,10,13]. The emergence of a large number of match-
ing algorithms is bound to lead to another important re-
search topic, namely matching algorithm performance
analysis and evaluation, which requires focused on solv-
ing two problems, the first is what the algorithm per-
formance parameters are, and the second is how to cal-
culate these parameters. The matching probability, match-
ing accuracy, matching time and other parameters having
been assumed quantitatively under certain experimental
conditions, the reliability, accuracy and real-time per-
formance of matching algorithms were evaluated respec-
tively in the design and studying algorithms in most of
the literatures [1,2,8,10]; and many other literatures pro-
posed the calculation methods of the parameters under
laboratory conditions or building methods of simulation
environment [9,11,12]. These index parameters and
simulation methods undoubtedly provided an important
theoretical basis and technical reference for performance
evaluation of matching algorithms and put a strong for-
ward to research and design of matching algorithm. But
considering the scene matching system influenced by vari-
ous disturbances, it is necessary to further study the anti-
interference capability of matching algorithm, or robust-
ness, to provide the analysis reference and decision-
making for practical applications. Many references pre-
sented robustness and adaptability of the algorithms,
which, however, were limited to qualitative description,
and did not give the mathematical definition and calcula-
tion method [2,8,10]. Based on the summarization and
analysis of the common performance parameters of scene
matching algorithm, and referred to the conception of
algorithm robustness in robust control theory, this paper
presented a definition of robustness of scene matching
algorithm, which was described quantitatively from ro-
bust stability and robust performance. Through perform-
ance comparison and analysis of 8 kinds of scene match-
ing algorithms, the reasonableness of the definition was
verified to provide the important theoretical basis for
performance analysis of matching algorithm.
2. Definitions of the Robustness Parameters
of Scene Matching Algorithm
Usually, the performance index parameters of algorithm
are considered as the mathematical basis for algorithm
performance evaluation. The common performance pa-
rameters of scene matching algorithm are matching prob-
ability, matching accuracy, and matching time [2,8,10].
2.1. Basic Performance Parameters of Scene
Matching Algorithm
*Project supported by National Natural Science Foundation of China
under Grant No. 61203189.  The reliability index - the matching probability Pc

Robust Performance of Scene Matching Algorithm 7
The matching probability is defined as the ratio of the
number of correct matches
R
n to the total number of
matches , namely
T
n
R
cT
n
Pn . The correct match refer
to those matching result is within the required error range.
In the algorithm evaluation and simulation experiment,
the error ranges select 3 pixels generally. The higher the
matching probability is, the better the reliability of the
matching algorithm be.
 The precision index - the matching precision

The precision is also called the veracity of matching
algorithm. The matching precision requires the matching
error of the correct matching is as small as possible. For
a single match, suppose the ideal matching position is

11
,

x
y, and the actual matching position is


11
,
x
y

,
then the single positioning error is
2
11111
()( )
2
x
xyy 
  (1)
As for results of n-time matching, if the ideal matching
positions are

11
,
x
y,

22
,

x
y, …,

,
nn
x
y
11
, and the
actual matching positions are

,
x
y


2
, , 2

x
y , …,

,
nn

x
y

, the position error (,
12
,,
n)

  can be
calculated according to Eq. (1). The mean error, or the
matching positioning precision, is
1
1n
i
i
n



 (2)
Sometimes the error variance 2
e

is also used to
indicate the distribution of matching errors.
2
1
1(
n
ei
i
n)




 (3)
To be attention, when the matching error mean and the
error variance are solved by Eq. (2) and Eq. (3), calculation
can be implemented only under the correct position (i.e.
the single matching error i

is within the error range
for requirements), which is not the statistical value of all
the matching results.
 The rapidity index ─the matching time
M
T
The rapidity is the real-time performance of the matching,
which requires the matching algorithm is fast enough to
meet the real-time requirements for the application
environment. The matching time is the parameter index
to measure the complexity and computational quantity of
a matching algorithm. For a certain matching algorithm,
the impact factors for calculation are: computational
quantity of feature extraction processes, computational
quantity of similarity measure, and the scope of search
strategy. The matching time TM is the ratio of the total
matching time Ttotal of the algorithm matching experiments
to the matching times, namely,
T
ntotal
MT
T
Tn .
2.2. The Definitions of Robustness Parameters
The referred to the conception of algorithm robustness in
robust control theory [14], this paper presented the
definitions of robustness of scene matching algorithm,
which was described quantitatively from robust stability
and robust performance.
Definition 1: Robustness of the matching algorithm
The robustness of the matching algorithm refers to its
adaptability to the differences between the reference image
(or the sub-reference image) and the real-time image and
the matching uncertainties caused by various factors, such
as character differences with the multi-source images,
distortion interference, scene features and so on.
Definition 2: Robust Stability of the matching algori-
thm
Robust stability means that correct matching can be
achieved under the condition of certain difference between
the reference image and the real-time image. In order to
quantitatively describe the robust stability of the matching
algorithm, here we define a new parameter named Match-
ing Margin (MM), and denotes as RMM. RMM describes the
difference degree the reference image and the real-time
image with Similarity Signal Noise Ratio (SSNR). The
matching margin RMM can be calculated by Eq. (4).
max
1
MM
RSSNR  (4)
It can be seen, the matching margin of the matching
algorithm is the reciprocal of max
SS , which is the
maximum SSNR of error matching. SSNR is defined as
follows
NR
()
()
()
SStdX
SSNR NStd X
Std XYStd Y
 



(5)
where, is the standard deviation of the image,
and
(*)Std
X
is the mean reference image, and Y is the
mean real-time image.
For the reference image X, then
1/2
11 2
00
1
()((,))
mm
ij
StdXX ijX
mm










 (6)
It can be proved that the value SSNR is not changed if
X
and Y are exchanged. And this is the unique
character of SSNR which is different from other signal to
noise ratios. In the scene matching area, the similarity
analysis based on SSNR plays an important role.
Also we can see, the smaller max is, the greater
the matching margin is. This shows that the matching
algorithm can achieve the right match in the case of
small signal to noise ratio, and the algorithm has strong
anti-distortion-interference ability and good stability,
otherwise, its ability is poor.
SSNR

Robust Performance of Scene Matching Algorithm
8
Definition 3: Robust Performance of the matching
algorithm
Robust performance means that an expected matching
probability can be guaranteed with a certain difference
between the reference image and the real-time image. We
indicated this character of the matching algorithm as
Matching Adaptability (MA), denotes as
M
A
R, which
can be calculated by Eq. (7).
max
c
M
A
P
RP
SSNR

cMM
R
(7)
It can be seen, RMA is proportional to the matching
probability and the matching margin. When the SSNRmax
is same, the higher the matching probability is, the
greater RMA is. It shows that the algorithm has a strong
adaptability to distortion, otherwise it has weak ability.
Through the above definitions, a quantitative descrip-
tion on robustness, stability and adaptability of the scene
matching algorithm in the same framework can be ob-
tained, and the algorithm performance index system is
completed. In the following parts, according to the per-
formance analysis of the edge feature scene matching
algorithm, the reasonableness of these parameters is il-
luminated.
3. Performance Evaluation Experiment and
Analysis of the Matching Algorithms
In order to verify the reasonableness and effectiveness of
the definitions in this paper, here, performance compare-
son and analysis of several classic scene matching algo-
rithms are implemented. At present, various types of lit-
erature on the scene matching algorithm can be described
as dazzling variety. However, the scene matching guidance
system for aircraft, the most basic three algorithms are
the Mean Absolute Difference (MAD) algorithm, the
Mean Square Difference (MSD) algorithm, and the Nor-
malized Product correlation (NProd) algorithm, which
based on image gray-scale [8,9]. Meantime, considering
the multi-source characteristics of the matching images,
the edge feature matching algorithm is a very hot topic in
real research. Here the performances of several edge
feature matching algorithms are analyzed, which based
on Roberts operator, Sobel operator, Prewitt operator,
Laplacian operator and LOG operator. Firstly, the struc-
ture of the algorithm is described.
3.1. Scene Matching Algorithm Based on Edge
Feature
Roberts operator, Sobel operator, Prewitt operator, Lapla-
cian operator and LOG operator are in accordance with
the difference between the gray-scale of the current pixel
and the gray-scale of the around the pixel [15]. By using
the classical method of similarity measure Nprod [2] ,
five kinds of edge feature matching algorithms based on
NProd can be obtained. The basic structure of algorithm
is as follows.
Step 1: Initialization of input data and parameters.
RI_Height = height of reference image;
RI_Width = width of reference image;
RtI_Height = height of real-time image;
RtI _Width = width of real-time image;
Rmax = 0; // Initialization of Nprod coefficient;
Lx = 0; Ly=0；// Initialization of matching position
Step 2: Edge feature detection between real-time im-
age Y and reference image X
Step 3: Calculating of the mould of the edge feature real-
time image.
Step 4: Translation search matching in the edge fea-
ture reference image.
for（int u=0; u< RI_Height - RtI_Height +1; u++）
for（int v=0;v< RI _Width - RtI _Width +1;v++）
{when position (u,v) of sub-reference image X
being selected, Nprod coefficient of position (u,v) is cal-
culated);
if（Ruv>Rmax）//The first-max method is used
here.
{ Rmax= Ruv; Lx=u; Ly=v; } }
Step 5: Output matching position (Lx, Ly).
Where, if the second step is removed, the algorithm is
the classic NProd scene matching algorithm. Based on
various edge feature detection operators, different edge
strength scene matching algorithms can be obtained. To
simplify the description of the problem, corresponding to
the above five detection operators, 5 kinds of edge strength
matching algorithms are denote as RSNprod, PSNprod,
SSNprod, LSNprod, and LOGSNprod respectively.
3.2. Experiment and Analysis
A multiple group pairs between PIONEER satellite images
and real flight images which are similar to Figure 1 are
used to implement the matching experiment, and the
simulation method is referred to reference [9]. In the
experiments, the size of the experimental reference
image is 256 × 256, which is the satellite images, and the
size of the real-time image is 64 × 64, which is the flight
measured image. Since the acquisition platform and
acquisition conditions are different, there exists a big
difference between the reference image and the real-time
image, and there are strong distortions and noise in-
terference in the real-time image.
Through a large number of matching simulation ex-
periments, the performance parameters of various matching
algorithms are calculated, and the results shown in Table 1.
It can be seen form the matching performance parameters,
in the gray-scale matching algorithms, the performance
of MAD is the poorest, and MSD is followed, and NProd
is the optimal. In the edge feature matching algorithms,

Robust Performance of Scene Matching Algorithm 9
(a) The reference image (b) The real-time image
Figure 1. The images for matching simulation experiment.
Table 1. The Performance Parameters of the Edge Strength
Matching Algorithms.
Matching
algorithm
Matching
probability (%)
Matching
precision
(Pixels)
Matching
margin
Matching
adaptability
MAD 65.7 0.058 1/1.002 65.57
MSD 70.8 0.042 1/0.973 72.96
NProd 77.7 0.039 1/0.967 80.35
RSNProd 68.5 0.057 1/1.002 68.36
PSNProd 80.6 0.084 1/0.944 85.38
SSNProd 80.8 0.080 1/0.944 85.59
LSNProd 96.8 0.007 1/0.873 110.88
LOGSNProd 98.6 0.084 1/0.853 115.59
LOG operator has the strongest anti-ability of distortion
and the best robustness. This is inseparable with the
detection principle of the LOG operator with filtering
first and detecting later. From the view of positioning
accuracy, Laplasian operator has a high matching accuracy,
which shows the Laplasian edge strength detection and
location accuracy is better than other edge detection
operators. In contrast, matching performance is not im-
proved using Roberts operator for scene matching, indicat-
ing that the influence on matching performance caused
by information loss with Roberts edge detection is even
more than the difference of the image itself. Prewitt operator
and Sobel operator have strong robust to the gray-scale
distortion, but are more sensitive to noise interference.
As the matching time has a strong relationship with the
experimental environment, here quantitative results are
not given. In general, the complexity of the matching
algorithm is equal to sum of the complexity of feature
extraction algorithms and the complexity of matching
similarity measure. Above eight kinds of algorithms,
MAD, MSD, NProd are directly based on the gray-scale,
and the computation quantity of the similarity measure is
equal to that of the matching algorithm, by comparison,
there is less computation quantity. The computation
quantities of the edge strength matching algorithms are
equal to that of the edge detection algorithms added to
that of similarity measure. From the detection principles
of the operators, the computation quantity of Roberts
operator is the least, and the computation quantities of
other operators are to some tune, with a simple operation
and high real-time performance.
4. Conclusions
This paper studies the scene matching algorithm perfor-
mance evaluation index system, defines the robustness of
scene matching algorithm, including the robust stability
and robust performance, which were quantitatively de-
scribed by using the matching margin and the matching
adaptability.
Then from the perspective of scene matching algo-
rithm performance evaluation, the practicability of eight
kinds of edge strength matching algorithms in the weap-
ons systems were analyzed and evaluated, indicating that
the robustness of the matching algorithm can be quantita-
tively described with the matching margin and the match-
ing adaptability, including the adaptability to distortion
interference and the adaptability to scene feature changes.
Experimental results also show that, the edge strength
matching algorithms based on Laplasian operator and
LOG operator have stronger robustness, and the algo-
rithms are simple, and easy to implement, and they have
important application prospection in real-time matching
aircraft guidance.
REFERENCES
[1] R. Missaoui, M. Sarifuddin, et al., “Similarity Measures
for Efficient Content-based Image Retrieval,” IEEE Pro-
ceedings on Vision, Image and Signal Process, 2005, pp.
875- 887.
[2] G. Abdul, N. I. Rao, Shoab and K., “Robust Image
Matching Algorithm,” 4th EURASIP Conference focused
on Vider/ Image Processing and Multimedia Communica-
tions, 2003, pp. 155-160.
[3] J. Li and J. Ma, “An Improved Edge Detection Algo-
rithm,” Computer Development & Applications, Vol. 24,
No. 1, 2011, pp. 71-73.
[4] J. B. Wang, X. M. Lu and Z. He, “An Improved Algo-
rithm of Image Registration Based on Fast Robust Fea-
tures,” Computer Engineering & Science, Vol. 33, No. 2,
2011, pp. 112-117.
[5] Z. Xiong, F. Chen, D. Wang and J. Y. Liu, “Robust Scene
Matching Algorithm for SAR/INS Integrated Navigation
System Based on SURF,” Journal of Nanjing University
of Aeronautics & Astronautics, Vol. 43, No. 1, 2011, pp.
49-54.
[6] Z. G. Ling, Y. Liang, Q. Pan, H. Shen and Y. M. Cheng,
“A Robust Multi-level Scene Matching Algorithm for In-
frared and Visible Light Image,” Acta Aeronautica Et As-
tronautica Sinica, Vol. 31, No. 6, 2010, pp. 1185-1195.
[7] Y. Li and W. H. Zhang, “Study of Scene Matching Algo-
rithm Based on Edge Strength,” Tactical Missile Tech-

Robust Performance of Scene Matching Algorithm
10
nology, Vol. 2, 2010, pp. 59-63.
[8] B. Han and Y. M. Wang, “Research of Image Matching
Based on a Fast Normalized Cross Correlation Algo-
rithm,” Acta Armamentarii, Vol. 31, No. 2, 2010, pp.
160-165.
[9] Y. G. Yang, S. Zuo and X. X. Huang, “Integral Experi-
ment and Simulation System for Image Matching,” Jour-
nal of System Simulation, Vol. 22, No. 6, 2010, pp.
1270-1273.
[10] S. M. Zhang, Y. Chen and Y. Lin, “Robust Algorithm of
Matching SAR Image to Optical Image Using Multiple
Subarea,” Journal of Tongji University, Vol. 37, No. 1,
2009, pp. 121-125.
[11] F. Meng, X. G. Yang and P. Sun, “A Novel Filtering and
Fusion Algorithm for Sequence Image Matching Naviga-
tion,” 2008 International Congress on Image and Signal
Processing, Vol. 4, 2008, pp. 668-671.
[12] X. B. Wang, G. S. Xu and S. W. Liu, “Research on the
Simulation of Forward-looking Image in the Infrared Im-
aging Guidance,” Infrared and Laser Engineering, Vol.
35, No. 10, 2006, pp. 68-72.
[13] F. W. Zhao, J. C. Li and Z. K. Shen, “Study of Scene
Matching Techniques,” Systems Engineering and Elec-
tronics, Vol. 24, No. 12, 2002, pp.111-114.
[14] K. M. Zhou, J. C. Doyle and K. Glover, Robust and Op-
timal Control. Prentice Hall, Englewood Cliffs, New Jer-
sey, 1996.
[15] Y. J. Zhang, “Image Engineering (2): Image Analysis,”
Tsinghua University Press, 2005.