基于顏色匹配的密集多目標(biāo)快速跟蹤算法

1、基于顏色匹配的密集多目標(biāo)快速跟蹤算法摘 要：基于公共場所的監(jiān)控場景，提出了一種適用于目標(biāo)密集環(huán)境的多運動目標(biāo)快速跟蹤算法。該方法運用形態(tài)學(xué)方法準(zhǔn)確提取目標(biāo)后，根據(jù)卡爾曼原理得到目標(biāo)在下一幀的預(yù)測位置，并以此確定搜索框的位置，提高匹配速率；然后在搜索框內(nèi)運用基于簡化的顏色匹配跟蹤方案,用于實現(xiàn)密集運動目標(biāo)的快速跟蹤；且通過設(shè)定穩(wěn)定度數(shù)組，來迅速排除碰撞、遮擋情況形成的干擾。仿真表明，該方法能在多目標(biāo)跟蹤過程中正確處理目標(biāo)的碰撞、遮擋等問題，可實現(xiàn)公共場所的實時監(jiān)控。關(guān)鍵詞：多密集目標(biāo)跟蹤,顏色匹配,穩(wěn)定度,卡爾曼預(yù)測a fast tracking algorithm of multiple an

2、d dense targets based on color matchingchen yu-ting1 cao yan2 zeng xiao-shan3(school of electronic and information engineering, south china university of technology, guangzhou 510640)abstract based on the video detection scene in the public, a fast tracking algorithm of multiple and dense targets is

3、 proposed. the targets are obtained accurately through morphology methods, then the position of the searching box in the next frame is predicted by kalman filer. in the searching box, the tracking algorithm based on simplified color matching is applied to track multiple and dense targets. moreover,

4、by setting a stability array, occlusion and collision can be solved fast. simulation results show that this method can deal with the occlusion and the collusion accurately during tracking multiple and dense targets, and achieve the video detection scene in the public.keywords tracking of multiple an

5、d dense targets, color matching, stability, kalman prediction1 引言視頻監(jiān)控系統(tǒng)在公共休閑娛樂場所具有越來越廣泛的應(yīng)用前景。以泳池監(jiān)控為例，游泳池內(nèi)泳者密集，泳技參差不齊，存在安全隱患，同時泳池的安保人員發(fā)現(xiàn)險情及實施救援也有一定的難度，有必要對泳者進行監(jiān)控。公共場所視頻監(jiān)控便是多目標(biāo)的匹配與跟蹤技術(shù)的應(yīng)用之一，其設(shè)計難點是目標(biāo)密集情況和發(fā)生碰撞遮擋情況的目標(biāo)匹配與跟蹤。多運動目標(biāo)匹配的常用方法有基于距離的匹配1，基于目標(biāo)位置、形狀或速度等目標(biāo)特征的匹配2，上下幀目標(biāo)重疊像素數(shù)的匹配3，區(qū)域生長4，基于顏色的匹配5-6等。其中，基于

6、顏色的匹配方案比較適合目標(biāo)密集情況下對外觀相似的目標(biāo)進行跟蹤。常規(guī)的顏色模型，從采樣點的角度分為手工采樣和自動采樣；從算法角度，顏色模型的建立方法主要有均值方差法、顏色直方圖統(tǒng)計法及其改進等。均值方差法需要對目標(biāo)的所有點都要參與運算，計算量較大；顏色直方圖統(tǒng)計法由于在rgb 顏色模型中，一共有2563種顏色，如果再考慮在此基礎(chǔ)上進行直方圖計算，計算量非常大，嚴(yán)重降低處理速度。基于此，本文考慮采用基于顏色的匹配方案。在采樣點的選取上采用自動采樣，即系統(tǒng)按照目標(biāo)的結(jié)構(gòu)比例自動完成采樣過程；從算法角度，本文則選取目標(biāo)少量的特殊顏色點，將特殊點的各維度顏色直接與顏色模型進行比較，簡化匹配過程。在對碰撞

