基于轨迹稀疏聚类的高速公路车辆检测

杨 露，宋焕生，张朝阳

长安大学 信息工程学院，西安 710064

1 引言

随着我国交通的飞速发展，基于视频的交通参数和交通事件检测、交通行为分析、安全预警及路侧辅助驾驶等，逐渐成为智能交通（ITS）领域的热点研究课题。其中，一个核心且关键的问题就是实现对交通目标（主要是车辆）高效准确的检测跟踪。

目前对车辆检测跟踪的方法可以分为两大类：自顶向下的方法、自底向上两大类。自顶向下的方法是以运动目标整体的结构为研究对象。该类方法在高清视频、光线良好且车辆之间无遮挡时具有很高的检测及跟踪精度。但其计算复杂度较高，运行效率较低，难以满足实时性的需求；且在实际场景中，当光线不稳定、车辆之间互相遮挡时极易出现误检以及目标丢失，导致车辆轨迹不完整影响车辆轨迹信息的准确提取。自底向上的方法采用从局部到整体的分析方法，以车辆目标局部的特征点检测为基础，逐渐向上完成目标的分割过程。该类方法对光照、抖动、遮挡等情况具有一定的稳定性，且其算法较为简单、运行效率高，更能满足实际应用中实时性的需求。该类方法通常先获取车辆特征点轨迹，对轨迹属于哪辆车进行判断。故轨迹聚类成为该类方法中的核心问题。

现有的轨迹聚类方法主要分为两类，一类是基于轨迹距离度量的分类方法。该方法以建立面向轨迹的度量为主要方向，对轨迹之间的距离进行研究。例如，Berndt等[1]提出了动态时间弯曲距离DTW（Dynamic Time Warping）。随后，Vlachos等人[2]提出一种使用最长公共子序列模型LCSS（Longest Common Subsequences）来计算轨迹间的相似度。Chen和Ng[3]以及Chen等人[4]使用编辑距离来定义距离函数，根据其成本函数的不同分别为实际惩罚编辑距离ERP（Edit distance with Real Penalty）和实际序列编辑距离EDR（Edit Distance on Real sequences）。另一类则是基于统计相似性的轨迹聚类方法。例如，Yutaka等人[5]提出了一种基于形状对移动对象轨迹的相似检索。Abraham等人[6]定义了一种基于兴趣点POI（Points of Interest）和兴趣时间TOI（Times of Interest）的轨迹相似度的计算方法。Jung-Im等人[7]提出了一种计算轨迹间不相似程度的度量DSL。

虽然目前的轨迹聚类和建模方法已解决了轨迹分析中的各种问题，但这些方法仅考虑了轨迹的二维信息。由于摄像机角度与光线的影响，仅考虑轨迹的二维信息难以解决车辆遮挡等影响对轨迹聚类结果的影响，并且，这些方法对车辆在路面上的分布以及车辆的运动信息考虑不足，许多有价值的信息没能投入使用，无法精准地对车辆进行检测。

本文针对上述情况，提出一种高速公路车辆的检测方法。方法总体流程图如图1所示，在图像平面上采用ORB[8]（Oriented FAST and Rotated BRIEF）算法提取特征点，并利用基于金字塔LK光流算法对特征点进行跟踪，实时获取运动目标的图像特征点轨迹；再将轨迹逆投影至世界坐标系，得出特征点轨迹的位置信息以及运动信息；对轨迹进行稀疏化处理后并利用谱聚类方法得到轨迹初步聚类结果。最后，利用车辆大小等先验信息并结合车辆运动信息对聚类进行合并，得到精准的车辆检测结果。本方案有效地减少了计算量，可实现高精度的车辆实时检测，结合了轨迹的三维信息能有效地解决车辆遮挡问题，相较其他方法检测精度更高。

图1 本文检测方法流程图

2 特征点轨迹

2.1 ORB特征点提取

运动目标上的特征点包含了多样的运动信息以及三维结构信息。精准地检测出运动目标的特征点，是准确获得聚类结果的基础和不可或缺的条件。研究者们提出了许多特征点描述算子可以直接利用。本文选用ORB完成车辆特征点的实时检测，得出特征点在图像坐标系中的位置，如图2所示。

图2 ORB特征点提取

