毕业设计（论文）文献综述：基于Mean Shift算法的计算复杂度研究

毕业设计（论文）--文献综述综述题目基于MeanShift算法的计算复杂度研究专业信息与计算科学姓名学号指导教师

基于MeanShift算法的计算复杂度研究摘要近年来MeanShift算法被广泛应用于图像处理和追踪等方面，是目前视觉目标追踪领域的重要研究方向.首先介绍了MeanShift算法仅仅依靠特征空间中的样本点进行分析和处理，算法原理简单，易于并行和实现，不需要任何先验知识和统计参数估计，采用MeanShift算法，追踪过程中只需通过较少的迭代次数就能收敛到点的分布中密度最大的地方.然后在理解MeanShift算法的基础上计算其复杂度，同时对另外的CamShift算法的复杂度进行计算，并对两种算法的复杂度研究方法进行对比分析.关键词目标追踪；MeanShift算法；时间复杂度；CamShift算法；ComputationalAComplexityBasedofMeanShiftAlgorithmLiHai-quan(SchoolofMathematicsandPhysics,AnhuiJianzhuUniversity,Hefei230601)AbstractTheMeanShiftalgorithmhasbeenwidelyusedinimageprocessingandtrackingrecently.whichisanimportantresearchdirectionofthecurrentvisualobjecttrackingfield.Firstly,theMeanShiftalgorithmdependsonlyonthesamplesinfeaturespaceanalysisandprocessingwasintroduced,thealgorithmissimpleinprinciple,easyrealizationofparallelanddoesnotneedanypriorknowledge,estimationandstatisticalparameters,usingtheMeanShiftalgorithm,thetrackingprocessonlythroughthelocaldensitydistributionislessthenumberofiterationswillconvergetothemaximum.Secondly,onthebasisofunderstandingtheMeanShiftalgorithmtocalculateitscomplexity,Atthesametime,thecomplexityoftheCamShiftalgorithmiscalculated,thenthecomplexityoftheresearchmethodsoftwoalgorithmsarecomparedandanalyzed.Keywordsobjecttracking；MeanShiftalgorithm；Timecomplexity；CamShiftalgorithm；1引言MeanShift算法概念的最早出现，可以追溯到1975年，概率密度梯度函数的估计描述由Fukunaga等人提出[1]，它指的是一个相对迭代的连续过程。主要包括（1）计算出当前目标点的均值偏移量；（2）移动该目标点到其计算所得到的偏移均值处；（3）以该点为新的起始点继续移动，直满足预先设定的条件后自动结束移动。该方法简单有效，但这个概念在被提出和验证之后并没有立即引起大家的关注，直到另外一篇关于MeanShift算法的文献发表，对其在计算机视觉领域的广泛应用才起到了真正的推动作用。随着近年来计算机视觉领域的不断发展，越来越多的研究者将目光聚焦在了MeanShift算法在基于目标追踪的不同应用中的改进和发展。作为一种有效的统计迭代算法，该算法在计算机视觉与模式识别等领域得到了更为广泛的应用，例如目标追踪[2-3]、图像分割[4]、模式识别[5]、聚类分析[6]与滤波等方面，引起越来越多人对它的关注。由于MeanShift方法仅仅依靠特征空间中的样本点进行分析和处理，算法原理简单，易于并行和实现，不需要任何先验知识和进行统计参数估计，在实现MeanShift算法过程中，只需通过较少的迭代次数就能收敛到点的分布中密度最大的地方，因此在理解MeanShift算法的基础上计算其复杂度较易实现。目前已有很多关于目标追踪技术的算法，从目标追踪的依据手段来看，现阶段已有的目标追踪算法可以分为基于先验知识和非基于先验知识。这两方面从结果的侧重点来看，现有的目标追踪算法又可以分为侧重于运动目标区域追踪和侧重于运动目标运行轨迹追踪两大类。两种方式各有特色，但是都面临着两个相同的问题：背景噪声的干扰和缺乏目标追踪的实时性。要想解决上述两个问题就必须先对目标追踪算法的基本思想进行分析和归纳。大多数目标追踪算法的基本思想都以其特征值的匹配和特征值的提取两个方面为核心。从排除噪声干扰的角度来说，提取多种特征以及复杂的特征匹配规则显然是最有利的，但是这样不但增加了算法的复杂度，而且还影响了算法实现的实时性。所以，如何能快速而又有较强“抗噪”能力地从视频序列中提取出代表性的特征成为了当前解决问题的关键。2国内外研究现状这些年来，国内外很多学者都在目标追踪的技术领域上花费了大量的时间，并且深度研究了各式各样的追踪算法，定期都会在一些国际重要会议上发表大量研究成果，其中重要的会议包括ECCV、CVPR、ICCV等。这些会议为研究学者们提供了广泛的交流和学习的平台。MeanShift概念最早是1975年由Fukunaga[5]等人在关于一篇概率密梯度函数的文献中估计中提出来的，最初的含义，就是均值向量的偏移。即，均值漂移。然而经过的很长一段时间，并没有引起人们的注意。直到1995年，另外一篇关于MeanShift算法的重要文献才发表[6]。在关于MeanShift的追踪算法中，自从提出以来就受到广泛研究者的青睐，在基于算法框架下的研究与改进是视觉目标追踪领域的一个研究方向。在国外，有许多研究机构。例如，美国国防高级研究项目署（DARPA,DefenseAdvancedResearchProjectionAgency）在1997年就建立了监控视频的项目（VideoSurveillanceandMonitorProjects），与此同时有许多国外高校参加研究讨论，这其中就包括卡内基梅隆大学、麻省理工学院等，最后他们的研究成果多数用于军事或民用的监控视频系统中[7]。2005年，Comaniciu[8]和Meer两位学者经过深度的研究分析，成功地把目标追踪MeanShift算法运用于特征空间分析中,并在许多文献中论述了MeanShift算法中核函数带宽的选择问题，虽然表面看起来计算量比较大,实用性不强,但是很有理论价值，是向真理迈出的重要一步。经过时间的沉淀，ChangjiangYang在此基础上又对多维图像领域的方法进行了研究讨论，研究结果表明，在算法计算时选用高斯核之后,因为高斯核与图像卷积的运算量过大,因此采用了改进的方法。采用快速高斯核变换，可以大大提高算法的运行速度。然后Collins在此基础之上提出了尺度空间和高斯核相结合的理论。解决了核函数带宽在目标实时追踪变化时的问题,但算法在速度方面不是很好。在国内，有许多大学及各项研究机构都深入研究了目标追踪算法[9]，例如：清华大学、上海交通大学、华中科技大学、哈尔滨工业大学等高校的人机交互所、媒体集成研究所、微软亚洲研究院视觉研究小组，都在目标追踪领域做了大量的研究工作，并取得一些不错的成果和很大的进展。3MeanShift算法3.1无参密度估计概率密度估计通常分为有参数法和无参数法两类，旨在寻找满足样本集要求的概率密度函数[3]。所谓参数法就是先将密度函数的形式简单地假设出来，然后在数据采样的过程中估计出描述密度函数的各个参数。例如，预先假定了正态形式的概率密度函数，则易知其均值和方差都为所要估计的参数。但是在实际应用中，尤其是计算机视觉领域中，预先假定的概率密度函数的形式往往不能符合实际应用情况，这是因为数据的模型几乎都是未知的，而且对概率密度函数的先验知识又知之甚少。另外，经典的概率密度函数常为单峰的，就是说，只有单个局部极大值，这与实际中常见的多峰模型是相悖的。这时候无参数估计方法就体现出了其优越和实用性。而无参数方法无须预先假设密度函数的结构形式，可由落入某一连续点邻域中的若干样本点估计出其密度函数值。这种方法的优势在于不需要对先验知识过多的了解，而完全依靠训练数据来进行估计，可以对任意分布进行密度估计，应用十分广泛。典型的无参数密度估计方法有最近邻域法、直方图法及核密度估计法。（1）直方图法：直方图法是最早的且应用最为广泛的无参密度估计方法。直方图法通常是把数据的值域分为若干相等区间，把数据按阈值填充到各个区间内，每个区间的一组数据用一个矩形表示，其高度与该组数据的多少成正比，将这些矩形按照区间的次序排列起来就组成了直方图，它的优点在于它表示的数据分布给人清晰直观的感觉，缺点是只适用于描述低维的数据。（2）最近邻域法：该方法是由Cover等人于1968年提出的。该方法的思路是比较已知类别与未知样本间的欧式距离，并判断出该样本点的离它最近的样本同类。该方法的缺点是容易受到局部噪声的干扰，所以模型估计变得十分困难。（3）核密度估计法：核密度估计方法于上世纪50到六十年代被提了出来，其基本思想与直方图法类似。把采样数据的值域分成若干个相等的区间，每个区间称为一个bin，把数据按阈值分配到各个区间，则bin的概率值就是每组数据的个数与参样个数总数的比值。与直方图法相比，核密度估计法是一种平滑的无参数估计方法，它增加了一个平滑数据的核函数。该方法的优点在于可以进行快速的无偏密度估计，概率统计性质良好，但是比较适合中小规模的数据集，这是该方法的一个局限。系统仿真是以相似原理、系统技术、信息技术及其应用领域有关专业技术为基础，以计算机和各种专用物理效应设备为工具，利用系统模型对真实的或假想的系统进行动态研究的一门多学科的综合性技术.相似论是系统仿真的主要理论依据[4].系统仿真研究的对象是系统.系统是指具有某些特定功能、按照某些规律结合起来、互相作用、互相依存的所有事物的集合或总和.任何系统都存在三方面需要研究的内容，即实体、属性和活动.实体是存在于系统中的每一项确定的物体.属性是实体所具有的每一项有效的特性.活动是导致系统状态发生变化的一个过程.活动是在一段时间内发生的情况,活动反映了系统的变化规律.存在系统内部的实体、属性和活动组成的整体称为系统的状态.处于平衡状态的系统统称为静态系统，状态随时间不断变化着的系统为动态系统.3.2彩色空间的选择在计算机中，[10-11]彩色模型（又称彩色空间或彩色系统）的用途是在某些标准下用通常可以接受的方式便于对彩色加以说明。本质上，彩色模型是坐标系统和子空间的阐述。位于系统中的每种颜色都由单个点来表示对颜色而言它有多种不同的表达方式，这样就形成了各种不同的颜色空间。最常见的颜色空间有：RGB和HSV等。每一种颜色空间都它各自产生的背景和应用领域，在实际中，应根据具体的应用来选择合适的颜色空间。列举以下两种常见颜色空间的进行简单介绍。（1）RGB颜色空间：是根据人眼识别的颜色定义的空间，可表示大部分的颜色，它是最通用的面向硬件的彩色模型，如彩色监视器和彩色视频摄像等。它采用三基色原理，将自然界中的色用R、G、B三基色按不同的比例相加混合而成。RGB的颜色空间可以用一个三维的立方体来表示[12]，如图3.1所示。这是最常见的色系坐标系，由R(红)、G(绿)和B(蓝)三个分量组成，所有R，G，B分量都在[0,1]之间取值。三维空间中三个轴分别与红、绿、蓝三基色相对应，原点对应于黑色，离远点最远的点对应于白色，而其他颜色则落在三维空间中由红、绿、蓝三基色组成的彩色立方体中。对角线从黑(0,0,0)到白(1,1,1)代表的是灰度。通常情况下以RGB色系坐标为基础描述其它色系坐标系，将其它色系坐标系的基色描述为RGB三色的线性或者非线性函数。图3.1RGB颜色的立体示意图在RGB彩色模型中，所表示的图像由三个图像分量组成，每个分量图像都是其原色图像。当送入RGB监视器时，这三幅图像在荧光屏上混合产生一幅合成的彩色图像。在RGB空间中，用于表示每一像素的比特数，称为像素深度。考虑RGB图像，其中每一幅红、绿、蓝图像都是一幅8比特图像，在这种条件下，每个RGB彩色像素（R、G、B）值三个一组称为有24比特深度（三个图像平面乘以每平面比特数）全彩色图像常用来定义24比特的彩色图像。在24比特RGB图像中，颜色总数是。（2）HSV空间：HSV（hue，Saturation，value）色彩属性模式是根据色彩的三个基本属性:色度、饱和度和亮度来确定颜色的一种方法。其中H是色调，是色彩的基本属性，也就是平常所说的红，橙，黄，绿，蓝等颜色名称，不受色彩鲜淡，明暗的影响。S是饱和度，表示颜色深浅的程度，饱和度越高色彩越深，越低则逐渐变浅。V是亮度，表示某种颜色明暗的程度。4MeanShift算法追踪原理4.1MeanShift向量Fukunaga对于MeanShift的定义为：给定d维空间中的n个样本点，i=1,…n。在x点的MeanShift向量的基本形式定义为：（4-SEQ（\*ARABIC\s31）其中，k表示在这儿n个样本点中，有k个点落入区域中。是一个半径为h的高维球区域，满足以下关系的y点的集合：（4-2）式（3-SEQ（\*ARABIC\s32）的物理意义如图3.3所示[17]。核函数的中心x点用中间黑点表示，周围表示样本点，是相对于x的偏移向量，平均的偏移量指向样本点最密的方向，即梯度方向如箭头方向所示。由图可见，而只要是落入区域的采样点，无论其离中心点x的远近，对最终的计算的贡献是一样的。而在实际的跟踪过程中，当跟踪目标出现遮挡等影响时，由于外层的像素值容易受遮挡或背景的影响，所以目标模型中心附近的像素比靠外的像素更可靠。中心像素给的权值大些，离中心点越远，赋的权值越小。并且在所有的样本点中，每个样本点的重要性也应该是不同的。因此在这里又引进了核函数和权重系数的概念来提高跟踪算法的鲁棒性并增加搜索跟踪能力。图4.1MeanShift向量的示意图这样就可以把MeanShift形式扩展为：（4-3）其中，是一个单位核函数，，是一个赋给采样点的权重。（4-4）4.2模板建立MeanShift算法是用人机交互的方法来对被跟踪目标进行初始化的。假设给定两帧图像，在第一帧中用鼠标选定一个包含目标特征的矩形或椭圆区域，该区域称为目标模型，区域的大小就是核函数的带宽，另一帧图像则称为候选模型。目标跟踪的任务就是在候选模型中找出被跟踪的目标，并对其精确定位。目标模型中的采样点表示为，这里为像素在图像中的二维坐标，而则为该像素对应的特征向量。候选图像中的采样点表示为，同样给出了采样点的二维坐标和对应的特征向量。特征向量是由特征空间中所有特征值组成的，特征空间可以是由颜色空间、纹理空间等来描述，特征值表示为某一空间中图像像素值的核密度估计。MeanShift算法首先要在初始帧内为被跟踪目标建立概率模型。设在初始帧中，采用手动方法通过鼠标选定一个包含被跟踪目标区域的外接矩形或椭圆，即被跟踪目标的目标窗口，其中包含n个像素点。这个目标区域即时核函数的作用区域，区域的大小就是核函数的带宽。如果采用RGB颜色空间，按照直方图方法将每个基色子空间R、G、B均匀地分成k个互不相交的区间，每个区间为一个特征值，称为一个bin，那么整个RGB颜色空间中bin的个数或者说特征空间空特征值的个数为。假设目标的中心位于处，表示目标模型的像素位置，那么目标模板的概率密度估计可表示为：（4-5）其中，k是核函数,h为核窗宽，决定着权重的分布，表示处象素的颜色值，u为直方图的颜色索引，范围是l~n。为Kroneckerdelta函数，作用是判断目标区域中像素的颜色值是否属于第u个单元的颜色索引值，等于为1，否则为0。C是归一化系数，表达式为：（4-6）运动目标在第二帧及以后的每帧中可能包含目标的区域称为候选目标区域，也就是说在第n帧时，根据第n-1帧的目标位置y，以y为搜索窗口中心坐标用同样的核函数计算当前帧的候选目标区域直方图。那么候选模板的概率密度估计表示为：（4-7）其中为归一化系数，相当于式（3-5）中的C。（4-8）4.3相似性度量给出了目标模型表示后，在当前帧中寻找目标位置的任务可以归纳为：在当前帧中寻找最优的y使目标模板与候选目标模板()最相似。于是引入了Bhattacharyya系数作为相似性函数来衡量目标模板和候选目标区域对应的直方图之间的相似性。以两个直方图的相似性最大为原则，使搜索窗口沿密度增加最大的方向移动到目标的真实位置。其中为目标模板，为候选目标模板，u=1…m。其值在0-1之间，越大，表示两个模板越相似。（4-9）为了使最大，将当前帧的目标中心先定位为前一帧中目标中心的位置，从这一点开始寻找最优匹配的目标。目标定位的过程就是把求取距离最小值转化为求Bhattacharyya系数最大值的问题。为了得到Bhattacharyya系数的最大值，现在要对进行分析，先以前一帧目标的中心坐标作为当前帧中目标区域的中心，在该点为起始点的某一邻域内对目标进行搜索。已知，将（3-8）在处进行泰勒展开，舍去高阶项，则可近似为：（4-10）式（3-9）中第一项为常量，第二项是y的函数。要使最大，只需使第二项取得最大值。对于第二项，令（4-11）上式可以看作轮廓函数为，权重为的样本点在y处的密度估计。根据MeanShift算法原理，可以推导出以为候选区域中心，平移到目标区域中心y的MeanShift向量：（4-12）一次迭代后目标的新位置为,当一次迭代完成之后，令，然后开始下一次迭代，重复这个过程直至，则进行下一帧的运算，否则根据新坐标计算的候选直方图继续计算均值漂移向量。5CamShift算法原理CamShift算法（ContinuouslyAdaptiveMean-Shift）基本思想是，从初始帧开始，将追踪视频图像里的每一帧都作MeanShift迭代运算，并将上一帧的追踪结果，包括搜索窗口的中心值的大小，作为下一帧MeanShift追踪算法搜索窗口的初始值，如此一直迭代下去，不断收敛到目标中心密度值最大的地方，就可以实现对追踪目标的追踪。同MeanShift一样，CamShift算法也采用目标模板及候选模板，CamShift算法采用的目标模板是颜色直方图（HSV颜色空间），根据追踪目标颜色空间的反向投影图得到下一帧追踪图像帧的颜色概率分布直方图，在此基础上，计算追踪目标的质心，将搜索窗口的中心不断移动到质心，当中心与质心的距离小于设定的固定阈值时（一般情况下，取两个像素之间的大小），或者当迭代的次数小于设定的最大值时，此时得到的质心的位置即为目标的位置。对于CamShift追踪算法，主要分为三个部分：（1）色彩投影图RGB颜色空间对光照亮度变化和强度较为敏感，为了减少此变化对追踪效果的影响，将图像从RGB颜色空间转换到HSV颜色空间。（2）H分量作直方图用H分量作出的直方图，在直方图中代表了不同的H分量，同时分量的值也代表出现的概率或者出现的像素个数，简单来说，就是可以查找出H分量的大小，即得到了颜色概率分布。（3）颜色概率分布将图像中每个追踪图像帧数的值用其颜色出现的概率对替换，就获得了颜色概率分布直方图。这个过程就是反向投影的过程[25-26]，而颜色概率分布图是一个灰度图像。6算法复杂度分析6.1时间复杂度算法的时间复杂性分析是一种事前分析估算的方法，它是对算法所消耗资源的一种渐进分析方法。所谓渐进分析是指忽略具体机器、编程语言和编译器的影响，只关注在输入规模增大时算法运行时间的增长趋势。渐进分析的好处是大大降低了算法分析的难度，是从数量级的角度评价算法的效率。一个算法执行所耗费的时间从理论上是不能算出来的，必须上机运行测试才能知道但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度记为。在刚才提到的时间频度中，n称为问题的规模，当不断变化时，时间频度也会不断变化，但有时我们想知道它变化时呈现什么规律，为此，引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模的某个函数，用表示，若有个辅助函数,使得当趋近于无穷大时，的极限值为不等于零的常数，则称是的同数量级函数。记作。称为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为。另外,在时间频度不相同时，时间复杂度有可能相同。如与它们的频度不同，但时间复杂度相同[8]，都为按数量级递增排列。常见的时间复杂度有常数阶，对数阶，线性阶，线性对数阶，平方阶，立方阶,…，次方阶，指数阶。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。6.2空间复杂度空间复杂度（SpaceComplexity）是一个算法在运行过程中临时占用存储空间量度的大小。比如，插入排序的时间复杂度是O()。空间复杂度是而一般的递归算法就要有的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面而衡量。关于时间复杂度的讨论，一个算法的空间复杂度是定义为该算法所耗费的存储空间[10]，它是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。算法在运算过程中所需的存储空间包括：执行算法需要的辅助空间；算法本身占用的空间；输入输出数据占用的空间。算法需要占用的临时空间存储单元数与解决问题的规模n息息相关，它随着n的变化而变化，当n变大时，将占用较多的空间存储单元。辅助空间数量是算法空间复杂性在算法的执行过程中的必要因素，简单来说也就是除算法本身之外的空间，即：算法临时开辟的存储空间，是辅助空间数量输入规模的函数，记作与时间复杂性相类似，空间复杂性是指算法在计算机内执行时所需存储空间的度量。本文讨论的两种算法空间复杂度相差不大，因此着重研究时间复杂度6.3复杂度分析方法在计算时间复杂度的过程中，最关键的是要算出算法语句中最多的执行次数。在很多学者看来，算法中最内层循环体语句往往具有最大的语句频度，在MeanShift算法及CamShift算法计算时间复杂度过程中，主要对它们进行分析和计算。目前，算法的时间复杂度分析方法可以归纳为如下几种：（1）求和法。在当算法中语句的执行次数与某一变量有直接关系的背景下，该变量的变化起止范围又较为明确，则可以利用求和公式得出最大的语句频度，再对其取数量级(阶)即可。（2）假设法。在某些较为复杂的算法中，循环结构的循环次数很难直接看出，特别是当循环次数与循环体中的某些语句执行有联系时，语句频度的计算变得比较困难。此时，可以先假设循环执行次数为k次，再对算法进行分析，根据循环终止条件求出语句频度，最后求出。（3）迭代法。当算法中包含递归函数时，其时间复杂度也会被转化为一个递归方程，上述两种方法此时不再适用。递归方程的形式多种多样，其求解方法也是不一而足，比较常用是迭代法。MeanShift算法及CamShift算法适用的即是此种算法。其基本步骤是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来得到时间复杂度。在分析时间复杂度时，须遵从以下几个简单的程序分析法则：（1）对于一些简单的输入输出语句或赋值语句，近似认为需要时间（2）对于顺序结构，需要依次执行一系列语句所用的时间可采用大下的“求和法则”。求和法则：是由算法法则的2个部分组成，时间复杂度分别为和，则，若，，则。（3）对于选择结构，如if语句，它的主要时间耗费是在执行then字句或else字句所用的时间，需注意的是检验条件也需要时间。（4）对于循环结构，循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费，一般可用大下的“乘法法则”。乘法法则：是由算法的2个部分组成。故，时间复杂度分别为和则。（5）对于复杂的算法，可以将它分成几个容易估算的部分，然后利用求和法则和乘法法则技术，并采用以下2个运算法则：（1）若，则；（2），其中C是一个正常数。如果一个算法的复杂度为、

