基于meanshift算法的目标跟踪技术的研究.doc

《基于meanshift算法的目标跟踪技术的研究.doc》由会员分享，可在线阅读，更多相关《基于meanshift算法的目标跟踪技术的研究.doc（24页珍藏版）》请在三一办公上搜索。

1、 毕业论文（设计）题 目基于mean-shift算法的目标跟踪技术的研究院 系 专 业 电子信息工程 学生姓名 学 号 指导教师 职 称_二O 一 二 年 五 月 十 日目录摘 要2第一章 绪论31.1 课题研究背景及意义31.2 运动目标跟踪的国内外研究现状41.3 课题研究的主要内容及章节安排6第2章 Mean Shift理论72.1 引言72.2 密度估计概述82.3 参数密度估计82.4 无参密度估计82.4.1 无参密度估计的常用方法82.4.2 核密度估计原理92.4.3 核函数的选取92.5 Mean Shift理论102.5.1 多维空间下核密度估计理论102.5.2 密度梯度

2、估计和 Mean Shift 向量122.5.3 Mean Shift 算法的收敛性14第3章 Mean Shift目标跟踪算法163.1 引言163.2 Mean Shift算法的步骤173.2.1 目标模型描述173.2.2 候选模型描述173.2.3 目标相似性度量183.2.4 目标定位183.3 算法的具体实现203.4 目标尺度的自适应更新223.5 实验结果分析223.6 本章小结22参考文献23结论23致谢23基于mean-shift算法的目标跟踪技术的研究 摘 要：基于视频的运动目标跟踪是计算机视觉研究领域的一项必不可少的关键技术。Mean Shift算法是众多优秀的运动目标

3、跟踪算法之一。本文的主要研究内容为Mean Shift理论和传统的Mean Shift目标跟踪算法，Mean Shift算法采用核颜色直方图作为描述目标的模型，核函数的单峰性使得该算法对目标的部分遮挡或目标变形具有较好的鲁棒性，并且具有较好的实时性。本文介绍了Mean Shift的一些相关理论，如核密度估计理论等，解释了Mean Shift向量的概念，并对Mean Shift算法的收敛性进行了证明。在Mean Shift理论的基础上，本文详细描述了Mean Shift应用于目标跟踪的具体方法和步骤，同时提出了尺度自适应的更新策略，以满足跟踪过程中目标尺度的变化要求，还列出了Mean Shift

4、算法在各种不同情况下的实验结果及分析。关键词：Mean Shift，密度估计，核函数 第一章 绪论 1.1 课题研究背景及意义人类从外部世界获得的感官信息中，80%以上是来自于视觉。人们通过视觉能力从外界获取各种事物的图像信息，视觉系统将这些信息传递给大脑进行处理，产生含义异常丰富的视觉信息，然后大脑再理解这些视觉信息，从而指导人们进行各种相应的活动让机器人具有视觉是人类的一个梦想，机器拥有人类的视觉功能对世界产生的影响怎么估计大概都不为过。现实世界中的物体都是三维的，而人眼所获得的景物图像是二维的，人类的视觉系统能从二维图像中获得三维信息，从而感知三维世界。但是让机器拥有这样的能力却是非常困

5、难的事情。随着信号处理理论的发展和计算机的出现，人们似乎发现了一条模拟人类视觉的可行之路:用摄像机获取环境图像并转换成数字信号，用计算机通过数字图像处理的方法模拟人类对视觉信息处理的全过程，这样，就形成了一门新兴的学科计算机视觉。计算机视觉是一门综合性和学科交叉性很强的学科，它涉及图像处理、人工智能、模式识别、人工神经网络和数学等。其研究目标是使计算机具有通过二维图像认知三维环境的能力，这种能力将不仅使机器能够感知三维环境中的形状、位置、姿势等物体的几何信息，而且更重要的是能够对这些信息进行描述、存储、识别和理解。计算机视觉的研究始于20世纪50年代末，到80年代，计算机视觉的基本研究中取得了

6、重要进展，David Marr基于数学和神经科学领域的背景提出了比较完善的计算机视觉理论，首次从信息处理的角度综合了图像处理、心理物理学和神经生理学等学科的研究成果，提出了第一个较为完善的视觉系统框架。20世纪50年代从统计模式识别开始的，当时的工作主要集中在二维图像的分析和识别上，如光学字符识别，工件表面、显微图片和航空图片的分析和解释等。60年代Robesrt(1965)通过计算机程序从数字图像中提取出诸如立方体、楔形体、棱柱体等多面体的三维结构，并对物体形状及物体的空间关系进行描述。Rboerts的研究工作开创了以理解三维场景为目的的三维计算机视觉的研究。Rboerts对积木世界的创造性

