樹描述符匹配算法在地形匹配中的應(yīng)用

肖賽男

(湖南城市學(xué)院信息科學(xué)與工程學(xué)院，湖南 益陽 413000)

1.引言

地形匹配技術(shù)是地形輔助導(dǎo)航的關(guān)鍵技術(shù)之一，它在航空領(lǐng)域應(yīng)用廣泛，在水下運載體的海底地形匹配定位、機(jī)器人導(dǎo)航定位以及陸地車輛導(dǎo)航等方面也有著廣闊的應(yīng)用前景。

地形匹配的過程，實際上是將實時測出的地形高程圖（實時圖）與飛行器內(nèi)預(yù)先制備的基準(zhǔn)地形高程圖（基準(zhǔn)圖）在空間上進(jìn)行對準(zhǔn)的過程，以獲取飛行器精確導(dǎo)航定位信息。經(jīng)典的平均絕對差(MAD)、平均均方差(MSD)和互相關(guān)(COR)等地形輪廓匹配算法可以完成匹配定位。但是這些方法是基于對應(yīng)點之間的差值關(guān)系計算相關(guān)度的，要求兩幅地形圖是在相同尺度的坐標(biāo)系下，并且待匹配兩圖之間不存在旋轉(zhuǎn)變換。但是多數(shù)情況下，由于生成手段、時間等因素的不同，同一區(qū)域的不同時相DEM覆蓋區(qū)域不可能完全重合，可能存在一定的未重合區(qū)域和定量的旋轉(zhuǎn)、平移、縮放等變換。解決存在縮放、旋轉(zhuǎn)條件下的地形匹配問題，可大大降低三維實時地形圖測量的要求，增強(qiáng)地形匹配的適應(yīng)性，具有非常重要的現(xiàn)實意義。

本文提出了改良的樹描述符匹配算法，用樹描述符對地形特征（山谷線）進(jìn)行重建，通過搜索樹描述符中最長公共子串的方法獲得最大同構(gòu)子樹，建立2個同構(gòu)子樹之間的匹配關(guān)系完成匹配工作。該算法可應(yīng)用于存在縮放、旋轉(zhuǎn)條件下的地形匹配問題。

2.地形匹配技術(shù)的原理

地形匹配技術(shù)的依據(jù)是地形的凹凸不平特征與地理位置之間的對應(yīng)關(guān)系，利用這種地形特征，在運動載體實時測量得到的地形圖與已知的三維地形基準(zhǔn)圖進(jìn)行配準(zhǔn)，從而確定載體自身的位置信息。本文通過提取匹配圖的山谷線作為待匹配的地形特征。

將山谷線的矢量圖映射到樹結(jié)構(gòu)中存儲其拓?fù)浣Y(jié)構(gòu)，通過兩者之間特征對的匹配，也就是樹結(jié)構(gòu)匹配，就可以獲取兩種DEM中的特征對應(yīng)關(guān)系，從而確定兩種DEM是否達(dá)到粗匹配的要求。

3.樹描述符匹配算法

為了更簡單、高效地進(jìn)行樹的匹配，本文提出了樹描述符算法對樹進(jìn)行拓?fù)淦ヅ洹涿枋龇宋矬w的形狀特征和拓?fù)涮卣鳌?/p>

3.1 樹描述符

定義對由匹配樹深度優(yōu)先搜索產(chǎn)生的節(jié)點序列中的所有節(jié)點用其孩子數(shù)替換，替換后得到的新序列即為樹描述符。

3.2 樹描述符匹配算法

對于2個匹配樹T1，T2，我們初步建立的匹配算法如下：

(1)深度優(yōu)先遍歷匹配樹T1、T2；

(2)用樹描述符重建樹，描述符分別為s1、s2；

(3)在基準(zhǔn)樹T1中搜索待匹配樹T2的最大同構(gòu)子樹T，即找出s1、s2的最長公共子串；

(4)如果最長公共子串和被匹配樹T2的描述符s2相等，說明T1、T2之間存在匹配關(guān)系，建立2個同構(gòu)子樹之間的匹配關(guān)系則匹配完成；