、、

，那么这个算法时间效率比较高；如果是

、和，那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。计算时间复杂度的分析过程是一个很重要的流程，任何一个实验人都应该熟练掌握该算法的概念和基本方法，而且要善于探寻算法复杂度的本质，只有这样才能真正的去学会它。7总结当前多数使用基于算法的目标追踪不能很好实时改变核窗宽的特点，提出了一种基于目标中心定位和特征的追踪算法。在目标追踪过程中，通过建立二值模型，利用特征识别要追踪的目标，追踪过程始终定位目标的中心。结合算法的寻优相似度函数，选择最优的核窗宽。目标在移动过程中，其中心点也是在做不规则的移动，以中心点为基点来扩展追踪窗口。从而使得在追踪目标的每一帧图像里，能够准确的放缩追踪窗口，进而使得在目标特征能够持续的被检测到。在这基础之上通过分析MeanShift及CamShift两种不同算法，计算两种算法的复杂度，进行比较分析，最终得出复杂度分析结论。参考文献[1]吕国英,任瑞征,钱宇华.算法设计与分析[M].北京:清华大学出版社,2006.[2]田莘.基于MeanShift算法的目标追踪问题研究[D].西安电子科技大学硕士学位论文,2010.[3]顾幸芳.李秋洁.基于MeanShift的视觉目标追踪算法综述[J].计算机科学,2012,2(6):604-608.[4]冯帆.复杂度可分级的目标追踪算法研究[D].华中科技大学硕士学位论文,2013.[5]姜明新.智能视频监控中的目标追踪技术研究[D].大连理工大学硕士学位论文,2013.[6]许晓丽.基于聚类分析的图像分割算法研究[D].哈尔滨工程大学硕士学位论文,2012.[7]何革.基于MeanShift算法的视频目标追踪研究[D].重庆大学硕士学位论文,2012.[8]覃剑.视频序列中的运动目标检测与追踪研究[D].重庆大学硕士学位论文,2014.[9]张宇山.进化算法的收敛性与时间复杂度分析的若干研究[D].华南理工大学硕士学位论文,2013.[10]殷超.常用算法时间复杂度的计算方法[J].科技信息,2011,26(1):118-184.[11]ShioA,SklanskyJ.Segementationofpeopleinmotion[A].IEEE