畢業(yè)設(shè)計(jì)（論文）mean shift目標(biāo)追 蹤算法計(jì)算復(fù)雜度分析

摘要運(yùn)動(dòng)目標(biāo)追蹤應(yīng)用于體育賽事直播、平安監(jiān)控和醫(yī)學(xué)診治等領(lǐng)域。本文主要分析MeanShift目標(biāo)追蹤算法及其改良的CamShift算法的計(jì)算復(fù)雜度。算法的時(shí)間復(fù)雜度是一種事前分析方法。闡述有關(guān)算法分析理論與方法，重點(diǎn)關(guān)注時(shí)間復(fù)雜度的分析方法。論述MeanShift目標(biāo)追蹤算法的根本原理，分析該算法在實(shí)際追蹤的過程中存在的優(yōu)缺點(diǎn)。MeanShift算法僅僅依靠特征空間中的樣本點(diǎn)進(jìn)行分析和處理，算法原理簡單，不需要先驗(yàn)知識(shí)，對(duì)目標(biāo)追蹤過程中存在遮擋情況處理不是很好，還有待改良。在分析MeanShift算法原理的根底上，闡述CamShift算法思想，對(duì)CamShift算法進(jìn)行算法描述與分析，比照兩種算法的時(shí)間復(fù)雜度。在分析兩種算法的時(shí)間復(fù)雜度時(shí)，采用時(shí)間代價(jià)函數(shù)作為度量標(biāo)準(zhǔn)，以追蹤同一視頻的不同消耗時(shí)間作為判斷依據(jù)，比擬兩種算法的時(shí)間復(fù)雜度。關(guān)鍵詞：目標(biāo)追蹤；MeanShift；時(shí)間復(fù)雜度；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

目錄摘要 的權(quán)重。(3-4)3.2MeanShift算法描述3.2.1偽代碼描述步驟一：選擇好目標(biāo)區(qū)域，圈定目標(biāo)初始估計(jì)位置與核窗寬h，建立目標(biāo)模板，并計(jì)算目標(biāo)模板的概率密度。步驟二：令迭代次數(shù)k=0；步驟三：用初始化當(dāng)前幀的目標(biāo)位置，計(jì)算候選目標(biāo)模板概率密度和權(quán)重系數(shù)；步驟四：計(jì)算目標(biāo)的新位置，候選目標(biāo)坐標(biāo)；步驟五：根據(jù)計(jì)算當(dāng)前窗口內(nèi)各點(diǎn)的權(quán)重值；步驟六：于1的像素間距設(shè)為閾值，如果那么停止，否那么←，執(zhí)行步驟一，重復(fù)移動(dòng)直至收斂；步驟七：算法結(jié)束。開始流程圖開始建立目標(biāo)模板確定初始位置建立目標(biāo)模板確定初始位置計(jì)算目標(biāo)候選模板計(jì)算目標(biāo)候選模板MeanShiftMeanShift迭代計(jì)算新的位置計(jì)算當(dāng)前窗口內(nèi)各點(diǎn)權(quán)重值計(jì)算當(dāng)前窗口內(nèi)各點(diǎn)權(quán)重值設(shè)定閾值設(shè)定閾值NONOYESYES讀取下一幀讀取下一幀圖3-SEQ圖\*ARABIC\s11MeanShift算法流程圖3.3MeanShift算法的缺乏MeanShift追蹤算法具有良好追蹤的實(shí)時(shí)性，是一種在追蹤領(lǐng)域較為簡單快捷的追蹤方法。但是MeanShift也存在以下缺點(diǎn)：〔1〕核函數(shù)HYPERLINK[23-24]直方圖對(duì)追蹤目標(biāo)的特征描述不明顯，在灰度圖像或者紋理圖像中，獲取的圖像信息較少?！?〕由當(dāng)MeanShift追蹤算法在追蹤目標(biāo)對(duì)象時(shí)容易出現(xiàn)局部極大值的情況、這樣會(huì)使該算法收斂速度變慢?！?〕雖然該算法計(jì)算速度較快，但是在追蹤方面，不能很好地解決目標(biāo)遮擋的問題。針對(duì)以上缺點(diǎn)，可以做出以下調(diào)整。〔1〕為進(jìn)一步減少M(fèi)eanShift追蹤的搜索時(shí)間，可以引入另一種追蹤算法進(jìn)行相應(yīng)的融合，如算法以便于預(yù)測(cè)移動(dòng)目標(biāo)的變化，從而降低計(jì)算量?！?〕傳統(tǒng)的MeanShift算法固定了內(nèi)核的帶寬，而不是動(dòng)態(tài)帶寬。所以更改為動(dòng)態(tài)帶寬會(huì)提高算法的追蹤性能。3.4CamShift算法描述3.4.1算法思想CamShift算法是MeanShift算法的改良，核心意義是，從初始幀選取開始，將追蹤視頻圖像里的每一幀以MeanShift算法為核心并依次做迭代運(yùn)算HYPERLINK[5]。然后把迭代后追蹤結(jié)果的中心值窗口的大小，作為下一幀MeanShift追蹤算法搜索窗口的初始值，如此一直迭代下去,不斷收斂到目標(biāo)中心密度值最大的地方，就可以實(shí)現(xiàn)對(duì)追蹤目標(biāo)的追蹤。根據(jù)追蹤目標(biāo)顏色空間的反向投影圖得到下一幀追蹤圖像幀的顏色概率分布直方圖，當(dāng)中心與質(zhì)心的距離小于設(shè)定的固定閾值時(shí)(一般情況下，取兩個(gè)像素之間的大小)，此時(shí)得到的質(zhì)心的位置。對(duì)于CamShift追蹤算法，主要分為三個(gè)局部：〔1〕色彩投影圖〔2〕H分量作直方圖〔3〕顏色概率分布由于CamShift算法是在MeanShift算法上的改良，所以描述MeanShift算法過程是其中不可缺少的一個(gè)環(huán)節(jié)。算法過程如下：〔1〕在顏色概率分布圖中選取搜索窗W〔2〕計(jì)算零階距：〔3-=5\*Arabic5〕計(jì)算一階距：〔3-=6\*Arabic6〕計(jì)算搜索窗的質(zhì)心：〔3-=7\*Arabic7〕〔3〕調(diào)整搜索窗大小寬度為；長度為1.2s；3.4.2CamShift算法步驟CamShift算法就是將MeanShift算法擴(kuò)展到連續(xù)圖像序列，在追蹤過程中可自適應(yīng)調(diào)整窗口大小。它將視頻的所有幀做MeanShift運(yùn)算并將上一幀的結(jié)果包括搜索窗口的大小和中心[9]，作為下一幀MeanShift算法搜索迭代的初始值。

