一種基于Meanshift算法的目標(biāo)跟蹤改進(jìn)

朱 鉀， 李 化

(太原理工大學(xué) 信息工程學(xué)院， 山西 晉中 030600)

?

一種基于Meanshift算法的目標(biāo)跟蹤改進(jìn)

朱 鉀， 李 化

(太原理工大學(xué) 信息工程學(xué)院， 山西 晉中 030600)

針對(duì)遮擋及相似干擾問(wèn)題， 在Meanshift算法的基礎(chǔ)上提出了一種新的改進(jìn)算法. 該算法有效地將Meanshift算法與Kalman濾波算法結(jié)合， 準(zhǔn)確確定目標(biāo)質(zhì)心位置， 并根據(jù)目標(biāo)質(zhì)心位置及前一幀搜索窗口邊界自適應(yīng)地調(diào)整當(dāng)前搜索窗口， 使其與目標(biāo)位置更匹配， 跟蹤結(jié)果更加準(zhǔn)確、 可靠， 同時(shí)也減小了環(huán)境等因素對(duì)算法的影響. 實(shí)驗(yàn)對(duì)比結(jié)果表明， 改進(jìn)算法具有良好的穩(wěn)定性和自適應(yīng)性， 可有效解決大面積遮擋和相似干擾問(wèn)題.

目標(biāo)跟蹤； Meanshift算法； Kalman濾波算法

0 引 言

目標(biāo)跟蹤包括目標(biāo)檢測(cè)和跟蹤兩部分， 其實(shí)質(zhì)是一個(gè)概率問(wèn)題， 可以通過(guò)實(shí)時(shí)估計(jì)來(lái)理解跟蹤過(guò)程. 近幾年， 目標(biāo)跟蹤在公共安全、 生產(chǎn)安全、 醫(yī)療診斷、 智能交通、 工業(yè)、 軍事等領(lǐng)域有著廣泛的應(yīng)用前景. 雖然國(guó)內(nèi)外研究者在目標(biāo)跟蹤問(wèn)題上提出了很多改進(jìn)算法[1-5]， 但在實(shí)際應(yīng)用中依然存在很多問(wèn)題， 如背景顏色干擾、 光照強(qiáng)度變化、 目標(biāo)尺度變化、 外界環(huán)境復(fù)雜化等直接影響目標(biāo)特征的提取， 最終導(dǎo)致跟蹤失敗.

常見(jiàn)的跟蹤算法有幀間差分法、 背景差分法、 邊緣差分法、 光流法、 Camshift算法[6-8]、 TLD算法[9]等. 本文在Meanshift算法[10]基礎(chǔ)上提出了一種新的改進(jìn)算法， 可根據(jù)目標(biāo)尺度及狀態(tài)選取部分特征進(jìn)行跟蹤， 并通過(guò)質(zhì)心位置及前一幀搜索窗口邊界自適應(yīng)地調(diào)整搜索窗口， 使其與目標(biāo)更匹配， 同時(shí)與Meanshift、 Kalman濾波和Camshift等算法相比， 改進(jìn)算法具有良好的穩(wěn)定性、 可靠性及自適應(yīng)性， 能夠有效解決相似干擾及大面積遮擋問(wèn)題.

1 Meanshift算法

Meanshift算法[10]是一種有效實(shí)時(shí)跟蹤算法， 其本質(zhì)是在給定條件下進(jìn)行多次迭代計(jì)算， 最終找到與目標(biāo)相匹配的區(qū)域. 該算法跟蹤過(guò)程如下： ① 目標(biāo)初始化， 找到初始目標(biāo)位置并建立目標(biāo)模型與候選模型； ② 計(jì)算目標(biāo)模型與候選模型的相似度； ③ 使用Meanshift向量計(jì)算下一幀目標(biāo)位置； ④ 依次重復(fù)以上步驟.

