孫　盛，劉仁峰，鄧少平

(1. 廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州510006；2.武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，武漢 430023；3.廣東省中山市基礎(chǔ)地理信息中心，廣東 中山 528403)

?

三維地形匹配性能的一種快速估計(jì)方法*

孫盛**，劉仁峰2，鄧少平3

(1. 廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州510006；2.武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，武漢 430023；3.廣東省中山市基礎(chǔ)地理信息中心，廣東 中山 528403)

針對(duì)起伏較小三維地形的匹配系統(tǒng)，提出了一種匹配性能的快速估計(jì)方法。給出了匹配性能指標(biāo)的定義，采用八聯(lián)通區(qū)域的鄰域完成了特征向量的多分辨率構(gòu)造，使用多分辨率高斯馬爾可夫隨機(jī)場(chǎng)建立特征與匹配性能之間的關(guān)系。在特征提取的過程中，將基準(zhǔn)圖劃分為若干個(gè)方塊，提取的特征兼顧了鄰域關(guān)系和多分辨率特性。給出了訓(xùn)練學(xué)習(xí)和推廣的公式，使用最大后驗(yàn)準(zhǔn)則，逐步推導(dǎo)出了性能指標(biāo)估計(jì)值的解析解。最后，以實(shí)測(cè)數(shù)據(jù)為基礎(chǔ)，通過實(shí)驗(yàn)驗(yàn)證了所提方法在運(yùn)算效率和定位誤差方面均有較好的性能。

三維地形匹配；性能估計(jì)；高斯馬爾可夫隨機(jī)場(chǎng)；多分辨率

1　引　言

三維地形匹配在低空飛行器導(dǎo)航中有廣泛的應(yīng)用，可以對(duì)慣性導(dǎo)航系統(tǒng)的累積誤差進(jìn)行修正，對(duì)于提高飛行器的導(dǎo)航性能具有重要意義。給定三維地形圖，快速地估計(jì)出地形匹配性能具有重要的應(yīng)用價(jià)值，可以用于快速尋找適合匹配的地形區(qū)域。

三維地形匹配的性能指標(biāo)主要包括匹配概率、匹配誤差、局部精度等，匹配性能的估計(jì)可以用于適配區(qū)的選擇、航跡規(guī)劃、匹配算法的評(píng)估等。對(duì)于匹配性能指標(biāo)的計(jì)算，最直接的方法是根據(jù)定義，但這種方法所需的計(jì)算量非常大，例如：計(jì)算一張分辨率為512 pixel×512 pixel基準(zhǔn)圖的匹配性能通常需要數(shù)百個(gè)小時(shí)。因此，許多研究者采用間接的方法來估計(jì)匹配性能，例如：使用多元二次回歸模型描述地形特征與匹配性能之間的關(guān)系[1]；使用Fisher線性分類器估計(jì)匹配概率[2]；使用Logistic回歸模型對(duì)景象匹配算法的性能進(jìn)行定量評(píng)估[3]；使用支持向量機(jī)評(píng)估景象匹配的性能[4]；結(jié)合地形起伏度和相似度因素的地形匹配性能快速評(píng)價(jià)方法[5]。

為了快速地對(duì)地形匹配系統(tǒng)的性能進(jìn)行估計(jì)，本文以起伏較小地形為實(shí)驗(yàn)對(duì)象，以馬爾可夫隨機(jī)場(chǎng)(Markov Random Field,MRF)作為概率模型，提出了一種基于統(tǒng)計(jì)學(xué)習(xí)的方法用于完成三維地形匹配性能的快速估計(jì)。本方法分為訓(xùn)練學(xué)習(xí)和推廣兩個(gè)部分，第2節(jié)給出了訓(xùn)練與推廣的相關(guān)定義以及性能估計(jì)值的解析解的推導(dǎo)過程，第3節(jié)結(jié)合實(shí)際數(shù)據(jù)進(jìn)行了驗(yàn)證。

2　地形匹配性能的估計(jì)

2.1匹配性能的定義

2.1.1匹配概率和匹配誤差

