毕业设计（论文）mean shift目标追 踪算法计算复杂度分析

摘要运动目标追踪应用于体育赛事直播、平安监控和医学诊治等领域。本文主要分析MeanShift目标追踪算法及其改良的CamShift算法的计算复杂度。算法的时间复杂度是一种事前分析方法。阐述有关算法分析理论与方法，重点关注时间复杂度的分析方法。论述MeanShift目标追踪算法的根本原理，分析该算法在实际追踪的过程中存在的优缺点。MeanShift算法仅仅依靠特征空间中的样本点进行分析和处理，算法原理简单，不需要先验知识，对目标追踪过程中存在遮挡情况处理不是很好，还有待改良。在分析MeanShift算法原理的根底上，阐述CamShift算法思想，对CamShift算法进行算法描述与分析，比照两种算法的时间复杂度。在分析两种算法的时间复杂度时，采用时间代价函数作为度量标准，以追踪同一视频的不同消耗时间作为判断依据，比拟两种算法的时间复杂度。关键词：目标追踪；MeanShift；时间复杂度；CamShift

AbstractThemovingtargettrackingisusedinmanyareas,suchaslivesportsevents,safetymonitoring,andmedicaldiagnosis.ThispapermainlyanalyzesthecomputationalcomplexityoftheMeanShifttargettrackingalgorithmanditsimprovedCamShiftalgorithm.Thetimecomplexityofthealgorithmisthemethodinadvance.Thispaperexpoundsthetheoryandmethodofalgorithmanalysis,andfocusesontheanalysismethodoftimecomplexity.ThispaperdiscussesthebasicprincipleoftheMeanShifttargettrackingalgorithm,andanalyzestheadvantagesanddisadvantagesofthealgorithmintheactualtrackingprocess.TheMeanShiftalgorithmdependsonlyonthesamplesinfeaturespaceanalysisandprocessing,thealgorithmissimpleinprinciple,thisalgorithmdoesnotrequireaprioriknowledge,anditisnotverygoodtodealwithocclusioninthetargettrackingprocess,whichneedstobeimproved.OnthebasisofanalyzingtheprincipleoftheMeanShiftalgorithm,thispaperexpoundstheideaofCamShiftalgorithm.ThealgorithmofCamShiftalgorithmisdescribed,timecomplexityofwhichiscomparedbytheMeanShiftalgorithm.Whenanalyzingthetimecomplexityofthetwoalgorithms,thetimecostfunctionisadoptedasthemeasurementstandard.Thetimecomplexityofthetwoalgorithmsiscomparedbytrackingthedifferentconsumptiontimeofthesamevideo.Keywords:targettracking;MeanShift;timecomplexity;CamShift