Meanshift算法原理簡(jiǎn)單、 計(jì)算量較小， 但存在很多問(wèn)題. 首先， 目標(biāo)顏色直方圖及模型的選取對(duì)該算法有很大影響. 若背景顏色存在干擾， 目標(biāo)模型及候選模型會(huì)產(chǎn)生一定的誤差， 二者不能準(zhǔn)確匹配， 無(wú)法正確跟蹤目標(biāo)； 其次， 目標(biāo)運(yùn)動(dòng)速度太快， 超出了Meanshift向量計(jì)算范圍， 該算法將無(wú)法繼續(xù)跟蹤目標(biāo)； 最后， 目標(biāo)遇到遮擋或存在相似干擾， 該算法無(wú)法自適應(yīng)地重新構(gòu)建目標(biāo)模型及候選模型進(jìn)行跟蹤.

2 Kalman濾波算法

卡爾曼濾波是一種線性遞歸濾波器， 通常運(yùn)用于解決最佳估計(jì)問(wèn)題. 其主要分為兩個(gè)階段： 預(yù)測(cè)階段和更新階段[11]. 預(yù)測(cè)階段包括狀態(tài)預(yù)測(cè)和誤差協(xié)方差預(yù)測(cè)； 更新階段包括卡爾曼濾波計(jì)算增益系數(shù)、 使用增益系數(shù)修正和誤差協(xié)方差的更新[12].

Kalman濾波通過(guò)對(duì)線性系統(tǒng)建立輸入、 輸出狀態(tài)方程， 每次僅需保存該系統(tǒng)上一時(shí)刻的狀態(tài)， 其系統(tǒng)狀態(tài)方程和測(cè)量方程分別為

式中：A表示狀態(tài)轉(zhuǎn)移矩陣；H表示測(cè)量矩陣；Wi，Vi分別是狀態(tài)噪聲矩陣和測(cè)量的噪聲矩陣， 且均為高斯白噪聲.

Kalman濾波算法原理簡(jiǎn)單、 計(jì)算量小、 實(shí)時(shí)性較強(qiáng)， 通過(guò)系統(tǒng)現(xiàn)有狀態(tài)可預(yù)測(cè)跟蹤目標(biāo)， 存儲(chǔ)量大大減少. 當(dāng)目標(biāo)被遮擋、 背景環(huán)境較復(fù)雜或光照強(qiáng)度發(fā)生明顯變化時(shí)， 都會(huì)影響系統(tǒng)的狀態(tài)轉(zhuǎn)移方程和測(cè)量方程， 系統(tǒng)將無(wú)法準(zhǔn)確確定目標(biāo)狀態(tài)， 因此該算法容易發(fā)生擴(kuò)散現(xiàn)象， 導(dǎo)致跟蹤精度降低.

3 改進(jìn)的算法

針對(duì)遮擋及相似干擾的情況， 本文在Meanshift算法的基礎(chǔ)上， 通過(guò)目標(biāo)質(zhì)心位置及前一幀搜索窗口邊界來(lái)確定當(dāng)前幀搜索窗口， 使其與目標(biāo)位置更加匹配， 減小了環(huán)境等因素對(duì)算法的影響， 以便改進(jìn)算法具有更廣泛的應(yīng)用性. 改進(jìn)算法具體跟蹤過(guò)程如下：

1) 目標(biāo)初始化. 將視頻圖像從RGB顏色空間轉(zhuǎn)換到Y(jié)UV顏色空間， 并提取其U分量. 由式(3)， 式(4)計(jì)算出目標(biāo)模型及候選模型的顏色概率分布直方圖， 找到第一幀目標(biāo)初始位置并初始化搜索窗口；

式中： C, Ch為歸一化系數(shù)， 使得∑qu=1， ∑pu=1， k(‖x‖2)為核函數(shù)； m為量化等級(jí)； h為核函數(shù)的窗寬； x0為假設(shè)目標(biāo)區(qū)域中心位置； xi為目標(biāo)窗口區(qū)域像素歸一化的位置； y0為當(dāng)前幀中目標(biāo)質(zhì)心位置； δ為Kronecker delta函數(shù)；b(x) 為像素在顏色直方圖中的索引函數(shù).

2) 計(jì)算目標(biāo)模型與候選模型的相似度ρ， 如式(5)所示.

4) 通過(guò)質(zhì)心估計(jì)位置及前一幀搜索窗口邊界確定目標(biāo)搜索窗口， 如式(6)～式(9)所示.

