摘  要：停车场出入口是基础地图数据，采用传统人工采集方式时效性差。根据车辆进出地下停车场时GPS信号状态改变的特性，融合DR轨迹、车辆状态、陀螺仪倾角等多传感器数据，提出一种众包地图构建方法，使用DBSCAN聚类及多边形生成算法，挖掘出地下停车场区域范围、出入口及其通行方向。结果表明，该方法提取的出入口数据准确度高，应用于地图数据生产中可实现数据动态更新。导航时将起终点绑定到出入口道路上，可提供最优路线，指引用户进出停车场，改善用户体验。

关键词：车辆轨迹;密度聚类;停车场出入口;多传感器融合;末端导航

中图分类号：U491.7+1;TP311.52     文献标识码：A 文章编号：2096-4706（2020）04-0054-04

Abstract：The gateway to the underground parking lot is basic map data. Its difficult to guarantee data freshness under manual data collection conditions. According to the characteristics of GPS signal state change when vehicles enter and leave the underground parking lot，and the multi-sensor data such as DR track，vehicle state and gyroscope angle are integrated，a method of building crowdsourcing map is proposed. DBSCAN clustering and polygon generation algorithm are used to excavate the area range，entrance and exit of the underground parking lot and its traffic direction. The results show that the accuracy of gateway extracted by using this method is high. Application in map data production can implement dynamic data update. During navigation，the start and end points are bound to the access road，which can provide the best route，guide users to enter and exit the parking lot，and improve the user experience.

Keywords：vehicle trajectory;density clustering;gateway of parking lot;multi-sensor fusion;terminal navigation

0  引  言

有过开车经验的人相信都遇到过找不到停车场入口的尴尬。地图导航软件如何解决末端导航中的用户痛点是笔者工作中的研究课题。究其原因有二：一是导航算路时没有将规划路线的终点绑定到停车场入口道路;二是地图数据中停车场出入口数据覆盖率及鲜度都不足。以上海19Q1数据为例，现有图商数据中，关联了进出口道路的停车场只占总数的28%，且出入口的通行方向经常变化，导致数据准确性不高。传统人工采集停车场出入口数据时效性差，无法反映出入口的后期变化[1]。近年来互联网汽车的兴起讓车辆位置可以发送到云端，通过车辆轨迹大数据挖掘的手段，获取停车场对应的出入口，用全新的方式来补充现有停车场数据的不足。基于停车场出入口数据，改进导航软件中的路径规划算法，实现用户进出停车场时的精确引导。

在现有公开文献中，未见有地下停车场出入口、通行方向及其区域范围挖掘的详细论述。本文融合GPS信号状态、DR（惯性导航）轨迹、车辆状态等多传感器数据，通过DBSCAN聚类及多边形生成算法，提取停车场出入口及区域，取得了良好效果，提供了一种数据更新的新思路。

1  数据采集及预处理

1.1  车辆数据上报到云端服务器

1.1.1  DR轨迹数据

惯性导航系统（INS）是依据牛顿惯性原理，利用陀螺仪、加速度计等惯性敏感元件及初始信息来计算载体的姿态、速度和位置[2，3]。组合导航综合了INS的稳定性好及GPS的精度高等优点，可以提供高精度且稳定可靠的导航信息[4]，在地下停车场中GPS失效时，仍能提供准确的车辆位置。上报数据包含：车辆的DR轨迹、车速、行驶方向、GPS信号状态、陀螺仪识别到的道路坡度变化值。

1.1.2  车辆开关机状态

进出停车场时通常会有停车熄火、开车点火的动作。记录车辆开关机状态，可以区分出是由于进入地下车库还是建筑物遮挡导致的GPS信号丢失。

1.1.3  行程信息

如用户使用导航时行程中设置的起点和终点位置。停车场通常为用户的出发地或目的地，更多维度的信息有助于提升数据挖掘的准确度。

1.2  行程切分

上传到云端的轨迹数据是所有车辆数据的集合，需要根据每条轨迹记录中的车辆通用唯一识别码（UUID），提取出一辆车从进入到退出停车场的完整行驶路径;每辆车对应一个行程，每个行程可以表示一个用户的一次出行旅程。

1.3  出入口轨迹串提取

车辆在进入地下停车场时，GPS信号丢失，记录为无信号状态;相反，车辆在离开地下停车场时，GPS信号接收成功，变更为有信号状态。

根据这一特征可大致定位到出入口位置的轨迹点。同时考虑到GPS信号的不稳定性及存在GPS漂移问题，在GPS信号状态变更前后的连续若干个轨迹点都可能是实际出入口位置，这些包含有出入口位置的连续轨迹点本文称之为出入口轨迹串，可形式化描述为轨迹点的时间序列T=P1，P2，…，PN。由于用户一天的行程可能出入于多个不同的地库，因此同一行程又可以进一步切分为进出各个地库场景的轨迹子串。

1.4  道路匹配

