关于mean shift视频目标跟踪算法的设计与实现-中期报告

1、河北工业大学城市学院本科毕业设计(论文)中期报告 河北工业大学城市学院本科毕业设计（论文）中期报告毕业设计（论文）题目：基于Mean-Shift的视频目标跟踪算法的设计与实现专业（方向）：网络工程学生信息：学号：088302姓名：坎启娇班级：网络C081班指导教师信息：教师号：02019姓名：侯向丹职称：副教授报告提交日期：2012年4月30号1前言1.1选题的背景运动目标的检测与跟踪是应用视觉领域1的一个重要的课题。目标跟踪涉及到图像处理、模式识别、人工智能以及自适应控制多领域问题的综合解决，其中对于复杂背景（或环境）下的图像处理一直是视觉信息处理和理解的难点。在实际应用中，复杂的现场环境以

2、及跟踪应用的实时性要求，对算法都提出了更高的要求。因此，研究复杂背景下运动目标的检测和跟踪的课题有重要意义。本文的研究目的是建立一个视频图像监控系统，根据目标的运动方向，系统将目标锁定在视野中。目标跟踪是在一段视频序列中寻找与指定目标最相似的部分，是计算机视觉的一个重要研究内容。它在视频监控、人机界面、增强现实、基于目标的视频压缩等众多领域中有着广泛的应用。1.2运动目标跟踪算法1.2.1常见的运动目标跟踪算法目前视频目标跟踪方法大体上可以分为基于区域匹配的目标跟踪、基于轮廓的匹配跟踪、基于特征的匹配跟踪、基于模型的跟踪，以及基于运动特性的跟踪。下面详细介绍这五类算法。（1）基于区域匹配跟踪区

3、域匹配跟踪的基本思想是:预先通过人为的方法或图像分割的方法得到包含目标的模板，然后在后续的视频序列中运用相关匹配准则进行目标的匹配跟踪。决定区域匹配跟踪效果好坏最主要的因素就是匹配度量和搜索算法的选取。最常用的相关准则是平方和准则法（SSD）,颜色法、形状法等。优点:提取了较完整的目标模板，因此相对其它跟踪算法能得到更多的图像信息，当目标未被遮挡时跟踪精度咼且稳定，因而广泛应用于小目标的跟踪或对比度比较差的目标跟缺点:需要进行全图搜索，因此计算量较大。另外，如果目标由于旋转、光线及运动等原因发生变化，尤其是出现了大面积的遮挡现象时可能找不到匹配点而产生错误匹配，这是需要克服的问题之一。基于轮廓

4、匹配跟踪轮廓匹配跟踪基本思想是:提取运动目标的边缘轮廓作为模板，对后续的视频序列每帧图像都进行二值化并且根据图像信息自动连续地更新边缘轮廓并跟踪。常见的基于轮廓匹配的跟踪算法有:Kass在1987年提出的主动轮廓模型,又称为Snake模型;基于Hausdorff距离的轮廓跟踪算法3Snake模型是一种采用主动轮廓目标提取的动态算法，它基于二维样条函数的动态生长来实现边缘检测与连接。Snake模型在构造能量函数时考虑了主动轮廓线的内部能量、图像作用力产生的能量和外部限制力产生的能量，使初始轮廓在外力和内力的作用下向目标边缘轮廓逼近。Snake模型非常适合可变形目标的跟踪，如对运动细胞的跟踪。Os

5、her等人提出的基于水平集方法的主动轮廓模型，克服了Snake模型对初始轮廓选取的敏感问题，非常适合多目标跟踪。基于Hausdorff距离的轮廓跟踪算法通过计算Hausdorff距离来反映初始模板和当前目标各象素的匹配程度，它能够根据模板来对目标进行平移、缩放变换，提高了匹配的准确性。基于特征匹配跟踪无论是刚体运动目标还是非刚体运动目标，它们都存在各自的个体特征。视频序列相邻帧在较短的采样时间间隔内，这些个体特征在运动形式上具有平滑性和连贯性，因此可以用纹理、颜色、形状、灰度等个体特征来对运动目标进行跟踪。基于特征匹配跟踪采用运动目标的某些局部特征作为跟踪对象。优点：在目标被部分遮挡的情况下只

6、要被选取的特征未消失，仍可以实现跟踪。缺点：当目标运动状态比较复杂时，如非匀加速运动或曲线运动，此时目标的特征提取就比较困难；目标在运动过程中不可避免会存在遮挡或暂时消失的情况，此时简单的基于部分特征的方法就很难继续跟踪;如何选取运动目标最有效的特征也是难点之一。基于模型跟踪基于模型的跟踪就是通过先验知识来获得目标模型从而实现跟踪，通常目标模型有线图型、2D模型、3D模型。可采用长方体对车辆进行三维建模来获得车辆的运动速度。也可采用多摄像头来跟踪人体运动目标，对人体的3D模型进行运动估计，该方法基于时空域联合来分析人体的轮廓特征，在遇到大面积遮挡时仍能保持较好的跟踪效果。优点：既适合刚体目标跟