目录摘要 的权重。(3-4)3.2MeanShift算法描述3.2.1伪代码描述步骤一：选择好目标区域，圈定目标初始估计位置与核窗宽h，建立目标模板，并计算目标模板的概率密度。步骤二：令迭代次数k=0；步骤三：用初始化当前帧的目标位置，计算候选目标模板概率密度和权重系数；步骤四：计算目标的新位置，候选目标坐标；步骤五：根据计算当前窗口内各点的权重值；步骤六：于1的像素间距设为阈值，如果那么停止，否那么←，执行步骤一，重复移动直至收敛；步骤七：算法结束。开始流程图开始建立目标模板确定初始位置建立目标模板确定初始位置计算目标候选模板计算目标候选模板MeanShiftMeanShift迭代计算新的位置计算当前窗口内各点权重值计算当前窗口内各点权重值设定阈值设定阈值NONOYESYES读取下一帧读取下一帧图3-SEQ图\*ARABIC\s11MeanShift算法流程图3.3MeanShift算法的缺乏MeanShift追踪算法具有良好追踪的实时性，是一种在追踪领域较为简单快捷的追踪方法。但是MeanShift也存在以下缺点：〔1〕核函数HYPERLINK[23-24]直方图对追踪目标的特征描述不明显，在灰度图像或者纹理图像中，获取的图像信息较少。〔2〕由当MeanShift追踪算法在追踪目标对象时容易出现局部极大值的情况、这样会使该算法收敛速度变慢。〔3〕虽然该算法计算速度较快，但是在追踪方面，不能很好地解决目标遮挡的问题。针对以上缺点，可以做出以下调整。〔1〕为进一步减少MeanShift追踪的搜索时间，可以引入另一种追踪算法进行相应的融合，如算法以便于预测移动目标的变化，从而降低计算量。〔2〕传统的MeanShift算法固定了内核的带宽，而不是动态带宽。所以更改为动态带宽会提高算法的追踪性能。3.4CamShift算法描述3.4.1算法思想CamShift算法是MeanShift算法的改良，核心意义是，从初始帧选取开始，将追踪视频图像里的每一帧以MeanShift算法为核心并依次做迭代运算HYPERLINK[5]。然后把迭代后追踪结果的中心值窗口的大小，作为下一帧MeanShift追踪算法搜索窗口的初始值，如此一直迭代下去,不断收敛到目标中心密度值最大的地方，就可以实现对追踪目标的追踪。根据追踪目标颜色空间的反向投影图得到下一帧追踪图像帧的颜色概率分布直方图，当中心与质心的距离小于设定的固定阈值时(一般情况下，取两个像素之间的大小)，此时得到的质心的位置。对于CamShift追踪算法，主要分为三个局部：〔1〕色彩投影图〔2〕H分量作直方图〔3〕颜色概率分布由于CamShift算法是在MeanShift算法上的改良，所以描述MeanShift算法过程是其中不可缺少的一个环节。算法过程如下：〔1〕在颜色概率分布图中选取搜索窗W〔2〕计算零阶距：〔3-=5\*Arabic5〕计算一阶距：〔3-=6\*Arabic6〕计算搜索窗的质心：〔3-=7\*Arabic7〕〔3〕调整搜索窗大小宽度为；长度为1.2s；3.4.2CamShift算法步骤CamShift算法就是将MeanShift算法扩展到连续图像序列，在追踪过程中可自适应调整窗口大小。它将视频的所有帧做MeanShift运算并将上一帧的结果包括搜索窗口的大小和中心[9]，作为下一帧MeanShift算法搜索迭代的初始值。

