城市交叉口的空间位置、范围及详细的转向信息是构成城市各级交通路网数据的关键^[1]。对于道路中心线级别的城市路网数据模型，交叉口一般被抽象表达为多条道路交汇的交点^[2]；对于车行道级别的城市路网数据模型，交叉口的空间描述由于路网细节的增加被表达为分/合流点^[3]；对于城市车道级路网数据模型，交叉口的空间结构则需要更加详细的描述，包括其空间范围、转向特征、拓扑连接等^[4-6]。目前大部分研究主要聚焦于从各类传感器数据中自动识别交叉口，包括：基于图像、多传感器组合以及GPS轨迹数据的交叉口识别，且交叉口空间结构识别根据空间结构详细程度主要有道路中心线级别和车行道级别两种。

基于图像的交叉口识别一般从影像数据中自动识别交叉口的空间位置，并将其简化表达为点，然后用于城市道路中心线级别的路网数据生成^[7-9]。由于图像数据受天气、光照、行人、车辆等因素影响，会造成交叉口细节识别困难。基于多传感器组合的城市交叉口识别利用多种传感器包括：激光测距仪、GPS定位装置、CCD相机等，采用基于视觉的方法实现车辆所在道路交叉口细节的探测^[10-12]，为智能辅助驾驶系统及无人驾驶提供数据支持。多传感组合的城市交叉口识别的服务对象为单个车辆，其识别区域往往局限在一定范围内；对于大区域的城市道路交叉口探测，则会存在信息获取成本高、周期长等缺点。另外，多传感器组合的数据往往会受到行人和车辆的干扰，信息提取难度高。基于GPS轨迹数据提取道路交叉口细节信息，实现城市道路中心线级别-车行道级别-车道级别的路网生成和更新是目前研究的热点^[13-16]。相比于遥感影像数据和多传感器组合获取的数据，GPS轨迹数据包含丰富的交通动/静态信息、获取成本低、周期短，因此更适用于大范围城市交通路网信息的获取和快速更新^[17-20]。文献[21]采用图形描述器方法从专业采集车和辅助大众运输车辆采集的高精度时空轨迹数据中识别道路交叉口，实现城市道路中心线级别路网数据生成。文献[22]提出利用测量车获取的高精度轨迹数据构建城市交叉口细节结构，完成城市交通路网生成。文献[23]基于高采样率的时空轨迹数据，采用力学模型融合时空轨迹，然后利用局部G统计的方法识别交叉口与非交叉口，实现城市车行道级别路网生成。然而，基于图形描述器方法^[21]识别交叉口需要训练大量数据构建经验模型，算法复杂且效率较低；文献[22]仅描述了一种高精度交叉口结构模型，且该模型的应用前提是交叉口位置已知，并未展开实现如何从轨迹数据中提取交叉口细节结构；利用轨迹融合算法以及局部G统计方法^[23]识别交叉口适用于高频采样数据，然而考虑到存储成本大部分轨迹数据的采样频率较低，因此该方法适应性不强。

本文基于现有研究提出了一种利用GPS轨迹大数据的城市交叉口识别及细节结构提取方法。该方法根据交叉口细节结构随道路结构详细程度的变化，分为交叉口与非交叉口识别(道路中心线级路网)、交叉口分/合流点提取(车行道级路网)以及交叉口车道级(车道级路网)结构获取3个层次。首先，根据轨迹跟踪获取车辆转向点对，利用基于距离和角度的生长聚类方法对其完成空间聚类，然后采用基于局部点连通性的聚类方法实现交叉口与非交叉口识别；最后基于交叉口范围圆及转向点对类簇，提取包含分/合流点的车行道级别交叉口结构和包含转向信息的车道级别交叉口空间结构。试验以武汉市上万辆出租车采集的轨迹大数据为例，实现了武汉市城区交叉口识别，准确率为96.1%，召回率为93.1%；并以武汉市关山大道与高新大道相交的十字交叉口作为具体案例，进行了不同尺度路网模型下交叉口结构的构建。最后，本文分析了识别错误的交叉口，并与已有研究进行了评价和对比。

