An Integrated Map Matching Algorithm Based on Road Connectivity and Shortest Path
-
摘要: 本文研究了要素加权法、路网拓扑法和网格划分法等地图匹配算法,分析了地图匹配过程,包括地图数据预处理、道路连通性的建立、投影点的计算和道路匹配度的计算,提出了一种基于道路连通性,采用捕捉圆获取候选道路集的地图匹配算法,并且对车辆GPS信号丢失的情况,采用最短路径算法,推算出车辆经过的道路。最后通过试验比较分析,验证了本算法具有较高的匹配准确度、匹配速度和实用性。Abstract: Map matching algorithm of factor weighting method、road network topology and grid division is studied in the paper. The process of map matching is analysed,including map data preprocessing、the establishment of road connectivity、the calculation of the projection point and the road matching weight. Next, a map matching algorithm based on road connectivity is proposed,which uses the capture circle to obtain candidate road sets.When the GPS signal is loss, the shortest path algorithm is started to calculate out the way the car passed. Finally, the algorithm mentioned in the paper is compared with others by experiment. It is proved that the algorithm is with high matching accuracy, matching speed and practicability.
-
Keywords:
- GPS /
- map matching /
- connectivity /
- shortest path /
- capturing circle /
- travel route
-
0. 引 言
连续运行参考站(CORS)技术能够将卫星导航定位的精度提升至厘米级，是现代社会基础设施的重要组成部分[1]，为满足经济社会发展的需要，我国各个省份均建设有自己的CORS系统[2]. 目前，我国大部分的CORS系统中网络实时动态(RTK)服务均采用虚拟参考站(VRS)技术，VRS技术通过在用户附近虚拟出一个基准站，该基准站利用用户发送的位置数据获取，然后将观测数据发送给用户，从而获得厘米级精度的定位结果. VRS技术在通用性、兼容性等方面的优势，成为了目前应用最广泛的网络RTK技术[1-3]. 然而VRS技术也存在以下两个问题：
1)随着自动驾驶、人工智能等技术的兴起，CORS系统的用户已经不再局限于测绘地理信息领域，用户数量得到了极大地提升. VRS技术针对每一个用户都生成虚拟观测值，虚拟观测值生成时涉及到大量的计算工作，需要消耗大量的计算资源，无法满足海量级用户的高并发请求.
2)目前大部分CORS系统实时测量得到的成果为大地高，用户想要获取正常高成果，必需通过事后转换的方式. 由于各地政策不同，高程转换的流程和所需要的材料也不尽相同. 这种方式存在着效率低下、时效性差等缺点，不利于CORS系统的推广和应用，因此实时正常高成果的获取也是一个亟须解决的问题.
1. CORS正常高服务方法
1.1 技术思路
利用VRS技术距离较近用户可使用同一个虚拟参考值进行高精度定位的特点，按照一定的间隔，将CORS服务范围划分为多个格网[4]，在格网中心点生成VRS数据，并推送到专门的用户服务器，将数据解算与用户服务分离. 由于解算软件所需要生成的VRS数据是固定的，与用户数量无关，其解算压力也是恒定的，而用户服务器无需参与数据解算，可以采用分布式、云服务技术，根据用户数量进行实时扩容，能够满足海量级用户的高并发请求[5]. 用户实时测量想得到正常高成果，可以根据用户位置和似大地水准面模型，计算出用户的高程异常值，用户发送VRS数据时，将VRS坐标中的大地高加上高程异常值后，测量得到的结果就是正常高成果.
1.2 服务架构
系统通过将解算服务器与用户服务器分离，解算服务器按照格网点生成虚拟观测数据，并单向推送至用户服务器，用户服务器根据用户请求，在不改变用户使用习惯的前提下，提供高精度的位置服务. 其整体架构如图1所示.
1)虚拟格网差分数据生成：虚拟差分数据生成服务器将网络RTK的服务范围划分为多个格网，根据格网中心点的位置，向网络RTK服务器请求各个格网点的差分数据，虚拟出各个格网中心点的差分数据，并单向推送到数据代理服务器，数据代理服务器对虚拟差分数据进行解码，得到VRS坐标、虚拟卫星观测数据、VRS信息等数据[6].
2)高程异常数据获取：数据代理服务器接收到数据请求后，根据接收到的用户位置，通过服务器代理IP白名单、参数校验、接口签名安全套接层(SSL)加密等方式，向似大地水准面数据内核获取用户的高程异常值.
3)虚拟差分数据生成：获取到高程异常值后，将高程异常值加入用户所在格网的VRS坐标中，并重新进行编码，生成虚拟差分数据.
4)差分数据返回：虚拟差分数据通过用户播发服务器发送给用户，用户接收到虚拟差分数据后，与自身的卫星观测数据进行差分定位，获取高精度的定位结果，由于虚拟差分数据中的参考站坐标经过了高程异常改正，因此用户的定位结果也经过了高程异常改正，直接测量得到的成果为正常高.
2. 网格划分策略分析
CORS正常高服务将CORS服务范围按照一定的间距，划分为若干个格网，根据数字高程模型(DEM)，计算出每个格网中心点的坐标以及高程，根据计算出的坐标和高程，虚拟出该位置的虚拟观测值，将发送给用户的虚拟观测值中的参考站坐标大地高加上一个高程异常值，用户就可以直接测量得到正常高成果. 与传统的VRS技术相比，其VRS值的生成并不是根据用户的实时位置生成的，且在VRS值中的参考站坐标增加了一个高程异常值，因此需要进一步分析用户位置与格网点距离所引起的误差和VRS坐标变化所引起的误差，来确定适合的格网划分方案[7].
2.1 用户与VRS距离引起的误差分析
分析用户与虚拟参考距离所引起的误差以及定位性能，VRS数据生成软件采用天宝Pivot软件，流动站接收机采用天宝的R8接收机，通过格网化服务软件，生成了与流动站0~10 km距离的虚拟观测值，发送给接收机获取定位结果，每次测量60个历元，分别测量20次，其测结果如图2所示.
由图2可知，当流动站距离VRS小于5 km时，其均方根(RMS)值并没有明显的变化，小于10 mm，超过5 km后，其RMS值逐步升高，平面方向达到了2 cm，高程方向达到4 cm. 当VRS与流动站距离超过10 km后，出现了流动站无法初始化的情况. 因此为保证测量用户的精度，在进行格网划分时，用户距离格网点的最大距离不宜超过5 km.
2.2 VRS坐标变化对定位结果的影响
CORS正常高服务系统为用户提供正常高服务，是通过修改虚拟观测值中的参考站坐标来实现. VRS坐标的改变相当于起始点位置偏差，VRS与用户之间的基线向量会产生系统性偏差，系统偏差的大小与起始点位置偏差的大小成正比，与基线平均纬度的正切函数值成正比[8]. 湖南省位于纬度24°~30°，高程异常值最大约为18 m[9-10]. 根据文献[8]分析，在位于平均纬度30°，基准站坐标差为18 m时，其对基线结果的影响为1.68×10−6. CORS系统提供的网络RTK服务的平面精度为2.4 cm，高程精度为5 cm、按照误差传播定律，为了保证测量精度，由VRS坐标变化所引起的最大系统性偏差应小于1 cm，以减少对网络RTK用户的影响. 因此在湖南省范围内，用户与格网中心点的距离应小于6 km.
3. 实测精度分析
为验证整个系统的性能，本文在湖南省范围内开展了精度测试，其中格网化正常高服务系统采用的网格划分为3′×3′，该格网范围内距离中心最远为3.2 km，保证了格网最远点至中心的距离小于5 km，虚拟格网点的大地高利用湖南省的DEM数据和网格中心点的坐标来获取. 高程异常获取采用2017版本的湖南省似大地水准面模型(HNGG2017). 选取了湖南省范围内均匀分布的50个A、B、C级作为测试点，测试点的高程成果为水准高. 分别采用天宝Pivot软件和CORS正常高服务系统进行网络RTK定位测试，定位设备采用天宝R8设备. 测试时，每次观测采集60个历元，测量20次，取其平均值作为测量结果，天宝Pivot软件测量完毕后，采用2017湖南省似大地水准面 (HNGG2017)模型计算其正常高. 测试点位分布如图3所示.
我们对CORS正常高服务系统与Pivot的测量结果以及控制点真值进行对比，其结果分别如图4~5所示. 由图4可知， CORS正常高服务系统与天宝Pivot软件测量的平面差异为2 cm以内，高程方向的差异为4 cm以内，其平面精度为1.1 cm，高程精度为2.3 cm. 由于CORS正常高服务系统的虚拟观测值同样也是利用天宝Pivot软件生成的，其精度相当与CORS系统的内符合精度. 由图5可知，CORS正常高服务系统与控制点成果平面差异在4 cm以内，高程方向在10 cm以内. 经统计，其平面精度为2.7 cm，高程精度为4.9 cm. 与现有HNCORS系统的精度相当[11]，CORS正常高服务系统不会降低原有CORS系统的精度，能够满足高精度位置服务的需求.
另外，我们进一步对CORS正常高服务系统测量成果高程与真值对比超过8 cm的点进行分析，如表1所示，其中1983、U225两个点的差异达到了10 cm以上，主要是由于似大地水准面精化成果与控制点水准成果差异所引起的，其余超过8 cm的点似大地水准面精华成果与控制点水准成果差异也达到了2 cm 以上. 而大部分测量的控制点其差异小于8 cm，利用CORS正常高服务系统，完全能够满足地形测量对正常高成果的要求.
表 1 CORS正常高服务系统测量成果高程与真值对比超过8 cm的点cm 控制点 CORS正常高服务系统与
控制点水准高差异控制点似大地水准面
成果水准高差异1893 –10.15 –5.9 U225 –11.05 –9.6 U019 8.80 2.0 U288 –8.60 –2.6 2000 8.90 2.8 U159 9.50 2.6 4. 结束语
本文研究了基于格网的CORS正常高服务新方法，利用网格划分方式，生成CORS服务范围内各个格网中心点的虚拟观测值，通过在VRS中加入用户所在位置高程异常的方式，实现了实时的正常高程测量，解决了传统VRS技术存在用户上限了的问题，提升了服务能力. 由于用户直接得到正常高结果，使其无法反算出高程异常，在保证似大地水准面数据安全的前提下，提升了测量效率. 同时本文进一步分析了VRS与用户距离对定位精度的影响，确定了最佳的格网划分间隔，能够为其他省市高精度位置服务提供参考.
-
[1]周成,袁家政,刘宏哲.智能交通领域中地图匹配算法研究［J］.计算机科学, 2015, 42(10):1-6. 吴世全.基于浮动车数据交通参数提取技术探讨［J］.测绘与空间地理信息, 2013, 36(7):133-135. 朱征宇,崔明,刘琳.一种基于终端的地图匹配方法［J］.计算机科学, 2013, 40(5):291-295. 李清泉,黄练.基于轨迹数据的地图匹配算法［J］.测绘学报, 2010, 39(2):207-212. 李殿茜,王翌,刘垒.一种地图匹配算法的设计与实现［J］.导航定位与授时, 2017, 4(2):31-34. ORAN A, JAILLET P.A precise proximity-weight formulation for map matching algorithms［C］／／IEEE WPNC. IEEE, 2013:1-6. 王志建,王力,汪健.基于拓扑判断的海量数据延时地图匹配算法［J］.西南交通大学学报, 2012, 47(5):86-100. LEVIN R, KRAVI E, KANZA Y. Concurrent and robust topological map matching［C］／／International Conference on Advances in Geographic Information Systems. ACM, 2012:617-620. 廖佳,俞荐中,李俊峰.一种利用网格划分及方向加权的地图匹配算法［J］.测绘通报, 2017, 30(3):124-127. GUO B, TANG T, ZHOU D.A quick map matching algorithm for train locating based on grid partition［C］／／International Conference on Transportation Engineering. 2007:3197-3202. 罗跃军,宋向勃,郑莉.一种基于空间语义特征的浮动车轨迹匹配技术［J］.测绘通报, 2015, 1(3):108-110. YANG Y L, YE H, FEI S M. Integrated map matching algorithm based on fuzzy logic and dead reck-oning［C］／／International Conference on Control Automation and Systems. IEEE, 2010:1139-1142.［13]唐进君,刘芳.基于路径预测的不确定性推理组合地图匹配算法［J］.测绘学报, 2010, 39(5):546-550. -
期刊类型引用(5)
1. 田时雨，田挚，许欣欣，丁文玉. 似大地水准面精化工程标准化探讨. 测绘与空间地理信息. 2024(05): 31-33 . 
百度学术
2. 翟耀红. 基于变量投影算法的高程异常改进拟合方法. 测绘与空间地理信息. 2024(09): 182-184+187 . 百度学术
3. 何庆，欧阳霖，陈春花，靳文凭，张玉冰，史照清. 湖南省卫星导航定位基准站网服务体系建设及思考. 国土资源导刊. 2024(03): 1-8 . 百度学术
4. 张锡越，任政兆，朱照荣，张凤录，王攀，邵华勇. 基于北京2000坐标系的CORS应用. 北京测绘. 2023(04): 588-591 . 百度学术
5. 顾建祥，赵奕澎，陈燕. 基于卫星导航基准站网的海量实时解算与服务算法. 测绘通报. 2023(11): 48-53+138 . 百度学术
其他类型引用(1)
下载:
计量
- 文章访问数: 492
- HTML全文浏览量: 70
- PDF下载量: 105
- 被引次数: 6