算法过程为：〔1〕初始化搜索窗口；〔2〕计算搜索窗口的颜色概率分布〔反向投影图〕；〔3〕对图像运行MeanShift算法，获得搜索窗口新的大小和位置；整个CamShift算法的具体步骤分五步：步骤一：将整个图像设为搜寻区域；步骤二：初始化搜索窗口的大小和位置；步骤三：计算搜索窗内的彩色概率分布，此区域的大小比搜索窗要稍微大点；步骤四：运行MeanShift，获得搜索窗口新的位置和大小；步骤五：在下一帧视频图像中，用步骤三获得的值初位置和大小。跳转到步骤三继续运行。开始转换图像空间3.4.3CamShift算法流程图开始转换图像空间否是得到目标的质心和窗口大小结束调整新的搜索窗位置判断质心是否收敛查找颜色直方图计算搜索窗的质心移动搜索窗的中心到质心位置在搜索搜索窗周围窗口稍大的区域初始化搜索窗的大小和位置否是得到目标的质心和窗口大小结束调整新的搜索窗位置判断质心是否收敛查找颜色直方图计算搜索窗的质心移动搜索窗的中心到质心位置在搜索搜索窗周围窗口稍大的区域初始化搜索窗的大小和位置图3-SEQ图\*ARABIC\s12CamShift算法流程图CamShift追踪算法的优点是能够有效解决目标形变和遮挡的问题，对系统占用资源要求不高，时间复杂度相对较低，并在简单背景下能够取得良好的追踪效果。但在追踪过程中，当背景较为复杂时，或有许多与目标颜色相似的像素干扰的情况下，会导致追踪失败。它会忽略目标的空间分布特性，因为它仅仅考虑颜色直方图。第四章算法分析4.1时间代价实验本文的度量标准以算法的帧率做比拟标准。通过计算机运行时的计时功能获得较为准确的时间，然后对两种算法进行运行时间的相互比拟。本文选取第一段具有代表性的测试视频序列进行追踪实验，测试的环境为Inter(R)Core(TM)i5-4200HCPU@2.80GHZ处理器及4.0GB内存，两种目标追踪算法在MATLAB〔2021Rb〕环境下运行实现，自行编写了追踪MATLAB主程序，调用Camshift源程序，并调用了tip和toc时间函数进行处理，得到追踪时间。在运行过程中分别使用均值漂移算法和改良的MeanShift算法〔CamShift算法〕在同的环境参数设置下，对相同的源视频进行了处理，源视频为两个人在走廊的过道相遇，然后互相握手，最后离开的过程，为了使源视频和源程序相匹配，把视频转换成无压缩的AVI格式，视频总帧数为282帧。计算出源视频的总帧数和追踪的总时间，二者用视频总帧数比上追踪的总时间得到帧率，用帧率分析两种追踪算法的复杂度。图4-SEQ图\*ARABIC\s11MeanShift算法追踪视频消耗的时间图4-SEQ图\*ARABIC\s12Camshift算法追踪视频消耗时间表4.SEQ表\*ARABIC\s11两种算法对应的运行时间和帧率比照算法运行时间〔S〕帧率〔FPS〕MeanShift算法9.839928.6CamShift算法7.850735.94.2追踪实验效果分析两种算法在追踪同一视频时，追踪的效果会有所差异。那么衡量两种算法追踪效果的度量标准是，追踪效果好的视频帧数比上总的视频帧数，作为本文度量依据。4.2.1实验设计选取第二段在静态背景、单一场景、有目标遮挡情况下的视频，此段视频的序列帧数共有216帧。实验环境为MATLAB〔2021Rb〕插入分帧函数，得到了从目标模板选取开始到追踪过程结束的视频追踪效果帧数。4.2.2采用MeanShift算法效果分析在使用MeanShift算法对第二段视频进行追踪时，从实验结果得出当目标未遮挡时，该算法能很好的追踪目标。所选的目标局部被遮挡时，追踪的窗口就会停止在被遮挡的物体上，即使再次出现时，追踪框也不能很好的再次定位在目标上继续追踪。效果图如图4-3所示。a71帧b96帧c117帧d149帧e161帧f162帧图4-SEQ图\*ARABIC\s13MeanShift算法追踪效果图由上图可以看出从视频的第a图71帧开始，手动选定追踪目标，直到视频的e图161帧为止，被追踪的目标一直被抓住，没有追踪丢掉。从追踪视频的第162帧开始到追踪结束，追踪的目标停留在被遮挡的物体上，即追踪目标丧失。故，追踪目标的追踪良好率为0.41。4.2.3采用CamShift算法效果分析在使用CamShift算法对第二段视频进行追踪效果，如图4-4所示.a71帧b108帧c171帧d181帧e182帧f216帧图4-SEQ图\*ARABIC\s14CamShift算法追踪效果图从实验分析结果得出从视频帧数的第a图71帧开始，到追踪过程中第d图181帧，都能牢固的抓住追踪目标。所以当追踪目标被遮挡时，依然可以追踪到目标，但是随着追踪目标速度的加快从视频的第e图182帧到追踪过程f图216帧的结束，追踪目标丢掉。即踪目标的追踪良好率为0.50。表4.SEQ表\*ARABIC\s12两种追踪算法良好率比照算法追踪良好率〔〕MeanShift算法0.41CamShift算法0.50由表4.2得出MeanShift算法在目标遮挡时，容易发生目标追踪不稳定的情况。而采用CamShift算法在遮挡时不会被影响，但由于目标移动太快，所以追踪过程中也会存在追踪目标丧失的情况。但总的来说改良的CamShift算法比原有的MeanShift算法追踪效果会好一些，追踪率也比MeanShift算法高。4.3时间复杂度分析在计算时间复杂度时，计算程序运行的时间函数一般会遮盖住算法自身的优点和缺点，因此针对这种情况，采用事先分析估算的算法不失为一种解决的方法，只考虑算法问题的规模。用自然数来表示，在某种特殊算法下，问题的规模是影响时间度的唯一因素，简单的说，计算算法的时间复杂度是问题的规模的某种函数。对于时间复杂度的比拟，比拟常见的手段是，首先从算法中选取一种所要研究的问题或算法模型，然后在进行根本的运算的操作，并重复执行根本语句次数。以作为评价算法时间复杂度的标准。一般为。这两种算法的时间复杂度都是跟输入规模有关，根据MeanShift算法描述，进行如下分析。步骤一：选择好目标区域，建立目标模板计算目标模板的概率密度，确定目标初始估计位置与核窗宽h；步骤二：令迭代次数k=0；步骤三：用初始化当前帧的目标位置，计算候选目标模板概率密度和权重系数；步骤四：计算目标的新位置，候选目标坐标；步骤五：根据计算当前窗口内各点的权重值；步骤六：在一个距离大于1的像素间距设为阈值，如果那么停止，否那么，执行步骤一，重复移动直至收敛；把步骤六变成语句如下语句1语句2只有可运行的语句才会增加时间复杂度，因此，上面的内容除了循环之外，其余的可运行语句的复杂度都是，这里面的是一个阈值，无论它的阈值多少，如果在一个大小为n循环中，循环变量按照一个常量c递增或递减，这个循环的复杂度就为。循环的复杂度与只与和的输入规模有关，在上述程序中，语句1的时间频度是，语句2的时间频度是，因此。对于MeanShift算法，时间复杂度即为。而CamShift算法是MeanShift算法的改良，只是在MeanShift算法的根底上进行改良，CamShift算法利用目标的颜色直方图模型得到每帧图像的颜色投影图，根据上一帧追踪的结果自适应调整搜索窗口的位置和大小，而得到当前图像中目标的尺寸和中心位置。只是对搜索窗口进行了改良。因此这两种算法的时间复杂度都是，即。4.4比照分析表4.SEQ表\*ARABIC\s13两种算法比照表算法运行时间〔S〕帧率〔FPS〕时间复杂度〔O〕MeanShift算法9.839928.6T(n)=O(n)CamShift算法7.850735.9T(n)=O(n)综上所述由表4.2可以看出采用Camshift追踪算法比MeanShift追踪算法的追踪效果更好。由表4.3可以看出MeanShift算法追踪的时间较长，CamShift算法时间效率比拟髙，Camshift追踪算法帧率高于MeanShift算法，由于Camshift追踪算法是MeanShift算法的改良，在追踪视频时所消耗的时间一定比MeanShift算法追踪视频时的时间短。

