Meanshift tracking algorithm based on SLIC superpixel
-
摘要: 为了增强目标跟踪算法在被跟踪目标发生运动位移、遮挡、形变、相似物体干扰等情况下的鲁棒性,提出利用超像素构建目标外观模型,将外观模型与候选区域进行匹配,获取候选区域当中目标超像素,并用Meanshift算法确定目标中心点的跟踪算法。仿真实验选取Benchmark库当中在运动位移、遮挡、形变、相似物体干扰方面具有代表性的视频Girl和FaceOcc1。该算法在视频Girl中的跟踪成功率和跟踪精度为0.601、0.856,比对比实验的经典算法当中跟踪效果最好的KCF算法的成功率和精度分别高0.059和0.084;在视频FaceOcc1中跟踪成功率和精度仅次于KCF。表明该跟踪算法在受到相似物体干扰和目标遮挡时具有良好的鲁棒性。
-
关键词:
- 超像素 /
- 颜色直方图 /
- Meanshift算法 /
- 外观模型 /
- 跟踪
Abstract: In order to enhance robustness of target tracking algorithm under conditions of motion displacement, occlusion, deformation and similar object disturbance, it is proposed to construct target appearance model by using super pixel, and match appearance model with candidate region to obtain candidate region target super pixel, and use Meanshift algorithm to determine target center point tracking algorithm. Simulation experiments select representative of video Girl and FaceOcc1 from Benchmark library, which represent video scene in terms of movement displacement, occlusion, deformation, interference of similar objects. Tracking success rate and tracking accuracy of algorithm are 0.601 and 0.856 in video Girl, and success rate and accuracy of KCF algorithm with best tracking performance are higher than normal algorithm of 0.059 and 0.084 respectively. In video FaceOcc1, tracking success rate and accuracy of proposed algorithm only ranked second to KCF, suggesting a fine robustness even when target is blocked or interfered by analogues.-
Keywords:
- superpixel /
- color histgram /
- meanshift /
- appearance model /
- tracking
-
引言
目标跟踪是计算机视觉领域的重要研究内容,广泛应用于安防监控、人机交互、智慧城市以及军事领域。在近年的研究中,新的跟踪算法不断涌现,跟踪效果也不断提高。然而由于受到光照、遮挡等环境因素的影响,实现稳定目标的跟踪仍然是跟踪算法面临的主要挑战。Liu等人[1]提出对视频帧中目标区域的超像素进行在线学习和聚类的方式构建模型特征库,实现目标跟踪;Fan等人[2]提出利用目标局部区域内超像素之间的结构信息来进行目标跟踪。这两种方法利用超像素在目标受到光照变化、遮挡等因素影响时具有更强的鲁棒性的优点,克服了超像素在连续视频帧中分割不稳定及前后帧同区域超像素之间的关系难以描述的缺点,实现了目标的稳定跟踪。但是,第一种方法需要大量的样本学习准确构建目标模型特征库,跟踪效率低,难以满足实时需求;第二种方法由于超像素的重心会随着光照、形变等因素的影响而发生漂移,造成局部区域内超像素的结构信息不稳定,难以实现非刚性目标的跟踪。
针对以上两种方法的缺陷,本文通过提取目标超像素的颜色直方图特征构建目标模型,并利用Meanshift算法搜索候选区域,实现目标的准确跟踪。与传统的Meanshift算法相比,本方法能够有效地避免严重遮挡和形变对跟踪效果的影响。同时,利用超像素在候选区域的匹配情况,还能够对目标是否处于遮挡、丢失等状态作出判断,从而实现对目标模型的自适应更新。
1 SLIC超像素算法
超像素是一种中层图像特征,是一组具有相似的纹理、颜色特征的像素集,由Ren等人在2003年首先提出,已经被广泛应用于图像分割、识别等领域[3]。本文选用简单线性迭代聚类(simple linear iterative clutering, SLIC)算法进行超像素分割[4]。
SLIC算法是一种基于K-means聚类的超像素分割法,具有计算效率高,边缘特性好的优点。该方法将待分割图像等分成边长为s的矩形,将矩形的中心点作为初始迭代中心,以迭代中心周围2s的区域作为聚类区域。通过公式(1)~(3)和K-means迭代寻找局部区域的最大概率中心点,实现对相似像素的聚类。
$$ ~{{d}_{c}}=\sqrt{{{\left( {{l}_{j}}-{{l}_{i}} \right)}^{2}}+{{\left( {{a}_{j}}-{{a}_{i}} \right)}^{2}}+{{\left( {{b}_{j}}-{{b}_{i}} \right)}^{2}}}~ $$ (1) $$ {{d}_{s}}=\sqrt{{{\left( {{x}_{j}}-{{x}_{i}} \right)}^{2}}+{{\left( {{y}_{j}}-{{y}_{i}} \right)}^{2}}} $$ (2) $$ {{D}^{\prime }}=\sqrt{{{\left( \text{ }\frac{{{d}_{c}}}{m}~ \right)}^{2}}+{{\left( \text{ }\frac{{{d}_{s}}}{s}~ \right)}^{2}}}~ $$ (3) 式中:lj、aj、bj是像素j的值;lj、ai、bi是像素i的值;xj、yj是像素j的坐标;xi、yi是中心点像素i的坐标;s是聚类区域的边长;m是颜色空间的权重系数。
如图 1中所示,图(a)为图片经过超像素分割后各个超像素块的颜色直方图,直方图中颜色分布相对集中;图(b)为每个超像素所在的原始分割区域的直方图,该图中颜色呈随机分布,特征不明显。因此,通过对比图 1当中的图(a)、图(b)2个直方图序列,我们发现超像素相比于一般分块跟踪方法当中使用的将目标进行矩形分割所得到的矩形块具有更好的颜色特性。
2 Meanshift跟踪
2.1 外观模型建立
利用分块思想构建目标模型能够有效地增强跟踪算法的抗遮挡能力,但是传统矩形的分块不仅无法适应目标光照、形变所带来的影响,而且还会对目标状态的判定造成干扰[5]。本文选用超像素作为目标区域的分块。设目标区域的n个超像素表示为{Xi(ai, fi)|,i=1,…,n},其中Xi(ai, fi)表示SLIC算法分割目标区域后得到的超像素,fi是超像素的颜色直方图特征,ai是颜色均值特征[6]。ai和fi分别通过(4)式和(5)式得到:
$$ {{a}_{i}}=\frac{\sum\limits_{j=1\text{ }}^{m}{{{x}_{j}}}}{m} $$ (4) $$ {{f}^{u}}_{i}=C\sum\limits_{j=1}^{m}{k}\left( \|\text{ }\frac{{{x}_{0}}-{{x}_{j}}}{h}~\text{ }{{\|}^{2}} \right)\delta \left[ b\left( {{x}_{j}} \right)-u \right]~ $$ (5) 式中:$ \sum\limits_{u=1}^{t}{\text{ }f_{i}^{u}=1}\text{ }$, u表示颜色空间直方图的数量。$ C=1/\sum\limits_{j=1}^{m}{k[\|\frac{{{x}_{0}}-{{x}_{j}}~}{h}{{\|}^{2}}]}\text{ }$是归一化系数,k(x)为核函数[7]。通过实验,目标模型与候选区域的匹配是超像素之间的粗匹配,使用如高斯核函数这样具有权重的核函数,可能会造成目标区域的漂移,因此本文选择(6)式所示的Box核函数,权重为1。
$$ k\left( x \right)=\left\{ \begin{align} & 1,while\left\| x \right\|\le 1 \\ & 0,while\left\| x \right\|>1 \\ \end{align} \right.\text{ }~ $$ (6) 则目标区域和候选区域的模型分别表示为{Xi(ai, fi),i=1,…,n}和$\left\{ {{{\mathit{\hat{X}}}}_{i}}(~{{{\mathit{\hat{a}}}}_{i}}\mathit{, ~}{{\mathit{f}}_{i}}\mathit{, })|\mathit{, }i=\mathit{1, }\cdots \mathit{, }n \right\} $
2.2 相似性度量
目标跟踪是在候选区域当中寻找与目标模板的匹配度最高的区域。利用SLIC超像素具有相似颜色特征的性质,我们设定颜色均值阈值θ,从候选区域当中筛选出目标模型中每个超像素Xi的候选超像素集合Ri。使用Bhattacharyya系数,用超像素Xi遍历集合Ri中所有超像素,得到目标区域和候选区域的每一个超像素之间的相似度。同时,设定阈值τ,抛弃相似度小于τ的超像素对,并从剩下的超像素对当中找出与目标模型当中匹配度最高的超像素。公式如下:
$$ {{{\hat{\rho }}}_{ir}}\left( y \right)=\rho \left( {{f}_{i}},{{f}_{r}} \right)=\sum\limits_{\text{ }u=1}^{m}{\sqrt{\text{ }f_{i}^{u}\cdot f_{r}^{u}}}\text{ } $$ (7) $$ S=\left\{ \begin{align} & 1,while\text{ }{{\rho }_{r}}=\text{max}(~{{{\hat{\rho }}}_{ir}}\left( y \right)) \\ & 0,while\text{ }others \\ \end{align} \right.\text{ } $$ (8) 其中,S等于1时表示该超像素属于目标区域,等于0时表示不属于目标区域。通过匹配,我们将得到一个和目标外观模型当中各超像素具有较高匹配度的超像素集合,该集合当中超像素的集中区域即为我们认定的目标区域。
2.3 目标定位
在Meanshift方法中均值移动矢量始终指向概率密度最大的区域[8-9]。本文均值移动矢量指向候选区域中超像素标记S等于1的密度最大的区域。搜索概率密度最大区域的算法分两步。
第一步,计算候选区域超像素的权重:
$$ {{w}_{i}}=\sum\limits_{u=1}^{m}{\sqrt{\frac{f_{r}^{m}}{f_{i}^{u}}}~~\delta \left[ b\left( {{x}_{i}} \right)-u \right]}\text{ }~ $$ (9) 文中候选区域标记S等于1的超像素表示属于目标区域,具有相同的权重,因此 wi=1。
第二步,计得新的目标中心点位置:
$$ \begin{align} & {{y}_{1}}=\frac{\sum\limits_{i=1}^{n}{{{x}_{i}}{{w}_{i}}g}\left[ \|\frac{\hat{y}{{~}_{0}}-{{x}_{i}}}{h}~{{\|}^{2}} \right]~}{\sum\limits_{i=1}^{n}{{{w}_{i}}g\left[ \|\frac{{{{\hat{y}}}_{0}}-{{x}_{i}}}{h}~{{\|}^{2}} \right]}}= \\ & \frac{\text{ }\sum\limits_{i=i}^{n}{{{x}_{i}}g\left[ \|\frac{~{{{\hat{y}}}_{0}}-{{x}_{i}}}{h}~{{\|}^{2}} \right]}~}{\sum\limits_{i=1}^{n}{g\left[ \|\frac{{{{\hat{y}}}_{0}}-{{x}_{i}}}{h}~{{\|}^{2}} \right]}}\text{ }~ \\ \end{align} $$ (10) 当$ \left\| {{y}_{1}}={{{\hat{y}}}_{0}} \right\|<\delta $时则停止迭代,否则继续迭代,迭代终止之后,(xi, yi)即为新的目标中心位置。
本文以三次迭代为例,通过Meanshift法计算候选区域的超像素与目标模型超像素匹配得到的超像素集的目标中心点,以该中心点为预测目标区域中心,框定外观模型相同大小的区域作为新的预测目标区域。计算预测目标区域的中心点,重复以上过程,跟踪新目标中心点。通过以上过程的迭代,最终得到目标区域。
2.4 目标模型的自适应更新
由于跟踪过程中,光照变化和遮挡等因素会造成目标模型的改变,因此需要根据目标的变化不断调整目标模型。
在跟踪过程中,目标模型与候选区域中的超像素会进行匹配,相似度小于阈值的超像素对会被抛弃[10]。因此,当目标外观发生剧烈变化时,匹配结果将会因为相似度的降低而少于目标模型当中超像素的数量。因此,设置参数φ来表示新一帧候选区域信息的完整度,当φ小于给定的阈值时,则表示候选区域的完整度过低,可能发生遮挡、剧烈的光照变化或者目标丢失, 目标模板和新的候选区域的匹配结果将如图 2所示。从图中可见匹配结果远小于模板,即小于实验设定阈值,满足模板更新条件。
3 算法流程
综上,本文的跟踪过程步骤如下:
第一步,在初始帧中确定目标区域(如图 3(a)所示),对目标区域进行超素分割(图 3(b)所示),通过公式(4)~(6)分别计算每个超像素的直方图特征,构建目标模板,如图 3(c)、(d)所示。
第二步,将上一帧目标区域的中心点作为当前帧的目标中心y点,确定候选区域,进行超像素分割(如图 3(e)所示),利用公式(7)计算候选区域超像素与模板中超像素的Bhattacharyya系数,作为相似度,将最大相似度的超像素作为目标区域超像素,权重wi=1,得到如图 3(d)中所示结果。
第三步,按照(10)式计算目标新的中心点。
第四步,若$\left\| {{y}_{1}}-{{{\hat{y}}}_{0}} \right\|<\delta $则停止迭代,否则y1代替y0作为中心点返回第四步,直到找到密度最大区域为止,迭代结果如图 3(d)中框图中所示。
4 实验分析
本实验使用i5处理器,4G内存电脑,VS2012,Benchmark数据库[11]实现文中所述算法,实验结果为本文算法对Benchmark数据库当中的Girl和FaceOcc1两段视频进行跟踪的结果。视频当中目标分别发生了运动、尺度变换、遮挡、相似物体干扰等情况。为了方便与Benchmark当中的各类算法进行对比,本文算法将初始跟踪参数(初始帧目标区域的位置以及跟踪区域的大小)设定为与Benchmark数据库当中的标定数据的初始值相同,跟踪实验结果分别与KCF[12]、STC[13]、TLD[14]、MIL[15]、CT[16]算法的跟踪结果进行对比,由文献[11]分享的实验对比程序画出实验结果(如图 4和图 5所示)。图 4为6种算法在Girl视频当中的跟踪结果,各算法的精度(如图 4(c)所示)和成功率(如图 4(d)所示)分别如表 1所示,本文算法精度为0.856,成功率为0.601,实验结果均优于其他5种跟踪方法。图 5为6种算法在FaceOcc1当中的跟踪结果,各算法的精度(如图 5(c)所示)和(如图(d)所示)成功率分别如表 2所示,本文算法精度为0.567,成功率为0.523,精度优于CT、TCL、MIL、STC,成功率优于STC。注:成功率=(成功跟踪的帧数)/(视频总的帧数);精度=(成功跟踪的帧数中偏离中心点小于5个像素的帧数)/(成功跟踪的帧数),文中直接用小数表示成功率和精度。通过对FaceOcc1的实验跟踪结果的逐帧回放,并进行分析,发现FaceOcc1是在对目标遮挡的条件下进行跟踪实验。当目标被遮挡时,本文算法在候选区域当中所能够匹配得到的超像素减少,并且将会集中于未被遮挡的区域,因此目标中心点也同样偏移向被遮挡的区域,造成中心点的偏移,而Benchmark程序当中当跟踪中心点偏离标定中心20个像素时即判定为目标丢失,而在该视频当中本文算法的目标中心点随着遮挡而发生漂移,部分帧的跟踪中心点和标定中心点的误差大于20个中心点,因此被Benchmark判定为丢失,但是通过逐帧回放跟踪结果,本文算法始终保持对目标的跟踪,没有发生目标丢失的情况。因此,对于FaceOcc1的跟踪的成功率应该高于Benchmark所测的数据。综合以上2个标准视频的实验结果,本文算法在多种环境下的跟踪结果的精度和成功率始终保持相对稳定,跟踪的精度和成功率的波动起伏远远小于STC、MIL、CT等方法,具有更强的鲁棒性。
表 1 跟踪结果1Table 1. Tracking results 1项目 OUR KCF CT MIL TLD STC 成功率 0.601 0.542 0.314 0.402 0.566 0.553 精度 0.856 0.772 0.626 0.722 0.805 0.790 表 2 跟踪结果2Table 2. Tracking results 2项目 OUR KCF CT MIL TLD STC 成功率 0.523 0.742 0.630 0.592 0.581 0.212 精度 0.567 0.677 0.489 0.412 0.453 0.200 综上,本文提出的通过超像素分割算法构建目标外观模型,并用Meanshift进行定位的跟踪的算法在对目标进行跟踪的过程中当目标发生运动、遮挡、形变、相似物体干扰的情况时能够实现对目标鲁棒的跟踪。
5 结束语
针对跟踪过程中目标形变、物体遮挡、相似物体干扰引起目标外观模型变化,甚至目标丢失的问题,本文利用超像素构建目标的外观模型,根据上下两帧目标外观模型中超像素的变化情况定性地判断出当前目标的状态,将目标的状态信息作为先验信息,判断当前帧的目标是否发生形变、遮挡、丢失,根据判定结果对目标模型进行更新、扩大范围等操作,并利用Meanshift算法搜索目标的中心位置,实现目标的稳定跟踪。本文与经典跟踪算法的实验对比结果如表 1和表 2所示。在实验1中目标发生变化,被相似物体干扰时,本文跟踪算法的成功率和进度分别达到了0601和0.856;在实验2中目标发生遮挡时,本文跟踪算法的成功率和精度分为0.523和0.567。综合两种情况下的实验结果,本文算法在目标发生变化和相似物体发生干扰时比经典算法具有更高的跟踪精度和成功率,在目标被遮挡时算法的跟踪精度和成功率也位居前列,且与经典算法中的CT、MIL、TLD、STC在2种不同条件下跟踪的结果差别巨大的情况不同,本文算法在不同环境下的跟踪结果始终保持相对稳定,具有更强的鲁棒性。下一步将重点研究如何解决超像素外观模型匹配过程当中的轻微漂移,以及超像素对目标状态的精确描述,进一步增强目标跟踪的鲁棒性。
-
表 1 跟踪结果1
Table 1 Tracking results 1
项目 OUR KCF CT MIL TLD STC 成功率 0.601 0.542 0.314 0.402 0.566 0.553 精度 0.856 0.772 0.626 0.722 0.805 0.790 表 2 跟踪结果2
Table 2 Tracking results 2
项目 OUR KCF CT MIL TLD STC 成功率 0.523 0.742 0.630 0.592 0.581 0.212 精度 0.567 0.677 0.489 0.412 0.453 0.200 -
[1] Liu L, Xing J, Ai H, et al. Semantic superpixel based vehicle tracking[C]. US: IEEE, 2012.
[2] Fan H, Xiang J, Liao H, et al. Robust tracking based on local structural cell graph[J]. Journal of Visual Communication and Image Representation, 2015: 54-63. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=b41acacffcdc5d33d6d7363f315657f7
[3] Ren X, Malik J. Learning a classification model for segmentation[C]. US: IEEE, 2003.
[4] Achanta R, Shaji A, Smith K, et al. SLIC superpixels compared to state-of-the-art superpixel methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(11): 2274-2282. doi: 10.1109/TPAMI.2012.120
[5] 李倩雯.基于超像素学习的分块目标跟踪系统[D].上海: 上海交通大学, 2014. Qianwen Li. Robust patch-based object tracking via superpixel learning[D]. Shanghai: Shanghai Jiaotong University, 2014.
[6] 王美华, 梁云, 刘福明, 等.部件级表观模型的目标跟踪方法[J].软件学报, 2015, 26(10):2733-2747. http://d.old.wanfangdata.com.cn/Periodical/rjxb201510018 Wang Meihua, Liang Yun, Liu Fuming, et al. Object tracking based on component-level appearance model[J]. Journal of Software, 2015, 26(10):2733-2747. http://d.old.wanfangdata.com.cn/Periodical/rjxb201510018
[7] Collins R T, Liu Y, Leordeanu M. Online selection of discriminative tracking features[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2005, 27(10):1631-1643. http://cn.bing.com/academic/profile?id=43891da4b0e5ab668733ec92ccc10dc7&encoded=0&v=paper_preview&mkt=zh-cn
[8] Comaniciu D, Meer P. Mean shift: a robust approach toward feature space analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619. doi: 10.1109/34.1000236
[9] Leichter I. Mean Shift Trackers with Cross-Bin Metrics[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(4): 695-706. doi: 10.1109/TPAMI.2011.167
[10] 程旭, 郭海燕, 李拟珺, 等.一种基于超像素的局部判别式跟踪算法[J].东南大学学报:自然科学版, 2014, 44(6):1105-1110. http://d.old.wanfangdata.com.cn/Periodical/dndxxb201406002 Cheng Xu, Guo Haiyan Li Nijun, et al. Local discriminative tracking algorithm based on superpixel[J]. Journal of Southeast University:Natural Science Edition, 2014, 44(6):1105-1110. http://d.old.wanfangdata.com.cn/Periodical/dndxxb201406002
[11] Wu Y, Lim J, Yang M H. Object tracking benchmark.[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2015, 37(9):1834-48. http://d.old.wanfangdata.com.cn/Periodical/nyjxxb201711005
[12] Henriques J F, Rui C, Martins P, et al. High-speed tracking with kernelized correlation filters[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2014, 37(3):583-596. http://cn.bing.com/academic/profile?id=22a95188d7f3b68216fa40f016abc7d9&encoded=0&v=paper_preview&mkt=zh-cn
[13] Zhang Kaihua, Zhang Lei, Yang M H, et al. Fast tracking via spatio-temporal context learning[J]. Computer Science, 2013. http://d.old.wanfangdata.com.cn/Periodical/jsjgcyyy201612032
[14] Kalal Z, Mikolajczyk K, Matas J. Tracking-learning-detection[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2012, 34(7):1409-1422. http://d.old.wanfangdata.com.cn/Periodical/kxjsygc201309014
[15] Babenko B, Yang M H, Belongie S. Robust object tracking with online multiple instance learning[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2011, 33(8):1619-32. http://cn.bing.com/academic/profile?id=c831864ffa50d8a4af3aa871738af6fc&encoded=0&v=paper_preview&mkt=zh-cn
[16] Zhang K, Zhang L, Yang M H. Real-time compressive tracking[C]. Berlin: Springer-Verlag, 2012.
-
期刊类型引用(5)
1. 王彬彬. 基于SVM与Meanshift跟踪算法的运动视频目标跟踪. 现代电子技术. 2022(01): 56-60 . 百度学术
2. 黄战华,陈智林,张晗笑,曹雨生,申苜弘. 基于音视频信息融合的目标检测与跟踪算法. 应用光学. 2021(05): 867-876 . 本站查看
3. 何璟彬,陈伟林,陈霖. 基于人工智能控制理论PDC钻头设计平台研发. 自动化与仪器仪表. 2020(10): 129-132+136 . 百度学术
4. 杨磊,刘美枝,高海,党婵娟. 结合纹理特征的Camshift目标跟踪算法研究. 电子设计工程. 2018(15): 136-141+147 . 百度学术
5. 罗育辉,蔡延光. 基于Android视频的目标手动追踪系统研究与实现. 工业控制计算机. 2018(01): 115-116+118 . 百度学术
其他类型引用(4)