随着计算机软、硬件及视觉技术的快速发展, 利用交通视频监控系统提升道路安全水平已成为可能, 而基于车辆运动轨迹的行为分析和识别无疑将成为其中一个最有前景的努力方向, 目前也越来越多地引起国内、外研究人员的关注^[1]。高速公路出入口是事故多发区, 如何改善其安全性一直是高速公路运营管理所面临的一个重要研究课题。通过对高速公路出入口车辆运动轨迹进行分析, 不仅可以有效判别频繁变更车道、逆行、超速等违规驾驶行为, 而且能够对车辆的运动趋势作出预测并实时评估其安全状态, 进而在危险发生前及时预警以避免事故发生。车辆轨迹聚类是运动行为分析和识别的基础, 良好的轨迹聚类结果不仅可以为识别模型构建提供样本支持, 而且直接影响轨迹分析预测的准确性和可靠性^[2]。

轨迹作为时变数据序列, 具有动态、不等长、高信息量等特点。轨迹聚类分析旨在利用非监督的学习方式来发掘大量序列数据中所隐藏的潜在模式。目前, 轨迹聚类算法主要有:K均值聚类^[3]、层次聚类^[4]、基于神经网络(Neural network, NN)聚类^{[5, 6]}和基于HMM(Hidden Markov model)聚类^{[7, 8]}等。其中, K均值聚类法计算简单, 但聚类结果一般且容易陷入局部最优解; 层次聚类算法虽也较为简单, 但传统的层次聚类算法对不完整轨迹聚类时适应性较差, 需要对其进行改进; 基于NN和HMM算法聚类效果相对较好, 但计算复杂, 难以满足实时性要求, 且HMM的状态个数如何确定仍是一个有待研究的问题。

针对现有轨迹聚类算法中所存在的问题, 提出了一种基于改进Hausdorff距离的运动轨迹分层聚类算法。首先, 采用改进Hausdorff距离衡量轨迹之间的相似性。继而, 根据轨迹时空特征的不同, 利用改进模糊C均值算法实现对有效轨迹的分层聚类。真实场景下的试验结果表明, 本文算法对于高速公路出入口区域车辆运动轨迹聚类具有较好的适用性和准确性。

轨迹编码的目的是指根据聚类算法的需要, 建立简洁、紧致的轨迹表达并最终获得开展聚类分析所需的数据样本库。本文采用类似文献^[9]的轨迹编码方法:给定一图像序列, 通过对目标进行跟踪可以获得由车辆不同时刻的特征点连接而成的轨迹序列, 在此基础上重新对原始轨迹进行等时间重采样, 采样间隔为Δ t。对于车辆O, 设t次采样时, 质心位置的二维坐标为(x_t, y_t), n次采样后可以得到一个由n个坐标点连接而成的时序数据序列 Tn:

Tn=(x1, y1), …, (xt, yt), …, (xn-1, yn-1), (xn, yn)1

若第t+1帧坐标为(x_t+1, y_t+1), 则车辆O在t时刻的速度向量可表示为:

V=δxt, δyt2

式中: δxt=xt+1-xt; δyt=yt+1-yt。

结合本文研究目的, 这里采用一个流矢量序列取代上述的位置点序列来描述车辆的运动轨迹, 其中流矢量 ft是一个四元组, 由车辆的位置和速度元素共同组成:

ft=xt, yt, δxt, δyt3

值得注意的是, 虽然通过轨迹分析也可以获得车辆的加速度, 但考虑到加速度噪音较大和聚类算法的效率, 这里暂不作考虑。最终, 车辆轨迹可表示为由 n个流矢量组成的集合:

Fn=f1, f2, …, ft, …, fn-1, fn4

通过对高速公路出入口区域内车辆进行跟踪, 可以采集到大量的车辆运动轨迹, 经有效性判断预处理后, 最终可获得有效轨迹样本集 S={F1, F2, …, Fl, …, FM}, 其中M为轨迹样本的总数目。

