UKF与Mean shift算法相结合的实时目标跟踪
刘献如，蔡自兴
(中南大学 信息科学与工程学院，湖南 长沙，410083)
摘要：针对Mean shift (即MS)算法理论上的不足以及跟踪目标时的邻域跟踪局限性，提出将Mean shift算法与尺度无迹卡尔曼滤波器(Scaled unscented Kalman filter, SUKF)相结合的实时目标跟踪算法。该算法利用尺度无迹卡尔曼滤波器获取Mean shift算法的初始位置，然后，利用Mean shift算法获取跟踪位置。通过分析跟踪区域内横纵向直线的统计变化获取目标的尺度变化，依此自适应调节Mean shift跟踪算法中核函数带宽，并对高速公路上快速运动的车辆进行跟踪实验。研究结果表明：该算法与固定核窗宽Mean shift算法相比，对目标跟踪更准确；SUKF滤波使MS的迭代次数减少，跟踪的实时性提高；核窗宽自适应调节可使跟踪误差降低到50%以下。
关键词：SUKF；Mean shift算法；自适应尺度；目标跟踪
中图分类号：TP242 文献标志码：A 文章编号：1672-7207(2011)05-1338-06
Real time object tracking using Mean shift combined UKF
LIU Xian-ru, CAI Zi-xing
(School of Information Science and Engineering, Central South University, Changsha 410083, China)
Abstract: Aiming at theoretic and neighborhood tracking limitation of Mean shift (MS), a real-time target tracking algorithm combined with Mean shift and scaled unscented Kalman filter (SUKF) was proposed. The algorithm firstly used SUKF to estimate the starting position of the Mean shift in every frame. And then the Mean shift was used to locate the target position. The target scale changing was estimated by analyzing the statistical changes of the horizontal and vertical lines in the tracking region. According to the estimated scale, the kernel-band width changed adaptively for Mean shift object tracking. Experiments on the highway vehicle tracking were done. The results show that the proposed tracking algorithm can locate the target more accurately than the traditional Mean shift; the SUKF can reduce the iteration times of MS and improve the real time of tracking. Adaptive adjustment of kernel-band width further can reduce the tracking errors to less than 50% of the MS algorithms.
Key words: SUKF; Mean shift, adaptively scale; object tracking
Mean shift(简称为MS)算法是一种密度梯度的无参估计方法，于1975年由Fukunage等[1]提出。1995年，Cheng[2]重新研究了Mean shift，提出了更一般的表达式并预示该算法在聚类和全局优化方面的巨大应用潜力。Comaniciu等[3]对Mean shift在图像分割和跟踪中的使用进行了论述。Mean shift广泛应用于目标跟踪[4-6]、图像分割[7]、聚类[8]分析等领域。朱胜利 等[9]将Mean shift算法引入卡尔曼滤波(Kalman filter，简称为KF)，提高了算法的速度，但是，KF只适用于线性系统。近年来，有研究将粒子滤波和Mean shift相结合应用于目标跟踪[10]，但是，粒子滤波本身的复杂计算降低了跟踪的实时性。Mean shift应用于目标跟踪具有一些优良性能，如：算法实时性较好；参数单一，可将其作为一个功能模块与其他算法集成；采用归一化核函数直方图建模，对边缘遮挡、目标形变以及背景变化不敏感。但是，也存在一些不足，如：由于Mean shift在目标起始点位置进行泰勒展开，即Mean shift是在起始位置寻找目标，当目标运动较快时，算法跟踪效果将会受到影响。采用滤法算法可解决这一问题，即首先对目标的状态空间进行滤波，Mean shift算法在滤波估计位置进行迭代跟踪。针对跟踪系统的非线性及实时性要求，本文作者提出将Mean shift与尺度UKF滤波器(SUKF)结合起来实现对快速运动目标的实时跟踪与定位。在Mean shift算法中核窗宽不但决定了参与迭代的样本数量，也反映了跟踪窗口的大小。由于运动目标的尺度变化，固定不变的核窗宽常导致Mean shift迭代次数增加或跟踪丢失。通过对前一帧跟踪窗口中目标直线特征的分析，结合SUKF滤波，估计当前帧中目标尺度，并依此自适应调节核窗宽，并将提出的算法应用于高速公路车辆跟踪实验。
1 UKF滤波
在“近似任意非线性函数的概率分布比近似非线性函数更容易”的思想指导下，Julier等[11]提出了基于Unscented变换的卡尔曼滤波，即UKF。在确保随机向量均值和协方差不变的前提下，选择一组 Sigma 样点集，每个 Sigma 点通过非线性变换，即Unscented 变换(U变换)，由变换后样点的统计量来估计随机向量通过非线性变换后的均值及方差，避免了线性化所带来的误差，且不需要计算非线性方程的Jacobi 矩阵，比EKF类算法具有更强的稳定性[12]。Mihaylova等[13]对UKF与PF的性能进行了分析实验，结果表明：UKF的滤波性能与PF的滤波性能基本相同，但是，UKF的计算时间比PF的少。
1.1 UKF建模
一个普通的状态空间模型可分成2部分，即状态转移模型和状态观测模型。跟踪系统的状态即目标的状态，观测则为序列图像；目标的状态包括目标中心点坐标、速度、尺度，同时考虑到目标的速度发生变化，设其加速度a是一随机量，满足
。令目标状态向量为：
。其中：x和y表示目标中心点的坐标；
和
分别表示x和y的导数，即目标的速度；
表示目标从k-1时刻到k时刻的核函数带宽变化。观测量
(其中xc(k)和yc(k)表示目标中心处的观测值)。UKF的状态转移模型和观测分别为：
(1)
(2)
其中：
=[1, 0, t, 0, 0; 0, 1, 0, t, 0; 0, 0, 1, 0, 0; 0, 0, 0, 1, 0; 0, 0, 0, 0, γ]；
；
；R=[1, 0, 0, 0, 0; 0, 1, 0, 0, 0]；wk和vk分别为状态转移与观测模型的高斯白噪声；t为相邻帧时间间隔，取t=1；γ为目标的尺度因子，由目标区域内目标特征的尺度变化确定其大小。设xc和yc为目标中心的坐标，其初始化由手动选取目标区域完成，取X(0)=(xc, yc, 0, 0, 1)。
1.2 UKF滤波
UKF算法中的Unscented变换(U变换)是其算法的核心，也是实现对非线性进行状态估计的重要手段。尺度U变换的SUKF(Scaled unscented Kalman filter)比UKF具有更好的滤波性能[14]，且当状态的维数高于3时不存在Sigma点“爆炸”等问题，由式(1)和(2)可知：状态空间的维数为5，因此，采用SUKF算法对状态空间进行滤波估计。假设L维状态向量X在k-1时刻的状态均值和方差为
和P(k-1)，SUKF的状态向量为X与噪声向量合成的扩增向量
，其相应的Sigma点向量为
。SUKF滤波估计具体实现步骤如下。
(1) 初始化：
(3)
其中：Pv为状态转移噪声协方差；Pn为观测噪声。
(2) 利用式(4)计算Sigma点：
,
(4)
系数
；k=3-L；
为待选参数，0＜ ≤1×10-4。
(3) 时间更新。将Sigma点代入状态转移和观测方程式(5)和(6)，并通过式(7)计算此时状态向量的均值：
(5)
(6)
(7)
其中：F为状态转移方程；H为观测方程；
为求均值的权系数，
；
；i=1, …, 2L。
(4) 观测更新方程。将式(5)和(6)代入式(8)和(9)，并利用式(10)计算增益：
(8)
(9)
(10)
参数
≥0，这里取=0；
(i=1, …, 2L)
将增益代入式(11)和(12)，对状态向量的均值和方差进行更新。
(11)
(12)
通过SUKF滤波，预测快速运动目标的位置，由于物体运动的不确定性，故其运动模型也具有不确性，因此，在跟踪起动以后，将每次Mean shift中定位出来的目标位置与上次的目标位置进行比较，更新并校正SUKF的状态模型。
2 Mean shift跟踪
Mean shift算法又常被称为均值漂移算法，它对跟踪邻域目标具有较好的性能，但是，当目标快速运动时，该算法容易出现跟丢的现象。因此，引入SUKF算法对目标状态进行滤波估计，并将估计的位置作为Mean shift算法迭代跟踪起始位置。
2.1 目标描述
将颜色核直方图作为目标特征的描述，假定目标模型和候选目标特征分别表示为：
和
。其中：y为候选目标区域的中心
位置，且
，
；m为核直方图的级数。为了得到一个相对于空间位置y平滑的相似函数，目标模型的特征分布表示为：
，相应的候选目标的特征分布为：
。其中：δ(?)为Kronecker delta函数；
i=1,…,n为归一化的目标模型像素位置，归一化后目标模型中心像素的位置为0；b: R2→{1,…,m}为像素点到像素特征的映射；C为归一化常数；Ch为归一化常数；nh为候选目标区域中的像素总数；k(·)为核函数；h为带宽。
2.2 相似性函数
目标模型与候选目标的相似性用Bhattacharyya系数来度量，定义为
，为了使
最大，以SUKF预测的位置作为当前帧的搜索窗口中位置y0，在y0邻域内寻找局部最优目标位置y1。对上式在p(y0)处进行泰勒展开，相似性函数可近似为：
(13)
其中：
，由于式(13)中第1项独立于y，所以，要使式(13)最大化，也就是使式(13)的第2项最大化，则第2项最大化可通过Mean shift 算法迭代实现，使核中心点不断从起始点往新的y1方向移动。
(14)
其中：
。
2.3 算法迭代过程
Mean shift 算法在每一帧的定位的迭代起始位置为SUKF算法滤波估计的位置。Mean shift算法定位目标实现如下。
(1) 初始化。y0=xsukf，计算{pu(y0)}u=1,…,m和
。
(2) 根据式(5)计算权重{wi}i=1,m。
(3) 根据式(6)计算y1，并代入下式：
(4) 若
＜
，则
，重新计算。
(5) 若
，则停止迭代。
(6) 否则，y0←y1并转至步骤(2)。
在Mean shift跟踪过程中，将每次找到位置与先前若干帧的位置进行比较，估计目标的速度，并依此更新SUKF的状态模型。将SUKF与Mean shift算法两者结合起来，形成一个闭环跟踪系统，可以对快速运动目标进行实时而有效地跟踪。
3 自适应尺度
Comaniciu等[3-4]采用3种不同尺度在当前帧中进行迭代运算，比较它们所得到的Bhattachayya系数，认为其中具有最大Bhattacharyya系数的尺度是最优的尺度。该方法具有盲目性。彭宁嵩等[15]采用匹配相邻帧的目标区域内角点，求仿射变换模型参数获取目标伸缩系数。但是，该方法角点的获取以及匹配相对于目标来说计算量较大，不适合实时性要求高的场合。
针对上述问题，本文作者提出一种简单快速的目标尺度估计方法。该方法采用相邻两帧中水平直线和垂直直线的长度变化估计目标的尺度变化，并依此调节核函数带宽，实现自适应核窗宽选取。其步骤是：首先，采用Sobel水平直线检测算子{1, 2, 1; 0, 0, 0; -1, -2, -1}和垂直检测算子{1, 0, -1; 2, 0, -2; 1, 0, -1}检测当前窗口中所有的水平直线集合{lk,i}和{vk,i} (i=1, 2, …, m)。其中：下标k表示时刻；i表示第i条直线。然后，计算它们与前一帧的平均长度之比；最后，采用式(7)获取目标的尺度变化因子γ：
(15)
其中：
和
分别表示水平直线与垂直直线伸缩因子，
；
； n′与
m′分别表示k－1时刻的直线数目；
为直线的模，即直线的长度。将依此求得的尺度因子代入式(13)更新核函数带宽。
4 实验结果与分析
为了验证本研究方法的有效性，通过采集高速公路一段视频进行跟踪测试。所用微机的内存为1 G，CPU容量为1.8 G，双核，编程语言为Matlab。
视频参数如下：采集速率25帧/s，图像格式为位图，大小为192×240。进行实验时，将图像从红绿蓝彩色空间映射到特征空间，并量化为16×16×16 个特征级。目标的初始化由手动完成。采用上述提出算法(简称SUKF-MS算法)对视频中的白色轿车进行实时跟踪，并与固定尺度Mean shift算法跟踪结果进行比较。图1所示为从其中随机抽取第40，48，60，66，72，80和89帧的跟踪结果，其中：白色框为SUKF-MS的跟踪结果，黑色框为传统MS算法的跟踪结果。从图1可见：在跟踪初始阶段，传统MS与SUKF-MS的跟踪框基本上重合，但是，随着目标的变化和快速离去，SUKF-MS算法的优越性逐渐显示出来；MS跟踪的目标不再位于跟踪框中心，即出现了较大的跟踪误差，而SUKF-MS保留着目标位置于跟踪框中心。
为了比较2种算法在时间上的性能，分别对它们的Mean shift迭代次数和每一帧定位目标所用时间进行比较，实验结果分别如图2和图3所示。从图2可看出：SUKF-MS的每帧的迭代次数小于或等于传统的MS的迭代次数。
由于文中所述算法加入了SUKF，相应地会增加计算时间，但是，从图3可以看出：SUKF-MS每帧的定位时间都要比MS的小。这是由于SUKF的引入减少了MS的迭代次数，使得算法整体上的计算时间比MS的小，这也体现了SUKF滤波较好的滤波性能。
SUKF-MS和MS算法两者的平均迭代次数、定位时间及定位平均相对误差见表1。从表1可知：SUKF- MS每帧的迭代次数减少为MS算法的70%左右，这也使得SUKF-MS算法每帧搜集目标的时间大为减少；同时，其定位误差减少为MS算法的50%(跟踪误差计算项中的目标真实位置是通过手动得到的，由于X方向的坐标变化不大，故只对Y方向平均每帧跟踪
图1 传统MS 与文中方法跟踪效果比较
Fig.1 Tracking results comparison between MS and proposed algorithm
图2 MS 与UKF-MS的迭代次数比较
Fig.2 Iternation times comparison between MS and SUKF-MS
图3 MS与UKF-MS每帧的目标定位时间比较
Fig.3 Object location time for each frame between MS and SUKF-MS
表1 MS与SUKF-MS的跟踪性能比较
Table 1 Comparison of MS and SUKF-MS tracking performance
误差进行分析)。
5 结论
(1) Mean shift由于其实时性好且具有一定的抗干扰能力，常用于复杂环境的目标跟踪。但是，它存在理论上的缺陷，导致其跟踪快速大范围内运动目标容易丢失。而尺度UKF滤波器(即SUKF)具有较好滤波性能，实现简单且较快，可以为Mean shift算法估计目标的跟踪迭代起始位置。将SUKF与Mean shift算法两者结合起来，可实现对快速运动目标的实时跟踪。
(2) 由于运动目标尺度变化要求核函数带宽相应地进行调整，通过对跟踪窗口区域内目标水平与垂直直线特征进行统计平均分析，估计目标尺度的变化，并依此自适应调节核函数带宽和跟踪窗口的大小。这样，对于逐渐变小的目标跟踪可以减少搜索时间，而对于逐渐增大的目标可以避免目标丢失。
(3) SUKF滤波方法同样存在随着维数的增加，Sigma点传播的计算时间会增大的问题。其中有些Sigma点对最后的均值和方差产生的影响很小，可以通过分析这些点的特征，在传播前进行相应删除，从而提高SUKF的滤波速度而不影响其滤波性能，以便进一步提高跟踪系统的实时性。
参考文献：
[1] Fukunage K, Hostetler L D. The estimation of the gradient of a density function with application in pattern recognition[J]. IEEE Transaction on Information Theory, 1975, 21(1): 32-40.
[2] Cheng Y. Mean shift, mode seeking and clustering[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1995, 17(8): 790-799.
[3] Comaniciu D, Meer P. Mean shift analysis and applications[C]// Proceeding of the IEEE International Conference on Computer Vision. Kerkyra, Greece, 1999: 1197-1203.
[4] Comaniciu D, Ramesh V, Meer P. Kernel-based object tracking[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2003, 25(5): 564-577.
[5] 文志强, 蔡自兴. 目标跟踪中巴氏系数误差的分析及其消除方法[J]. 计算机学报, 2008, 31(7): 1165-1171.
WEN Zhi-qiang, CAI Zi-xing, Errors of Bhattacharyya coefficient and its reduction in object tracking[J]. Journal of Computer, 2008, 31(7): 1165-1171.
[6] 李培华. 一种改进的Mean shift跟踪算法[J]. 自动化学报, 2007, 33(4): 347-354.
LI Pei-hua. An improved Mean shift algorithm for object tracking[J]. Acta Automatica Sinica, 2007, 33(4): 347-354.
[7] Unnikrishnan R,Pantofaru C,Hebert M.Toward objective evaluation of image segmentation algorithms[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(6): 929-944.
[8] Wu K, Yang M. Mean shift-based clustering[J]. Pattern Recognition, 2007, 40(11): 3035-3052.
[9] 朱胜利, 朱善安, 李旭超. 快速运动目标的Mean shift跟踪算法[J]. 光电工程, 2006, 33(5): 66-70.
ZHU Sheng-li, ZHU Shan-an, LI Xu-chao. Algorithm for tracking of fast motion objects with Mean shift[J]. Opto-Electronic Engineering, 2006, 33(5): 66-70.
[10] Shan C, Tan T, Wei Y. Real-time hand tracking using a mean shift embedded particle filter[J]. Pattern Recognition, 2007, 40(7): 1958-1970.
[11] Julier S J, Uhlmann J K, Durrant-Whyte H F. A new method for the nonlinear transformation of means and covariance in filters and estimators[J]. IEEE Transaction on Automatic Control, 2000, 45(3): 477-482.
[12] Daum F. Nonlinear filters: Beyond the Kalman filter[J]. IEEE Aerospace and Electronic Systems Magazine, 2005, 20(8): 57-69.
[13] Mihaylova L, Boel R, Hegyi A. An unscented Kalman filter for freeway traffic estimation[C]//Proceedings of 11st IFAC Symposium on Control in Transportation Systems. Netherlands, 2006: 31-36.
[14] Julier S J. The scaled unscented transformation[C]//Proceeding of the American Control Conference. Anchorage, USA, 2002: 4555-4559.
[15] 彭宁嵩, 杨杰, 刘志, 等. Mean shift跟踪算法中核核函数窗宽的自动选取[J]. 软件学报, 2005, 16(9): 1542-1550.
PENG Ning-song, YANG Jie, LIU Zhi, et al. Automatic selection of Kernel-Bandwidth for Mean-shift object tracking[J]. Journal of Software, 2005, 16(9): 1542-1550.
(编辑 陈灿华)
收稿日期：2010-05-11；修回日期：2010-07-25
基金项目：国家自然科学基金重大专项项目(90820302)；国家自然科学基金面上项目(60805027)；国家博士点基金资助项目(200805330005)
通信作者：刘献如(1977-)，女，湖南娄底人，博士研究生，从事计算机视觉等研究；电话：13548986493；E-mail:lxrcsu@163.com
