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

孫　盛，劉仁峰，鄧少平

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

?

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

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

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

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

三維地形匹配；性能估計；高斯馬爾可夫隨機場；多分辨率

1　引　言

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

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

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

2　地形匹配性能的估計

2.1匹配性能的定義

2.1.1匹配概率和匹配誤差

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

2.1.2局部精度

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

2.2特征向量的提取

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

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

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

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

2.2.2特征向量

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

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

(1)

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

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

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

(2)

2.3馬爾可夫隨機場的引入

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

設(shè)高斯馬爾可夫隨機場為

(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è)匹配性能服從高斯分布，這與實際情況是大致相符的[9-10]。圖2給出了某個地形圖定位誤差的經(jīng)驗分布、擬合的高斯分布?？梢钥闯觯`差分布大致服從高斯分布。

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

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

2.4.1參數(shù)θ的估計

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

(6)

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

θ=(FTF)-1FTx。

(7)

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

(8)

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

(9)

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

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

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

(10)

x=F′θ 。

(11)

3　實驗及分析

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

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

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

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

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

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

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

3.2實驗結(jié)果及分析

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

表1　算法運算效率對比實驗結(jié)果

表2　平均定位誤差的對比實驗結(jié)果

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

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

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

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

4　結(jié)束語

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

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

[1]黃宸,柳健,張繼賢. 均勻設(shè)計用于地形特征與匹配性能關(guān)系的研究[J].華中理工大學(xué)學(xué)報,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].模式識別與人工智能,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回歸模型的景像匹配算法性能評估[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é)會控制與應(yīng)用第十二屆學(xué)術(shù)年會論文集.西安:中國航空學(xué)會,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匹配算法性能比較與改進研究[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é)圖像識別與人工智能研究所獲工學(xué)博士學(xué)位，現(xiàn)為廣東工業(yè)大學(xué)計算機學(xué)院講師，主要研究方向為遙感圖像處理與計算機視覺；

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é)圖像識別與人工智能研究所獲工學(xué)博士學(xué)位,現(xiàn)為武漢輕工大學(xué)數(shù)學(xué)與計算機學(xué)院講師,主要研究方向為立體視覺與視覺測量；

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ǔ)地理信息中心高級工程師，主要研究方向為遙感影像處理與解譯。

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é)基金資助項目(41501362)；廣東省公益研究與能力建設(shè)專項項目(2014A020218015)；廣東省教育廳創(chuàng)新強校工程青年創(chuàng)新人才項目(15ZK0117)

TP751.1

A

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

引用格式：孫盛，劉仁峰，鄧少平.三維地形匹配性能的一種快速估計方法[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