气象卫星图像导航的地标匹配算法研究与优化

郭强，杨磊，赵现纲，冯小虎，林维夏，张志清，魏彩英

国家卫星气象中心，北京 100081

气象卫星图像导航的地标匹配算法研究与优化

郭强，杨磊，赵现纲，冯小虎，林维夏，张志清，魏彩英

国家卫星气象中心，北京 100081

1 引言

气象卫星是重要的天基气象观测平台，广泛应用于气象业务、环境监测、防灾减灾、军事活动、科学研究等领域。气象卫星按轨道的不同分为静止轨道气象卫星和极轨气象卫星。我国是世界上少数几个同时拥有静止和极轨气象卫星的国家之一，与美国、欧盟一起构成全球气象卫星观测系统。目前，我国发展的气象卫星有风云二号静止轨道气象卫星、风云一号和风云三号极轨气象卫星，以及正在研究的新一代风云四号静止轨道气象卫星，在轨运行的卫星达到7颗[1]。

气象卫星利用星上搭载的可见光和红外扫描辐射计获取卫星遥感图像，经过预处理的图像导航得到精确的图像定位信息。目前，国际上气象卫星大多采用基于地标匹配的图像导航技术来保证定位精度，以获得高质量的卫星定量产品。地标导航有人工地标导航和自动地标导航两种方法。人工地标导航通过人工选取地标进行交互式地标导航[2-3]，需要大量的重复性人力劳动，不能保证准确性和一致性，无法满足实时、自动、准确的地标导航要求。因此，国内外科学家对自动地标导航技术进行了大量研究[4-7]。Emery等人针对极轨气象卫星观测数据开展了自动地标导航方法的研究[4]，美国SSEC对静止轨道GOES卫星设计了自动地标导航系统[5]，杨磊等分别研究了我国静止和极轨气象卫星的自动地标导航方法[6-7]，这些研究工作成为实现我国气象卫星自动地标导航系统的基础。

地标匹配算法主要有基于边界的匹配方法[8]、基于特征的地标匹配方法[9]和基于灰度相关的地标匹配方法[4，6-7]等。其中，基于相关的地标匹配方法在地标导航中应用最为广泛，该方法易于实现，匹配精度高，但计算量大。在自动地标导航方法的研究中，针对地标匹配算法研究及优化的讨论并不多。Emery等利用基本的最大互相关方法进行卫星图像自动导航[4]，杨磊等利用最大互相关地标匹配方法设计了我国气象卫星的自动地标导航系统[6-7]，朱永松等研究了基于相关系数的图像匹配算法和改进方法[10]，刘莹等讨论了灰度相关图像匹配算法的改进方法[11]。本文在此基础上，针对气象卫星遥感图像的特点，采用最大互相关地标匹配算法，综合利用计算优化、搜索优化、并行优化等技术，有效降低算法复杂度，提高算法执行效率，以满足气象卫星图像自动地标导航的定位精度和实效性要求。

2 自动地标导航

气象卫星的自动地标导航功能是基于地标匹配进行卫星图像导航来实现的。风云二号静止轨道气象卫星的自动地标导航中，实时卫星遥感图像采用标称图数据，地标模板图像由许多有明显特征的地标组成，可以从标准的海陆地标模板库中提取，与卫星图像有相同的投影方式。根据地标信息，在实时卫星图像中提取对应的地标区域数据，并利用云检测处理剔除云污染因素，以避免造成图像导航偏移。对卫星地标区域图像与地标模板图像进行自动匹配，利用地标匹配算法计算地标偏移量。完成对标称图中所有地标点的匹配后，经过质量控制得到有效的偏移结果，然后对卫星图像重新导航，得到精确的图像定位结果。

图1是风云二号气象卫星图像自动地标导航的流程图。极轨气象卫星自动地标导航的处理过程与静止轨道气象卫星大致相同。

图1 风云二号气象卫星图像自动地标导航流程图

3 地标匹配方法

3.1 地标匹配算法