由此可知： 改進(jìn)算法可有效彌補(bǔ)Menshift與Kalman濾波算法的不足， Meanshift算法計(jì)算值可作為Kalman濾波的參數(shù)， 并且Kalman濾波的預(yù)測(cè)值亦作為下一幀中Meanshift算法的初始值， 從而使搜索窗口與目標(biāo)位置更加匹配. 跟蹤過(guò)程中若存在遮擋及相似目標(biāo)干擾， 改進(jìn)算法可通過(guò)目標(biāo)原顏色概率分布直方圖及Kalman濾波算法重新找到原目標(biāo)的質(zhì)心位置， 有效解決了相似目標(biāo)干擾問(wèn)題， 提高了目標(biāo)跟蹤的穩(wěn)定性和可靠性.

4 實(shí)驗(yàn)結(jié)果分析

本文實(shí)驗(yàn)在win7 64位系統(tǒng)環(huán)境下， Menshift算法、 Camshift算法、 Kalman濾波算法、 幀間差分法及改進(jìn)的算法均在Matalb2013a下運(yùn)行， 分別對(duì)兩個(gè)Video中目標(biāo)實(shí)現(xiàn)跟蹤， 各Video分辨率均為320×240， 每秒15幀. Video1(共121幀)存在背景顏色干擾和遮擋、 Video2(共225幀， 選取右邊的人作為跟蹤目標(biāo))， 存在與目標(biāo)相似干擾且遮擋.

4.1 實(shí)驗(yàn)跟蹤結(jié)果

Meanshift算法、 Camshift算法、 TLD算法及改進(jìn)算法在實(shí)驗(yàn)過(guò)程中需選取各視頻第一幀， 用鼠標(biāo)選出所要跟蹤的目標(biāo)(用矩形框表示)， 雙擊矩形框即可開(kāi)始跟蹤， 而Kalman濾波算法及幀間差分法無(wú)須選取跟蹤對(duì)象， 自動(dòng)進(jìn)行跟蹤. 各算法跟蹤結(jié)果如圖 1～圖 3 所示.

圖 1 Video1跟蹤結(jié)果對(duì)比Fig.1 Comparison of Video1 tracking results

圖 2 Video2跟蹤結(jié)果對(duì)比Fig.2 Comparison of Video2 tracking results

圖 3 TID算法跟蹤結(jié)果對(duì)比Fig.3 Comparison of tracking results of TID algorithm

由圖 1 可知， 改進(jìn)算法可選取目標(biāo)部分特征進(jìn)行跟蹤， 背景顏色干擾和大面積遮擋均不影響跟蹤過(guò)程的穩(wěn)定性與可靠性， 而Meanshift算法由于背景顏色干擾， 跟蹤過(guò)程很不穩(wěn)定， 遇到樹(shù)木遮擋不能繼續(xù)跟蹤目標(biāo)， Camshift及Kalman濾波算法由于背景顏色等干擾完全不能進(jìn)行有效跟蹤， 而幀間差分法在遮擋的情況下能夠正常跟蹤且具有良好的穩(wěn)定性， 因此該算法在一定情況下可解決遮擋問(wèn)題； 由圖 2 可知， Video2中由于存在相似目標(biāo)干擾和遮擋情況， 改進(jìn)算法在第60幀時(shí)產(chǎn)生錯(cuò)誤跟蹤相似目標(biāo)， 第129幀時(shí)重新跟蹤原目標(biāo)， 因此改進(jìn)算法可自適應(yīng)調(diào)整繼續(xù)跟蹤原目標(biāo)， 而Meanshift、 Camshift算法由于環(huán)境等因素的影響均不能正常跟蹤目標(biāo)， Kalman濾波算法發(fā)生嚴(yán)重?cái)U(kuò)散現(xiàn)象， 幀間差分法不能有效檢測(cè)出目標(biāo)進(jìn)行跟蹤； 由圖 3 可知， TLD算法由于遮擋或相似干擾問(wèn)題均不能完整進(jìn)行跟蹤目標(biāo)， Video1跟蹤68幀后停止跟蹤， Video2在跟蹤187幀后結(jié)束跟蹤， 且跟蹤過(guò)程中目標(biāo)特征選取不當(dāng)直接影響跟蹤效果.

4.2 算法對(duì)比分析

