一种基于Meanshift算法的目标跟踪改进

朱 钾， 李 化

(太原理工大学 信息工程学院， 山西 晋中 030600)



一种基于Meanshift算法的目标跟踪改进

朱 钾， 李 化

(太原理工大学 信息工程学院， 山西 晋中 030600)

针对遮挡及相似干扰问题， 在Meanshift算法的基础上提出了一种新的改进算法. 该算法有效地将Meanshift算法与Kalman滤波算法结合， 准确确定目标质心位置， 并根据目标质心位置及前一帧搜索窗口边界自适应地调整当前搜索窗口， 使其与目标位置更匹配， 跟踪结果更加准确、 可靠， 同时也减小了环境等因素对算法的影响. 实验对比结果表明， 改进算法具有良好的稳定性和自适应性， 可有效解决大面积遮挡和相似干扰问题.

目标跟踪； Meanshift算法； Kalman滤波算法

0 引 言

目标跟踪包括目标检测和跟踪两部分， 其实质是一个概率问题， 可以通过实时估计来理解跟踪过程. 近几年， 目标跟踪在公共安全、 生产安全、 医疗诊断、 智能交通、 工业、 军事等领域有着广泛的应用前景. 虽然国内外研究者在目标跟踪问题上提出了很多改进算法[1-5]， 但在实际应用中依然存在很多问题， 如背景颜色干扰、 光照强度变化、 目标尺度变化、 外界环境复杂化等直接影响目标特征的提取， 最终导致跟踪失败.

常见的跟踪算法有帧间差分法、 背景差分法、 边缘差分法、 光流法、 Camshift算法[6-8]、 TLD算法[9]等. 本文在Meanshift算法[10]基础上提出了一种新的改进算法， 可根据目标尺度及状态选取部分特征进行跟踪， 并通过质心位置及前一帧搜索窗口边界自适应地调整搜索窗口， 使其与目标更匹配， 同时与Meanshift、 Kalman滤波和Camshift等算法相比， 改进算法具有良好的稳定性、 可靠性及自适应性， 能够有效解决相似干扰及大面积遮挡问题.

1 Meanshift算法

Meanshift算法[10]是一种有效实时跟踪算法， 其本质是在给定条件下进行多次迭代计算， 最终找到与目标相匹配的区域. 该算法跟踪过程如下： ① 目标初始化， 找到初始目标位置并建立目标模型与候选模型； ② 计算目标模型与候选模型的相似度； ③ 使用Meanshift向量计算下一帧目标位置； ④ 依次重复以上步骤.

Meanshift算法原理简单、 计算量较小， 但存在很多问题. 首先， 目标颜色直方图及模型的选取对该算法有很大影响. 若背景颜色存在干扰， 目标模型及候选模型会产生一定的误差， 二者不能准确匹配， 无法正确跟踪目标； 其次， 目标运动速度太快， 超出了Meanshift向量计算范围， 该算法将无法继续跟踪目标； 最后， 目标遇到遮挡或存在相似干扰， 该算法无法自适应地重新构建目标模型及候选模型进行跟踪.

2 Kalman滤波算法

卡尔曼滤波是一种线性递归滤波器， 通常运用于解决最佳估计问题. 其主要分为两个阶段： 预测阶段和更新阶段[11]. 预测阶段包括状态预测和误差协方差预测； 更新阶段包括卡尔曼滤波计算增益系数、 使用增益系数修正和误差协方差的更新[12].

Kalman滤波通过对线性系统建立输入、 输出状态方程， 每次仅需保存该系统上一时刻的状态， 其系统状态方程和测量方程分别为

式中：A表示状态转移矩阵；H表示测量矩阵；Wi，Vi分别是状态噪声矩阵和测量的噪声矩阵， 且均为高斯白噪声.

Kalman滤波算法原理简单、 计算量小、 实时性较强， 通过系统现有状态可预测跟踪目标， 存储量大大减少. 当目标被遮挡、 背景环境较复杂或光照强度发生明显变化时， 都会影响系统的状态转移方程和测量方程， 系统将无法准确确定目标状态， 因此该算法容易发生扩散现象， 导致跟踪精度降低.

3 改进的算法

针对遮挡及相似干扰的情况， 本文在Meanshift算法的基础上， 通过目标质心位置及前一帧搜索窗口边界来确定当前帧搜索窗口， 使其与目标位置更加匹配， 减小了环境等因素对算法的影响， 以便改进算法具有更广泛的应用性. 改进算法具体跟踪过程如下：

1) 目标初始化. 将视频图像从RGB颜色空间转换到YUV颜色空间， 并提取其U分量. 由式(3)， 式(4)计算出目标模型及候选模型的颜色概率分布直方图， 找到第一帧目标初始位置并初始化搜索窗口；

式中： C, Ch为归一化系数， 使得∑qu=1， ∑pu=1， k(‖x‖2)为核函数； m为量化等级； h为核函数的窗宽； x0为假设目标区域中心位置； xi为目标窗口区域像素归一化的位置； y0为当前帧中目标质心位置； δ为Kronecker delta函数；b(x) 为像素在颜色直方图中的索引函数.