为了进行轨迹间对比, 产生有意义的聚类结果, 在聚类之前必须确定采用哪种合适的距离指标度量样本间的相似性。轨迹相似性指标主要用于衡量两条轨迹的相似程度, 是轨迹聚类的前提条件。目前常用的轨迹相似性度量指标包括:欧氏距离(Euclidean)、豪斯多夫距离(Hausdorff)、最长公共序列(Longest common subsequence, LCSS)和DTW(Dynamic time warping)等^[10]。其中, 欧氏距离要求轨迹样本等长, 受噪声影响严重且对时序变化敏感; LCSS和DTW虽然能够对轨迹相似性进行有效度量, 但均更适用于度量柔性物体的形状变化轨迹^[11]。尽管Hausdorff距离不能考虑轨迹的方向, 但考虑到本文研究对象为高速公路出入口结构化场景中长短不一、方向一致的车辆轨迹, 在综合分析上述各指标优缺点的基础上, 这里提出并采用改进Hausdorff距离指标衡量轨迹之间的相似性。

Hausdorff距离是描述一对点集之间相似程度的一种度量指标, 它可以用于对组成轨迹的两个点集之间的距离进行定义^{[12, 13]}。但当两条轨迹间的长度存在较大差异时, 传统Hausdorff距离会因轨迹长度影响而增大, 并不能客观反映轨迹间真实的相似程度。因此, 给定样本集中第i条和第j条轨迹F_i 、F_j, 本文提出并对称定义了如下改进Hausdorff距离 DH(Fi, Fj):

DHFi, Fj=minDHFi, Fj, DHFj, Fi5

式中：

DHFi, Fj=maxfi, kminfj, ldEfi, k, fj, l, ∀k, l

DHFj, Fi=maxfj, lminfi, kdEfj, l, fi, k, ∀l, k

式中: dE(fi, k, fj, l)为轨迹F_i 、F_j 中第k和l个多维特征向量 fi, k、fj, l之间的Euclidean距离。

轨迹聚类的目的是根据研究特征, 将相似的轨迹样本划分为一类。与普通C均值算法相比, 模糊C均值算法由于采用模糊理论来指导聚类, 所以其设计思路更加符合客观实际, 尤其适用于各聚类存在交叉区域的情况, 实际应用中往往可以以较少的工作量和较好的学习效果完成任务^[5]。然而, 与前两者相比, 改进模糊C均值算法却拥有更好的鲁棒性和适用性, 其不但能够较好地处理存在野值的情况, 而且因为放松的隶属度条件, 使得最终的聚类结果对预先确定的聚类数目并不敏感。鉴于实际获得的轨迹样本复杂多样, 数据重叠严重, 并且存在个别异常轨迹, 因此, 为提高聚类的效率和精度, 本文依据轨迹时空特征的不同建立基于改进模糊C均值的分层聚类算法, 即首先根据轨迹的空间几何位置进行路径聚类, 在此基础上, 再根据车辆的速度信息对已有路径聚类成果进一步聚类。

为了验证本文所提出的轨迹聚类算法的有效性和适用性, 选取真实的高速公路出入口交通场景作为研究对象, 出入口类型均为平行式, 主线为双车道。通过处理长度均为30 min的2个视频片段, 每帧大小为520× 480, 帧率为25 帧· s^-1, 测试期间出口共有352辆车通过, 入口共有447辆车通过, 利用基于区域跟踪算法采集轨迹并建立样本集, 轨迹由目标不同时刻的质心点连接而成^[14]。通过对轨迹进行人工判断预处理, 剔除短小或明显错误样本后, 最终共分别获得405条和529条有效轨迹, 如图1所示。上述轨迹总数略多于车辆数是由于跟踪算法因为对遮挡或其他情况无法处理而导致轨迹发生断裂, 但经有效性判断这些轨迹仍为有效样本的情况。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 出口和入口样本轨迹Fig.1 Trajectories from the exit scene and entrance scene

利用分层聚类算法对所获得的出入口样本轨迹分别进行聚类, 迭代控制参数ε =0.01。在获得模糊聚类结果后, 为验证聚类的效果, 与其他算法进行比较, 需要先对其去模糊明确化处理, 设定判断阈值T_R=0.01。当计算轨迹样本的最大隶属度R_jl< T_R时, 则认为聚类失败; 否则聚类成功, 并以此对聚类成功率进行计算。表1为本文算法以及其他两种典型算法的聚类结果对比。从表1中可以发现:3种算法不仅聚类个数有所不同, 而且聚类成功率也存在明显差异。其中, 层次聚类法^[4]由于只考虑了轨迹在空间位置和运动方向上的相似性, 并未对轨迹中所包含的速度特征进行考虑, 因此对轨迹的分辨能力稍弱, 聚类总数最少, 并且将相当比例车速差别较大的轨迹错误地归为一类, 进而影响了聚类的成功率。K均值法^[15]虽然在进行轨迹相似性度量时, 综合考虑了轨迹的空间位置、速度大小和方向等特征, 但为实现聚类一次完成, 只能利用上述特征构建了综合距离指标, 因此聚类的效果虽较前者有所提高, 但并不十分令人满意。本文算法由于在聚类时既充分考虑了上述特征的相似性, 又利用改进模糊C均值算法分步进行, 因此进一步有效提升了算法对运动目标轨迹的区分能力, 故采用本文算法的轨迹聚类个数在3种算法中为最多, 同时, 聚类成功率也较前两者有了明显提高。由此可见, 对于长短不一、方向相同的高速公路出入口车辆轨迹, 本文算法在具有较强适应性同时, 还能够获得令人满意的聚类成功率。