7、踪也适合非刚体目标跟踪，而且跟踪效果不受观测角度的影响。即使在复杂环境中，目标发生遮挡的情况下，利用模型的先验知识也可以较好地得到跟踪结果。缺点：由于运动分析的精度取决于几何模型的精度，而获得运动目标的精确几何模型非常困难；而且计算量大，实时性差，不太适合实时应用场合。基于运动特性的目标匹配跟踪基于运动特性的目标匹配跟踪实质上是一种运动预测的跟踪方法，根据目标的运动规律进行建模。把运动目标在较短时间间隔内运动描述为匀速直线运动或匀加速直线运动。通过建立的运动模型预测目标在下一帧中的位置，然后以这个位置为中心在附近的领域内搜索目标最佳位置。经典的运动估计算法有基于光流场、卡尔曼滤波、扩展卡尔曼滤

8、波、粒子滤波等。通过对目标的运动估计可以缩小目标的搜索范围，提高目标的跟踪速度，非常适合于实际应用。1.2.2基于Mean-Shift的目标跟踪算法本文重点介绍了特征匹配跟踪算法中的Mean-Shift跟踪算法。在众多的跟踪算法中,Mean-Shift算法由于其理论严格、实现简单和较好的跟踪性能，近年来受到广泛的关注。本文的主要研究对象就是基于Mean-Shift的目标跟踪算法。Mean-Shift算法是一种基于特征概率密度统计的建模方法。Mean-Shift算法用于视频目标跟踪时，采用目标的颜色直方图作为搜索特征，通过不断迭代Mean-Shift向量使得算法收敛于目标的真实位置，从而达到跟踪

9、的目的。在跟踪过程中，目标区域通常由用户在视频序列的第一帧中选定，并建立相应的目标直方图。根据Bhattacharyya相似度,Mean-Shift算法在后续帧中迭代地搜索目标模型的最佳候选区域。优点：（1）算法计算量不大，在目标区域已知的情况下完全可以做到实时跟踪；（2）采用核函数直方图模型，对边缘遮挡、目标旋转、变形和背景运动不敏感。缺点：（1）缺乏必要的模板更新；（2）跟踪过程中由于窗口宽度大小保持不变，当目标尺度有所变化时，跟踪就会失败；（3）当目标速度较快时，跟踪效果不好；（4）直方图特征在目标颜色特征描述方面略显匮乏，缺少空间信息；Mean-Shift算法主要是用在单张影像上。而C

10、am-shift算法利用Mean-Shift算法的方河北工业大学城市学院本科毕业设计（论文）中期报告河北工业大学城市学院本科毕业设计（论文）中期报告 法，对影像串联进行分析，是Mean-Shift算法的改进，称连续自适应的Mean-Shift算法4编程语言及编程环境编程语言：VC+、OpenCV编程环境：VisualStudio2008Mean-Shift算法Mean-Shift算法的基本思想Mean-Shift跟踪算法通常是基于目标区域的颜色概率分布直方图的。将颜色空间分成m个索引子空间，计算目标初始模板和候选区域的颜色概率分布直方图q=quu-1,2,，m初始模板与候选目标区域的相似度用u

