基于Cam-shift的预测跟踪方法分析与改进

2017-11-24刘振宇张百颖

辽宁大学学报（自然科学版） 2017年3期

关键词：线性滤波背景

刘振宇,张百颖

(沈阳工业大学信息科学与工程学院,辽宁沈阳 110870)

基于Cam-shift的预测跟踪方法分析与改进

刘振宇,张百颖

(沈阳工业大学信息科学与工程学院,辽宁沈阳 110870)

为了在有遮挡等因素干扰的复杂背景下很好的完成移动目标的位置预测跟踪,研究了Kalman滤波与Cam-shift算法结合的方法.Kalman滤波可以较精准地完成移动目标的位置预测,与Cam-shift算法结合可以很好的完成跟踪.在此基础上,提出了一种线性预测与Cam-shift算法结合的目标预测跟踪方法,即将线性预测方法代替Kalman滤波完成预测估计,并将预测估计结果代入Cam-shift算法中进行跟踪.实验表明该方法既可以保证遮挡过程中追踪的准确性,又能减少迭代时间,能够更好地满足实时性的要求.

Cam-shift;Kalman滤波;线性预测;移动目标跟踪;位置预测

0 引言

移动目标轨迹的跟踪和预测是人工智能研究领域不可缺少的一部分,是机器视觉、目标跟踪检测的关键技术.不同的应用背景,有不同的跟踪方法:L-K(Lucas&Kanade)光流法和H-S (Horn&Schunck)光流法[1]不需考虑背景信息,通过给像素点赋予速度矢量,根据目标与背景速度矢量的差异追踪目标,但要求相邻帧之间亮度恒定;图割算法[2]是将目标跟踪问题映射到能量函数中,优化求解出目标区域,计算复杂;Kass提出的Snake模型算法[3-4]是基于轮廓边缘特征的跟踪方法,其能量利用最小,但轮廓初始化复杂;董春利[5]等人通过将粒子滤波和GVF-Snake的结合,提出的自适应非线性滤波算法,对运动和变形目标进行跟踪,但效率较低;而Yizong Cheng[6]提出的Mean-shift算法是基于颜色特征的密度梯度无参估计算法,其形式简单,易于操作,但没有实时更新搜索窗口的功能,移动目标尺度变化快,易造成目标跟踪丢失;Bradski在Mean-shift算法的基础上提出的Cam-shift算法[7],可以自动实时地调整搜索窗口的大小,并且保留了Mean-shift算法的优点,但移动目标的颜色特征不明显或有遮挡等因素干扰时,会导致跟踪失败.

本文从Cam-shift算法分析出发,结合Kalman滤波进行移动目标的识别与估计,很好地降低了在复杂背景下跟丢目标的概率,并利用物理学运动相关知识,提出了线性预测与Cam-shift算法相结合的方法,改进的方法既能保证在复杂背景下的成功跟踪,又能减少计算时间,具有更好的实时性.

1 Cam-shift算法原理分析

Cam-shift算法是在Mean-shift算法的基础上提出的改进算法[8],该方法对连续图像序列的每一帧都做Mean-shift算法处理,当前帧的处理结果作为下一帧Mean-shift算法搜索窗口的初始值,依次进行迭代运算,完成跟踪.具体实现步骤如下:

1) 颜色模型的建立

Cam-shift算法采用颜色模型做特征进行目标跟踪.RGB颜色模型产生或显示色彩,HSV颜色模型能反应颜色的本质特征,它可以将色度,饱和度,明度分开处理,提高算法的稳定性.因此,选择HSV颜色空间H分量作为跟踪目标的特征,建立颜色直方图,这样会比完整的RGB和HSV模型计算量减少很多.RGB与HSV模型的转换公式如下:

V=max(R,G,B)

(1)

S=(V-min(R,G,B))/V

(2)

(3)

2) 反向投影图的生成