地标匹配是利用图像匹配算法在实时卫星图像中寻找与地标模板图像相同或相似区域的过程，可以得到实际图像相对于标准地标模板图像的偏移量。地标匹配算法主要有基于特征的地标匹配方法、基于灰度相关的地标匹配方法、基于边界的匹配方法等。基于特征的地标匹配方法，通过从原始图像中提取点、线、区域等显著特征作为匹配基元来进行特征匹配，该算法的效率较高，但匹配精度不够。基于相关的地标匹配方法利用空间域的一维或二维滑动模板进行图像匹配，该算法易于实现，匹配精度高，但通常计算量较大[10]。

考虑到气象卫星遥感图像需要很高的定位精度，通常采用基于灰度相关的地标匹配方法来进行图像导航。相关匹配算法主要有最小误差法和相关系数法等方法，前者利用图像之间的差别程度进行匹配，而后者利用图像之间的相似程度进行匹配。最小误差法在卫星图像区域中搜索与地标模板图像绝对差最小的位置，作为地标匹配位置，算法计算速度快，但可靠性低，无法满足卫星图像导航的高可靠性要求。相关系数法将地标模板图像在实时卫星图像上滑动，计算每一位置上对应的相关系数值，选取相关系数最大的点作为地标匹配点，相关系数描述了图像间的线性相似度。相关系数法在地标导航中应用最为广泛，该方法易于实现，匹配精度高，但计算量大。本文将对这一算法进行优化，以满足自动地标导航应用需求。

3.2 基于最大相关系数的地标匹配算法

对于给定的卫星图像f(x,y)和地标模板图像w(x,y)，图像大小分别为M×N和J×K，如图2所示。基于最大相关系数的地标匹配算法的基本原理是在卫星图像中搜索与标准地标模板图像相匹配的位置，将地标模板图像w(x,y)作为一个空间滤波器在卫星图像f(x,y)中的每个位置计算相关系数R(x,y)。为克服相关系数随幅度的变化，采用归一化互相关系数（Normalized Maximum Cross Correlation），即

图2 地标模板与卫星图像在(x0,y0)位置的匹配

其中x=0,1,…,M-1，y=0,1,…,N-1，fˉ为地标模板与卫星图像重叠区域的像素平均值，wˉ为地标模板图像的像素平均值，求和运算在w和f重叠区域内进行。归一化互相关系数R(x,y)在[-1,1]范围内，相关系数越接近于1，代表图像匹配的相似度越高。

4 地标匹配算法优化

根据最大相关系数匹配算法的原理，可以看到其处理过程需要在图像范围内每个可能的位置进行搜索计算，而且相关系数求取也涉及到大量的计算。通过对式（2）的分析，可以得到一次地标匹配过程所需要的计算量：加法运算约12MNJK次，乘法运算约3MNJK次。由于在整个图像上进行相关系数计算，这种传统的地标匹配算法计算速度慢，算法复杂度高，有待进一步优化。

地标匹配算法的优化研究，可以从降低算法复杂度和提高算法计算速度两个方面来开展。由于地标匹配算法的计算量与相关系数计算和搜索位置数直接相关，所以利用计算优化和搜索优化来降低算法复杂度。另一方面，针对地标匹配算法的特点，对图像进行分区并行处理，利用并行计算来提高算法计算速度。

4.1 算法复杂度优化

地标匹配算法最佳匹配位置的搜索过程中包括很多重复和无效的计算，搜索范围过大也是影响算法复杂度的直接原因。针对算法的特点，在保证地标匹配精度前提下，通过减小相关系数运算量和搜索范围来降低算法总的计算量。

（1）计算优化

归一化互相关系数的计算优化可以通过简化相关系数的计算公式和去除冗余计算来实现，即通过优化A和优化B的处理过程来完成。

优化A：简化相关系数计算。根据式（1），相关系数公式的分子为协方差，分母可以通过方差求得，简化方差和协方差的计算过程可以减少计算量[13]。根据式（2）将协方差和方差展开并进行简化后，可以分别得到式（3）和式（4）。