改進(jìn)算法與Menshift算法、 Kalman濾波算法、 Camshift算法、 幀間差分法及TLD算法對(duì)比如下：

1) 與Meanshift算法相比， 改進(jìn)算法可選擇目標(biāo)部分特征進(jìn)行跟蹤， 不受背景顏色干擾和大面積遮擋的影響， 而Meanshift算法由于背景顏色干擾， 穩(wěn)定性一般， 雖一段時(shí)間內(nèi)能夠跟蹤目標(biāo)， 但遇到遮擋情況將不能繼續(xù)跟蹤目標(biāo)， 同時(shí)目標(biāo)特征選擇較小或相似目標(biāo)干擾很容易丟失目標(biāo).

2) 與 Camshift算法相比， 改進(jìn)算法將圖像從RGB空間轉(zhuǎn)換到Y(jié)UV空間， 提取其U分量計(jì)算顏色概率分布圖， 同時(shí)根據(jù)目標(biāo)質(zhì)心位置自適應(yīng)調(diào)整當(dāng)前搜索窗口， 能夠解決背景顏色或相似目標(biāo)干擾問(wèn)題， 而Camshift算法將圖像從RGB空間轉(zhuǎn)換到HSV空間， 提取其H分量計(jì)算顏色概率分布圖， 通過(guò)對(duì)每一幀搜索窗口內(nèi)像素進(jìn)行歸一化處理來(lái)調(diào)整窗口大小， 但在遮擋或相似目標(biāo)干擾情況下， 該算法不能較好地實(shí)現(xiàn)跟蹤.

3) 與Kalman濾波算法相比， 改進(jìn)算法將Meanshift算法計(jì)算值作為Kalman濾波算法的參數(shù)， 提高了Kalman濾波算法跟蹤精度， 使跟蹤過(guò)程更穩(wěn)定、 可靠， 彌補(bǔ)了Kalman濾波算法的不足， 而Kalman濾波算法受環(huán)境因素影響較大， 在實(shí)驗(yàn)過(guò)中雖在前幾幀可以跟蹤目標(biāo)， 但由于擴(kuò)散現(xiàn)象嚴(yán)重不能達(dá)到跟蹤目標(biāo)的效果.

4) 與幀間差分法相比， 改進(jìn)算法及幀間差分法都不受背景顏色干擾的影響， 能夠有效地跟蹤目標(biāo)且能很好地解決遮擋問(wèn)題. 但在相似干擾及遮擋的情況下， 改進(jìn)算法受環(huán)境等外界因素影響較小雖存在跟蹤相似目標(biāo)的現(xiàn)象， 但不影響跟蹤并具有良好的視覺(jué)效果， 而幀間差分法卻不能有效地檢測(cè)出目標(biāo)進(jìn)行跟蹤， 因此改進(jìn)算法具有一定的優(yōu)勢(shì).

5)與TLD算法相比， 改進(jìn)算法可選取目標(biāo)部分特征進(jìn)行跟蹤同時(shí)具有良好的穩(wěn)定性， 可有效地解決遮擋及相似干擾問(wèn)題， 而TLD算法雖對(duì)目標(biāo)進(jìn)行不斷檢測(cè)、 學(xué)習(xí)， 但遇到遮擋及相似目標(biāo)干擾等情況會(huì)終止運(yùn)行停止跟蹤， 且目標(biāo)特征選取不當(dāng)直接影響跟蹤過(guò)程的穩(wěn)定性.

5 結(jié) 語(yǔ)

以上幾種算法比較表明， 改進(jìn)算法將具有更廣泛的應(yīng)用性. 在背景較復(fù)雜情況下， 改進(jìn)算法仍能夠繼續(xù)跟蹤目標(biāo)， 并根據(jù)目標(biāo)質(zhì)心位置及前一幀搜索窗口邊界來(lái)確定當(dāng)前幀搜索窗口， 使其與目標(biāo)更加匹配， 減小了環(huán)境等因素對(duì)算法的影響， 可有效解決大面積遮擋及相似干擾問(wèn)題， 并可根據(jù)目標(biāo)尺度及狀態(tài)選取部分特征進(jìn)行跟蹤， 且具有良好穩(wěn)定性. 但當(dāng)目標(biāo)被長(zhǎng)時(shí)間完全遮擋， 改進(jìn)算法會(huì)認(rèn)為跟蹤結(jié)束而不再繼續(xù)跟蹤目標(biāo)， 因此改進(jìn)算法仍有一定的改進(jìn)空間， 使跟蹤過(guò)程更加智能、 可靠. 未來(lái)仍需要更加智能的多目標(biāo)跟蹤跟蹤， 需要更多的學(xué)者融合各方面知識(shí)研究能夠自主識(shí)別、 自主判斷、 自主跟蹤的智能跟蹤算法.

