基于交通视频序列的多运动目标跟踪算法

高韬，刘正光，张军

(天津大学 电气与自动化工程学院，天津，300072)

多运动目标跟踪应用广泛，特别是在交通视频监控方面，对其进行了广泛的研究，提出了许多识别跟踪算法。然而，这些算法大都只针对某一特定场景，并且由于硬件的限制，这一课题的发展历史较短，而且其内容涉及到图像处理、模式识别和人工智能等多个学科，其理论还不够完善，一些重要的问题尚未解决，行之有效的方法和技术还有待开发。肖敬若等[1]结合扩展卡尔曼滤波法与均值漂移法对运动目标进行跟踪，该方法可用于背景较复杂的情况，但是，当目标形变较大，并且运动方向改变时，跟踪往往会失效。Yao等[2]通过光流法识别运动目标后，利用卡尔曼滤波，采用运动区域颜色特征匹配跟踪方法，对多个目标进行跟踪，但该方法只适用于背景较简单、目标较明显的情况。如果背景过于复杂且目标不明显，会导致处理速度过慢，影响跟踪效果。Lei等[3-4]使用混合高斯模型背景建模法检测运动目标，并通过卡尔曼滤波，利用目标颜色直方图和形状模型进行匹配识别，从而对多目标进行跟踪。但跟踪匹配参数无法自适应获得，常会导致累积跟踪误差，准确度较低。Okuma等[5-6]提出Boosted粒子滤波与均值漂移相结合的多目标跟踪算法，可有效地跟踪人体等非刚体目标，并且具有较好的抗遮挡性。但该算法事先需要大量的样本训练，计算复杂度高，并且不适用于目标大小变化剧烈的场景，限制了它的应用。卢晓鹏等[7]也提出一种Mean-shit与粒子滤波结合跟踪算法，首先应用Mean-shift 算法进行跟踪，由得到的目标位置计算相似系数，与预先设定好的门限系数比较并采用不同的滤波策略，具有一定的抗遮挡性。但该算法同样没有考虑目标大小变化明显的情况，并且选择粒子采样的门限阈值需人工预先设定，不利于实际应用。在多目标数据关联方面，最直接的方法是最近邻域(NN)法，即如果1个量测与1个目标轨迹的空间距离最近，则该量测为该目标的当前量测，但在实际应用中采用欧式距离的测度常存在各种缺陷；联合概率数据关联滤波(JPDA)算法[8-9]综合考虑了相交的波门内的所有回波和航迹，在密集回波环境下，跟踪多个近距离机动目标时仍然有很好的跟踪性能，但其计算量随着跟踪门内回波数目的增长而呈指数增长。在密集回波环境下，由于其计算量和存储量巨大而难于在实际中应用。多假设数据关联跟踪算法(MHT)[10]把多个假设继续传递，让后续的观测数据解决这种不确定性，但其主要应用在雷达领域的航迹跟踪。目前，数据关联根据先验知识，如目标的动力学特征，将检测结果与目标状态关联起来，并对跟踪轨迹进行滤波，而针对视频监控领域，摄像头与图像之间相关性较低，所以，应对被跟踪目标建模并据此在图像序列各帧中定位目标。针对现有跟踪算法的不足，本文作者提出一种结合SIFT特征粒子滤波和Mean-shift算法，采用队列链表结构数据关联的多目标跟踪算法，提高了跟踪的准确性与效率，具有较高的应用价值。

1 运动目标识别

背景减法是目前最常用的一种识别算法，相对于其他算法，能够提供最完整的运动信息，而且其操作简单，检测位置准确且速度快。但该算法的性能完全取决于背景生成的质量。本文作者对运动目标识别采用一种基于Marr小波概率核函数的背景算法(MarrB)，并在 B/RDWT(Binary/redundant discrete wavelet transforms)域[11]提取运动信息从而检测运动目标。

1.1 静态背景生成

将初始帧作为背景B，设当前输入帧为f，分别对其进行金字塔1/2分解，进行2级分解的公式为：

其中：n1和n2都为3，表示高斯滤波核宽；均方差σ为0.5。交通监控摄像头一般固定在道路标杆上，考虑到车辆干扰对其引起的轻微震动，设偏移矩阵为[v,h]，v和h分别代表垂直和水平抖动参数。设第n-1级的初始偏移矩阵为[vn-1,hn-1]，偏移函数为：

