### Paper Menu >>

### Journal Menu >>

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. Email: ythtxia@163.com 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 Copyright © 2013 SciRes. JSEA 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 Copyright © 2013 SciRes. JSEA 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, Copyright © 2013 SciRes. JSEA 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- Copyright © 2013 SciRes. JSEA Robust Performance of Scene Matching Algorithm Copyright © 2013 SciRes. JSEA 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. |