协方差计算简化：

优化B：去除冗余计算。相关系数计算中涉及到大量重复和无效的冗余计算，可以通过下面的方法进行优化：在一次地标匹配过程中，地标模板图像保持不变，地标模板图像的像素平均值wˉ只计算一次；在实际卫星图像窗口范围内计算相关系数时，模板图像方差为常数，可提前计算并直接代入运算；相关系数计算中分子协方差小于零时相关系数为负值，图像之间的匹配程度很小，此位置不是匹配点，可以不进行后续的方差计算等处理。

经过上述处理去除冗余计算后，相关系数计算量将大大减少。假设相关系数为正值的概率为X，那么单独利用此优化步骤可以使相关系数的计算量降低为：

加法运算6MNJK+2XJK(MN+2MK+2JN-2JK)次；乘法运算MNJK+XJK(MN+MK+JN-JK)次。有效剔除了冗余计算。

（2）搜索优化

在图像范围内进行相关系数运算的搜索位置数是影响地标匹配算法复杂度的另一重要因素。为减少计算量，采用网格搜索（Grid Search）算法对搜索范围进行优化。

优化G：采用网格搜索算法。

为保证地标匹配的精度，选取网格搜索步长为2，尽量覆盖图像区域。在每个格点位置计算相关系数，找到最大相关系数对应的格点Gm，然后求取原图像中Gm周围各点对应的相关系数，这些点中有相关系数最大的就是最佳的匹配位置。具体的网格搜索步骤如下：

步骤1遍历图像网格各个位置，计算各格点对应的相关系数，得到相关系数矩阵RG。

步骤2在RG中搜索具有最大相关系数GRm(xm,ym)的格点位置。

步骤3在原图像区域中计算(xm,ym)周围8个点的相关系数，取9个点中相关系数最大者为匹配点。

根据卫星图像的特点，地标匹配位置邻近范围内各点对应的相关系数也比较大，其变化过程是渐变的。由于搜索步长为2，这种网格搜索算法可以基本覆盖到每个可能的地标匹配位置，最大程度地保证地标匹配的精度。通过搜索优化，算法搜索位置数可以减少到原来的1/4。

利用计算优化和搜索优化降低算法复杂度后，地标匹配算法的计算量减少为：

加法运算约MNJK+(1/4)XJK(MN+3MK+3JN-3JK)次；乘法运算约(1/4)[MNJK+XJK(MN+MK+JN-JK)]次。

可以看到，优化地标匹配算法相对于经典算法的计算量大大减少，有效降低了算法的复杂度，提高了相关系数的计算速度。

4.2 并行地标匹配算法

根据地标匹配算法的特点，在图像各个位置的相关系数计算是相互独立的，利用这种低耦合性可以在图像上进行分区处理。采用并行计算技术[14]，充分利用处理器资源，多线程并行地在不同图像区域上计算相关系数，可以大大提高算法的执行效率，缩短地标匹配时间。

优化P：并行优化。地标匹配算法的并行优化（Parallel Optimization）思路如下：将卫星图像划分为n个均匀大小的区域，可以按行、列分割，或者行列同时分割；对每一个图像区域调用一个线程进行处理，计算得到的相关系数存储到统一的相关系数矩阵R中；等待所有线程计算完成后，调用后续的算法处理指令计算地标匹配位置。并行计算的图像区域划分如图3所示，其中实线和虚线分别代表行和列方向的图像划分，黑点表示网格搜索时的匹配点，白点表示其周围的8个像素点。由于同时采用网格搜索优化，图像划分的粒度不能太大。如果采用双线程进行并行计算，相关系数计算将节省近一半时间。

图3 并行计算的图像区域划分示意图

综合利用上述的计算优化、搜索优化和并行优化步骤，得到改进的最大互相关地标匹配算法。经过优化的地标匹配算法，能够保证算法精确性和稳定性的同时，有效降低算法复杂度，提高算法的执行效率，满足卫星图像导航的高可靠、高时效性要求。

5 实验分析