算法過程為：〔1〕初始化搜索窗口；〔2〕計(jì)算搜索窗口的顏色概率分布〔反向投影圖〕；〔3〕對(duì)圖像運(yùn)行MeanShift算法，獲得搜索窗口新的大小和位置；整個(gè)CamShift算法的具體步驟分五步：步驟一：將整個(gè)圖像設(shè)為搜尋區(qū)域；步驟二：初始化搜索窗口的大小和位置；步驟三：計(jì)算搜索窗內(nèi)的彩色概率分布，此區(qū)域的大小比搜索窗要稍微大點(diǎn)；步驟四：運(yùn)行MeanShift，獲得搜索窗口新的位置和大?。徊襟E五：在下一幀視頻圖像中，用步驟三獲得的值初位置和大小。跳轉(zhuǎn)到步驟三繼續(xù)運(yùn)行。開始轉(zhuǎn)換圖像空間3.4.3CamShift算法流程圖開始轉(zhuǎn)換圖像空間否是得到目標(biāo)的質(zhì)心和窗口大小結(jié)束調(diào)整新的搜索窗位置判斷質(zhì)心是否收斂查找顏色直方圖計(jì)算搜索窗的質(zhì)心移動(dòng)搜索窗的中心到質(zhì)心位置在搜索搜索窗周圍窗口稍大的區(qū)域初始化搜索窗的大小和位置否是得到目標(biāo)的質(zhì)心和窗口大小結(jié)束調(diào)整新的搜索窗位置判斷質(zhì)心是否收斂查找顏色直方圖計(jì)算搜索窗的質(zhì)心移動(dòng)搜索窗的中心到質(zhì)心位置在搜索搜索窗周圍窗口稍大的區(qū)域初始化搜索窗的大小和位置圖3-SEQ圖\*ARABIC\s12CamShift算法流程圖CamShift追蹤算法的優(yōu)點(diǎn)是能夠有效解決目標(biāo)形變和遮擋的問題，對(duì)系統(tǒng)占用資源要求不高，時(shí)間復(fù)雜度相對(duì)較低，并在簡單背景下能夠取得良好的追蹤效果。但在追蹤過程中，當(dāng)背景較為復(fù)雜時(shí)，或有許多與目標(biāo)顏色相似的像素干擾的情況下，會(huì)導(dǎo)致追蹤失敗。它會(huì)忽略目標(biāo)的空間分布特性，因?yàn)樗鼉H僅考慮顏色直方圖。第四章算法分析4.1時(shí)間代價(jià)實(shí)驗(yàn)本文的度量標(biāo)準(zhǔn)以算法的幀率做比擬標(biāo)準(zhǔn)。通過計(jì)算機(jī)運(yùn)行時(shí)的計(jì)時(shí)功能獲得較為準(zhǔn)確的時(shí)間，然后對(duì)兩種算法進(jìn)行運(yùn)行時(shí)間的相互比擬。本文選取第一段具有代表性的測(cè)試視頻序列進(jìn)行追蹤實(shí)驗(yàn)，測(cè)試的環(huán)境為Inter(R)Core(TM)i5-4200HCPU@2.80GHZ處理器及4.0GB內(nèi)存，兩種目標(biāo)追蹤算法在MATLAB〔2021Rb〕環(huán)境下運(yùn)行實(shí)現(xiàn)，自行編寫了追蹤MATLAB主程序，調(diào)用Camshift源程序，并調(diào)用了tip和toc時(shí)間函數(shù)進(jìn)行處理，得到追蹤時(shí)間。在運(yùn)行過程中分別使用均值漂移算法和改良的MeanShift算法〔CamShift算法〕在同的環(huán)境參數(shù)設(shè)置下，對(duì)相同的源視頻進(jìn)行了處理，源視頻為兩個(gè)人在走廊的過道相遇，然后互相握手，最后離開的過程，為了使源視頻和源程序相匹配，把視頻轉(zhuǎn)換成無壓縮的AVI格式，視頻總幀數(shù)為282幀。計(jì)算出源視頻的總幀數(shù)和追蹤的總時(shí)間，二者用視頻總幀數(shù)比上追蹤的總時(shí)間得到幀率，用幀率分析兩種追蹤算法的復(fù)雜度。圖4-SEQ圖\*ARABIC\s11MeanShift算法追蹤視頻消耗的時(shí)間圖4-SEQ圖\*ARABIC\s12Camshift算法追蹤視頻消耗時(shí)間表4.SEQ表\*ARABIC\s11兩種算法對(duì)應(yīng)的運(yùn)行時(shí)間和幀率比照算法運(yùn)行時(shí)間〔S〕幀率〔FPS〕MeanShift算法9.839928.6CamShift算法7.850735.94.2追蹤實(shí)驗(yàn)效果分析兩種算法在追蹤同一視頻時(shí)，追蹤的效果會(huì)有所差異。那么衡量兩種算法追蹤效果的度量標(biāo)準(zhǔn)是，追蹤效果好的視頻幀數(shù)比上總的視頻幀數(shù)，作為本文度量依據(jù)。4.2.1實(shí)驗(yàn)設(shè)計(jì)選取第二段在靜態(tài)背景、單一場景、有目標(biāo)遮擋情況下的視頻，此段視頻的序列幀數(shù)共有216幀。實(shí)驗(yàn)環(huán)境為MATLAB〔2021Rb〕插入分幀函數(shù)，得到了從目標(biāo)模板選取開始到追蹤過程結(jié)束的視頻追蹤效果幀數(shù)。4.2.2采用MeanShift算法效果分析在使用MeanShift算法對(duì)第二段視頻進(jìn)行追蹤時(shí)，從實(shí)驗(yàn)結(jié)果得出當(dāng)目標(biāo)未遮擋時(shí)，該算法能很好的追蹤目標(biāo)。所選的目標(biāo)局部被遮擋時(shí)，追蹤的窗口就會(huì)停止在被遮擋的物體上，即使再次出現(xiàn)時(shí)，追蹤框也不能很好的再次定位在目標(biāo)上繼續(xù)追蹤。效果圖如圖4-3所示。a71幀b96幀c117幀d149幀e161幀f162幀圖4-SEQ圖\*ARABIC\s13MeanShift算法追蹤效果圖由上圖可以看出從視頻的第a圖71幀開始，手動(dòng)選定追蹤目標(biāo)，直到視頻的e圖161幀為止，被追蹤的目標(biāo)一直被抓住，沒有追蹤丟掉。從追蹤視頻的第162幀開始到追蹤結(jié)束，追蹤的目標(biāo)停留在被遮擋的物體上，即追蹤目標(biāo)喪失。故，追蹤目標(biāo)的追蹤良好率為0.41。4.2.3采用CamShift算法效果分析在使用CamShift算法對(duì)第二段視頻進(jìn)行追蹤效果，如圖4-4所示.a71幀b108幀c171幀d181幀e182幀f216幀圖4-SEQ圖\*ARABIC\s14CamShift算法追蹤效果圖從實(shí)驗(yàn)分析結(jié)果得出從視頻幀數(shù)的第a圖71幀開始，到追蹤過程中第d圖181幀，都能牢固的抓住追蹤目標(biāo)。所以當(dāng)追蹤目標(biāo)被遮擋時(shí)，依然可以追蹤到目標(biāo)，但是隨著追蹤目標(biāo)速度的加快從視頻的第e圖182幀到追蹤過程f圖216幀的結(jié)束，追蹤目標(biāo)丟掉。即蹤目標(biāo)的追蹤良好率為0.50。表4.SEQ表\*ARABIC\s12兩種追蹤算法良好率比照算法追蹤良好率〔〕MeanShift算法0.41CamShift算法0.50由表4.2得出MeanShift算法在目標(biāo)遮擋時(shí)，容易發(fā)生目標(biāo)追蹤不穩(wěn)定的情況。而采用CamShift算法在遮擋時(shí)不會(huì)被影響，但由于目標(biāo)移動(dòng)太快，所以追蹤過程中也會(huì)存在追蹤目標(biāo)喪失的情況。但總的來說改良的CamShift算法比原有的MeanShift算法追蹤效果會(huì)好一些，追蹤率也比MeanShift算法高。4.3時(shí)間復(fù)雜度分析在計(jì)算時(shí)間復(fù)雜度時(shí)，計(jì)算程序運(yùn)行的時(shí)間函數(shù)一般會(huì)遮蓋住算法自身的優(yōu)點(diǎn)和缺點(diǎn)，因此針對(duì)這種情況，采用事先分析估算的算法不失為一種解決的方法，只考慮算法問題的規(guī)模。用自然數(shù)來表示，在某種特殊算法下，問題的規(guī)模是影響時(shí)間度的唯一因素，簡單的說，計(jì)算算法的時(shí)間復(fù)雜度是問題的規(guī)模的某種函數(shù)。對(duì)于時(shí)間復(fù)雜度的比擬，比擬常見的手段是，首先從算法中選取一種所要研究的問題或算法模型，然后在進(jìn)行根本的運(yùn)算的操作，并重復(fù)執(zhí)行根本語句次數(shù)。以作為評(píng)價(jià)算法時(shí)間復(fù)雜度的標(biāo)準(zhǔn)。一般為。這兩種算法的時(shí)間復(fù)雜度都是跟輸入規(guī)模有關(guān)，根據(jù)MeanShift算法描述，進(jìn)行如下分析。步驟一：選擇好目標(biāo)區(qū)域，建立目標(biāo)模板計(jì)算目標(biāo)模板的概率密度，確定目標(biāo)初始估計(jì)位置與核窗寬h；步驟二：令迭代次數(shù)k=0；步驟三：用初始化當(dāng)前幀的目標(biāo)位置，計(jì)算候選目標(biāo)模板概率密度和權(quán)重系數(shù)；步驟四：計(jì)算目標(biāo)的新位置，候選目標(biāo)坐標(biāo)；步驟五：根據(jù)計(jì)算當(dāng)前窗口內(nèi)各點(diǎn)的權(quán)重值；步驟六：在一個(gè)距離大于1的像素間距設(shè)為閾值，如果那么停止，否那么，執(zhí)行步驟一，重復(fù)移動(dòng)直至收斂；把步驟六變成語句如下語句1語句2只有可運(yùn)行的語句才會(huì)增加時(shí)間復(fù)雜度，因此，上面的內(nèi)容除了循環(huán)之外，其余的可運(yùn)行語句的復(fù)雜度都是，這里面的是一個(gè)閾值，無論它的閾值多少，如果在一個(gè)大小為n循環(huán)中，循環(huán)變量按照一個(gè)常量c遞增或遞減，這個(gè)循環(huán)的復(fù)雜度就為。循環(huán)的復(fù)雜度與只與和的輸入規(guī)模有關(guān)，在上述程序中，語句1的時(shí)間頻度是，語句2的時(shí)間頻度是，因此。對(duì)于MeanShift算法，時(shí)間復(fù)雜度即為。而CamShift算法是MeanShift算法的改良，只是在MeanShift算法的根底上進(jìn)行改良，CamShift算法利用目標(biāo)的顏色直方圖模型得到每幀圖像的顏色投影圖，根據(jù)上一幀追蹤的結(jié)果自適應(yīng)調(diào)整搜索窗口的位置和大小，而得到當(dāng)前圖像中目標(biāo)的尺寸和中心位置。只是對(duì)搜索窗口進(jìn)行了改良。因此這兩種算法的時(shí)間復(fù)雜度都是，即。4.4比照分析表4.SEQ表\*ARABIC\s13兩種算法比照表算法運(yùn)行時(shí)間〔S〕幀率〔FPS〕時(shí)間復(fù)雜度〔O〕MeanShift算法9.839928.6T(n)=O(n)CamShift算法7.850735.9T(n)=O(n)綜上所述由表4.2可以看出采用Camshift追蹤算法比MeanShift追蹤算法的追蹤效果更好。由表4.3可以看出MeanShift算法追蹤的時(shí)間較長，CamShift算法時(shí)間效率比擬髙，Camshift追蹤算法幀率高于MeanShift算法，由于Camshift追蹤算法是MeanShift算法的改良，在追蹤視頻時(shí)所消耗的時(shí)間一定比MeanShift算法追蹤視頻時(shí)的時(shí)間短。