2) 计算目标模型与候选模型的相似度ρ， 如式(5)所示.

4) 通过质心估计位置及前一帧搜索窗口边界确定目标搜索窗口， 如式(6)～式(9)所示.

由此可知： 改进算法可有效弥补Menshift与Kalman滤波算法的不足， Meanshift算法计算值可作为Kalman滤波的参数， 并且Kalman滤波的预测值亦作为下一帧中Meanshift算法的初始值， 从而使搜索窗口与目标位置更加匹配. 跟踪过程中若存在遮挡及相似目标干扰， 改进算法可通过目标原颜色概率分布直方图及Kalman滤波算法重新找到原目标的质心位置， 有效解决了相似目标干扰问题， 提高了目标跟踪的稳定性和可靠性.

4 实验结果分析

本文实验在win7 64位系统环境下， Menshift算法、 Camshift算法、 Kalman滤波算法、 帧间差分法及改进的算法均在Matalb2013a下运行， 分别对两个Video中目标实现跟踪， 各Video分辨率均为320×240， 每秒15帧. Video1(共121帧)存在背景颜色干扰和遮挡、 Video2(共225帧， 选取右边的人作为跟踪目标)， 存在与目标相似干扰且遮挡.

4.1 实验跟踪结果

Meanshift算法、 Camshift算法、 TLD算法及改进算法在实验过程中需选取各视频第一帧， 用鼠标选出所要跟踪的目标(用矩形框表示)， 双击矩形框即可开始跟踪， 而Kalman滤波算法及帧间差分法无须选取跟踪对象， 自动进行跟踪. 各算法跟踪结果如图 1～图 3 所示.

图 1 Video1跟踪结果对比Fig.1 Comparison of Video1 tracking results

图 2 Video2跟踪结果对比Fig.2 Comparison of Video2 tracking results

图 3 TID算法跟踪结果对比Fig.3 Comparison of tracking results of TID algorithm

由图 1 可知， 改进算法可选取目标部分特征进行跟踪， 背景颜色干扰和大面积遮挡均不影响跟踪过程的稳定性与可靠性， 而Meanshift算法由于背景颜色干扰， 跟踪过程很不稳定， 遇到树木遮挡不能继续跟踪目标， Camshift及Kalman滤波算法由于背景颜色等干扰完全不能进行有效跟踪， 而帧间差分法在遮挡的情况下能够正常跟踪且具有良好的稳定性， 因此该算法在一定情况下可解决遮挡问题； 由图 2 可知， Video2中由于存在相似目标干扰和遮挡情况， 改进算法在第60帧时产生错误跟踪相似目标， 第129帧时重新跟踪原目标， 因此改进算法可自适应调整继续跟踪原目标， 而Meanshift、 Camshift算法由于环境等因素的影响均不能正常跟踪目标， Kalman滤波算法发生严重扩散现象， 帧间差分法不能有效检测出目标进行跟踪； 由图 3 可知， TLD算法由于遮挡或相似干扰问题均不能完整进行跟踪目标， Video1跟踪68帧后停止跟踪， Video2在跟踪187帧后结束跟踪， 且跟踪过程中目标特征选取不当直接影响跟踪效果.

4.2 算法对比分析

改进算法与Menshift算法、 Kalman滤波算法、 Camshift算法、 帧间差分法及TLD算法对比如下：

1) 与Meanshift算法相比， 改进算法可选择目标部分特征进行跟踪， 不受背景颜色干扰和大面积遮挡的影响， 而Meanshift算法由于背景颜色干扰， 稳定性一般， 虽一段时间内能够跟踪目标， 但遇到遮挡情况将不能继续跟踪目标， 同时目标特征选择较小或相似目标干扰很容易丢失目标.

2) 与 Camshift算法相比， 改进算法将图像从RGB空间转换到YUV空间， 提取其U分量计算颜色概率分布图， 同时根据目标质心位置自适应调整当前搜索窗口， 能够解决背景颜色或相似目标干扰问题， 而Camshift算法将图像从RGB空间转换到HSV空间， 提取其H分量计算颜色概率分布图， 通过对每一帧搜索窗口内像素进行归一化处理来调整窗口大小， 但在遮挡或相似目标干扰情况下， 该算法不能较好地实现跟踪.

3) 与Kalman滤波算法相比， 改进算法将Meanshift算法计算值作为Kalman滤波算法的参数， 提高了Kalman滤波算法跟踪精度， 使跟踪过程更稳定、 可靠， 弥补了Kalman滤波算法的不足， 而Kalman滤波算法受环境因素影响较大， 在实验过中虽在前几帧可以跟踪目标， 但由于扩散现象严重不能达到跟踪目标的效果.

