基于顏色匹配的密集多目標快速跟蹤算法

1、基于顏色匹配的密集多目標快速跟蹤算法摘 要：基于公共場所的監(jiān)控場景，提出了一種適用于目標密集環(huán)境的多運動目標快速跟蹤算法。該方法運用形態(tài)學(xué)方法準確提取目標后，根據(jù)卡爾曼原理得到目標在下一幀的預(yù)測位置，并以此確定搜索框的位置，提高匹配速率；然后在搜索框內(nèi)運用基于簡化的顏色匹配跟蹤方案,用于實現(xiàn)密集運動目標的快速跟蹤；且通過設(shè)定穩(wěn)定度數(shù)組，來迅速排除碰撞、遮擋情況形成的干擾。仿真表明，該方法能在多目標跟蹤過程中正確處理目標的碰撞、遮擋等問題，可實現(xiàn)公共場所的實時監(jiān)控。關(guān)鍵詞：多密集目標跟蹤,顏色匹配,穩(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)控便是多目標的匹配與跟蹤技術(shù)的應(yīng)用之一，其設(shè)計難點是目標密集情況和發(fā)生碰撞遮擋情況的目標匹配與跟蹤。多運動目標匹配的常用方法有基于距離的匹配1，基于目標位置、形狀或速度等目標特征的匹配2，上下幀目標重疊像素數(shù)的匹配3，區(qū)域生長4，基于顏色的匹配5-6等。其中，基于

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22、路機動車監(jiān)控視頻對其中一組機動車（共7輛）的跟蹤結(jié)果。由圖可見，采用提出的算法，能夠?qū)矆鏊亩噙\動目標進行準確的跟蹤。4.3 計算量分析本文采用對特征區(qū)域進行顏色采樣的簡化的顏色匹配方案。由式（1）-（3）可知，當采樣點數(shù)為k時，只需4k-1次加減法，2k次邏輯與運算；當目標像素點總數(shù)為nm時，文獻5中的均值法,每個圖4 公路機動車的跟蹤目標顏色模型的建立需要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)境中碰撞、遮擋等情況下的多目標快速準確跟蹤。具體實現(xiàn)上，首先在搜索框內(nèi)綜合使用多種形態(tài)學(xué)方法檢測目標位置；再對目標采樣點進行顏色匹配；根據(jù)匹配結(jié)果更新穩(wěn)定度數(shù)組并顯示跟蹤結(jié)果。實驗證明了該系統(tǒng)能夠應(yīng)對碰撞、遮擋等特殊情況，且能實現(xiàn)公共場所的多目標快速準確跟蹤。參考文獻1隆武林,陳穎琪.基于圖像分割與特征匹配的目標檢測及跟蹤j.信息技術(shù),2009,11:18-23 2 coll insr t. mean-shift blob tra