第五章總結(jié)5.1主要工作移動(dòng)目標(biāo)追蹤在近年來成為計(jì)算機(jī)視頻領(lǐng)域的一個(gè)熱門研究方向。但由于理論的不完整性和各種條件的限制，絕大多數(shù)的目標(biāo)追蹤算法都是在某一具體情況下提出的，具有不廣泛性。再者會(huì)受到一些環(huán)境、設(shè)備、人為干擾客觀條件的限制，也會(huì)使目標(biāo)追蹤的準(zhǔn)確性有所降低。因此想要完善不同情況的追蹤算法，還有更嚴(yán)峻的挑戰(zhàn)在等待解決。本文首先對(duì)現(xiàn)有計(jì)算復(fù)雜度的方法進(jìn)行了分析，找到了復(fù)雜度分析時(shí)所需要的工具方法和需進(jìn)行改良的地方，然后本文詳細(xì)分析了的根本原理和該算法在實(shí)際追蹤的過程中一些優(yōu)缺點(diǎn)，對(duì)MeanShift算法分析復(fù)雜度的局部，由于在對(duì)追蹤視頻時(shí)MeanShift算法目標(biāo)顏色特征比擬單一，所以本文采用了一種改良的MeanShift算法，為Camshift目標(biāo)追蹤算法。其次，概述了MeanShift算法在目標(biāo)遮擋時(shí)的追蹤能力，采用了改良的MeanShift算法，利用Camshift算法中的核心思想，這樣即使在遮擋時(shí)，算法仍能追蹤到目標(biāo)，以便于計(jì)算復(fù)雜度。與此同時(shí)，MeanShift算法可以縮小迭代的時(shí)間，提高追蹤效率。最后在分析兩種算法MeanShift算法和Camshift算法的時(shí)間復(fù)雜度時(shí)，采用時(shí)間函數(shù)作為度量標(biāo)準(zhǔn)，以追蹤同一視頻的不同消耗時(shí)間作為判斷依據(jù)，比擬兩種算法的復(fù)雜度。在分析過程中，先是對(duì)兩種算法的描述做了很足的工作，即算法的偽代碼描述和算法的流程圖，這是分析復(fù)雜度的必要工具，然后對(duì)兩種算法的幀率做了比擬，通過兩種算法的偽代碼描述得出了不同追蹤情況的復(fù)雜度，最后得出結(jié)論。本文采用MeanShift算法對(duì)目標(biāo)追蹤和計(jì)算時(shí)間復(fù)雜度分析時(shí)，無論是在追蹤效果方面，還是在時(shí)間復(fù)雜度的計(jì)算方面都存在很多的缺乏。關(guān)于研究的目標(biāo)追蹤領(lǐng)域，認(rèn)為有以下兩點(diǎn)：第一，本文在追蹤效果分析局部，采用MeanShift算法對(duì)目標(biāo)進(jìn)行追蹤時(shí)，由于選取的視頻有目標(biāo)遮擋，所以在追蹤過程中,遇到有遮擋的情況，就會(huì)出現(xiàn)追蹤目標(biāo)喪失并停留在遮擋物上的情況，追蹤效果不是很理想。第二，在采用MeanShift算法對(duì)時(shí)間復(fù)雜度進(jìn)行計(jì)算時(shí)，本文利用的是時(shí)間函數(shù)代價(jià)分析，在分析過程中，由于MeanShift算法原理比擬簡單，通過實(shí)驗(yàn)得出的實(shí)驗(yàn)結(jié)果時(shí)間較長。針對(duì)追蹤窗口的自適應(yīng)調(diào)整仍然沒有適宜的解決方案。如果能夠找到一種計(jì)算簡單，性能優(yōu)良的因素作為窗口伸縮系數(shù)的計(jì)算依據(jù)，那么會(huì)進(jìn)一步提高目標(biāo)追蹤的精度并擴(kuò)大它的應(yīng)用范圍。5.2展望從目前來看，運(yùn)動(dòng)目標(biāo)追蹤是一個(gè)還在處于上升階段的的研究課題，在圖像處理、模式識(shí)別、計(jì)算機(jī)視覺等領(lǐng)域的研究還有待提高。近年來，雖然對(duì)該領(lǐng)域付出了許多汗水，但隨著應(yīng)用的逐層深入，仍然面臨許多困難，這些困難包括：〔1〕算法的實(shí)時(shí)性追蹤算法能否得到實(shí)際應(yīng)用，很重要一個(gè)因素就是實(shí)時(shí)性，但目前多數(shù)的算法都是在一些假定條件下才能實(shí)現(xiàn)，因此下一步研究的主要方向就是滿足實(shí)際應(yīng)用的實(shí)時(shí)性這個(gè)條件。〔2〕目標(biāo)遮擋問題當(dāng)追蹤目標(biāo)發(fā)生遮擋時(shí)，追蹤對(duì)象會(huì)出現(xiàn)有一局部是看不見的，并且過程中可能發(fā)生形變、旋轉(zhuǎn)等各種不可預(yù)知的情況。如何構(gòu)架一個(gè)準(zhǔn)確的處理遮擋的模型也是今后研究的重要問題?！?〕多目標(biāo)的追蹤在多目標(biāo)追蹤中，不僅考慮與單目標(biāo)追蹤中相似的遮擋問題，還要考慮新目標(biāo)出現(xiàn)時(shí)的識(shí)別及舊目標(biāo)消失時(shí)的判定等問題。在眾多多目標(biāo)追蹤算法中，粒子濾波法是目前解決多目標(biāo)追蹤問題的主要方法，但隨著目標(biāo)數(shù)目的增多，需要為多個(gè)目標(biāo)建適宜的動(dòng)態(tài)模板，怎樣降低狀態(tài)空間的維數(shù)、設(shè)計(jì)高效的樣算法等問題還需要進(jìn)一步的研究。

