畢業(yè)設(shè)計（論文）文獻(xiàn)綜述：基于Mean Shift算法的計算復(fù)雜度研究

畢業(yè)設(shè)計（論文）--文獻(xiàn)綜述綜述題目基于MeanShift算法的計算復(fù)雜度研究專業(yè)信息與計算科學(xué)姓名學(xué)號指導(dǎo)教師

基于MeanShift算法的計算復(fù)雜度研究摘要近年來MeanShift算法被廣泛應(yīng)用于圖像處理和追蹤等方面，是目前視覺目標(biāo)追蹤領(lǐng)域的重要研究方向.首先介紹了MeanShift算法僅僅依靠特征空間中的樣本點進(jìn)行分析和處理，算法原理簡單，易于并行和實現(xiàn)，不需要任何先驗知識和統(tǒng)計參數(shù)估計，采用MeanShift算法，追蹤過程中只需通過較少的迭代次數(shù)就能收斂到點的分布中密度最大的地方.然后在理解MeanShift算法的基礎(chǔ)上計算其復(fù)雜度，同時對另外的CamShift算法的復(fù)雜度進(jìn)行計算，并對兩種算法的復(fù)雜度研究方法進(jìn)行對比分析.關(guān)鍵詞目標(biāo)追蹤；MeanShift算法；時間復(fù)雜度；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算法概念的最早出現(xiàn)，可以追溯到1975年，概率密度梯度函數(shù)的估計描述由Fukunaga等人提出[1]，它指的是一個相對迭代的連續(xù)過程。主要包括（1）計算出當(dāng)前目標(biāo)點的均值偏移量；（2）移動該目標(biāo)點到其計算所得到的偏移均值處；（3）以該點為新的起始點繼續(xù)移動，直滿足預(yù)先設(shè)定的條件后自動結(jié)束移動。該方法簡單有效，但這個概念在被提出和驗證之后并沒有立即引起大家的關(guān)注，直到另外一篇關(guān)于MeanShift算法的文獻(xiàn)發(fā)表，對其在計算機視覺領(lǐng)域的廣泛應(yīng)用才起到了真正的推動作用。隨著近年來計算機視覺領(lǐng)域的不斷發(fā)展，越來越多的研究者將目光聚焦在了MeanShift算法在基于目標(biāo)追蹤的不同應(yīng)用中的改進(jìn)和發(fā)展。作為一種有效的統(tǒng)計迭代算法，該算法在計算機視覺與模式識別等領(lǐng)域得到了更為廣泛的應(yīng)用，例如目標(biāo)追蹤[2-3]、圖像分割[4]、模式識別[5]、聚類分析[6]與濾波等方面，引起越來越多人對它的關(guān)注。由于MeanShift方法僅僅依靠特征空間中的樣本點進(jìn)行分析和處理，算法原理簡單，易于并行和實現(xiàn)，不需要任何先驗知識和進(jìn)行統(tǒng)計參數(shù)估計，在實現(xiàn)MeanShift算法過程中，只需通過較少的迭代次數(shù)就能收斂到點的分布中密度最大的地方，因此在理解MeanShift算法的基礎(chǔ)上計算其復(fù)雜度較易實現(xiàn)。目前已有很多關(guān)于目標(biāo)追蹤技術(shù)的算法，從目標(biāo)追蹤的依據(jù)手段來看，現(xiàn)階段已有的目標(biāo)追蹤算法可以分為基于先驗知識和非基于先驗知識。這兩方面從結(jié)果的側(cè)重點來看，現(xiàn)有的目標(biāo)追蹤算法又可以分為側(cè)重于運動目標(biāo)區(qū)域追蹤和側(cè)重于運動目標(biāo)運行軌跡追蹤兩大類。兩種方式各有特色，但是都面臨著兩個相同的問題：背景噪聲的干擾和缺乏目標(biāo)追蹤的實時性。要想解決上述兩個問題就必須先對目標(biāo)追蹤算法的基本思想進(jìn)行分析和歸納。大多數(shù)目標(biāo)追蹤算法的基本思想都以其特征值的匹配和特征值的提取兩個方面為核心。從排除噪聲干擾的角度來說，提取多種特征以及復(fù)雜的特征匹配規(guī)則顯然是最有利的，但是這樣不但增加了算法的復(fù)雜度，而且還影響了算法實現(xiàn)的實時性。所以，如何能快速而又有較強“抗噪”能力地從視頻序列中提取出代表性的特征成為了當(dāng)前解決問題的關(guān)鍵。2國內(nèi)外研究現(xiàn)狀這些年來，國內(nèi)外很多學(xué)者都在目標(biāo)追蹤的技術(shù)領(lǐng)域上花費了大量的時間，并且深度研究了各式各樣的追蹤算法，定期都會在一些國際重要會議上發(fā)表大量研究成果，其中重要的會議包括ECCV、CVPR、ICCV等。這些會議為研究學(xué)者們提供了廣泛的交流和學(xué)習(xí)的平臺。MeanShift概念最早是1975年由Fukunaga[5]等人在關(guān)于一篇概率密梯度函數(shù)的文獻(xiàn)中估計中提出來的，最初的含義，就是均值向量的偏移。即，均值漂移。然而經(jīng)過的很長一段時間，并沒有引起人們的注意。直到1995年，另外一篇關(guān)于MeanShift算法的重要文獻(xiàn)才發(fā)表[6]。在關(guān)于MeanShift的追蹤算法中，自從提出以來就受到廣泛研究者的青睞，在基于算法框架下的研究與改進(jìn)是視覺目標(biāo)追蹤領(lǐng)域的一個研究方向。在國外，有許多研究機構(gòu)。例如，美國國防高級研究項目署（DARPA,DefenseAdvancedResearchProjectionAgency）在1997年就建立了監(jiān)控視頻的項目（VideoSurveillanceandMonitorProjects），與此同時有許多國外高校參加研究討論，這其中就包括卡內(nèi)基梅隆大學(xué)、麻省理工學(xué)院等，最后他們的研究成果多數(shù)用于軍事或民用的監(jiān)控視頻系統(tǒng)中[7]。2005年，Comaniciu[8]和Meer兩位學(xué)者經(jīng)過深度的研究分析，成功地把目標(biāo)追蹤MeanShift算法運用于特征空間分析中,并在許多文獻(xiàn)中論述了MeanShift算法中核函數(shù)帶寬的選擇問題，雖然表面看起來計算量比較大,實用性不強,但是很有理論價值，是向真理邁出的重要一步。經(jīng)過時間的沉淀，ChangjiangYang在此基礎(chǔ)上又對多維圖像領(lǐng)域的方法進(jìn)行了研究討論，研究結(jié)果表明，在算法計算時選用高斯核之后,因為高斯核與圖像卷積的運算量過大,因此采用了改進(jìn)的方法。采用快速高斯核變換，可以大大提高算法的運行速度。然后Collins在此基礎(chǔ)之上提出了尺度空間和高斯核相結(jié)合的理論。解決了核函數(shù)帶寬在目標(biāo)實時追蹤變化時的問題,但算法在速度方面不是很好。在國內(nèi)，有許多大學(xué)及各項研究機構(gòu)都深入研究了目標(biāo)追蹤算法[9]，例如：清華大學(xué)、上海交通大學(xué)、華中科技大學(xué)、哈爾濱工業(yè)大學(xué)等高校的人機交互所、媒體集成研究所、微軟亞洲研究院視覺研究小組，都在目標(biāo)追蹤領(lǐng)域做了大量的研究工作，并取得一些不錯的成果和很大的進(jìn)展。3MeanShift算法3.1無參密度估計概率密度估計通常分為有參數(shù)法和無參數(shù)法兩類，旨在尋找滿足樣本集要求的概率密度函數(shù)[3]。所謂參數(shù)法就是先將密度函數(shù)的形式簡單地假設(shè)出來，然后在數(shù)據(jù)采樣的過程中估計出描述密度函數(shù)的各個參數(shù)。例如，預(yù)先假定了正態(tài)形式的概率密度函數(shù)，則易知其均值和方差都為所要估計的參數(shù)。但是在實際應(yīng)用中，尤其是計算機視覺領(lǐng)域中，預(yù)先假定的概率密度函數(shù)的形式往往不能符合實際應(yīng)用情況，這是因為數(shù)據(jù)的模型幾乎都是未知的，而且對概率密度函數(shù)的先驗知識又知之甚少。另外，經(jīng)典的概率密度函數(shù)常為單峰的，就是說，只有單個局部極大值，這與實際中常見的多峰模型是相悖的。這時候無參數(shù)估計方法就體現(xiàn)出了其優(yōu)越和實用性。而無參數(shù)方法無須預(yù)先假設(shè)密度函數(shù)的結(jié)構(gòu)形式，可由落入某一連續(xù)點鄰域中的若干樣本點估計出其密度函數(shù)值。這種方法的優(yōu)勢在于不需要對先驗知識過多的了解，而完全依靠訓(xùn)練數(shù)據(jù)來進(jìn)行估計，可以對任意分布進(jìn)行密度估計，應(yīng)用十分廣泛。典型的無參數(shù)密度估計方法有最近鄰域法、直方圖法及核密度估計法。（1）直方圖法：直方圖法是最早的且應(yīng)用最為廣泛的無參密度估計方法。直方圖法通常是把數(shù)據(jù)的值域分為若干相等區(qū)間，把數(shù)據(jù)按閾值填充到各個區(qū)間內(nèi)，每個區(qū)間的一組數(shù)據(jù)用一個矩形表示，其高度與該組數(shù)據(jù)的多少成正比，將這些矩形按照區(qū)間的次序排列起來就組成了直方圖，它的優(yōu)點在于它表示的數(shù)據(jù)分布給人清晰直觀的感覺，缺點是只適用于描述低維的數(shù)據(jù)。（2）最近鄰域法：該方法是由Cover等人于1968年提出的。該方法的思路是比較已知類別與未知樣本間的歐式距離，并判斷出該樣本點的離它最近的樣本同類。該方法的缺點是容易受到局部噪聲的干擾，所以模型估計變得十分困難。（3）核密度估計法：核密度估計方法于上世紀(jì)50到六十年代被提了出來，其基本思想與直方圖法類似。把采樣數(shù)據(jù)的值域分成若干個相等的區(qū)間，每個區(qū)間稱為一個bin，把數(shù)據(jù)按閾值分配到各個區(qū)間，則bin的概率值就是每組數(shù)據(jù)的個數(shù)與參樣個數(shù)總數(shù)的比值。與直方圖法相比，核密度估計法是一種平滑的無參數(shù)估計方法，它增加了一個平滑數(shù)據(jù)的核函數(shù)。該方法的優(yōu)點在于可以進(jìn)行快速的無偏密度估計，概率統(tǒng)計性質(zhì)良好，但是比較適合中小規(guī)模的數(shù)據(jù)集，這是該方法的一個局限。系統(tǒng)仿真是以相似原理、系統(tǒng)技術(shù)、信息技術(shù)及其應(yīng)用領(lǐng)域有關(guān)專業(yè)技術(shù)為基礎(chǔ)，以計算機和各種專用物理效應(yīng)設(shè)備為工具，利用系統(tǒng)模型對真實的或假想的系統(tǒng)進(jìn)行動態(tài)研究的一門多學(xué)科的綜合性技術(shù).相似論是系統(tǒng)仿真的主要理論依據(jù)[4].系統(tǒng)仿真研究的對象是系統(tǒng).系統(tǒng)是指具有某些特定功能、按照某些規(guī)律結(jié)合起來、互相作用、互相依存的所有事物的集合或總和.任何系統(tǒng)都存在三方面需要研究的內(nèi)容，即實體、屬性和活動.實體是存在于系統(tǒng)中的每一項確定的物體.屬性是實體所具有的每一項有效的特性.活動是導(dǎo)致系統(tǒng)狀態(tài)發(fā)生變化的一個過程.活動是在一段時間內(nèi)發(fā)生的情況,活動反映了系統(tǒng)的變化規(guī)律.存在系統(tǒng)內(nèi)部的實體、屬性和活動組成的整體稱為系統(tǒng)的狀態(tài).處于平衡狀態(tài)的系統(tǒng)統(tǒng)稱為靜態(tài)系統(tǒng)，狀態(tài)隨時間不斷變化著的系統(tǒng)為動態(tài)系統(tǒng).3.2彩色空間的選擇在計算機中，[10-11]彩色模型（又稱彩色空間或彩色系統(tǒng)）的用途是在某些標(biāo)準(zhǔn)下用通?？梢越邮艿姆绞奖阌趯Σ噬右哉f明。本質(zhì)上，彩色模型是坐標(biāo)系統(tǒng)和子空間的闡述。位于系統(tǒng)中的每種顏色都由單個點來表示對顏色而言它有多種不同的表達(dá)方式，這樣就形成了各種不同的顏色空間。最常見的顏色空間有：RGB和HSV等。每一種顏色空間都它各自產(chǎn)生的背景和應(yīng)用領(lǐng)域，在實際中，應(yīng)根據(jù)具體的應(yīng)用來選擇合適的顏色空間。列舉以下兩種常見顏色空間的進(jìn)行簡單介紹。（1）RGB顏色空間：是根據(jù)人眼識別的顏色定義的空間，可表示大部分的顏色，它是最通用的面向硬件的彩色模型，如彩色監(jiān)視器和彩色視頻攝像等。它采用三基色原理，將自然界中的色用R、G、B三基色按不同的比例相加混合而成。RGB的顏色空間可以用一個三維的立方體來表示[12]，如圖3.1所示。這是最常見的色系坐標(biāo)系，由R(紅)、G(綠)和B(藍(lán))三個分量組成，所有R，G，B分量都在[0,1]之間取值。三維空間中三個軸分別與紅、綠、藍(lán)三基色相對應(yīng)，原點對應(yīng)于黑色，離遠(yuǎn)點最遠(yuǎn)的點對應(yīng)于白色，而其他顏色則落在三維空間中由紅、綠、藍(lán)三基色組成的彩色立方體中。對角線從黑(0,0,0)到白(1,1,1)代表的是灰度。通常情況下以RGB色系坐標(biāo)為基礎(chǔ)描述其它色系坐標(biāo)系，將其它色系坐標(biāo)系的基色描述為RGB三色的線性或者非線性函數(shù)。圖3.1RGB顏色的立體示意圖在RGB彩色模型中，所表示的圖像由三個圖像分量組成，每個分量圖像都是其原色圖像。當(dāng)送入RGB監(jiān)視器時，這三幅圖像在熒光屏上混合產(chǎn)生一幅合成的彩色圖像。在RGB空間中，用于表示每一像素的比特數(shù)，稱為像素深度。考慮RGB圖像，其中每一幅紅、綠、藍(lán)圖像都是一幅8比特圖像，在這種條件下，每個RGB彩色像素（R、G、B）值三個一組稱為有24比特深度（三個圖像平面乘以每平面比特數(shù)）全彩色圖像常用來定義24比特的彩色圖像。在24比特RGB圖像中，顏色總數(shù)是。（2）HSV空間：HSV（hue，Saturation，value）色彩屬性模式是根據(jù)色彩的三個基本屬性:色度、飽和度和亮度來確定顏色的一種方法。其中H是色調(diào)，是色彩的基本屬性，也就是平常所說的紅，橙，黃，綠，藍(lán)等顏色名稱，不受色彩鮮淡，明暗的影響。S是飽和度，表示顏色深淺的程度，飽和度越高色彩越深，越低則逐漸變淺。V是亮度，表示某種顏色明暗的程度。4MeanShift算法追蹤原理4.1MeanShift向量Fukunaga對于MeanShift的定義為：給定d維空間中的n個樣本點，i=1,…n。在x點的MeanShift向量的基本形式定義為：（4-SEQ（\*ARABIC\s31）其中，k表示在這兒n個樣本點中，有k個點落入?yún)^(qū)域中。是一個半徑為h的高維球區(qū)域，滿足以下關(guān)系的y點的集合：（4-2）式（3-SEQ（\*ARABIC\s32）的物理意義如圖3.3所示[17]。核函數(shù)的中心x點用中間黑點表示，周圍表示樣本點，是相對于x的偏移向量，平均的偏移量指向樣本點最密的方向，即梯度方向如箭頭方向所示。由圖可見，而只要是落入?yún)^(qū)域的采樣點，無論其離中心點x的遠(yuǎn)近，對最終的計算的貢獻(xiàn)是一樣的。而在實際的跟蹤過程中，當(dāng)跟蹤目標(biāo)出現(xiàn)遮擋等影響時，由于外層的像素值容易受遮擋或背景的影響，所以目標(biāo)模型中心附近的像素比靠外的像素更可靠。中心像素給的權(quán)值大些，離中心點越遠(yuǎn)，賦的權(quán)值越小。并且在所有的樣本點中，每個樣本點的重要性也應(yīng)該是不同的。因此在這里又引進(jìn)了核函數(shù)和權(quán)重系數(shù)的概念來提高跟蹤算法的魯棒性并增加搜索跟蹤能力。圖4.1MeanShift向量的示意圖這樣就可以把MeanShift形式擴展為：（4-3）其中，是一個單位核函數(shù)，，是一個賦給采樣點的權(quán)重。（4-4）4.2模板建立MeanShift算法是用人機交互的方法來對被跟蹤目標(biāo)進(jìn)行初始化的。假設(shè)給定兩幀圖像，在第一幀中用鼠標(biāo)選定一個包含目標(biāo)特征的矩形或橢圓區(qū)域，該區(qū)域稱為目標(biāo)模型，區(qū)域的大小就是核函數(shù)的帶寬，另一幀圖像則稱為候選模型。目標(biāo)跟蹤的任務(wù)就是在候選模型中找出被跟蹤的目標(biāo)，并對其精確定位。目標(biāo)模型中的采樣點表示為，這里為像素在圖像中的二維坐標(biāo)，而則為該像素對應(yīng)的特征向量。候選圖像中的采樣點表示為，同樣給出了采樣點的二維坐標(biāo)和對應(yīng)的特征向量。特征向量是由特征空間中所有特征值組成的，特征空間可以是由顏色空間、紋理空間等來描述，特征值表示為某一空間中圖像像素值的核密度估計。MeanShift算法首先要在初始幀內(nèi)為被跟蹤目標(biāo)建立概率模型。設(shè)在初始幀中，采用手動方法通過鼠標(biāo)選定一個包含被跟蹤目標(biāo)區(qū)域的外接矩形或橢圓，即被跟蹤目標(biāo)的目標(biāo)窗口，其中包含n個像素點。這個目標(biāo)區(qū)域即時核函數(shù)的作用區(qū)域，區(qū)域的大小就是核函數(shù)的帶寬。如果采用RGB顏色空間，按照直方圖方法將每個基色子空間R、G、B均勻地分成k個互不相交的區(qū)間，每個區(qū)間為一個特征值，稱為一個bin，那么整個RGB顏色空間中bin的個數(shù)或者說特征空間空特征值的個數(shù)為。假設(shè)目標(biāo)的中心位于處，表示目標(biāo)模型的像素位置，那么目標(biāo)模板的概率密度估計可表示為：（4-5）其中，k是核函數(shù),h為核窗寬，決定著權(quán)重的分布，表示處象素的顏色值，u為直方圖的顏色索引，范圍是l~n。為Kroneckerdelta函數(shù)，作用是判斷目標(biāo)區(qū)域中像素的顏色值是否屬于第u個單元的顏色索引值，等于為1，否則為0。C是歸一化系數(shù)，表達(dá)式為：（4-6）運動目標(biāo)在第二幀及以后的每幀中可能包含目標(biāo)的區(qū)域稱為候選目標(biāo)區(qū)域，也就是說在第n幀時，根據(jù)第n-1幀的目標(biāo)位置y，以y為搜索窗口中心坐標(biāo)用同樣的核函數(shù)計算當(dāng)前幀的候選目標(biāo)區(qū)域直方圖。那么候選模板的概率密度估計表示為：（4-7）其中為歸一化系數(shù)，相當(dāng)于式（3-5）中的C。（4-8）4.3相似性度量給出了目標(biāo)模型表示后，在當(dāng)前幀中尋找目標(biāo)位置的任務(wù)可以歸納為：在當(dāng)前幀中尋找最優(yōu)的y使目標(biāo)模板與候選目標(biāo)模板()最相似。于是引入了Bhattacharyya系數(shù)作為相似性函數(shù)來衡量目標(biāo)模板和候選目標(biāo)區(qū)域?qū)?yīng)的直方圖之間的相似性。以兩個直方圖的相似性最大為原則，使搜索窗口沿密度增加最大的方向移動到目標(biāo)的真實位置。其中為目標(biāo)模板，為候選目標(biāo)模板，u=1…m。其值在0-1之間，越大，表示兩個模板越相似。（4-9）為了使最大，將當(dāng)前幀的目標(biāo)中心先定位為前一幀中目標(biāo)中心的位置，從這一點開始尋找最優(yōu)匹配的目標(biāo)。目標(biāo)定位的過程就是把求取距離最小值轉(zhuǎn)化為求Bhattacharyya系數(shù)最大值的問題。為了得到Bhattacharyya系數(shù)的最大值，現(xiàn)在要對進(jìn)行分析，先以前一幀目標(biāo)的中心坐標(biāo)作為當(dāng)前幀中目標(biāo)區(qū)域的中心，在該點為起始點的某一鄰域內(nèi)對目標(biāo)進(jìn)行搜索。已知，將（3-8）在處進(jìn)行泰勒展開，舍去高階項，則可近似為：（4-10）式（3-9）中第一項為常量，第二項是y的函數(shù)。要使最大，只需使第二項取得最大值。對于第二項，令（4-11）上式可以看作輪廓函數(shù)為，權(quán)重為的樣本點在y處的密度估計。根據(jù)MeanShift算法原理，可以推導(dǎo)出以為候選區(qū)域中心，平移到目標(biāo)區(qū)域中心y的MeanShift向量：（4-12）一次迭代后目標(biāo)的新位置為,當(dāng)一次迭代完成之后，令，然后開始下一次迭代，重復(fù)這個過程直至，則進(jìn)行下一幀的運算，否則根據(jù)新坐標(biāo)計算的候選直方圖繼續(xù)計算均值漂移向量。5CamShift算法原理CamShift算法（ContinuouslyAdaptiveMean-Shift）基本思想是，從初始幀開始，將追蹤視頻圖像里的每一幀都作MeanShift迭代運算，并將上一幀的追蹤結(jié)果，包括搜索窗口的中心值的大小，作為下一幀MeanShift追蹤算法搜索窗口的初始值，如此一直迭代下去，不斷收斂到目標(biāo)中心密度值最大的地方，就可以實現(xiàn)對追蹤目標(biāo)的追蹤。同MeanShift一樣，CamShift算法也采用目標(biāo)模板及候選模板，CamShift算法采用的目標(biāo)模板是顏色直方圖（HSV顏色空間），根據(jù)追蹤目標(biāo)顏色空間的反向投影圖得到下一幀追蹤圖像幀的顏色概率分布直方圖，在此基礎(chǔ)上，計算追蹤目標(biāo)的質(zhì)心，將搜索窗口的中心不斷移動到質(zhì)心，當(dāng)中心與質(zhì)心的距離小于設(shè)定的固定閾值時（一般情況下，取兩個像素之間的大小），或者當(dāng)?shù)拇螖?shù)小于設(shè)定的最大值時，此時得到的質(zhì)心的位置即為目標(biāo)的位置。對于CamShift追蹤算法，主要分為三個部分：（1）色彩投影圖RGB顏色空間對光照亮度變化和強度較為敏感，為了減少此變化對追蹤效果的影響，將圖像從RGB顏色空間轉(zhuǎn)換到HSV顏色空間。（2）H分量作直方圖用H分量作出的直方圖，在直方圖中代表了不同的H分量，同時分量的值也代表出現(xiàn)的概率或者出現(xiàn)的像素個數(shù)，簡單來說，就是可以查找出H分量的大小，即得到了顏色概率分布。（3）顏色概率分布將圖像中每個追蹤圖像幀數(shù)的值用其顏色出現(xiàn)的概率對替換，就獲得了顏色概率分布直方圖。這個過程就是反向投影的過程[25-26]，而顏色概率分布圖是一個灰度圖像。6算法復(fù)雜度分析6.1時間復(fù)雜度算法的時間復(fù)雜性分析是一種事前分析估算的方法，它是對算法所消耗資源的一種漸進(jìn)分析方法。所謂漸進(jìn)分析是指忽略具體機器、編程語言和編譯器的影響，只關(guān)注在輸入規(guī)模增大時算法運行時間的增長趨勢。漸進(jìn)分析的好處是大大降低了算法分析的難度，是從數(shù)量級的角度評價算法的效率。一個算法執(zhí)行所耗費的時間從理論上是不能算出來的，必須上機運行測試才能知道但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度記為。在剛才提到的時間頻度中，n稱為問題的規(guī)模，當(dāng)不斷變化時，時間頻度也會不斷變化，但有時我們想知道它變化時呈現(xiàn)什么規(guī)律，為此，引入時間復(fù)雜度概念。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模的某個函數(shù)，用表示，若有個輔助函數(shù),使得當(dāng)趨近于無窮大時，的極限值為不等于零的常數(shù)，則稱是的同數(shù)量級函數(shù)。記作。稱為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個常數(shù)，則時間復(fù)雜度為。另外,在時間頻度不相同時，時間復(fù)雜度有可能相同。如與它們的頻度不同，但時間復(fù)雜度相同[8]，都為按數(shù)量級遞增排列。常見的時間復(fù)雜度有常數(shù)階，對數(shù)階，線性階，線性對數(shù)階，平方階，立方階,…，次方階，指數(shù)階。隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。6.2空間復(fù)雜度空間復(fù)雜度（SpaceComplexity）是一個算法在運行過程中臨時占用存儲空間量度的大小。比如，插入排序的時間復(fù)雜度是O()。空間復(fù)雜度是而一般的遞歸算法就要有的空間復(fù)雜度了，因為每次遞歸都要存儲返回信息。一個算法的優(yōu)劣主要從算法的執(zhí)行時間和所需要占用的存儲空間兩個方面而衡量。關(guān)于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度是定義為該算法所耗費的存儲空間[10]，它是問題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度。算法在運算過程中所需的存儲空間包括：執(zhí)行算法需要的輔助空間；算法本身占用的空間；輸入輸出數(shù)據(jù)占用的空間。算法需要占用的臨時空間存儲單元數(shù)與解決問題的規(guī)模n息息相關(guān)，它隨著n的變化而變化，當(dāng)n變大時，將占用較多的空間存儲單元。輔助空間數(shù)量是算法空間復(fù)雜性在算法的執(zhí)行過程中的必要因素，簡單來說也就是除算法本身之外的空間，即：算法臨時開辟的存儲空間，是輔助空間數(shù)量輸入規(guī)模的函數(shù)，記作與時間復(fù)雜性相類似，空間復(fù)雜性是指算法在計算機內(nèi)執(zhí)行時所需存儲空間的度量。本文討論的兩種算法空間復(fù)雜度相差不大，因此著重研究時間復(fù)雜度6.3復(fù)雜度分析方法在計算時間復(fù)雜度的過程中，最關(guān)鍵的是要算出算法語句中最多的執(zhí)行次數(shù)。在很多學(xué)者看來，算法中最內(nèi)層循環(huán)體語句往往具有最大的語句頻度，在MeanShift算法及CamShift算法計算時間復(fù)雜度過程中，主要對它們進(jìn)行分析和計算。目前，算法的時間復(fù)雜度分析方法可以歸納為如下幾種：（1）求和法。在當(dāng)算法中語句的執(zhí)行次數(shù)與某一變量有直接關(guān)系的背景下，該變量的變化起止范圍又較為明確，則可以利用求和公式得出最大的語句頻度，再對其取數(shù)量級(階)即可。（2）假設(shè)法。在某些較為復(fù)雜的算法中，循環(huán)結(jié)構(gòu)的循環(huán)次數(shù)很難直接看出，特別是當(dāng)循環(huán)次數(shù)與循環(huán)體中的某些語句執(zhí)行有聯(lián)系時，語句頻度的計算變得比較困難。此時，可以先假設(shè)循環(huán)執(zhí)行次數(shù)為k次，再對算法進(jìn)行分析，根據(jù)循環(huán)終止條件求出語句頻度，最后求出。（3）迭代法。當(dāng)算法中包含遞歸函數(shù)時，其時間復(fù)雜度也會被轉(zhuǎn)化為一個遞歸方程，上述兩種方法此時不再適用。遞歸方程的形式多種多樣，其求解方法也是不一而足，比較常用是迭代法。MeanShift算法及CamShift算法適用的即是此種算法。其基本步驟是迭代地展開遞歸方程的右端，使之成為一個非遞歸的和式，然后通過對和式的估計來得到時間復(fù)雜度。在分析時間復(fù)雜度時，須遵從以下幾個簡單的程序分析法則：（1）對于一些簡單的輸入輸出語句或賦值語句，近似認(rèn)為需要時間（2）對于順序結(jié)構(gòu)，需要依次執(zhí)行一系列語句所用的時間可采用大下的“求和法則”。求和法則：是由算法法則的2個部分組成，時間復(fù)雜度分別為和，則，若，，則。（3）對于選擇結(jié)構(gòu)，如if語句，它的主要時間耗費是在執(zhí)行then字句或else字句所用的時間，需注意的是檢驗條件也需要時間。（4）對于循環(huán)結(jié)構(gòu)，循環(huán)語句的運行時間主要體現(xiàn)在多次迭代中執(zhí)行循環(huán)體以及檢驗循環(huán)條件的時間耗費，一般可用大下的“乘法法則”。乘法法則：是由算法的2個部分組成。故，時間復(fù)雜度分別為和則。（5）對于復(fù)雜的算法，可以將它分成幾個容易估算的部分，然后利用求和法則和乘法法則技術(shù)，并采用以下2個運算法則：（1）若，則；（2），其中C是一個正常數(shù)。如果一個算法的復(fù)雜度為、