ORB是基于视觉信息的特征点检测与描述算法，是具有方向的FSAT角点检测算子与具有旋转不变特性的BRIEF角点描述子的结合。相较其他算法，虽ORB对特征点的描述细致程度较低，但其受图像噪声的影响较小，且具有尺度、仿射变换和旋转不变性，计算时间消耗较少。对ORB与SURF[9]、SIFT[10]、BRISK[11]、FREAK[12]等算法进行分析后，将上述算法在相同的高速路监控视频帧上进行特征点检测，以上算法对车辆特征点的检测效果相当，但本文算法是为高速公路视频实时检测提供有效的方法与手段，因此对算法的运行速率要求较高。各算法的检测时间如表1所示，ORB算法特征点检测所需时间最短。

表1 特征检测时间

2.2 金字塔LK光流跟踪

为了得到稳定的特征点轨迹，需要对特征点进行跟踪。本文利用基于金字塔LK光流算法进行特征点跟踪。金字塔LK光流算法利用了金字塔模型，该模型是尺度变换的一种方法，它通过对图像进行上采样或下采样而生成，如图3所示。金字塔LK光流算法的大致过程是：从最高层开始，用LT方法计算图像金字塔中某层的光流信息，得到的信息作为其下一层金字塔的起点，不断对上述过程进行迭代运算直到处理到最底层。该算法利用“由粗到细”的设计思路，将高层次匹配到的较粗的特征点位置作为低层次光流匹配的起点进行搜索，从而将不满足小运动假设的概率降到最低，实现对目标特征点持续而稳定的跟踪。

图3 金字塔模型

如图4所示，使用该方法对视频帧序列进行稳定跟踪，即可得到特征点的二维轨迹。

图4 金字塔LK光流跟踪获取轨迹

特征轨迹可以表示为特征点数据集，如下所示：

其中，N为轨迹数据集轨迹总条数i为轨迹数据集中的特征点轨迹的条数，ni是第i条特征点轨迹的特征点个数，(uin,vin)是第i条轨迹第n个特征点的像素坐标，即其在第i帧中的位置。

3 轨迹聚类

3.1 轨迹3D特征构建

摄像机的成像将目标从世界坐标系转换至图像坐标系，这种映射是一对一的关系，然而从图像坐标系到世界坐标系的映射却是一对多的关系，因此这种转换必定会丢失一部分信息。目前几乎所有的基于视频分析的目标检测、跟踪算法，都是在图像坐标系上开展的，但由于摄像机成像的透视变换，原目标的几何特性以及运动特性在经过透视变换后消失不见。该问题导致基于图像坐标系的轨迹聚类难以达到较高的精度。为了更好地解决复杂交通场景中车辆检测的问题，本文结合相机的标定参数，将轨迹逆投影至世界坐标系；通过对车辆三维轨迹的分析，选择高度、速度、3D位置信息作为特征点轨迹的3D特征并提取。

由于在标定场景下尺度因子未知，通过轨迹点的图像坐标无法直接获取其世界坐标系坐标。因此，需要特征点的真实高度，才能得到唯一的逆投影点。由于车辆的高度是在有限的范围内，根据文献[13]可知，利用公式（2）可计算出轨迹间的相对高度间接获取车辆轨迹点的3D信息。

其中，v为参考轨迹速度，Hc为摄像机高度，Hi、vi(2D)分别为第i条特征点轨迹的相对高度、像素速度。

构建轨迹特征的具体步骤如下：

（1）计算轨迹逆投影速度。将所有轨迹点投影至世界坐标系，并计算其逆投影速度。例如，对于第i条特征点轨迹上第k个特征点(uik,vik)，将其投影至地平面（高度为0 m），投影后3D坐标记为(Xik,Yik,0)。结合视频帧率，通过式（3）得出其逆投影速度vi(3D)。

其中，s为时间t内特征点的像素位移，n为连续的帧数。

（2）轨迹间的相对高度计算。同一车辆上不同高度的特征点的逆投影速度不同，距地面越近逆投影速度越小，与车辆的真实速度越接近。选择逆投影速度最小的特征点轨迹作为参考轨迹，假设该速度为所属车辆目标的真实速度。结合公式（2）计算出其他轨迹相对于参考轨迹的相对高度hi。

（3）获取特征点轨迹的3D位置。根据摄像机的透视投影矩阵变换方程，将轨迹最新的特征点重投影至高度为hr平行于地面的平面。对于第i条特征点轨迹上最新的特征点(uini,vini)，将其投影至高度为hr的平面，更新其3D坐标为重投影后的(Xini,Yini,hr)。由于本文选用轨迹，并将其最新的点作为位置特征，无需将轨迹上所有点重新投影，只需将轨迹最新的点重新投影，作为轨迹特征点的的3D位置特征，大大减少了计算量。

