冯 斌，邓新蒲，马 超

FENG Bin,DENG Xinpu,MA Chao

国防科学技术大学 电子科学与工程学院，长沙410073

College of Electronic Science and Engineering,National University of Defense Technology,Changsha 410073,China

1 引言

遥感图像地标匹配是利用图像匹配算法在遥感图像中寻找与地标模板图像相同或相似区域的过程。基于地标匹配的卫星图像导航系统[1-2]、无人飞行器定位系统[3-6]主要采用图像匹配技术来保证定位精度。杨磊、郭强等[1-2]对我国气象卫星地标自动导航的方法进行了深入的研究，李耀军、吉祥等[3-4]对无人飞行器定位的方法进行了详细的研究；Mostafa 等[5-6]对基于特征的遥感图像匹配技术在定位系统的应用进行了全面的研究。这些研究为遥感卫星自动导航、无人飞行器定位奠定了基础。

文献[7-11]对图像匹配技术的原理、方法以及研究进展作了较为全面的分析和总结。文献[8]中基于Hausdorff距离来进行边缘图像匹配的方法，是通过计算边缘图像边缘点的Hausdorff 距离来衡量两幅边缘图像的相似程度，具有较好的可靠性，但计算复杂。文献[12]提出一种基于边缘的相似距离（ESD）进行图像匹配的方法，该方法的实质是统计两边缘图像具有相同像素点的个数，具有较高的可靠性和鲁棒性，但对边缘提取精度要求较高。文献[13]提出了改进的距离变换的图像匹配方法，能使正确匹配位置的相关峰更显著，但计算量大。

本文提出边缘距离扩展和设置相似门限的距离变换方法，通过优化距离计算和区域搜索，减少了匹配计算时间，提高了算法匹配效率，与文献[14]中传统的距离变换算法以及文献[13]中改进距离变换算法作比较实验，结果表明本文算法在保证匹配精度的基础上，计算时间有很大优势。

2 地标边缘匹配算法

2.1 基于距离变换的地标边缘匹配算法

基于距离变换的地标边缘匹配算法是以地标边缘图像边缘点之间的距离测度作为相似性度量的一种匹配方法。

算法的基本原理：

（1）对地标模板图像和遥感图像进行边缘检测，转化为二值的边缘图像。

（2）计算地标模板边缘图像上所有边缘点到遥感边缘图像对应子图的边缘点的最小距离，并在当前搜索位置上记录最小距离的值，其余非边缘点位置值均为0，生成距离变换图像。如图1 所示，地标模板边缘图像1（b），计算其边缘点到图1（a）所示遥感边缘图像子图中距其最近的边缘点的距离，得到距离变换图上相应位置的值，结果如图1（c）所示。

图1 距离变换图生成示意图

对于平移量(i,j)，记地标模板边缘图像I1上点p到遥感边缘图像的子图I2上点q的最小距离为dij(p)，则有dij(p)=min{dij(p,q)}，其中p∈I1，q∈I2，dij(p,q)为在该平移量下p点和q点之间的距离（街区距离）。

（3）计算地标模板边缘图像上所有搜索位置上记录值的算术平均值。

其中，N为地标模板边缘图像的边缘点的数量，D(i,j)是相似性度量，表示匹配程度，D(i,j)的值越小，匹配度越高。

（4）在遥感边缘图像上遍历，寻找最佳匹配位置，即

在D(i,j)取得最小值时匹配度最高，为最佳匹配位置。对于完全匹配的情况，即边缘重合度最大时，D(i,j)趋于零或等于零。

2.2 算法性能分析

通过对算法基本原理分析可以得知，该算法存在求取最小距离值计算量大、重复冗余计算多和遍历计算相似度量值效率低等问题[2]。

（1）求取最小距离值计算量大

dij(p,q)计算需要遍历图像I1和I2上的所有边缘点才能求取最小距离值dij(p)，计算量大。以图1 为例，地标模板I1边缘点的数量为9，遥感边缘图像子图I2的边缘点数量为7，此时，遍历两图像边缘点的计算次数为9×7。地标模板边缘图像在遥感边缘图像上平移滑动的区域尺寸为4×4，那么，总的计算量为Z=4×4×9×n，其中0 ≤n≤25，n为遥感边缘图像子图边缘点的数量。由于地标模板边缘点数量是确定的，遥感图像和地标模板图像的尺寸也是可以获得的固定数据，遥感边缘图像子图的边缘点数量随着平移量(i,j) 位置的变化而变化，因此，计算量随着遥感边缘图像子图边缘点数量递增而增加。如果地标模板与遥感边缘图像子图的边缘点数量和匹配搜索区域增加一个数量级，那么，计算量将会增加四个数量级数甚至更多，计算时间也相应快速增加。