第五章总结5.1主要工作移动目标追踪在近年来成为计算机视频领域的一个热门研究方向。但由于理论的不完整性和各种条件的限制，绝大多数的目标追踪算法都是在某一具体情况下提出的，具有不广泛性。再者会受到一些环境、设备、人为干扰客观条件的限制，也会使目标追踪的准确性有所降低。因此想要完善不同情况的追踪算法，还有更严峻的挑战在等待解决。本文首先对现有计算复杂度的方法进行了分析，找到了复杂度分析时所需要的工具方法和需进行改良的地方，然后本文详细分析了的根本原理和该算法在实际追踪的过程中一些优缺点，对MeanShift算法分析复杂度的局部，由于在对追踪视频时MeanShift算法目标颜色特征比拟单一，所以本文采用了一种改良的MeanShift算法，为Camshift目标追踪算法。其次，概述了MeanShift算法在目标遮挡时的追踪能力，采用了改良的MeanShift算法，利用Camshift算法中的核心思想，这样即使在遮挡时，算法仍能追踪到目标，以便于计算复杂度。与此同时，MeanShift算法可以缩小迭代的时间，提高追踪效率。最后在分析两种算法MeanShift算法和Camshift算法的时间复杂度时，采用时间函数作为度量标准，以追踪同一视频的不同消耗时间作为判断依据，比拟两种算法的复杂度。在分析过程中，先是对两种算法的描述做了很足的工作，即算法的伪代码描述和算法的流程图，这是分析复杂度的必要工具，然后对两种算法的帧率做了比拟，通过两种算法的伪代码描述得出了不同追踪情况的复杂度，最后得出结论。本文采用MeanShift算法对目标追踪和计算时间复杂度分析时，无论是在追踪效果方面，还是在时间复杂度的计算方面都存在很多的缺乏。关于研究的目标追踪领域，认为有以下两点：第一，本文在追踪效果分析局部，采用MeanShift算法对目标进行追踪时，由于选取的视频有目标遮挡，所以在追踪过程中,遇到有遮挡的情况，就会出现追踪目标丧失并停留在遮挡物上的情况，追踪效果不是很理想。第二，在采用MeanShift算法对时间复杂度进行计算时，本文利用的是时间函数代价分析，在分析过程中，由于MeanShift算法原理比拟简单，通过实验得出的实验结果时间较长。针对追踪窗口的自适应调整仍然没有适宜的解决方案。如果能够找到一种计算简单，性能优良的因素作为窗口伸缩系数的计算依据，那么会进一步提高目标追踪的精度并扩大它的应用范围。5.2展望从目前来看，运动目标追踪是一个还在处于上升阶段的的研究课题，在图像处理、模式识别、计算机视觉等领域的研究还有待提高。近年来，虽然对该领域付出了许多汗水，但随着应用的逐层深入，仍然面临许多困难，这些困难包括：〔1〕算法的实时性追踪算法能否得到实际应用，很重要一个因素就是实时性，但目前多数的算法都是在一些假定条件下才能实现，因此下一步研究的主要方向就是满足实际应用的实时性这个条件。〔2〕目标遮挡问题当追踪目标发生遮挡时，追踪对象会出现有一局部是看不见的，并且过程中可能发生形变、旋转等各种不可预知的情况。如何构架一个准确的处理遮挡的模型也是今后研究的重要问题。〔3〕多目标的追踪在多目标追踪中，不仅考虑与单目标追踪中相似的遮挡问题，还要考虑新目标出现时的识别及旧目标消失时的判定等问题。在众多多目标追踪算法中，粒子滤波法是目前解决多目标追踪问题的主要方法，但随着目标数目的增多，需要为多个目标建适宜的动态模板，怎样降低状态空间的维数、设计高效的样算法等问题还需要进一步的研究。

