改進的Meanshift運動目標跟蹤算法

張　英，車　進，牟曉凱，白雪冰

(寧夏大學(xué) 物理電氣信息學(xué)院，寧夏 銀川 750021)

?

改進的Meanshift運動目標跟蹤算法

張英，車進，牟曉凱，白雪冰

(寧夏大學(xué) 物理電氣信息學(xué)院，寧夏 銀川 750021)

Meanshift算法在對快速運動的目標進行跟蹤時容易丟失目標，并且在目標被遮擋時，也容易造成跟蹤失敗，跟蹤的過程中跟蹤框不能隨著運動目標的大小變化而變化。提出一種基于Meanshift運動目標跟蹤算法的改進算法。該算法基本思想是采用改進的三幀差分法對運動目標區(qū)域進行提取，求得跟蹤框輪廓，同時用Meanshift算法對運動目標進行跟蹤，獲得目標最大概率區(qū)域，將該區(qū)域中心作為跟蹤框的中心。跟蹤過程中通過巴氏系數(shù)判斷是否目標被遮擋，若被遮擋則調(diào)用Kalman濾波進行預(yù)測跟蹤。實驗結(jié)果表明，該算法能夠快速、準確地跟蹤目標。

三幀差分；Meanshift；運動目標跟蹤；Kalman濾波

智能視頻監(jiān)控系統(tǒng)如今被廣泛應(yīng)用，它是計算機視覺領(lǐng)域中近些年來新興起的一個研究方向。它主要是利用計算機視覺技術(shù)對采集到的視頻圖像信號進行處理、分析和理解，得到關(guān)鍵信息從而對視頻監(jiān)控系統(tǒng)進行控制，提高視頻監(jiān)控系統(tǒng)數(shù)字化水平。跟蹤運動目標可以獲得運動目標的運動狀態(tài)和軌跡，同時為更高級別的處理提供可靠的數(shù)據(jù)。由于噪聲的存在、天氣的變化、目標的無規(guī)則運動等都會給準確跟蹤帶來很多問題。對運動目標跟蹤的完整性和準確性主要取決于對跟蹤算法的選取。2002年Dorin Comaniciu采用Meanshift算法跟蹤運動目標，縮短了跟蹤時間，計算難度也降低了。Meanshift算法主要是基于無參數(shù)密度估計對運動目標進行跟蹤，該算法通過計算目標模型和候選模型的核密度直方圖來比較它們的相似程度，運動目標形狀的改變對顏色直方圖影響不大[1]。因此，Meanshift算法對運動目標尺度變化有較好的適應(yīng)性[2]。但是當運動目標運動速度過快或目標被遮擋的情況，Meanshift算法就沒有辦法準確地跟蹤運動目標，往往容易跟丟，這就需要跟蹤算法必須具有預(yù)測能力。本文提出了一種基于Meanshift算法的目標跟蹤改進算法，該算法結(jié)合了三幀差分檢測運動目標和Kalman濾波器對Meanshift算法進行改進，改進算法的優(yōu)點在于可以使跟蹤框自適應(yīng)變化，并且當目標被遮擋之后也能很準確地跟蹤運動目標。

1　三幀差分算法原理

傳統(tǒng)幀間差分或者三幀差分得到的運動目標都存在一定的缺點，獲得的運動目標不完整，特別是對于緩慢運動的目標會存在大量的空洞。本文采用一種改進的三幀差分算法確定運動區(qū)域[3]。該算法首先用Surendra背景提取算法提取有效背景，采用背景選擇性更新方法對背景進行實時更新；用連續(xù)的三幀圖像分別與背景進行差分，采用HSV顏色空間陰影去除方法對三個差分結(jié)果進行陰影去除，然后進行三幀差分，將差分結(jié)果進行“與”運算；最后用“與”運算得到的結(jié)果與中間幀背景減除的結(jié)果進行“或”運算，則可以得到運動區(qū)域。如圖1所示。

圖1　三幀差分運動目標檢測結(jié)果

2　Meanshift算法

2.1Meanshift算法原理

從d維空間Rd中取出n個采樣點xi，其中i=1,…,n，在這里能夠給出在參考點x處的Meanshift向量的基本形式為

(1)