參考文獻(xiàn)[1]SegenJ,PingaliS.Acamera-basedsystemfortrackingpeopleinreal-time[A].ProceedingsofICPR’96[C].NewYork,USA:[s.n.],1996.63-67.[2]姜明新.智能視頻監(jiān)控中的目標(biāo)追蹤技術(shù)研究[D].大連理工大學(xué)碩士學(xué)位論文,2021.[3]李培華.一種改良的MeanShift追蹤算法[J],自動(dòng)化學(xué)報(bào),2007,33(4):347-354.[4]BirchfieldS,SriramR.SpatiogramsVersushistogramsforregion-basedtracking[C]CVPR05,SanDiego,2005:pp.1158-1163.[5]毛勇,周曉波,夏錚.特征選擇算法研究綜述[J].模式識(shí)別與人工智能,2007,20(2):211-218.[6]ShiP.,etal.Amodel-basedintegratedapproachtotrackmyocardialdeformationusingdisplacementandvelocityconstraints[C].InProc.ofEuropeanConf.ComputerVision.Cambridge,MA,USA.1995:299-304.[7]彭寧高,楊杰.MeanShift追蹤算法中核函數(shù)窗寬的自動(dòng)選取[J].軟件學(xué)報(bào),2005,16(9):1542-1550.[8]DoucetA.,N.Gordon,V.Krishnamurthy.ParticlefilterforstateestimationofjumpMarkovlinearsystems[J].IEEETransactionSignalProcessing,2001.49(3):613-624.[9]田莘.基于MeanShift算法的目標(biāo)追蹤問題研究[D].西安電子科技大學(xué)碩士學(xué)位論文,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].哈爾濱工程大學(xué)碩士學(xué)位論文,2021.[13]王紅梅,胡明.算法設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社,2021.[14]呂國英,任瑞征,錢宇華.算法設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社,2006.[15]馮帆.復(fù)雜度可分級(jí)的目標(biāo)追蹤算法研究[D].華中科技大學(xué)碩士學(xué)位論文,2021.[16]殷超.常用算法時(shí)間復(fù)雜度的計(jì)算方法[J].科技信息,2021,26(1):118-184.[17]張宇山.進(jìn)化算法的收斂性與時(shí)間復(fù)雜度分析的假設(shè)干研究[D].華南理工大學(xué)碩士學(xué)位論文,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]袁國武,徐丹.一種結(jié)合了紋理和顏色的運(yùn)動(dòng)目標(biāo)追蹤算法[J].計(jì)算機(jī)應(yīng)用與軟件,2021,28(11):81-84.[21]安國成,張鳳軍等.多窗口目標(biāo)追蹤算法[J].計(jì)算機(jī)研究與開展,2021,48(11):2024-2029.[22]L.J.Reese.Intelligentpaint:Region-basedinteractiveimagesegmentation[D].Brighamyounguniversity,1999.[23]楊振興.基于DM642Camshift追蹤算法研究[D].南京理工大學(xué),2021.[24]馬麗,胡尼亞,李娜,王志軍,唐雄燕.電信產(chǎn)品發(fā)布方法與業(yè)務(wù)管理子系統(tǒng)[P].中國專利:CN102446308A,2021-05-09.[25]ShioA,SklanskyJ.Segementationofpeopleinmotion[A].IEEEWorkshoponVisualMotion[C].Princeton,NJ,USA:IEEEComputerSociety,1991.325-332.