7、和遮擋問題的處理上，已提出的方法如動態(tài)貝葉斯網(wǎng)絡(luò)模型7、顏色直方圖的粒子濾波8、網(wǎng)格模型9等，它們有較高的精確度，但較復(fù)雜。本文擬僅通過穩(wěn)定度，對目標(biāo)存在的可能性進行判斷。這樣設(shè)計的優(yōu)勢是：（1）不需設(shè)計專門的模塊識別或應(yīng)對碰撞和遮擋的情況；（2）目標(biāo)遮擋和碰撞均被視為目標(biāo)粘連的情況，不需分開討論。該方法雖然在目標(biāo)粘連時無法實現(xiàn)匹配，但卻不會導(dǎo)致目標(biāo)丟失，同時省去了目標(biāo)鏈、指針等許多參數(shù)的設(shè)置，在碰撞遮擋發(fā)生頻繁的跟蹤環(huán)境，可極大地提高算法的效率。由此，本文提出了一種適用于目標(biāo)密集環(huán)境的跟蹤方案。該方案將簡化的顏色匹配與卡爾曼預(yù)測相結(jié)合，實現(xiàn)密集多目標(biāo)的快速準(zhǔn)確跟蹤；同時設(shè)置穩(wěn)定度數(shù)組，在碰撞

8、、遮擋現(xiàn)象結(jié)束后幾幀內(nèi)，即可快速去除虛假目標(biāo)，且保證原目標(biāo)的正確跟蹤。2 核心思想2.1 簡化的顏色匹配模型顏色匹配比較適合外觀相似的目標(biāo)。本文提出的簡化顏色匹配方案，首先是在第一幀中，按照目標(biāo)的結(jié)構(gòu)比例，選取能代表目標(biāo)顏色特征的區(qū)域作為顏色的采樣區(qū)域。再將各目標(biāo)的采樣區(qū)域的若干點記作采樣點，同時記錄這些點相對于目標(biāo)質(zhì)心的位置。取各目標(biāo)的采樣點對應(yīng)的rgb三個維度的顏色值，依次存入顏色模型矩陣,記為colormode(k,j,v)，k、j、v分別表示采樣點總數(shù)、目標(biāo)總數(shù)及維度。元素colormode(k,j,v)表示第j個目標(biāo)的第k 個采樣點對應(yīng)的原rgb圖像中的第v維的顏色值。其中，k(1,

9、k), j(1,j), v(1,v)。然后在此后的各幀中，如第i(i>1)幀，按同樣的選取采樣點的規(guī)則對目標(biāo)進行顏色采樣，再與已有的colormode對比。|f(k,j,1)-colormode(k,j,1)|<a （1）|f(k,j,2)-colormode(k,j,2)|<a （2）|f(k,j,3)-colormode(k,j,3)|<a （3）其中，f(k,j,1)、f(k,j,2)、f(k,j,3)分別表示目標(biāo)j的第k個采樣點在r、g、b維度的顏色值，a為各維度匹配時允許的色差閾值。若同時滿足式（1）-（3），則認為該采樣點與顏色模型匹配，即實現(xiàn)了簡化的顏色匹

10、配。若目標(biāo)j 實現(xiàn)了匹配，則將第i 幀中目標(biāo)j的各采樣點的顏色值f(k,j,v)替換colormode中相應(yīng)位置的原值，實現(xiàn)顏色模型的更新。對檢測確認的新生目標(biāo)，按照同樣方法建立顏色模型，并采用簡化的顏色匹配方法實現(xiàn)目標(biāo)匹配。各幀中每個目標(biāo)都在相同的特殊點處采樣，并將前后幀相同采樣處的顏色值進行比對，這樣可避免目標(biāo)不同的位置客觀存在的顏色誤差，但該方法仍可能會因為光線、浪花等產(chǎn)生的白點影響到某個采樣點的顏色值而失配，解決方法是選取k>>1個采樣點，根據(jù)具體跟蹤情況設(shè)定一個匹配數(shù)的閾值，若實現(xiàn)匹配的采樣點數(shù)超過該閾值，則認定該目標(biāo)實現(xiàn)了匹配。2.2 碰撞遮擋問題的處理碰撞和遮擋的情況

