基于改进的颜色和SURF特征的粒子滤波目标跟踪

金志刚，卫津津，罗咏梅，刘晓辉

1.天津大学电子信息工程学院，天津300072

2.天津大学计算机科学与技术学院，天津300072

3.国家计算机网络应急技术处理协调中心，北京100029

基于改进的颜色和SURF特征的粒子滤波目标跟踪

金志刚1，卫津津1，罗咏梅2，刘晓辉3

1.天津大学电子信息工程学院，天津300072

2.天津大学计算机科学与技术学院，天津300072

3.国家计算机网络应急技术处理协调中心，北京100029

针对视频中运动目标的准确跟踪问题，提出了一种改进的颜色直方图特征和SURF特征的粒子滤波跟踪算法。采用SURF算法提取特征点，利用分层迭代的KLT算法对特征点进行稳定跟踪。将SURF特征与改进的视觉显著性颜色特征进行乘性融合，作为粒子滤波的观测概率。针对跟踪过程中SURF匹配数下降和不稳定的现象，设计了SURF特征模板集的更新策略。与传统特征的跟踪进行多组对比实验，其结果证明了该方法对光照和遮挡具有很好的鲁棒性，对目标跟踪的准确率更高。

目标跟踪；视觉显著性；颜色直方图；加速鲁棒特征（SURF）；粒子滤波；KLT算法

1　引言

目标跟踪是绝大多数视觉系统中不可或缺的环节，同时也是计算机视觉和模式识别领域的热点问题，在人机交互、机器人导航、智能视频监控等方面有广泛的应用。为了实现准确、稳定的目标跟踪，许多学者已经提出不同的跟踪算法［1-3］。作为运动目标跟踪方法的常用数学工具，粒子滤波（Particle Filter）对运动模型的非线性、非高斯、多峰等问题表现出良好的适应性，已被大量应用于行人、车辆等运动目标的跟踪［4-8］。

粒子滤波需要建立目标的观测模型，为了提高跟踪的鲁棒性，多种类型的特征被用来表征目标。文献［3-7］中算法大都是提取目标的颜色、纹理、运动等一种或多种特征，虽然一定程度上能够完成对目标的跟踪，但对目标的特征描述并不完备，无法适应目标和背景的变化。Tang等［8］提出了结合Mean-shift和粒子滤波的算法，该算法虽然对目标跟踪有很好的鲁棒性，但在目标遮挡以及相邻帧出现较大的目标位移时，受Mean Shift算法搜索区域的限制，跟踪会出现发散现象；Hossain等［9］利用SIFT（Scale Invariant Feature Transform）局部不变特征实现对目标的跟踪，由于图像的局部区域特征具有对光照、尺度、旋转的不变性，因此以局部不变特征表征目标进行跟踪效果比较好，但SIFT特征匹配计算复杂，无法满足实时跟踪的要求。近年来，SURF（Speeded Up Robust Features）［10］、RIFF（Rotation Invariant Fast Features）［11］、BRIEF（Binary Robust Independent Elementary Features）［12］等各种角点提取和描述算法陆续被提出，文献［13］对这几种优秀的特征点检测算法进行了综合性能比较，在旋转测试、模糊测试等方面，SURF的综合性能占优势。SURF算法借鉴SIFT中简化近似的思想，对DoH（Determinant of Hessian）中的高斯二阶微分模板进行近似简化，计算速度提高了3倍。如果对视频的每一帧都进行特征点检测，会消耗较长时间，这时基于相邻帧连续信息的特征光流法进行跟踪会更加快速有效。本文选用KLT（Kanade-Lucas-Tomasi）［14］来实现对特征点的匹配，文献［15-16］中是利用属于光流法的KLT算法实现对目标跟踪。

以上述内容为基础，本文提出基于SURF算法和KLT匹配算法，获取特征点匹配结果，结合颜色直方图特征，作为粒子滤波模型中的观测函数，同时设计了特征点更新策略，最终实现对连续稳定的视频中目标进行准确跟踪。

