EN中文

地球信息科学学报 >

2015 , Vol. 17 >Issue 10: 1172 - 1178

DOI: https://doi.org/10.3724/SP.J.1047.2015.01172

基于航向角变化的趋势集合轨迹特征划分算法

  • 李翔 , 1, * ,
  • 张江水 1 ,
  • 杨柏欣 2 ,
  • 王希 3
展开
  • 1. 信息工程大学地理空间信息学院,郑州 450001
  • 2. 93116部队,沈阳 110141
  • 3. 61206部队,北京 100042

作者简介：李翔（1987-）,男,博士生,研究方向为GIS辅助定位技术、嵌入式导航。E-mail:

收稿日期: 2015-03-16

  要求修回日期: 2015-04-30

  网络出版日期: 2015-10-10

基金资助

国家自然科学基金项目(41271450、41471336);“十二五”国家科技支撑计划项目(2012BAK12B02)

收起

An Extraction Algorithm of Track Features Based on Trend Set of Heading Angle Variable

  • LI Xiang , 1, * ,
  • ZHANG Jiangshui 1 ,
  • YANG Baixin 2 ,
  • WANG Xi 3
Expand
  • 1. Institute of Survey and Mapping, Information Engineering University, Zhengzhou 450001, China
  • 2. Troop 93116, Shenyang 110141, China
  • 3. Troop 61206, Beijing 100042, China
*Corresponding author: LI Xiang, E-mail:

Received date: 2015-03-16

  Request revised date: 2015-04-30

  Online published: 2015-10-10

Copyright

《地球信息科学学报》编辑部 所有
Fold

摘要

在GPS或网络信号受到干扰或遮蔽时,导航精度和自主性会大大降低,组合导航技术能弥补这一缺陷。针对组合导航匹配实时、快速和准确的应用需求,本文提出一种具有实时性、高准确性的基于航向角变化的趋势集合特征划分算法。该算法通过计算轨迹点的航向角变化量,对趋势确定集合和趋势待定集合的趋势状态进行赋值,能有效地划分出轨迹上各段的特征点集合。算法还对由外界因素（如超车、紧急避让和驾驶员不同驾驶习惯等）引起的无效特征情况,进行趋势集合状态的分析和判断,以保证特征划分的准确性。本文以北京西五环地区的车辆轨迹数据为例,进行了实地跑车实验表明,基于航向角的趋势集合特征划分算法,在实时性和提取效果方面,具有明显的优势,算法简单可行、高效、可操作性强。

关键词： 组合导航; 趋势集合; 趋势状态; 航向角; 特征划分

本文引用格式

李翔 , 张江水 , 杨柏欣 , 王希 . 基于航向角变化的趋势集合轨迹特征划分算法[J]. 地球信息科学学报, 2015 , 17(10) : 1172 -1178 . DOI: 10.3724/SP.J.1047.2015.01172

Abstract

When the GPS or a network signal is disturbed or obscured, the precision and autonomy of navigation will be greatly reduced. The integrated navigation technology can compensate for this defect. In view of the application requirements of real-time, quickness and accuracy of trail data and road data during the integrated navigation process, this paper puts forward a real-time, high accuracy algorithm which is entitled as an extraction algorithm of track features based on trend set of heading angle variable. The algorithm picks up the calculation and analysis of heading angle in trail data points for navigation, assigns values to the confirmed trend set and the pending trend set innovatively, which effectively improve the real-time aspect and the accuracy of this algorithm in the navigation trajectory data extraction, ensuring the efficiency and precision of the integrated navigation. This algorithm also provides analysis and judgment on trend set status for the invalid features which is caused by external factors (e.g. the overtaking, the emergency avoidance and the drivers’ driving habits). The invalid features will be filtered and eliminated using the buffer of the pending trend set, ensuring the accuracy of the feature extraction. The vehicle trajectory data in Beijing is used for conducting experiments. The results show that the extraction algorithm of track features based on trend set of heading angle variable has obvious advantages in real-time application and extracting effect, and the buffer judging with the pending trend set is able to rule out some invalid features and interferences caused by external factors. The proposed algorithm is not only simple and feasible, but also has high efficiency and strong maneuverability.