将生成的H分量信息直方图转换成颜色的概率分布图像,即将像素值为255的点概率对应设置为1,将像素值为0的点的概率设置为0,这样得到的颜色概率投影图像即为原颜色直方图的反向投影图像.

3) 利用Mean-shift算法寻找质心

初始化搜索窗口,设I(x,y)为像素点(x,y)反向投影图的对应像素点,通过计算搜索窗口的零阶矩和一阶矩得到搜索窗口的质心,将搜索窗口的中心移到质心位置,并根据零阶矩M00更新窗口大小.具体公式如下[9]:

(4)

搜索窗口的质心为:

(5)

更新窗口大小为:

(6)

当窗口移动到质心的距离大于预设值时,重新计算窗口质心的位置,直至满足收敛条件,再进行下一帧的追踪计算,依次循环,完成整个追踪过程.

图1显示了利用Cam-shift算法在复杂背景下移动目标序列的的跟踪结果,a图为第10,20,30,40帧序列正常无遮挡情况下的跟踪结果,b图为第50,60,70,80帧序列在有遮挡情况下的跟踪结果.容易看出,Cam-shift算法可以自动的实时的调整搜索窗口的大小,在无干扰的背景下可以准确地跟踪目标,但当遇到遮挡等因素影响时,很容易由于颜色特征不明显,迭代过程繁杂而造成计算失误,进而导致跟踪失败.因此,针对这一缺点引入估计器预测移动目标的位置,减少迭代次数,进而减少失误率.

图1 传统Cam-shift算法跟踪结果

2 Cam-shift改进算法的研究

2.1 Kalman与Cam-shift算法结合

2.1.1 Kalman滤波

卡尔曼滤波器是通过最小均方误差准则对移动目标实现的预测估计方法[10],它是通过状态方程和观测方程的关系进行建模来构建一个离散的时间线性系统.系统的状态方程和观测方程[11]分别为:

X(k)=AX(k-1)+BU(k)+W(k)

(7)

Z(k)=HX(k)+V(k)

(8)

其中,X(k)为K时刻系统的状态向量,可定义为:

X(k)=[x(k)y(k)v(k)u(k)]T

(9)

x(k)与y(k)分别表示目标中心在x,y轴的坐标分量;v(k),u(k)分别表示目标中心在x,y轴的速度;U(k)Z(k)分别为K时刻系统的控制量和观测向量,xz(k)与yz(k)分别代表目标中心在x,y轴的坐标值.

Kalman滤波算法[12]为:

(10)

本文中,Kalman系统的状态方程和观测方程构建时根据随机加速运动方程,可得到:

由此,Kalman滤波器建模完成.

2.1.2 Kalman与Cam-shift算法结合实现过程

由于应用Kalman滤波算法进行预测跟踪时是基于像素的全局搜索,计算量大,当应用于复杂背景时,全局搜索抗干扰能力弱,容易丢失跟踪目标.本文根据Kalman算法和Cam-shift算法的优缺点,将其进行结合,即可将全局搜素转变成局部搜索,从而减少计算量,提高准确率.

具体方法如下:

1)首先,设置追踪目标的初始值,例如速度,位置等;

2)计算下一帧图像的方差,代入公式求出此时的目标状态,利用Kalman相关公式预测协方差和状态的更新,估计出追踪目标在下一帧最可能出现的位置和运动速度;

3)将上述结果导入Cam-shift算法中,在预测估计的目标位置附近,进行局部的目标搜索及匹配,将搜索后的窗口中心位置作为Kalman的测量值;

4)更新跟踪窗口;

5)更新目标的协方差矩阵和目标状态方程,重复步骤(2),直至结束.

2.2 线性预测与Cam-shift算法结合

2.2.1 线性预测