2　颜色特征与SURF局部特征

为避免对目标的特征提取中背景区域过多而引入噪声，本文在获取矩形窗口后，利用最小二乘法使用椭圆拟合目标形状。

2.1目标显著性颜色特征

颜色直方图法［17］计算简单且便于实现，对运动目标形变、目标的平面旋转、非刚体以及部分遮挡有较强的鲁棒性，本文基于目标形状拟合的椭圆区域，在HSV空间定义目标的颜色直方图。

其中，num（color（k））为第k种颜色的数目。sum（Pixel）代表图像区域的总像素数。对视频做视觉显著性分析［18］，有助于实现目标的分割、识别和检索。定义显著性加权颜色直方图为：

其中，SM为图像的视觉显著图，sum（SM（color（k）））是颜色为color（k）的像素处的视觉显著值之和，sum（SM）为视觉显著图中所有元素之和。

2.2特征点提取与匹配

2.2.1SURF特征点提取

SURF算法在SIFT基础上做了许多改进，对DoH算法中的高斯二阶微分模板进行简化，通过采用不断增大盒状滤波模板尺寸的间接方法，逐步放大的近似高斯滤波器对输入图像的积分图像做卷积操作形成尺度空间。然后使用Hessian矩阵［19］进行特征点检测，其中用盒状滤波模板对卷积计算做近似估计，以提高速度，可得到近似的Hessian矩阵行列式：

以此表示某像素点x处的角点响应值。其中，Dxx，Dxy，Dyy分别是二阶偏导滤波器的近似估计。遍历图像中所有像素点，形成某一尺度下特征点检测的响应图像。使用不同的模板尺寸形成多尺度角点响应的图像后，将所有小于预设极值的角点响应值舍弃。利用非极大值抑制方法，得到稳定的特征点位置及尺度值。

2.2.2KLT特征点匹配

利用SURF算法提取特征点后，一般采用距离准则进行匹配，但这需要求取特征点的SURF特征描述子，该方法非常耗时，不适合用于实时跟踪。KLT算法是一种基于最优估计的匹配方法，以待跟踪窗口H×W在视频图像帧间的灰度差平方和（SSD）作为度量的跟踪算法。该算法利用每个特征点周围小窗口的局部信息之间的相似性度量进行最优估计，耗时较少。因此，本文选用改进的KLT算法对特征点进行匹配。

（1）KLT算法理论

KLT算法假设了一个包含特征纹理信息的窗口区域H×W，用一个平移模型描述特征窗口内的像素点变化，t时刻的图像帧I（x，y，t）和t+τ时刻的图像帧I（x，y，t+τ）满足如下关系：

运动量d=（Δx，Δy）为点（x，y）的偏移，该算法就是将运动参数的问题转化为找到使SSD函数（用ε表示）最小化的特征窗口位移d，假设给定两幅图像I和J，定义ε为：

其中H×W表示特征窗口，ω（X）是加权函数，通常为1。d是远小于X的量，故可将J（X+d）进行泰勒展开，去掉高次项，只保留前两项，g是泰勒展开的一阶泰勒系数，然后根据式（5）对d求导，最终化简得：

式中，d表示特征窗口中心的平移，dk表示第k次牛顿迭代法计算得到的d值。迭代计算d需要初始估计值d0，本文初始迭代值设为0。

（2）改进的KLT算法

KLT算法匹配耗时少，精度高，适合于目标运动速度小，帧间位移较小的情况。但当目标快速运动时，帧间位移很大，小窗口匹配容易漏匹配，而选择大的窗口，匹配精度会下降。因此，需要对上述KLT匹配算法进行分层迭代匹配。

首先根据高斯金字塔分解，对图像I和J分别进行精度递减的L层金字塔分解，可得到Il和Jl（其中l= 0，1，…，L），初始化=0，n=0，令l=L，n=n+1，根据公式（7）得到，判断迭代次数是否达到规定要求或精度是否满足要求，然后判断若l=0则结束，最终令。

