一种改进的Mean-Shift 实时车辆跟踪算法

张 彤，马延柯，首照宇

(桂林电子科技大学 a. 机电工程学院;b. 认知无线电与信息处理省部共建教育部重点实验室，广西 桂林541004)

在智能车流量统计系统［1］中，对于车辆的精确快速跟踪是交通参数提取、交通事件处理的一项关键技术。车辆的不规律运动影响了跟踪的效率，近年来，众多学者对此展开了深入的研究，并提出了一些较好的方法［2－4］，其中Mean－Shift 跟踪方法自提出以来就备受关注。Mean－Shift 跟踪算法的目标模型选取核函数空间加权的颜色直方图，采用Bhattacharrya系数作为相似性度量，通过Mean－Shift 迭代搜寻目标位置。其具有计算负荷小、调节参数少等优点，但是存在无法估计目标的尺度方向，对变速运动目标的跟踪效果差的问题［5］。于此，在此算法理论的基础上提出了一些改进。文献［6－8］通过特征点匹配方法，结合整体与局部模型各自优点，计算连续帧间相关特征点的仿射变换系数得到尺度与方向信息，但是特征点提取、描述与匹配可能影响实时性;文献［9］通过权重图法，利用像素点权重的协方差矩阵计算尺度和方向信息，计算量小，效果较好，但易受到光照等因素影响;文献［10－11］通过尺度法，使用图像金字塔或全局概率密度搜索提高目标定位能力，这里尺度分别指图像尺度和带宽尺度，但缺点是易受相似目标干扰;文献［12］通过预测法，结合Kalman 滤波或者粒子滤波算法，增加目标搜索能力，但对非线性、非高斯分布的状态变量的预测有一定局限，对目标运动模型有一定要求。现有的预测方法有很多，神经网络法、线性预测法、马尔科夫链预测法等，它们分别具有各自的特点，适用于不同的场合。理论上样本或者先验知识的积累决定了这几种方法的预测精度。然而在工程应用中，这种积累是难以实现的。在传统均值飘移算法基础上，通过寻找搜索区域与当前目标所在真实位置区域尽可能的重叠，从而尽快地搜索出当前目标位置。据此，本文提出一种基于时间序列预测法的运动历史Mean－Shift 跟踪方法，首先通过运动历史信息加权图像来记录前几帧的运动目标位置，根据其运动属性来预测当前帧目标所在位置，然后选定该预测中心位置来进行搜索，从而减少迭代次数，提高智能车流量统计系统的实时性和鲁棒性。实验结果表明，该方法取得了良好的效果。

1 Mean－Shift 跟踪算法

1.1 Mean-Shift 算法

Mean－Shift 算法的原理是在核密度估计的基础上，在一组数据的密度分布中采用步长迭代寻找局部极值点，步长具有自适应性。属于一种无参非监督特征空间分析方法。计算机视觉处理中，通常都是在多维空间中对数来分析处理，在假设d 维欧式空间情况下，其中有n 个样本xi∈Rd，i=1，2，…，n，x 表示该空间中的一个点，可以得到Rd空间中的点x 的密度概率估计值为

根据核函数公式，若采用H=h2I，对应的Mean－Shift 矢量为

根据经典算法的计算公式，密度梯度的估计相当于核密度估计的梯度，有g(x)=－k'(x)。m(x)通常与概率密度速率最大的方向重叠，经过若干次迭代可以收敛至概率密度的局部极值点。

1.2 Mean-Shift 跟踪目标模型描述

Mean－Shift 跟踪算法的基本原理是首先建立目标模型，再采用匹配度函数来衡量目标相似度，通过密度估计方法来解决搜索匹配度的局部极值问题，通过Mean－Shift 迭代来定位其局部最大值。

1.2.1 初始目标模型的建立

在视频序列中，目标特征是通过灰度或颜色分量来进行描述的。通过一定方法筛选出要跟踪的目标区域，该区域为一矩形，d0为其中心，h 设为边长，把选定目标区域颜色空间均匀分成m 个特征区间，通过此选定搜索域全部特征值的概率值来表述目标模型，通过直方图估计法得到的特征值v 的概率核密度qv为

式中:xj表示该选定搜索域中第j 个像素值坐标;k(·2)表示核函数;C 为一个归一化常量系数;函数b 和δ 的构造是为了分析判断第j 个像素颜色灰度值是否与对应特征值v 匹配;

1.2.2 当前目标模型的建立

对于当前帧图像中可能会出现搜索目标区域描述为待选目标模型，在当前帧目标搜索区域中，第v 个特征概率的表达式为

式中:y0表示当前帧搜索区域的中心坐标;Ch是一个归一化常系数，且，使得=1，m 表示特征个数。

1.2.3 特征相似性函数

用Bhattacharyya 系数来衡量初始目标模型和当前目标模型的相似程度，如果值越大，表示相似程度越高，也即当前目标与初始目标最相似。

Bhattacharyya 系数定义为

两个目标模型的相似程度跟ρ(y)函数值成正比例关系，相似性函数最大的当前帧区域就是当前目标所在区域。

1.2.4 跟踪步骤