其中：fmax和fmin分别为图像中像素的最大和最小灰度。为了便于实际运算，采用 Gauss函数的差ψ(t)=形成的DOG(Difference of Gaussian)来近似Marr小波。不断调整(Δx,Δy)，根据最佳近似度得到最佳偏移距离同时，将作为下一级fn的初始偏移矩阵。通过逐级迭代，最终确定背景图像的扩展范围。设偏移修正过后初始背景像素为B(i,j)，当前帧像素为f(i,j)，定义当前帧与背景偏差的Marr核概率分布为：

图1 背景建模比较Fig.1 Background modeling comparison

其中：控制参数α=0.3；方差γ初值取β=0.01。同时，设背景像素更新权重为：

则迭代更新背景为：

其中：i为迭代次数；N为处理视频序列帧数。图 1所示为连续帧差法、混合高斯法和本研究中使用的MarrB算法对交通视频序列背景建模的结果。从图 1可知：MarrB算法在去除背景噪声以及静态背景生成方面具有更佳的抗干扰鲁棒性。

1.2 B/RDWT域运动目标识别

分别对背景和当前帧进行B/RDWT，在离散小波域直接提取运动信息。对于二维数字图像，可采用二进小波变换的特例：冗余离散小波变换(RDWT)来实现。冗余离散小波变换是除去了下采样的离散小波变换。由于没有下采样，不同尺度的时间抽样率固定，离散小波变换固有的平移变化在这里被消除，并且冗余离散小波变换后各子带的大小与输入信号的大小相同，从而运动信息M(x,y)可根据各子带差异获得，具体过程可参考文献[11-12]。图2所示为当前帧以及根据运动区域多运动车辆目标识别检测结果。

图2 运动车辆检测Fig.2 Motion vehicles detection

1.3 边缘阴影剔除

要剔除阴影，首先要判断图像中是否有阴影存在，目前，判断场景中是否有阴影存在的研究较少。毛燕芬等[13-14]将前景像素分为“暗色”和“亮色”，定义“亮色”像素点的平均能量为Eb，阴影程度为Pd，当前景区域的Eb和Pd都超过相应阈值时，判断存在阴影。但阈值常由经验判定，并且当背景环境较复杂时，常会误判。一般地，当场景中光照较强时，阴影很可能存在，因此，本文作者采用直接判断背景亮度来判断是否有阴影。当亮度超过类间方差阈值T的像素数目时，判断为存在阴影，一般T取全部像素数目的1/4。该方法处理速度快、效果好，即使偶尔误判，由于采用边缘阴影剔除算法，也不会导致目标丢失。目前，运动目标阴影检测一般采用基于彩色空间的方法[15-16]。该方法认为阴影区域色彩变化很小，只是背景彩色分量乘以某个系数K(掩膜)，以此进行阴影分割。但是，在某些情况下，目标和阴影在颜色信息上没有明显的差别，例如，当交通道路环境中同时存在黑车和阴影时，难于区分黑车与黑色阴影。一般认为，阴影处具有稀少的边缘细节，而目标内部边缘细节丰富。本研究中，依靠完整提取的前景信息，首先，对前景模板进行“Canny”算子边缘提取，然后，对前景区域进行“Sobel”边缘提取，除去噪声后的两者信息的差值即可得到运动目标。图3所示为该算法各步骤处理结果。

2 结合SI_P与Mean-shift的跟踪算法

以检测出来的运动目标信息作为后续帧跟踪的初始条件，采用一种结合 SIFT特征粒子滤波和 Meanshift的跟踪算法，提高跟踪的准确度。

2.1 SI_P算法

SIFT特征点[17]代表了运动目标鲁棒性特征，将其与粒子滤波算法[18-19]相结合，形成 SI_P滤波算法。初始粒子的选取以及状态转移都以 SIFT特征点为依据。算法具体过程如下。

(1)样本初始化。在初始帧中通过运动目标识别算法确定目标区域，并计算目标模板的颜色概率分布：