7、研究给人们以极大的启发，许多人相信，一旦由白色积木玩具组成的三维世界可以被理解，则可以推广到理解更复杂的三维场景。70年代，已经出现了一些视觉应用系统。70年代中期，麻省理工学院(MIT)人工智能A(D实验室正式开设“计算机视觉，(Maehinevision)课程，由国际著名学者B.K.P.Horn教授讲授。同时，MITI实验室吸引了国际上许多知名学者参与计算机视觉的理论、算法和系统设计的研究，DvadiMarr教授就是其中的一位。他于1973年应邀在MTIAI实验室领导一个以博士生为主体的研究小组，1977年提出了不同于”积木世界”分析方法的计算视觉理论(computatofnalvisio

8、n)，该理论在80年代成为计算机视觉研究领域中的一个十分重要的理论框架。本文研究的是一种基于视频的运动目标跟踪算法Mean Shift算法。在计算机视觉的许多应用领域中，视频分析是一项重要的任务，视频分析一般分为几个关键步骤：感兴趣运动目标的区域检测、一帧一帧地对这些目标进行跟踪和对目标的运动轨迹进行分析以识别出他（它）们的行为，也可以简单地归结为运动、运动目标跟踪和行为分析。当前的目标检测分为两类:1.静止背景下的目标检测方法2.运动背景下的目标检测方法两类。1.静止背景下的目标检测和提取一般的智能视频监控系统往往是摄像头固定的(至少一个摄像头如此)，因此静止背景下的目标检测算法吸引了很多人

9、的目光。算法大体可以分为三类:帧差法背景差法，背景模型法。帧差法:利用视频序列中连续两帧图像取差得到差分图像，差分图像的区域仅仅是浙江大学博士学位论文:跟踪中的研究目标在前后帧可能存在的区域。然后对差分图像二值化，象素值大于事先确定的阀值时，认为该象素为前景象素，否则为背景象素。这样就确定出目标的所在区域。阀值的选择相当关键，选择过低不足以抑制图像中的噪声，过高则忽略了图像中有用的变化。这限制了它的使用。而且，如果目标本身的纹理均匀，运动缓慢，算法的结果不好。但它的优点也是显而易见而且诱人的:算法简单易行，计算量小。所以，人们也提出了许多改进的算法。背景差法:既然静止背景下的背景是静止不动的，

10、我们利用每一帧的图像和背景图像求差值，将结果图像进行二值化处理，不就检测出运动目标了吗?背景差法的原理即是如此。不过，在该算法中，静止背景图像被背景模型图像所取代。在一个长时间的目标跟踪系统中，背景不太可能不变。一天中光照的不同、场景中移入了新物体等都会引起背景象素值的变化。所以背景差法的难点在对背景模型的合理的更新。改进方法有统计平均法和IIR滤波法等。背景模型法:该方法与背景差法的区别在于该算法利用背景的参数模型来模拟背景图像的象素值，通过判断输入图像的各个象素值是否与这个模型项匹配来实现对目标的检测。当场景中有树枝的晃动、水面的波动等现象时，对背景建立数学模型能更好地描述背景的变化，比如

11、利用多个(一般3个)高斯模型组成的混合高斯模型来描述背景的变化，每个高斯模型的权值由该高斯模型的正确匹配频率决定。这种方法的计算量一般很大，用快速高斯变换可以加快算法的速度。其他的方法还有贝叶斯决策法和卡尔曼预测法。2.动态背景下的目标检测当摄像机由于本身或者运载平台的运动而发生运动时，会造成视频图像中的背景发生变化，从而形成动态背景。摄像头的运动是一种全局运动，即它造成的图像变化是一种全局变化，而且变化一致，因而可以用全局运动技术进行补偿，克服这种运动的影响。因此背景运动的参数是进行目标检测的关键参数，大部分算法都以此为突破口。对图像进行视频分割，获得运动目标。有两种方法可以完成动态背景下对

12、目标的检测。一种是借助于视频图像的运动估计和分割算法来实现，其典型算法是光流法;另一种是“图像匹配法”:首先将不同帧间的背景图像相互匹配，然后借助于静止背景图像下的视频监视算法完成目标的检测和提取。这类算法计算量大，无法使系统达到实时性要求，但是，对图像压缩领域而言，这类研究是很重要的。1.2 运动目标跟踪的国内外研究现状运动目标跟踪的目的是通过定位目标在视频每一帧中的位置或者目标在每一帧中所占据的目标区域，建立目标对象的位置、速度、颜色和形状以及轮廓等特征与图像序列之间的对应关系，从而产生出目标的运动轨迹。随着高计算能力的计算机、高质量的廉价摄像头和自动视频分析的需求增加，运动目标跟踪技术越

13、来越引起人们的兴趣和广泛的关注。运动目标跟踪是计算机视觉研究领域中的一个极具挑战性的课题。由于跟踪过程中遇到的诸多因素，对视频中的运动目标进行跟踪常常是很困难的。这些因素包括：1. 从三维世界到二维空间的映射造成的信息丢失；2. 图像中包含的各种噪声；3. 复杂的目标运动形式；4. 运动目标的非刚性特性；5. 复杂的目标性状；6. 场景背景或光泽等变化；7. 实时处理的要求；1.实时性好，算法要费时少，至少要比视频采集系统的图像帧的采集速率快，否则无法实现正常跟踪，如果系统的跟踪环节后面还有其他的图像处理环节，还要预留较多的时间给后面的处理，所以实时性至关重要。2.鲁棒性强，实际的观测环境，图

14、像的背景可能很复杂，光照、图像噪音及随时可能出现的对目标的遮挡均使目标的跟踪变得非常困难，这对算法的鲁棒性有很高的要求。这两条常难于同时满足，往往需要某种折衷，以得到较好的综合性能。计算机视觉的目的是实现计算机对人类视觉的模拟，而目标跟踪属于计算机视觉中的低层视觉范畴。说它低层，并不意味着它的算法简单，在复杂背景下的目标跟踪依然是一件非常困难的事情。目前的各种算法都是在某种针对性的环境或目标条件下有效，缺乏通用性。无论是视频监控、人机交互，还是更高级的视频系统，对感兴趣目标的跟踪往往是其中必不可少的重要环节，它为后面更高级的高级视觉提供有价值的信息。因此，对于视频序列目标跟踪算法的研究意义非常

15、重大，但也充满挑战。在实际的跟踪中，要同时避免上面列出的所有不利因素或同时解决这些因素所带来的问题是极其困难的。因此，在研究目标跟踪算法时总是会对目标的运动形式或者目标的外观等赋予一定的约束条件。例如，几乎所有的目标跟踪算法都假设目标的运动是相对平滑的，而不会长时间地剧烈变化。这些条件假设使得跟踪问题的研究在一定程度上得到简化，从而促进了国内外大量的研究机构和研究人员对这一课题积极的研究工作，取得了很多显著的成果，也基于各种假设条件提出了许多优秀的运动目标跟踪算法。对于目前国内外提出的各种运动目标跟踪算法，并没有一个可以依照的明确标准来对其进行分类。根据跟踪算法中目标表示方式的不同，可以大致将

16、其分为点跟踪、核跟踪和剪影跟踪等。点跟踪（Point Tracking）：点跟踪算法中，在连续的图像序列中检测出的目标对象是用一组点的集合来表示的，而且点与点之间的关联关系是建立在以前各帧所包含的目标位置和目标的运动情况等信息的基础上。点跟踪方法需要有一个外部目标检测机制对每一帧中的目标对象进行检测。在点跟踪中，目标跟踪问题化为建立各帧中检测到的目标对象之间对应关系的问题，检测到的目标对象采用一组点的形式来表示。点对应问题是一个非常复杂的问题，尤其是存在遮挡、误检、目标的出现和消失的情况下，会更为复杂。Sethi和Jain采用贪心算法基于临近性和刚性约束解决了点跟踪中的对应问题。 等人引入了

17、一般运动约束（ commonconstraints）来进行点对应，但不能对分布在孤立的向不同方向运动的目标上的点进行很好的对应。Broida和Chellappa则采用卡尔曼滤波器对噪声图像中的点进行跟踪。点跟踪方法总的来说可以分为两大类，一种是确定性方法，另一种是统计方法。确定性方法采用定性的运动启发法（qualitative motion heuristics）来进行点对应，而统计方法则考虑到目标度量和目标的不确定性来建立点之间的对应关系。点跟踪非常适合于很小的目标的跟踪问题，这些目标都可以采用简单的点来表示。核跟踪（Kernel Tracking）：核跟踪主要是采用目标的形状和外观信息，通

18、常采用矩形模板或者椭圆形区域结合直方图技术来表示目标。通过在连续的帧中计算核的运动来定位跟踪目标。核的运动常常以参数变换的形式来表示，如平移、旋转和仿射变换等。核跟踪算法依据目标的外观表示、跟踪目标的数目以及估计目标运动方法的不同分为两类，即模板与基于密度的外观模型和多视角外观模型。模板与基于密度的外观模型相对简单、计算复杂度低，因此，在许多领域中得到了广泛的应用。剪影跟踪（Silhouette Tracking）：运动目标常常具有复杂的形状，如手、头以及肩膀等，若采用简单的几何形状来表示整个目标，则不能很好地描述出这些形状的细节，而基于剪影的跟踪方法能够对目标的形状进行精确的描述。剪影跟踪的

19、目的是依据前帧中产生的目标模型，估计每一帧中目标所占的区域来达到跟踪的目的。这种方法常采用目标区域中蕴含的外观信息或密度信息，如颜色直方图以及形状模型，形状模型包括边缘图（edgemaps）或轮廓等形式。给定了目标模型，通过形状匹配或轮廓演化来对剪影进行跟踪。根据匹配原理的不同，也可以将跟踪算法分为基于模型的跟踪、基于区域的跟踪、基于特征的跟踪以及基于活动轮廓的跟踪。这些不同的算法致力于克服目标跟踪过程中的噪声干扰、遮挡情况以及复杂的背景运动等困难，提高目标跟踪的鲁棒性和准确性及目标跟踪的性能。基于模型的目标跟踪:基于模型的跟踪方法多用于非刚性物体的跟踪，如人体运动。人体运动具有姿势灵活多变的

20、特征，因此，常采用一些贴近人体形状的模型，例如对人体建立纸板模型。除此之外，对人体建立的模型还包括线图法、二维轮廓和三维立体模型等。基于区域的跟踪：基于区域的跟踪采用某种特定几何形状的区域表示目标对象，利用目标区域的颜色、边缘、纹理等信息完成对目标的跟踪。Comaniciu等人提出的Mean Shift算法就是利用目标区域的颜色直方图信息表示目标对象，然后通过计算Mean Shift向量使相似度函数最大化，从而匹配到最可能的目标区域作为真实的目标位置。基于特征的目标跟踪：对于基于特征的跟踪方法，选取合适的特征是十分重要的。总的来说，最期望所选特征具有这样的性质，即特征具有唯一性，以致能够很容易

21、在特征空间将不同的目标区分开来。特征选取和目标表示有着密切的联系，经常选用的特征包括颜色、边缘、光流、角点和纹理等。这些特征常常可以将运动目标与其他运动目标或背景区分开来，根据这些特征就可以达到目标跟踪的目的。目标跟踪应用中一个典型的目标特征是角点特征。角点是一类含有区分目标的足够信息且从当前帧和下一帧中均能提取出来的点。Harris在图像灰度强度的二阶导数的基础上提出了目标跟踪中最普遍使用的角点定义。这些角点信息具有很好的定位特性，通常能够有效地定位目标的整个结构范围。此外，只需要少量的角点特征就可以较好地达到目标定位的目的，使目标定位过程的计算量大大降低。基于活动轮廓的目标跟踪：基于轮廓的

22、跟踪采用一条封闭的曲线轮廓来表示目标对象，通过极小化一个以曲线函数为参数的能量函数实现对曲线函数的迭代更新，曲线的演化过程代表了目标轮廓的变化过程。该方法计算量小，实时性较好，但目标轮廓的初始化通常很困难，这在很大程度上限制了该方法的应用范围。随着大量研究人员在目标跟踪领域投入的大量时间和努力，目标跟踪技术发展很快，并开始由单摄像头单目标的跟踪逐渐转向更复杂的多目标和多摄像头的跟踪。多摄像头的跟踪研究在近几年也开始成为一个研究热点，而且同样产生了很多骄人的成果。综上所述，目标跟踪的研究正在一个迅速发展的过程中，研究人员提出的各种目标跟踪算法，它们各有自己的优势和缺点，而且大量的研究人员也正在针

23、对各种跟踪算法的缺点不断提出新的改进策略，甚至提出新的跟踪算法，目标跟踪领域的研究目前既可以说是“硕果累累”，又有着广阔的研究和发展空间，正处在一个充满活力的状态。1.3 课题研究的主要内容及章节安排第一部分主要研究基于核估计理论的传统Mean Shift跟踪算法。MeanShift跟踪算法是一种基于无参密度估计的算法，目前在目标跟踪、聚类分析、图像滤波及图像分割领域，有广泛的应用。主要内容包括Mean Shift算法的理论基础、Mean Shift算法的原理及算法的收敛性 第二部分主要研究传统Mean Shift跟踪算法的过程、Mean Shift跟踪的尺度自适应更新策略以及Mean Shi

24、ft应用于视频段的实验效果及分析等。在典型的运动目标跟踪算法中，目标表示和目标定位是一个核心问题，本文中详细阐述了Mean Shift算法采用的目标表示和目标定位方法。Mean Shift算法的目标模型的表示采用核颜色直方图作为目标特征，在后续帧中可能的目标位置以同样的方式计算目标候选模型的核颜色直方图，然后采用相似性度量函数计算出目标模型和目标候选模型的相似度，同时得到Mean Shift向量，即从当前初始位置向下一个候选位置偏移的向量，然后，用当前初始位置向量加上Mean Shift向量，就计算出了目标位置的下一候选位置。不断地重复迭代此过程，由于Mean Shift算法的收敛性，最终算法

25、会收敛于目标在当前帧中的真实目标位置。第1章为绪论，主要介绍了计算机视觉的相关发展状况、目标跟踪算法研究的研究意义和研究现状。在第2章中，详细介绍了Mean Shift理论，阐述了无参密度估计原理，尤其是核密度估计原理，以及Mean Shift算法的原理，并对Mean Shift算法的收敛性进行了数学证明。第3章对Mean Shift理论应用于目标跟踪过程的基本步骤，即目标模型表示、候选模型表示、相似度函数定义及目标定位，进行了详细的阐述。之后具体介绍了Mean Shift的具体实现方法，并列出了传统Mean Shift算法应用于视频的情况，并分别对实验结果进行了分析，说明了Mean Shif

26、t算法能够实现连续稳定的目标跟踪。第2章 Mean Shift理论2.1 引言Mean Shift这个概念最早是由Fukunaga和Hostetler于1975年在一篇关于概率密度梯度函数估计的文章中提出来的。这篇文献详细地解释了MeanShift的概念，即漂移的均值向量。然而，在Mean Shift概念提出后近20年的时间里并没有得到人们充分的重视，也因此未在各领域中得到广泛的应用。直到1995年，Yizong Cheng发表了另一篇关于Mean Shift峰值寻求和聚类的文章，Mean Shift算法才引起了广泛的关注。这篇文献中，Yizong Cheng引入了一族核函数，考虑了样本与被漂

27、移点的距离的大小和该样本的漂移量对样本均值漂移向量的贡献大小之间的关系，距离越大贡献越小，反之亦然。而且对不同的样本点赋予不同的权重，使得不同样本点的重要性不同。这两方面的推广大大扩展了Mean Shift算法的适用性。另外，YizongCheng还举出了Mean Shift应用于聚类分析和霍夫变换领域的例子。近年来，人们对Mean Shift算法进行了大量的研究工作，Mean Shift算法已经被成功地应用于许多领域，如聚类分析、目标检测、图像分割和目标跟踪领域等。Dorin Comaniciu和Peter Meer将MeanShift引入到灰度图像和彩色图像的联合空间-值域中，以进行图像平

28、滑和图像分割。此文献中提出图像滤波（平滑）算法将图像的每一个像素点与其最近的密度函数局部峰值点联系起来，而图像分割则将区域融合与附近的峰值点相联系。本章主要介绍Mean Shift的基本理论，包括核密度估计、密度梯度估计理论及Mean Shift算法的收敛性。2.2 密度估计概述运动目标检测和运动目标跟踪，是计算机视觉中重要的低层任务。要实现这些任务，首先需要解决的问题就是目标（或背景）的表示或特征描述问题，一种非常重要的目标表示方式是对目标的外观表象信息进行统计建模。统计建模的过程实质上是将目标的外观表象信息映射到特定的特征空间，获得的统计数据则是特征空间中的某个随机变量的观察值（样本点）。

29、于是，概率密度函数很自然地成为我们描述目标表象信息的一个很好的选择。从服从特定概率分布的一些样本数据点中获得特定的概率密度函数的方法即是密度估计过程。概率密度估计方法有两种：参数密度估计和无参密度估计。参数密度估计是假设特征空间中的特征值，即随机变量所服从的概率密度函数的形式是已知的，而函数中的某些具体参数的值是未知的。需要从在目标区域中提取的一系列特征值中估计出这些具体的参数值。这种密度估计方法称为参数密度估计方法。在很多实际的应用过程中我们很难得知一个随机变量所服从的概率分布的形式，因此，采用参数密度估计方法解决不了问题。而且即使是我们能够知道概率分布的形式，参数密度估计方法可能仍然不能很

30、好地获得估计结果，因为已知的概率密度函数的形式往往是单峰的函数，而很多计算机视觉实际应用中所涉及的概率密度分布是多峰的。此时，无参密度估计方法的优势就体现出来了。无参密度估计是一种统计方法，一般也称为非参数估计，可以在没有任何信息指导或理论约束条件的情况下，从数据中获得符合数据分布的密度函数形式。因此，无参密度估计过程没有与之相关的参数。下面我们对两种密度估计方法进行简单的介绍。2.3 参数密度估计参数估计的目的是从一组样本数据中寻求符合这些样本数据分布的概率密度函数。假设已知这些样本数据独立地取自服从某种形式的概率分布的一个总体，总体 X 的概率密度函数为 f ( x; )（ 是待估参数）。

31、要寻求符合样本数据分布的最优密度函数估计，也就是寻找 的一个最优估计值 。参数估计中最常用和最有效一种方法是最大似然估计。最大似然估计把待估计的参数看作是确定性的量，只是其取值未知。其本质思想是能够使得产生已观测到的样本的概率为最大的那个参数值便是最佳的参数估计值。设一组来自总体X 的样本数据X1X2，XN则X1X2，XN 的联合概率密度为ni=1f（Xi；），使得该式取得最大值的 即为最优估计在已知总体分布形式的情况下，参数估计可以很好地描述样本数据点的分布，是一个非常有力的估计工具。但由于它要求总体分布的形式是明确已知的，而在计算机视觉的实际应用过程中，这个条件常常是不能满足的，如果选用了

32、错误的密度函数形式，估计的准确性将难以保证。因此，参数估计的应用就受到了限制。正如前面我们提到的，无参密度估计不需要预先知道数据服从何种形式的分布，便可从数据中获得符合数据分布的密度函数。因此，在参数估计不适用的许多应用中，无参密度估计有很强的实用价值。2.4 无参密度估计2.4.1 无参密度估计的常用方法目前常见的无参密度估计方法包括：直方图估计、最近邻法和核密度估计。本文中的Mean Shift算法便是基于核密度估计理论的。直方图估计法的基本思想是把数据的值域划分成若干个相等的区间，数据按照区间分成若干个组，每组对应一个矩形，矩形的高度代表了划分到该组数据的个数，即矩形的高与该组中数据的多

33、少成正比，这些矩形依次排列就构成了数据的直方图。直方图法相对另外两种估计方法来说比较直观，但由于直方图中组的个数与数据的维数之间是指数的关系，在数据的维数较高时，直方图组的规模呈指数级增长，因此，直方图法只适用于数据维数不高的情形。最近邻法的核心思想是为了从n个样本数据中估计概率密度 p ( x )，以x为中心，进行体积扩张，直到包含进 k 个样本数据为止， k 是关于n 的某个特定函数。令Pn（x）=k/n/vn即可得到 x 处的密度估计值 p ( x )。最近邻法的缺点在于很容易受到噪声数据的影响。核密度估计是目前最常用的无参密度估计方法，它是在直方图估计的基础上引入了用于平滑数据的核函数

34、。对于一组采样数据，把这组数据的值域分成若干个相等的区间，每个区间称为一个bin ，数据按照这些区间划分成若干组，每组数据的个数与总的参样个数的比值就是每个 bin 对应的概率值。在此基础上再定义一个用于平滑的核函数。2.4.2 核密度估计原理为了说明核函数估计的原理，我们先对简单的一维的情况进行讨论。设Xii=1,n为一维欧几里得空间中的任意一组数据点，则由核函数 K ( x)和核窗半径h在数据点 x处计算出的核密度估计值定义为 (2-1)若取核函数 (2-2)则有 (2-3)其中， h 为核函数的带宽，且Kh（x）满足Kh（x）0，Kh（x）=Kh（-x），Kh（x）dx=1由于Kh（x）

35、=Kh（-x）即核函数Kh（x）关于中心点 0是对称的，因此，Kh（x-xi）关于点xi是对称的，也即xi为Kh（x-xi）的中心点。于是， (2-3)式可以解释为：概率密度函数的估计值即为以各个数据采样点为中心的核函数的平均值。2.4.3 核函数的选取在2.4.2 节中，我们已知核函数 K ( x )需要满足几个条件： K ( x ) 0，K ( x ) = K (- x)，K ( x )d x=1。可见核函数具有对称性、单峰性和有限局部支撑性。单峰性是指核函数的值从中心点开始向两侧迅速衰减到 0，有限局部支撑性是指，在核函数的窗宽h内，核函数的值大于 0，而在核函数的窗宽以外的数据点出，函

36、数值则为 0。满足这样的条件的函数有很多，目前实际应用中常用的核函数主要有：均匀核函数（Uniform）、伊潘涅切科夫核函数（Epanechnikov）、双伊潘涅切科夫核函数（Double Epanechnikov）、三角核函数（Triangle）、高斯核函数（Gaussian）、双权核函数（Biweight）和双指数核函数（Double Exponential）。这几种常用的核函数的具体形式如 图 2-1所示。2.5 Mean Shift理论2.5.1 多维空间下核密度估计理论在 2.4.2 节中，我们已经讨论了在一维空间中，如何采用核函数密度估计从一组采样的数据点中获得概率密度函数的估计。

37、但一维的情况只是我们为了说明核密度估计的原理而采用的简化手段。实际的应用过程中，尤其是计算机视觉领域的实际应用中，常常需要对多维空间中的一组采样数据点进行概率密度估计。因此，我们需要讨论多维空间中，如何采用核密度估计法对概率密度函数进行估计。多维空间下的核密度估计与一维空间的情况原理是相同的，只是需要将一维空间的核函数扩展到多维空间的核函数。多维情况下的核密度估计的数学描述：设Xii=1,n为 d 维欧几里得空间Rd中的任意一组数据点，可引入一个带宽矩阵 H ，则由核函数kH( x) 和带宽矩阵 H 在数据点x处计算出的核密度估计值定义为 （2-4）其中，kH( x) 为定义在Rd上的核函数。

38、其中， H 为一非奇异的带宽矩阵。一个需要考虑的问题是，在多维变量情况下，我们的核函数 K ( x )应该采取何种形式。多维变量情况下的核函数有两种生成方式，一种最简单的方法就是采用连乘（multiplicative）核函数（2-5）(2-5)式中的 K ( x )代表一维情况时的核函数。此时，(2-4)式变为：（2-6）另一种核函数生成方式是由一维变量核函数在空间Rd中旋转而得到，其形式为（2-7）Ks ( x) 是放射状对称的（Radial-Symmetric），标准化常数Skd保证Ks ( x) 的积分为 1。如 图 2-2和图 2-3 中所示是高斯核函数和双指数核函数在二维空间中的旋转

39、曲面。在计算机视觉应用中，更加关注这样一类放射状核函数，它们满足：（2-8）其中 k ( x )为 K ( x )的轮廓函数，且 x0，正的标准化常数Ck ,d保证 K ( x)的积分为1。另一个问题是带宽矩阵 H 采用何种形式。复杂的带宽矩阵虽然能够提高多维变量密度估计的灵活性，但是采用复杂的带宽矩阵会使计算变得繁杂。因此，在实际应用中，带宽矩阵 H 通常采用两种比较简单的形式，一种是对角矩阵H=diag h12， h22 ，.hd2，另一种是单位比例矩阵 H= hI的形式。显然，后一种形式的带宽矩阵更为简便，它只有一个参数h。若采用这样的带宽矩阵，则密度估计式(2-4)就变为密度估计的典型

40、形式：(2-9)将(2-8)式代入(2-9)中，得到(2-10)(2-10)式就是多维变量情况下通用的核密度估计式。2.5.2 密度梯度估计和 Mean Shift 向量通过核密度估计方法估计出概率密度函数后，我们要寻求概率密度函数的峰值（Mode），也即概率密度函数的最大值，它暗含了采样数据分布的最密集区域。在Mean Shift聚类分析中，也是通过寻求概率密度函数的峰值点来进行聚类的。为了找到概率密度函数的最大值，我们可以利用核密度估计式的可微性。由(2-10)式可以得到概率密度梯度的估计式(2-11)令g ( x )=-k ( x)， 并 且 假 设 对 于 除 了 有 限 个 点 集

41、外 ， 对 所 有 的x0,+)，k ( x )都存在。然后，我们采用 g ( x )作为核函数的轮廓函数，即定义核函数 G ( x )为(2-12)其中，c g ,d是标准化常量。将 g ( x )代入 (2-11)式，得到(2-13)由(2-10)式知，由核函数 G ( x )和窗宽 h 得到的在数据点 x 处的核密度估计式为(2-14)比较(2-13)式和(2-14)式可以发现，(2-13)式中的第一项与(2-14)式只相差一个比例常数。第二项就是 Mean Shift 向量：(2-15)不难看出，Mean Shift 向量即为以核函数 G ( x )的轮廓函数为权重系数的加权平均值与x