道路匹配是指将单个用户行程中的连续轨迹点，根据行驶方向、经纬度，与基础路网中道路的方向和投影距离进行相似度比较，取相似度最大的道路作为匹配结果，从而将轨迹集映射为道路集。文献[5]通过路网拓扑关系来推测轨迹行进路径，以改善车辆轨迹数据在并行路段、立交桥等复杂道路场景中的地图匹配效果。

将轨迹点匹配到道路后，就可以根据道路属性、轨迹点与道路间的关系来过滤异常轨迹数据。

1.5  数据清洗

上述提到的每个行程的出入口轨迹子串，实际并不一定都是进出停车场的场景。需要排除由于高架道路遮挡、进出隧道等原因导致的GPS信号丢失。基于轨迹点匹配道路、车速、车辆行驶方向等数据进行筛选，以去除异常数据。

（1）因为在地库中车辆行驶速度受限，统计轨迹串中轨迹点速度大于30 km/h的个数，如果大于点总数的1/10，则认为是非地库场景。（2）轨迹串中是否存在类型为熄火或点火的信号，如果不存在，则认为是非地库场景;因为地库场景中存在典型特征是：车辆会有停车熄火或开车点火的信号。（3）轨迹点匹配到的道路必须不是高速、高架类型，以排除高架道路遮挡的原因导致的GPS信息丢失;同时也不会由高速高架路直接进入地下停车场（需要经由低等级道路进入）。（4）轨迹点匹配到道路的总数过多，如果大于预定值（点总数的1/5），则认为是非地库场景;因为地库范围内大概率存在地面建筑物，很少存在道路。（5）单个离散GPS信号丢失可能是由于周边建筑物的遮挡引起，可通过连续多帧GPS信号丢失状态来确认进入地库的场景。

1.6  停车场入口点确定

在每个行程终点附近，针对过滤异常数据后的出入口子串，可通过以下条件分析得到地下停车场入口的具体位置：（1）GSP信号状态由有信号变更为信号丢失状态。（2）存在连续多帧GPS信号丢失，且后续状态一直持续。（3）车库中车辆行驶速度受限，行驶速度<30 km/h（预定值）。（4）进入地库时车辆通常会有较大的转向角度。（5）陀螺仪识别到进入地下车库时的坡度变化（下坡）。

1.7  停车场出口点确定

针对每个行程起点附近，连续多幀数据成功接收GPS信号时，将首个成功接收GPS信号的位置点确定为出口点。由此可以分析得到地下停车场出口的具体位置，确定出口点的条件为：（1）此前车辆位于地下停车场区域。（2）出车库时，连续多帧数据成功接收GPS信号。（3）陀螺仪识别到退出地下车库时的坡度变化（上坡）。

2  停车场出入口聚类

针对所有车辆、所有行程中的入口点和出口点，分别进行聚类分析，得到地下停车场的出口和入口。DBSCAN算法由Martin Ester、Hans-PeterKriegel等人[6]在1996年提出。它有以下优点：（1）聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。（2）与K-Means比较起来，不需要输入要划分的聚类个数。

因为停车场出入口个数不确定，且车辆轨迹存在一定程度的漂移，选用DBSCAN来实现停车场出入口个数自动发现，根据DR位置精度设置EPS参数，排除漂移的轨迹点。

2.1  出入口位置聚类

基于轨迹点经纬度可计算出任意两点间的球面距离，使用该距离调整邻域距离阈值，对停车场出入口分别使用DBSCAN算法，参数设置如下：

EPS——在一个点周围邻近区域的半径;待聚类的数据集中，任意两个点之间的距离，反映了点之间的密度，说明了点与点是否能够聚到同一类中;文献[7]指出，民用GPS的定位误差为±10 m，设置距离阈值为10 m。

MinPts——邻近区域内至少包含点的个数;该参数依赖于参与聚类的轨迹串个数而定;根据经验采用数据集内样本数量的1/25[8]，设置个数为20。

2.2  出入口通行方向聚类

基于上述出入口位置聚类的结果，需要进一步识别出轨迹的行驶方向，从而标志为出口或入口。类似地，根据行驶方向对位置聚类结果进行二次聚类即可。

2.3  停车场出入口聚合

一个停车场会有多个出入口，而通过一次进出地库的行程只能提取出一对出入口;如何将不同行程的出入口关联到同一停车场？本文基于聚类簇和出入口成对关系进行停车场聚合，可挖掘出停车场对应的所有出入口：（1）从某一个聚类簇开始，簇内所有的出入口标记为同一停车场。（2）根据出入口成对关系找到另一个簇，而此簇内所有的出入口同样标记为此停车场。（3）以此类推，递归找到该停车场所有出入口。

3  停车场区域面聚合

将上述出口点和入口点之间的轨迹确定为地下停车场内部轨迹，基于所有行程的地下停车场内部轨迹，通过外接多边形生成算法，确定地下停车场区域。

（1）按天过滤聚类簇内没有成对的出入口轨迹（过滤入口或出口信息丢失的轨迹串，只保留同时有出入口的轨迹串）。（2）按天取完整出入口轨迹计算外接多边形凸包。（3）合并多天的凸包，得到停车场区域面。（4）建立停车场出入口与区域范围的关联。