从物理学可知,当描述系统中的目标物体运动状态方程为线性方程时,给定目标运动状态的初始条件,即可预见该目标之后的任意时刻的运动状态.而从运动学角度分析,曲线运动可以看作是由短时间的匀速直线运动构成的,当移动物体的速度及运动方向和前一时刻保持大体相同时,可以看作是匀速直线运动.特别的,当目标的移动速度平缓,由于每一帧的时间间隔很短,可以将每帧间的物体运动看作是匀速直线运动.

线性预测方法的计算过程为:已知目标的初始位置,根据目标的当前位置坐标与初始位置坐标,计算出运动速度与方向的坐标偏移差,然后根据所得的坐标偏移差,计算出下一帧的期望位置,即假设目标在上一帧的中心位置坐标为(xi-1,yi-1),当前帧的中心位置坐标为(xi,yi),则坐标偏移差可近似为(Δx,Δy)=(xi-xi-1,yi-yi-1),由于两帧间的移动目标移动时间很短,可以近似看成是匀速直线运动,所以可以根据运动学公式,得到下一帧中目标的期望位置为:(xi+1,yi+1)=(xi+Δx,yi+Δy).

图2 跟踪流程图

2.2.2 线性预测与Cam-shift算法结合的实现

本文根据线性预测的思想,将其与Cam-shift算法结合,将得到的目标期望位置作为搜索窗口的中心,代入Cam-shift算法中,进而在局部迭代收敛出真实的移动目标质心,更新新的中心位置坐标,依次循环,很好的完成追踪过程.

跟踪流程图如图2所示:

3 实验结果与分析

本文通过对Kalman与Cam-shift算法结合与上述的线性预测与Cam-shift算法结合的对比分析,来验证上述线性预测与Cam-shift算法结合的有效性和实时性.本文采用复杂背景下有遮挡过程的人直立行走序列图像(大小为360*640)进行跟踪实验,跟踪窗口为矩形窗口,初始窗口由背景差分法检测出第一帧移动目标的位置确定,分别选取第30,60,90,130帧跟踪序列图像以示说明.

下图为Kalman与Cam-shift算法结合和线性预测与Cam-shift算法结合的跟踪结果:

从图3可以看出,Kalman与Cam-shift算法结合的方法和线性预测与Cam-shift算法结合的方法均可以自动实时的更新窗口大小,当有遮挡过程时,这两种改进的方法与传统的Cam-shift方法比较,受遮挡因素影响较小,均能保证追踪的准确性,很好的完成跟踪.

本文又在复杂背景下进行了50次跟踪实验,分析比较了三种算法的跟踪正确率,从表1中可以直观地看出,本文提出的线性预测与Cam-shift结合算法和Kalman与Cam-shift结合算法跟踪正确率比传统的Cam-shift算法高很多.通过跟踪连续30帧无遮挡干扰情况的序列图像,分析比较了传统Cam-shift算法与改进算法的迭代次数与消耗时间,可以看出,本文提出的线性预测与Cam-shift结合的算法与Kalman与Cam-shift结合的算法的总迭代次数相差很少,比传统的Cam-shift算法减少一半左右;而本文提出的线性预测与Cam-shift结合的算法单次迭代平均耗时与传统的Cam-shift算法相差很少,但由于迭代次数是传统Cam-shift算法的一半,所以总耗时比传统的Cam-shift算法少很多.而Kalman与Cam-shift结合的算法构建的预测系统复杂,单次迭代平均耗时较长,所以总耗时高于本文提出的算法的花费时间,但仍然低于传统Cam-shift算法的耗用时间.因此,本文提出的算法既能满足遮挡等干扰的准确追踪,又能保证更好的实时性.

图3 改进的算法跟踪结果

跟踪正确率总迭代次数总耗时单次迭代平均耗时传统Cam-shift算法84%4568.5ms1.52msKalman与Cam-shift结合100%2141.7ms1.98ms线性预测与Cam-shift结合100%2335.4ms1.54ms

4 结论