1 基于轨迹大数据的交叉口识别

基于轨迹大数据的交叉口与非交叉口识别是提取道路级别-车行道级别-车道级别交叉口结构信息的前提。车辆在通过交叉口与非交叉口时的行驶特征主要存在两类差异：一是记录车辆行驶方向的航向角度变化不同；二是车辆发生转向的转向类型数量不同。基于这两种差异，本文通过轨迹跟踪提取车辆的转向点对，然后利用相似度聚类方法对不同转向类型的转向点对进行聚类，最后通过分析不同区域车辆转向点对的聚类类簇数量，实现交叉口与非交叉口的初次识别。

1.1 基于轨迹跟踪的转向点对提取及聚类

低精度时空轨迹数据定位精度在10~15 m左右，采样频率为10~60 s，如城市出租车系统采集的浮动车数据。对于低采样率的时空轨迹数据，车辆在完成一次转向过程中，其GPS轨迹通常在交叉口或弯道区域可以保留2~4个轨迹点。为了提取低精度时空轨迹的转向特征，本文提出转向点对的概念。转向点对是指车辆在完成一次转向过程中留下的前后两个轨迹点，也即这两个相邻的轨迹点航向角度变化量符合车辆转向特征(图 1)。

如图 1所示，某一车辆完成一次转弯过程中留下至少两个轨迹点P₁和P₂，轨迹点P₁的航向角为α₁，相邻的下一个轨迹点P₂的航向角为α₂，两个轨迹点航向角度变化值为Δα。给定转向角阈值α，以及完成一次转向过程所需的最大时间阈值t，若Δα大于给定的阈值α，且轨迹点P₁和P₂的时间间隔小于给定的阈值t，则认为轨迹点P₁和P₂是一个转向点对。在试验部分，本文结合目前城市交叉口转弯设置最小角度(60°)，并考虑低精度轨迹数据航向角度误差(5°~10°)，将转向角阈值α设为45°，完成一次转向过程所需的最大时间间隔t设为20 s(根据目前研究表明^[24]，车辆通过交叉口的时长一般为8~20 s)。

对于任意的两个转向点对，其空间相似性主要体现在角度差异和距离差异两个方面。利用角度差异可以将不同转向类型的转向点对进行剥离，而利用距离差异则可以将属于不同交叉口的转向点对进行剥离。如图 2所示，用向量P和向量Q分别表示转向点对p_i(x_pi，y_pi)、p_j(x_pj，y_pj)和q_i(x_qi，y_qi)、q_j(x_qj，y_qj), 即P=p_ip_j，Q=q_iq_j。向量P和向量Q之间的距离差异定义为点对起点间距离d_i和终点间距离d_j的平均值；角度差异定义为向量P和向量Q之间的夹角Δθ。基于现有研究基础^[25]，本文提出了一种针对转向点对距离和角度差异的相似度评价模型

式中，diff_d表示转向点对之间的距离，其计算方法如公式(2) 所示

式中，按照时间顺序分别计算前后两个时刻转向点对两点的欧氏距离d_i、d_j，Dis为常量，其大小取决于城市道路路面宽度。根据中国城市道路建设标准，本文将其设置为50 m。

diff_Δθ表示转向点对之间的角度差异。Δθ表示转向点对构成的向量之间的夹角，对其标准化处理后得到diff_Δθ，计算公式如下

基于任意两个转向点对之间的空间相似度进行生长聚类，具体方法如下所示：

1.2 基于局部点连通性的交叉口识别

通常情况下，车辆在行驶过程可能存在少数非法掉头或随机转弯等情况，这些情况下的转向点对之间的相似性较低，聚类得到的类簇包含的点对数量也相对较少。统计转向点对聚类结果中每个类簇包含的点对数量，所有转向点对类簇包含的点对数量近似服从泊松分布，设置置信度为0.95的置信区间，将点对数量小于置信区间下限的聚类类簇视为异常驾驶去除，保留大于置信区间下限的聚类结果用于交叉口和非交叉口的识别。