3.2 基于稀疏谱聚类的轨迹初聚类

目前，图论的谱理论已经相当成熟，有很多研究成果可直接应用。本文利用特征点轨迹的3D信息构造了一种轨迹间新的相似度量关系，并对相似矩阵进行稀疏化得到稀疏相似矩阵，并通过矩阵变换构造分块对角矩阵[14]，依据选定的划分准则对其进行划分；再结合Ncut[15]算法实现对车辆特征点轨迹的聚类，得到初步划分结果。

3.2.1 相似矩阵构造

G=(V,E,W)为无向加权图，V为特征点轨迹集，E为连接轨迹节点的边所构成的集合，为轨迹点之间的相似度矩阵。

本文通过对刚性运动约束的分析，将轨迹间的相似度定义如公式（4）所示，从而构造出相似矩阵。

其中，i=1,2,…,N;j=1,2,…,N；d(Fi,Fj)2为轨迹集中任意两条轨迹的属性特征向量间的欧式距离，Fi(vi(3D),hr)为1×2的特征向量，包含了该轨迹的2D轨迹速度、参考轨迹的相对高度。

相似矩阵具体构造过程如下：

（1）根据轨迹集的2D轨迹点计算每条轨迹在图像上的速度v={v1,v2,…,vN}，选取最小的2D轨迹速度vp所对应的轨迹为参考轨迹tp。

（2）利用公式（2）计算每条轨迹ti与参考轨迹tp之间的相对高度hi。

（3）构造每条轨迹对应的属性特征向量Fi( )vi(3D),hr。

（4）通过式（4）计算不同轨迹之间的相似度wij，构造出相似矩阵W。

3.2.2 相似矩阵稀疏化

当轨迹数量较多时，程序计算量迅速增加，难以达到实时处理的要求。本文通过相似矩阵稀疏化解决该问题。由实验知同一辆车的特征点轨迹的3D相对高度差值在0～4 m的范围内，利用该特性对轨迹进行稀疏化。相似矩阵稀疏化后减少了数据量，降低了算法的复杂度并减少了程序运行的时间。再通过矩阵变换构建分块对角矩阵，分块对角矩阵具备稀疏矩阵的所有良好性能，结构简单，容易区分类群体，选取普通算法即可达到优秀聚类的目的。

具体可分为如下两步：

（1）矩阵稀疏化。若轨迹间的相对高度大于4 m，将两轨迹间的相似性wij置0。

（2）将上一步得到的相似矩阵通过行和列排序等初等变换，再经过局部调整得到分块对角矩阵。

3.2.3 基于Ncut的谱聚类

在对各种划分准测的分析和对比后，Ncut准则优势明显，其既能克服最小割准则的固有缺陷，又能兼顾类内的相似性和类间的差异性，并且计算复杂度不高，运行速率可以满足实时性，故选择其作为本文聚类的划分准则。

Ncut的理论已经相当成熟，有很多研究可直接使用。具体实现步骤如下：

（1）根据前文计算相似度矩阵W并进行稀疏化。

（2）计算其规范化的拉普拉斯矩阵（Laplacian matrix）。

（3）计算 L的特征值{λi,i=1,2,…,N} 及其对应的特征向量{Hi,i=1,2,…,N}。

（4）计算与Hi对应的指示特征向量Qi。

（5）利用Q的前k个最小特征值对应的特征向量进行K-means聚类。

处理结束后输出N×1维聚类结果矩阵，给出N个对象所对应的类别，方便后续类间合并的处理。

3.3 类间合并

经过初始聚类，大部分情况下能够精准地分割车辆，但是由于构造的相似矩阵的误差，会出现同一辆车的轨道被划分为多个类别的情况，特别是来自大车上的特征点轨迹。因此，有必要结合刚性运动规律以及车辆大小等先验知识对聚类结果进行类间合并。

在此阶段，通过判断是否满足3D车辆模型，决定类间是否进行合并处理。其本质为比较各个特征点之间的位置关系，且特征点之间的3D坐标是估计值，因此不需要精确地对各种车辆进行建模。本文中将车辆的3D模型简单的分为小型车辆、中型车辆和大型车辆三类，并对其进行简单的建模。类间合并算法的具体实现过程分为以下步骤：