设置视频序列，已知初始帧的目标模型{q^v}v=1，2，…，m，并给出t－1 时刻的目标位置d0，对t 帧图像进行目标搜索过程如图1 所示。

图1 Mean－Shift 跟踪步骤

2 运动历史预测和优化的Mean－Shift跟踪算法

传统的均值飘移跟踪算法是以前一帧运动目标的所在位置为依据进行搜索，搜索区域与当前目标所在区域部分重合，搜索区域的大小对搜索时间有一定的影响，如果从前一帧的运动目标位置开始搜索，将会通过多次迭代才能收敛于当前帧目标所在位置，从而造成算法计算量大，实时性差。在实际应用中，可以通过一定的方法减少迭代次数，从而减少算法计算量，提高系统实时性，实现对多个目标的实时跟踪。

2.1 运动历史信息的提取

运动历史信息的提取技术在虚拟现实中备受关注，同时在智能监控领域也被广泛应用［13］。在运动目标的跟踪中，是对下一帧运动目标位置进行有效预测的关键，其基本思路是，提取每帧图像对应的不同时刻并将连续图像进行加权叠加，时间序列图像通过浮点数来表达，这是它的核心理论。通过将当前视频序列时间戳转换为浮点矩阵后进行目标运动信息加权图像更新。随着时间的推进，当前帧信息加权图像总是具有最大灰度值(最亮)，而过去帧信息加权在当前运动信息图像中的影响将会越来越弱(图像变暗);当过去时间序列与当前时间序列的间隔超过设置阈值时，其影响将被清为零。

系统通过一定的目标检测算法比如背景差、帧差等提取出运动车辆目标，但是系统只能获得运动发生的位置，而其他运动历史信息并未知，然而运动历史信息加权图像(motion history－weighted images)能够描述更多的运动属性，例如运动的方向［14］等。

运动历史信息图像更新公式如下

式中:τ 是当前系统时间，δ 表示运动历史图所能表示的时间片段。图2a 是一段视频运动序列中的第31 帧图像;图2b 是该序列帧图像中的运动车辆所获取的经典运动历史信息加权图像，可见此信息图像是一个亮度从黑到白的灰度图，从暗到明的方向表示运动的方向。

图2 运动历史信息图

提取出一定时间序列的运动历史加权图像后，将3×3 的Sobel 算子应用到图像上［15］，并对其水平、垂直方向求偏导，从而得到特征空间像素点(x，y)上的梯度sx(x，y)、sy(x，y)，据此进一步计算梯度方向Orient(x，y)和幅值M(x，y)分别为

对其梯度图进行运动分割，先计算每个分割区域的运动方向，再计算选择区域内的整个运动方向，并且返回［0，360］之间的角度值。对每一帧图像进行处理时，对其梯度方向进行计算，无论是全局的还是局部的都需要对该区域运动历史信息图像进行标准化处理，并且对其权值进行规则化，以使运动历史图像中最近的时间序列运动信息具有最大影响值。计算公式为

2.2 优化的Mean-Shift 跟踪算法

2.2.1 预测原理

运动历史信息加权图像记录了运动车辆的位置、运动方向、面积、速度等信息。据此运动历史信息对下一帧运动目标状态进行最优估计，预测具有定位准确、可靠性高等特点。假设系统状态Xk为一个4×Nk维向量，目标预测方程［16］为

式中:Xk表示依据k－1 时刻的状态对k 时刻状态的估计值;Xk－1为k－1 时刻最优状态估计值;Uk为k 时刻的控制量;Φk/k－1为状态转移矩阵。

根据k 时刻的提取值和估计值，得出k 时刻的最优预测值为

式中:Hk为观测矩阵。

然后计算预测位置最接近的目标