（2）重复冗余计算多

对不同平移量(i,j)的最小距离值dij(p)计算过程中重复冗余计算多。以图1 为例，当在平移位置(2,2)时，如图1（a）所示，得到图1（c）所示的距离变换图。在平移位置(2,3)时得到图2（a）所示的距离变换图。对比两幅距离变换图可知，红色位置的距离值，如图2（b）所示，在图1（c）所示的距离变换图中已经得到，而此时需要重新计算。由于平移量的变化，使得相同位置的最小距离值重新计算，这些计算是重复冗余计算。因此，可以得出一个结论：当地标模板边缘图像在遥感边缘图像上平移滑动计算距离值时，某个像素点位置的最小距离值经过一次计算得到后是固定不变的。以图1（a）为例，得到如图2（c）所示距离变换图。

图2 分析图

（3）遍历计算相似度量值效率低

地标模板图像在遥感边缘图像中平移滑动进行相似性度量值D(i,j)的计算时，地标模板对于所有可能的平移量(i,j)位置都需计算。以图1 为例，假设当遥感边缘图像子图处于如图3（a）所示平移位置(4,4)时，子图边缘点的数量为3；如图3（b）所示，地标模板边缘点的数量为9。此时模板和子图两幅图像边缘点数量差别比较大，通过比较可以得出，两幅图像不匹配。在计算相似性度量值D(i,j)时，对于类似情况都进行了计算，由于无效的计算多，从而导致遍历效率低。因此，为了提高效率，类似情况在遍历搜索时可以排除，以此避免无效计算。

图3 边缘图像对比图

3 改进的地标边缘匹配算法

3.1 算法性能优化

从以上算法性能分析知道，对算法进行优化主要从降低求取最小距离值的计算量，去除重复冗余计算和提高搜索效率方面来进行。

（1）计算量的优化

由2.2 节中分析得出结论：某个像素点位置的最小距离值经过一次计算得到后是固定不变的。因此，采用边缘距离扩展的方法可以实现减少算法计算量和去除重复冗余计算的目的。由于地标模板一般为地理结构明显且相对固定的图像，因此，可以对地标模板边缘图像采用边缘距离扩展的方法，预先计算出地标模板边缘图像上所有位置的最小距离值，即对地标模板边缘图像进行距离扩展至全图像素点，从而生成边缘距离扩展图像，使最小距离值模板化。边缘距离扩展图像在遥感边缘图像上平移滑动，遥感边缘图像子图上边缘点所对应边缘距离扩展图像的值就是求取的最小距离值。以图1为例，模板边缘图像经边缘距离扩展后生成边缘距离扩展图，如图4（a）所示，与图1（a）子图进行匹配时，不再需要计算最小距离值dij(p)，只需将子图边缘点位置与图4（b）所对应位置的值相加求算术平均，即计算相似度量值D(i,j)。边缘距离扩展的方法，不仅可以降低遍历两图像边缘点来计算最小距离值计算量大的问题，而且能去除不同平移量(i,j) 求取最小距离值的重复冗余计算，从而达到了减少计算量，提高计算速度的目的。

图4 分析图

（2）搜索效率的优化

采用设置相似门限的方法可以实现搜索的优化。通过2.2 节的算法性能分析（3）可知，在最佳匹配位置上，地标模板边缘图像上的边缘点数量与遥感边缘图像子图的边缘点数量应该相差不大。基于这一思想，如果两幅匹配图像边缘点的数量相差比较大，那么可以认为该位置为非匹配位置，则不必计算相似性度量值，直接予以剔除。因此，可以通过设定子图边缘点数量占地标模板边缘点数量的比例来判断两图像是否匹配，即设置子图边缘点数量与模板边缘点数量的相似门限，对遥感边缘图像子图中边缘点数量过少或过多的位置予以剔除。通过设置相似门限，可以直接剔除遥感图像上绝大部分的非匹配图像点，从而缩小搜索范围，提高搜索效率。