一般情况下，属于同一个交叉口的转向点对类簇，其类簇中心点会聚集在交叉口区域内。另外，由于城市路网的密集性和复杂性，属于同一交叉口但距离最远的两个转向点对类簇中心点，其距离可能会超过某两个相邻交叉口的距离。因此，为了自适应不同空间尺度识别属于同一交叉口的转向点对类簇中心点，本文提出基于局部点连通性的聚类方法识别交叉口。该方法的实质是为了将所有转向点对类簇按照交叉口进行分类，也即找出属于同一个交叉口范围内的所有转向点对类簇，并利用非交叉口处(如弯道，只包含一种左转和一种右转)转向类型数量小于或等于2的特征，实现交叉口与非交叉口的初次识别。其原理如下：

2 交叉口结构信息提取

交叉口在道路中心线级别路网模型中表达为空间节点，在车行道级别路网模型中表达为由出/入口点构成的车行道交叉口结构，在车道级别路网模型中则表达为由各个车道拓扑关系构成的详细空间结构。基于交叉口与非交叉口的识别结果，本节主要介绍如何进行道路中心线级别-车行道级别-车道级别的交叉口结构信息提取。

2.1 交叉口空间位置提取(道路中心线级路网)

城市道路中心线级别路网模型将交叉口抽象表达为点，也即记录路网数据拓扑信息的拓扑点。本文根据交叉口与非交叉口识别结果，分析处于同一个交叉口区域内的转向点对类簇，自适应提取交叉口的中心位置及范围。具体方法如下所示：

(1) 对于每一个交叉口，计算属于该交叉口的所有转向点对的中心作为交叉口范围圆的圆心O；

(2) 计算每一个转向点对的类簇中心到圆心O的距离；

(3) 按照交叉口范围取大不取小的规则，选取距离最大值作为交叉口范围圆的半径R(图 4)。图 4中，不同颜色的点表示该区域内不同转向类型的转向点对类簇聚类结果，红色的点表示属于该交叉口的转向点对类簇的中心点，点O是该交叉口的中心，点P是交叉口区域内距点O最远的一个转向点对类簇中心点，图中的圆即表示交叉口范围。交叉口范围圆的中心点则可以作为道路中心线级别路网的空间节点。

2.2 分/合流点提取(车行道级路网)

车行道级别路网比道路中心线级别路网的详细度更高，主要体现在对同一条道路不同行驶方向的两条车行道进行了表达。在车行道级别路网模型中，交叉口结构主要由车辆驶入交叉口区域和驶出交叉口区域的分/合流点构成。上文提取的每个转向点对的前一个点可以作为交叉口入口点，后一个点可以作为一个交叉口出口点，这些入/出口点分别集中在交叉口相应的分/合流点处。获取交叉口处分/合流点方法如下：

(1) 将每一个转向点对拆分为入口点和出口点，以入口点为例，从所有入口点中随机选取未分类的一个入口点作为种子点，遍历所有入口点，如果该点与种子点航向角差值小于Φ(考虑到城市交叉口建设标准，最小转向角度为60°，本文后续试验中选取60°作为阈值)则聚为一类，否则从未被分类的入口点中选取下一个种子点，重复该过程，直至每个入口点都归属到对应的类别；

(2) 对所有出口点进行同样的操作，最终得到多个入口点类簇和出口点类簇，如图 5所示，红色点表示入口点类簇，蓝色点表示出口点类簇；

(3) 计算每个类簇的中心点和平均航向角，分别以中心点C₁和C₂为端点(图 5)，沿其平均航向角及相反方向作延长线，延长线与交叉口范围圆较近的一个交点S和I即为所求的交叉口分/合流点。

2.3 车道级别交叉口结构提取(车道级路网)

在车道级别的路网模型中，不能简单地把交叉口抽象为点或者出/入口点，需要明确交叉口处每条车道之间的拓扑信息，即提取交叉口区域内的所有转向信息。利用上文提取的交叉口范围圆及不同转向类型的转向点对类簇可以容易地获取交叉口的详细空间结构特征，方法如下：

(1) 利用交叉口范围圆检测直行点对类簇；