表1

Table 1

表1(Table 1)

表1 轨迹聚类结果 Table 1 Trajectory clustering results 算法 交通 场景 轨迹 总数/条 类数 /个 成功聚 类数/条 失败聚 类数/条 聚类成 功率/% 层次聚 类法[4] 出口 405 19 372 33 91.82 入口 529 24 489 40 92.44 K均值 法[15] 出口 405 25 381 24 94.07 入口 529 31 505 40 95.46 本文 算法 出口 405 30 394 11 97.28 入口 529 35 512 17 96.79

表1 轨迹聚类结果 Table 1 Trajectory clustering results

出入口轨迹聚类结果分别如图2所示, 不同的聚类中心分别以均值多段线表示。从图2可以看出:轨迹聚类结果不仅较为规律, 与高速公路出入口处车辆的实际运动行为模式相一致, 而且在存在明显异常轨迹干扰的情况下, 部分重叠严重或空间特征相近的轨迹均能够得以正确划分, 因此, 本文算法对于高速公路出入口车辆运动轨迹具有较好的分辨可靠性, 而且聚类结果物理意义明确, 能够客观地反映车辆在出入口区域所对应样本轨迹的时空分布情况。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 出口和入口聚类结果Fig.2 Clustered result in exit scene and entrance scene

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 出口和入口聚类失败轨迹Fig.3 Failure samples for clustering of trajectories in exit and entrance

出入口聚类失败轨迹分别如图3所示, 图中红色实线为空间聚类失败的轨迹样本, 黄绿色虚线为时间聚类失败的轨迹样本。

对上述失败聚类轨迹进行深入分析可知, 红色实线一部分为车辆随机驾驶行为轨迹, 如车辆随意变道或连续变道超车等, 其他部分则为车辆异常轨迹, 如车辆为避免与前车发生碰撞或发生故障而不得以占用右侧硬路肩行驶、清洁人员的横穿轨迹等。黄绿色虚线除一条逆行轨迹是由于Hausdorff距离指标缺陷导致分类错误外, 其余则多是由于车辆超速或速度过低行驶而导致聚类失败。总之, 上述两者均为与出入口固定运动行为模式无关的车辆轨迹, 不同的是, 只有极小一部分轨迹属于合法驾驶行为, 但由于其自身的随意性, 导致基于统计的算法对该类行为无法彻底分析, 还需从驾驶行为模型角度深入进行研究, 而其他更多的则为违法或违规驾驶行为, 需要引起足够重视, 而这也正是道路日常管理所应该关注的重点, 可见, 本文算法能够为其提供可靠支持。通过以上分析可知, 轨迹聚类失败的主要原因在于轨迹样本的特殊性而非聚类算法本身, 因此进一步验证了本文算法的有效性。

结合高速公路出入口处轨迹的时空特征, 提出了一种合理的车辆运动轨迹分层聚类算法。首先提出并利用改进Hausdorff距离来衡量轨迹之间的相似性, 该指标能够适于出入口处长短不一、方向一致的轨迹样本; 其次, 基于改进模糊C均值算法建立了轨迹层次聚类算法, 即首先根据轨迹的位置几何形状信息进行路径聚类, 在此基础上, 再根据车辆的速度信息对已有路径聚类成果进行进一步聚类。通过对采集到的真实轨迹样本进行试验, 结果表明了本文算法对于场景固定运动行为模式不仅具有较高的聚类成功率, 而且聚类结果准确、可靠。更为重要的是, 采用本文算法所产生的聚类结果为轨迹样本在空间路径和车速层面上的分别划分, 因此最终获得的聚类结果物理意义明确, 可为进一步的车辆运动行为理解和分析提供依据。