1 引言
随着GPS移动定位技术的日臻成熟, 越来越多的智能终端配备了时空定位的功能, 实时采集移动位置信息, 形成蕴含城市人口移动行为的时空轨迹大数据, 基于GPS时空大数据的路网信息挖掘及知识发现成为领域研究热点[1]。
本文结合GeoHash和K近邻算法, 提出一种新的城市交叉路口识别方法。利用GeoHash编码对GPS轨迹数据和轨迹活动区域进行编码处理, 有效地降低待处理轨迹点的计算规模, 使得算法在识别效率上优于基于经纬度坐标系数据集; 使用K近邻的分类思想识别交叉路口, 不受因交通模式变化而导致的GPS轨迹采样频率变化的影响, 从而适用于多交通方式混合产生的GPS轨迹数据集上的交叉路口识别, 具有较强的通用性。
2 研究现状
围绕如何利用GPS轨迹数据识别交叉路口的问题, 现有的部分研究根据计算轨迹数据集中蕴含的角度、速度变化等特征进行判断。Karagiorgou等基于车辆轨迹数据, 利用转向角度和轨迹点间距离的变化计算单条轨迹蕴含的“转折点”, 然后对这些“转折点”进行聚类分析, 得到整体交通路网的交叉点[17]。Liu等在Karagiorgou等的研究基础上, 提出更细粒度的道路交叉点, 将聚类细化到车道级别[18]。Huang等研究低采样率下的轨迹数据集上的交叉路口识别问题, 在轨迹聚类的基础上, 引入轨迹曲线变化特征实现交叉路口的识别, 并在武汉出租车数据集上验证了方法的有效性[19]。唐炉亮等提出基于“转向点对”的城市交叉路口识别方法, 采用基于局部点连通性的聚类方法对“转向点对”进行空间聚类, 并利用“交叉口范围圆”和“转向点对”提取城市各级别路网下的交叉路口结构[20]。上述方法尝试提取不同的轨迹特征或特征组合提高交叉路口识别的精度, 但是这些算法均需事先设定相关指标的阈值, 如果阈值设置不当往往导致错误的识别。
Xie等指出, 基于阈值设定的交叉路口识别方法具有局限性, 较低的阈值设定使得非交叉路口被错误识别, 而较高的阈值设定导致无法识别所有真实存在的交叉路口, 他们研究并提出了一种新的基于最长公共子序列(Longest Common Subsequence, LCS)的交叉路口识别算法: 对原始轨迹进行两两的相似性比较, 获得最长公共子序列并分段; 基于交叉路口即连接三个及以上不同方向道路的事实, 在子序列的起始点和终止点位置处进一步进行交叉路口判定[21]。该方法无需轨迹特征的相关阈值设定, 但需要对数据集中所 有轨迹进行相似性的两两比对, 算法的时间复杂度 较高。
综上, 现有基于活动轨迹集的交叉路口识别方法多数采用设定角度、速度、距离变化等属性相应的阈值, 进而使用聚类或者分类的算法对交叉路口进行识别。这些方法更适用基于采样频率较稳定的单一交通方式形成的轨迹, 通常为车辆数据。在真实的城市移动人口轨迹数据采集环境中, 轨迹产生的交通方式可能是步行、自行车、公交车等多种交通模式混合, 即使在同样的采集频率下, 同一条轨迹中不同位置点的密度也可能具有较大差异, 使得阈值设定的方法更加难以实现, 限制了此类方法的通用性。
3 研究思路与框架
本文提出一种新的基于GPS轨迹数据的城市交叉路口识别方法, 如图1所示, 包括数据预处理模块、GeoHash编码模块、特征集提取模块和交叉路口识别模块。
图1
(1) 数据预处理模块实现对原始GPS轨迹数据分段等预处理工作。用户在混合交通模式下产生的移动轨迹, 由“行程段”及“活动段”组成[22]。其中, “行程段”是用户在移动过程中, 速度、密度和角度等移动参数较稳定情况下产生的轨迹, 通常代表较明显的道路几何特征; “活动段”则代表用户在某一区域或兴趣点停留所产生的轨迹, 是交叉路口识别中的噪声数据, 需在预处理阶段去除。
(2) GeoHash编码模块实现GPS轨迹点及轨迹活动区域的编码和分格处理。经过GeoHash编码, 将原始轨迹中二维的经度和纬度坐标转化为一维的GeoHash字符串编码。进而, 对轨迹的活动区域进行同一粒度下的编码分格, 获取代表活动区域的GeoHash编码矩阵。
(3) 特征集提取模块使用编码轨迹序列和区域编码矩阵构建二值化融合矩阵, 实现交叉路口的特征矩阵选择。选取一定范围的轨迹活动区域进行样本特征的学习, 将区域内的轨迹序列和区域编码矩阵中的矩阵元素进行映射, 并将映射结果构建为二值化融合矩阵, 形成表示轨迹交叉点的正负样例特征集合。
(4) 识别模块实现带有滑动窗口的K近邻算法的交叉路口识别。利用同特征矩阵等大的滑动窗口, 按一定顺序滑过融合二值化矩阵, 对测试实例与训练集中的特征矩阵进行计算, 实现交叉路口判定和识别。
与传统方法相比较, 本文方法的优势在于: 不受交通模式变化而产生的GPS轨迹采样频率的影响, 对用户产生的轨迹数据做统一处理, 适用于混合交通模式下产生的高低频混合GPS轨迹的交叉路口识别; 利用GeoHash编码对GPS轨迹数据和轨迹活动区域进行编码处理, 有效降低了待处理的轨迹点数量和计算时间复杂性, 使得算法在识别效率上优于基于经纬度坐标系数据集; 使用K近邻的分类思想识别交叉路口, 不受交叉路口形态的影响, 算法具有较好的通用性。
4 算法设计与实现
4.1 问题描述及相关定义
为更深入地展开研究和讨论, 对本文所涉及的概念做如下的定义和描述。
定义1 原始GPS轨迹$T$, 记录着移动对象在时空上的有序运动所产生的信息。记为:
$T=\{{{P}_{1}},{{P}_{2}},\cdot \cdot \cdot ,{{P}_{n}}\},$
${{P}_{i}}=(lat,lon,t)\ \ (0\le i\le n)$
其中, ${{P}_{i}}$表示移动轨迹点, $lat\mathrm{(}\mathrm{)}lon$(经度)表示位置信息, $t$表示处于当前位置的时间信息。
定义2 GeoHash编码轨迹$T\text{ }\!\!\_\!\!\text{ }Geo$, 是利用GeoHash算法对原始轨迹T进行编码转换后的轨迹码, 记为:
$T\text{ }\!\!\_\!\!\text{ }Geo=\{G{{P}_{1}},G{{P}_{2}},\cdot \cdot \cdot ,G{{P}_{n}}\},$
$G{{P}_{j}}=(GeoHas{{h}_{j}},{{t}_{mid}})\ \ (1\le j\le n)$
其中, $G{{P}_{j}}$表示经过GeoHash编码后的轨迹码, 原始轨迹序列T中经过同一区域的若干个轨迹点经过计算转换为相同的GeoHash编码, ${{t}_{mid}}$表示当前区域内轨迹点的时间中值。原始轨迹$T$和GeoHash编码轨迹$T\text{ }\!\!\_\!\!\text{ }Geo$的转化关系如图2所示。
图2
定义3 区域编码矩阵${{G}_{mn}}$, 是一个地理区域抽象成的编码矩阵。利用GeoHash算法对整个轨迹活动的区域进行编码和分格, 矩阵中的每个GeoHash编码元素代表固定大小的矩形地理区域, 整个轨迹活动区域用编码矩阵${{G}_{mn}}$表示。
定义4 二值化融合矩阵${{H}_{mn}}$。将GeoHash编码轨迹$T\_Geo$与区域编码矩阵${{G}_{mn}}$进行融合, 利用区域编码的唯一性, 则$T\_Geo$中每个GeoHash编码对应的${{G}_{mn}}$形成二值化融合矩阵${{H}_{mn}}$。
4.2 基于GeoHash编码的格网化
表1 GeoHash编码字符串长度与误差对应关系表①(① https://en.wikipedia.org/wiki/Geohash.)
| 字符串长度 | 误差(km) | 字符串长度 | 误差(km) | 字符串长度 | 误差(km) |
|---|---|---|---|---|---|
| 1 | ±2500 | 4 | ±20 | 7 | ±0.076 |
| 2 | ±630 | 5 | ±2.4 | 8 | ±0.019 |
| 3 | ±78 | 6 | ±0.61 | 9 | ±0.002 |
依照GeoHash的特性, 对整个活动区域进行划分, 形成编码矩阵${{G}_{mn}}$。图3为一个地理区域被迭代划分为若干个GeoHash矩阵单元格的过程, 在同样的编码精度$\alpha $下, 采用GeoHash算法对空间位置进行“Z”字形的曲线空间划分, 计算所得字符串编码前缀的重合位数越高, 其地理位置越接近。
图3
4.3 K近邻算法实现交叉路口识别
设计一个带滑动窗口的K近邻分类器, 将基于GPS轨迹数据识别交叉路口的问题转化为一个有监督学习的二分类问题。在模型构建阶段, 随机选取若干区域形成训练集, 提取训练集中交叉路口的特征, 形成K近邻算法的特征集合。将该区域内所有GeoHash编码轨迹$G{{P}_{j}}$, 映射到该区域编码矩阵${{G}_{mn}}$中, 通过二值化处理, 得到一个0、1矩阵。在交叉路口特征实例集合中, 每个矩阵都表示一个特定标识和类别的轨迹交叉路口。在分类识别阶段, 设计一个和特征实例样本同样大小的滑动窗口, 依次对待测区域的特征提取形成特征矩阵${{H}_{mn}}$, 并将特征矩阵进行K近邻分类, 实现交叉路口的判定, 如图4所示。带滑动窗口的K近邻算法如算法1所示。
图4
5 实验结果分析
5.1 实验数据集描述
表2 GeoLife数据集中轨迹点数据结构样例
| 纬度 | 经度 | 海拔(英尺) | 转化日期 | 日期 | 时间 |
|---|---|---|---|---|---|
| 39.9066 | 116.3855 | 49 240 097 | 586516198 | 2009-10-11 | 14:04:30 |
| 39.9065 | 116.3856 | 49 240 097 | 586516203 | 2009-10-11 | 14:04:35 |
GeoLife数据集中的轨迹采集自不同的GPS记录仪和GPS手机, 记录了用户在驾车、乘坐公交车、步行时的轨迹, 轨迹中记录的出行方式具有多样性和交替性, 是典型的混合交通模式下产生的高低频混合的用户轨迹数据集。
5.2 GeoHash编码
本实验基于GeoHash算法实现轨迹点的统一编码处理, 需要确定编码的精度a。a的取值在参考数据集中轨迹点的间隔距离基础上, 满足编码的连续性, 将GPS轨迹序列T转化为GeoHash编码轨迹T_Geo, 同时满足二者的几何相似性。混合交通模式下轨迹点间间隔分布如图5所示, 其中, 横坐标是轨迹点间的距离, 纵坐标是该距离下的轨迹段数量。
图5
数据集中轨迹点间的间隔集中在0-10米间, 轨迹点间的平均距离为7.35m, 因此最终确定采用8位的GeoHash编码对轨迹点和地理区域进行处理。当a=8时, 将原始的GPS轨迹T转化为GeoHash编码轨迹T_Geo, T_Geo具有与原始轨迹T相似的几何形态, 如图6所示。
图6
原始轨迹点数量和GeoHash编码后数据规模的对比结果如图7所示。实验表明, 经过GeoHash编码, 数据集规模减少, 其平均缩减率达到原有轨迹点数量的39%, 数据规模的缩减降低了识别轨迹交叉路口问题的计算复杂度。
图7
5.3 交叉路口识别
交叉路口在空间结构中呈现出多种形态, 同类交叉路口类型具有相似的轨迹特征。在构建交叉路口特征矩阵时, 在地图上定位交叉路口区域范围, 将该区域内GeoHash编码轨迹中的GPi编码映射到区域编码矩 阵Gmm中, 形成融合矩阵Hmm, 最终将Hmm转化为二 值化矩阵。本实验采用矩阵的大小为15×15, 实验构建的部分交叉路口正负样本示例及其特征矩阵如图8所示。
图8
训练集构造完成, 便可在轨迹活动区域内进行轨迹交叉路口的识别和位置标注。选定北京市海淀区为测试区域, 经纬度范围为: 经度(116°19′0″E, 116°23′0″E), 纬度(39°58′13″N, 40°01′00″N)。该区域中共包含75条用户轨迹数据, 总轨迹点数约85 000个坐标点。
将这些散列的轨迹点整合到同一个GeoHash编码粒度的融合矩阵中: 初始化一个和区域编码矩阵同样大小的全0融合矩阵$H_{mn}^{1}$, 保证两个矩阵所代表的区域大小一致, 也保证了矩阵内坐标编码的对应关系; 将所有$T\_Geo$中的代表位置GeoHash编码映射到区域编码矩阵中, 如果寻址成功, 在全0的初始矩阵相应的位置作加1操作。当所有的轨迹点都投影结束, 获得一个新的融合矩阵$H_{mn}^{2}$, 矩阵中的每个单元格对应一个GeoHash编码区域所停留的轨迹点的数量。最后, 将矩阵$H_{mn}^{2}$转化为一个150×191的0、1矩阵$H_{mn}^{3}$。矩阵$H_{mn}^{3}$示例如图9所示。
图9
通过滑动窗口解决实例特征矩阵选取的问题, 滑动窗口的大小和特征矩阵样本的大小保持一致。在该分类器中, 参数K值设置为10, 滑动窗口步长p设为1。在带有滑动窗口的K近邻算法识别过程中, 将每次滑动窗口取得的矩阵文件和特征集合中的样本矩阵, 均按照首尾顺序链接, 转化为一个1×225的向量, 然后利用欧氏距离进行计算和排序。实验结果可视化如图10所示, 其中, 红色的点表示由本文方法识别的交叉路口, 绿色的点表示参照路网进行标识的交叉路口。
图10
5.4 对比实验结果
实验结果如图11所示, 其中, 横坐标d为误差距离, 表明交叉路口识别的容错范围。纵坐标${{I}_{TP}}$、${{I}_{FN}}$、${{I}_{FP}}$分别表示随着距离d的变化, 交叉路口识别算法成功匹配的交叉路口数量、未识别的交叉路口数量、算法识别出但在路网中不存在的错误识别的交叉路口数量。图11表明, 随着距离d的增加, 采用本文方法与对比实验中方法的${{I}_{TP}}$、${{I}_{FN}}$、${{I}_{FP}}$值逐渐收敛并趋于稳定。但是, 如图11(a)所示, 本文方法在距离d为50m时, 数值趋于稳定, 成功匹配的交叉路口数量${{I}_{TP}}$占真实交叉路口的比例达61%, 在距离d为100m时达75%; 而图11(b)表明, 采用基于转向角度的识别方法, 当距离d为100m时才趋于稳定, 距离d为200m时${{I}_{TP}}$的占比为60%。实验结果表示, 本文所提交叉路口识别方法的识别精度和数量均优于传统的基于转向角度的交叉路口识别方法。
图11
为进一步量化本文方法的识别效果, 分别计算精确率P、召回率R和综合评价指数的分值$F1\mathrm{-}Measure$, 计算方法如公式(1)至公式(3)所示。
在距离为50m时, 基于转向角度的方法和本文方法的精确率、召回率和F值如表3所示。
实验结果表明, 本文方法具有较高的精确率, 此外, F值也优于基于转向角度的方法, 体现了本文方法在交叉路口识别问题上的有效性。
5.5 识别结果分析和讨论
上述实验表明, 本文方法识别的结果存在识别出的交叉路口在路网中并无标注的集合${{I}_{FP}}$, 以及路网中存在、但未被识别的交叉路口集合${{I}_{FN}}$。结合地图信息, 对${{I}_{FP}}$和${{I}_{FN}}$产生的原因做进一步分析。
图12
对于本文并未识别出的交叉路口集合IFN, 经分析, 其产生的原因主要是由于实验数据集在该区域轨迹数据稀疏, 或者是用户行为轨迹并未体现出交叉特性所致。如图13所示, 位于北京市北四环的展春二桥和牡丹园附近, 虽然位置处于交叉路口, 但是参照本文实验的轨迹数据分布, 并未出现交叉特性。随着GPS用户移动轨迹数据的丰富和完备, 本文所提交叉路口识别方法的准确性会得到进一步提升。
图13
未来可结合GPS轨迹点的高程信息, 实现立体交叉路口等基于三维轨迹数据信息的立体道路识别。此外, 还可结合轨迹中的时间信息、轨迹相关的POI信息实现更加丰富的轨迹蕴含信息的数据挖掘。
6 结 语
围绕基于GPS轨迹数据识别城市交叉路口的问题, 本文提出一种使用GeoHash编码和带有滑动窗口的K近邻算法结合的交叉路口识别方法。利用GeoHash算法分别对轨迹和轨迹活动区域进行编码和分格, 将轨迹编码与区域编码矩阵进行融合处理, 构造代表不同交叉路口和非交叉路口模型的特征矩阵集合。最后选取活动区域, 利用带有滑动窗口的K近邻算法实现交叉路口识别。通过真实的混合交通模式下的轨迹数据集进行实验表明, 本文所提交叉路口识别方法具有较强的通用性, 且识别精度和数量均优于传统的基于转向角度的交叉路口识别方法, 当误差距离为50米时, 综合评价指数的分值$F1\mathrm{-}Measure$达到0.82。本文参照路网, 对错配和未能匹配成功的情况结合地图信息进行分析, 进一步探讨基于GPS轨迹的交叉路口识别方法在路网建设中的意义。
致谢:
感谢应用经济学与管理学国家级实验教学示范中心为本实验提供的实验支持。
作者贡献声明
高原, 王东: 提出研究思路, 设计研究方案, 撰写论文;
王东: 进行实验;
段治州, 施元磊: 采集清洗和分析数据;
高原, 冯宏伟: 论文最终版本修订。
利益冲突声明
所有作者声明不存在利益冲突关系。
支撑数据
支撑数据由作者自存储, E-mail: hellation@126.com。
[1] 王东. GeoLife.db. GeoLife. GPS轨迹数据集合.
[2] 王东. beijing.osm-line.shp. 北京市路网数据.
[3] 王东. Data.zip. 城市交叉路口识别算法.
参考文献
45(4): Article
No.
基于长短记忆型卷积神经网络的犯罪地理位置预测方法
[J].
Predicting Crime Locations Based on Long Short Term Memory and Convolutional Neural Networks
[J].
Personalized Travel Route Recommendation Using Collaborative Filtering Based on GPS Trajectories
[J].DOI:10.1080/17538947.2017.1326535 URL [本文引用: 1]
A Comparison and Evaluation of Map Construction Algorithms Using Vehicle Tracking Data
[J].DOI:10.1007/s10707-014-0222-6 URL [本文引用: 1]
SMOPAT: Mining Semantic Mobility Patterns from Trajectories of Private Vehicles
[J].DOI:10.1016/j.ins.2017.10.043 URL [本文引用: 1]
Automatic Intersection and Traffic Rule Detection by Mining Motor-Vehicle GPS Trajectories
[J].DOI:10.1016/j.compenvurbsys.2016.12.006 URL [本文引用: 1]
Learning Traffic Signal Phase and Timing Information from Low-Sampling Rate Taxi GPS Trajectories
[J].DOI:10.1016/j.knosys.2016.07.036 URL [本文引用: 1]
时空数据建模方法研究综述
[J].
Review of Spatio-temporal Data Modeling Methods
[J].
Road Extraction from Very High Resolution Remote Sensing Optical Images Based on Texture Analysis and Beamlet Transform
[J].
An Automatic Road Network Construction Method Using Massive GPS Trajectory Data
[J].
Recent Progress in Road and Lane Detection: A Survey
[J].
DOI:10.1007/s00138-011-0404-2
URL
[本文引用: 1]
The problem of road or lane perception is a crucial enabler for advanced driver assistance systems. As such, it has been an active field of research for the past two decades with considerable progress made in the past few years. The problem was confronted under various scenarios, with different task definitions, leading to usage of diverse sensing modalities and approaches. In this paper we survey the approaches and the algorithmic techniques devised for the various modalities over the last 5 years. We present a generic break down of the problem into its functional building blocks and elaborate the wide range of proposed methods within this scheme. For each functional block, we describe the possible implementations suggested and analyze their underlying assumptions. While impressive advancements were demonstrated at limited scenarios, inspection into the needs of next generation systems reveals significant gaps. We identify these gaps and suggest research directions that may bridge them.
高分辨率遥感影像中的道路信息提取与表达方法研究
[D].
Research on Road Extraction and Representation from High Resolution Remote Sensing Images
[D].
高分辨率遥感图像道路交叉口自动提取
[J].
DOI:10.6046/gtzyyg.2016.01.10
URL
[本文引用: 1]
道路交叉口是道路网络(简称路网)的重要组成元素,获取道路交叉口对提取路网信息、影像匹配和车辆导航等有重要作用。然而,基于遥感图像对道路交叉口自动提取的研究尚不多。针对高分辨率遥感图像中道路交叉口的特点,提出一种自动识别道路交叉口的方法。在图像预处理的基础上,首先对图像进行多尺度圆形均匀区检测,使用梯度变换和形态学变换提取可能存在道路交叉口的候选区;然后对候选区进行特征提取和进一步筛选,得到候选道路交叉口的位置中心;最后提取位置中心的角度纹理信息,通过波谷检测判断其连接属性,识别出道路交叉口。结果表明,该方法能有效提取出城市地区的道路交叉口,对于较复杂地区的道路交叉口提取也有一定的效果。
Auto-Extraction of Road Intersection from High Resolution Remote Sensing Image
[J].
DOI:10.6046/gtzyyg.2016.01.10
URL
[本文引用: 1]
道路交叉口是道路网络(简称路网)的重要组成元素,获取道路交叉口对提取路网信息、影像匹配和车辆导航等有重要作用。然而,基于遥感图像对道路交叉口自动提取的研究尚不多。针对高分辨率遥感图像中道路交叉口的特点,提出一种自动识别道路交叉口的方法。在图像预处理的基础上,首先对图像进行多尺度圆形均匀区检测,使用梯度变换和形态学变换提取可能存在道路交叉口的候选区;然后对候选区进行特征提取和进一步筛选,得到候选道路交叉口的位置中心;最后提取位置中心的角度纹理信息,通过波谷检测判断其连接属性,识别出道路交叉口。结果表明,该方法能有效提取出城市地区的道路交叉口,对于较复杂地区的道路交叉口提取也有一定的效果。
高分辨率SAR影像道路交叉口自动提取方法
[J].
A New Method for Automatic Extraction Road Junctions from High Resolution SAR Images
[J].
像元结构指数的平面道路交叉口提取方法
[J].
Plane Road Intersection Extraction Method Based on Pixel Structure Index
[J].
A Novel Approach for Generating Routable Road Maps from Vehicle GPS Traces
[J].DOI:10.1080/13658816.2014.944527 URL [本文引用: 1]
On Vehicle Tracking Data-Based Road Network Generation
[C]//
Generating Enhanced Intersection Maps for Lane Level Vehicle Positioning Based Applications
[J].DOI:10.1016/j.sbspro.2013.08.268 URL [本文引用: 1]
Complex Road Intersection Modelling Based on Low-Frequency GPS Track Data
[J].
利用轨迹大数据进行城市道路交叉口识别及结构提取
[J].
Urban Intersection Recognition and Construction Based on Big Trace Data
[J].
Detecting Road Intersections from GPS Traces Using Longest Common Subsequence Algorithm
[J].
SeTra: A Smart Framework for GPS Trajectories’ Segmentation
[C]//
Spatial Indexing for Data Searching in Mobile Sensing Environments
[J].
DOI:10.3390/s17061427
URL
PMID:28629156
[本文引用: 1]
Data searching and retrieval is one of the fundamental functionalities in many Web of Things applications, which need to collect, process and analyze huge amounts of sensor stream data. The problem in fact has been well studied for data generated by sensors that are installed at fixed locations; however, challenges emerge along with the popularity of opportunistic sensing applications in which mobile sensors keep reporting observation and measurement data at variable intervals and changing geographical locations. To address these challenges, we develop the Geohash-Grid Tree, a spatial indexing technique specially designed for searching data integrated from heterogeneous sources in a mobile sensing environment. Results of the experiments on a real-world dataset collected from the SmartSantander smart city testbed show that the index structure allows efficient search based on spatial distance, range and time windows in a large time series database.
Mining Interesting Locations and Travel Sequences from GPS Trajectories
[C]//
GeoLife: A Collaborative Social Networking Service Among User, Location and Trajectory
[J].