4) 与帧间差分法相比， 改进算法及帧间差分法都不受背景颜色干扰的影响， 能够有效地跟踪目标且能很好地解决遮挡问题. 但在相似干扰及遮挡的情况下， 改进算法受环境等外界因素影响较小虽存在跟踪相似目标的现象， 但不影响跟踪并具有良好的视觉效果， 而帧间差分法却不能有效地检测出目标进行跟踪， 因此改进算法具有一定的优势.

5)与TLD算法相比， 改进算法可选取目标部分特征进行跟踪同时具有良好的稳定性， 可有效地解决遮挡及相似干扰问题， 而TLD算法虽对目标进行不断检测、 学习， 但遇到遮挡及相似目标干扰等情况会终止运行停止跟踪， 且目标特征选取不当直接影响跟踪过程的稳定性.

5 结 语

以上几种算法比较表明， 改进算法将具有更广泛的应用性. 在背景较复杂情况下， 改进算法仍能够继续跟踪目标， 并根据目标质心位置及前一帧搜索窗口边界来确定当前帧搜索窗口， 使其与目标更加匹配， 减小了环境等因素对算法的影响， 可有效解决大面积遮挡及相似干扰问题， 并可根据目标尺度及状态选取部分特征进行跟踪， 且具有良好稳定性. 但当目标被长时间完全遮挡， 改进算法会认为跟踪结束而不再继续跟踪目标， 因此改进算法仍有一定的改进空间， 使跟踪过程更加智能、 可靠. 未来仍需要更加智能的多目标跟踪跟踪， 需要更多的学者融合各方面知识研究能够自主识别、 自主判断、 自主跟踪的智能跟踪算法.

[1]Li Jian, Chen Haifeng, Li Gang, et al. Salient object detection based on meanshift filtering and fusion of colour information[J]. IET Image Processing, 2015, 9(11)： 977-985.

[2]Huang Hai, Sheng Mingwei, Li Yueming, et al. Remote operated vehicle tether disturbances analysis and target tracking control[C]. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014： 103-108.

[3]Xiao Hanzhen, Li Zhijun, Yang Chenguang, et al. RGB-D sensor-based visual target detection and tracking for an intelligent wheelchair robot in indoors environments[J]. International Journal of Control, Automation and Systems, 2015, 13(3)： 521-529.

[4]Zhou Zhiyu, Wu Dichong, Peng Xiaolong, et al. Object Tracking Based on CamShift with Multi-feature Fusion[J]. Journal of Software, 2014, 9(1)： 147-153.

[5]Zhou Zhiping, Zhou Mingzhu, Shi Xiaofeng. Target tracking based on foreground probability[J]. Multimedia Tools and Applications, 2016, 75(6)： 3145-3160.

[6]Xiu Chunbo, Wei Shian, Wan Rongfeng, et al. Cam shift tracking method based on target decomposition[J]. Mathematical Problems in Engineering, 2015： 1-20.

[7]Yan Zouguo, Ling Weiguo, Lü Haidong. A target tracking algorithm based on improved camshift and UKF[J]. Journal of Software Engineering and Applications, 2014, 7(13)： 1065-1073.

[8]Xia Jingxin, Rao Wenming, Huang Wei, et al. Automatic multi-vehicle tracking using video cameras： an improved CAMShift approach[J]. KSCE Journal of Civil Engineering, 2013, 17(6)： 1462-1470.

[9]Kalal Z, Mikolajczyk K, Matas J. Tracking-learning-detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7)： 1409-422.

[10]Du Kai, Ju Yongfeng, Jin Yinli, et al. Meanshift tracking algorithm with adaptive block color histogram[C]. International Conference on Consumer Electronics, Communications and Networks, 2012： 2692-2695.

[11]Chi Jiannan, Qian Chenfei, Zhang Pengyu, et al. A novel ELM based adaptive Kalman filter tracking algorithm[J]. Neurocomputing, 2014, 128： 42-49.

[12]Moussakhani B, Flåm J T, Ramstad T A, et al. On change detection in a Kalman filter based tracking problem[J]. Signal Processing, 2014, 55： 268-276.

An Improved Meanshift Algorithm for Target Tracking

ZHU Jia， LI Hua

(College of Information Engineering, Taiyuan University of Technology, Jinzhong 030600， China)

Aiming at the problem of occlusion and similar interference, a new improved algorithm based on the Meanshift algorithm was proposed. The algorithm effectively combined the Meanshift algorithm with the Kalman filtering algorithm to accurately determine the location of the target centroid. According to the target centroid position and the front frame search window boundary, the current search window boundary is adjusted adaptively to match the target position. In this way，the tracking results are more accurate and reliable, and the influence of the environment and other factors on the algorithm are also reduced. Through the experimental analysis, the improved algorithm which has good stability and adaptability can effectively solve the problem of large area occlusion and similar interference.

target tracking; Meanshift algorithm; Kalman algorithm

1673-3193(2016)06-0633-05

2016-04-22

山西省自然科学基金资助项目(2014011019-1)

朱 钾(1991-)， 男， 硕士生， 主要从事无线传感器目标跟踪的研究.

TP391

A

10.3969/j.issn.1673-3193.2016.06.014