致謝轉(zhuǎn)眼間，大學(xué)四年的學(xué)習(xí)生涯即將過去了，我有過壓力，也有過成就感，有過失落也有過欣慰。此時(shí)的心情可謂百感交集，在此我要向培養(yǎng)我的母校安徽建筑大學(xué)致以崇高的敬意，也要感謝我的輔導(dǎo)員黃紅娟，她對(duì)我四年的生活提供了積極的幫助!我要感謝我的導(dǎo)師王煥寶教授。王老師是一個(gè)知識(shí)淵博的學(xué)者，有著嚴(yán)謹(jǐn)?shù)膽B(tài)度、敏銳的洞察力、寬厚隨和的為人以及睿智儒雅的學(xué)者風(fēng)范，這些都給我留下了深刻的印象。他對(duì)我大學(xué)期間的學(xué)習(xí)給予了精心的指導(dǎo)，每次論文的批改都會(huì)進(jìn)行到深夜，試問有幾個(gè)導(dǎo)師可以做到這些，而且生活上對(duì)我無微不至地照顧。其次還要感謝那些提供文獻(xiàn)的作者，如殷超，田莘等。為本文的撰寫提供了極大的靈感和幫助。我還要感謝我的研究生師姐、師哥和我的各位同學(xué)給予我的幫助。在此我要特別感謝我的學(xué)姐孫晶晶。她對(duì)我的研究工作提出了建設(shè)性的意見和各方面的指導(dǎo)和幫助。無論在學(xué)習(xí)方面還是生活方面遇到困難時(shí)，他們總能及時(shí)給予幫助、支持與鼓勵(lì)。我感謝他們的陪伴!

附錄1源代碼〔MeanShift算法時(shí)間代價(jià)實(shí)驗(yàn)〕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算法時(shí)間代價(jià)實(shí)驗(yàn)〕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