（1）设类别Ci和Cj是轨迹初步聚类结果中的两个类别，两个类别内分别有ni、nj条轨迹。计算每条轨迹的逆投影速度，找到每个类别的最小逆投影速度vi和vj作为类别Ci和Cj的代表速度，具有最小逆投影速度的特征点轨迹作为该类别的参考轨迹。

（2）比较两个类的代表速度vi和vj，找到最小的代表速度作为该运动物体的真实运动速度vT，即参考速度vT=min(vi,vj)。

（3）将参考类别内的轨迹点高度置为0，将其恢复至世界坐标系得出其3D坐标(Xi,Yi,0)；结合参考速度vT计算出待合并类中轨迹的相对高度hr，将其恢复至世界坐标系得出其3D坐标(Xm,Ym,hr)。

（4）计算待合并类别内特征点轨迹与参考特征轨迹的绝对距离，即两轨迹代表点3D位置的绝对距离，用DIS(ΔX,ΔY,ΔZ)来表示。

（5）根据ΔZ预先判断该运动目标可能属于的3D模型类别，再判断ΔX与ΔY是否都在该3D模型内，若ΔX与ΔY满足由ΔZ所给出的3D模型，则记录待合并类别内可以进行处理的特征轨迹条数的参数nc加1，不满足则跳过该轨迹。当待合并类别内的nj条特征点轨迹都处理完后，若，则将两个类别合并；若不满足，不做合并处理。

4 实验结果分析

4.1 实验环境

为了验证所提出的聚类框架的有效性和鲁棒性，本文以杭州金衢高速部分路段真实监控视频为测试数据，在Windows10平台上进行了测试，文中特征点轨迹获取与轨迹聚类算法使用C++编写，运行于Visual Studio 2015平台，并与2D谱聚类方法做出了比较。测试视频每帧图像的大小为1 280×720，频率为25帧/s。

4.2 轨迹3D特征提取

4.2.1 特征点轨迹

使用ORB算法对不同场景及不同视角的高速监控视频帧上测试，实验结果如图5所示，局部特征点检测器不仅能在日常白天有效地检测前景目标中的特征点，还能在光照较暗且视角较低的隧道场景稳定的检测到运动目标特征点，也能在能见度较低的雾天、雨天检测出车辆目标特征点。

图5 不同场景下ORB特征点提取结果

利用基于金字塔LK光流算法进行特征点跟踪，在实际视频上进行跟踪得到的车辆特征点轨迹结果部分如图6所示。

从图6（a）～（c）中可以发现，该算法能够实现正常白天场景下，对高速公路监控视频中的车辆目标进行较为准确的特征点轨迹提取，即使车辆存在部分遮挡如图6（a）、（b），提取的特征点轨迹数据稳定性仍较高。图6（d）、（e）为雨雾天下的检测结果，大部分情况下，算法能较为稳定地获取特征点轨迹，但当雨雾过大导致画面模糊，或镜头上雨滴导致画面严重变形，部分特征点轨迹会出现弯曲及断裂的情况。在低视角、低光照的隧道场景中，由于摄像机架设高度较低，车辆遮挡问题以及车辆速度的影响，导致该环境下特征点轨迹抖动较大。

图6 不同场景跟踪所得轨迹

4.2.2 3D特征提取

对图7所示的三组特征点轨迹提取3D特征。首先计算每条轨迹在像素坐标系下的速度得出其高度，再将轨迹恢复至三维空间提取其特征。

图7 车辆特征点轨迹

图7 三个场景特征点轨迹的实际高度如图8（a）～（c）所示，真实速度如图8（d）～（f）所示，轨迹在世界坐标系下的位置分布如图8（g）～（i）所示。在所有特征点轨迹来自同一辆车、车辆间没有遮挡或有较明显的速度差时，如图8（a）、（b）场景下，来自同一辆车的特征点轨迹的3D相对高度差值基本在0～4 m的范围内，而不属于同一辆车的轨迹高度差一般会超出这个范围，图8（c）；且特征点轨迹恢复至3D空间后具有较明显的空间分割信息。但当车辆间存在遮挡且车辆间运动模式相似时，如图8（c），来自不同车辆的特征点轨迹相对高度差在0～4 m的范围内，其真实速度差别无明显差距，轨迹的3D分布也没有明显的分割信息，单独考虑单个特征不能达到很好的分类效果。

4.3 轨迹聚类

