毛曉波,郝向東,梁　靜

基于ELM與Mean Shift的抗遮擋目標(biāo)跟蹤算法

毛曉波,郝向東,梁靜

(鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州 450001)

摘要：針對目標(biāo)跟蹤過程中發(fā)生遮擋時(shí)跟蹤出現(xiàn)偏差的情況，在傳統(tǒng)Mean Shift跟蹤算法的基礎(chǔ)上引入極限學(xué)習(xí)機(jī)(extreme learning machine,ELM)，提出了基于ELM與Mean Shift的目標(biāo)跟蹤算法。該算法根據(jù)過去3個(gè)時(shí)刻的目標(biāo)位置信息，利用ELM預(yù)測出目標(biāo)當(dāng)前可能位置，代替目標(biāo)前一時(shí)刻位置作為Mean Shift迭代起始點(diǎn)，并在鄰域范圍內(nèi)進(jìn)行迭代，得到目標(biāo)的真實(shí)位置.實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的改進(jìn)算法相比，新算法減少了迭代次數(shù)和運(yùn)算時(shí)間，同時(shí)在遮擋情況下能夠準(zhǔn)確定位目標(biāo)位置并進(jìn)行跟蹤，提高了跟蹤系統(tǒng)的實(shí)時(shí)性和魯棒性.

關(guān)鍵詞：目標(biāo)跟蹤；遮擋；Mean Shift；ELM

0引言

目標(biāo)跟蹤技術(shù)是機(jī)器視覺的熱門課題, 廣泛應(yīng)用于工業(yè)生產(chǎn)、國防軍事和生活安防等眾多領(lǐng)域.遮擋問題是目前目標(biāo)跟蹤的難題之一，遮擋尤其是嚴(yán)重遮擋會(huì)直接影響跟蹤的準(zhǔn)確性和持續(xù)性，可能導(dǎo)致目標(biāo)跟蹤發(fā)生偏差甚至丟失目標(biāo).因此，研究抗遮擋的目標(biāo)跟蹤算法具有重要的理論和實(shí)際意義.

Mean Shift算法[1]、光流算法[2]、卡爾曼濾波算法[3]、粒子濾波算法[4]等都能在一定條件下有效地跟蹤目標(biāo).其中，Mean Shift算法以其無需參數(shù)、快速模式匹配的特性被廣泛地應(yīng)用[5].但是,當(dāng)目標(biāo)運(yùn)動(dòng)速度過快或遮擋較為嚴(yán)重時(shí)，傳統(tǒng)Mean Shift算法往往會(huì)發(fā)生目標(biāo)的定位偏差甚至跟丟.為解決上述問題，研究人員提出了一些有效方法，如在算法中引入模板分塊匹配[6]或?qū)ean Shift算法與濾波算法相結(jié)合[7-10]等.這些方法能夠提高跟蹤算法的抗遮擋能力，但由于需要進(jìn)行分塊跟蹤或進(jìn)行復(fù)雜的濾波運(yùn)算，增加了算法的復(fù)雜度，跟蹤實(shí)時(shí)性受到影響.針對以上問題，筆者提出一種基于ELM與Mean Shift的抗遮擋目標(biāo)跟蹤算法，利用ELM的快速學(xué)習(xí)和預(yù)測能力預(yù)測目標(biāo)的運(yùn)動(dòng)趨勢，以預(yù)測出的目標(biāo)中心作為Mean Shift迭代起始點(diǎn)，通過迭代得到目標(biāo)當(dāng)前真實(shí)位置.筆者將新算法與基于模板分塊匹配的Mean Shift算法和基于卡爾曼濾波的Mean Shift算法作了比較.實(shí)驗(yàn)證明，新算法能夠在目標(biāo)高速運(yùn)動(dòng)或遮擋情況下快速精確穩(wěn)定地跟蹤目標(biāo)，具有很好的實(shí)時(shí)性和魯棒性.

1Mean Shift算法

Mean Shift算法是一種基于核密度估計(jì)的非參數(shù)模式匹配算法, 通過建立加權(quán)直方圖來描述目標(biāo)的顏色分布[11].該方法利用像素概率密度函數(shù)梯度最優(yōu)化方法,首先選定跟蹤目標(biāo)的區(qū)域，計(jì)算核函數(shù)加權(quán)下的目標(biāo)區(qū)域的直方圖分布，然后用同樣的方法對當(dāng)前幀的數(shù)據(jù)密度直方圖進(jìn)行漂移，且通過Mean Shift迭代尋找與目標(biāo)區(qū)域相似性最大的區(qū)域，最終實(shí)現(xiàn)快速目標(biāo)定位.