從式(1)中能夠看出(xi-x)是樣本點xi相對于確定的參考點x的偏移量大小，Meanshift算法的基本向量Mh(x)的含義是在多維空間中，首先選擇一個參考點x，在事先確定區(qū)域內(nèi)對樣本點xi與參考點的偏移量先進行求和然后再求平均值[4]?？梢钥闯?，所有區(qū)域內(nèi)的樣本點xi是從概率密度函數(shù)f(x)中采樣得到的，根據(jù)概率統(tǒng)計學(xué)可知如果概率密度梯度值不等于零，則函數(shù)梯度指向概率密度增加最大的那個方向，sh區(qū)域中的采樣樣本幾乎都落在沿著概率密度梯度的方向。顯然，相應(yīng)的Meanshift向量Mh(x)就是指向概率密度梯度最大的方向。

如圖2所示，大圓的范圍表示為sh，圖中箭頭方向表示參考點x的偏移向量，空心圓為落入?yún)^(qū)域sh中的n個采樣點xi∈sh，而實心圓就是Meanshift基本向量的參考點x。很顯然，基本向量Mh(x)的結(jié)果就是使參考點向采樣點概率密度最大的方向進行偏移。

圖2　均值偏移示意圖

從式(1)中能夠看出，在區(qū)域sh(x)中所得到的采樣點xi，無論確定的參考點x離采樣點有多遠，對Meanshift基本向量Mh(x)的計算結(jié)果的影響是一致的。通過仿真可以看出這樣的形式會使得參考點的收斂速度變得很慢。通常情況下，參考點x附近的采樣點對基本向量的估計結(jié)果起到的作用就越大，因此對距離參考點不同遠近的采樣點賦予了不同的權(quán)值，常用的Meanshift擴展形式可以寫為

(2)

2.2Meanshift跟蹤算法

(3)

式中：δ為克羅內(nèi)克函數(shù)[6]。k(x)是核函數(shù)的輪廓函數(shù)，采用該函數(shù)給不同的像素點賦權(quán)值。對中心點附近的像素點賦予的權(quán)值比較大，離中心點遠的像素點所得權(quán)值就會比較小。通過該函數(shù)可以使得密度估計更加穩(wěn)定可靠。C的計算表達式為

(4)

(5)

通過式(5)可以看到Ch與y值之間并沒有什么聯(lián)系，根本原因是由于像素位置xi的形式是規(guī)則化網(wǎng)格，因此確定核密度和尺度h后，Ch的大小也就被確定了[7]。

(6)

y0為當前視頻幀圖像的初始位置，式(6)在y0處進行泰勒展開可以得到

(7)

通過上式可以看出經(jīng)過泰勒展開后，y值只受等式右邊第二項的影響。這樣看來可以利用Meanshift算法對其進行迭代，在區(qū)域中得到概率密度估計最大值，通過該值確定目標的最新位置y1[8]。完成迭代以后，y1的值就是最后匹配的最佳位置。

3　Kalman濾波器

Meanshift算法主要是在目標中心領(lǐng)域附近搜索出相似度最大的運動目標，如果目標運動太快，或是目標被障礙物遮擋，都會使得跟蹤的結(jié)果有很大的誤差。因此本文結(jié)合Kalman 濾波算法，該算法主要具有預(yù)測當前幀狀態(tài)向量的功能，它是根據(jù)以往幀觀測向量進行預(yù)測的，這樣就可以得到運動目標的預(yù)測位置目標。Kalman濾波器主要是運用最小均方誤差估計方法對動態(tài)系統(tǒng)的狀態(tài)序列進行計算，由此可以得到下一幀中運動目標區(qū)域的中心位置信息，與此同時替換當前幀運動目標區(qū)域的位置[9]。假設(shè)目標位置在x軸以及y軸的狀態(tài)向量表示為X=(xc,yc)T，預(yù)測目標的位置在x軸以及y軸的測量矢量表示為Z=[xc,yc]T。首先初始化狀態(tài)向量Xi，接著用該狀態(tài)向量作為Kalman濾波器的觀測值來預(yù)測相鄰幀的值。

Kalman濾波器的狀態(tài)方程和測量方程分別表示為

Xi+1=AXi+Wi，

Zi=HXi+Vi

(8)

式中：A為狀態(tài)轉(zhuǎn)移矩陣；H為測量矩陣；Wi,Vi分別表示狀態(tài)噪聲向量和測量噪聲向量，假定該噪聲都是獨立的白噪聲，對應(yīng)的方差分別為Q,R。

