2. 太原科技大学 电子信息学院, 山西 太原 030024
地形匹配导航是利用带有地理信息的机载数字高程图 (简称基准图) 与传感器实时获取的数字高程图 (简称实时图) 进行匹配, 以实现飞行器的导航定位, 是辅助GNSS导航的主要方式之一。目前用于地形匹配的二维地形数据表示方法主要有栅格数据和等高线数据2种, 栅格数据在进行地形匹配导航中存在计算量大且对旋转变换不鲁棒的问题; 而等高线数据在一定的高度采样间隔下, 将地形信息映射到曲线轮廓空间, 可实现数据降维、提高地形匹配效率。
采用目前的技术进行等高线匹配存在以下3个问题:①由于实时图所表示地形包含于基准图之中, 两者之间的匹配属于局部匹配, 实时等高线与基准等高线长度不一致、差异大、常展现为非封闭曲线, 故基于全局描述和封闭轮廓描述的方法[1-2]不适用于局部等高线匹配; ②实时地形图存在测量噪声, 由于噪声环境下扰动像素点增多, 相同区域的等高线的长度发生变化, 导致基于轮廓点集的域变换匹配方法[3]匹配精度下降, 也影响了基于局部点特征的提取以及特征描述方法[4]的鲁棒性, 文献[5]的形状匹配方法虽然可解决噪声环境下曲线轮廓点位置发生变化的匹配问题, 但无法解决点集数量和位置都发生变化的情况; ③等高线匹配需要精确找出实时图等高线在基准图等高线中的对应位置，而形状/序列匹配的方法侧重于描述形状/序列之间相似程度, 多用于形状识别与分类[6], 最长公共子序列[7]是解决序列匹配的一种有效途径, 但在序列长度差异较大情况下得到的外点比例大, 影响参数解算的正确率与精度, 而采用滑窗方法进行遍历计算大大增加了计算量, 并且在路径回溯过程中寻找正确匹配点的性能差。
针对上述问题, 本文引入多边形逼近进行等高线的简化表述与关键点提取; 基于局部相邻特征点的相对空间位置信息, 构造对旋转平移鲁棒的弦长夹角描述子对特征点进行描述; 为了提高参数解算的可靠性与精度, 提出候选集、相对位置偏移方差、回溯路径同列最小的三重约束的最长公共子序列算法, 用于寻找特征描述子序列中的匹配点。实验采用秦岭地区ASTER-GTM地形数据验证该地形匹配方法的有效性与性能。
1 一种鲁棒的等高线特征序列地形匹配方法基于等高线特征的地形匹配主要包括地形数据表述、点特征提取、点序列特征描述、特征匹配、参数解算5个步骤。首先将地形数据进行地理信息标注得到地形基准图; 然后分别将地形基准图与实时地形图进行地形数据表述, 其中地形数据表述的等高线生成算法参见文献[3]; 点特征的提取采用多边形逼近表示 (polygon approximation, PA)[8]方法, 采用自顶向下的PA方法对等高线进行分割表示, 将分割点作为等高线轮廓的特征点; 然后对点序列特征进行描述:除起点与终点外, 根据特征点的像素坐标计算特征点与前后特征点的欧式距离及夹角, 构造特征点的局部特征的弦长夹角描述子 (chord angle chord descriptor, CACD); 在生成实时图与基准图的CACD序列后, 等高线的匹配问题即转化为不等长描述子序列的匹配问题, 采用三重约束最长公共子序列 (triple constraint longest common sub-sequence, T-LCSS) 方法进行特征匹配与参数解算, 实现飞行器的导航定位。图 1给出了本文算法的基本结构框图。
|
| 图 1 本文算法结构框图 |
LCSS算法可以找到基准特征序列A与实时特征序列B中的匹配点, 在求取LCSS过程中获取记录最长公共子序列长度的矩阵c与记录回溯方向的矩阵b, 从矩阵c中长度最大的位置开始, 依照矩阵b中对应元素的回溯方向回溯得到回溯路径, 寻找回溯路径上回溯方向为“↖”的元素, 其所在行列值即为匹配点在A, B序列中的对应位置。引入记录LCSS长度的矩阵c与记录回溯方向的矩阵b, 其中c[i, j]存储{A1, A2, …, An}与{B1, B2, …, Bm}的最长公共子序列的长度 (其中m＜n), b[i, j]记录指示c[i, j]的值来源于哪一个子问题的解 (也即记录关键路径的回溯方向)。
2.1 三重约束在描述子序列长度n>>m的情况下, 设定候选集 (约束一):在长度为γm×m(γ为匹配序列缩放系数γ＞0) 的窗口中若包含连续匹配元素的长度不小于th时, 将此窗口对应的子序列A′作为LCSS的一个候选单元。
候选集算法步骤:
1) 生成A, B描述子序列的马氏距离矩阵M, M(i, j)=dist (Ai, Bj), 其中
|
(1) |
Σ为描述子序列A的协方差阵;
2) 计算连续长度矩阵M-LEN。其中M-LEN初始值为
|
(2) |
ε为判定2个描述子相似的阈值, 对矩阵M-LEN中非零元素进行遍历, 若满足M-LEN(Ai, Bj)≠0且M-LEN(Ai-1, Bj-1)≠0, 则更新连续长度矩阵M-LEN(i, j) 的连续匹配长度
|
(3) |
3) 从M-LEN中找出满足连续长度不小于th的γm×m的窗口, 选取其对应A中的序列子集A′做为候选单元, 由多个候选单元构成候选集{Ak′}, k为候选集中候选子序列个数。
求取候选集后, 对候选集{A′k}进行LCSS计算, 可得到r条最长公共子序列的回溯路径以及对应点的映射集fr(由于一个候选区域可能产生多于一条的回溯路径和对应点映射集, r≥k, B序列中并非所有元素在A序列中都找到对应点, 故m′≤m), 定义fr为B→A的映射函数:
|
(4) |
对于序列A与序列B基于映射fr的距离定义为
|
(5) |
最终求取r条路径的映射f中距离最短的映射点集匹配序列
|
(6) |
但在LCSS回溯求取对应点对的映射f过程中, 会出现以下误匹配的情况:
1) 对于一条回溯路径, 同列上只选择回溯方向为“↖”作为匹配点, 而未对同列中回溯路径上其他具有相似值的点对进行考量。这种误匹配的现象, 提出回溯路径同列最小判决方法 (约束二):
|
(7) |
式中，q为回溯路径中i列上的序列位置的集合。
2) 对于多回溯路径的情况下, 由于相似序列的出现, 会发生误匹配的现象。虽然在序列距离测度上难以区分, 但是匹配序列具有局部相对位移稳定性, 正确的匹配点对在A, B序列的位置差fi-i相较于错误匹配序列的位置差更加稳定, 其方差量也更小。定义基于相对位移方差的序列距离 (约束三) 如下
|
(8) |
|
(9) |
|
(10) |
式中, dr(A, B, fr) 是映射集fr中描述子匹配对的平均距离, Dr(A, B, fr) 是fr中匹配对的相对位移方差, d(A, B, fr) 是经过归一化的平均距离与相对方差之和, ω为权重系数, 新的目标函数转化为在相对位移方差与序列距离综合约束下的求解问题
|
(11) |
通过T-LCSS方法可减少误匹配对的数量, 为参数解算提供了更可靠的数据, 但在已得到的匹配点对中无法完全排除误匹配点的现象, 仍然存在偏离原有位置较大的野点, 在解算过程中使用RANSAC算法可以完成实时图与基准图几何变换矩阵优化求解, 同时有效排除存留的野点。
3 实验结果以及分析实验基准图DEM来自ASTER-GTM V2数据源, 数据格式为栅格数据, 空间分辨率为1″。选取北纬33°21′44.88″~34°21′44.88″, 东经106°41′16.45″~108° 41′16.45"内秦岭山区部分地形作为实验数据。
从DEM数据源中截取201×201像素单位的图像作为基准图, 等高线采样间隔为60 m, 在基准图中截取101×101大小、经过随机旋转角度θ([-90°~90°]) 的图像, 在此图上加标准差为σ随机噪声作为实时图, 采用T-LCSS与LCSS算法寻找实时图与基准图的匹配点, 并采用RANSAC对旋转平移参数进行解算。设置RANSAC迭代次数为150次, 适用模型的欧式距离阈值为3, 最少解算数据个数为3。
限于篇幅, 列出2组实验数据, 图 2中a)、b) 为第一组实验, c)、d) 为第二组实验, 其中a)、c) 为基准图, b)、d) 为经过平移旋转和加噪的实时图。图中浅色框为实时图的真实位置, 深色框为解算获取的实时图的位置，由图可见解算位置与真实位置框图基本重合; 图中“º”为LCSS获取的匹配点, “△”为T-LCSS获取的匹配点。实验结果见表 1, 其中σ为噪声标准差, θ, x, y分别是实际旋转的角度、X方向平移、Y方向平移, Δx, Δy, Δθ为解算参数与真实参数的差值, 内点比例为正确的匹配点数量与匹配方法检测出的匹配点数量的比值。
|
| 图 2 基于T-LCSS方法的参数解算实验 |
| 图 | 真实值 (σ, θ, x, y) | 方法 | Δx | Δy | Δθ/(°) | 内点比例 |
| a)、b) | (4, 0, 60, 40) | LCSS | 0.136 1 | 0.234 5 | 1.374 1 | 19/40 |
| T-LCSS | 0.068 9 | 0.187 8 | 0.820 0 | 21/23 | ||
| c)、d) | (6, 15, 80, 70) | LCSS | 0.463 3 | 0.384 1 | 3.745 1 | 17/44 |
| T-LCSS | 0.205 2 | 0.373 2 | 1.269 6 | 18/20 |
由图 2可见, 虽然LCSS找到的匹配点数量远大于T-LCSS的匹配点数量, 但其正确的比率很小, 分布在正确区域以外的比例很大。由表 1可知, 采用LCSS方法产生的野点数量多, 内点比率低于50%, 而采用T-LCSS方法得到90%以上的内点比率。由RANSAC算法的特性可知, 随着内点比率的减小, 参数模型解算的精度和正确率会显著降低。解算结果也验证了T-LCSS方法比LCSS得到的参数准确度要高。
为了验证本文方法对匹配正确率的影响, 分别采用T-LCSS、LCSS与文献[3]方法进行100次的随机旋转平移的参数解算仿真实验, 基准图同上, 噪声标准差σ分别设置为2~14 m。将解算结果中Δx＜3∩Δy＜3∩Δθ＜3的实验记为正确匹配实验, 其中正确匹配率为
|
(12) |
实验结果如图 3所示, 由图可知在不同噪声影响下T-LCSS均比LCSS方法具有更高的正确匹配率, 而文献[3]的匹配方法由于每一条等高线只生成一个控制点, 控制点的数量少、精度不高造成了正确匹配率低。实验验证本文提出的等高线地形匹配方法在噪声环境下具有更高的可靠性。
|
| 图 3 噪声环境下3种算法的正确匹配率 |
本文提出了一种基于等高线特征序列的地形匹配方法, 该方法可解决地形匹配中的如下问题:
1) 采用等高线的地形数据描述实现了数据降维, 采用PA特征点的CACD描述方法解决了噪声环境下等高线长度变化引起的等高线描述问题。
2) T-LCSS算法具有良好的去除野点的性能, 与传统LCSS的对比实验获得了更高匹配成功率与定位精度, 也为参数解算提供了更高的可靠性。
基于秦岭山区的大量实验验证本文方法在实时图存在旋转平移以及噪声的情况下鲁棒性好。
| [1] | Belongie S, Malik J, Puzicha J. Shape Matching and Object Recognition Using Shape Contexts[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2002, 24(4): 509–522. DOI:10.1109/34.993558 |
| [2] | Alajlan N, El Rube I, Kamel M S, et al. Shape Retrieval Using Triangle-Area Representation and Dynamic Space Warping[J]. Pattern Recognition, 2007, 40(7): 1911–1920. DOI:10.1016/j.patcog.2006.12.005 |
| [3] |
于秋则, 程辉, 田金文, 等.
基于等高线图与小波变换的3D地形匹配算法研究[J]. 宇航学报, 2004, 25 (3): 262–268.
Yu Qiuze, Cheng Hui, Tian Jinwen, et al. 3D Terrain Matching Algorithm Based on Iso-Elevation-Contour Map and Normalized Wavelet Description[J]. Journal of Astronautics, 2004, 25(3): 262–268. (in Chinese) |
| [4] | Rodriguez J J, Aggarwal J K. Matching Aerial Images to 3-D Terrain Maps[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 1990, 12(12): 1138–1149. DOI:10.1109/34.62603 |
| [5] |
黄伟国, 胡大盟, 杨剑宇, 等.
用于遮挡形状匹配的弦角特征描述[J]. 光学精密工程, 2015, 23 (6): 1758–1767.
Huang Weigoung, Hu Dameng, Yang Jianyu, et al. Chord Angle Representation for Shape Matching under Occlusion[J]. Optics and Precision Engineering, 2015, 23(6): 1758–1767. DOI:10.3788/OPE. (in Chinese) |
| [6] |
杨亚飞, 郑丹晨, 韩敏.
一种基于多尺度轮廓点空间关系特征的形状匹配方法[J]. 自动化学报, 2015, 41 (8): 1405–1411.
Yang Yangfei, Zheng Danchen, Han Min. A Shape Matching Method Using Spatial Features of Multi-Scaled Contours[J]. Acta Automatica Sinica, 2015, 41(8): 1405–1411. (in Chinese) |
| [7] | Vlachos M, Hadjieleftheriou M, Gunopulos D, et al. Indexing Multi-Dimensional Time-Series with Support for Multiple Distance Measures[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003:216-225 |
| [8] | Pinheiro A M G, Ghanbari M. Piecewise Approximation of Contours through Scale-Space Selection of Dominant Points[J]. IEEE Trans on Image Processing, 2010, 19(6): 1442–1450. DOI:10.1109/TIP.2010.2041415 |
2. Department of Control Engineering, Taiyuan University of Science and Technology, Taiyuan 030024, China