Key words： integrated navigation; trend sets; set status; heading angle; extraction of features

1 引言

现有地图匹配算法基本都在GPS导航基础上进行,由于GPS导航精度较高,采用垂直匹配法可取得较高的匹配精度,但在交叉路口或复杂路段会出现偏差,尤其是在一些具有信号干扰或无信号的遮蔽区域,定位精度将大大降低;而采用轨迹匹配法虽然精度较高,但实时性会受到限制。根据现在武器装备的特点,摆脱卫星导航在车辆导航中的应用,采用以惯性导航为主的组合导航系统进行自主导航有重要意义[1]。
车辆轨迹数据记录车辆行驶路径,是道路网络几何特征的直接反映。目前,轨迹数据一般通过车载定位设备如GPS、惯性导航系统等方式获取,所以,轨迹数据通常是以连接轨迹点而成轨迹线的形式进行矢量表达[2-5]。导航数据和道路数据的匹配效率和匹配度直接影响组合导航的精度和准确度,轨迹数据的特征划分方法则是影响匹配效果的主要因素。
传统的矢量特征划分方法,主要有道格拉斯-普克算法、曲率分析算法、最小二乘法的曲线拟合算法等[6-9]。道格拉斯-普克及其衍生算法计算量较大且不能有效保留特征点,造成矢量形状特征失真。不少学者针对分段道格拉斯法进行了改进,Hershberger和Agarwal等人提出了减少时间复杂度的改进方法[10-11],Wu等人提出了无自相交算法[12],还有一些学者引入遗传算法和动态规划算法对其优化[13-15],但大多只是对现有算法的改进且计算量较大,无法满足矢量轨迹数据的特征实时划分与同步匹配的应用需求[16]。
曲率分析和曲线拟合算法,是通过将轨迹线的整体曲线形状进行拟合分析与计算,对整体矢量形状特征的划分比较准确。但当遇到较为复杂的轨迹路段或连续缓慢转弯路段时,同样存在计算量过大的问题,且特征划分过程中需要整体轨迹数据,无法满足矢量轨迹数据的特征实时划分的要求。此外车辆在道路上行驶也会有很多干扰因素,如超车、紧急避让、驾驶员个性化的驾驶习惯等[17],所以,针对这些干扰特征的剔除是特征划分方法的关键。鉴此,本文提出了基于航向角变化的趋势集合轨迹特征划分算法,其以车辆行驶过程中各轨迹点的航向角变化趋势,利用集合对各个轨迹点状态的判断,划分出轨迹线中的不同特征段;同时还进行了实地试验,论证该方法的实用性。

2 基于航向角变化的趋势集合轨迹特征划分算法与应用

2.1 算法的原理

导航轨迹数据由一系列的轨迹点构成,每个轨迹点都存有该点的地理信息,如经纬度坐标、采集时间、航向角及累积行驶距离等。根据这些轨迹点地理信息可获取某一时刻任一轨迹点的运动趋势（如直行、左转弯或右转弯）。按照轨迹点的运动趋势变化,可将轨迹的特征理解为行驶过程中航向角变化趋势一致的一组位置序列,即实际行车中通过的一个曲率较大的弯曲路段,如道路转弯、交叉路口等突出的部分。
趋势集合按照时间序列将接收的轨迹点运动趋势信息依次存放,按照运动趋势的变化,对当前运动状态进行判断,并进行轨迹特征划分的实时追踪,当达到某一特定的轨迹特征结束条件,完成整个特征的划分并将归属于该特征的轨迹点提取出来。基于航向角变化的趋势集合轨迹特征划分算法采用递归方式,当系统接收到一个组合导航数据后,需判断其与之前的组合导航数据是否构成一个完整特征。
算法的目标是能实时准确地划分轨迹线的特征,排除由于外界影响因素（如超车、紧急避让等）造成的无效特征。为了提高特征划分的实时性和准确性,提出了趋势集合状态值、航向角变化量、同向运动状态、反向运动状态、直线运动状态等概念及其判断方法。