为验证优化地标匹配算法的性能，利用FY-2D气象卫星2012年10月11日UT04：30（世界时）的多通道扫描辐射计可见光图像数据对算法进行测试。选取实际卫星图像区域的大小为201像素×201像素，地标模板图像的大小为51×51，如图4所示。卫星图像相对于地标模板图像的实际偏移量在东西方向和南北方向预置为0，便于进行地标匹配精度测试。算法搜索优化的网格步长选为2，以保证地标匹配的准确性。算法并行优化采用双线程并行计算，卫星图像在行方向以图像中心点划分为南北两个区域，并行进行相关运算，提高算法执行效率。

图4 待匹配的卫星图像区域和地标模板图像

算法实验分析的步骤如下：第一步，利用经典的最大互相关地标匹配算法进行地标匹配，测试经典算法的执行效率。第二步，利用简化的相关系数计算公式进行算法测试，验证优化A步骤的效果。第三步，测试去除冗余计算后的算法性能，即单独进行优化B步骤的结果。第四步，测试计算优化后的算法性能，即同时利用优化A和优化B步骤对算法性能的改进。第五步，利用优化G的网格搜索对经典算法进行改进，测试优化后的算法性能。第六步，利用优化P的并行计算对经典算法进行改进，测试并行算法的运算性能。第七步，验证经过计算优化和搜索优化降低算法复杂度后算法的执行效率，即同时利用优化A、优化B和优化G步骤。最后，对综合利用计算优化、搜索优化和并行优化后的算法进行测试，验证优化地标匹配算法的性能，并对算法执行效率进行对比分析。

地标匹配算法的性能测试结果见表1。可以看到，经过相关系数计算简化后的算法性能略有提高，这是因为优化步骤A只减少了加法运算，而乘法运算量保持不变，对算法性能的改进有限；经过优化B去除冗余计算后，算法性能大约提高了一倍，这是因为经典地标匹配算法中含有大量的重复和无效运算；利用搜索优化进行网格搜索，搜索位置数减少到原来的1/4，所以算法执行时间也减少到原来的1/4左右；同时利用计算优化和搜索优化的改进算法，性能进一步明显提高；利用双线程的并行计算技术，可以将原始算法的执行速度提高近一倍，加速比达到1.83；经过综合优化的算法性能大大提高，一次地标匹配过程的执行时间只有经典算法的6.68%。如果改变搜索优化和并行优化策略，算法性能还有很大的提升空间。图5是对应的地标匹配结果，由图中相关系数的空间分布可见，最大的相关系数值出现在最佳地标匹配点附近，输出的最佳地标匹配点和偏移量与预设参数一致，地标匹配算法有很高的精确度。根据实验分析结果，本文提出的优化地标匹配算法能够在保证地标匹配精度的同时，有效降低算法复杂度，明显提高执行效率，满足卫星自动地标导航系统的可靠性和时效性要求。

表1 地标匹配算法性能对比

图5 地标匹配结果

6 结束语

本文讨论了气象卫星图像导航的地标匹配算法优化问题，针对地标导航系统和卫星遥感图像的特点研究了地标匹配的方法，采用基于最大相关系数的地标匹配算法来保证匹配精度。在此基础上，对地标匹配算法的优化方法进行了深入研究，通过相关系数的计算优化和搜索优化，简化计算过程，去除冗余计算，减少搜索量，有效降低了算法的复杂度。利用并行优化，在图像范围内进行分区并行计算，显著提高了算法的执行效率。测试结果表明，利用该算法能够快速完成地标匹配，同时有很高的匹配精度，能够满足卫星图像自动地标导航的应用需求。

[1]许健民，杨军，张志清，等.我国气象卫星的发展与应用[J].气象，2010，17（3）：94-100.

[2]Illera P，Delgado J A，Calle A.A navigation algorithm for satellite images[J].International Journal of Remote Sensing，1996，17（3）：577-588.

[3]Ho D，Asem A.NOAA AVHRR image referencing[J].International Journal of Remote Sensing，1986，7（6）：895-904.