匹配概率和匹配誤差的計(jì)算方法如下：在基準(zhǔn)圖中選取多個(gè)子圖作為基準(zhǔn)子圖，對(duì)于每個(gè)基準(zhǔn)子圖選取多個(gè)實(shí)時(shí)圖；然后使用傳感器的誤差模型對(duì)實(shí)時(shí)圖加入噪聲和畸變，模擬實(shí)際的實(shí)時(shí)圖；對(duì)各個(gè)實(shí)時(shí)圖分別與基準(zhǔn)圖進(jìn)行仿真匹配實(shí)驗(yàn)，記錄正確匹配次數(shù)和各次的匹配誤差[6]。對(duì)于任一基準(zhǔn)子圖，將正確匹配次數(shù)與總的匹配次數(shù)之比定義為該基準(zhǔn)子圖的匹配概率；將各次匹配誤差的和除以總的匹配次數(shù)定義為該基準(zhǔn)子圖的匹配誤差。

2.1.2局部精度

局部精度(Local Accuracy,LA)是實(shí)際得到的匹配位置與真實(shí)的匹配位置的偏差[7]，通常采用該偏差的方差來描述。在實(shí)際實(shí)現(xiàn)中，可通過控制相同的外部條件(例如基準(zhǔn)圖、實(shí)時(shí)圖的噪聲和畸變等)，做多次實(shí)驗(yàn)，計(jì)算平均的定位誤差，該誤差就是這一點(diǎn)的局部匹配誤差。

2.2特征向量的提取

2.2.1塊的近鄰關(guān)系

將地形圖劃分為有重疊的矩形塊。對(duì)于某些性能指標(biāo)，例如局部精度，還應(yīng)考慮到多分辨率特性。由于不同的地形在某些分辨率下會(huì)有類似的特征，而在其他一些分辨率會(huì)有不同的特征[8]。因此，本方法還考慮了多分辨率特征。

對(duì)于地形圖上的每個(gè)位置，其特征包括絕對(duì)特征和相對(duì)特征。絕對(duì)特征很大程度上決定了匹配性能，包括以它為中心的塊的特征、其直接近鄰塊的特征、在更大分辨率上的近鄰塊的特征。相對(duì)特征用于表征不同塊之間的差異，它作為約束條件修正匹配性能。圖1給出了塊的近鄰關(guān)系。本方法采用的是八連通鄰域。

圖1　特征向量構(gòu)造的鄰域和多分辨率示意圖

2.2.2特征向量

一個(gè)矩形塊內(nèi)的地形方差反映了地形的細(xì)節(jié)豐富程度，因此，我們將方差作為構(gòu)造特征的基本單元。記層的數(shù)目為l，第i塊在第s層的鄰域?yàn)镹s(i)，第i塊在第s層的方差為var(i,s)，第i塊在第1層的絕對(duì)特征fi為

fi=[var(j,s)]m×1。

(1)

式中：j∈Ns(i)∪{i}；s=1,2,…,l。向量fi的維數(shù)為m=l·(|Ns(i)|+1)，|·|表示求集合的元素個(gè)數(shù)。

定義塊i與塊j在第s層的的相對(duì)特征：

fij(s)=[var(i,s)-var(j,s)]1×1。

(2)

2.3馬爾可夫隨機(jī)場(chǎng)的引入

馬爾可夫隨機(jī)場(chǎng)具有很強(qiáng)的建模能力，廣泛應(yīng)用于圖像處理和計(jì)算機(jī)視覺等領(lǐng)域。本方法采用一種多分辨率的馬爾可夫隨機(jī)場(chǎng)對(duì)局部匹配誤差進(jìn)行建模，其基本思想是：某一點(diǎn)的匹配性能不僅與它所在的中心區(qū)域的統(tǒng)計(jì)特性有關(guān)，還與相鄰區(qū)域的統(tǒng)計(jì)特性有關(guān)。這種特性稱作空間的馬爾可夫性，這類問題可以采用馬爾可夫隨機(jī)場(chǎng)進(jìn)行建模。

設(shè)高斯馬爾可夫隨機(jī)場(chǎng)為

(3)

式中：Z為歸一化常數(shù)；xN×1=[x1,x2,…,xN]T為匹配性能；FN×m=[f1,f2,…,fN]T為特征構(gòu)成的矩陣；θm×1、σ1,i、σ2,ij(s)為參數(shù)，滿足

(4)

(5)

式中：v為m×1向量;us為1×1向量。

在式(3)中，本方法假設(shè)匹配性能服從高斯分布，這與實(shí)際情況是大致相符的[9-10]。圖2給出了某個(gè)地形圖定位誤差的經(jīng)驗(yàn)分布、擬合的高斯分布?？梢钥闯?，誤差分布大致服從高斯分布。

