肖賽男

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

1.引言

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

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

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

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

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

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

3.樹(shù)描述符匹配算法

為了更簡(jiǎn)單、高效地進(jìn)行樹(shù)的匹配，本文提出了樹(shù)描述符算法對(duì)樹(shù)進(jìn)行拓?fù)淦ヅ?。?shù)描述符包含了物體的形狀特征和拓?fù)涮卣鳌?/p>

3.1 樹(shù)描述符

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

3.2 樹(shù)描述符匹配算法

對(duì)于2個(gè)匹配樹(shù)T1，T2，我們初步建立的匹配算法如下：

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

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

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

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

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

3.3 算法改進(jìn)

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

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

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

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

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

(3)字符串匹配算法：

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

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

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

3.4 結(jié)果分析

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

圖2 樹(shù)匹配符算法

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

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

4.結(jié)束語(yǔ)

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

[1]劉文予，劉俊濤.基于骨架樹(shù)描述符匹配的物體相似性度量方法[J].紅外與毫米波學(xué)報(bào)，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é)報(bào)，2009，30(11)：2143-2148.

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

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

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