2.2 术语定义

（1）趋势集合：按照系统时间序列存放具有不同趋势状态的轨迹点的有序集合。
为了实时划分出轨迹的特征,本文定义了趋势确定和趋势待定2个集合：
① 记 C 为趋势确定集合,存放航向角变化趋势确定的轨迹点;
② 记 P 为趋势待定集合,存放航向角变化趋势中需接收更多导航数据后才能判断的轨迹点。
其中, C 和 P 是相互独立的2个集合,只有当 P 中元素满足某种特定条件后才能并入 C 。趋势集合具有以下特征：
① 确定性：集合中每一个对象都能确定满足该集合条件的元素;
② 互异性：集合中任意2个元素都是不同的对象,即 C 中的轨迹点是不同时刻接收到的轨迹点,各个轨迹点独立;
③ 有序性：由于系统根据时间序列接收轨迹点,所以,趋势集合中的各个元素按接收的时间先后进行排列。
（2）趋势集合状态：表示该趋势集合当前的航向角方向变化趋势, C 和 P 都有各自的状态值,分别记为 T c 和 T p ,二者相互独立,其赋值为：
T c = 0 趋势不明 - 1 表示航向角减少 1 表示航向角增加 （1）
T p = 0 趋势不明 - 1 表示航向角减少 1 表示航向角增加 （2）
为了准确地划分轨迹特征,剔除特征干扰,本文还定义一个临时趋势状态值,表示当前接收轨迹点（未进入任一个趋势集合）的航向角变化趋势,若该点前存在一个点位信息,则将该点的航向角信息与前一点相比较,以获得临时趋势状态值。
（3）航向角变化量：航向角是指车辆的行驶方向与正北方向之间的夹角,用以描述车辆的行驶方向和运动趋势。航向角变化量是记录有序的前后2个轨迹点航向角变化的值,用以对趋势集合状态的赋值。
△ ϕ = ψ - ψ - 1 - π ≤ ψ - ψ - 1 ≤ π ψ - ψ - 1 + 2 π ψ - ψ - 1 < - π ψ - ψ - 1 - 2 π ψ - ψ - 1 > π （3）
式中, ψ 和 ψ - 1 表示前一个轨迹点和后一个轨迹点的航向角。

2.3 算法的描述与构建

基于航向角变化的趋势集合轨迹特征划分算法,强调对导航轨迹数据点的航向角变化进行追踪和分析,算法针对接收到的相邻时刻的2个轨迹点航向角进行比较,应用航向角的变化量计算公式,对趋势集合的状态进行赋值。当前一点的运动趋势状态已知时,可作为 C 的趋势状态值,后一点则暂时进入 P 中进行运动趋势判断,从而快速实时发现导航轨迹的趋势变化。当后续点的趋势与前点相同时,则认定为有同向运动趋势,将 P 中的点并入 C 中,并继后续点接收判断。若2点的运动趋势不同,则认定为有反向运动趋势,后点仍存放在 P 中不作处理,作为待定趋势继续接收后续点进行判断。只有当轨迹点的航向角变化值,小于特定的直线状态阈值时,才作为一个完整的特征划分出来。利用趋势集合划分轨迹矢量特征的算法描述见表1,其关键技术路线如图1所示。
Tab. 1 An extraction algorithm of track features based on the trend set of heading angle variable

表1 基于航向角变化的趋势集合轨迹特征划分算法