圖2　定位誤差的概率密度函數(shù)

2.4模型參數(shù)的估計(jì)

2.4.1參數(shù)θ的估計(jì)

本方法采用最大似然法估計(jì)參數(shù)θ：

(6)

于是，θ的求解轉(zhuǎn)化為最小二乘估計(jì)問題。θ具有解析解：

θ=(FTF)-1FTx。

(7)

2.4.2參數(shù)σ1和σ2的估計(jì)(即v和us)的估計(jì)

(8)

于是，v的求解轉(zhuǎn)化為二次規(guī)劃(Quadratic Programming,QP)問題。

(9)

于是，us的求解轉(zhuǎn)化為二次規(guī)劃問題。特別地，本方法中的us為1維向量，式(9)退化成帶約束的一元二次方程求極值問題。

最后，根據(jù)最大后驗(yàn)概率-馬爾可夫隨機(jī)場(chǎng)模型準(zhǔn)則進(jìn)行推斷，具體過程如下：

式(3)的概率模型是多元高斯分布，將其寫成標(biāo)準(zhǔn)形式，得到

(10)

x=F′θ 。

(11)

3　實(shí)驗(yàn)及分析

3.1實(shí)驗(yàn)數(shù)據(jù)設(shè)置及實(shí)驗(yàn)方案

實(shí)驗(yàn)使用一個(gè)山地的三維地形圖作為實(shí)驗(yàn)數(shù)據(jù)，每個(gè)格子對(duì)應(yīng)的實(shí)際尺寸是8 m×8 m，地形的起伏在100～300 m之間。

訓(xùn)練用的基準(zhǔn)圖分辨率為512 pixel×512 pixel；基準(zhǔn)子圖分辨率為256 pixel×256 pixel，實(shí)時(shí)圖分辨率為32 pixel×32 pixel。相應(yīng)的匹配概率和定位誤差是使用去均值平均差值平方(Mean Squared Difference,MSD)算法[11]仿真得到。

層數(shù)的設(shè)置：對(duì)于匹配概率和定位誤差，基準(zhǔn)子圖的各像素是地位相等的，沒有必要設(shè)置多分辨率特性。設(shè)置層數(shù)為l=1。為了使第一層的9個(gè)塊大致覆蓋整個(gè)基準(zhǔn)子圖，設(shè)置塊的尺寸為85×85(256/3≈85)。

圖3為一組訓(xùn)練樣本，包括地形圖以及根據(jù)定義計(jì)算的匹配概率和定位誤差。使用該數(shù)據(jù)訓(xùn)練多分辨率馬爾可夫隨機(jī)場(chǎng)得到相關(guān)的參數(shù)，擬合的結(jié)果如圖4所示。

圖3　一組訓(xùn)練樣本

圖4　對(duì)樣本進(jìn)行擬合的結(jié)果

3.2實(shí)驗(yàn)結(jié)果及分析

由于本文提出的方法具有解析解，計(jì)算復(fù)雜度較低。本實(shí)驗(yàn)使用的計(jì)算機(jī)配置為Intel i7-5500U CPU，8 GB內(nèi)存。表1列舉了3種已有方法與本文提出的新方法的運(yùn)算效率對(duì)比結(jié)果，表2給出了定位3種已有方法與本文所提方法的平均定位誤差的對(duì)比?？梢钥闯?，在運(yùn)算效率和定位誤差方面，本文的方法都好于以往方法。

表1　算法運(yùn)算效率對(duì)比實(shí)驗(yàn)結(jié)果

表2　平均定位誤差的對(duì)比實(shí)驗(yàn)結(jié)果

對(duì)于一張給定的512 pixel×512 pixel三維地形圖，本文算法的平均運(yùn)行時(shí)間為30 790 ms。當(dāng)圖像的尺寸比較大的時(shí)候，可以將它分成若干個(gè)小塊，每個(gè)小塊分別進(jìn)行預(yù)測(cè)。因此，算法所需的時(shí)間跟圖像的像素?cái)?shù)大致成正比。對(duì)于一張1 024 pixel×1 024 pixel的三維地形圖，算法的平均運(yùn)行時(shí)間為119 087 ms。可以看出，隨著圖像維度的線性增加，運(yùn)算復(fù)雜度也呈線性增加。

