三维地形匹配性能的一种快速估计方法*

孙　盛，刘仁峰，邓少平

(1. 广东工业大学 计算机学院，广州510006；2.武汉轻工大学 数学与计算机学院，武汉 430023；3.广东省中山市基础地理信息中心，广东 中山 528403)



三维地形匹配性能的一种快速估计方法*

孙盛**，刘仁峰2，邓少平3

(1. 广东工业大学 计算机学院，广州510006；2.武汉轻工大学 数学与计算机学院，武汉 430023；3.广东省中山市基础地理信息中心，广东 中山 528403)

针对起伏较小三维地形的匹配系统，提出了一种匹配性能的快速估计方法。给出了匹配性能指标的定义，采用八联通区域的邻域完成了特征向量的多分辨率构造，使用多分辨率高斯马尔可夫随机场建立特征与匹配性能之间的关系。在特征提取的过程中，将基准图划分为若干个方块，提取的特征兼顾了邻域关系和多分辨率特性。给出了训练学习和推广的公式，使用最大后验准则，逐步推导出了性能指标估计值的解析解。最后，以实测数据为基础，通过实验验证了所提方法在运算效率和定位误差方面均有较好的性能。

三维地形匹配；性能估计；高斯马尔可夫随机场；多分辨率

1　引　言

三维地形匹配在低空飞行器导航中有广泛的应用，可以对惯性导航系统的累积误差进行修正，对于提高飞行器的导航性能具有重要意义。给定三维地形图，快速地估计出地形匹配性能具有重要的应用价值，可以用于快速寻找适合匹配的地形区域。

三维地形匹配的性能指标主要包括匹配概率、匹配误差、局部精度等，匹配性能的估计可以用于适配区的选择、航迹规划、匹配算法的评估等。对于匹配性能指标的计算，最直接的方法是根据定义，但这种方法所需的计算量非常大，例如：计算一张分辨率为512 pixel×512 pixel基准图的匹配性能通常需要数百个小时。因此，许多研究者采用间接的方法来估计匹配性能，例如：使用多元二次回归模型描述地形特征与匹配性能之间的关系[1]；使用Fisher线性分类器估计匹配概率[2]；使用Logistic回归模型对景象匹配算法的性能进行定量评估[3]；使用支持向量机评估景象匹配的性能[4]；结合地形起伏度和相似度因素的地形匹配性能快速评价方法[5]。

为了快速地对地形匹配系统的性能进行估计，本文以起伏较小地形为实验对象，以马尔可夫随机场(Markov Random Field,MRF)作为概率模型，提出了一种基于统计学习的方法用于完成三维地形匹配性能的快速估计。本方法分为训练学习和推广两个部分，第2节给出了训练与推广的相关定义以及性能估计值的解析解的推导过程，第3节结合实际数据进行了验证。

2　地形匹配性能的估计

2.1匹配性能的定义

2.1.1匹配概率和匹配误差

匹配概率和匹配误差的计算方法如下：在基准图中选取多个子图作为基准子图，对于每个基准子图选取多个实时图；然后使用传感器的误差模型对实时图加入噪声和畸变，模拟实际的实时图；对各个实时图分别与基准图进行仿真匹配实验，记录正确匹配次数和各次的匹配误差[6]。对于任一基准子图，将正确匹配次数与总的匹配次数之比定义为该基准子图的匹配概率；将各次匹配误差的和除以总的匹配次数定义为该基准子图的匹配误差。

2.1.2局部精度

局部精度(Local Accuracy,LA)是实际得到的匹配位置与真实的匹配位置的偏差[7]，通常采用该偏差的方差来描述。在实际实现中，可通过控制相同的外部条件(例如基准图、实时图的噪声和畸变等)，做多次实验，计算平均的定位误差，该误差就是这一点的局部匹配误差。

2.2特征向量的提取

2.2.1块的近邻关系

将地形图划分为有重叠的矩形块。对于某些性能指标，例如局部精度，还应考虑到多分辨率特性。由于不同的地形在某些分辨率下会有类似的特征，而在其他一些分辨率会有不同的特征[8]。因此，本方法还考虑了多分辨率特征。

对于地形图上的每个位置，其特征包括绝对特征和相对特征。绝对特征很大程度上决定了匹配性能，包括以它为中心的块的特征、其直接近邻块的特征、在更大分辨率上的近邻块的特征。相对特征用于表征不同块之间的差异，它作为约束条件修正匹配性能。图1给出了块的近邻关系。本方法采用的是八连通邻域。

图1　特征向量构造的邻域和多分辨率示意图

2.2.2特征向量

一个矩形块内的地形方差反映了地形的细节丰富程度，因此，我们将方差作为构造特征的基本单元。记层的数目为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的维数为m=l·(|Ns(i)|+1)，|·|表示求集合的元素个数。

定义块i与块j在第s层的的相对特征：

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

(2)

2.3马尔可夫随机场的引入

马尔可夫随机场具有很强的建模能力，广泛应用于图像处理和计算机视觉等领域。本方法采用一种多分辨率的马尔可夫随机场对局部匹配误差进行建模，其基本思想是：某一点的匹配性能不仅与它所在的中心区域的统计特性有关，还与相邻区域的统计特性有关。这种特性称作空间的马尔可夫性，这类问题可以采用马尔可夫随机场进行建模。

设高斯马尔可夫随机场为

(3)