11、在目標(biāo)密集環(huán)境下會時常發(fā)生，因此系統(tǒng)應(yīng)能保證這些特殊情況下的正確跟蹤。當(dāng)碰撞和遮擋發(fā)生時，兩目標(biāo)發(fā)生了粘連，系統(tǒng)會誤認為出現(xiàn)了一個新生目標(biāo)，兩目標(biāo)跟蹤失敗。為了避免這種情況，本文在跟蹤過程中建立一個穩(wěn)定度數(shù)組stablej,j表示目標(biāo)總數(shù)。stablej的值即為第j個目標(biāo)的穩(wěn)定度，初始化為1，最大值為smax（經(jīng)驗值）。其意義為：每個目標(biāo)在剛出現(xiàn)時，都被視為不穩(wěn)定的，初始化為1，隨著跟蹤成功次數(shù)的增加，其穩(wěn)定度也增加；若匹配不成功，其穩(wěn)定度減小，當(dāng)穩(wěn)定度減小到stablej=0時，即可認為目標(biāo)j已消失，不再對該目標(biāo)進行跟蹤。目標(biāo)粘連的情況（遮擋或碰撞）及跟蹤結(jié)果如圖1所示，在進行目標(biāo)1的跟蹤時

12、，系統(tǒng)會將位于目標(biāo)1的搜索框內(nèi)的粘 連目標(biāo)誤認為一個目標(biāo)與目標(biāo)1進行匹配，得到失配的結(jié)果。但由于建立了穩(wěn)定度數(shù)組，目標(biāo)1不會立即被認為消亡，在下一幀仍然對其進行檢測與匹配；而且由卡爾曼預(yù)測（詳見目標(biāo)預(yù)測部分），仍能估計出目標(biāo)在本幀的位置并顯示。目標(biāo)2的跟蹤過程同上。而發(fā)生粘連的兩目標(biāo)會被系統(tǒng)當(dāng)做一個新生目標(biāo)（記為目標(biāo)3）進行記錄，穩(wěn)定度置為1。在目標(biāo)分離后，目標(biāo)3因不會被檢測到，致使穩(wěn)定度逐次減1，直至為0，目標(biāo)3被系統(tǒng)認為已消亡，不再參與任何計算和顯示。目標(biāo)1目標(biāo)1的位置預(yù)測框目標(biāo)1的搜索框目標(biāo)2被誤認的目標(biāo)3的位置框 圖1 目標(biāo)粘連示意圖2.3 多目標(biāo)的快速匹配本方案在完成目標(biāo)檢測后，并不

13、判斷是否發(fā)生了目標(biāo)粘連，而是無論發(fā)生粘連與否，都進行簡化的顏色匹配。若顏色匹配成功，則必然沒有粘連的情況發(fā)生，更新穩(wěn)定度數(shù)組。這樣便僅使用較少的采樣點，實現(xiàn)了跟蹤。若顏色匹配失敗，則有兩種可能：一是發(fā)生了目標(biāo)粘連，二是目標(biāo)消亡。對這兩種可能，無需設(shè)計專門的模塊進行判斷，只需將stablej的相應(yīng)元素減1，然后用卡爾曼預(yù)測估計這一幀目標(biāo)的真實位置。系統(tǒng)會在穩(wěn)定度減至0之前始終保留該目標(biāo)的相關(guān)數(shù)據(jù)，當(dāng)發(fā)生碰撞或遮擋的兩目標(biāo)分離后，即可重新實現(xiàn)跟蹤。如果該目標(biāo)的穩(wěn)定度已降為0，則認為目標(biāo)消亡，刪除該目標(biāo)相應(yīng)的跟蹤參數(shù)。另外，當(dāng)碰撞遮擋發(fā)生時，由于粘連目標(biāo)無法實現(xiàn)匹配，因此系統(tǒng)會將粘連目標(biāo)誤認為新生目