[4]Emery W J，Baldwin D G，Matthews D.Maximum cross correlation automatic satellite image navigation and attitude corrections for open ocean image navigation[J].IEEE Transactions on Geoscience and Remote Sensing，2003，41（1）：33-42.

[5]SSEC.McIDAS navigation manual[Z].Madison：University of Wisconsin-Madison，1986.

[6]杨磊，冯小虎，郭强，等.风云二号气象卫星图像自动几何精校正[J].计算机工程与应用，2011，47（3）：202-206.

[7]杨磊，杨忠东.极轨气象卫星自动地标导航方法[J].应用气象学报，2009，20（3）：329-336.

[8]Eugenio F，Marque S F.Automatic satellite image georeferencing using a contour-matching approach[J].IEEE Transactions on Geoscience and Remote Sensing，2003，41（12）：2869-2880.

[9]Dai Xiaolong，Korran S.A feature-based image registration algorithm using improved chain-code representation combined with invariant moments[J].IEEE Transactions on Geoscience and Remote Sensing，1999，37（5）：2351-2362.

[10]朱永松，国澄明.基于相关系数的相关匹配算法的研究[J].信号处理，2003，19（6）：531-534.

[11]刘莹，曹剑中，许朝晖，等.基于灰度相关的图像匹配算法的改进[J].应用光学，2007，28（5）：536-540.

[12]Gonzalez C R.Digital image processing[M].2nd ed.[S.l.]：Publishing House of Electronics Industry，2003.

[13]Sun Changming.Multi-resolution rectangular subregioning stereo matching using fast correlation and dynamic programming techniques，CMIS Report No.98/246[R].1998.

[14]Grama A，Gupta A，Karypis G，et al.Introduction to parallel computing[M].2nd ed.Pearson：Addison Wesley，2003.

GUO Qiang,YANG Lei,ZHAO Xiangang,FENG Xiaohu,LIN Weixia,ZHANG Zhiqing,WEI Caiying

National Satellite Meteorological Center,Beijing 100081,China

This paper studies the landmark matching algorithm in automatic landmark navigation system of the meteorological satellite.The landmark matching algorithm based on maximum correlation coefficient method is used to guarantee the matching precision.The optimized algorithm is proposed using computing optimization,search optimization and parallel optimization comprehensively.The experimental results show that this algorithm can effectively reduce the complexity of the algorithm and significantly improve the execution efficiency.The optimized algorithm can meet the high reliability and time-sensitive requirements of automatic landmark navigation system,and guarantee the matching precision at the same time.

automatic landmark navigation;landmark matching;maximum correlation coefficient;algorithm optimization

对气象卫星图像自动地标导航系统中的地标匹配算法进行了深入研究，采用基于最大相关系数的地标匹配算法来保证匹配精度，综合利用计算优化、搜索优化、并行优化等技术得到优化的地标匹配算法。实验结果表明，该算法能够有效降低算法复杂度，明显提高算法执行效率，同时保证地标匹配的准确性，满足自动地标导航系统的高可靠性和高时效性需求。

自动地标导航；地标匹配；最大相关系数；算法优化

A

TP751

10.3778/j.issn.1002-8331.1305-0212

GUO Qiang,YANG Lei,ZHAO Xiangang,et al.Research and optimization of landmark matching algorithm for meteorological satellite image navigation.Computer Engineering and Applications,2013,49（24）：152-156.

国家公益性行业（气象）科研专项（No.GYHY201006046）。

郭强（1986—），男，工程师，研究领域为卫星通信和高性能计算；杨磊（1978—），男，博士，副研究员，研究领域为遥感图像处理和模式识别；赵现纲（1976—），男，博士，高级工程师，研究领域为计算机应用；冯小虎（1970—），男，高级工程师，研究领域为卫星地面应用系统。E-mail：cscowboy@126.com

2013-05-17

2013-08-27

1002-8331（2013）24-0152-05

CNKI出版日期：2013-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20131011.1653.009.html