河北工业大学城市学院本科毕业设计（论文）中期报告毕业设计（论文）题目：基于Mean-Shift的视频目标跟踪算法的设计与实现专业(方向)：网络工程学生信息：学号：088302 姓名：坎启娇班级：网络C081班指导教师信息：教师号：02019 姓名：侯向丹职称：副教授报告提交日期：2012年4月30号1.前言1.1选题的背景运动目标的检测与跟踪是应用视觉领域[1]的一个重要的课题。

目标跟踪涉及到图像处理、模式识别、人工智能以及自适应控制多领域问题的综合解决,其中对于复杂背景(或环境)下的图像处理一直是视觉信息处理和理解的难点。

在实际应用中，复杂的现场环境以及跟踪应用的实时性要求，对算法都提出了更高的要求。

因此，研究复杂背景下运动目标的检测和跟踪的课题有重要意义。

本文的研究目的是建立一个视频图像监控系统，根据目标的运动方向，系统将目标锁定在视野中。

目标跟踪是在一段视频序列中寻找与指定目标最相似的部分，是计算机视觉的一个重要研究内容。

它在视频监控、人机界面、增强现实、基于目标的视频压缩等众多领域中有着广泛的应用。

1.2运动目标跟踪算法1.2.1常见的运动目标跟踪算法目前视频目标跟踪方法[2]大体上可以分为基于区域匹配的目标跟踪、基于轮廓的匹配跟踪、基于特征的匹配跟踪、基于模型的跟踪,以及基于运动特性的跟踪。

下面详细介绍这五类算法。

(1)基于区域匹配跟踪区域匹配跟踪的基本思想是:预先通过人为的方法或图像分割的方法得到包含目标的模板，然后在后续的视频序列中运用相关匹配准则进行目标的匹配跟踪。

决定区域匹配跟踪效果好坏最主要的因素就是匹配度量和搜索算法的选取。

最常用的相关准则是平方和准则法(SSD),颜色法、形状法等。

优点:提取了较完整的目标模板，因此相对其它跟踪算法能得到更多的图像信息，当目标未被遮挡时跟踪精度高且稳定，因而广泛应用于小目标的跟踪或对比度比较差的目标跟踪。

缺点:需要进行全图搜索，因此计算量较大。

另外，如果目标由于旋转、光线及运动等原因发生变化，尤其是出现了大面积的遮挡现象时可能找不到匹配点而产生错误匹配，这是需要克服的问题之一。

(2)基于轮廓匹配跟踪轮廓匹配跟踪基本思想是:提取运动目标的边缘轮廓作为模板，对后续的视频序列每帧图像都进行二值化并且根据图像信息自动连续地更新边缘轮廓并跟踪。

常见的基于轮廓匹配的跟踪算法有:Kass在1987年提出的主动轮廓模型，又称为Snake 模型;基于Hausdorff距离的轮廓跟踪算法[3]。

Snake模型是一种采用主动轮廓目标提取的动态算法，它基于二维样条函数的动态生长来实现边缘检测与连接。

Snake模型在构造能量函数时考虑了主动轮廓线的内部能量、图像作用力产生的能量和外部限制力产生的能量，使初始轮廓在外力和内力的作用下向目标边缘轮廓逼近。

Snake模型非常适合可变形目标的跟踪，如对运动细胞的跟踪。

Osher等人提出的基于水平集方法的主动轮廓模型，克服了Snake 模型对初始轮廓选取的敏感问题，非常适合多目标跟踪。

基于Hausdorff距离的轮廓跟踪算法通过计算Hausdorff距离来反映初始模板和当前目标各象素的匹配程度，它能够根据模板来对目标进行平移、缩放变换，提高了匹配的准确性。

(3) 基于特征匹配跟踪无论是刚体运动目标还是非刚体运动目标，它们都存在各自的个体特征。