当轨迹较多的时候，直接计算轨迹间的相似矩阵计算量增大，难以保证算法的实时性。图9（a）中共有25条轨迹，轨迹真实高度分布如图9（b）所示。按3.2.2小节，将轨迹高度差为4 m以上的轨迹间相似度置为0。相似矩阵由25×25的矩阵简化为17×17、5×5、3×3三个相似矩阵。在调整后的相似矩阵上使用基于Ncut的谱聚类，得到的聚类中心分布如图9（c）所示，聚类结果如图9（d）所示，此情况下算法表现良好。

图8 轨迹3D特征

图9 轨迹聚类过程

实验使用杭州金衢高速20个路段的1 000组车辆轨迹数据进行聚类算法的测试，分别对包含不同数量的车辆目标的轨迹数据集做聚类分析，其中包含的车辆目标个数有1个、2个、3个、4个等。

对轨迹集仅进行谱聚类的部分实验结果如图10所示。可以发现即便车辆发生共速或者部分遮挡，本文算法也能将属于不同车辆的特征点轨迹进行有效的聚类。如图10（a）～（e）。但是，也出现了少量将同一目标的运动轨迹分成多个类别的情况，如图10（f）。经过对实验数据的分析，发现这类情况主要是由相似矩阵构建过程中的误差导致的。

图10 稀疏化谱聚类结果

不同场景中的轨迹初步聚类结果与经过类间合并处理后的对比结果如图11所示，图11（a）～（c）为未进行类间合并的聚类结果，图11（d）～（f）为相应场景进行类间合并后的结果。发现经过类间合并的完善，轨迹的聚类结果完全正确，其中该场景中所建立的简单3D模型参数如表2所示，由于本文中恢复的3D参数是估计值，较真实值偏大，所以该模型与真实模型之间存在略微的差异。

图11 类间合并结果

表2 三维车辆模型m

以图11（a）中的17条轨迹2个类别为例，对谱聚类的实验结果进行分析。图中的17条轨迹初聚类为两个类；该场景下摄像机的高度为13 m，则图像中两轨迹类的中心位置以及逆投影速度如表3所示。

表3 初聚类数据

根据3.3节，进行计算，两类满足合并要求聚为一类，如图11（d），最终类数据信息如表4所示。

表4 最终聚类数据

为了更好地评价本文算法的聚类效果，使用聚类的精度CP来进行描述，其定义如公式（6）所示：

其中，N表示具有相同车辆数目的轨迹数据集个数，ti为第i个轨迹数据集中正确分类的轨迹条数，ni为第i个轨迹数据集所包含的轨迹总条数。实验所得聚类精度如表5所示，针对不同数目的车辆，其运行时间如表6所示。

表5 聚类精度%

表6 聚类所需时间s

由表6可以看出，算法的运行时间随着轨迹条数的增多而增长，且基于3D轨迹的聚类所耗费的时间虽然比2D轨迹数据的时间要长，但其运行时间都不超过5 s，可以满足实际检测的需求，为智能交通系统提供实时交通数据。

为了更进一步评价本方法的聚类效果，本文对高速路段在某段时间内监控视频的整体车流量进行了统计，选用杭州金衢高速部分路段进行统计，其中每个路段的测试时间为60 min，实验结果如表7所示，可以发现本文算法应用于实际的车辆检测平均准确度可达到93%，可为交通流量统计和行为分析提供有效的数据参考。

表7 车流量统计结果

5 结束语

本文提出了一种基于轨迹稀疏谱聚类的高速公路车辆检测方法。本方法主要分为四个阶段：特征点轨迹获取、轨迹特征构建、轨迹聚类、类间合并。在轨迹特征构建阶段，对轨迹的三维参数进行重构，减小了光照抖动、车辆遮挡对聚类结果的影响，较其他方法检测结果更为精准。在轨迹聚类阶段，对轨迹相似矩阵进行稀疏化能减少计算时间，满足实时检测的要求。在不同的交通路段中，采用本检测方法对聚类性能进行了测试。实验结果表明，即使有拥堵等情况，方法也能满足实时检测的要求且精度较高，能达到93%。因此本方法性能良好，能实时提供准确有效的交通参数，可应用于交通流量测量、车辆行为分析、高速公路异常事件检测等不同领域，对高速公路运行管理和提升运行效率具有重要意义。本方法类间合并所使用的车辆模型固定，当货车长度大于10 m时容易出现误差。下一步将对轨迹特征向量的构造进行优化以提高初聚类精度，使得方法的适用性更佳。