狀態(tài)向量預(yù)測方程的表達式為

(9)

狀態(tài)向量協(xié)方差矩陣預(yù)測方程的表達式為

(10)

狀態(tài)向量更新方程表達式為

(11)

狀態(tài)向量協(xié)方差更新方程表達式為

(12)

Kalman加權(quán)矩陣或增益矩陣表達式為

(13)

4　基于Meanshift的改進跟蹤算法

通常情況下，Meanshift算法是一種有效的跟蹤算法，很大程度上能夠保證很好的跟蹤效果[10]。Meanshift算法沒有過多的考慮目標的實際運動情況，而僅僅是用偏移量也就是最大概率梯度的方向來確定目標位置，這樣就忽略了實際運動目標的運動速度和運動方向信息。Meanshift算法的缺點在于跟蹤框?qū)τ谶\動速度過快的目標跟蹤效果不好，甚至?xí)撾x實際目標。跟不上目標的主要原因是因為選取的初始值不正確，使得之后的迭代就出現(xiàn)更多的錯誤。在Meanshift算法中，對泰勒式展開的目的是使得巴氏系數(shù)最大化，其中只有當y1值與y0值相差不大的時候泰勒展開有作用。這個時候，如果將當前幀的初始值定為前一幀目標的中心坐標，當目標運動過快時就不能準備跟蹤目標。并且在目標被遮擋時，也容易造成跟蹤失敗，跟蹤過程中窗口大小無法自適應(yīng)變化。

針對以上問題，本文提出一種基于Meanshift算法的改進算法。采用改進的三幀差分法對運動目標區(qū)域進行提取，求得跟蹤框輪廓，同時用Meanshift算法對運動目標進行跟蹤，獲得目標最大概率區(qū)域，將該區(qū)域中心作為跟蹤框的中心。跟蹤過程中通過巴氏系數(shù)判斷是否目標被遮擋，若被遮擋則調(diào)用Kalman濾波進行預(yù)測跟蹤。改進算法的優(yōu)點在于可以使跟蹤框自適應(yīng)變化，并且當目標被遮擋之后也能很準確地跟蹤運動目標。算法流程圖如圖3所示。

圖3　本文算法流程圖

1)首先要獲得前景區(qū)域即運動目標區(qū)域。采用三幀差分對運動區(qū)域進行提取，然后將運動區(qū)域用跟蹤框進行標注。

2)其次利用Meanshift算法進行迭代，由于它是重心移動，即向反向投影圖中概率大的地方移動，所以會得到運動目標的中心點位置。

3)將獲得的運動目標中心點也就是最大概率點作為跟蹤框的中心，這樣就實現(xiàn)了準確的跟蹤，同時實現(xiàn)了跟蹤框的實時變化。

4)在每一幀圖像中，都利用巴氏系數(shù)(式(1))判斷運動目標是否被遮擋，如果巴氏系數(shù)大于閾值T(經(jīng)過多次實驗，取T=0.4效果最佳)，則不調(diào)用Kalman預(yù)測算法；否則調(diào)用Kalman預(yù)測算法對運動目標進行預(yù)測跟蹤。

5　實驗結(jié)果分析

圖4是傳統(tǒng)Meanshift算法的跟蹤結(jié)果。該視頻的運動目標的大小由大變小， 傳統(tǒng)的Meanshift算法跟蹤框不能實現(xiàn)自適應(yīng)變化，所以整個過程中跟蹤框不能隨目標的大小而變化；并且當運動目標被遮擋時，第131幀圖像中運動軌跡發(fā)生了錯誤的變化。圖5是本文算法的跟蹤結(jié)果。結(jié)合了三幀差分和Kalman預(yù)測跟蹤，實現(xiàn)了跟蹤框的自適應(yīng)變化，并且遮擋之后還能準確跟蹤。

圖4　傳統(tǒng)的Meanshift算法跟蹤結(jié)果

圖5　本文算法的跟蹤結(jié)果

6　結(jié)論