经上述分层迭代后，选择小的搜索窗口，通过不断将高分辨率层的迭代结果作为低分辨率层迭代的初始值继续进行迭代，到最低层为止，可大大提高目标作快速运动时的特征点匹配精度。

3　基于颜色和SURF特征的粒子滤波跟踪

获取目标的视觉特征后，目标的跟踪可以视为状态估计问题，即根据目标在前一帧的状态信息估计其当前帧的状态。粒子滤波［20］又称序列化的蒙特卡罗方法，以蒙特卡罗随机模拟理论为基础，将系统状态的后验分布用一组加权的随机样本近似表示，新的状态通过这些随机样本的贝叶斯递推估计。

其中Zk表示目标模板的观测状态。k时刻目标的估计状态由式（9）计算得出。

3.1粒子跟踪初始化

选定跟踪目标以后，首先初始化目标模板状态和粒子点集。目标状态的粒子表示为：［x，y，a，b］，其中（x，y）是椭圆窗口的中心坐标，a和b分别表示椭圆窗口的长、短轴。设定粒子数目N，N个粒子的权重初始化为。在目标初始状态附近随机分布粒子状态参数，得到初始时刻0的粒子集2，…，N｝。

粒子运动模型采用二阶自回归模型：

其中，Ut-1是4元随机高斯噪声，高斯分布均值为0，方差与目标尺度相关。C=｛C1，C2，C3，C4｝表示粒子的随机传播半径。

3.2计算观测概率

粒子观测是指将新捕获的图像信息表示为观测值，并计算状态更新后的粒子与目标模板的相似程度，用观测概率更新粒子的权值。

3.2.1颜色观测概率

采用Bhattacharyya距离衡量目标模板和候选区域（粒子i=1，2，…，N）的显著性颜色直方图相似距离。

3.2.2SURF特征观测概率

在跟踪窗口的相邻区域（基于上一帧窗口位置选择3H×3W邻域范围）寻找匹配的SURF特征点，得到数目为M的匹配SURF特征模板集。对于某个粒子i，计算落入粒子区域（粒子i=1，2，…，N）中的匹配特征点的个数m。定义SURF观测概率：：

3.2.3联合的观测概率

本文采用乘性融合框架，获得目标的最终观测概率如下：

3.3粒子权重更新

3.4目标状态估计

估计目标状态是指通过估计运动目标的状态参数和粒子状态参数的加权。

其中，［xt，yt，at，bt］i是t时刻粒子i的状态，是t时刻粒子i的权重。加权求和后的状态参数即为目标当前帧的状态估计，获得目标的位置和尺寸，从而完成对当前帧的跟踪。

本文实现的粒子滤波跟踪基本流程如图1所示。

图1　粒子滤波跟踪流程

3.5模板更新和SURF特征点更新

受光照、运动形态的变化，目标的颜色特征和SURF特征点集也会产生变化。因此，需要以一定的时间间隔对目标模型进行更新，通过扩展椭圆跟踪窗口，使其包含一定的背景区域，做显著性检测和分割，使用分割出的目标区域拟合出椭圆外接窗口，同时基于新的窗口区域重新计算模板颜色直方图。另外，本文设计的SURF特征点集的更新包括增加特征点、删除特征点和更新特征点三个方面，具体方法如下：

（1）对于模板中的SURF特征点，定义一个权值K，初始化为1。模板特征点集定义为Sm=｛fi，Ki|i=1，2，…，F｝。使用模板对t时刻的目标进行跟踪时，通过状态估计获取目标新的状态估计，使用新的目标窗口区域中的SURF对模板特征集进行更新。如果匹配的特征点数与模板总特征点的比值小于某个阈值，则SURF特征集不进行更新。

（2）模板特征集中没有匹配的那些特征点，权值K值减少1，如果K≤x1，则从模板集中删去（x1为变量，x1≤0）。