其中：I为粒子区域的像素的个数；δ为Kronecker余子函数；参数a为粒子区域的规模大小；h代表颜色直方图；xi为第i个像素点的位置；函数f为归一化因子；k为Epanechnikov核函数的轮廓函数。结合目标区域和当前帧 SIFT特征点建立初始状态样本集合

(2)由替代选择法[20]根据样本权值从样本集St-1中抽取N个样本。计算样本集合归一化累积权值，产生[0, 1]区间上的均匀分布的随机数r。在样本中搜索使得权值的最小k，并使

(3)设样本空间通过运动模型

其中：A为状态转移矩阵；R为扰动矩阵；r为随机高斯矩阵。A和R分别为：

其中：σ=3, 0.35α= 。同时，将t时刻由SIFT匹配的特征点赋予St，得到Ssift,t。

(4)计算候选样本分布和目标模板的Bhattacharyya系数

重新计算Ssift,t中每个样本的权值：

图3 阴影剔除后的目标提取Fig.3 Targets segmentation after removing shadow

(5)由样本的加权平均估计t时刻运动目标的中心位置：

图 4所示为结合 SIFT特征点的粒子滤波跟踪结果。

2.2 Mean-shift运动目标边界提取

Mean-shift[21]是一种基于外部特征的跟踪算法，能够对机动目标进行实时跟踪。对于目标实时跟踪，设由 SI_P滤波得到的目标中心初始位置为yˆ0，计算分布概率，然

后计算权值{wi}，其中：

为颜色概率分布函数；i=1, …,nh。令g为加权核函数，则目标中心新位置为：

则

通过自适应改变Marr小波核宽尺度，较好地解决了上述问题。

3 多目标数据关联

对于交通视频监控序列，车辆的行驶情况与数据结构的队列链表类似，先驶进某一道路场景的车辆一般也先离开道路(违章超车情况较少，并且不影响跟踪准确性)。因此，对于多运动车辆的跟踪数据关联采用队列链表处理法(如图 5所示)，链表中每一个元素代表运动车辆，元素为结构体，包含车辆的中心位置、四周边界点位置、行驶方向、内部颜色概率分布以及最佳Bhattacharyya匹配系数等重要信息。

(1)新目标的进入。在空间上，新目标只可能在视频图像帧的边界区域出现。若在图像的边界区域检测到1个观测值，中心为y, 则计算其和所有现存目标的距离D；若该距离远大于目标在相邻帧中可能运动的距离，则说明该观测为1个新目标，在队列链表中插入相应新元素值。否则，计算其颜色概率分布pu(y)，判断其与现存运动目标{ω1,ω2, …,ωn}的Bhattacharyya相关系数ρ，即若ρ小于现存目标的Bhattacharyya系数，则判断为新目标；否则，选取差值最大的为最佳匹配目标的状态变化，并更新链表对应元素内部结构值。

图4 SIFT特征点粒子滤波跟踪Fig.4 Particle filtering tracking based on SIFT matching

图5 队列链表数据关联Fig.5 Data association of queue technique

(2)旧目标的消失。旧目标的消失也只可能出现在图像的边界区域。假设上一帧图像中的目标ωi接近边界，即将在下一帧图像消失，则用如下方法对消失目标进行判定：读取新一帧图像，计算目标ωj与新一帧中各目标{ω1,ω2, …,ωm}的 Bhattacharyya相关度，若与任何目标都不相关，则目标ωj消失。

该方法的优点在于运算复杂度低及利于交通监控。在实际监控中，更关心对违章车辆的监控，如跨道行驶、逆行和闯红灯等车辆，对这些车辆可根据目标的中心值以及行驶方向快速判断。对于无违章行为的目标可以提前从队列链表中删除，不进行处理，从而提高跟踪系统的性能并降低对硬件的需求，利于现场应用。

4 实验结果

图 6所示为传统粒子滤波跟踪与 SI_P(SIFT-particle)滤波跟踪性能，十字代表粒子状态，黑线为滤波得到的运动轨迹。从图6可以看出：在SI_P算法中，每帧中的粒子一直保持在目标区域内，而在传统粒子滤波算法中，由于目标面积改变，轨迹误差较大，从而偏移运动物体导致跟踪失效。