14、標(biāo)（如圖1中目標(biāo)1和2發(fā)生粘連，被標(biāo)記為目標(biāo)3）。本文沒有設(shè)計專門的模塊對目標(biāo)是新生目標(biāo)還是粘連目標(biāo)進行判斷，而是通過穩(wěn)定度數(shù)組對目標(biāo)存在的可能性大小進行標(biāo)記：新生目標(biāo)會隨著跟蹤的進行穩(wěn)定度逐次增加至smax；而粘連目標(biāo)則會在目標(biāo)分離后穩(wěn)定度逐次減小至0，之后便不再參與任何計算和顯示。通過以上方法，匹配過程大大減化。3 基于顏色匹配的密集多目標(biāo)快速跟蹤算法實現(xiàn)3.1 目標(biāo)檢測檢測模塊運用多種形態(tài)學(xué)方法，可得到較清晰的目標(biāo)二值圖像。通過背景差分可以得到目標(biāo)的大致輪廓，但輪廓不夠清晰準(zhǔn)確。采用腐蝕方法，可有效去除邊緣噪聲，得到較清晰的目標(biāo)二值圖像。通過目標(biāo)區(qū)域標(biāo)注，可將n個目標(biāo)依次標(biāo)記為1，2，n

15、，n即為搜索范圍內(nèi)的目標(biāo)總數(shù)。為了防止出現(xiàn)虛假目標(biāo)，對于目標(biāo)外形相似的情況，利用目標(biāo)的像素面積基本一致這一特點，可認為小于某面積的目標(biāo)為虛假目標(biāo)并消除，由此去除了虛假目標(biāo)。通過上述方法，便得到了清晰、準(zhǔn)確的目標(biāo)二值圖像。返回的目標(biāo)總數(shù)和目標(biāo)坐標(biāo)、半徑等參數(shù)，將作為跟蹤部分的相關(guān)參數(shù)被使用。3.2目標(biāo)位置預(yù)測在i>1的各幀中，可通過上一幀的真實位置，利用卡爾曼10狀態(tài)預(yù)測方程：x(i|i-1)=ax(i-1|i-1)+ w(i) （4）預(yù)測出下一幀可能出現(xiàn)的位置x(i|i-1)，考慮了預(yù)測可能存在的誤差，及目標(biāo)運動方向突然發(fā)生變化（如碰撞分離后）等情況，可將位置預(yù)測框擴大為目標(biāo)大小的若干倍

16、作為搜索框。這樣，目標(biāo)檢測只在搜索框內(nèi)進行，縮小了搜索范圍，同時可將上一幀目標(biāo)直接與搜索框內(nèi)的目標(biāo)進行匹配，判斷是否為同一目標(biāo)，縮小了匹配范圍，提高了匹配速度，又大大降低因顏色相近的其他目標(biāo)的干擾，而導(dǎo)致誤判的可能。位置預(yù)測的另一個重要作用是，當(dāng)發(fā)生碰撞或遮擋時，系統(tǒng)無法在目標(biāo)粘連區(qū)域內(nèi)區(qū)分出原目標(biāo)，但通過公式（4）的計算，仍可估計出目標(biāo)的位置，并將預(yù)測位置作為真實位置，顯示真實位置框，繼續(xù)參與下一幀的卡爾曼濾波的迭代計算。3.3多目標(biāo)跟蹤算法的實現(xiàn)step1 相關(guān)參數(shù)的初始化。第1幀圖像，進行目標(biāo)檢測，初始化stable數(shù)組、卡爾曼濾波參數(shù)。將每個目標(biāo)采樣點處的rgb顏色值存入colormo