(5)由匹配關(guān)系得到對應(yīng)點之間的坐標(biāo)關(guān)系，建立兩圖之間的坐標(biāo)對應(yīng)關(guān)系，完成目標(biāo)對準(zhǔn)過程。

3.3 算法改進(jìn)

上述匹配算法只能解決匹配模型中的子樹匹配問題，不能解決松弛匹配的問題，如圖1所示。為了得到更全面、更準(zhǔn)確的匹配結(jié)果，提高算法的查全率，我們有必要改進(jìn)這種匹配方法，才能得到正確的拓?fù)浣Y(jié)構(gòu)匹配結(jié)果。

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

經(jīng)分析，上述匹配算法需要對第三個步驟中的搜索最大同構(gòu)子樹過程加以改進(jìn)，以解決松弛匹配問題。改進(jìn)的搜索最大同構(gòu)子樹算法如下：

(1)搜索出s1中的所有葉子節(jié)點（描述符為0的節(jié)點），并進(jìn)行標(biāo)識；

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

(3)字符串匹配算法：

a.如果s2中字符等于0（葉子節(jié)點），則查詢到s1中與之對應(yīng)的字符值為n，則s1向后移n位，后移的時候如果繼續(xù)遇到非零值n1，n2…，則s1再向后移n1+n2+…位，然后s1、s2同時下移一位并繼續(xù)進(jìn)行下一位的字符匹配，如果下一位是s2到達(dá)結(jié)束符，則匹配成功。

b.如果s2中字符值不等于0，且s2的字符值等于s1中的字符值，則s1、s2同時下移一位，如果s2的字符值m小于s1中的字符值p，則s2向后移m位，s1向后移p位，然后再同時下移一位，繼續(xù)匹配直到找到最大同構(gòu)子樹，匹配成功。

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

3.4 結(jié)果分析

以圖1為例，分別用樹描述符算法以及改進(jìn)的樹描述算法進(jìn)行樹結(jié)構(gòu)匹配，其搜索最長公共子串匹配過程如圖2和圖3所示：

圖2 樹匹配符算法

圖3 改進(jìn)的樹匹配符算法

圖中上行是T1中被框部分的樹描述符，下行是T2的描述符，按照改進(jìn)的匹配算法，我們可以得到正確的匹配結(jié)果，T2中的每一個節(jié)點都能在T1中得到匹配。說明改進(jìn)的算法是有效和可行的，能夠得到與實際情況一致的匹配結(jié)果。

4.結(jié)束語

樹描述符算法使用了樹描述符來描述樹，完整表達(dá)了樹的形狀和拓?fù)浣Y(jié)構(gòu)，避免了復(fù)雜的運算，基于樹描述符的同構(gòu)子樹匹配方法簡單而快速，建立的拓?fù)淦ヅ潢P(guān)系具有地形的旋轉(zhuǎn)、大小、平移不變性，一般情況下，也不受地形小的扭曲變形的影響，因為高程的細(xì)微改變是不會改變拓?fù)湫螤畹?，除非是?jīng)過嚴(yán)重的地質(zhì)災(zāi)害，改變了地形的基本面貌，那就另當(dāng)別論了。該方法能夠獲得快速而最優(yōu)最準(zhǔn)確的匹配結(jié)果。

[1]劉文予，劉俊濤.基于骨架樹描述符匹配的物體相似性度量方法[J].紅外與毫米波學(xué)報，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]李立春，苑云.三維地形不變性特征描述及其在地形匹配中的應(yīng)用[J].航空學(xué)報，2009，30(11)：2143-2148.

[6]陳紹順，李彥斌，李云.地形匹配制導(dǎo)技術(shù)研究[J].制導(dǎo)與引信，2003，24(3)：17-21.

[7]林應(yīng)強(qiáng)，吳立德.基于模型的三維物體識別[J].自動化學(xué)報，1997，23(6)：756-761.

[8]姚全珠，丁新村，冉占軍.基于XMI的樹匹配構(gòu)件檢索算法的研究與實現(xiàn)[J].計算機(jī)應(yīng)用研究，2008，25(4)：1013-1019.