42、的差。由(2-14)式和(2-15)式，可以将(2-13)式改写为：(2-16)即（2-17）由(2-17)式知， x 点处的基于核函数 G ( x )的Mean Shift向量与基于核函数 K ( x )的密度梯度估计值之间仅相差一个正的常数系数，由此可知，MeanShift向量的方向与密度梯度方向相同，即与密度变化最快的方向相同，Mean Shift向量总是指向密度增加最快的方向。因此，要通过一组数据样本点来寻求估计的密度函数在某点的邻域内的最大值，就可以通过计算该点的Mean Shift向量来实现。首先由以 x为中心的一个邻域内的数据样本点计算出Mean Shift向量M h G（x）

43、，然后将中心点 x偏移至下一个中心点x c（加上Mean Shift向量），若x c- x 的值小于一个给定的阈值 ，则停止迭代，否则继续以当前中心作为x重复上述过程，直至停止。这个过程就是Mean Shift算法的基本过程。当算法停止时，会收敛到梯度为零的一个数据点，这个数据点就是概率密度的最大值点。2.5.3 Mean Shift 算法的收敛性由 2.5.2 节中的论述知道，Mean Shift 偏移过程就是计算 Mean Shift 向量，然后根据 Mean Shift 向量移动核函数的中心位置的重复迭代过程。定义序列y k k=1,2.。为核函数 G ( x )的中心在Mean Shi