本文提出一種基于Meanshift算法的改進算法。采用改進的三幀差分法對運動目標區(qū)域進行提取，該方法不僅保證了系統(tǒng)的檢測效率而且還可以完整地提取出待跟蹤的運動目標區(qū)域，從而求得跟蹤框輪廓。同時用Meanshift算法對運動目標進行跟蹤，獲得運動目標信息即最大概率區(qū)域，將該區(qū)域中心作為跟蹤框的中心，這樣實現(xiàn)了跟蹤框的自適應(yīng)變化。跟蹤過程中通過對巴氏系數(shù)的計算，判斷目標是否被遮擋，若被遮擋則啟用Kalman對下一幀目標位置進行預(yù)測。實驗結(jié)果證明，本文將Meanshift算法結(jié)合三幀差分和Kalman濾波算法可以對運動目標進行實時準確跟蹤。

[1]楊紅霞，杭亦文，劉旭. 基于Meanshift與Kalman的視頻目標跟蹤算法[J]. 武漢理工大學(xué)學(xué)報(信息與管理工程版)，2012，34(2)：147-150.

[2]姚放吾，許辰銘. 基于目標質(zhì)心的Meanshift跟蹤算法[J]. 計算機技術(shù)與發(fā)展，2012，22(6)：104-110.[3]張英，車進，周鵬. 一種改進的三幀差分運動目標實時檢測算法[J].計算機測量與技術(shù)，2015，23(6)：2073-2075.

[4]許辰銘. 視頻圖像中的運動目標檢測與跟蹤[D].南京：南京郵電大學(xué)，2012.

[5]陳柱，李子印，朱明凌. 基于塊的Mean-shift 跟蹤算法[J].電視技術(shù)，2015，39(20)：6-10.

[6]HE J W， YANG Y Y. Multi-iterative tracking method using meanshift based on kalman filter[C]//Proc. 2014 IEEE International Conference on Signal Processing， Communications and Computing (ICSPCC).[S.l.]：IEEE，2014：22-27.

[7]YIN H P， CHAI Y， YANG S X， et al. Fast-moving target tracking based on mean-shift and frame-difference methods[J]. Systems engineering and electronics， 2011，22(4)：587-592.

[8]許慧芳，許亞軍. 智能視頻監(jiān)控系統(tǒng)中多攝像頭協(xié)同跟蹤算法[J].電視技術(shù)，2015，39(18)：86-90.

[9]CHU C， HWANG J. Fully unsupervised learning of camera link models for tracking humans across non-overlapping cameras[J].IEEE transaction on circuits and systems for video technology，2014，24(6)：979-994.

[10]AVED A J， HUA K A， GURAPPA V. An informatics-based approach to object tracking for distributed live video computing[J]. Multimedia tools and applications，2014，68(1)：111-133.

張英(1989— )，碩士，主研信號、圖像處理與模式識別；

車進(1973— )，博士，教授，碩士生導(dǎo)師，主要研究方向為圖像處理及智能視頻技術(shù)方向的研究，為本文通信作者；

牟曉凱(1990— )，碩士生，主研模式識別與圖像處理；

白雪冰(1991— )，碩士生，主研信號、圖像處理與模式識別。

責(zé)任編輯：閆雯雯

Improved meanshift moving tracking algorithm

ZHANG Ying， CHE Jin， MU Xiaokai， BAI Xuebing

(SchoolofPhysics&ElectricalInformationEngineering，NingxiaUniversity，Yinchuan750021，China)

When Meanshift algorithm tracks the fast-moving targets， it is easy to lose the target. And when the targets are blocked， it is likely to cause tracking failure. The tracking window size can not be adapted to change. An improved Meanshift target tracking algorithm is presented. The algorithm uses improved three-frame difference method to extract moving target area， and seek tracking frame outline. At the same time， Meanshift algorithm tracks the moving targets and obtains the target maximum probability region. Then the regional center can be a center of the tracking frame. During tracking process， Pap coefficient can determines whether the target is blocked. If target is blocked， then kalman filter can be called to forecast and track. Experimental results show that the algorithm is quick and accurate to track the target.

three-frame difference； Meanshift； moving target tracking； Kalman filter

TP391

ADOI： 10.16280/j.videoe.2016.10.020

國家自然科學(xué)基金項目(61162020)

2015-12-22

文獻引用格式：張英，車進，牟曉凱，等. 改進的Meanshift運動目標跟蹤算法[J].電視技術(shù)，2016，40(10)：97-100.

ZHANG Y， CHE J， MU X K，et al. Improved meanshift moving tracking algorithm[J]. Video engineering，2016，40(10):97-100.