1.1目標(biāo)模型

Mean Shift跟蹤算法利用目標(biāo)區(qū)域的直方圖分布來描述目標(biāo)，根據(jù)目標(biāo)模型和候選模型的相似度進(jìn)行中心的均值漂移.在第一幀中手動(dòng)確定包含跟蹤目標(biāo)的區(qū)域，設(shè)中心坐標(biāo)為d0;區(qū)域中包含n個(gè)像素，位置記為{di}i=1,2,…，n；特征值u=1,2,…,m是直方圖的顏色索引.則目標(biāo)模型的特征估計(jì)概率密度可表示為

(1)

式中：h為核函數(shù)的窗寬，即目標(biāo)區(qū)域的大小；s(·)為核函數(shù)的輪廓函數(shù)，對靠近中心的區(qū)域像素賦予一個(gè)大的權(quán)值，對遠(yuǎn)離中心的區(qū)域像素賦予越來越小的權(quán)值；δ[·]是克羅內(nèi)科函數(shù)，δ[·]用于判斷目標(biāo)區(qū)域中像素di的顏色值是否屬于第u個(gè)單元的顏色索引值，若為1,則是,為0,則不是；Ch為歸一化常數(shù)，其取值滿足

(2)

1.2候選模型

目標(biāo)運(yùn)動(dòng)過程中，每一幀圖像中目標(biāo)可能存在的區(qū)域稱為候選區(qū)域，其核函數(shù)窗寬中的特征模型稱為目標(biāo)候選模型.假設(shè)第k幀時(shí)得到的目標(biāo)中心為yk，則在第k+1幀中候選模型的特征值為：

1.3相似度判定函數(shù)

在跟蹤過程中，Mean Shift算法將候選模型與目標(biāo)模型進(jìn)行相似性判別，尋找式(3)中最優(yōu)的yk，使得pu和qu相似度達(dá)到最大.qu和pu的相似度可由如下函數(shù)判定：

(4)

式中：ρ(y)是Bhattacharyya系數(shù)，其值在0～1之間，ρ(y)值越大，表示兩個(gè)模型相似度越高.目標(biāo)發(fā)生遮擋時(shí)，ρ(y)變小，給定遮擋閾值T，當(dāng)ρ(y)

1.4Mean Shift算法

(5)

(6)

由式(6)可知，相似度函數(shù)只隨等式右側(cè)第二項(xiàng)中y的變化而變化，與第一項(xiàng)無關(guān).通過Mean Shift算法在鄰域內(nèi)不斷迭代，對相似度函數(shù)求最大值，即可得到跟蹤目標(biāo)新的位置：

(7)

迭代結(jié)束后，得到的yk+1，即為第k+1幀的目標(biāo)中心.

1.5Mean Shift算法的缺點(diǎn)

在實(shí)際應(yīng)用中，由于Mean Shift算法沒有專門有效的抗遮擋機(jī)制，當(dāng)跟蹤目標(biāo)經(jīng)過遮擋物時(shí)，往往會(huì)發(fā)生目標(biāo)的跟偏甚至跟丟.另外，當(dāng)目標(biāo)高速運(yùn)動(dòng)時(shí)，Mean Shift算法跟蹤效果變差.為此，筆者在Mean Shift算法的基礎(chǔ)上引入了ELM算法[12-13]，利用ELM的預(yù)測能力較好地解決了上述問題.

2ELM與Mean Shift相結(jié)合的算法

2.1ELM的基本原理

若一個(gè)標(biāo)準(zhǔn)的單隱層前饋神經(jīng)網(wǎng)絡(luò)含有N個(gè)訓(xùn)練樣本，記為{xi，oi}i=1,2,…,N，其中xi= (xi1,xi2,…,xin)T∈Rn，oi= (oi1,oi2,…,oim)T∈Rm，含有N′個(gè)隱層節(jié)點(diǎn)，設(shè)其激勵(lì)函數(shù)為g(x)，則該神經(jīng)網(wǎng)絡(luò)的輸出可以表示為

納稅意識(shí)是指公民、法人等納稅人對稅法確定的納稅義務(wù)的認(rèn)同和看法。納稅意識(shí)強(qiáng)，則會(huì)積極主動(dòng)配合稅務(wù)機(jī)關(guān)依法納稅；納稅意識(shí)弱則會(huì)拖延納稅、偷稅逃稅，對稅務(wù)機(jī)關(guān)的征稅行為采取隱瞞、欺騙甚至抵抗行為。