44、ft迭代过程中的一系列位置，y k+1为y k的下一个偏移中心点，即（2-18）用fhk(k)k=1,2.。表示在相应的位置点y k k=1,2.。 处的密度估计值，即（2-19）已知Mean Shift向量M h G（ x ）与在中心点 x 处的密度梯度估计具有相同的方向，朝着梯度方向的移动保证了“爬山”过程只能进行有限步移动。下面的定理证明了Mean Shift算法对于离散数据的收敛性。定理 1如果核函数 K ( x )的轮廓函数 k ( x )是单调递减的凸函数，则序列y k k=1,2.。和序列fhk(k)k=1,2.。均收敛，且fhk(k)k=1,2.。是严格单调递增的。证明：由核函

45、数的定义可知，轮廓函数 k ( x )是有界的，又n是有限的，因此，f h K是有界的，从而序列fhk(k)k=1,2.。也是有界的。因此，只要证明序列fhk(k)k=1,2.。是单调递增的，即对于任意的 k=1,2.，若y k y k+1则有fhk(k) fhk(k+1) 就可以证明fhk(k)k=1,2.。一定收敛。不失一般性，假设y k=0，从(2-14)式和(2-19)式，可得(2-20)轮廓函数 k ( x )为凸函数，因此对于任意的x1x20,+),(2-21)因为，g ( x )=-k ( x)， (2-21)式变为(2-22)由(2-20)式和(2-22)式可得(2-23) 再