17、de顏色模型矩陣。step2 目標(biāo)的預(yù)測與檢測。第i（i>1）幀圖像，依次對第j（j=1,2n，n為目標(biāo)總數(shù)）個目標(biāo)，計算其搜索框，在搜索框內(nèi)進行目標(biāo)檢測（若目標(biāo)密集，可能檢測到多個目標(biāo)）。step3 簡化的顏色匹配。對搜索框內(nèi)檢測到的目標(biāo)l（l=1,2l，l為搜索框內(nèi)檢測到的目標(biāo)總數(shù)），依次與目標(biāo)j進行顏色匹配。a.若目標(biāo)l與目標(biāo)j顏色匹配成功，則實現(xiàn)了跟蹤，搜索框內(nèi)序號在l之后的目標(biāo)不再與目標(biāo)j進行匹配。目標(biāo)j的穩(wěn)定度加1（加至smax為止），且記錄目標(biāo)j的檢測框（即目標(biāo)l的位置）；b.若搜索框內(nèi)檢測到的l個目標(biāo)全部與目標(biāo)j顏色匹配失?。ò繕?biāo)檢測模塊沒有檢測到目標(biāo)的情況，即l=0

18、），則目標(biāo)j的穩(wěn)定度減1（減至0為止）。step4 檢測新生目標(biāo)。對圖像中不屬于任何檢測框的區(qū)域進行目標(biāo)檢測，檢測到的目標(biāo)記為新生目標(biāo)，初始化過程同step1。step5 更新相關(guān)參數(shù)，顯示目標(biāo)位置。更新卡爾曼參數(shù)及colormode矩陣。對于目標(biāo)j，若該目標(biāo)實現(xiàn)匹配，則顯示檢測框和真實位置框（由卡爾曼濾波算法得到）；若匹配失敗，但穩(wěn)定度不為0，則根據(jù)式（4），將預(yù)測位置作為真實位置顯示真實位置框；若匹配失敗且穩(wěn)定度為0，則認為目標(biāo)j 消亡，刪除該目標(biāo)的所有參數(shù)。step6 跳轉(zhuǎn)至步驟step4，進行下一幀圖像的跟蹤計算。4 實驗仿真本文對基于簡化顏色匹配的多目標(biāo)跟蹤方案進行了仿真。首先通過4

19、個運動小球的圖像序列，展示了檢測跟蹤的結(jié)果，并對碰撞情況的跟蹤結(jié)果進行了說明。接著對該方案稍加修改，即可應(yīng)用于公共場所的視頻監(jiān)控。 4.1 碰撞情況的跟蹤實驗 圖2b 紅綠兩球碰撞的目標(biāo)跟蹤示意圖圖2c 碰撞后目標(biāo)跟蹤示意圖圖2b 藍紫兩球碰撞的目標(biāo)跟蹤示意圖實驗一：五個不同顏色的運動小球的多目標(biāo)檢測和跟蹤。開始階段，五個小球沿各自初始方向運動。在第3幀，藍、紫兩球發(fā)生碰撞，在第4幀，紅、綠兩球碰撞，兩組球均在碰撞后的下一幀彈開。根據(jù)目標(biāo)的特點，采樣點為沿著目標(biāo)的運動方向，在目標(biāo)質(zhì)心的前后4/5半徑處的兩個像素點即k=2，色差閥值a=12,穩(wěn)定度最大值smax=5，匹配數(shù)閥值為2。圖3 小球的

20、運動軌跡圖2展示了目標(biāo)的跟蹤結(jié)果。圖2a-2c分別展示出第三幀、第四幀發(fā)生碰撞時及第五幀碰撞結(jié)束后的跟蹤結(jié)果，白色“+”線表示被檢測并成功匹配的目標(biāo)；黑色“-”線表示本幀目標(biāo)經(jīng)過卡爾曼濾波后得到的真實位置?？梢?，在發(fā)生碰撞時而由于籃球與紫球、紅球與綠球分別發(fā)生粘連，兩組目標(biāo)都沒有被檢測到，而是被誤認為新生目標(biāo)。但由于它們的穩(wěn)定度stablej未降至0，因此仍通過卡曼預(yù)測原理，對四個球的位置進行較準(zhǔn)確的估計（如“-”線所示）。在第4幀（圖2b），藍、紫球又重新實現(xiàn)檢測與匹配，在第5幀（圖2c）,紅、綠球又重新實現(xiàn)檢測與匹配。同時因粘連而產(chǎn)生的虛假目標(biāo)穩(wěn)定度降為0，不再被跟蹤。圖3則顯示了五個小球