而對(duì)于采用間接方法[3-5]估計(jì)匹配性能的方法，可以看出，隨著圖像維度的線性增加，其運(yùn)算復(fù)雜度呈幾何級(jí)數(shù)增長。

使用本方法提出的模型對(duì)一張新的地形圖計(jì)算匹配概率和定位誤差，結(jié)果如圖5所示?？梢钥闯?，在地形起伏較大的地方，通常匹配概率較大，并且定位誤差比較小；反之，在地形起伏較小的地方，通常匹配概率較小，并且定位誤差大。因此，適合作為地形匹配的地區(qū)通常是地形起伏的地區(qū)。

圖5　匹配性能估計(jì)的結(jié)果

4　結(jié)束語

本文針對(duì)起伏較小地形的匹配系統(tǒng)，提出了一種快速估計(jì)地形匹配系統(tǒng)性能的方法，其基本思想是：某一點(diǎn)的匹配性能不僅與其所在區(qū)域的統(tǒng)計(jì)特性有關(guān)，還與相鄰區(qū)域的統(tǒng)計(jì)特性有關(guān)。這種方法不需要各種先驗(yàn)知識(shí)，僅需要一個(gè)訓(xùn)練樣本集，因此使用方便，具有較好的工程應(yīng)用價(jià)值。

本文僅選擇方差作為構(gòu)造特征，除此之外，在未來的研究中還可以使用相關(guān)長度、高程熵等構(gòu)造多特征，以進(jìn)一步提高估計(jì)精度。

[1]黃宸,柳健,張繼賢. 均勻設(shè)計(jì)用于地形特征與匹配性能關(guān)系的研究[J].華中理工大學(xué)學(xué)報(bào),1998,26(8):74-76.

HUANG Chen,LIU Jian,ZHANG Jixian. Research on the relations between terrain features and performance of terrain registration using even experiment design [J].Journal of Huazhong University of Science and Technology,1998,26(8):74-76.(in Chinese)

[2]楊昕,楊新. 景象匹配精確制導(dǎo)中匹配概率的一種估計(jì)方法[J].模式識(shí)別與人工智能,2003,16(4):448-451.

YANG Xin,YANG Xin. Estimating the probability of landmark matching in precise guidance system [J].Pattern Recognition and Artificial Intelligence,2003,16(4):448- 451.(in Chinese)

[3]王洋,徐剛鋒,左東廣. 基于Logistic回歸模型的景像匹配算法性能評(píng)估[J].紅外技術(shù),2008,30(9):524-528.

WANG Yang,XU Gangfeng,ZUO Dongguang. Performance evaluation of image registration algorithm based on Logistic regression model [J].Infrared Technology,2008,30(9):524-528.(in Chinese)

[4]YANG Z,CHEN Y,ZHANG S. Performance evaluation for scene matching algorithms by SVM[C]//Proceedings of 21st ISPRS Congress.Beijing:ISPRS,2008:503-508.

[5]李杰，王養(yǎng)柱. 地形輪廓匹配導(dǎo)航中的地形匹配性能分析[C]//中國航空學(xué)會(huì)控制與應(yīng)用第十二屆學(xué)術(shù)年會(huì)論文集.西安:中國航空學(xué)會(huì),2006:622-626.

LI Jie,WANG Yangzhu. Terrain matching performance analysis in terrain contour matching[C]//Proceedings of 2006 IEEE Chinese Guidance,Navigation and Control Conference.Xi'an:Chinese Society of Aeronautics and Astronautics,2006:622-626.(in Chinese)

[6]楊容浩. 無控制DEM匹配算法性能比較與改進(jìn)研究[D].成都：西南交通大學(xué),2012.

YANG Ronghao.The research on performance comparison and improvement of DEM matching algorithms without ground control point [D].Chengdu:Southwest Jiaotong University,2012.(in Chinese)

[7]LEE C,OH J,HONG C,et al.Automated generation of a digital elevation model over steep terrain in antarctica from high-resolution satellite imagery [J].IEEE Transactions on Geoscience and Remote Sensing,2015,53(3):1186-1194.

[8]陳懷新,王連亮. 基于PCA的小波多分辨圖像融合方法 [J].電訊技術(shù),2006,46(1):79-82.

CHEN Huaixin,WANG Lianliang.A wavelet multi- resolution image fusion method based on principle component analysis [J].Telecommunication Engineering,2006,46(1):79-82.(in Chinese)