3.2 改进的距离变换匹配算法

改进算法的具体步骤：

（1）提取边缘图像。对地标模板图像和遥感图像进行边缘检测，转化为二值的边缘图像。

（2）生成边缘距离扩展图像：

①对地标模板边缘图像进行边缘扩展并相加，得到相加图像。第一，对地标模板边缘图像，如图5（a）所示，进行形态学膨胀[15]，结构元素如图5（b）所示，得到一次膨胀图像，如图5（c）所示。第二，将一次膨胀图像与地标模板边缘图像相加，得到一次相加图像，如图5（d）所示。第三，对一次膨胀图像进行第二次形态学膨胀，得到二次膨胀图像，如图5（e）所示。第四，将二次膨胀图像与一次相加图像相加，得到二次相加图像，如图5（f）所示。依此类推，进行多次膨胀至距原边缘点较远位置停止，最后得到多次相加图像。膨胀次数可依据需要进行设定。

②形成边缘距离扩展图像并赋值。选取多次相加图像中的最大值（等于膨胀次数加1）形成最大值图像，用其减去多次相加图像，得到边缘距离扩展图像，如图5（g）所示。为了加大远距离边缘点之间的非对应性，在边缘距离扩展图像的最大值处（即边缘没有膨胀到的位置）直接赋一个更大值，如图5（h）所示。这样，在边缘距离扩展图像中，离原边缘点越近的值越小，越远的值越大。

（3）对于平移量(i,j)计算相似性度量值D(i,j)。计算出遥感边缘图像(i,j)处子图像中边缘点的数量和地标模板边缘图像中边缘点的数量。设置相似门限值，即子图边缘点数量占模板边缘点数量的最小和最大比例，取大于最小比例和小于最大比例之间的子图位置为搜索范围。相似门限可根据需要设定。在比例系数范围以外的区域剔除，直接赋予相似性度量值（相似性度量值的设置可依据边缘未扩展区域赋值确定）。在搜索范围以内的区域则计算匹配相似性度量值D(i,j)，即

其中，dij(g)为子图边缘点位置对应边缘距离扩展图位置的值，S为子图边缘点的数量，D(i,j)是相似性度量值，表示匹配程度，D(i,j)的值越小，匹配度越高。

（4）定位最佳匹配位置。在遥感边缘图像上遍历搜索，寻找最佳匹配位置，即

在D(i,j)取得最小值时，边缘图像的匹配度最高，即为最佳匹配位置。

图5 边缘距离扩展图像生成示意图

4 实验仿真及结果分析

为了验证算法的性能进行了实验仿真，仿真环境为MATLAB R2013a，主频2.34 GHz。仿真实验采用的遥感图像选自某地区的MODIS 图像，尺寸为512×512，如图6（a）所示。为了验证本文算法的有效性和2.2 节分析所得结论，选取三个不同尺寸大小的模板进行实验仿真，三个模板图像分别取自遥感图像中的一部分：模板（I）位置为（448，45），尺寸为38×30；模板（II）位置为（225，84），尺寸为53×56；模板（III）位置为（434，244），尺寸为76×63，如图6（b）所示。遥感图像和模板图像均采用Canny 算子提取边缘[16]，转化为二值的边缘图像。分别采用传统的距离变换算法、改进的距离变换算法以及本文算法进行遥感图像和模板图像的匹配，得到的地标匹配时间如表1 所示。

图6 实验图像

从表1 的实验结果可以看出，三个不同的地标模板利用传统距离变换算法进行匹配，匹配时间随着模板尺寸的增大而快速增加，与2.2 节中分析的结论一致；利用改进的距离变换算法进行匹配，匹配时间不但快速增加，而且比传统算法匹配时间还长；利用本文算法进行匹配，匹配时间只有传统距离变换算法匹配时间的0.1%～0.5%，与3.1 节（1）中计算量优化所得结论相同，同时也可以看出本文算法匹配时间不会随模板尺寸的增大而快速增加。结果表明，采用边缘距离扩展的优化方法解决了算法计算量大的问题，验证了本文算法对计算量优化的有效性。

表1 匹配时间对比表