21、的運動軌跡。x、y坐標(biāo)分別表示小球在各幀中橫縱方向的位置。由圖3可見，該算法在存在碰撞的情況下仍能對目標(biāo)的位置進行正確的估計。4.2 公共場所的多目標(biāo)跟蹤實驗二：公路監(jiān)控視頻的多目標(biāo)跟蹤。實驗對公路上的機動車進行跟蹤，采用的圖像序列的分辨率為640*480，幀率為6/s，時長t=10s。在簡化的顏色匹配部分，將車尾和車頂區(qū)域作為采樣區(qū)域，兩區(qū)域分別選取了兩個采樣點來與每個目標(biāo)的顏色模型colormode比較。四個顏色采樣點位置為汽車運動方向的前后距質(zhì)心距離為7/10半徑，垂直運動方向的左右距質(zhì)心水平距離為1/5半徑處的四個像素點，k=4。色差閥值a=10,穩(wěn)定度最大值smax=3。圖4展示了公

22、路機動車監(jiān)控視頻對其中一組機動車（共7輛）的跟蹤結(jié)果。由圖可見，采用提出的算法，能夠?qū)矆鏊亩噙\動目標(biāo)進行準(zhǔn)確的跟蹤。4.3 計算量分析本文采用對特征區(qū)域進行顏色采樣的簡化的顏色匹配方案。由式（1）-（3）可知，當(dāng)采樣點數(shù)為k時，只需4k-1次加減法，2k次邏輯與運算；當(dāng)目標(biāo)像素點總數(shù)為nm時，文獻5中的均值法,每個圖4 公路機動車的跟蹤目標(biāo)顏色模型的建立需要6 nm次加減法，nm+2次乘除法；文獻6的改進直方圖方法，由于采用的顏色量化級為32 × 32 × 32，因此共有323種顏色，每種顏色從計算直方圖顏色概率u到映射至（0,255）轉(zhuǎn)換為灰度圖的過程，共需3 nm

23、+1次加減法，3 nm+2次乘除法。由于k<< nm，可見本文算法的計算量大大降低。在發(fā)生碰撞時，通過穩(wěn)定度數(shù)組的設(shè)置，沒有增加額外的計算量，使碰撞和遮擋發(fā)生時的匹配被大大簡化，在保證正確跟蹤的同時，進一步提高了跟蹤速度。結(jié)束語本文提出了一種簡化的基于顏色的匹配算法，且通過設(shè)置穩(wěn)定度數(shù)組并與卡爾曼預(yù)測相結(jié)合，便可實現(xiàn)密集環(huán)境中碰撞、遮擋等情況下的多目標(biāo)快速準(zhǔn)確跟蹤。具體實現(xiàn)上，首先在搜索框內(nèi)綜合使用多種形態(tài)學(xué)方法檢測目標(biāo)位置；再對目標(biāo)采樣點進行顏色匹配；根據(jù)匹配結(jié)果更新穩(wěn)定度數(shù)組并顯示跟蹤結(jié)果。實驗證明了該系統(tǒng)能夠應(yīng)對碰撞、遮擋等特殊情況，且能實現(xiàn)公共場所的多目標(biāo)快速準(zhǔn)確跟蹤。參考文獻1隆武林,陳穎琪.基于圖像分割與特征匹配的目標(biāo)檢測及跟蹤j.信息技術(shù),2009,11:18-23 2 coll insr t. mean-shift blob tra