46、由(2-18)式，有(2-24)对于所有的 x0，轮廓函数 k ( x )单调递减，严格正，因此 ， 只 要y k y k+1 (2-24) 式 右 面 的 项 也 是 严 格 正 的 。 因 此 ， 序 列fhk(k)k=1,2.。是收敛的。为了证明序列ykk=1,2. 的收敛性，对于任意的核中心y k0重写(2-24)式，经过一些代数运算，我们有(2-25)将(2-25)式的两边对于 k , k 1,.k m 1分别相加，(2-26)其中，M 是对于所有的ykk=1,2. ，和式中的最小值，M是严格正的。由于fhk(k)k=1,2.。收敛，它也是柯西序列，联式 (2-26)式，可知序列yk

47、k=1,2. 也是柯西序列，因此，ykk=1,2.在欧几里得空间中也是收敛的。至此，Mean Shift 的收敛性得到证明。第3章 Mean Shift目标跟踪算法3.1 引言 在第 2 章中，我们介绍了一种无参密度估计方法核密度估计，在此基础上阐述了 Mean Shift 算法的基础理论，定义了 Mean Shift 向量，并证明了 Mean Shift 过程的收敛性。本章将把前面的 Mean Shift 理论应用于基于视频的运动目标跟踪中。 对于视频中的每一帧图像，通过在空间域中对目标区域掩上一个各向同性的核函数，计算出目标的核颜色直方图，在此基础上可以定义出一个空间平滑的相似度函数，使得目标模型与候选模型相似度最大的位置点就是在当前帧中的目标位置，于是目标定位问题就化为一个搜索相似性函数的吸引盆（basin of attraction）的过程。相似性函数的平滑性使得采用梯度优化方法成为可能，采用