(2) 将直行点对类簇、左转转向点对类簇和右转转向点对类簇均拆分为入口点类簇和出口点类簇，并计算每个类簇的中心点和平均航向角，如图 6所示，图中不同颜色的点表示同一车行道的车辆在经过交叉口时的发生不同转向的轨迹点，圆形点表示入口点，三角形点表示出口点；

(3) 如图 6(a)，以通过该交叉口的一个左转入口点类簇为例，计算该类簇中心点C，并以点C为端点，沿其平均航向角及相反方向作延长线，延长线与交叉口范围圆较近的一个交点T即为该交叉口的一个拓扑点，使用同样方法即可得到该交叉口的其他拓扑点，如图 6(b)所示。

图 6(b)中，S、L和R分别表示直行、左转和右转，圆形点表示入口点，三角形点表示出口点。这些反映交叉口不同转向信息的拓扑点是构成车道级交叉口结构的根基，其相互的连通关系则进一步丰富了车道级交叉口结构。

3 试验分析

本文选择2013年8月1日到2013年8月7日武汉市城区一周的出租车轨迹数据为数据源进行试验，轨迹点采集间隔为10~60 s，定位精度为10~15 m，出租车数量为4799辆，共包含1 004 442个轨迹点。每条数据记录了采集时间、经度、纬度、速度和航向角等信息。由于现代建筑群比较集中，并且髙层居多，浮动车在城市道路行驶过程中会受到遮挡，GPS信号会出现失真、漂移，导致获取的轨迹点并不能代表车辆实际行驶的位置，GPS轨迹点分布在道路面上的密度要明显高于道路面以外，其中位于道路中心线处的密度值最高且密度值依次向两边衰减。此外，在出租车实际运营中，出租车通常不会选择道路等级较低的支路作为行驶道路，轨迹在支路的覆盖度较低。根据车辆轨迹数据的分布特点，本文采用Delaunay三角网方法^[26]进行数据预处理，原始数据如图 7(a)，预处理后的轨迹如图 7(b)。

3.1 交叉口识别参数讨论

在交叉口识别过程中，需要确定相似度评价模型的权重值，同时也需要选取合适的相似度阈值。本文通过多次调整试验参数，对试验结果进行了讨论，从而为选取试验参数提供参考。首先，在转向点对的相似度评价模型中，不同转向点对之间的距离和角度差异对相似度评价的影响同等重要，令权重ω₁=ω₂=0.5，此时本文算法的聚类效果比较理想。在对转向点对进行相似度聚类时，相似度阈值sim_{(P, Q)}的取值主要取决于转向点对之间的距离和角度差异。令转向点对之间的距离差异和角度差异分别取不同的值，代入公式(1)-(3) 计算相似度阈值sim_{(P, Q)}，基于该阈值对试验区内的转向点对进行相似度聚类，并统计聚类结果中位于交叉口且转向识别正确的转向点对类簇的数量，然后将该值与交叉口转向类别识别总数量的比值作为交叉口转向识别准确率。根据图 8中的试验结果可以看出，当角度差异值为44°，距离差异值为25 m，识别的准确率较高，将其代入公式(1)-(3)，计算得到此时的相似度阈值sim_{(P, Q)}≈0.765。

在进行局部点连通性聚类时, 邻域半径r的设置对交叉口最终的识别有很大影响。道路宽度、交叉口类型和范围以及GPS轨迹数据的精度都会影响r值的确定，本文通过重复试验不断调整试验参数，并利用准确率(Precision)和召回率(Recall)来综合评估邻域半径r对交叉口识别效果的影响，试验结果如表 1所示。根据表中结果，最终将邻域半径r设置为33 m，此时识别正确率最高。准确率和召回率的计算公式如下所示

式中，True_positive和False_positive分别表示正确识别的交叉口数量和错误识别的交叉口数量，False_negative表示漏检的交叉口数量。

3.2 交叉口识别及结构提取

本文选取的试验区域内共包含189个交叉口，采用本文所提方法对该区域内交叉口进行了识别，图 9(a)为试验区域内交叉口识别结果，黄色点表示基于本文方法识别出的交叉口，红色星号表示目视解译识别出的交叉口。