同时，在CPU为1.4 GHz，内存为512 M，软件为 VC++6.0的环境下，选取 15帧图像(分辨率为768×576)，对两者的运行时间进行对比，结果如图7所示，添加SIFT特征点提取过程后，SI_P平均运行时间只比粒子滤波算法的平均运行时间多 0.15 s，完全在监控系统时延容许范围内。

对于交通视频序列的多目标跟踪，虽然遮挡车辆目标的分离是一个很难的问题，但是在交通监控的实际应用中，对于在遮挡情况比较严重时(比如交通路口的堵车)，往往更关心的是堵车队列的长度，对于单独车辆的分割没有很高的要求；只有在车流比较顺畅时才更关心单独车辆的检测与跟踪，而在这种情况下，车辆之间往往都有一定的间距，遮挡的情况比较少，即使有也比较简单。图8所示为高速上车辆路监控结果。在实际监控应用中，当车辆目标过于细小时监控也无意义，行人和远处车辆可作为噪声去除，而主要关注近景车辆。作为比较，将本文跟踪系统与目前使用较广泛的 MoG-Kalman多目标跟踪系统[3-4]进行对比，测试序列选为市区车流量较大时的监控录像片断。图9和图10所示为2种跟踪系统的测试结果。从图9和图10可以看出，由于背景建模以及运动识别的准确性，本文作者提出的跟踪系统能有效地除去行人、晃动的树叶及光照的变化等背景噪声的影响(为清晰起见，去掉了粒子显示)，同时跟踪窗口尺度随目标大小自适应改变，并且对车辆的相互遮挡也具有一定的鲁棒性；而MoG-Kalman多目标跟踪系统由于背景差的缺陷，识别结果具有较大误差，往往只含有噪声信息，跟踪窗口也无法自适应改变尺度。对于该序列，设识别误差测度e为：

图6 传统粒子滤波与SI_P滤波跟踪Fig.6 Traditional particle filtering and SI_P filtering tracking

图7 运行时间对比Fig.7 Runtime comparison

图8 高速路跟踪结果Fig.8 Multiple targets tracking on freeway

图9 本文跟踪系统在市区道路上的多目标跟踪结果Fig.9 Multiple targets tracking on urban road by system provides by authors

图10 MoG-Kalman跟踪系统在市区道路上的多目标跟踪结果Fig.10 Multiple targets tracking on urban road by system of MoG-Kalman

其中：r为算法识别跟踪的全部像素数目；f为前景像素数目。选取0～230帧作为对比对象，识别误差结果如图11所示。

图11 误差测度比较Fig.11 Error comparison

5 结论

(1)提出了一种基于交通视频序列的多目标跟踪算法。该算法通过Marr小波概率核函数生成静态背景，提高了背景生成的有效性，并结合当前帧在B/RDWT域进行多运动目标识别，同时采用边缘阴影剔除算法去除阴影的干扰。

(2)运动跟踪采用新型的SI_P粒子滤波算法，并结合均值漂移法获得运动目标的准确跟踪窗口，并自适应改变尺度。采用队列链表法记录多运动目标之间的数据关联，在提高识别准确率的同时降低了运算的复杂度。实际道路测试结果表明：该算法对于多运动目标识别跟踪具有优越的性能，可应用于智能交通监控、跟踪等。

[1] 肖敬若, 张艳宁, 胡伏原, 等. 一种鲁棒的多目标自动跟踪算法[J]. 信号处理, 2007, 23(3): 437-440.XIAO Jing-ruo, ZHANG Yan-ning, HU Fu-yuan, et al. A robust automatic multi-target tracking algorithm in complex environments[J]. Signal Processing, 2007, 23(3): 437-440.

[2] Yao F H, Sekmen A, Malkani M J. Multiple moving target detection, tracking, and recognition from a moving observer[C]//Proceedings of the IEEE International Conference on Information and Automation. New York: IEEE, 2008:978-983.

[3] LEI Bang-jun, XU Li-qun. Real-time out-door video surveillance with robust foreground extraction and object tracking via multi-state transition management[J]. Pattern Recognition Letters, 2006, 27(15): 1816-1825.

[4] Rowe D, Reid I, Gonzàlez J, et al. Unconstrained multiple-people tracking[C]//Proceedings of the 28th DAGM Symposium. Berlin: Springer, 2006: 505-514.

