2017, Vol. 45
随着计算机软、硬件及视觉技术的快速发展，交通视频监控系统已越来越多地被用于日常公路运营安全管理工作.在交通监控系统的智能化研究中，基于车辆运动轨迹的行为识别与分析无疑是其中一个最有前景的努力方向，并且已广泛引起了国内外研究人员的关注[1-2].车辆运动轨迹是指车辆在通过交通视频监控场景时，在连续不同帧时刻所形成的特征点序列.轨迹作为时变数据序列，具有动态、不等长、高复杂度等特点.路径模型是指在车辆通过结构化交通场景时，由形成运动轨迹所蕴含的潜在常用运动路线模式.轨迹路径建模旨在利用非监督的学习方式来发掘大量轨迹数据中所隐藏的客观运动路径.车辆轨迹建模是运动行为分析与识别的基础，通过对固定监控场景内的车辆运动轨迹建模分析，不仅可以对连续变道、急转、逆行等违规驾驶行为进行可靠检测，而且能够对车辆的运动趋势作出客观预测并实时评估其安全状态，进而在危险发生前及时预警以避免事故发生.
目前，许多研究人员针对运动目标轨迹采集方法已经开展了广泛研究，但是对于如何进行轨迹建模分析的研究成果相对较少.Makris和Ellis[3]通过对轨迹自适应学习，提出了一种由中轴线和2条极值边界线表征的轨迹样本集几何模型.Hu等[4]在轨迹预处理的基础上建立了行为模式的统计模型.袁和金等[5]通过最小信息准则(AIC)和贝叶斯信息准则(BIC)优化准则，提出了一种基于隐马尔科夫模型(HMM)聚类的轨迹分布模式提取和异常行为检测算法.张宁等[6]使用OGS-DTW算法对轨迹数据进行预处理求解距离函数，实现了交通事件检测.汤春明等[7]提出了一种基于批处理(batch-mode)模型初始化的增量式轨迹建模并将其应用于在线异常检测.范菁等[8]借助轨迹曲率特征分析，利用二次谱聚类和HMM-RF混合模型建立了车辆行为识别方法.尽管上述研究部分实现了行为识别与分析的目的，但大多在结构设计上存在缺陷，或者需要对轨迹进行预处理进而造成信息失真，因此导致最终建立起的模型精度均一般，灵活性和适应性欠佳.
轨迹聚类是指按照“物以类聚”的思想，对未知类别的轨迹，根据轨迹样本之间的相似程度进行分类，将相似程度大的样本归为一类、不相似的归为其他类别的工作.车辆轨迹聚类是后续运动分析识别的基础，良好的轨迹聚类结果不仅可以为路径模型构建提供样本支持，而且直接影响轨迹分析的准确性和可靠性[9].鉴于此，针对轨迹建模过程中的主要缺陷，提出一种基于“先聚类后建模”的车辆运动轨迹路径模型构建方法，即首先借助改进Hausdorff距离指标建立改进模糊C均值聚类算法，用于实现对轨迹的聚类，然后，针对各轨迹子类的几何分布特点，建立各轨迹类的路径模型.
1 基于改进模糊C均值的轨迹聚类 1.1 轨迹相似性指标为进行轨迹间对比，产生有意义的聚类结果，在聚类之前必须确定采用哪种适合的距离指标来度量样本间的相似性.轨迹相似性指标主要用于衡量2条轨迹的相似程度，是轨迹聚类的前提条件.常用的轨迹相似性度量指标主要包括：欧氏距离(Euclidean)、豪斯多夫距离(Hausdorff)、最长公共序列(LCSS，longest common subsequence)和DTW(dynamic time warping)等[10].其中，欧氏距离要求轨迹样本等长，受噪声影响严重且对时序变化敏感；LCSS和DTW虽然能够对轨迹相似性有效度量，但其均更适用于柔性物体的形状变化轨迹[11].考虑到Hausdorff距离对长短不一车辆轨迹的适应性，这里拓展采用改进Hausdorff距离指标来衡量轨迹之间的相似性.
Hausdorff距离是描述一对点集之间相似程度的一种度量，它可以用于对组成轨迹的2个点集之间的距离进行定义[12].当2条轨迹间的长度存在较大差异时，传统Hausdorff距离会受轨迹长度的影响而增大，并不能客观反映轨迹间的相似程度，因此，给定样本集中第i条和第j条轨迹Fi, Fj，轨迹相似性衡量采用如下改进Hausdorff距离[13]：
| ${D_{\rm{H}}}({F_i},{F_j}) = {\rm{min}}\;({D_{\rm{h}}}({F_i},{F_j}),{D_{\rm{h}}}({F_j},{F_i}))$ | (1) |
其中
| ${D_{\rm{h}}}({F_i},{F_j}) = \mathop {{\rm{max}}}\limits_{{f_{i,k}}} (\mathop {{\rm{min}}}\limits_{{f_{j,l}}} {d_{\rm{E}}}({\mathit{\boldsymbol{f}}_{i,k}},{\mathit{\boldsymbol{f}}_{j,l}})),\forall l,k$ | (2) |
| ${D_{\rm{h}}}({F_j},{F_i}) = \mathop {{\rm{max}}}\limits_{{f_{j,l}}} (\mathop {{\rm{min}}}\limits_{{f_{i,k}}} {d_{\rm{E}}}({\mathit{\boldsymbol{f}}_{j,l}},{\mathit{\boldsymbol{f}}_{i,k}})),\forall l,k$ | (3) |
式中：dE(fi, k, fj, l)为轨迹Fi, Fj中第k和l个多维特征向量fi, k, fj, l之间的Euclidean距离.
1.2 轨迹聚类轨迹聚类是行为分析与理解的基础，其目的是将相似的轨迹划分为一类.与普通C均值算法相比，模糊C均值算法由于采用模糊理论来指导聚类，其设计思路更加符合客观实际，尤其适用于各聚类存在交叉区域的情况，实际应用中往往可以以较少的工作量和较好的学习效果完成任务[4].然而，与前两者相比，改进模糊C均值算法却拥有更好的鲁棒性和适用性，其不但能够较好地处理存在野值的情况，而且因为放松的隶属度条件，使得最终的聚类结果对预先确定的聚类数目并不敏感.鉴于实际获得的轨迹样本复杂多样，重叠严重，存在个别异常轨迹，并且轨迹间距离计算任务繁重，因此，为提高聚类的效率与精度，本文依据轨迹的空间分布特征建立基于改进模糊C均值的空间聚类算法.
给定一图像序列，通过目标跟踪可以获得由车辆特征点组成的原始运动轨迹.轨迹聚类前首先对其进行等时间重采样，采样间隔为Δt.对于车辆O，设t次采样时，质心位置的二维坐标为(xt, yt)，n次采样后可以得到一个由n个坐标点对连接而成的时序序列Fn.
| ${F_n} = \{ ({x_1},{y_1}),({x_2},{y_2}), \ldots ,({x_t},{y_t}), \ldots ,({x_{n - 1}},{y_{n - 1}}),({x_n},{y_n})\} $ | (4) |
令特征向量ft=(xt, yt)，则
| ${F_n} = \{ {\mathit{\boldsymbol{f}}_1},{\mathit{\boldsymbol{f}}_2}, \cdots ,{\mathit{\boldsymbol{f}}_t}, \cdots ,{\mathit{\boldsymbol{f}}_{n - 1}},{\mathit{\boldsymbol{f}}_n}\} $ |
假设通过对采集到的车辆轨迹样本进行有效性判断后，最终获得的有效轨迹集合为S={F1, F2, …, Fl, …, FM}，其中M是轨迹样本的总数目.轨迹聚类的目的是将样本集S聚成K个不同的子类集合θ={θ1, θ2, …, θc, …, θK}，即
| $s = \mathop \cup \limits_{c = 1}^K {\theta _c}$ | (5) |
式中：θc表示第c个轨迹聚类；K是聚类总数目，其可事先确定，亦可以根据某种准则确定，这里根据交通场景实际情况，采用反复试验法确定.利用改进模糊C均值对轨迹聚类实现的步骤如下：
(1) 随机初始化K个轨迹聚类中心.
(2) 依次输入并计算每个样本Fl到已有K个聚类中心θc的改进Hausdorff距离，即
| ${D_{\rm{H}}}\left( {{F_l},{\theta _c}} \right) = {\rm{min}}\left( {{D_{\rm{h}}}\left( {{F_l},{\theta _c}} \right),{D_{\rm{h}}}\left( {{\theta _c},{F_l}} \right)} \right)l = 1,2, \cdots M,c = 1,2, \cdots K$ | (6) |
(3) 计算各样本到所有K个聚类中心的隶属度Rc l(t)为
| ${R_{c{\rm{ }}l}}\left( t \right) = \frac{{M/D_{\rm{H}}^2({F_l},{\theta _c})}}{{\sum\limits_{k = 1}^K {\sum\limits_{m = 1}^M {(1/D_{\rm{H}}^2({F_m},{\theta _k}))} } }}$ | (7) |
(4) 根据隶属度调节每个聚类中心向量元素.
| ${\theta _c}\left( {t + 1} \right) = \frac{{\sum\limits_{l = 1}^M {R_{c{\rm{ }}l}^2\left( t \right){F_l}} }}{{\sum\limits_{l = 1}^M {R_{c{\rm{ }}l}^2} \left( t \right)}}$ | (8) |
(5) 根据是否满足下面的聚类中心稳定条件来判断是否停止迭代以结束聚类过程.
| $\mathop {{\rm{max}}}\limits_{1 \le c \le K} \{ \left\| {{\theta _c}} \right.\left( {t + 1} \right) - {\theta _c}\left. {\left( t \right)} \right\|\} < \varepsilon $ | (9) |
式中：ε为迭代控制参数.
最终可获得基于空间分布的原始轨迹聚类结果如下：
| $\left\{ {\begin{array}{*{20}{l}} {s = \{ \left\{ {{F_{1,1}}, \cdots ,{F_{1,{M_1}}}} \right\}, \cdots ,\left\{ {{F_{c,1}}, \cdots ,{F_{c,{M_c}}}} \right\}, \cdots ,}\\ {\quad \quad \left\{ {{F_{K,1}}, \cdots ,{F_{K,{M_K}}}} \right\}\} }\\ {\sum\limits_{c = 1}^K {{M_c} = M} } \end{array}} \right.$ | (10) |
其中：Mc是第c个轨迹类的样本轨迹数目.
2 路径建模虽然前述算法实现了对车辆运动轨迹的聚类，但并未建立起各聚类的合理表达，因此为进行有效推理，本着“简洁、直观、表达能力强”的原则，还需进一步建立各轨迹聚类的路径模型.以往基于轨迹构建路径模型的几何结构如图 1所示，该类结构由于模型简单固化而导致表达能力一般，精度较差.实质上轨迹路径模型可以看作是一种离散随机过程的表达，即基于随机发生的轨迹点构造出各节点的离散分布状态，继而由各节点的有序排列连接构成轨迹总体空间分布，它集中概括了类内轨迹的几何形状和位置特征，具体在构建时应满足以下三方面要求：
|
图 1 路径模型几何结构 Fig.1 Geometric structure of path model |
(1) 能够处理同一运动轨迹类别中空间尺度上轨迹存在的轻微特征变化，即习得的模型具有一定的鲁棒性.
(2) 足够灵活反映运动状态的不确定性.
(3) 与研究场景的结构化特征紧密相关，并且可为轨迹推理分析提供空间依据.
根据上述要求，提出了一种基于离散状态的路径模型.该方法采用离散状态对连续运动近似分析，每个轨迹类的路径模型θc由1条中心线和2侧相应的包络线组成：中心线是1条由Nc个离散状态节点连接而成的多段线，代表了轨迹类相应的位置，根据类内轨迹样本的均值确定；而包络线为该聚类内各状态的有效“宽度”，代表了类内轨迹的空间分布差异，由各状态分布的标准差确定.一般情况下，离散状态数越大，宽度越窄，则模型总数目越多，精度越高，但随之计算越复杂，耗时越多.当确定运动起止兴趣点(POI，point of interest)后，贯穿两者间的路径模型结构如图 2所示.
|
图 2 轨迹离散路径模型 Fig.2 Trajectory discrete path model |
由于改进模糊C均值聚类方法最终获得的是各轨迹类的模糊划分结果，为建立空间模型，首先需要对其去模糊化处理，因此这里采用最大隶属度原则对轨迹样本进行确定性分类并据此构建各类相应的模型.对于轨迹类θc，假设Lc为该类轨迹样本长度的最大值，Δ为采样间距，则模型状态个数Nc=「Lc/Δ」，且模型中的各节点p与样本轨迹中相应的第p段内相应的Np个采样点的特征向量F相对应.假定各节点的空间分布φc, p服从高斯分布，且相互独立，则节点p分布的计算公式如下：
| ${\mathit{\boldsymbol{\mu }}_p} = \frac{1}{{{M_c}{N_p}}}\sum\limits_{n = 1}^{{M_c}} {\sum\limits_{l = 1}^{{N_p}} {{\mathit{\boldsymbol{F}}_{n,l}}} } $ | (11) |
| ${\mathit{\boldsymbol{ \boldsymbol{\varSigma} }}_p} = \frac{1}{{{M_c}{N_p}}}\sum\limits_{n = 1}^{{M_c}} {\sum\limits_{l = 1}^{{N_p}} {({\mathit{\boldsymbol{F}}_{n,l}} - {\mathit{\boldsymbol{\mu }}_p}){{({\mathit{\boldsymbol{F}}_{n,l}} - {\mathit{\boldsymbol{\mu }}_p})}^{\rm{T}}}} } $ | (12) |
式中：均值向量μp=E(F)=(x, y)；特征向量Fn, l=(xn, l, n, l)；Σp为协方差矩阵.
在计算各节点的状态分布后，将各离散状态的均值连接形成中心线，另外根据正态分布的“3σ”准则确定包络线，即可成功建立各轨迹类的路径模型.然后，设模型间分隔距离阈值为TD，计算所有模型θu与θv包络线采样点间的距离DH(θu, θv)，u, v∈(1, 2, …，K)，当DH(θu, θv)≤TD时，则将模型合并，重新计算中心及包络线，模型总数减1；重复该过程直到模型总数不再发生变化，建模过程结束.
3 异常检测当收集足够多的轨迹样本并建立起车辆轨迹的路径模型时，实际上就获得了研究场景中所有正常的车辆运动模式.借助于建立的路径模型，就可以方便地对新采集的部分或完整轨迹进行异常检测.检测时，首先需要对未知轨迹进行模型识别，识别可采用最大化准则进行，即以最大化轨迹后验概率的路径模型作为该轨迹的最有可能所属类别.假设一条轨迹T={f1, f2, …, fr, …fL}，其中L为轨迹长度，则轨迹点fr在概率分布φc, p下的条件概率为
| $P({\mathit{\boldsymbol{f}}_r}\left| {{\varphi _{c,p}}} \right.) = {\rm{exp}}\left( { - \frac{1}{2}{{({\mathit{\boldsymbol{f}}_r} - {\mathit{\boldsymbol{\mu }}_p})}^{\rm{T}}}{\sum ^{ - 1}}({\mathit{\boldsymbol{f}}_r} - {\mathit{\boldsymbol{\mu }}_p})} \right)$ | (13) |
轨迹T由模型θc产生的后验概率计算公式为
| $P\left( {T\left| {{\theta _c}} \right.} \right) = \frac{{P'\left( {T\left| {{\theta _c}} \right.} \right)}}{{\sum\limits_{k = 1}^K {P'\left( {T\left| {{\theta _k}} \right.} \right)} }}$ | (14) |
| $P'(T\left| {{\theta _c}} \right.) = \prod\limits_{r = 1}^L {P({f_r}\left| {{\varphi _{c,p}}} \right.)} $ | (15) |
最有可能类别θcmax的确定公式为
| ${c_{{\rm{max}}}} = {\rm{arg}}\;\mathop {{\rm{max}}}\limits_{c = 1,2, \cdots ,K} P(T\left| {{\theta _c}} \right.)$ | (16) |
如果车辆某行为对应的运动轨迹与其最匹配模型计算的后验概率也小于某一较低异常判断阈值TP时，则认为该运动轨迹异常，需要对其重点关注并及时预警，以防事故发生；否则为正常轨迹，具体公式如下：
| $\left\{ {\begin{array}{*{20}{l}} {P\left( {T\left| {{\theta _{{c_{{\rm{max}}}}}}} \right.} \right) \ge {T_P}}&{正常轨迹}\\ {P(T\left| {{\theta _{{c_{{\rm{max}}}}}}} \right.) < P}&{异常轨迹} \end{array}} \right.$ | (17) |
以真实的高速公路出入口交通场景作为研究对象，通过处理长度均为30 min的2个实际视频片段，帧大小为520×480，帧率25帧·s-1，视频内出口共有352辆车通过，入口共有447辆车通过，采用基于区域跟踪算法采集车辆轨迹，轨迹由目标不同时刻的质心点连接而成[14].经过对轨迹进行手工有效性判断及处理，最终共分别获得405条和529条出入口有效轨迹(如图 3所示)，并建立样本集.
|
图 3 高速公路出入口样本轨迹 Fig.3 Trajectories from the exit scene and entrance scene |
对获得的出入口样本轨迹分别进行聚类并构建各类相应的路径模型，参数设置如下：ε=0.01，Δ=2.0 m，TD=1.0 m，最终获得的3条出口典型轨迹聚类及路径模型如图 4所示，2条入口典型轨迹聚类及路径模型如图 5所示.对比可以发现，构建的路径模型均值线与包络线可以紧致有效地对相应样本轨迹类进行表达.
|
图 4 出口处3条直行轨迹模型学习结果 Fig.4 Three learned straight trajectories models in the exit |
|
图 5 入口2条驶入轨迹模型学习结果 Fig.5 Two learned converging trajectories models in the entrance |
出入口所有轨迹样本集进行路径建模的结果如图 6所示，分别共产生轨迹路径模型26个和31个，为简洁表示，这里不同模型仅以各自的几何均值线表示.如图所示，轨迹的路径建模结果不仅较为规律，而且与高速公路出入口处车辆的实际运动模式相一致，客观反映了车辆在出入口区域所对应样本轨迹的分布特征.因此，本文所提出的方法对于高速公路出入口区域车辆运动轨迹的路径建模是适用的.
|
图 6 高速公路入出口轨迹路径模型 Fig.6 The established trajectory path models of freeway exit and entrance |
为了验证建立路径模型的有效性，对额外采集的出入口分别为80和100条轨迹进行了试验，最终检测结果见表 1.为提供客观判据，采用人工观察的方法对测试视频及其轨迹结果进行了分析，最终发现测试集中包括异常轨迹分别为7条和8条.计算结果表明，本文建立的路径模型不仅可以检测出85%及以上的异常轨迹，而且能够保证正确率达到70%或更高水平，结果令人满意.
|
下载CSV 表 1 异常检测结果 Tab.1 Anomaly detection results |
图 7和图 8分别显示了出入口轨迹集的检测结果，普通及异常轨迹分别以白色虚线和黑色实线表示.如图所示，对于检测出的异常轨迹样本，绝大部分实际上均属违规驾驶，如车辆频繁连续变道轨迹、向右占用硬路肩的超车轨迹、清洁人员的横穿行走轨迹、长时间压线行驶轨迹等，但也有极小部分由随机驾驶行为导致的变道轨迹被虚假检测出，这是由于路径模型实质上属于统计模型的一种，其只能对场景中具有统计意义的固定轨迹模式进行建模分析，而如果要想进一步提高模型全面性，还需融入微观驾驶行为模型进行进一步拓展研究.总之，基于轨迹路径模型能够对绝大部分异常轨迹实现有效检测，并且基本与客观情况相一致，具有较为准确的分析结果，可为道路安全管理提供支持.
|
图 7 出口异常检测结果 Fig.7 Anomaly detection results in the exit |
|
图 8 入口异常检测结果 Fig.8 Anomaly detection results in the entrance |
综合考虑车辆运动轨迹的特点以及轨迹建模的相关要求，提出了一种合理的车辆运动轨迹建模方法.该方法按“先聚类、后建模”思路进行，两者有机结合，缺一不可.在轨迹聚类时，结合轨迹特点，拓展采用改进Hausdorff距离指标来衡量轨迹之间的相似性，构建了改进模糊C均值轨迹聚类算法.在轨迹聚类的基础上，基于轨迹模型构建的具体要求，建立了基于离散状态的路径模型，并随后提出了轨迹异常检测方法.通过对采集到的高速公路出入口轨迹进行试验，验证了采用本文方法所构建车辆轨迹路径模型的适用性和有效性，并有望为进一步的车辆运动行为理解提供依据.
| [1] |
TRIVEDI M. Understanding vehicular traffic behavior from video: A survey of unsupervised approaches[J]. Journal of Electronic Imaging, 2013, 22(4): 6931 |
| [2] |
MORRIS B T, TRIVEDI M M. A Survey of vision-based trajectory learning and analysis for surveillance[J]. IEEE Transactions on Circuits & Systems for Video Technology, 2008, 18(8): 1114 |
| [3] |
MAKRIS D, ELLIS T. Path detection in video surveillance[J]. Image & Vision Computing, 2002, 20(12): 895 |
| [4] |
HU W, XIAO X, FU Z, et al. A system for learning statistical motion patterns[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2006, 28(9): 1450 |
| [5] |
袁和金, 吴静芳, 贾建军. 一种基于HMM聚类的视频目标轨迹分析方法[J]. 华北电力大学学报(自然科学版), 2010, 37(6): 90 YUAN Hejin, WU Jingfang, JIA Jianjun. A method of video target's trajectory analysis based on HMM clustering[J]. Journal of North China Electric Power University(Natural Science), 2010, 37(6): 90 |
| [6] |
张宁, 施毅, 黄卫. 基于OGS-DTW算法的交通事件自动检测方法[J]. 公路交通科技, 2010, 27(8): 103 ZHANG Ning, SHI Yi, HUANG Wei. Traffic event automatic detection based on OGS-DTW algorithm[J]. Journal of Highway and Transportation Research and Development, 2010, 27(8): 103 |
| [7] |
汤春明, 浩欢飞, 韩旭, 等. 车辆轨迹的增量式建模与在线异常检测[J]. 计算机应用研究, 2014, 31(7): 2008 TANG Chunming, HAO Huanfei, HAN Xu, et al. Incremental modeling and online anomaly detection of vehicle trajectories[J]. Application Research of Computers, 2014, 31(7): 2008 |
| [8] |
范菁, 阮体洪, 吴佳敏, 等. 基于二次谱聚类和HMM-RF混合模型的车辆行为识别方法研究[J]. 计算机科学, 2016, 43(5): 288 FAN Jing, RUAN Tihong, WU Jiamin, et al. Vehicle behaviour recognition method based on quadratic spectral clustering and HMM-RF hybrid model[J]. Computer Science, 2016, 43(5): 288 |
| [9] |
ATEV S, MILLER G, PAPANIKOLOPOULOS N P. Clustering of vehicle trajectories[J]. IEEE Transactions on Intelligent Transportation Systems, 2010, 11(3): 647 DOI:10.1109/TITS.2010.2048101 |
| [10] |
XU R. Survey of clustering algorithms[J]. IEEE Transactions on Neural Networks, 2005, 16(3): 645 DOI:10.1109/TNN.2005.845141 |
| [11] |
ZHANG Z, HUANG K, TAN T N. Comparison of similarity measures for trajectory clustering in outdoor surveillance scenes [C]// Proceedings International Conference on Pattern Recognition. Piscataway: IEEE Press, 2006: 1135-1138.
|
| [12] |
ATEV S, MASOUD O, PAPANIKOLOPOULOS N. Learning traffic patterns at intersections by spectral clustering of motion trajectories[C]// International Conference on Intelligent Robots and Systems. [S.l.]: IEEE Press, 2006:4851-4856.
|
| [13] |
胡宏宇. 基于视频处理的交通事件识别方法研究[D]. 长春: 吉林大学, 2010. HU Hongyu.Research on methods for traffic event recognition based on video processing[D].Changchun: Jilin University, 2010. |
| [14] |
王俊骅, 张方方, 张兰芳. 基于OpenCV和Halcon的交通冲突视频自动检测及数据处理[J]. 同济大学学报(自然科学版), 2010, 38(2): 238 WANG Junhua, ZHANG Fangfang, ZHANG Lanfang. Halcon and OpenCV-Based traffic automatic conflicting detecting method and data transaction[J]. Journal of Tongji University(Natural Science), 2010, 38(2): 238 |