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

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

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

?

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

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

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

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

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

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

1　三幀差分算法原理

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

圖1　三幀差分運動目標檢測結果

2　Meanshift算法

2.1Meanshift算法原理

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

(1)

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

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

圖2　均值偏移示意圖

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

(2)

2.2Meanshift跟蹤算法

(3)

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

(4)

(5)

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

(6)

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

(7)

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

3　Kalman濾波器

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

Kalman濾波器的狀態方程和測量方程分別表示為

Xi+1=AXi+Wi，

Zi=HXi+Vi

(8)

式中：A為狀態轉移矩陣；H為測量矩陣；Wi,Vi分別表示狀態噪聲向量和測量噪聲向量，假定該噪聲都是獨立的白噪聲，對應的方差分別為Q,R。

狀態向量預測方程的表達式為

(9)

狀態向量協方差矩陣預測方程的表達式為

(10)

狀態向量更新方程表達式為

(11)

狀態向量協方差更新方程表達式為

(12)

Kalman加權矩陣或增益矩陣表達式為

(13)

4　基于Meanshift的改進跟蹤算法

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

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

圖3　本文算法流程圖

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

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

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

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

5　實驗結果分析

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

圖4　傳統的Meanshift算法跟蹤結果

圖5　本文算法的跟蹤結果

6　結論

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

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

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

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

[5]陳柱，李子印，朱明凌. 基于塊的Mean-shift 跟蹤算法[J].電視技術，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]許慧芳，許亞軍. 智能視頻監控系統中多攝像頭協同跟蹤算法[J].電視技術，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— )，博士，教授，碩士生導師，主要研究方向為圖像處理及智能視頻技術方向的研究，為本文通信作者；

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

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

責任編輯：閆雯雯

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

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

2015-12-22

文獻引用格式：張英，車進，牟曉凱，等. 改進的Meanshift運動目標跟蹤算法[J].電視技術，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.