式中：wi= (wi1,wi2,…，win)T為輸入神經(jīng)元與第i個(gè)隱層節(jié)點(diǎn)的輸入權(quán)值；βi= (βi1,βi2,…，βim)T為第i個(gè)隱層節(jié)點(diǎn)與輸出神經(jīng)元的輸出權(quán)值；bi為第i個(gè)隱層節(jié)點(diǎn)的偏置.

神經(jīng)網(wǎng)絡(luò)的理想目標(biāo)是實(shí)際輸出與給定樣本相等，因此存在βi、wi和bi使得

(9)

式(9)即為ELM的模型，其中,οj為第j個(gè)輸入樣本的對應(yīng)的輸出樣本，該模型可用矩陣表示為

Hβ=O.

(10)

H為神經(jīng)網(wǎng)絡(luò)的隱層輸出矩陣.在ELM中，輸入權(quán)重wi和隱層偏置bi由系統(tǒng)隨機(jī)確定，則H被唯一確定.由Moore-Penrose廣義逆定理可求出H+，則

β=H+O .

(11)

2.2基于ELM與Mean Shift的抗遮擋目標(biāo)跟蹤算法

在目標(biāo)運(yùn)動(dòng)過程中，第t時(shí)刻目標(biāo)的位置與其上一時(shí)刻的位置、速度和加速度有關(guān)，即可以通過這3個(gè)參數(shù)確定目標(biāo)當(dāng)前時(shí)刻的位置.而這3個(gè)參數(shù)包含在第t-1、t-2、t-3時(shí)刻的目標(biāo)位置信息中，因此，由前3時(shí)刻目標(biāo)的位置可以預(yù)測出第4時(shí)刻目標(biāo)的位置.

首先,通過對無遮擋目標(biāo)的精確跟蹤得到一組目標(biāo)運(yùn)動(dòng)軌跡，為了提高樣本精確度，采用手工逐幀確定.取連續(xù)200組中的前160組位置坐標(biāo)作為ELM的訓(xùn)練樣本，將連續(xù)3組坐標(biāo)作為輸入，第4組作為輸出來訓(xùn)練ELM神經(jīng)網(wǎng)絡(luò).利用后40組作為測試樣本，通過不斷調(diào)節(jié)隱層節(jié)點(diǎn)數(shù)使預(yù)測達(dá)到最優(yōu).同理，對遮擋目標(biāo)進(jìn)行訓(xùn)練，訓(xùn)練樣本和測試樣本依然分別取160組和40組.調(diào)節(jié)隱層節(jié)點(diǎn)數(shù)，使兩個(gè)訓(xùn)練集合的預(yù)測結(jié)果最佳.通過試驗(yàn)，當(dāng)隱層節(jié)點(diǎn)設(shè)為30時(shí),預(yù)測值達(dá)到最優(yōu).

(12)

于是，式(7)變?yōu)?/p>

(13)

同時(shí)計(jì)算ρ(y)并與遮擋閾值T進(jìn)行比較，若ρ(y)≥T，則繼續(xù)執(zhí)行；若ρ(y)

3仿真結(jié)果分析

在2.10 GHz主頻4 GB內(nèi)存的Windows8操作系統(tǒng)電腦上使用Matlab2010，對筆者提出的算法進(jìn)行了測試實(shí)驗(yàn)，并在相同條件下與基于模板分塊匹配的Mean Shift算法和基于卡爾曼濾波的Mean Shift算法跟蹤效果進(jìn)行了對比.

為驗(yàn)證跟蹤結(jié)果的實(shí)時(shí)性，我們對公路上高速行駛的汽車進(jìn)行了20次跟蹤，統(tǒng)計(jì)3種算法對第11幀到110幀共計(jì)100幀目標(biāo)進(jìn)行20次跟蹤的平均迭代次數(shù)，并對跟蹤效果進(jìn)行了對比.表1顯示了3種不同算法的平均迭代次數(shù)對比結(jié)果.通過對比可以發(fā)現(xiàn)，由于新算法采用了位置預(yù)測，迭代起始位置與目標(biāo)實(shí)際位置的距離大大減少，因此比基于模板分塊匹配的Mean Shift算法迭代次數(shù)平均減少1.20次；同時(shí),新算法的位置預(yù)測方法較卡爾曼濾波更為簡便，一定程度上簡化了融合算法且計(jì)算效率有所提高， 比基于卡爾曼濾波的Mean Shift算法平均減少0.76次.

表1　3種算法迭代次數(shù)