（3）模板中与新的目标窗口中匹配的那些特征点，使用新的窗口中相应的特征点对其特征矢量进行更新，同时K加1。设定一个变量x2（x2＞1），如果K≥x2，该特征点将永久保留。

（4）将新的目标窗口中出现的，但没有匹配的SURF也加入特征点集S，作为新增加的特征点，设置权值K= 1，并保存目标窗口尺寸、中心坐标和该特征点坐标。

其中，参数x1，x2的设置对SURF特征集的有用性和冗余性会产生关键的影响，因此本文通过实验选择合适的参数x1，x2。采用Crowd_PETS09跟踪数据库中的视频（#S2#L1）和L1_BPR的car两段视频进行实验，实验视频如图2所示，红色矩形标注的为用于更新特征集的目标。

图2　用于参数选择的实验视频

先假设x2为一个不变大数，模板集的平均总数和平均每帧正确匹配点数随x1变化如表1所示。

表1　模板集规模和平均匹配数随参数x1变化

由结果可以看出，随着x1的增加，虽然模板集规模在变大，但是平均正确匹配数并没有明显的增加。x1的选择实质上是增加了前些帧没有正确匹配的特征点，而模板集规模的增加，容易导致误匹配的增加，因此选择参数x1=0，即只将前1帧没有正确匹配的特征点加入模板集。确定x1=0后，调整x2的大小，获得模板集规模和平均正确匹配数的变化如表2所示。

表2　模板集规模和平均匹配数随参数x2变化

从表2中看出，随着参数x2的增加，模板集的规模和平均正确匹配点数都有所下降。x2=2显然是不可取的，模板集总数会一直增加。设置x2的实质是保存那些能够连续正确匹配的特征点，本文选择x2=4。

4　实验结果及分析

本文提出了基于颜色特征和SURF特征的粒子滤波跟踪算法。为了验证显著性特征的跟踪效果，将本文算法与传统的基于颜色直方图的粒子滤波跟踪（Color based Particle Filter tracking，Color PT）相比较。

4.1实验环境

实验环境和实验参数如下：笔记本电脑Acer-4741g，Intel CoreTMi5 CPU@2.53 GHz，内存2 GB；操作系统为Windows XP Professional，SP2；仿真软件采用Matlab R2010b和Microsoft VC++2008以及opencv2.3视觉库。目标的初始位置通过手工的方式给出，粒子数目N设为200；初始分布为均匀分布U（x）=1/N。本文采用的视觉显著图生成算法为LC［21］。

4.2实验结果

为了验证本文方法的效果，本文进行了以下几组实验。实验1为了验证算法对遮挡和类似目标影响的鲁棒性；实验2为了验证算法对光照变化的鲁棒性。

实验1遮挡对算法的跟踪性能影响。测试视频采用CAVIAR的视频序列（OneLeaveShopReenter2cor，分辨率384×288）。其中图3（a）显示的是使用颜色直方图粒子跟踪的结果，可以看出，从193帧开始，跟踪行人开始被走廊中新出现的行人遮挡，而且具有相似的颜色特征，基于颜色特征的粒子滤波跟踪从此开始失效，一直持续到视频第400帧附近。而本文提出的跟踪算法（如图3（b））由于利用了SURF特征匹配，其对伸缩、旋转、光照等具有不变性的特点，弥补了颜色特征的不足，另外，基于粒子滤波的方法能够对下一时刻的目标进行预测，使其在遮挡结束后能够准确找到原来的跟踪目标。该视频序列具有人工标定的运动目标位置和尺寸信息，图3（c）计算出了跟踪过程中估计的目标中心与手工标定的目标中心的距离。从跟踪准确性看，本文方法明显优于仅使用颜色直方图的粒子滤波跟踪。