基于航向角变化的趋势集合轨迹特征划分算法
输入：Ai=(Li,λi,ti,ψi,Tot_Distantce)(i=0,1,2,⋯,n) ←导航轨迹数据点
输出：轨迹特征点集合C
BEGIN
1. while(C=∅）
2. Ai⇒C; //初始化,将接收到导航轨迹数据的第一点存放入C中
3. else
4. i++,Ai+1⇒P; //将接收到导航轨迹数据点存放入P中
5. Δϕ=ψ-ψ-1,Tc=0,Tp=TAi+1; //计算该点的航向角变化,并给趋势状态赋值
6. while（Tc=0）
7. Tc=Tp,C=C⋃P,P=∅,Tp=0; //若C趋势不明,则将C和P合并,用P的趋势替换C,并将P清空
8. else
9. if(Tc=Tp) //若C和P趋势状态相同
10. C=C⋃P,P=∅,Tp=0; //将C和P合并,并将P清空
11. goto 14; //跳到步骤14,进行直线状态判断
12. else(Tc≠Tp) //若C和P趋势状态不同
13. goto 14;
14. ϕ=ϕ+Δϕ //计算航向角变化和,即该段时间内航向角的变化程度
15. if（|ϕ&gt;ϕs tr aight）//航向角变化大于给定直线状态阈值
16. goto 4; //返回步骤4,继续接收新的轨迹数据点进行判断
17. else
18. return C;//特征划分完毕,C即为特征点集合
END
首先,系统需完成趋势集合的初始化工作,将接收到的导航轨迹数据的第1个轨迹点直接存入 C 中,以备后续趋势的判断。然后,接收到的第2个轨迹点存入 P 中进行趋势待定判断,计算该点的航向角变化量,获得该点的状态值,并根据该点状态值分别给 C 和 P 进行状态赋值。将2个集合的状态值进行比较判断,若二者状态相同则2个集合内的轨迹点具有相同运动趋势,反之具有相反的运动趋势。按照集合中轨迹点的变化状态进行直线运动的判断,若该运动趋势完成后变为直线行驶,则可视为一个待检测特征。最后,将待检测特征进行特征干扰检测后,可将该特征包含的轨迹点集合提取出来,完成一个特征的划分。
Fig. 1 Overview of the proposed approach

图1 技术路线框图

2.4 算法特征划分的实例

（1）一般特征的划分
车辆在道路上的某个仿真行驶轨迹如图2所示。图2中实线连接而成的导航轨迹数据点组成的轨迹线,轨迹线上的各点表示算法根据时间序列接收到的单个轨迹点。
Fig. 2 The track feature

图2 轨迹特征示意图

图3描述了轨迹线上各点在特征划分过程的各个阶段趋势集合,以及趋势状态的变化,图中“+”、“-”表示趋势集合的当前状态,分别表示航向角增加、航向角减少。算法开始时航向角的趋势一致变化后,自m点开始持续反向变化,此时 P 和 C 的运动趋势不同,即 T c ≠ T p ,当前点留在 P 中,需进行后续点趋势状态判断。第m+1点的运动趋势与前一点相同,也保留在 P 中。直至第m+p点时, P 中所有的点航向角满足“反向运动状态”条件,认为航向进入持续反向转弯阶段,此时将 C 中轨迹点提取出来进行可匹配性检测,记为 C i ,并使 P 成为新的 C 。
Fig. 3 Result of the extraction algorithm of track features based on trend set of heading angle variable

图3 基于航向角变化的趋势集合轨迹特征划分算法示意图

本算法能实时分析轨迹点的运动趋势,快速地将特征集合划分出来,保证特征划分的效率和实时性。
（2）无效特征的划分
车辆在实际行驶过程中会遇到一些外界因素的影响,如超车、紧急避让和驾驶员个性化驾驶习惯等,都会改变导航轨迹数据点,对特征划分造成干扰,如图4所示。
Fig. 4 The invalid track feature

图4 无效特征示意图

图5描述了算法在判断无效特征过程中,各个阶段趋势集合及趋势状态的变化,图中“+”、“-”表示趋势集合的当前状态,分别表示航向角增加、航向角减少。从第1点到第m-1点航向角趋势变化一致,可按算法一般过程进行趋势集合的操作;自m-1点开始反向转弯,此时 P 开始存放并追踪第m-1后续点的趋势状态,判断其是否满足特征划分条件;但经过分析判断,直至第m+p点尚未满足“趋势反向运动状态”条件,第m+p点又恢复了前一转弯处的趋势状态。自第m+p点起,开始累加后续趋势一致的轨迹点数,若累计点数超过特定阈值,则认为存放在 P 中先前的趋势状态变化的轨迹点未形成完整的特征,即 P 中轨迹点为无效特征集合,可以合并入 C 中。
Fig. 5 The result of invalid track feature exaction

图5 无效特征划分示意图

本算法的另一特点是能有效地排除一些冗余无效的特征干扰轨迹点集合,保证特征划分的准确性。

2.5 算法应用实验结果与评价

为了验证算法划分轨迹特征的准确性和实际效果,本文对北京西五环阜石路地区约30 km的路段,进行了实地跑车实验,采集的数据为惯性导航实测轨迹数据。其中,平均车速为60 km/h;惯性导航中陀螺常值漂移量为0.05 °/h,随机漂移量为0.01 °/h,加速度计的初始零偏均值取10-4 g,随机零偏值为0.5′10-4 g,东向、北向和方位失准角的初始值取1°。算法每100 ms接收一次导航轨迹数据,进行轨迹特征的划分。
在相同配置环境下,针对不同长度轨迹路线的特征提取的效率进行比较（图6）,从结果看出,本算法相比传统曲率分析算法在处理效率上有一定的提高,而且随着数据量的增加,效率提高得愈加明显。
Fig. 6 The comparison of computation time between the proposed extraction algorithm and varisized curvature analysis in roads with different lengths

图6 针对不同长度路线轨迹特征提取用时及与曲率分析算法的比较

在相同机器配置环境下,针对同一路线两种算法的特征提取效率进行比较（图7）,从图7可以看出,本算法提取实时性比传统曲率分析算法强,随着路线点的推移不断进行特征的划分和提取,特征点数量变化较平滑;而使用曲率分析算法路线需经过整个曲线形状特征后才能进行提取,其在600~900 ms,1400~1800 ms和2300~2600 ms期间,特征点数量保持不变,一定程度上影响了系统效率。
Fig. 7 The comparison of the extraction point quantity for the same route

图7 针对同一路线2种算法的特征提取点数量的比较

将5 m定距采集到的轨迹矢量数据集构成的原始轨迹数据图,应用趋势集合划分轨迹特征算法进行特征划分（航向角变化量的直线状态阈值取3 ° ）,结果如图8所示。实验结果表明,本文算法能实时快速地完成导航轨迹数据点的特征划分,车辆通过相应路段后,划分的轨迹特征能及时反馈系统,且轨迹特征提取效率良好,轨迹基本形状特征被完整划分出来,保证了特征划分的效率和实时性。
Fig. 8 The extraction algorithm of track features based on trend set of heading angle variable

图8 基于航向角变化的趋势集合轨迹特征划分算法效果图

本文利用“提取准确率=正确提取的有效特征点数量/组合导航匹配所需的特征点数量”对特征提取结果进行定量评价。
根据上述评价指标,对本文得到的车辆轨迹特征点进行了统计,如表2、3所示。
Tab. 2 Statistics of the test results for the extraction of track features based on the proposed algorithm

表2 基于航向角变化的趋势集合轨迹特征划分实验统计表

路线 里程(km) 总点数 特征总点数 有效特征点数 提取准确率(%)
1 3 812 137 125 91.0
2 4 1474 255 235 92.3
3 2 371 68 62 91.2
4 3 560 89 81 91.0
总计 12 3217 549 454 91.6
由表2和表3的实验统计结果表明,本文算法能较好地提取有效轨迹特征,其准确率达到91.6%,相比传统的曲率分析算法（80.0%）,有了较大的提高,能满足地图匹配特征划分准确性的要求。而无效特征主要是由因超车变道、紧急避让等外界因素造成。如图9所示,算法还针对由于外界干扰因素造成无效轨迹特征的划分进行了实验分析。图9中虚线圈的轨迹是由外界因素造成车辆行驶状态发生的改变而形成的轨迹,按照算法中2个趋势集合的判断方法,对其航向角变化趋势进行分析和判断,将圈中轨迹点作为无效特征集合并入该段特征集合中,从而剔除了无效特征的影响。
Fig. 9 Quality of the extraction of the interference features

图9 无效特征划分效果图

Tab. 3 Statistics of the test results for the extraction of track features based on varisized curvature analysis

表3 基于曲率分析特征划分实验统计表

路线 里程(km) 总点数 特征总点数 有效特征点数 提取准确率(%)
1 3 812 137 112 81.8
2 4 1474 255 201 78.8
3 2 371 68 51 75.0
4 3 560 89 75 84.3
总计 12 3217 549 454 80.0

3 结语

面对组合导航过程中对导航轨迹数据和道路数据的匹配实时、快速和准确的应用需求,尤其是一些具有信号干扰或者遮蔽区域的情况下,本文提出了基于航向角的趋势集合特征划分算法,根据轨迹点航向角的变化,建立2个趋势集合,对导航轨迹数据进行了特征实时地划分和提取。实验结果表明,该算法在实时性和提取效果方面具有明显的优势,趋势待定集合的缓冲判断,能排除一些特殊因素造成的无效特征和干扰,提高了特征划分的准确性和实时性,可操作性较强。算法能满足后续组合导航匹配工作的要求。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
许建国,张志利,周召发.交互式地图匹配算法在组合导航中的应用[J].上海交通大学报,2013,47(8):1323-1328.

[2]
梁昆,杨明,王春香,等.基于低精度GPS的智能车视觉导航方法[J].上海交通大学学报,2011,45(2):168-173.

[3]
刘为任,王宁,刘国彬,等.一种双惯导组合导航方法[J].中国惯性技术学报,2014,22(1):1-5.

[4]
崔留争. MEMS-SINS/GPS组合导航关键技术研究[D].长春:长春光学精密机械与物理研究所,2014.

[5]
杨得志,王杰臣,闾国年.矢量数据压缩的Douglas-Peucker算法的实现与改进[J].测绘通报,2002(7):18-21.

[6]
李星军,杨海忠.基于曲率分析的地图匹配算法研究[J].科学技术与工程,2012,12(29):7664-7668.

[7]
李翔,张江水,盖世豪,等.一种基于路网曲线特征和惯导测量数据的辅助导航定位方法[J].测绘科学技术学报,2013,30(2):210-213.

[8]
Mantoro T, Abubakar A I, Ayu M A.3D maps in mobile devices: Pathway analysis for interactive navigation aid[J]. International Journal of Mobile Computing and Multimedia Communications (IJMCMC), 2013,5(3):88-106.

[9]
罗国玮,张新长,齐立新,等.矢量数据变化对象的快速定位与最优组合匹配方法[C].中国地理信息科学2014学术年会论文集,2014:114-122.

[10]
Ren M, Karimi H A.Adaptive road candidates search algorithm for map matching by clustering road segments[J]. Journal of Navigation, 2013,66(3):435-447.

[11]
Attia M, Moussa a,El-Sheimy N . Map aided pedestrian dead reckoning using buildings information for indoor navigation applications[J]. Positioning, 2013,4(3):227-239.

[12]
陈飞翔,周治武,张建兵.基于动态规划算法的矢量数据压缩改进算法[J].计算机应用,2008,28(1):168-170.

[13]
李珂,杨杨,邱雪松.城市汽车导航中一种改进的D-S证据理论地图匹配算法[J].测绘学报,2014,43(2):208-213,220.

[14]
肖维丽,岳春生,奚玲.基于匹配误差的导航图路网数据预处理技术研究[J].信息工程大学学报,2014,15(3):375-379.

[15]
赵东保,刘雪梅,郭黎.网格索引支持下的大规模浮动车实时地图匹配方法[J].计算机辅助设计与图形学学报,2014(9):1550-1556.

[16]
蒋益娟,李响,李小杰,等.利用车辆轨迹数据提取道路网络的几何特征与精度分析[J].地球信息科学学报,2012,14(2):165-170.

[17]
陈焕明,郭孔辉.基于航向角和位置偏差控制的驾驶员模型[J].农业机械学报,2013,44(10):36-40.

Options
文章导航

/

〈 〉