以武汉市关山大道与高新大道相交的十字交叉口作为具体案例，对该交叉口进行了不同尺度路网模型下结构的构建，图 9(b)为道路中心线级别交叉口识别结果，图 9(c)为车行道级别交叉口结构构建结果(S表示分流点，I表示合流点)，图 9(d)为车道级别交叉口结构构建结果(S、L和R分别表示直行、左转和右转)。

3.3 交叉口识别错误分析

交叉口识别错误的结果主要有两种类型，分别是漏检和错判。漏检的交叉口主要发生在有效轨迹数据稀疏的地方，如图 10(a)所示，由于获取的浮动车轨迹数据量有限，在部分支路保留的GPS轨迹数据较少，不能提取出足够数量的转向点对，导致漏检。随着无线传感器与定位技术的发展与普及，产生海量的出租车轨迹数据、个人出行轨迹等VGI轨迹数据，使得GPS轨迹数据可以完全覆盖于城市的每一条道路每一个车道，高覆盖率会不断弱化城市交叉口漏检。错判的交叉口主要包括以下几种原因：① 大型复杂立体交叉口类型比较多样，转向信息也更加复杂，而且车辆GPS轨迹数据中没有高度信息，无法区分行驶在不同高度的车辆轨迹数据，导致不能准确识别这种类型的交叉口，如图 10(b)；② 距离较近的两个相邻交叉口易被识别为一个交叉口，本文虽然采用了局部点连通性的聚类方法，能够自适应识别不同大小的交叉口，但仍存在某些相邻交叉口距离较近，其距离甚至小于某些大型交叉口连接的相邻道路之间的距离，如图 10(c)，这种类型的交叉口数量较少，并且识别结果仍然可以保持其原有的拓扑关系；③ 某些大型停车场或者小区出入口处与交叉口具有相似的特征，易被错判，对于这种情况需要结合遥感影像进行人工检查，如图 10(d)所示。

3.4 交叉口识别方法评价

交叉口识别结果是提取城市各级路网交叉口结构的关键。本文利用图形描述器方法^[21]和轨迹融合方法^[23]的试验结果进行统计对比，3种方法的统计结果如表 2所示。图形描述器方法需要训练大量的样本来提取交叉口先验知识，然而交叉口类型多样，很难选取足够类型交叉口样本，导致交叉口识别率较低。轨迹融合方法中的力学模型对直行道路的融合效果较好，但在交叉口和弯道附近，融合效果不理想，导致交叉口识别效果较差。本文利用转向点对集中分布在交叉口的特征来识别交叉口位置，转向点对能够体现一条轨迹在完成转向过程中的转向典型特征，也可以很好地刻画一条轨迹在通过某一交叉口区域的进出情况。此外，对于大规模轨迹数据来说，分析所有轨迹点需要很大的计算开销，而利用转向点对来对原始轨迹进行化简，既可以保留交叉口处车辆的行为特征，又能节省计算开销。采用本方法共探测到183个交叉口，其中准确识别的交叉口为176个，准确率为96.1%，召回率为93.1%。

4 结论

本文针对低精度时空轨迹数据的特点，提出了一种城市交叉口自动识别和结构提取方法。该方法可以准确地从轨迹大数据中识别出城市交叉口及其结构。试验以武汉市上万辆出租车采集的轨迹大数据为例，实现了武汉市城区试验区域内交叉口的自动识别以及道路中心线级别-车行道级别-车道级别的交叉口结构信息的探测，其中交叉口识别准确率为96.1%，召回率为93.1%。利用本文所提方法可以缩短交叉口信息获取的周期，降低信息提取成本，为城市各级别交通路网的快速生成、更新提供支持。然而，由于本文试验数据源单一，导致城市若干路段数据覆盖率低，造成一些道路交叉口被漏检；同时，对于大型复杂立体交叉口，还不能实现交叉口细节结构的准确提取。未来会继续深入研究如何实现复杂立体交叉口的识别和细节结构提取，以及进一步完成基于各级路网交叉口结构实现全局路网的生成。