表2為3種算法分別對100幀視頻進(jìn)行20次跟蹤的平均時(shí)間.由表2可知，新算法平均跟蹤時(shí)間是4 918 ms，比兩種已有改進(jìn)算法分別減少17.9%和7.2%.

表2　3種算法跟蹤時(shí)間

圖1為3種算法跟蹤效果，分別取第20、40、60、80幀圖片.表3為3種算法的跟蹤誤差，表示跟蹤位置和實(shí)際位置中心的距離，實(shí)際位置采用手工逐幀確定.由表3可知，新算法與基于模板分塊匹配的 Mean Shift算法跟蹤誤差近似，明顯小于基于卡爾曼濾波的Mean Shift算法.

圖1　高速運(yùn)動(dòng)車輛跟蹤結(jié)果對比

算法Frame20Frame40Frame60Frame80分塊算法5.38518.60140.79252.631濾波算法6.70824.83961.221107.415 新算法6.00017.80444.68954.918

圖2為3種算法對公路上被遮擋車輛進(jìn)行跟蹤的結(jié)果，分別取第5、17、29、43幀圖片.表4為3種算法的跟蹤誤差.由表4可以看出，當(dāng)目標(biāo)發(fā)生遮擋時(shí)，3種算法跟蹤誤差變化較為劇烈，此時(shí)新算法的跟蹤誤差為66.129，明顯小于另外兩種改進(jìn)算法.遮擋結(jié)束后恢復(fù)到正常跟蹤，3種算法跟蹤誤差均變小.

圖2　遮擋車輛跟蹤結(jié)果對比

算法Frame5Frame17Frame29Frame43分塊算法3.00031.32181.02549.980濾波算法4.12337.121110.02377.621新算法2.82832.24966.12941.976

表5為3種算法跟蹤60幀車輛遮擋視頻所用時(shí)間，新算法跟蹤時(shí)間比另外兩種改進(jìn)算法分別減少18.5%和7.5%.

表5　3種算法跟蹤時(shí)間

圖3為3種算法對被遮擋的行人進(jìn)行跟蹤的結(jié)果，取第20、40、50、70幀進(jìn)行比較.由圖3可以看出，由于跟蹤過程中行人被完全遮擋，基于模板分塊匹配的Mean Shift算法無法進(jìn)行子塊匹配，造成了錯(cuò)誤的跟蹤，丟失了目標(biāo)；而基于卡爾曼濾波的Mean Shift算法和新算法在目標(biāo)被遮擋時(shí)自動(dòng)以預(yù)測的目標(biāo)位置為起點(diǎn)繼續(xù)跟蹤，遮擋結(jié)束后恢復(fù)正常跟蹤，因此能夠較好地跟蹤目標(biāo).

圖3　行人遮擋跟蹤結(jié)果對比

以上實(shí)驗(yàn)表明，當(dāng)目標(biāo)高速運(yùn)動(dòng)或發(fā)生遮擋時(shí)，新算法具有更好的實(shí)時(shí)性和魯棒性.

4結(jié)論

筆者提出一種基于ELM與Mean Shift的抗遮擋目標(biāo)跟蹤算法，解決了Mean Shift算法在目標(biāo)發(fā)生遮擋時(shí)跟蹤性能變差的問題.該算法利用目標(biāo)的歷史位置信息，通過神經(jīng)網(wǎng)絡(luò)預(yù)測出當(dāng)前位置信息，所需信息少，計(jì)算量小，有效地減少了迭代次數(shù)，在目標(biāo)發(fā)生遮擋時(shí)以預(yù)測位置信息繼續(xù)跟蹤，能夠準(zhǔn)確跟蹤目標(biāo).實(shí)驗(yàn)證明，新算法能夠在目標(biāo)發(fā)生嚴(yán)重遮擋時(shí)準(zhǔn)確跟蹤目標(biāo)，具有很好的實(shí)時(shí)性和魯棒性，并且與現(xiàn)有的改進(jìn)算法相比，具有一定的優(yōu)勢.

神經(jīng)網(wǎng)絡(luò)具有強(qiáng)大的自學(xué)能力、聯(lián)想能力和計(jì)算能力，將神經(jīng)網(wǎng)絡(luò)應(yīng)用到目標(biāo)跟蹤技術(shù)中，突破傳統(tǒng)算法的限制，使跟蹤系統(tǒng)更加智能化，為解決目標(biāo)跟蹤問題提供了新方法，對于處理目標(biāo)跟蹤過程中的遮擋問題，提高復(fù)雜場景下目標(biāo)跟蹤的穩(wěn)定性具有重要意義.筆者并沒有考慮多目標(biāo)跟蹤的問題，因此下一步將考慮對多個(gè)目標(biāo)進(jìn)行跟蹤時(shí)如何利用神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)有效跟蹤.