参考文献[1]SegenJ,PingaliS.Acamera-basedsystemfortrackingpeopleinreal-time[A].ProceedingsofICPR’96[C].NewYork,USA:[s.n.],1996.63-67.[2]姜明新.智能视频监控中的目标追踪技术研究[D].大连理工大学硕士学位论文,2021.[3]李培华.一种改良的MeanShift追踪算法[J],自动化学报,2007,33(4):347-354.[4]BirchfieldS,SriramR.SpatiogramsVersushistogramsforregion-basedtracking[C]CVPR05,SanDiego,2005:pp.1158-1163.[5]毛勇,周晓波,夏铮.特征选择算法研究综述[J].模式识别与人工智能,2007,20(2):211-218.[6]ShiP.,etal.Amodel-basedintegratedapproachtotrackmyocardialdeformationusingdisplacementandvelocityconstraints[C].InProc.ofEuropeanConf.ComputerVision.Cambridge,MA,USA.1995:299-304.[7]彭宁高,杨杰.MeanShift追踪算法中核函数窗宽的自动选取[J].软件学报,2005,16(9):1542-1550.[8]DoucetA.,N.Gordon,V.Krishnamurthy.ParticlefilterforstateestimationofjumpMarkovlinearsystems[J].IEEETransactionSignalProcessing,2001.49(3):613-624.[9]田莘.基于MeanShift算法的目标追踪问题研究[D].西安电子科技大学硕士学位论文,2021.[10]R.Jain,R.Kasturi,B.G.Schunck.MachineVision[M].NewYork:McGraw-Hill,2003.[11]ChenBS,LeiYQ,LiWW.Anovelbackgroundmodelforreal-timevehicledetection[C]//7thInt.Conf.onSignalProcessing,2004:1278-1281.[12]许晓丽.基于聚类分析的图像分割算法研究[D].哈尔滨工程大学硕士学位论文,2021.[13]王红梅,胡明.算法设计与分析[M].北京:清华大学出版社,2021.[14]吕国英,任瑞征,钱宇华.算法设计与分析[M].北京:清华大学出版社,2006.[15]冯帆.复杂度可分级的目标追踪算法研究[D].华中科技大学硕士学位论文,2021.[16]殷超.常用算法时间复杂度的计算方法[J].科技信息,2021,26(1):118-184.[17]张宇山.进化算法的收敛性与时间复杂度分析的假设干研究[D].华南理工大学硕士学位论文,2021.[18]D.Kirsanov,S.J.Gortler.Adiscreteglobalminimizationalgorithmforcontinuousvariedproblems[R].HarvardComputerScienceTechnicalReport,TR-14-04,2004.[19]SON,JAEHYEAK.METHODANDAPPARATUSFORCANCELLINGECHOOF2021-11-26.COMMUNICATIONSYSTEM[P].国外专利:KR20210102712,2021-11-26.[20]袁国武,徐丹.一种结合了纹理和颜色的运动目标追踪算法[J].计算机应用与软件,2021,28(11):81-84.[21]安国成,张凤军等.多窗口目标追踪算法[J].计算机研究与开展,2021,48(11):2024-2029.[22]L.J.Reese.Intelligentpaint:Region-basedinteractiveimagesegmentation[D].Brighamyounguniversity,1999.[23]杨振兴.基于DM642Camshift追踪算法研究[D].南京理工大学,2021.[24]马丽,胡尼亚,李娜,王志军,唐雄燕.电信产品发布方法与业务管理子系统[P].中国专利:CN102446308A,2021-05-09.[25]ShioA,SklanskyJ.Segementationofpeopleinmotion[A].IEEEWorkshoponVisualMotion[C].Princeton,NJ,USA:IEEEComputerSociety,1991.325-332.