4  停车场出入口在导航中的应用

基于上述停车场及其出入口数据，可以改善末端导航中缺乏引导信息或引导信息错误的问题。在以停车场为导航目的地时，现有主流导航软件都无法精确地引导用户到达停车场入口位置。在以地下停车场为出发地时，规划路线的开始道路往往不是停车场的出口道路，而是离车辆位置直线距离最近的道路（该道路不可直达）。这会导致当用户驶离停车场时，看不到规划路线，直到GPS信号良好时（通常需要较长的时间），才会提示用户重新计算路线。在新路线完成之前，用户实际无路线可引导，经常走错路口。

如图1所示，车辆以XXX地下停车场为起点，规划导航路线，现有导航软件规划的路线以距离车辆最近的B路优先匹配，作为起始道路;而本文通过停车场区域与当前位置点的包含关系，能够准确获取到所在停车场及其出口，规划路线起始道路为A路，即停车场出口道路，计算出最佳导航路线。

在停车场导航中，图2展示了基于出入口的路径规划策略;从停车场出入口道路精准地计算路线并引导，可解决用户进出停车场时无路线引导或引导路线错误的问题。

5  停车场出入口挖掘实例分析

5.1  实验数据

以上海为例，基于2019年10月份的轨迹数据，共挖掘出793个停车场，包含1 048个入口和1 049个出口。本公司设计的某停车场软件如图3所示，其中多边形区域为生成的某停车场区域，两个小圆点分别为进出口位置。经验证，多边形区域范围和出入口位置均与实际停车场数据相吻合。

5.2  实验结果评测

5.2.1  评测流程

考虑到人工验证的方式无法大量地评测挖掘结果，本文通过与图商采集到的停车场数据进行对比，实现大规模自动化评测，评测流程如图4所示。

5.2.2  评测标准

（1）图商停车场周边30 m范围内找到同类型的挖掘出入口，视为匹配成功;当距离超过30 m但匹配道路一致时，也视为匹配成功。（2）如果图商停车场在30 m范围内没有道路，说明该点误差太大，再扩大一倍搜索范围。（3）挖掘的停车场面只包括1个图商停车场，如果挖掘的出入口个数都匹配到图商出入口，只是图商个数多于挖掘的个数，仍视为成功。（4）挖掘的停车场面包括多个图商停车场，如果图商的出入口都能匹配到挖掘的出入口，忽略停车场名称误差，视为成功。

5.2.3  评测结果

（1）共有418个停车场关联到图商出入口，涉及挖掘的出口579个，挖掘的入口585个。（2）其中90.4%的停车场与图商数据匹配成功。（3）其中90.2%的停车场出入口与图商数据匹配成功。（4）在车辆接近停车场出入口时，DR轨迹会有一定程度的漂移，在GPS信號很差的情况下，聚类后的出入口点会与实际位置有所偏差。后续的改进方向，一是提升DR位置精度，二是收集更多的行程轨迹数据，以清洗掉漂移过大的轨迹点。

6  结  论

本文针对车辆进出地下停车场的场景，融合多传感器数据，如DR位置、GPS信号状态、车辆熄火点火状态、陀螺仪倾角，通过大数据挖掘的方式，成功提取出停车场区域及其出入口，经与图商采集到的停车场数据比较，有90.0%以上的匹配度，效果令人满意;这一思路可直接应用于实际数据生产中，以提高生产效率、提升数据鲜度。在导航算路时，将起终点位置绑定到停车场出入口道路上，可规划出最优路径，以解决用户末端导航时的引导焦虑问题，改善用户体验，具有很大的实用价值和应用前景。

参考文献：

[1] 傅梦颖，王培晓，张恒才，等.一种室内导航网络众包构建方法 [J].测绘科学技术学报，2019，36（1）：100-104.

[2] 秦永元.惯性导航：第2版 [M].北京：科学出版社，2014.

[3] 孙泽鹏.浅谈惯导发展及其分类 [J].山东工业技术，2017（17）：277.

[4] 杨新状，许承东，李怀建，等.SINS/GPS组合导航计算机系统设计与开发 [J].弹箭与制导学报，2004（1）：34-36.

[5] 张校慧，孙凯，职保平，等.针对复杂道路网络的车辆轨迹地图匹配算法 [J].测绘科学，2018，43（8）：110-115.

[6] ESTER M，KRIEGEL H P，J?RG S，et al. A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise [C]// AAAI Press.KDD96.Proceedings of the Second International Conference on Knowledge Discovery and Data Mining，1996（8）：226–231.

[7] 韩明锋，丁万庆，谢世杰.GPS误差概论 [J].测绘通报，1999（5）：3-5+11.

[8] 侯雄文.浅析DBSCAN算法中参数设置问题的研究 [J].科教导刊-电子版（下旬），2017（10）：266+277.

作者简介：蒋民锋（1978-），男，汉族，江西新余人，毕业于南京大学地图学与地理信息系统专业，硕士，LBS部门经理，研究方向：LBS数据挖掘及地图引擎研发。