视频序列相邻帧在较短的采样时间间隔内，这些个体特征在运动形式上具有平滑性和连贯性，因此可以用纹理、颜色、形状、灰度等个体特征来对运动目标进行跟踪。

基于特征匹配跟踪采用运动目标的某些局部特征作为跟踪对象。

优点：在目标被部分遮挡的情况下只要被选取的特征未消失,仍可以实现跟踪。

缺点：当目标运动状态比较复杂时，如非匀加速运动或曲线运动，此时目标的特征提取就比较困难;目标在运动过程中不可避免会存在遮挡或暂时消失的情况，此时简单的基于部分特征的方法就很难继续跟踪;如何选取运动目标最有效的特征也是难点之一。

(4) 基于模型跟踪基于模型的跟踪就是通过先验知识来获得目标模型从而实现跟踪，通常目标模型有线图型、2D模型、3D模型。

可采用长方体对车辆进行三维建模来获得车辆的运动速度。

也可采用多摄像头来跟踪人体运动目标，对人体的3D模型进行运动估计，该方法基于时空域联合来分析人体的轮廓特征，在遇到大面积遮挡时仍能保持较好的跟踪效果。

优点：既适合刚体目标跟踪也适合非刚体目标跟踪，而且跟踪效果不受观测角度的影响。

即使在复杂环境中，目标发生遮挡的情况下，利用模型的先验知识也可以较好地得到跟踪结果。

缺点：由于运动分析的精度取决于几何模型的精度，而获得运动目标的精确几何模型非常困难；而且计算量大，实时性差，不太适合实时应用场合。

(5) 基于运动特性的目标匹配跟踪基于运动特性的目标匹配跟踪实质上是一种运动预测的跟踪方法，根据目标的运动规律进行建模。

把运动目标在较短时间间隔内运动描述为匀速直线运动或匀加速直线运动。

通过建立的运动模型预测目标在下一帧中的位置，然后以这个位置为中心在附近的领域内搜索目标最佳位置。

经典的运动估计算法有基于光流场、卡尔曼滤波、扩展卡尔曼滤波、粒子滤波等。

通过对目标的运动估计可以缩小目标的搜索范围，提高目标的跟踪速度，非常适合于实际应用。

1.2.2 基于Mean-Shift的目标跟踪算法本文重点介绍了特征匹配跟踪算法中的Mean-Shift跟踪算法。

在众多的跟踪算法中,Mean-Shift算法由于其理论严格、实现简单和较好的跟踪性能,近年来受到广泛的关注。

本文的主要研究对象就是基于Mean-Shift的目标跟踪算法。

Mean-Shift算法是一种基于特征概率密度统计的建模方法。

Mean-Shift算法用于视频目标跟踪时，采用目标的颜色直方图作为搜索特征，通过不断迭代Mean-Shift向量使得算法收敛于目标的真实位置，从而达到跟踪的目的。

在跟踪过程中,目标区域通常由用户在视频序列的第一帧中选定,并建立相应的目标直方图。

根据Bhattacharyya相似度,Mean-Shift算法在后续帧中迭代地搜索目标模型的最佳候选区域。

优点：（1）算法计算量不大，在目标区域已知的情况下完全可以做到实时跟踪；（2）采用核函数直方图模型，对边缘遮挡、目标旋转、变形和背景运动不敏感。

缺点：（1）缺乏必要的模板更新；（2）跟踪过程中由于窗口宽度大小保持不变，当目标尺度有所变化时，跟踪就会失败；（3）当目标速度较快时，跟踪效果不好；（4）直方图特征在目标颜色特征描述方面略显匮乏，缺少空间信息；Mean-Shift算法主要是用在单张影像上。

而Cam-shift算法利用Mean-Shift算法的方()0120120,y h x y g w h x y g w x x m k kn i i i n i i i i G h -⎥⎥⎦⎤⎢⎢⎣⎡-⎥⎥⎦⎤⎢⎢⎣⎡-=∑∑==法，对影像串联进行分析，是Mean-Shift 算法的改进，称连续自适应的Mean-Shift 算法[4]。

