树描述符匹配算法在地形匹配中的应用

肖赛男

(湖南城市学院信息科学与工程学院，湖南 益阳 413000)

1.引言

地形匹配技术是地形辅助导航的关键技术之一，它在航空领域应用广泛，在水下运载体的海底地形匹配定位、机器人导航定位以及陆地车辆导航等方面也有着广阔的应用前景。

地形匹配的过程，实际上是将实时测出的地形高程图（实时图）与飞行器内预先制备的基准地形高程图（基准图）在空间上进行对准的过程，以获取飞行器精确导航定位信息。经典的平均绝对差(MAD)、平均均方差(MSD)和互相关(COR)等地形轮廓匹配算法可以完成匹配定位。但是这些方法是基于对应点之间的差值关系计算相关度的，要求两幅地形图是在相同尺度的坐标系下，并且待匹配两图之间不存在旋转变换。但是多数情况下，由于生成手段、时间等因素的不同，同一区域的不同时相DEM覆盖区域不可能完全重合，可能存在一定的未重合区域和定量的旋转、平移、缩放等变换。解决存在缩放、旋转条件下的地形匹配问题，可大大降低三维实时地形图测量的要求，增强地形匹配的适应性，具有非常重要的现实意义。

本文提出了改良的树描述符匹配算法，用树描述符对地形特征（山谷线）进行重建，通过搜索树描述符中最长公共子串的方法获得最大同构子树，建立2个同构子树之间的匹配关系完成匹配工作。该算法可应用于存在缩放、旋转条件下的地形匹配问题。

2.地形匹配技术的原理

地形匹配技术的依据是地形的凹凸不平特征与地理位置之间的对应关系，利用这种地形特征，在运动载体实时测量得到的地形图与已知的三维地形基准图进行配准，从而确定载体自身的位置信息。本文通过提取匹配图的山谷线作为待匹配的地形特征。

将山谷线的矢量图映射到树结构中存储其拓扑结构，通过两者之间特征对的匹配，也就是树结构匹配，就可以获取两种DEM中的特征对应关系，从而确定两种DEM是否达到粗匹配的要求。

3.树描述符匹配算法

为了更简单、高效地进行树的匹配，本文提出了树描述符算法对树进行拓扑匹配。树描述符包含了物体的形状特征和拓扑特征。

3.1 树描述符

定义对由匹配树深度优先搜索产生的节点序列中的所有节点用其孩子数替换，替换后得到的新序列即为树描述符。

3.2 树描述符匹配算法

对于2个匹配树T1，T2，我们初步建立的匹配算法如下：

(1)深度优先遍历匹配树T1、T2；

(2)用树描述符重建树，描述符分别为s1、s2；

(3)在基准树T1中搜索待匹配树T2的最大同构子树T，即找出s1、s2的最长公共子串；

(4)如果最长公共子串和被匹配树T2的描述符s2相等，说明T1、T2之间存在匹配关系，建立2个同构子树之间的匹配关系则匹配完成；

(5)由匹配关系得到对应点之间的坐标关系，建立两图之间的坐标对应关系，完成目标对准过程。

3.3 算法改进

上述匹配算法只能解决匹配模型中的子树匹配问题，不能解决松弛匹配的问题，如图1所示。为了得到更全面、更准确的匹配结果，提高算法的查全率，我们有必要改进这种匹配方法，才能得到正确的拓扑结构匹配结果。

图1 松弛匹配模型（T1，T2）

经分析，上述匹配算法需要对第三个步骤中的搜索最大同构子树过程加以改进，以解决松弛匹配问题。改进的搜索最大同构子树算法如下：

(1)搜索出s1中的所有叶子节点（描述符为0的节点），并进行标识；

(2)用字符串匹配算法搜索s1、s2中最长公共子串；

(3)字符串匹配算法：

a.如果s2中字符等于0（叶子节点），则查询到s1中与之对应的字符值为n，则s1向后移n位，后移的时候如果继续遇到非零值n1，n2…，则s1再向后移n1+n2+…位，然后s1、s2同时下移一位并继续进行下一位的字符匹配，如果下一位是s2到达结束符，则匹配成功。

b.如果s2中字符值不等于0，且s2的字符值等于s1中的字符值，则s1、s2同时下移一位，如果s2的字符值m小于s1中的字符值p，则s2向后移m位，s1向后移p位，然后再同时下移一位，继续匹配直到找到最大同构子树，匹配成功。

c.如果s2中字符不等于0，且s2的字符值大于s1中的字符值，则匹配不成功。

3.4 结果分析

以图1为例，分别用树描述符算法以及改进的树描述算法进行树结构匹配，其搜索最长公共子串匹配过程如图2和图3所示：

图2 树匹配符算法

图3 改进的树匹配符算法

图中上行是T1中被框部分的树描述符，下行是T2的描述符，按照改进的匹配算法，我们可以得到正确的匹配结果，T2中的每一个节点都能在T1中得到匹配。说明改进的算法是有效和可行的，能够得到与实际情况一致的匹配结果。

4.结束语

树描述符算法使用了树描述符来描述树，完整表达了树的形状和拓扑结构，避免了复杂的运算，基于树描述符的同构子树匹配方法简单而快速，建立的拓扑匹配关系具有地形的旋转、大小、平移不变性，一般情况下，也不受地形小的扭曲变形的影响，因为高程的细微改变是不会改变拓扑形状的，除非是经过严重的地质灾害，改变了地形的基本面貌，那就另当别论了。该方法能够获得快速而最优最准确的匹配结果。

[1]刘文予，刘俊涛.基于骨架树描述符匹配的物体相似性度量方法[J].红外与毫米波学报，2005，24(6)：432-436.

[2]Gan Guoqiang，Qiu Zhihe.Navigation and position[M].Beijing：National Defence Industry Press，2000.

[3]O’Callaghan J F.The Extraction of Drainage Networks Digital Elevation Data[J].Computer Vision，Graphics，and Image Processing，1984(28)：323-344.

[4]Golden JP.Terrain contour matching(TERCOM)：a cruise missile guidance aid [C]//Proceedings ofthe Society ofPhoto-Optical Instrumentation Engineers(SPIE).1980，238：10-18.

[5]李立春，苑云.三维地形不变性特征描述及其在地形匹配中的应用[J].航空学报，2009，30(11)：2143-2148.

[6]陈绍顺，李彦斌，李云.地形匹配制导技术研究[J].制导与引信，2003，24(3)：17-21.

[7]林应强，吴立德.基于模型的三维物体识别[J].自动化学报，1997，23(6)：756-761.

[8]姚全珠，丁新村，冉占军.基于XMI的树匹配构件检索算法的研究与实现[J].计算机应用研究，2008，25(4)：1013-1019.