- 相关推荐
基于镜像Mean Shift的遮挡目标跟踪算法
摘要：针对当目标跟踪过程中目标被全遮挡时易导致目标跟踪不精确、甚至丢失目标的问题，提出一种基于镜像Mean Shift的遮挡目标跟踪算法。当前后帧Bhattacharyya系数匹配度大于等于80%时，表示目标没有被遮挡，采用颜色特征和轮廓特征定位目标，利用分块沙包窗核函数实现尺寸自适应;当前后帧Bhattacharyya系数匹配度小于80%时，表示目标进入遮挡区域，则利用先验训练分类器和镜像原理对遮挡区域目标的位置和尺寸大小进行预测;当前后帧Bhattacharyya系数匹配度再次大于等于80%时，表示目标离开遮挡区域，则转换为Mean Shift跟踪。当目标没有遮挡时，采用颜色特征和轮廓特征定位目标，利用分块沙包窗核函数实现尺寸自适应;当目标进入遮挡区域时，在改进的巴氏系数条件触发下(低于设定阈值)，利用先验训练分类器和镜像原理对遮挡区域目标的位置和尺寸大小进行预测;当目标离开遮挡区域时，再次利用巴氏系数条件触发(高于设定阈值)【什么】转换为Mean Shift跟踪实验结果表明：所提算法与子区域分类器的在线Boosting算法和多视角多目标协同追踪算法相比，在目标全遮挡的情况下能更好地跟踪目标，提高了跟踪精度和鲁棒性，且满足实时性要求。
关键词：镜像; Mean Shift; 全遮挡; 巴氏系数; 目标跟踪; 全遮挡
引言
机器视觉技术广泛应用于军事制导、视频监控、医疗诊断、产品检测等领域[1-3]。而在上述领域中都会涉及目标跟踪，在跟踪目标的过程中，由于目标本身特征的多样性以及外界环境的复杂性，尤其当目标被自遮挡、物体相互遮挡、背景遮挡时，如何更精确地定位和跟踪目标成为一个极具挑战性的课题[4]。Thompson等[5]提出利用光流场来检测视频中的遮挡面，但是没有涉及如何跟踪目标。Maver等[6]从遮挡的角度出发，研究如何获得一个未知场景的3D数据，利用几何关系从先验的纹理信息预测出遮挡时目标状态，但是预测状态的误差会随着跟踪的进行而逐渐增大，同时计算复杂度高。Zitnick等[7]利用视差图的方法解决遮挡问题，要求各个像素点具有唯一性，否则当遇到相似目标或者背景时易导致跟踪失败。在文献[8-10]中学者利用分割理论提取遮挡区域的目标解决目标部分遮挡问题，对全遮挡情况误差很大，甚至跟踪失败。Zhang等[11]通过帧内、帧间、跟踪等级三个顺序层次实现目标遮挡跟踪; 李沛等[12]提出基于信用度分类遮挡问题解决方法，对前后帧计算结果的连续性要求较高，否则计算得到的遮挡目标定位精度不高。颜佳等[13]在遮挡环境下采用在线Boosting的目标跟踪，利用分区域的特征匹配法剔除被遮挡子区域对目标定位的影响，但对目标尺寸发生变化并且伴有遮挡时的跟踪问题没有提供解决方案。龚卫国等[14]提出一种像素投影算法(Running Average with Selectivily， RAS)背景更新，利用RAS对遮挡粘连目标进行分离，采用滤波加Mean Shift 算法，并将其与 Kalman算法结合，实现红外目标的实时准确跟踪，较好地解决了部分遮挡问题。周良毅等[15]提出基于动态遮挡阈值的多视角多目标协作追踪，引入遮挡变量，改进了目标遮挡的判决标准和公共平面中的目标融合特征，并通过结合改进粒子滤波得到基于遮挡变量的多视角目标协作追踪算法。
上述目标跟踪算法对目标被自遮挡、物体相互遮挡、背景遮挡时针对目标部分遮挡跟踪取得了较好的效果，但仍存在以下不足：1)目标在部分遮挡的场景下提出的算法对目标的定位不精确;2)涉及的是目标部分遮挡跟踪，而对于目标在被相似目标和背景全遮挡的场景下没有提供很好的解决方案。
基于以上不足，本文提出一种基于镜像Mean Shift的目标遮挡处理算法。在没有或者部分遮挡(D(n)≥0.8D(n-1))情况下，融合颜色特征和轮廓特征表述目标，然后利用沙包核窗函数和Mean Shift算法对目标进行跟踪，并将每帧的序号和目标的位置信息保存在一个记忆队列中;当D(n)<0.8D(n-1)时，表明目标处于完全遮挡的情况，记录当前阈值变化帧的序号(假设为第m帧)，利用先验训练分类器和镜像原理可以预测在遮挡区域中目标第n帧尺寸大小等于第2m-n帧的尺寸大小(已知)，遮挡区域的目标到临界点的距离(第n帧到第m帧的距离)等于目标从未遮挡区域(第2m-n帧)到临界点(第m帧)的距离，从而可以确定目标的位置信息。
一、传统的Mean Shift目标跟踪算法
1.1颜色特征描述
设qc={qcu}u=1，2，…，Bc表示目标参考颜色直方图，{xi}i=1，2，…，n为中心位置y的目标候选区域的像素位置，则目标候选图像区域的颜色加权直方图pc={pcu(y)}u=1，2，…，Bc为：
pcu(y)=ch∑ni=1k(‖(y-xi)/h‖2)δ[bf(xi)-u](1)
其中：ch为颜色直方图归一化常数;u为目标特征值;k(・)为下列Epanechnikov核剖面函数：
kE(r)=
1-r，r≤1
0，r>1 (2
对于离目标中心位置越近的像素赋予较大的权值，对于远离目标中心位置的像素赋予较小的权值;h为核半径;δ是Epanechnikov函数;bf(・)是将给定位置的像素映射到颜色直方图相应颜色区间(color bin)的映射函数。
1.2轮廓特征描述
轮廓作为特征来描述目标有一定的优势，轮廓的提取过程比较简单，以目标的形状作为先验信息，结合Bayesian理论来提取目标的轮廓，当目标运动时目标轮廓所包含的面积变化明显。如果图像中某一区域目标静止，则轮廓所包含的面积变化率很小，图像的像素落到轮廓直方图较低的颜色区间;如果该区域发生运动时，则相应的轮廓所包含的面积变化率很大，图像像素会落到轮廓直方图的每个颜色空间，因此采用均匀分布模型。设qo={qou}u=1，2，…，Bo表示目标参考轮廓直方图，{xi}i=1，2，…，n为中心位置y的目标候选区域的像素位置，则目标候选图像区域的轮廓加权直方图po={pou(y)}u=1，2，…，Bo为：
pou(y)=ch∑ni=1k(‖(y-xi)/h‖2)δ[bf(xi)-u](3
1.3跟踪窗的选取和遮挡跟踪
传统Mean Shift 跟踪算法跟踪窗采用固定尺寸的矩形窗以及利用分割算法和Kalman算法预测目标在遮挡区域的状态。当目标尺寸变化时，跟踪窗包含目标特征的同时，也包含更多的背景特征，导致定位不精确、计算复杂度高、实时性差; Kalman算法对目标的位置和尺寸的预测，在短时间跟踪或者部分遮挡的场景取得不错的效果，但在长时间遮挡或者全遮挡的场景下，跟踪误差会逐渐增大，甚至跟踪失败，而实际场景长时间全遮挡的场景很常见，所以算法具有一定的局限性，影响跟踪效果。
二、基于镜像Mean Shift的遮挡目标跟踪算法
在部分遮挡的场景下，采用传统的Mean Shift目标跟踪算法融合颜色特征和轮廓特征描述目标和采用固定尺寸的矩形窗跟踪目标，在精度要求不高的情况下可取得不错的跟踪效果。而在全遮挡和要求精度稍高的情况下，传统算法具有局限性。因此本文采用一种基于镜像Mean Shift的遮挡目标跟踪算法来优化算法。在部分遮挡和没有遮挡的情况下，采用改进的Bhattacharyya系数来优化传统的目标定位方法，而跟踪窗采用可自适应的沙包窗跟踪目标;根据前后帧Bhattacharyya系数匹配度是否大于80%判断目标是否遮挡，当大于80%说明目标是没有遮挡或者部分遮挡，传统算法仍然可以跟踪，否则，根据记录的先前序列号和位置信息利用镜像原理可以预测出目标的尺寸大小和位置信息，实现跟踪。
2.1Bhattacharyya系数的选取
Bhattacharyya系数是衡量目标参考模型和候选模型的最大相似度，当取得最大相似度时可以定位目标，同时也可以根据前后两帧的相似度是否小于80%来判定目标是否被完全遮挡，条件成立时则判定为完全遮挡，跟踪方式转换为镜像Mean Shift目标跟踪模式，以便更好地跟踪目标。传统的Bhattacharyya系数计算有根号运算，计算复杂度高，本文选取文献[16]式(4)的度量系数避免开方运算，降低运算复杂度：
(Y)=∑mu=1min (u，u(Y))(4
2.2Mean Shift目标搜索
给定目标参考颜色直方图和目标上一帧的估计中心位置0，则目标在当前帧的位置1可由式(5)目标函数所得到：
D(y)≈λcρ(qc，pc(y))+λoρ(qo，po(y))(5)
其中：0≤λc≤1、 0≤λo≤1分别表示颜色特征和轮廓特征的权值，且λc+λo=1; ρ(・)表示两直方图的Bhattacharyya系数。将式(1)、(3)、(4)代入式(5)得到式(6)：
D(y)=
min Ch∑ni=1(λc+λo)k(‖(y-xi)/h‖2)δ(bf(xi)-u) (6
利用式(7)进行Mean Shift迭代，当核跟踪窗口由位置0移到1时，函数D(y)将会递增：
1=∑ni=1xiωig(‖(0-xi)/h‖2)∑ni=1ωig(‖(0-xi)/h‖2)(7)
其中：ωi=min Ch∑ni=1(λc+λo);g(x)=-k′(x)。令0←1，重复此迭代过程，直到‖1-0‖<ε或达到预先指定的迭代次数为止，ε是预先给的正数，本文选取ε=0.02。
2.3特征自适应融合
已知目标当前帧位置，设qc、qo、pcl、pol分别表示颜色直方图、边界直方图、背景区域颜色直方图、背景区域边界直方图;ρ(·)是表示两直方图的Bhattacharyya系数。假设颜色特征和轮廓特征在当前帧的权值为λtc和λto，则颜色特征和轮廓特征下一帧的权值为：
λt+1c=(1-α)λtc+αρ(qo，pol)ρ(qc，pcl)+ρ(qo，pol)(8
λt+1b=(1-α)λtb+αρ(qc，pcl)ρ(qc，pcl)+ρ(qo，pol)(9)
其中：α为权值常数，决定权值更新的速度; ρ(qc，pcl)ρ(qo，pol)表示哪个特征更准确定位目标，当比值大于1则说明ρ(qo，pol)轮廓特征能更好区分目标，所以用1-ρ(qc，pcl)[ρ(qc，pcl)+ρ(qo，pol)]来反映其在总体特征所占的比例，反之则用颜色特征。
2.4核窗宽自适应
目标通常不是标准的矩形或者椭圆形状，常常是椭圆和矩形的复合体形状，其形状如图1所示，故命名为沙包窗。沙包窗核函数既能包含特征目标，也能减少背景特征干扰，更加准确地描述目标。
图片
图1沙包窗模型
核窗宽调整原理如图2所示。
图片
图2窗宽调整原理
在初始帧手动选取目标区域，确定目标窗口中心x0及核窗宽h，提取目标的边界最高点x1和最低中心点x2(最好3点在1条垂直线上)，并分别计算x0与x1和x2的距离d1和d2。读取下一帧，以上一帧窗口的中心为候选目标中心进行Mean Shift迭代，得到候选目标的新跟踪窗口中心x0′，并根据分块区域跟踪窗口的Mean Shift迭代得到x1′和x2′，分别计算d1′和d2′，计算：
=(d1′/d1+d2′/d2)/2(10
以来调整窗宽，设内接最大面积矩形的长为m，宽为n，矩形面积为定值mn=2ab;矩形上下部分的椭圆面积相等为：
s=πab2-an2bb2-n24-ab arcsin1-n24b2 (11
则更新跟踪窗：
m=・m
n=・n
s=・πab2-an2bb2-n24-ab arcsin1-n24b2(12 2.5全遮挡处理
2.5.1镜像原理
在空间放置一点电荷q，在其周围产生磁场E，磁场中距离电荷q的距离为r处的磁场大小为：
E=kqr2(13
在同一线选取距离点电荷q的距离为r1、r2、r3的点分别为a1、b1、c1，而与之同等电势(在水平轴)的点有a2、b2、c2其位置关于点电荷q对称，故称为“镜像”，原理如图3所示。
图片
图3镜像原理
2.5.2全遮挡问题处理
当目标未进入遮挡区域时根据颜色特征和轮廓特征定位目标以及用沙包核函数实现尺寸自适应;当目标进入遮挡区域时，在D(n)≥0.8D(n-1)时说明目标没有遮挡或者是部分遮挡，根据Mean Shift的鲁棒性，仍然可以跟踪目标，将当前帧的序号和目标的位置信息保存在一个记忆队列中;在D(n)<0.8D(n-1)时说明目标严重遮挡或者是全遮挡，此时利用镜像原理预测目标的位置和尺寸大小，当前帧记为第n帧，尺寸大小为：
Cn=C2m-n(14
位置为：
Sn=vT(2m-n)(15)
其中：C为目标尺寸大小即跟踪窗的大小;m是目标介于部分遮挡和全遮挡的序列帧数序号，T为每帧的耗时，假设目标运动速度恒定为v;当D(n)≥0.8D(n-1)时说明离开遮挡区域，同样采用Mean Shift算法跟踪。跟踪原理如图4所示。
分区
图片
图4跟踪原理
三、算法步骤
基于上述分析，基于镜像Mean Shift的目标遮挡处理算法如下：
手动选取目标区域，给定参考颜色直方图qc和参考边界直方图qo，初始权值λc=λo=0.5，目标在上一帧的位置0，确定目标跟踪窗口中心位置x0、边界最高点x1和边界最低中心点x2，摄像头点与道路做垂直焦点记为0点，目标速度恒为v。
1)计算d1、d2。
2)以0为初始位置，计算pc(0)和po(0)(根据式(1)和式(3))。
3)计算D(0)(根据式(4)、(5)目标更新位置1(根据式(7))。
4)计算pc(1)， po(1)和D(1)。
5)若0.8D(0) 6)若‖1-0‖<ε(ε一般取10-5)，则停止;否则0←1返回步骤2)。
7)更新权值λc和λo(根据式(8)、(9))。
8)计算d1′和d2′。
9)更新a、b、s(根据式(12))，返回步骤1)依次跟踪下去。
10)将每一帧的序号和目标的位置信息尺寸大小保存在一个记忆队列中，记垂直点处为m帧。
11)预测出目标的位置和尺寸大小(根据式(14)、(15))，返回步骤1)依次跟踪下去。
四、实验结果与分析
为了验证本文算法，实验均在Intel Core i33220 3.3GHz CPU、 3.22GB内存的电脑上采用Matlab 2012环境下进行了仿真实验，其中实验视频来自实际拍摄的车辆目标测试视频，序列分辨率为640×480。图5～7分别是目标进入区域未遮挡或者部分遮挡、进入全遮挡区域、离开遮挡区域场景情况下，文献[13]、文献[15]和本文算法实验对比结果，从图中可以看出，本文算法定位更精确。表1是3种算法的成功跟踪率和每帧平均耗时的实验结果，验证算法的实时性。其中成功跟踪率=全遮挡序列成功跟踪的帧数/全遮挡序列总帧数，当目标预测的位置与实际的目标位置差距小于一个车身长度则认为跟踪成功(约120个像素)，否则跟踪失败。
根据图5可以看出文献[13]、文献[15]和本文的算法都可以在未遮挡区域跟踪车辆目标。文献[13]采用背景差分法检测目标和矩形核窗函数跟踪目标;文献[15]采用HSV颜色特征检测目标和矩形核窗函数跟踪目标;本文采用融合颜色特征和轮廓特征精确定位目标和沙包核窗函数。在目标的颜色和背景的颜色相似度不高的场景下，颜色特征和背景差分法都能很好地检测目标，但矩形核窗函数在包含目标特征的同时包含了更多的背景特征，使得计算复杂度高，计算时间长。而本文提出的沙包核窗函数在包含了目标特征的同时减少了背景特征的影响，计算复杂度低，实时性更好。
从图6和表1可以看出3种算法大体都能对全遮挡目标实现跟踪。因为进入全遮挡区域，文献[13]、[15]利用Kalman算法对遮挡目标进行运动位置预测和估计可实现较为鲁棒的跟踪，刚开始的误差小，但是预测的结果会影响下一帧的目标位置和尺寸的大小，随着跟踪的推进误差逐渐增大，后遮挡区域目标位置的预测和估计就容易失败。而本文算法利用位置镜像原理，根据目标运动时间确定位置和尺寸大小，与前后帧的位置和尺寸大小无关，仅与目标运动的时间相关，故误差不会累积，所以误差小。
通过表1可以看出本文算法比文献 [13]和文献[15]算法跟踪成功率分别提高了1.6%、11%;同时每帧平均耗时24ms，满足实时性要求。
根据图7可以看出，文献[13]、[15]和本文算法都可以在离开遮挡区域时跟踪车辆目标。当目标离开遮挡区域时，目标颜色和背景的颜色区分度很大，根据颜色特征和背景差分法以及本文算法融合颜色特征和轮廓特征都可以准确地重新定位目标，依次跟踪下去。
文献[13]、[15]提出的算法利用颜色特征和背景差分法定位目标，结合Mean Shift算法在没有遮挡或者部分遮挡的情况下能准确地跟踪目标;而在全遮挡的情况下，利用Kalman算法预测目标的位置，随着跟踪的推进会产生误差累积，导致跟踪成功率下降。本文算法在没有遮挡或者部分遮挡的情况下，利用颜色特征和轮廓特征可以精确定位目标;在全遮挡的情况下利用镜像原理可以精确地预测目标的位置和尺寸大小，提高了跟踪效果，满足实时性要求。
五、结语
本文提出一种基于镜像Mean Shift的遮挡目标跟踪算法，利用先验训练分类器和镜像原理较好地解决了目标在完全遮挡场景下的目标跟踪问题。但是，本文算法是基于目标的运动速度是恒定的前提，而实际中跟踪的目标速度是多变的，如何准确跟踪速度多变的目标是下一步工作的研究重点。
参考文献：
[1] CAO Y， JIN S， FAN Y. Research on detection and tracking system of near space vehicle based on STK/Matlab[J].Journal of System Simulation， 2014，26(5)：1058-1063.(曹运合，靳松阳，樊友友.基于STK/Matlab的临近空间飞行器检测跟踪系统研究[J]. 系统仿真学报，2014，26(5)：1058-1063.)
[2] SANG H， WU D， WANG H. Face tracking and recognition system for video surveillance[J]. Computer Engineering and Applications， 2014， 50(12)： 175-179.(桑海峰，吴丹阳，王会.视频监控下的人脸跟踪与识别系统[J].计算机工程与应用，2014，50(12)：175-179.)
[3] LI W， CHENG L. New progress of fabric defect detection based on computer vision and image processing[J].Journal of Textile Research，2014，35(3)：158-164.(李文羽，程隆棣.基于机器视觉和图像处理的织物疵点检测研究新进展[J]. 纺织学报，2014，35(3)：158-164.)
[4] XUE C， ZHU M， LIU C. Review of tracking algorithms under occlusion[J].Chinese Journal of Optics and Applied Optics，2009， 2(5)：388-394.(薛陈，朱明，刘春香.遮挡情况下目标跟踪算法综述[J]. 中国光学与应用光学，2009，2(5)：388-394.)
[5] THOMPSON W B， MUTCH K M， BERZINS V A. Dynamic occlusion analysis in optical flow fields[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1985， 7(4)：374-383.
[6] MAVER J， BAJCSY R. Occlusions as a guide for planning the next view[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1993， 15(5)：417-433.
[7] ZITNICK C L， KANADE T. A cooperative algorithm for stereo matching and occlusion detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22(7)： 675-684.
[8] PANG C C C， LAM W W L， YUNG N H C. A novel method for resolving vehicle occlusion in a monocular trafficimage sequence[J]. IEEE Transactions on Intelligent Transportation Systems，2004，5(3)：129-141.
[9] GENTILE C，CAMPS O，SZNAIER M. Segmentation for robust tracking in the presence of severe occlusion[C]// Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE，2004，132： 483-489.
[10] ZHANG Y， XU H. Fragment tracking under occluded target[J].Journal of Image and Graphics， 2014， 19(1)：92-100.(张彦超，许宏丽.遮挡目标的分片跟踪处理[J]. 中国图象图形学报，2014，19(1)：92-100.)
[11] ZHANG W， WU Q， YANG X， et al. Multilevel framework to detect and handle vehicle occlusion[J]. IEEE Transactions on Intelligent Transportation Systems，2008， 9(1)：161-174.
[12] LI P， LUO W， LI G， et al. Using credit coefficients to solve occlusion problems in the stereo vision[J].OpticsElectronic Engineering， 2008， 35(12)： 89-95. (李沛，罗武胜，李冠章，等.基于信用度分类遮挡问题解决方法[J].光电工程，2008，35(12)：89-95.)
[13] YAN J， WU M. Online Boosting based target tracking under occlusion[J].Optics and Precision Engineering，2012， 20(2)： 439-446.(颜佳，吴敏渊.遮挡环境下采用在线Boosting的目标跟踪[J]. 光学精密工程，2012，20(2)：439-446.)
[14] GONG W， WANG X， LI Z. Antiocclusion detection and tracking algorithm for multiple for infrared targets[J]. Chinese Journal of Scientific Instrument，2014， 35(3)：535-542.(龚卫国，王旭，李正浩.一种抗遮挡的红外多目标实时检测跟踪算法[J].仪器仪表学报，2014，35(3)：535-542.)
[15] ZHOU L， WANG Z， WANG Y. Multiview cooperative tracking of multiple mobile object based on dynamic occlusion threshold[J].Journal of Research and Development，2014， 51(4)：813-823.(周良毅，王智，王营冠.基于动态遮挡阈值的多视角多目标协作追踪[J].计算机研究与发展，2014，51(4)：813-823.)
[16] DI N， ZHU M. An algorithm for realtime tracking target in complex environment[J].Journal of Image and Graphics，2008， 13(9)：1758-1765.(邸男，朱明.一种复杂背景下的实时目标跟踪算法[J].中国图象图形学报，2008，13(9)：1758-1765.)
【基于镜像Mean Shift的遮挡目标跟踪算法】相关文章：
基于货物当前状态全程跟踪的调度算法03-07
基于序贯蒙特卡罗算法的MIMO信道跟踪11-22
动背景下基于模板匹配的快速跟踪算法03-07
基于DirectShow与粒子滤波器的人体运动目标跟踪03-07
基于DSP的信道译码算法优化03-19
基于阶梯细化的图像放大算法03-07
基于遗传算法的OD分布03-21
基于ICA的鲁棒图像水印算法11-22