2. 编程语言及编程环境编程语言：VC++、OpenCV编程环境：Visual Studio 20083. Mean-Shift 算法3.1 Mean-Shift 算法的基本思想Mean-Shift 跟踪算法通常是基于目标区域的颜色概率分布直方图的。

将颜色空间分成m个索引子空间, 计算目标初始模板和候选区域的颜色概率分布直方图m u u q q ,,2,1}ˆ{ˆ⋅⋅⋅==和m u u y p y p,,2,1)}(ˆ{)(ˆ⋅⋅⋅==初始模板与候选目标区域的相似度用Bhattacharyya 系数来衡量,即()()∑==m 1u ˆˆˆu u q y p y ρ。

其几何含义是m 维单位矢量q ˆ和()y p ˆ夹角的余弦值，显然当()y ρˆ越大时匹配程度就越高，即当前帧目标与初始帧目标最相似。

因此对()y ρˆ求极值，即得到Mean-Shift 向量:（公式1） 因此连续的迭代y1->y0，将会收敛于局部极大值，即满足y1=y0的固定点，也就是说Mean-Shift 是一个连续迭代过程，使达到当前帧目标最优位置。

3.2Mean-Shift 算法迭代步骤Mean-Shift 算法是一种寻找局部极值的方法。

作为一种直观上的理解是它一步一步爬向最高点即爬山算法.而怎么个爬法，用计算出的重心作为下一步窗口的中心，直到窗口的位置不再变化。

下面从Mean-Shift 向量的定义出发来讨论Mean-Shift 算法具体计算步骤。

首先对Mean-Shift 向量（公式1）右边的第一项记为()x M G h ,，即()∑∑==⎥⎥⎦⎤⎢⎢⎣⎡-⎥⎥⎦⎤⎢⎢⎣⎡-=k k n i i i n i i i i G h h x y g w h x y g w x x M 120120, （公式2） Mean-Shift 算法就是按以下三个步骤连续迭代计算。

（1）计算Mean-Shift 向量()x M G h ,. （2）把()x M G h ,的值赋给x.（3）判断是否满足()ε<-i G h x x M ,，若是则结束循环，否则继续执行（1）。

因此上面的步骤就是使Mean-Shift 向量不断地沿着概率密度的梯度方向移动，移动的步长不仅与梯度的大小有关也与该点的概率密度有关。

在密度大的地方移动的步长小些，密度小的地方移动的步长就大些。

4. Cam-Shift 算法Cam-Shift 算法，即“Continuously Adaptive Mean-Shift ”算法[5]，是一种运动跟踪算法。

它是一个基于Mean-Sift 的改进算法。

将Mean-Shift 算法扩展到连续图像序列（一般都是指视频图像序列），这样就形成了Cam-Shift 算法。

它首次由Gary R.Bradski 等人提出和应用在人脸的跟踪上，并取得了不错的效果。

由于它是利用颜色的概率信息进行的跟踪，使得它的运行效率比较高。

4.1 Cam-Shift 算法原理Cam-Shift 利用目标的颜色直方图模型将图像转换为颜色概率分布图，初始化一个搜索窗的大小和位置，并根据上一帧得到的结果自适应调整搜索窗口的位置和大小，从而定位出当前图像中目标的中心位置。

它主要通过视频图像中运动物体的颜色信息来达到跟踪的目的。

我把这个算法分解成三个部分，便于理解：（1）Back Projection 计算（2）Mean-Shift 算法（3）Cam-Shift 算法4.1.1 Back Projection 计算计算Back Projection 的步骤：(1) 计算被跟踪目标的色彩直方图。

在各种色彩空间中，只有HSV 空间(或与HSV 类似的色彩空间)中的H 分量可以表示颜色信息。