实验2两种算法在明显光照变化下的跟踪效果比较。如图4所示，在ETH的测试序列（sunny_day-img-left，分辨率640×480）中的目标进行跟踪。使用CPT的跟踪从101帧开始，由于光照的变化跟踪明显开始不稳定；到286帧（如图4（a）的第三幅图像），CPT跟踪了错误的目标，一直到第350帧以后跟踪才逐步正常。而本文所提的方法跟踪效果如图4（b）所示，结合SURF特征提取方法弥补了基于颜色直方图特征对目标跟踪的缺点，基本上没有受到光照的影响，跟踪稳定性明显好于CPT。

图3　视频OneLeaveShopReenter2cor的实验结果

图4　视频ETH（sunny_day-img-left）的跟踪结果

在粒子数目有限的前提下，由于粒子的随机分布和运动的随机性，粒子滤波跟踪并不是完全稳定的跟踪。为了定量地衡量算法的效果，对两次实验分别做5次独立重复实验，计算跟踪的平均失败帧数。跟踪失败的定义为：真实状态与估计状态的重合程度低于50%，即基本上偏离了目标。表3是重复实验得到的两次跟踪实验中平均失败帧数。

表3　两个实验场景中对目标的跟踪结果

经过大量的实验发现，本文跟踪算法对行人目标具有良好的跟踪效果，特别是对于目标被遮挡、光照变化等情况也能够实现较为准确的跟踪。由于跟踪计算量和耗时的因素主要包括跟踪窗口的大小、粒子数目和特征的计算复杂度。本文通过利用改进的KLT算法，对特征点进行匹配，与通常利用距离的特征点匹配算法相比，在处理速度上有所提高，实验1中平均每帧的处理时间为0.067 s，实验2中平均每帧的处理时间为0.071 s，能够较好地满足实时处理的要求。

5　结论

跟踪目标的尺度、形状变化，遮挡，光照变化等都影响视觉跟踪的鲁棒性，本文在粒子滤波框架下，提出了改进的视觉显著性颜色直方图和SURF特征联合跟踪的方法，其中对SURF特征点的匹配是利用了改进的分层迭代KLT特征匹配方法，大大提高了特征点匹配的速度。针对快速运动的目标，SURF特征匹配中可能出现的匹配数目急剧减少的问题，提出一种SURF特征集的更新策略，并通过实验验证了本文所提方法在跟踪速度和跟踪准确度方面，较Color PT方法都有所提高。

［1］Shiina Y，Ikenaga T.Recovery method based particle filter for object tracking in complex environment［C］//Signal& Information Processing Association Annual Summit and Conference（APSIPA ASC），Hollywood，CA，2012：1-4.

［2］吴垠，李良福，肖樟树，等.基于尺度不变特征的光流法目标跟踪技术研究［J］.计算机工程与应用，2013，49（15）：157-161.

［3］Jiang Zhengqiang，Huynh D Q，Moran W，et al.Multiple pedestrian tracking using colour and motion models［C］// Digital Image Computing：Techniques and Applications（DICTA），2010：328-334.

［4］Ying Hongwei，Qiu X，Song Jiatao，et al.Particle filtering object tracking based on texture and color［C］//Intelligence Information Processing and Trusted Computing（IPTC），2010：626-630.

［5］陈金广，马丽丽，陈亮.基于边缘粒子滤波的目标跟踪算法研究［J］.计算机工程与应用，2010，46（28）：128-131.

［6］Pérez P，Vermaak J，Blake A.Data fusion for tracking with particles［J］.Proceedings of the IEEE，2004：495-513.

［7］Li P，Chaumette F.Image cues fusion for object tracking based on particle filter［C］//Int’l Conf Articulated Motion and Deformable Objects，2004：99-107.

［8］Tang Da，Zhang Yujin.Combining mean-shift and particle filter for object tracking［C］//Image and Graphics（ICIG），Hefei，Anhui，2011：771-776.

［9］Hossain K，Oh Chi-min，Lee Chi-Woo，et al.Multi-part SIFT feature based particle filter for rotating object tracking［C］//Informatics，Electronics&Vision（ICIEV），2012：1016-1020.

