【正文】 ng Mean Shift Proc Eighth Int39。 當(dāng)噪聲向量是屬于高斯分布，最好的方法是用卡爾曼濾波法 但是，從本論文的研究現(xiàn)狀的討論中，可以知道卡爾曼濾波是一種把大多數(shù)情況進(jìn)行理想化的粗糙辦法，實(shí)用性并不強(qiáng)。在第二章節(jié)中 ，本文詳細(xì)討論了 Meanshift 算法原理，深入解析了該算法的本質(zhì)和證明了它的基本特征，得出了 Meanshift 算法的迭代過程是個(gè)逐步遞增的迭代過程，并且只會(huì)收斂到函數(shù)極大值。通過大量的實(shí)例分析，我們得出：無論是 Camshift還是 Meanshift，在跟蹤的時(shí)候會(huì)由于目標(biāo)的亮度變暗而失真，其主要原因是因?yàn)閲?guó)際上現(xiàn)存的 RGB 到 HSV 轉(zhuǎn)換方法是在亮度或者飽和度很小的情況下，色相會(huì)產(chǎn)生很大的波動(dòng)并且不穩(wěn)定。 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 進(jìn)度安排 第 1 周 — 第 3 周 ：查閱相關(guān)文獻(xiàn)資料，明確研究?jī)?nèi)容，了解研究所需的相關(guān)背景知識(shí)，確定方案，完成開題報(bào)告； 第 4 周 — 第 6 周 ： 深入學(xué)習(xí) Meanshift 算法原理，以及該算法的性質(zhì)，復(fù)雜度等分析，并且了解該算法在跟蹤領(lǐng)域的應(yīng)用； 第 7 周 — 第 10 周 ： 了解 Meanshift 跟蹤算法的優(yōu)缺點(diǎn)，并且在保證優(yōu)點(diǎn)的情況下，修改其缺點(diǎn)，結(jié)合自己的創(chuàng)新研究更好的跟蹤算法，同時(shí)編程實(shí)踐； 第 11 周 — 第 14 周 ：完成并修改畢業(yè)設(shè)計(jì)論文； 第 15 周 ：準(zhǔn)備論文答辯 。 3．指導(dǎo)教師意見：學(xué)生的調(diào)研是否充分？基本內(nèi)容和技術(shù)方案是否已明確？是否已經(jīng)具備開始設(shè)計(jì)（論文）的條件？能否達(dá)到預(yù)期的目標(biāo)？是否同意進(jìn)入設(shè)計(jì)（論文）階段。在分析一些傳統(tǒng)的跟蹤算法優(yōu)缺點(diǎn)后，提出了局部的 CamShift 算法，后經(jīng)分析得知，該算法在保證了 MeanShift 的快速優(yōu)點(diǎn)的前提下，改進(jìn)了該算法的多種缺點(diǎn)，從而能夠在目標(biāo)距離發(fā)生變化，室內(nèi)環(huán)境光線昏暗，目標(biāo)物體遭到干擾的情況下依然能夠有效地追蹤物體。并用大量的實(shí)例演示其跟蹤效果。 object tracking。 Meanshift 算法 [1]是該派別的主力算法之一，該算法是一種在一組數(shù)據(jù)的密度分布中尋找局部極值的穩(wěn)定 [2]的方法。 另一種 濾波和數(shù)據(jù)關(guān)聯(lián)度 是一個(gè)處理目標(biāo)動(dòng)態(tài)變化，先驗(yàn)學(xué)習(xí)的由上至下的過程。 研究現(xiàn)狀 基于濾波和數(shù)據(jù)關(guān)聯(lián)度的跟蹤算法 研究現(xiàn)狀 基于濾波和數(shù)據(jù)關(guān)聯(lián)度的目標(biāo)跟蹤，可以歸納為對(duì)離散時(shí)間動(dòng)態(tài)系統(tǒng)的狀態(tài)空間建模方法。 當(dāng)噪聲向量是屬于高斯分布， kf ， kh 都是線型算子的時(shí)候，最好的方法是用卡爾曼濾波法 (Kalman Filter)[8, ]，當(dāng) kf ， kh 都是非線性算子的時(shí)候，進(jìn)行線型化就得到了擴(kuò)展的卡爾曼濾波法 (Extended Kalman Filter, EKF)[8]，兩種方法的后驗(yàn)概率分布都是高 斯型。 當(dāng)跟蹤于一個(gè)多目標(biāo)的混亂環(huán)境下，一些跟蹤方法的有效性和關(guān)聯(lián)性就產(chǎn)生了。連接數(shù)據(jù)關(guān)聯(lián)度濾波 (Joint Data Association Filter(JPDAF)[8, ], 于此同時(shí)，計(jì)算了方法和目標(biāo)的關(guān)聯(lián)度概率把所有目標(biāo)都聯(lián)系起來。在文獻(xiàn) [16]中，概率排除的多目標(biāo)算法被提出。目標(biāo)定位和配準(zhǔn)方法都是最大化似然函數(shù)。對(duì)模型的訓(xùn)練學(xué)習(xí)是建立在一些穩(wěn)定的圖像結(jié)構(gòu)，運(yùn)動(dòng)信息和一些異常過程 [24]的基礎(chǔ)之上的。與此同時(shí)人的直接跟蹤法 [28]時(shí)間復(fù)雜度高，而且經(jīng)常會(huì)用上一些其它的模型 [29][30]。最后，利用 Meanshift算法對(duì)其進(jìn)行跟蹤并且分析其算法復(fù)雜度和該算法的優(yōu)勢(shì)； 3) 在 Meanshift 的基礎(chǔ)之上，建立一個(gè)能夠自適應(yīng)目標(biāo)大小的 camshift 算法，同時(shí)將全局運(yùn)算改為對(duì)圖像的局部進(jìn)行運(yùn)算，從而可以大大節(jié)省運(yùn)算量。一本書 [32]討論了用 Meanshift 做密度檢測(cè)的優(yōu)點(diǎn)時(shí)，這個(gè)算法才被統(tǒng)計(jì)領(lǐng)域所發(fā)現(xiàn)并廣泛使用。由于建立的相關(guān)度摸型是個(gè)連續(xù)函數(shù)，因此，基于梯度的方法便可以使用，使得該優(yōu)化方法會(huì)比優(yōu)化的搜索方法要快速許多。 本論文成功的進(jìn)行了很多跟蹤方法，處理了許多復(fù)雜的跟蹤問題。 Meanshift 算法定義以及效率分析 Meanshift 算法核函數(shù)概述 [1] 核函數(shù)密度估計(jì)是最常見的密度估計(jì)函數(shù)之一。以上討論的兩種函數(shù)都可以滿足公式 (3)的條件，但根據(jù)我們的目的，一般選擇關(guān)于半徑對(duì)稱的方程作為核函數(shù)更加合適。后者明顯好處是讓參數(shù)變成了一個(gè)值 0h? ，又一次降低了問題的復(fù)雜程度。在兩種由一元變量的方程來產(chǎn)生多元核函數(shù)方程的公式中，人們測(cè)出武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 8 （同時(shí)也證明了）最好的估計(jì)質(zhì)量的核函數(shù) 方程為 [33,] 1()0Exkx ??? ?? 011xx??? (7) 同時(shí)，它在 d 維空間中，按照半徑對(duì)稱的形式進(jìn)行擴(kuò)展可以得到 211 ( 2) (1 )() 20dEc d XKX ?? ???? ??? 1Xotherwise? (8) 需要注意的是， 該形式的核函數(shù)在邊界出不存在導(dǎo)數(shù)。很容易想到，密度最密集的部分，其梯度 ( ) 0fx??， Meanshift 方法就是找到該點(diǎn)位置的一個(gè)快捷算法。這個(gè)條件在實(shí)際應(yīng)用中不難做到。在Fukunaga 和 Hostetler[1]中，證明了該算法一個(gè)特性： Meanshift 向量會(huì)一直指向密度增長(zhǎng)最快的方向。低密度區(qū)域是不感興趣的區(qū)域，在這片區(qū)域內(nèi)，由于算法的性質(zhì) [2]， Meanshift 步長(zhǎng)會(huì)比較大和快速，相應(yīng)的，在最大值附近，收斂步長(zhǎng)會(huì)變慢，分析地就越仔細(xì)，因此該梯度是一個(gè)自適應(yīng)的梯度。 證明： 由于 n 是有限的，序列 ,{ ( )}hKfj? 是有界的，根據(jù)序列 ,{ ( )}hKfj? 的定義，221, 1( 1 ) ( ) ( ) ( )n j i j ikdh K h K d iy x y xcf j f j k kn h h h?? ??????? ? ? ?????? (A .1) 根據(jù)凹函數(shù)的定義，對(duì)于所有的 1 2 1 2, [0 , ),x x x x? ? ?就有 2 1 1 2 1( ) ( ) ( ) ( )k x k x k x x x?? ? ? (A .2) 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 11 由于 ( ) ( )g x k x??? ， ()式可以化為 2 1 1 1 2( ) ( ) ( ) ( )k x k x g x x x? ? ? (A .3) 代入上式到 ()，得 ,222,121222,1121( 1 ) ( )()( ) 2( )h K h Knjikdj i j idinjikd TTj j j i jdif j f jyxcg y x y xnh hyxcg y y y x ynh h???????????? ??? ? ? ?????? ??? ? ? ??????? (A .4) 根據(jù) (20)式，得到 22, 1, 2 1( 1 ) ( ) ( )n jikdjjh K h K d iyxcf j f j y y gn h h???? ??? ? ? ? ? (A .5) 由于 ()kx 在 0x? 上單調(diào)遞減，因此 21()n jiiyxg h??? 就是一個(gè)正實(shí)數(shù)。 然后，將 ()的連續(xù) m 項(xiàng)累加，便得到 221,12122,12122,1122,2( ) ( ) ( ) ... ... ...().....nj m ikdj m j mh K h K dinjikdjjdikdj m j m j jdkdj m jdyxcf j m f j y y gnh hyxcy y gnh hcy y y y Mnhcy y Mnh??? ? ??????? ? ? ?????? ? ? ? ? ?????? ? ? ? ????????? (A .6) M 表示上式的 m 個(gè) 21()n jiiyxg h??? 的最小值。算法結(jié)束。 PN 表示屬于該圓的樣本點(diǎn)數(shù)目。 從數(shù)學(xué)上看， Meanshift 方法與牛頓爬山法類似，是一種基于梯度來求得函數(shù)最大值的方法。該方法是合理的，因?yàn)樘嗟慕y(tǒng)計(jì)數(shù)據(jù)會(huì)大大增加算法的復(fù)雜度從而使計(jì)算變慢從而失去了跟蹤的實(shí)時(shí)性。該模型的優(yōu)點(diǎn)就是運(yùn)算快，效率好，計(jì)算機(jī)只用統(tǒng)計(jì)其直方圖便能得到圖像的特征。也可以將飽和度(Saturation)和色相一并用作目標(biāo)物體的模型，從而由一位模型變?yōu)槎S模型，進(jìn)而可以改進(jìn)跟蹤的精度。 反向投影也是直方圖里的一個(gè)基本工具之一。比如對(duì)一個(gè)人臉直方圖進(jìn)行反向投影，可以得到的投影圖如下（如圖 4）： 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 16 圖 4 反向投影成像（右）和原圖（左） 由上節(jié)的 meanshift 算法，我們可以知道可以加權(quán)改進(jìn)該算法。 由此 可知，根據(jù) Meanshift 加權(quán)的算法步驟如下： 輸入一個(gè)圖像和給定的直方圖 以及初始的搜索 點(diǎn) 00( , )xy 和窗口半徑 h ，以及精度 ? ： (1) 計(jì)算該圖像相對(duì)與模型直方圖的反向投影，生成概率圖像 ( , )I xy 。（如圖 7） 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 18 圖 7 反向投影跟蹤效果。但窗口不變，這意味著大小不變的窗口會(huì)包括人臉，但也會(huì)包括和人臉無關(guān)的區(qū)域，這會(huì)嚴(yán)重影響跟蹤效果 (如圖 8) 圖 8 人的距離變化導(dǎo)致跟蹤失效 因此，在跟蹤物體與攝像機(jī)位置發(fā)生變化時(shí)， Meanshift 算法跟蹤器會(huì)失效， 失效的原因在于窗口大小沒有隨著人臉大小而進(jìn)行相應(yīng)調(diào)整，從而導(dǎo)致窗口內(nèi)的密度分布變稀疏， Meanshift 算法失去了實(shí)用性。該算法可以實(shí)現(xiàn)針對(duì)物體在視頻中的大小進(jìn)行自適應(yīng)調(diào)整，從而大大改善跟蹤效果。因此，可以定義一個(gè)圖像的灰度體積為： ( , )V I x y d x d y??? (25) 利用灰度體積除以圖像的平均灰度值，就可以得到圖像的面積 S ： VS I? (26) 其中 I 為圖像區(qū)域的平均灰度值 。因此，我們將窗口寬度設(shè)置為： 002 256Ms ? (28) 之所以開根號(hào)是為了長(zhǎng)度量綱保持一致。 該算法的步驟如下： 給定圖像和目標(biāo)直方圖，窗口大小 h ， 已知 精度 ? (1) 將搜索初始點(diǎn)設(shè)置為目標(biāo)初始位置，對(duì)給定的圖像和目標(biāo)直方圖，進(jìn)行全局的反向投影； (2) 由上面的 Meanshift 算法進(jìn)行迭代運(yùn)算，收斂后，返回跟蹤目標(biāo)的零階矩00M ； (3) 由 (28)式進(jìn)行窗口的尺寸計(jì)算，并且按照該公式跟新窗口大小。 讓反向投影的全局計(jì)算修改為局部計(jì)算。 利用該算法做跟蹤，效果如下： 圖 13 改進(jìn)后的跟蹤效果圖 由圖 (12)系列可以看出，在改進(jìn)之后，周圍背景與人臉無關(guān)的區(qū)域的噪點(diǎn)有效減少，從而也在降低計(jì)算量的同時(shí)，改善了跟蹤效果。但該方法也有缺點(diǎn)，就是當(dāng)視頻中目標(biāo)移動(dòng)較快的時(shí)候，有時(shí)候會(huì)出現(xiàn)跟蹤失敗的情況。因此，提高模型對(duì)物體的描述才是關(guān)鍵。其原因，就是因?yàn)樵谄浞较蛲队皥D上，與目標(biāo)無關(guān)的噪點(diǎn)大大減少，從而保證了跟蹤質(zhì)量。 但是，當(dāng)室內(nèi)環(huán)境光線充足的時(shí)候，該算法的迭代速度并沒有明顯的改進(jìn) ，只是略微減少 。我們測(cè)試對(duì)同一個(gè)視頻進(jìn) 行跟蹤，發(fā)現(xiàn)迭代次數(shù)在室內(nèi)昏暗的時(shí)候有所降低，原因是因?yàn)楫?dāng)室內(nèi)光線昏暗的時(shí)候，反向投影的效果比較多，嚴(yán)重影響了算法收斂方向和速度（如圖 17）。 局部 Camshift算法的跟蹤效果比較 由于 CamShift 算法是基于圖像的全局信息基礎(chǔ)之上，當(dāng)室內(nèi)亮度不夠，光線不足的時(shí)候，容易造成色相提取的誤差，并且色相運(yùn)算并不穩(wěn)定，導(dǎo)致反向投影圖有許多和目標(biāo)無關(guān)的噪點(diǎn)，嚴(yán)重干擾了跟蹤算法，以及跟蹤的穩(wěn)定性（如圖15）。導(dǎo)致跟蹤失效。效果如圖： 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 24 圖 14 目標(biāo)物體距離改變的跟蹤效果。該算法如下： 對(duì)給定的圖像和目標(biāo)直方圖，初始窗口和精度 ? (1) 首先，設(shè)定初試窗口的位置，準(zhǔn)備跟蹤； (2) 計(jì)算一個(gè)比當(dāng)前窗口稍微更大一些的范圍內(nèi)的反向投影值； 武漢理工大學(xué)畢業(yè)設(shè)計(jì)