式中：Z为归一化常数；xN×1=[x1,x2,…,xN]T为匹配性能；FN×m=[f1,f2,…,fN]T为特征构成的矩阵；θm×1、σ1,i、σ2,ij(s)为参数，满足

(4)

(5)

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

在式(3)中，本方法假设匹配性能服从高斯分布，这与实际情况是大致相符的[9-10]。图2给出了某个地形图定位误差的经验分布、拟合的高斯分布。可以看出，误差分布大致服从高斯分布。

图2　定位误差的概率密度函数

2.4模型参数的估计

2.4.1参数θ的估计

本方法采用最大似然法估计参数θ：

(6)

于是，θ的求解转化为最小二乘估计问题。θ具有解析解：

θ=(FTF)-1FTx。

(7)

2.4.2参数σ1和σ2的估计(即v和us)的估计

(8)

于是，v的求解转化为二次规划(Quadratic Programming,QP)问题。

(9)

于是，us的求解转化为二次规划问题。特别地，本方法中的us为1维向量，式(9)退化成带约束的一元二次方程求极值问题。

最后，根据最大后验概率-马尔可夫随机场模型准则进行推断，具体过程如下：

式(3)的概率模型是多元高斯分布，将其写成标准形式，得到

(10)

x=F′θ 。

(11)

3　实验及分析

3.1实验数据设置及实验方案

实验使用一个山地的三维地形图作为实验数据，每个格子对应的实际尺寸是8 m×8 m，地形的起伏在100～300 m之间。

训练用的基准图分辨率为512 pixel×512 pixel；基准子图分辨率为256 pixel×256 pixel，实时图分辨率为32 pixel×32 pixel。相应的匹配概率和定位误差是使用去均值平均差值平方(Mean Squared Difference,MSD)算法[11]仿真得到。

层数的设置：对于匹配概率和定位误差，基准子图的各像素是地位相等的，没有必要设置多分辨率特性。设置层数为l=1。为了使第一层的9个块大致覆盖整个基准子图，设置块的尺寸为85×85(256/3≈85)。

图3为一组训练样本，包括地形图以及根据定义计算的匹配概率和定位误差。使用该数据训练多分辨率马尔可夫随机场得到相关的参数，拟合的结果如图4所示。

图3　一组训练样本

图4　对样本进行拟合的结果

3.2实验结果及分析

由于本文提出的方法具有解析解，计算复杂度较低。本实验使用的计算机配置为Intel i7-5500U CPU，8 GB内存。表1列举了3种已有方法与本文提出的新方法的运算效率对比结果，表2给出了定位3种已有方法与本文所提方法的平均定位误差的对比。可以看出，在运算效率和定位误差方面，本文的方法都好于以往方法。

表1　算法运算效率对比实验结果

表2　平均定位误差的对比实验结果

对于一张给定的512 pixel×512 pixel三维地形图，本文算法的平均运行时间为30 790 ms。当图像的尺寸比较大的时候，可以将它分成若干个小块，每个小块分别进行预测。因此，算法所需的时间跟图像的像素数大致成正比。对于一张1 024 pixel×1 024 pixel的三维地形图，算法的平均运行时间为119 087 ms。可以看出，随着图像维度的线性增加，运算复杂度也呈线性增加。

而对于采用间接方法[3-5]估计匹配性能的方法，可以看出，随着图像维度的线性增加，其运算复杂度呈几何级数增长。

使用本方法提出的模型对一张新的地形图计算匹配概率和定位误差，结果如图5所示。可以看出，在地形起伏较大的地方，通常匹配概率较大，并且定位误差比较小；反之，在地形起伏较小的地方，通常匹配概率较小，并且定位误差大。因此，适合作为地形匹配的地区通常是地形起伏的地区。

图5　匹配性能估计的结果

4　结束语

本文针对起伏较小地形的匹配系统，提出了一种快速估计地形匹配系统性能的方法，其基本思想是：某一点的匹配性能不仅与其所在区域的统计特性有关，还与相邻区域的统计特性有关。这种方法不需要各种先验知识，仅需要一个训练样本集，因此使用方便，具有较好的工程应用价值。

本文仅选择方差作为构造特征，除此之外，在未来的研究中还可以使用相关长度、高程熵等构造多特征，以进一步提高估计精度。

[1]黄宸,柳健,张继贤. 均匀设计用于地形特征与匹配性能关系的研究[J].华中理工大学学报,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]杨昕,杨新. 景象匹配精确制导中匹配概率的一种估计方法[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].红外技术,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]李杰，王养柱. 地形轮廓匹配导航中的地形匹配性能分析[C]//中国航空学会控制与应用第十二届学术年会论文集.西安:中国航空学会,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].成都：西南交通大学,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].电讯技术,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年于华中科技大学图像识别与人工智能研究所获工学博士学位，现为广东工业大学计算机学院讲师，主要研究方向为遥感图像处理与计算机视觉；

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年于华中科技大学图像识别与人工智能研究所获工学博士学位,现为武汉轻工大学数学与计算机学院讲师,主要研究方向为立体视觉与视觉测量；

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年于武汉大学获工学博士学位,现为广东省中山市基础地理信息中心高级工程师，主要研究方向为遥感影像处理与解译。

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

国家自然科学基金资助项目(41501362)；广东省公益研究与能力建设专项项目(2014A020218015)；广东省教育厅创新强校工程青年创新人才项目(15ZK0117)

TP751.1

A

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

引用格式：孙盛，刘仁峰，邓少平.三维地形匹配性能的一种快速估计方法[J].电讯技术，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