、、

，那么這個算法時間效率比較高；如果是

、和，那么稍微大一些的n就會令這個算法不能動了，居于中間的幾個則差強人意。計算時間復(fù)雜度的分析過程是一個很重要的流程，任何一個實驗人都應(yīng)該熟練掌握該算法的概念和基本方法，而且要善于探尋算法復(fù)雜度的本質(zhì)，只有這樣才能真正的去學(xué)會它。7總結(jié)當(dāng)前多數(shù)使用基于算法的目標(biāo)追蹤不能很好實時改變核窗寬的特點，提出了一種基于目標(biāo)中心定位和特征的追蹤算法。在目標(biāo)追蹤過程中，通過建立二值模型，利用特征識別要追蹤的目標(biāo)，追蹤過程始終定位目標(biāo)的中心。結(jié)合算法的尋優(yōu)相似度函數(shù)，選擇最優(yōu)的核窗寬。目標(biāo)在移動過程中，其中心點也是在做不規(guī)則的移動，以中心點為基點來擴展追蹤窗口。從而使得在追蹤目標(biāo)的每一幀圖像里，能夠準(zhǔn)確的放縮追蹤窗口，進(jìn)而使得在目標(biāo)特征能夠持續(xù)的被檢測到。在這基礎(chǔ)之上通過分析MeanShift及CamShift兩種不同算法，計算兩種算法的復(fù)雜度，進(jìn)行比較分析，最終得出復(fù)雜度分析結(jié)論。參考文獻(xiàn)[1]呂國英,任瑞征,錢宇華.算法設(shè)計與分析[M].北京:清華大學(xué)出版社,2006.[2]田莘.基于MeanShift算法的目標(biāo)追蹤問題研究[D].西安電子科技大學(xué)碩士學(xué)位論文,2010.[3]顧幸芳.李秋潔.基于MeanShift的視覺目標(biāo)追蹤算法綜述[J].計算機科學(xué),2012,2(6):604-608.[4]馮帆.復(fù)雜度可分級的目標(biāo)追蹤算法研究[D].華中科技大學(xué)碩士學(xué)位論文,2013.[5]姜明新.智能視頻監(jiān)控中的目標(biāo)追蹤技術(shù)研究[D].大連理工大學(xué)碩士學(xué)位論文,2013.[6]許曉麗.基于聚類分析的圖像分割算法研究[D].哈爾濱工程大學(xué)碩士學(xué)位論文,2012.[7]何革.基于MeanShift算法的視頻目標(biāo)追蹤研究[D].重慶大學(xué)碩士學(xué)位論文,2012.[8]覃劍.視頻序列中的運動目標(biāo)檢測與追蹤研究[D].重慶大學(xué)碩士學(xué)位論文,2014.[9]張宇山.進(jìn)化算法的收斂性與時間復(fù)雜度分析的若干研究[D].華南理工大學(xué)碩士學(xué)位論文,2013.[10]殷超.常用算法時間復(fù)雜度的計算方法[J].科技信息,2011,26(1):118-184.[11]ShioA,SklanskyJ.Segementationofpeopleinmotion[A].IEEE