參考文獻(xiàn)：

[1]何志勇，蔡樂才，許繼家．基于Mean Shift算法跟蹤視頻中運(yùn)動(dòng)目標(biāo)[J]．鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2010，42(1)：38-40，48．

[2]李劍峰，黃增喜，劉怡光．基于光流場估計(jì)的自適應(yīng)Mean-Shift目標(biāo)跟蹤算法[J]．光電子·激光，2012，23(10)：1996-2002．

[3]WENG S K，KUO C M，TU S K．Video object tracking using adaptive Kalman filter[J]． Journal of visual communication and image representation，2006，17(6)：1190-1208．

[4]屈鑒銘，劉志鏡，賀文驊．結(jié)合有向場景運(yùn)動(dòng)模式的粒子濾波行人跟蹤方法[J]．西安交通大學(xué)學(xué)報(bào)，2014，48(12)：74-79．

[5]袁霄，王麗萍．基于MeanShift算法的運(yùn)動(dòng)人體跟蹤[J]．計(jì)算機(jī)工程與科學(xué)，2008，30(4)：46-49．

[6]顏佳，吳敏淵，陳淑珍，等．應(yīng)用Mean Shift和分塊的抗遮擋跟蹤[J]．光學(xué) 精密工程，2010，18(6)：1413-1418．

[7]章學(xué)靜，陳禾，楊靜．結(jié)合卡爾曼濾波和Mean Shift的抗遮擋跟蹤算法[J]．北京理工大學(xué)學(xué)報(bào)，2013，33(10)：1056-1061．

[8]張偉麗，江春華，郝宗波．基于改進(jìn)的均值漂移和卡爾曼濾波的目標(biāo)跟蹤算法[J]．計(jì)算機(jī)應(yīng)用與軟件，2014，31(5)：240-243．

[9]HE J W,YANG Y Y．Signal Processing, communications and computing: ICSPCC2014[C] ∥Multi-interative tracking mathod using meanshift based on kalman filter.Guilin，2014：22-27．

[10]權(quán)義萍，金鑫，張蕾，等．基于Mean-Shift的卡爾曼粒子濾波車輛跟蹤算法研究[J]．計(jì)算機(jī)應(yīng)用與軟件，2014，31(9)：236-252．

[11]楊杰，張翔．視頻目標(biāo)檢測和跟蹤及其應(yīng)用[M]．上海：上海交通大學(xué)出版社，2012．

[12]王杰，畢浩洋．一種基于粒子群優(yōu)化的極限學(xué)習(xí)機(jī)[J]．鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2013，45(1) ：100-104．

[13]胡義涵，張小剛，陳華，等．一種基于魯棒估計(jì)的極限學(xué)習(xí)機(jī)方法[J]．計(jì)算機(jī)應(yīng)用研究，2012，29(8)：2926-2930．

Target Tracking Algorithm Based on Mean Shift with ELM

MAO Xiaobo, HAO Xiangdong, LIANG Jing

(School of Electrical Engineering,Zhengzhou University，Zhengzhou 450001,China)

Abstract:In view of the problem of object deviation when occlusions occur during the target tracking, a new algorithm using Mean Shift with ELM is proposed. According to the formal information of the object’s location, current possible location was predicted by ELM, the iteration was started from the possible location instead of formal location, and the object’s real center is calculated by mean shift algorithm. The simulation results show that proposed algorithm can track precisely target occluded, operation time and number of iteration are reduced so that efficiency and robustness are improved.

Key words:target tracking; occlusion; Mean Shift; ELM

收稿日期:2015-03-10；

修訂日期：2015-05-20

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61473266); 河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目資助計(jì)劃(14A410001)

作者簡介:毛曉波(1965—)，男，河南開封人，鄭州大學(xué)教授，博士，主要從事仿生機(jī)器視覺研究，E-mail: mail-mxb@zzu.edu.cn.

文章編號(hào):1671-6833(2016)01-0001-05

中圖分類號(hào)：U461.6

文獻(xiàn)標(biāo)志碼：A

doi:10.3969/j.issn.1671-6833.201503043

引用本文:毛曉波,郝向東,梁靜.基于ELM與Mean Shift的抗遮擋目標(biāo)跟蹤算法[J].鄭州大學(xué)學(xué)報(bào)(工學(xué)版)，2016,37(1):1-5.