［10］Bay H，Tuytelaars T，Gool L V.SURF：Speeded up robust features［C］//Computer Vision-ECCV 2006，2006：404-417.［11］Takacs G，Chandrasekhar V，Tsai S，et al.Unified realtime tracking and recognition with rotation-invariant fast features［C］//IEEE Computer Conference on Computer Vision and Pattern Recognition（CVPR），San Francisco，CA，2010：934-941.

［12］Calonder M，Lepetit V，Strecha C，et al.BRIEF：binary robustindependentelementaryfeatures［C］//Computer Vision-ECCV 2010，2010：778-792.

［13］Khvedchenya E.Feature descriptor comparision report［R/OL］.［2012-08-18］.http：//computer-vision-talks.com/.

［14］Tomasi C，Kanade T.Detection and tracking of point features，Carnegie Mellon University Technical Report CMUCS-91-132［R/OL］.［1991］.http：//www.lira.dist.unige.it/teaching/ SINA/slides-current/tomasi-kanade-techreport-1991.pdf.

［15］Gong J，Liu F Q，Song C L，et al.Research on the moving vehicle detection algorithm based on the motion vector［J］.Advances in Intelligent and Soft Computing，2012，127：41-49.

［16］刘玉，王敬东，李鹏.一种基于SIFT和KLT相结合的特征点跟踪方法研究［J］.宇航学报，2011，32（7）：1618-1625.

［17］Yang Hanxuan，Shao Ling，Zheng Feng，et al.Recent advances and trends in visual tracking：a review［J］.Neurocomputing，2011，74（18）：3823-3831.

［18］Montabone S，Soto A.Human detection using a mobile platform and novel features derived from a visual saliency mechanism［J］.Image and Vision Computing，2010：89-94.

［19］王永明，王贵锦.图像局部不变性特征与描述［M］.北京：国防工业出版社，2010.

［20］胡仕强，敬忠良.粒子滤波原理及其应用［M］.北京：科学出版社，2010.

［21］Achanta R，Hemami S，Estrada F，et al.Frequency-tuned salient region detection［C］//IEEE Int’l Conf Computer Vision and Pattern Recognition（CVPR），2009：1597-1604.

Targets tracking based on improved color histogram and SURF features using particle filter.

JIN Zhigang1，WEI Jinjin1，LUO Yongmei2，LIU Xiaohui3

1.School of Electronic Information Engineering，Tianjin University，Tianjin 300072，China
2.School of Computer Science and Technology，Tianjin University，Tianjin 300072，China
3.National Computer Network Emergency Treatment Coordination Center，Beijing 100029，China

In order to track moving targets of video exactly，a novel tracking scheme is proposed using particle filter based on improved color histogram features and Speeded Up Robust Features（SURF）.SURF algorithm is applied to extracting features.The features are tracked stably by the hierarchically iterative matching of the Kanade-Lucas-Tomasi（KLT）matching algorithm.Based on fusion mode of multiplicative weights，the SURF and improved saliency weighted color histogram are used to the joint observation probability.Meanwhile，for avoiding the drop of SURF matching numbers and the instability in tracking process，a SURF feature-point-set update method is presented.Through using multi-group experiments，the results demonstrate that this approach has great robustness for either sunlight or block and has high accuracy in tracking. Key words:target tracking；visual saliency；color histogram；Speeded Up Robust Features（SURF）；particle filter；KLT algorithm

A

TP391

10.3778/j.issn.1002-8331.1310-0297

国家高技术研究发展计划（863）（No.2009AA01A336）。

金志刚（1972—），男，教授，博士生导师，研究领域为网络与信息安全，图像/视频处理；卫津津（1987—），通讯作者，女，博士研究生，研究领域为模式识别，视频图像处理；罗咏梅（1974—），女，工程师，研究领域为计算机网络技术与应用；刘晓辉（1986—），男，博士生，研究领域为模式识别，视频图像处理。E-mail：weijin525@163.com

2013-10-23

2014-01-16

1002-8331（2015）22-0193-06

CNKI网络优先出版：2014-03-18，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1310-0297.html