致谢转眼间，大学四年的学习生涯即将过去了，我有过压力，也有过成就感，有过失落也有过欣慰。此时的心情可谓百感交集，在此我要向培养我的母校安徽建筑大学致以崇高的敬意，也要感谢我的辅导员黄红娟，她对我四年的生活提供了积极的帮助!我要感谢我的导师王焕宝教授。王老师是一个知识渊博的学者，有着严谨的态度、敏锐的洞察力、宽厚随和的为人以及睿智儒雅的学者风范，这些都给我留下了深刻的印象。他对我大学期间的学习给予了精心的指导，每次论文的批改都会进行到深夜，试问有几个导师可以做到这些，而且生活上对我无微不至地照顾。其次还要感谢那些提供文献的作者，如殷超，田莘等。为本文的撰写提供了极大的灵感和帮助。我还要感谢我的研究生师姐、师哥和我的各位同学给予我的帮助。在此我要特别感谢我的学姐孙晶晶。她对我的研究工作提出了建设性的意见和各方面的指导和帮助。无论在学习方面还是生活方面遇到困难时，他们总能及时给予帮助、支持与鼓励。我感谢他们的陪伴!

附录1源代码〔MeanShift算法时间代价实验〕function[rowcentercolcenterM00]=meanshift(I,rmin,rmax,cmin,...cmax,probmap)tic;M00=0;%zerothmeanM10=0;%firstmomentforxM01=0;%firstmomentforyhistdim=(0:1:255);%dimensionsofhistogram...0to255,incrementby1[rowscols]=size(I);cols=cols/3;forc=cmin:cmaxforr=rmin:rmaxM00=M00+probmap(r,c);endendforc=cmin:cmaxforr=rmin:rmaxM10=M10+c*probmap(r,c);M01=M01+r*probmap(r,c);endendtoc;colcenter=M10/M00;rowcenter=M01/M00;*92源代码〔CamShift算法时间代价实验〕camshiftfunction[trackmovprobmovcenters]=camshifttic;rmin=0;rmax=0;cmin=0;cmax=0;numofframes=0;threshold=1;centerold=[00];centernew=[00];M=aviread('vipmen.avi');[dontneednumberofframes]=size(M);imagecenters=zeros(numberofframes,2);Frame1=M(1,1);Image1=frame2im(Frame1);[cmin,cmax,rmin,rmax]=select(Image1);cmin=round(cmin);cmax=round(cmax);rmin=round(rmin);rmax=round(rmax);wsize(1)=abs(rmax-rmin);wsize(2)=abs(cmax-cmin);hsvimage=rgb2hsv(Image1);huenorm=hsvimage(:,:,1);hue=huenorm*255;hue=uint8(hue);histogram=zeros(256);fori=rmin:rmaxforj=cmin:cmaxindex=uint8(hue(i,j)+1);histogram(index)=histogram(index)+1;endendfori=1:numberofframesFrame=M(1,i);I=frame2im(Frame);hsvimage=rgb2hsv(I);huenorm=hsvimage(:,:,1);hue=huenorm*255;hue=uint8(hue);[rowscols]=size(hue);probmap=zeros(rows,cols);forr=1:rowsforc=1:c