计算目标j 的匹配度L(i，j')，根据匹配度函数，对检测目标进行匹配。预先设定一阈值T，通常取为0.006 ～0.060。

2.2.2 优化后的方法具体步骤:

对于一个视频序列，已知初始帧的目标模型{q^v}v=1，2，…，m，并给出t－1 时刻的目标位置d0，对t 帧图像进行目标搜索流程图如图3 所示。

图3 目标搜索流程图

3 实验结果分析

为了验证本文算法的有效性，对两组方向速度改变(变道)车辆进行了实验，并与Mean－Shift 方法进行了比较。

车辆方向速度改变(变道)情况的跟踪结果如图4 所示，图4a 为第529 帧变道前车辆位置图，方框标记的白色车辆处在左二车道，准备变道;图4b 为对应的运动历史信息加权图像，依据此图像记录的车辆运动属性进行估计下一帧运动位置;图4c 为采用本文方法实验的目标车辆变道后跟踪结果，变道后的白色车辆处在右二车道;图4d 为传统Mean－Shift 方法对目标车辆的跟踪结果。图5a 为第2 027 帧目标车辆位置图，方框标记的灰色车辆处在右一车道，准备变道;图5b 为对应的运动历史信息加权图像;图5c 为采用本文方法对目标车辆的跟踪结果;图5d 为传统方法对目标车辆的实验结果，右二车道方框标记的灰色车辆为图5a 中变道的车辆。从图中结果可以看出，本文方法能在车辆运动属性发生变化情况下准确跟踪，效果明显比传统方法好。

图4 第529 帧的变道车辆跟踪结果

图5 第2 027 帧的变道车辆跟踪结果

图6 中针对右二车道进行分析，图6a 表示运动目标所在原始位置，图6b 表示当前帧要检测运动目标位置，根据运动历史属性信息，在搜索之前预测出当前帧运动目标可能在矩形框附近，然后在矩形框附近搜索，预测下一帧车辆目标位置，如果利用传统的均值飘移算法，开始搜索位置定位在原始图像中矩形框，一般情况下要通过5 次左右的迭代才能收敛于当前帧中的矩形框位置，而且系统很难实现短时间内同时对多个目标进行准确跟踪，与传统方法相比，本文算法迭代次数减少，收敛速度加快，提高了系统的实时性。

图6 实验目标位置图

图7 比对了传统算法与改进算法在监控区域内的迭代次数，对一辆车进行跟踪时，传统算法需要2 ～3 次迭代才能完成一次搜索，而本文改进的跟踪算法为平均1 次，提高了监控系统的实时性。

图7 传统算法与本文算法迭代次数对比图

4 小结

本文针对传统Mean－Shift 算法存在无法有效地估计车辆目标方向、变速运动车辆目标的缺陷进行改进，在Mean－Shift迭代搜索的基础上增加了预测功能，提出了改进算法。在本实验中，通过记录的运动历史属性信息来构建数学模型，并对下一帧位置进行预测，包括方向、速度等，从而避免因车辆的变道、提速等不规律运动行为而引起的错跟、丢跟。实验表明，该预测算法能为Mean－Shift 提供帧间相似密度低的区域目标的锁定能力，以及对视频帧的高效处理能力，减轻处理器的负担。下一步还将对多个样本进行训练，并通过算法学习来进一步提高车辆跟踪算法的自适应性和高效性。实现对复杂视频、复杂场景的有效分析。

［1］WANG Guolin，XIAO Deyun，GU J. Review on vehicle detection based on video for traffic surveillance［C］//Proc. IEEE International Conference on Automation and Logistics. Piscataway，USA:IEEE Press，2008:2961－2966.

［2］SUBUDHI B N，NANDA P K，GHOSH A. A change information based fast algorithm for video object detection and tracking［J］.IEEE Trans. Circuits and Systems for Video Technology，2011，21(7):993－1004.

［3］JAZAYERI A，CAI Hongyuan，JIANG Yuzheng. Vehicle detection and tracking in car video based on motion model［J］.IEEE Trans.Intelligent Transportation Systems，2011，12(2):583－595.

［4］郑可飚，黄文清，张佐理，等. 运动目标跟踪系统的遮挡问题处理［J］.计算机工程与设计，2009，30(11):2816－2818.

［5］顾幸方，茅耀斌，李秋洁.基于Mean－Shift 的视觉目标跟踪算法综述［J］.计算机科学，2012，39(12):16－17.

［6］康一梅，谢晚冬，胡江，等. 目标尺度自适应的Mean－Shift 跟踪算法［J］.兵工学报，2011，32(2):210－216.

［7］ZHAO Chuan，KNIGHT A，REID I. Target tracking using meanshift and affine structure［C］//Proc. 2008 International Conference on Pattern Recognition.［S.l.］:IEEE Press，2008:1－5.

［8］CHEN Aihua，ZHU Ming，WANG Yanhua，et al. Mean－Shift tracking combining SIFT［C］//Proc. International Conference on Signal Processing.［S.l.］:IEEE Press，2008:1532－1535.

［9］NING Jifeng，ZHANG Lei，ZHANG D，et al. Scale and orientation adaptive Mean Shift tracking［J］.IET Computer Vision，2012，6(1):52－61.

［10］LI Shuxiao，CHANG Hongxing，ZHU Chengfei. Adaptive pyramid mean shift for global real－time visual tracking［J］.Image and Vision Computing，2010，28(3):424－437.

［11］LI Liangfu，FENG Zuren，CHEN Weidong，et al. A coarse－to－fine kernel matching approach for mean－shift based visual tracking［J］.Opto－Electronics Review，2009，17(1):65－71.

［12］李弟平，邹北骥，傅自刚. 快速运动目标的Mean－Shift 的高速运动目标跟踪［J］.小型微型计算机系统，2011，32(8):1665－1668.

［13］DAVIS J W. Hierarchical motion history images for recognizing human motion［EB/OL］.［2014－12－20］.http://wenku.baidu.com/view/fd02140df12d2af90342e605.html.

［14］BRADSKI G R，DAVIS J W. Motion segmentation and pose recognition with motion history gradients［J］.Machine Vision and Applications，2002(13):174－184.

［15］刘军学，屈桢深，任行行，等.基于改进运动历史图像的多运动目标实时跟踪［J］.计算机应用，2008，28(3):199－200.

［16］胡学刚，刘忠振. 基于高斯模型和卡尔曼预测的检测和跟踪［J］.计算机工程与设计，2013，34(1):247－248.