樹描述符匹配算法在地形匹配中的應用

肖賽男

(湖南城市學院信息科學與工程學院，湖南 益陽 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.