由于传统的Cam-shift算法在复杂背景下存在受遮挡因素影响较大、跟踪不精准的可能性,本文从研究Kalman与Cam-shift算法结合的方法中受到启发,用线性预测代替Kalman滤波简化了线性估计系统的构成,提出了一种线性预测与Cam-shift算法结合的预测跟踪算法.跟踪实验表明,该算法既能满足移动目标在遮挡过程中的成功跟踪,又能减少单次迭代时间,进而提高跟踪效率,更好的满足了实时性的要求.

[1] Amiaz T,Kiryat N.Dense discontinuous optical flow via contour-based segment-ation[C].Proceedings of IEEE International Conference on Image Processing,2006,3:1264-1267.

[2] Suga A,Fukuda K,Takiguchi T,et al.Object recognition and segmentation using SIFT a-nd Graph Cuts[C].Proceedings of the 19th International Conference on Pattern Reco-gnition,2008:1-4.

[3] 陈立潮,牛玉梅,潘理虎,等.Snake模型的研究进展[J].计算机应用研究,2014,31(7):1931-1936.

[4] Michael Kass,Andrew Witkin D T.Snake:Active contour models[J].Internatio-nal Journal ofComputer Vision,1988,1(4):321-331.

[5] 董春利,董育宁,刘杰.基于粒子滤波和GVF-Snake的目标跟踪算法[J].仪器仪表学报:2009,30(4):828-833.

[6] Cheng Y Z.MeanShift,model seeking,a-nd clustering.IEEE Transactions on Pattern Analysis and Machine[J].Intelligence,1995,17(8):790-799.

[7] 闫钧华,陈少华,艾淑芳.基于 Kalman 预测器的改进的 CAMShift 目标跟踪[J].中国惯性技术学报,2014,22(4):536-542.

[8] Zhang R,Zhang S,Yu S.Moving objects detection method based on brightness d-istortion and chromaticity distortion [J].Consumer Electronics,IEEE Transactions on,2014,53(3):1177-1185

[9] 王泽楷,吴黎明,蔡文.基于Camshift改进算法的视频目标跟踪方法[J].自动化与信息工程,2014,35(1):27-31

[10] Liu R M,Li X L,Han L,et al.Track infrared point targets based on projection coefficient templat-es and non-linear correlation combined with Kalman prediction[J].Infrared Physi-cs & Technology,2013,57(3):68-75.

[11] 袁胜智,谢晓芳,李洪周.一种基于Kalman-mean shift 的自适应跟踪算法[J].激光与红外,2009,39(5):558-561

[12] 黄晓丽,杨国为,吴少龙.一种改进的Cams-hift和Kalman相结合的运动目标跟踪算法[J].工业控制计算机,2016,29(1):80-81.

(责任编辑李超)

AnalysisandImprovementofPredictiveTrackingAlgorithmbasedonCam-shiftMethod

LIU Zhen-yu,ZHANG Bai-ying

(SchoolofInformationScienceandEngineering,ShenyangUniversityofTechnology,Shenyang110870,China)

In order to finish the position tracking of the moving target accurately in complex backgrounds which have occlusion interference,the article has studied Kalman filter combined with Cam-shift algorithm.Using Kalman filter could make the prediction of moving target more accurate and speed,when combined with the Cam-shift algorithm could achieve good tracking.On this basis,then proposed a new tracking algorithm based on linear prediction and Cam-shift algorithm,the linear prediction method is used as filtering estimation to instead of Kalman filter,and the prediction results would be substituted into Cam-shift estimation algorithm for tracking.The experimental results show that the method can not only ensure the accuracy of tracking,but also reduce the iteration time.

cam-shift;kalman filter;linear prediction;moving target tracking;position prediction

2017-02-20

辽宁省自然科学基金(2015020162)

刘振宇(1973-)，男，辽宁瓦房店人，博士，副教授，从事视觉伺服、模式识别的研究.

TN 912

1000-5846(2017)03-0234-07