【正文】 x y?????? (24) ( , )1( , )( , )( , )m n jm n jm n nx y Pjmnx y Pp x y yy p x y?????? 其中 ( , )mnp x y 就是像素點(diǎn) ( , )mnxy 經(jīng)過反向投影后的概率值。該式即是 (23)式中，將該點(diǎn)的概率值 ( , )mnp x y 作為權(quán)值 iw 代入方程 (23)中，從而得到該公式 。 由此可知，根 據(jù) Meanshift 加權(quán)的算法步驟如下： 輸入一個圖像和給定的直方圖 以及初始的搜索 點(diǎn) 00( , )xy 和窗口半徑 h ，以及精度 ? ： (1) 計(jì)算該圖像相對與模型直方圖的反向投影，生成概率圖像 ( , )I xy 。 (2) 對每個以搜索點(diǎn)為中心的窗口， 計(jì)算 該窗口內(nèi)的 概率圖像的一階矩和零階矩，公式如下： 00 ( , )xyM I x y? ?? 10 ( , )xyM x I x y? ?? 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 17 01 ( , )xyM y I x y? ?? (3) 計(jì)算新的搜索中心 1000cMx M? ， 0100cMyM? (4) 比較新舊搜索點(diǎn)，如果距離大于等于 ? ，則重復(fù)步驟 (2)和 (3)，否則，返回，算法結(jié)束。 Meanshift 視頻跟蹤應(yīng)用以及優(yōu)缺點(diǎn)分析 運(yùn)用該算法跟蹤，得到的效果如下（ 如圖 5， 6） ： 圖 5 Meanshift 算法跟蹤杯子的效果 圖 6 Meanshift 算法跟蹤人臉的效果 該算法的優(yōu)點(diǎn)是，對每一幀視頻迭代快速，只需要求均值操作便可以有很好的跟蹤效果。其跟蹤原理也很容易理解，即反向投影以后，利用 Meanshift 算法找到白點(diǎn)密度分布最密集的位置。（如圖 7） 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 18 圖 7 反向投影跟蹤效果。 但該算法也有一些缺點(diǎn)。比如計(jì)算反向投影的時候要掃描整個圖像，這樣的計(jì)算也是十分耗時的，在一些配置低端的計(jì)算機(jī)上，該算法實(shí)時性并不理想，但對目前的主流計(jì)算機(jī)來說，對一般清晰度的視頻，該計(jì)算量 并不成問題，但視頻如果分辨率高，則會造成很明顯的延遲。 其次，該算法的窗口大小有待改進(jìn)，原因是由于視頻當(dāng)中，如果人物由進(jìn)到遠(yuǎn)的行動，人物在視頻中會變小。但窗口不變，這意味著大小不變的窗口會包括人臉，但也會包括和人臉無關(guān)的區(qū)域，這會嚴(yán)重影響跟蹤效果 (如圖 8) 圖 8 人的距離變化導(dǎo)致跟蹤失效 因此，在跟蹤物體與攝像機(jī)位置發(fā)生變化時， Meanshift 算法跟蹤器會失效， 失效的原因在于窗口大小沒有隨著人臉大小而進(jìn)行相應(yīng)調(diào)整，從而導(dǎo)致窗口內(nèi)的密度分布變稀疏， Meanshift 算法失去了實(shí)用性。根據(jù)該缺陷， 人們提出了許多改進(jìn)方法，其中非常有效的一種是 Camshift[5] 跟蹤算法。 此外，本文也提出了一種局部運(yùn)算的 Camshift 算法，大大改善了跟蹤效果。 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 19 3 局部 Camshift 算法 原理以及實(shí)踐 Camshift跟蹤器 Camshift 算法原理 Camshift 算法全稱是 Continuously Adaptive Mean Shift Algorithm，是由Meanshift 的改進(jìn)算法。該算法可以實(shí)現(xiàn)針對物體在視頻中的大小進(jìn)行自適應(yīng)調(diào)整，從而大大改善跟蹤效果。 Camshift[5] 充分利用了 Meanshift 算法的計(jì)算簡單快捷的優(yōu)點(diǎn)， 并且在不增加計(jì)算復(fù)雜度的同時，實(shí)現(xiàn)了自適應(yīng)的窗口大小控制。在 Meanshift 迭代完成之后，改進(jìn)的算法都會對窗口大小進(jìn)行調(diào)整。 窗口調(diào)整的原理如下： 對一副灰度連續(xù)圖像，如果將該圖像投影至 3 維平面內(nèi)，橫縱坐標(biāo)分別為對應(yīng)的圖像維度， z 軸范圍為 [0,255]，其數(shù)值為在該點(diǎn)對應(yīng)圖像中的像素的灰度值。因此，可以定義一個圖像的灰度體積為： ( , )V I x y d x d y??? (25) 利用灰度體積除以圖像的平均灰度值，就可以得到圖像的面積 S ： VS I? (26) 其中 I 為圖像區(qū)域的平均灰度值 。由于計(jì)算機(jī)圖像為離散圖像，故有 ( , )V I x y??? (27) 而為了保守圖像的大小，我們采用像素最大值（即 255）來代替平均灰度值。這么做的原因，是一方面，我們希望跟蹤窗口盡 可能的小，以便我們在跟蹤的時候讓窗口盡可能地不讓無關(guān)物體進(jìn)入，于是我們采取使用灰度最大值來代替灰度平均值。當(dāng)然也不能太過于小，這樣容易造成跟蹤窗口的尺寸太小而導(dǎo)致算法容易收斂到局部最大值。因此，我們將窗口寬度設(shè)置為： 002 256Ms ? (28) 之所以開根號是為了長度量綱保持一致。由于人臉的形狀是橢圓型，長度可以設(shè)武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 20 置為寬度的 倍，即 ? 。 我們也可以根據(jù)需要，輸出人臉的偏移角度。 根據(jù) [5]， 可以得出，橢圓的旋轉(zhuǎn)角度為： 11002220 0200 002( )a r c t a n( ) ( )2ccccM xyMMMxyMM??????? ? ?????? (29) 其中，220 ( , )xyM x I x y? ??，202 ( , )xyM y I x y? ??， ( , )ccxy 是窗口的中心點(diǎn) 。 該算法的步驟如下： 給定圖像和目標(biāo)直方圖，窗口大小 h ， 已知 精度 ? (1) 將搜索初始點(diǎn)設(shè)置為目標(biāo)初始位置，對給定的圖像和目標(biāo)直方圖，進(jìn)行全局的反向投影； (2) 由上面的 Meanshift 算法進(jìn)行迭代運(yùn)算，收斂后，返回跟蹤目標(biāo)的零階矩00M ； (3) 由 (28)式 進(jìn)行窗口的尺寸計(jì)算，并且按照該公式跟新窗口大小。 (4) 根據(jù)更新大小的窗口作為下一幀視頻的初試窗口，并且將 Meanshift 所得到的迭代窗口中心重新作為目標(biāo)初始位置，進(jìn)行 (2)，若是視頻結(jié)束，則返回。 跟蹤效果如下： 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 21 圖 9 Camshift 算法跟蹤效果 (原圖與對應(yīng)的反向投影圖 ) 同時，該方法也有效地解決了物體里視頻位置改變而產(chǎn)生的跟蹤問題，效果如下： 圖 10 Camshift 算法跟蹤距離改變的目標(biāo) CamShift 算法優(yōu)缺點(diǎn)分析 由于該算法屬于一種自適應(yīng)算法，根據(jù)跟蹤的目標(biāo)估 算出其面積，并且使得窗口做自適應(yīng)調(diào)整，故 該算法的使用，使得跟蹤的穩(wěn)定性 顯著 提高，視頻過程中如果有其它物體干擾，對結(jié)果的影響并不大： 圖 11 手的干擾對跟蹤的影響 不大 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 22 但 Camshift 算法也有缺陷，不光是在反向投影過程中，全局運(yùn)算增加了不必要的運(yùn)算負(fù)擔(dān)，同時全局運(yùn)算也會大大降低跟蹤質(zhì)量，原因主要是因?yàn)樵诹炼炔粡?qiáng)的背景區(qū)域，反向投影會產(chǎn)生噪點(diǎn)，其原因是因?yàn)樵?RGB 轉(zhuǎn)換到 HSV 空間的時候，亮度或飽和度不大的映射穩(wěn)定性不高，導(dǎo)致一些無關(guān)點(diǎn)也被當(dāng)成目標(biāo)區(qū)域，原因如下圖： 圖 12 跟蹤效果不理想的 原因是白點(diǎn)的錯誤分布 局部 Camshift 算法 局部 Camshift 算法原理 根據(jù)上述對 Camshift 算法的跟蹤缺點(diǎn)分析，白點(diǎn)的錯誤分布是因?yàn)檫M(jìn)行了全局運(yùn)算而導(dǎo)致，全局運(yùn)算不僅僅增大了運(yùn)算量，并且無關(guān)的計(jì)算容易讓更多無關(guān)的物體干擾跟蹤算法，將算法由全局改成局部，有效的改善了跟蹤效果。 我們可以初步分析，無論是 Camshift 算法，還是 Meanshift 算法，如果經(jīng)過反向投影的圖像，只有目標(biāo)區(qū)域有離散的白點(diǎn)，其余區(qū)域沒有，那么，這種投影的跟蹤肯定是成功的，因?yàn)閳D像的數(shù)據(jù)分布密集點(diǎn)只有一 處（即目標(biāo)位置），而Camshift 算法或者 Meanshift 算法，其作用都是找到數(shù)據(jù)密集處。 讓反向投影的全局計(jì)算修改為局部計(jì)算。即讓反向投影的范圍限制在搜索窗口的內(nèi)部進(jìn)行，這樣不僅僅可以大大減少計(jì)算量，也可以保證跟蹤質(zhì)量，從而更有效地進(jìn)行跟蹤。該算法如下： 對給定的圖像和目標(biāo)直方圖，初始窗口和精度 ? (1) 首先，設(shè)定初試窗口的位置，準(zhǔn)備跟蹤； (2) 計(jì)算一個比當(dāng)前窗口稍微更大一些的范圍內(nèi)的反向投影值； 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 23 (3) 使用 Meanshift 算法迭代，收斂后，返回跟蹤目標(biāo)的零階矩 00M 和收斂位置 ； (4) 以收斂位置為中心建立窗口，由 (28)式進(jìn)行窗口的尺寸計(jì)算，并且按照該公式更新窗口大小。 (5) 根據(jù)更新的窗口作為下一幀視頻的初試窗口，并且將 Meanshift 所得到的迭代窗口中心重新作為目標(biāo)初始位置，進(jìn)行 (2)，若是視頻結(jié)束，則返回。 利用該算法做跟蹤，效果如下： 圖 13 改進(jìn)后的跟蹤效果圖 由圖 (12)系列可以看出，在改進(jìn)之后，周圍背景與人臉無關(guān)的區(qū)域的噪點(diǎn)有效減少，從而也在降低計(jì)算量的同時，改善了跟蹤效果。同時在距離改變的跟 蹤上，問題也得到了明顯改善，搜索窗口幾乎很少出錯，其原因正是因?yàn)橄拗屏朔聪蛲队暗膮^(qū)域，使得白色點(diǎn)盡可能分布在搜索區(qū)域附近。效果如圖： 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 24 圖 14 目標(biāo)物體距離改變的跟蹤效果。 局部 Camshift 算法的優(yōu)缺點(diǎn)分析 該方法的優(yōu)點(diǎn)，就是計(jì)算量非常小，跟蹤的實(shí)時性好，這是由于我們將全局的運(yùn)算改為局部的運(yùn)算而導(dǎo)致的。但該方法也有缺點(diǎn)，就是當(dāng)視頻中目標(biāo)移動較快的時候，有時候會出現(xiàn)跟蹤失敗的情況。原因是因?yàn)橛捎谌诌\(yùn)算改為局部運(yùn)算，這樣就會出現(xiàn)在連續(xù)兩幀內(nèi)，由于目標(biāo)移動太快速而導(dǎo)致突然從窗口中消失， 窗口中沒有目標(biāo)的數(shù)據(jù)從而停止了移動。導(dǎo)致跟蹤失效。 同時，由于跟蹤的模型是建立在顏色模型的基礎(chǔ)之上，無論是局部Camshift 還是全局 Camshift，都有可能讓跟蹤窗口包括與目標(biāo)無關(guān)的物體里面，因此，跟蹤最大的改進(jìn)位置就是對目標(biāo)的模型描述，如果能在跟蹤的過程中，能夠?qū)ξ矬w的形狀進(jìn)行描述，則該物體可以進(jìn)行準(zhǔn)確跟蹤。因此，提高模型對物體的描述才是關(guān)鍵。 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 25 4 局部 Camshift 算法與 Camshift 算法對比 為了進(jìn)一步說明局部 CamShift 算法的優(yōu)點(diǎn)， 我們將傳統(tǒng)的 CamShift 和局 部的 CamShift 算法進(jìn)行比較，從效率以及迭代次數(shù)出發(fā)進(jìn)行對比，分析局部CamShift 算法的優(yōu)缺點(diǎn)。 局部 Camshift算法的跟蹤效果比較 由于 CamShift 算法是基于圖像的全局信息基礎(chǔ)之上，當(dāng)室內(nèi)亮度不夠，光線不足的時候，容易造成色相提取的誤差，并且色相運(yùn)算并不穩(wěn)定，導(dǎo)致反向投影圖有許多和目標(biāo)無關(guān)的噪點(diǎn)，嚴(yán)重干擾了跟蹤算法，以及跟蹤的穩(wěn)定性（如圖15）。 圖 15 跟蹤效果對比（左圖為 Camshift,右圖為局部 Camshift） 由此可見，當(dāng)室內(nèi)光線十分昏暗的時候，局部 Camshift 算法可以有效地改進(jìn)跟蹤效果，對目標(biāo)無關(guān)的噪點(diǎn)進(jìn)行排除，以達(dá)到跟蹤效果。其原因，就是因?yàn)樵谄浞较蛲队皥D上，與目標(biāo)無關(guān)的噪點(diǎn)大大減少，從而保證了跟蹤質(zhì)量。 圖 16 說明了反向投影的效果 圖 16 反向投影效果對比（左圖為 Camshift，右圖為局部 Camshift） 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 26 局部 Camshift算法的迭代次數(shù)比較 由于局部 Camshift 算法把與目標(biāo)相關(guān)的離散數(shù)據(jù)點(diǎn)位于一定范圍內(nèi)部，所以，與目標(biāo)無關(guān)的數(shù)據(jù)點(diǎn)會大大減少，無關(guān)數(shù)據(jù)的干擾作用也會大大減低，因此迭代更快。我們測試對同一個視頻進(jìn)行跟蹤， 發(fā)現(xiàn)迭代次數(shù)在室內(nèi)昏暗的時候有所降低，原因是因?yàn)楫?dāng)室內(nèi)光線昏暗的時候，反向投影的效果比較多，嚴(yán)重影響了算法收斂方向和速度（如圖 17）。 圖 17 兩種算法的迭代次數(shù)對比（昏暗環(huán)境下） 跟蹤效果如圖 15。 但是，當(dāng)室內(nèi)環(huán)境光線充足的時候，該算法的迭代速度并沒有明顯的改進(jìn) ，只是略微減少 。 效果如下圖： 圖 18 室內(nèi)光線充足的情況下跟蹤對比 (左圖為 Camshift，右圖為局部 Camshift) 其原因，是因?yàn)榉聪蛲队岸际且粯?，因?yàn)槭覂?nèi)光線充足 ，色相轉(zhuǎn)換失真比較少，所以跟蹤效果都很好，反向投影效果如下圖： 武漢理工大學(xué)畢業(yè)設(shè)計(jì) (論文 ) 27 圖