[1]Li Jian, Chen Haifeng, Li Gang, et al. Salient object detection based on meanshift filtering and fusion of colour information[J]. IET Image Processing, 2015, 9(11)： 977-985.

[2]Huang Hai, Sheng Mingwei, Li Yueming, et al. Remote operated vehicle tether disturbances analysis and target tracking control[C]. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014： 103-108.

[3]Xiao Hanzhen, Li Zhijun, Yang Chenguang, et al. RGB-D sensor-based visual target detection and tracking for an intelligent wheelchair robot in indoors environments[J]. International Journal of Control, Automation and Systems, 2015, 13(3)： 521-529.

[4]Zhou Zhiyu, Wu Dichong, Peng Xiaolong, et al. Object Tracking Based on CamShift with Multi-feature Fusion[J]. Journal of Software, 2014, 9(1)： 147-153.

[5]Zhou Zhiping, Zhou Mingzhu, Shi Xiaofeng. Target tracking based on foreground probability[J]. Multimedia Tools and Applications, 2016, 75(6)： 3145-3160.

[6]Xiu Chunbo, Wei Shian, Wan Rongfeng, et al. Cam shift tracking method based on target decomposition[J]. Mathematical Problems in Engineering, 2015： 1-20.

[7]Yan Zouguo, Ling Weiguo, Lü Haidong. A target tracking algorithm based on improved camshift and UKF[J]. Journal of Software Engineering and Applications, 2014, 7(13)： 1065-1073.

[8]Xia Jingxin, Rao Wenming, Huang Wei, et al. Automatic multi-vehicle tracking using video cameras： an improved CAMShift approach[J]. KSCE Journal of Civil Engineering, 2013, 17(6)： 1462-1470.

[9]Kalal Z, Mikolajczyk K, Matas J. Tracking-learning-detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7)： 1409-422.

[10]Du Kai, Ju Yongfeng, Jin Yinli, et al. Meanshift tracking algorithm with adaptive block color histogram[C]. International Conference on Consumer Electronics, Communications and Networks, 2012： 2692-2695.

[11]Chi Jiannan, Qian Chenfei, Zhang Pengyu, et al. A novel ELM based adaptive Kalman filter tracking algorithm[J]. Neurocomputing, 2014, 128： 42-49.

[12]Moussakhani B, Fl?m J T, Ramstad T A, et al. On change detection in a Kalman filter based tracking problem[J]. Signal Processing, 2014, 55： 268-276.

An Improved Meanshift Algorithm for Target Tracking

ZHU Jia， LI Hua

(College of Information Engineering, Taiyuan University of Technology, Jinzhong 030600， China)

Aiming at the problem of occlusion and similar interference, a new improved algorithm based on the Meanshift algorithm was proposed. The algorithm effectively combined the Meanshift algorithm with the Kalman filtering algorithm to accurately determine the location of the target centroid. According to the target centroid position and the front frame search window boundary, the current search window boundary is adjusted adaptively to match the target position. In this way，the tracking results are more accurate and reliable, and the influence of the environment and other factors on the algorithm are also reduced. Through the experimental analysis, the improved algorithm which has good stability and adaptability can effectively solve the problem of large area occlusion and similar interference.

target tracking; Meanshift algorithm; Kalman algorithm

1673-3193(2016)06-0633-05

2016-04-22

山西省自然科學(xué)基金資助項(xiàng)目(2014011019-1)

朱 鉀(1991-)， 男， 碩士生， 主要從事無(wú)線傳感器目標(biāo)跟蹤的研究.

TP391

A

10.3969/j.issn.1673-3193.2016.06.014