[5] Okuma K, Taleghani A, Freitas N, Little J, Lowe D. A boosted particle filter: multitarget detection and tracking[C]//Proceedingsof the 8th European Conference on Computer Vision. Berlin:Springer, 2004, 1: 28-39.

[6] CAI Yi-zheng, Freitas N, Little J. Robust visual tracking for multiple targets[C]//Proceedings of the 9th European Conference on Computer Vision. Berlin: Springer, 2006, 4: 107-118.

[7] 卢晓鹏, 殷学民, 邹谋炎. 一种基于颜色分布的混合视频跟踪方法[J]. 电子与信息学报, 2008, 30(2): 259-262.LU Xiao-peng, YIN Xue-min, ZOU Mou-yan. A hybrid algorithm of object tracking based on color distribution[J].Journal of Electronics & Information Technology, 2008, 30(2):259-262.

[8] 巴宏欣, 赵宗贵, 杨飞, 等. 多传感器多目标跟踪的 JPDA算法[J]. 系统仿真学报, 2004,16(7): 1563-1566.BA Hong-xin, ZHAO Zong-gui, YANG fei, et al. JPDA in multisensor multitarget tracking[J].Journal of System Simulation, 2004, 16(7): 1563-1566.

[9] 杨春玲, 余英林, 刘国岁. 多目标跟踪中的数据关联算法[J].系统工程与电子技术, 2000, 22(3): 11-15.YANG Chun-ling, YU Ying-lin, LIU Guo-sui. Data association algorithm in multi-target tracking[J]. Systems Engineering and Electronics, 2000, 22(3): 11-15.

[10] Cox I J, Hingorani S L. An efficient implementation of reid's multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(2): 138-150.

[11] GAO Tao, LIU Zheng-guang, ZHANG Jun. Redundant discrete wavelet transforms based moving object recognition and tracking[J]. Journal of Systems Engineering and Electronics,2009, 20(5): 1115-1123.

[12] GAO Tao, LIU Zheng-guang, ZHANG Jun. BDWT based moving object recognition and mexico wavelet kernel mean shift tracking[J]. Journal of System Simulation, 2008, 20(19):5236-5239.

[13] 毛燕芬. 交通视频监控中的目标检测与跟踪[D]. 上海: 上海交通大学图书馆, 2005.MAO Yan-fen. Object detection and tracking in traffic video surveillance[D]. Shanghai: Library, Shanghai Jiao Tong University, 2005.

[14] XIAO Mei, HAN Chong-zhao, ZHANG Lei. Moving shadow detection and removal for traffic sequences[J]. International Journal of Automation and Computing, 2007, 4(1): 38-46.

[15] 潘翔. 基于彩色信息和边缘特征的运动阴影检测[J]. 浙江大学学报: 工学版, 2004, 38(4): 389-391.PAN Xiang. Moving shadow detection based on color information and edge features[J]. Journal of Zhejiang University:Engineering Science, 2004, 38(4): 389-391.

[16] 王萍, 王波. 基于小波系数及光学特征的车辆阴影检测[J].天津大学学报, 2008, 41(2): 199-203.WANG Ping, WANG Bo. Vehicle shadow detection based on wavelet coefficients and photometric features[J]. Journal of Tianjin University, 2008, 41(2): 199-203.

[17] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004,60(2): 91-110.

[18] Nummiaro K. An adaptive color-based particle filter[J]. Image and Vision Computing, 2003, 21(1): 99-110.

[19] Arulampalam M S, Maskell S, Gordon N, Clapp T. A tutorial on particle filters for on-line nonlinear/non-gaussian bayesian tracking[J]. IEEE Transactions on Signal Processing, 2002, 50(2):174-188.

[20] Reckleitis I. A particle filter tutorial for mobile robot localization[C]//Proceedings of the IEEE International Conference on Robotics and Automation. New York: IEEE, 2003,42: 1-36.

[21] 宋新, 沈振康, 王平, 等. Mean shift在目标跟踪中的应用[J].系统工程与电子技术, 2007, 29(9): 1405-1409.SONG Xin, SHEN Zhen-kang, WANG Ping, et al. Application of mean shift method in target tracking[J]. Systems Engineering and Electronics, 2007, 29(9): 1405-1409.