图7 是地标模板（III）的匹配结果，此时本文算法中参数的设置为：扩展次数为3，未扩展空白区赋为10，子图边缘点数量占地标模板边缘点数量的最小和最大比例系数分别为0.5 和1.5，剔除的图像点相似性度量值赋为10。从图7（b）相似性度量值的空间分布可以看出，遥感图像中的绝大部分非匹配图像点（白色部分）被剔除在匹配搜索范围以外，其所占的比例为70.29%，匹配搜索区域（灰色部分）不到原来搜索范围的30%。结果表明，采用设置相似门限的方法可以有效地减少匹配搜索区域，提高匹配搜索效率，验证了本文算法对搜索优化的有效性。

图7 地标模板（III）匹配结果图

图8 是地标模板（III）分别利用三种算法匹配所得结果的相关曲面图，图中相关曲面的最高峰对应最佳匹配位置[13]。对比图8（a）、（b）和（c）可以看出，传统距离变换算法的相关曲面非常平缓，最高峰不明显，改进距离变换算法的相关曲面最高峰比较明显，本文算法的相关曲面最高峰位置明显，相关峰尖锐，表明本文算法匹配定位精度很高。

图8 地标模板（III）匹配结果相关曲面图

仿真结果表明，本文提出的边缘距离扩展和设置相似门限的距离变换算法在保证匹配精度的基础上，大大减少了匹配的时间，实现了快速匹配，能满足匹配的高时效性要求。

5 结束语

针对距离变换算法存在的问题，采用边缘距离扩展和设置相似门限的方法解决了算法计算和搜索时间长的问题。通过将地标模板边缘图像进行距离扩展生成边缘距离扩展图像，从而解决了要遍历两图像所有边缘点来计算距离值以及其中重复冗余计算的问题。基于最佳匹配位置两图像边缘点数量相差不大的基本思想，通过判断子图边缘点数量占地标模板边缘点数量比例的方法，直接剔除了遥感图像上绝大部分的非匹配图像点，从而缩小了搜索的范围，解决了搜索效率低的问题。

最后，采用不同地标模板进行仿真实验，将传统的距离变换算法和本文算法作了对比。实验结果表明，本文算法在计算时间上有很大程度的提升，能满足图像匹配的实时性要求。

[1] 杨磊，杨忠东.遥感卫星图像自动导航方法研究[J].计算机工程与应用，2009，45（10）：204-207.

[2] 郭强，杨磊.气象卫星图像导航的地标匹配算法研究与优化[J].计算机工程与应用，2013，49（24）：152-156.

[3] 李耀军.基于空间关系几何约束的无人机景象匹配导航[J].计算机应用研究，2010，27（10）：3822-3835.

[4] 吉祥.基于景象匹配的无人飞行器定位方法[J].系统仿真学报，2014，26（6）：1291-1296.

[5] Cesetti A，Frontoni E，Mancini A，et al.Vision-based guidance system for UAV navigation and safe landing using natural landmarks[J].Journal of Intelligent & Robotic Systems，2010，57（1/4）：233-257.

[6] Mostafa K，Majid B，Ali P.UAV navigation based on PIIFD/INS method[J].International Journal of Computer Theory and Engineering，2012，4（2）：283-287.

[7] 王红梅，张科，李言俊.图像匹配研究进展[J].计算机工程与应用，2004，40（19）：42-45.

[8] 王鲲鹏，徐一丹，余起峰.红外与可见光图像配准方法分类及现状[J].红外技术，2009，31（5）：270-274.

[9] 汪汉云，王程.多源遥感图像配准技术综述[J].计算机工程，2011，37（19）：17-21.

[10] Zitova B，Flusser J.Image registration methods：a survey[J].Image Vision Computing，2003，21：977-l000.

[11] Brown L G.A survey of image registration[J].ACM Computing Surveys，l992（4）：325-376.

[12] 张志佳，黄莎白，史泽林.新的基于边缘特征的图像相关匹配方法[J].红外与激光工程，2003，32（6）：365-368.

[13] 张卫炜.基于边缘的红外与可见光图像匹配方法研究[D].长沙：国防科学技术大学，2010.

[14] 李伟.地面场景光学图像辅助导航技术研究[D].长沙：国防科学技术大学，2008.

[15] 高展宏，徐文波.基于Matlab 的图像处理案例教程[M].北京：清华大学出版社，2011：217-219.

[16] Nixon M S，Aguado A S.特征提取与图像处理[M].2 版.李实英，杨高波，译.北京：电子工业出版社，2013：92-109.