11、-1_0（y）-Bhattacharyya系数来衡量，即其几何含义是m维单位矢量q和p（y）夹角的余弦值，显然当（y）越大时匹配程度就越高，即当前帧目标与初始帧目标最相似。因此对（y）求极值，即得到Mean-Shift向量：(公式1)m(xh,Gy-x20i-hxwgiii-1因此连y-x20i-hwgii-1-yo续的迭代y1-y0,将会收敛于局部极大值，即满足y1=y0的固定点，也就是说Mean-Shift是一个连续迭代过程，使达到当前帧目标最优位置。3.2Mean-Shift算法迭代步骤Mean-Shift算法是一种寻找局部极值的方法。作为一种直观上的理解是它一步一步爬向最高点即爬山算法

12、而怎么个爬法，用计算出的重心作为下一步窗口的中心，直到窗口的位置不再变化。下面从Mean-Shift向量的定义出发来讨论Mean-Shift算法具体计算步骤。首先对Mean-Shift向量（公式1）右边的第一项记为Mh,g（x），即y-x20ih9xwgiii=1M(x)二h,Gy-x20ihWgii=1（公式2）Mean-Shift算法就是按以下三个步骤连续迭代计算。（1）计算Mean-Shift向量Mh,g.（2）把Mh,g（x）的值赋给x.（3）判断是否满足Mh,g（X）一J，若是则结束循环，否则继续执行（1）。因此上面的步骤就是使Mean-Shift向量不断地沿着概率密度的梯度方向移动

13、，移动的步长不仅与梯度的大小有关也与该点的概率密度有关。在密度大的地方移动的步长小些，密度小的地方移动的步长就大些。Cam-Shift算法Cam-Shift算法，即“ContinuouslyAdaptiveMean-Shift”算法5是一种运动跟踪算法。它是一个基于Mean-Sift的改进算法。将Mean-Shift算法扩展到连续图像序列（一般都是指视频图像序列），这样就形成了Cam-Shift算法。它首次由GaryR.Bradski等人提出和应用在人脸的跟踪上，并取得了不错的效果。由于它是利用颜色的概率信息进行的跟踪，使得它的运行效率比较高。Cam-Shift算法原理Cam-Shift利用目

14、标的颜色直方图模型将图像转换为颜色概率分布图，初始化一个搜索窗的大小和位置，并根据上一帧得到的结果自适应调整搜索窗口的位置和大小，从而定位出当前图像中目标的中心位置。它主要通过视频图像中运动物体的颜色信息来达到跟踪的目的。我把这个算法分解成三个部分，便于理解：（1）BackProjection计算（2）Mean-Shift算法（3）Cam-Shift算法BackProjection计算计算BackProjection的步骤：（1）计算被跟踪目标的色彩直方图。在各种色彩空间中，只有HSV空间（或与HSV类似的色彩空间）中的H分量可以表示颜色信息。所以在具体的计算过程中，首先将其他的色彩空间河北工

15、业大学城市学院本科毕业设计（论文）中期报告河北工业大学城市学院本科毕业设计（论文）中期报告河北工业大学城市学院本科毕业设计(论文)中期报告 的值转化到HSV空间，然后对其中的H分量做直方图计算。根据获得的色彩直方图将原始图像转化成色彩概率分布图像，这个过程就被称作BackProjection。算法分析：直方图可以看作是一种概率分布图。在处理前，目标图像中的每一个象素的值描述的在这一点的颜色信息，而处理后，图像中每一个象素的值就变成了这个颜色信息出现在此处的可能性的一种离散化的度量，出现的可能性大，象素的值就大，反之则小。这样就为后面的匹配和跟踪提供了线索。Mean-Shift算法在讨论Mean

16、-Shift算法之前，首先讨论在概率分布图像中6如何计算某个区域的质心(MassCenter)的问题，质心可以通过以下公式来计算：计算区域内0阶矩for(inti=0;iheight;i+)for(intj=0;jwidth;j+)M00+=I(i,j);/I(i,j)为像素点值区域内1阶矩for(inti=0;iheight;i+)for(intj=0;jwidth;j+)M10+=i*I(i,j);M01+=j*I(i,j);则MassCenter为：X=M10/M00;Y=M01/M00(用1阶距除以0阶距)。Mean-Shift算法可以分为以下4步：选择窗的大小和初始位置.（2）计算此

17、时窗口内的MassCenter.（3）调整窗口的中心到MassCenter.（4）重复（2）和（3）,直到窗口中心“会聚”，即每次窗口移动的距离小于一定的阈值。Cam-Shift算法在了解了Mean-Sh辻t算法以后，我们将Mean-Sh辻t算法扩展到连续图像序列（一般都是指视频图像序列），这样就形成了Cam-Shift算法。Cam-Shift算法的基本思想是视频图像的所有帧作Mean-Shift运算，并将上一帧的结果（即SearchWindow的中心和大小）作为下一帧Mean-Shift算法的SearchWindow的初始值，如此迭代下去，就可以实现对目标的跟踪。整个算法的具体步骤分5步：（

18、1）确定初始目标及其区域；（2）计算出目标的色度（Hue）分量的直方图；（3）利用直方图计算输入图像的反向投影图；（4）利用Mean-Shift算法在反向投影图中迭代搜索7,直到其收敛或达到最大迭代次数。（5）从第（4）步中获得收索窗口的中心位置和计算出新的窗口大小，以此为参数，进入到下一帪的目标跟踪。（即跳转到第（2）步）；几点说明：（1）在输入图像进行反向投影图之前在HSV空间内做了一个阀值处理，用以滤掉一些噪声。（2）反向投影图则是概率分布图，在反向投影图中某一像素点的值指的是这个点符合目标的概率分布的概率是多少，或者直接说其为目标图像像素点的像素点是多少。计算方法为：根据像素点的像素值查询目标的直方图，其对应像素值的概率是多少就作为该点在反向投影图中的值。（3）在设定计算区域时，区域要略大于初始化的窗口/上一帧的跟踪窗口。目的是当目标变大或移动时，不会丢失目标颜色特征，提高算法有效性。下一步计划2012-05-05-2012-05-26完成算法，完成并提交论文初稿。2012-05-27-2012-06-02进一步完善算法，并修改整理论文，