[9]MA J Y,ZHAO J,YUILLE A L.Non-rigid point set registration by preserving global and local structures [J].IEEE Transactions on Image Processing,2016,25(1):53-64.

[10]THRUN S,BURGARD W,FOX D. Probabilistic robotics[M].Cambridge,MA:The MIT Press,2005:50.

[11]LEHMANN E L,CASELLA G. Theory of point estimation[M].2nd ed.New York:Springer,2003:109.

孫盛(1980—)，男，湖北建始人，2013年于華中科技大學(xué)圖像識(shí)別與人工智能研究所獲工學(xué)博士學(xué)位，現(xiàn)為廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院講師，主要研究方向?yàn)檫b感圖像處理與計(jì)算機(jī)視覺；

SUN Sheng was born in Jianshi,Hubei Province,in 1980. He received the Ph.D.degree from Huazhong University of Science and Technology in 2013. He is now a lecturer. His research concerns remote-sensing imagery processing and computer vision.

Email:shengsun@189.cn

劉仁峰(1980—)，男，江西吉安人，2012年于華中科技大學(xué)圖像識(shí)別與人工智能研究所獲工學(xué)博士學(xué)位,現(xiàn)為武漢輕工大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院講師,主要研究方向?yàn)榱Ⅲw視覺與視覺測(cè)量；

LIU Renfeng was born in Ji′an,Jiangxi Province,in 1980. He received the Ph.D.degree from Huazhong University of Science and Technology in 2012. He is now a lecturer. His research concerns stereoscopic vision and vision measurement.

鄧少平(1984—)，男，湖南長沙人，2013年于武漢大學(xué)獲工學(xué)博士學(xué)位,現(xiàn)為廣東省中山市基礎(chǔ)地理信息中心高級(jí)工程師，主要研究方向?yàn)檫b感影像處理與解譯。

DENG Shaoping was born in Changsha,Hunan Province,in 1984. He received the Ph.D.degree from Wuhan University in 2013. He is now a senior engineer. His research concerns remote-sensing imagery processing and interpretation.

The National Natural Science Foundation of China(No.61202269)；Guangdong Province Science and Technology Plan Projects(2014A020218015)；The Innovative Talents Projects of Education Department of Guangdong Province(15zk0117)

A Fast Performance Evaluation Method for 3D Terrain Matching

SUN Sheng1，LIU Renfeng2，DENG Shaoping3

(1.School of Computer Science,Guangdong University of Technology,Guangzhou 510006,China；2.School of Mathematics and Computer Science,Wuhan Polytechnic University,Wuhan 430023,China;3.Geomatics Center of Zhongshan City,Zhongshan 528403,China)

A fast matching performance evaluation method is proposed for three-dimensional terrain matching systems with small-amplitude undulation. The definition of performance indicators for terrain matching is put forward at first. Eight-connected field is then employed to construct the multi-resolution feature vectors. Multi-resolution Gaussian Markov random field is used to model the relationship between terrain features and the matching performance.During the procedure of feature extraction,the reference map is divided into several rectangle blocks and both the neighborhood relationship and multi-resolution characteristics are utilized. Learning and testing equations are introduced and therewith the analytic solutions of estimation values for performance indicators are obtained by exploring maximum a posteriori criterion. Finally,it is validated that the new proposed method has better performance in terms of computing complexity and localization bias based on the ground truth sample data.

3D terrain matching；performance evaluation；Gaussian Markov random field；multi-resolution

10.3969/j.issn.1001-893x.2016.10.011

2016-03-11；

2016-08-03Received date:2016-03-11；Revised date：2016-08-03

國家自然科學(xué)基金資助項(xiàng)目(41501362)；廣東省公益研究與能力建設(shè)專項(xiàng)項(xiàng)目(2014A020218015)；廣東省教育廳創(chuàng)新強(qiáng)校工程青年創(chuàng)新人才項(xiàng)目(15ZK0117)

TP751.1

A

1001-893X(2016)10-1124-05

引用格式：孫盛，劉仁峰，鄧少平.三維地形匹配性能的一種快速估計(jì)方法[J].電訊技術(shù)，2016,56(10):1124-1128.[SUN Sheng，LIU Renfeng，DENG Shaoping.A fast performance evaluation method for 3D terrain matching[J].Telecommunication Engineering,2016,56(10):1124-1128.]

**通信作者：shengsun@189.cnCorresponding author：shengsun@189.cn1