劉振宇,張百穎

(沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院,遼寧 沈陽 110870)

基于Cam-shift的預(yù)測跟蹤方法分析與改進

劉振宇,張百穎

(沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院,遼寧 沈陽 110870)

為了在有遮擋等因素干擾的復(fù)雜背景下很好的完成移動目標的位置預(yù)測跟蹤,研究了Kalman濾波與Cam-shift算法結(jié)合的方法.Kalman濾波可以較精準地完成移動目標的位置預(yù)測,與Cam-shift算法結(jié)合可以很好的完成跟蹤.在此基礎(chǔ)上,提出了一種線性預(yù)測與Cam-shift算法結(jié)合的目標預(yù)測跟蹤方法,即將線性預(yù)測方法代替Kalman濾波完成預(yù)測估計,并將預(yù)測估計結(jié)果代入Cam-shift算法中進行跟蹤.實驗表明該方法既可以保證遮擋過程中追蹤的準確性,又能減少迭代時間,能夠更好地滿足實時性的要求.

Cam-shift;Kalman濾波;線性預(yù)測;移動目標跟蹤;位置預(yù)測

0 引言

移動目標軌跡的跟蹤和預(yù)測是人工智能研究領(lǐng)域不可缺少的一部分,是機器視覺、目標跟蹤檢測的關(guān)鍵技術(shù).不同的應(yīng)用背景,有不同的跟蹤方法:L-K(Lucas&Kanade)光流法和H-S (Horn&Schunck)光流法[1]不需考慮背景信息,通過給像素點賦予速度矢量,根據(jù)目標與背景速度矢量的差異追蹤目標,但要求相鄰幀之間亮度恒定;圖割算法[2]是將目標跟蹤問題映射到能量函數(shù)中,優(yōu)化求解出目標區(qū)域,計算復(fù)雜;Kass提出的Snake模型算法[3-4]是基于輪廓邊緣特征的跟蹤方法,其能量利用最小,但輪廓初始化復(fù)雜;董春利[5]等人通過將粒子濾波和GVF-Snake的結(jié)合,提出的自適應(yīng)非線性濾波算法,對運動和變形目標進行跟蹤,但效率較低;而Yizong Cheng[6]提出的Mean-shift算法是基于顏色特征的密度梯度無參估計算法,其形式簡單,易于操作,但沒有實時更新搜索窗口的功能,移動目標尺度變化快,易造成目標跟蹤丟失;Bradski在Mean-shift算法的基礎(chǔ)上提出的Cam-shift算法[7],可以自動實時地調(diào)整搜索窗口的大小,并且保留了Mean-shift算法的優(yōu)點,但移動目標的顏色特征不明顯或有遮擋等因素干擾時,會導(dǎo)致跟蹤失敗.

本文從Cam-shift算法分析出發(fā),結(jié)合Kalman濾波進行移動目標的識別與估計,很好地降低了在復(fù)雜背景下跟丟目標的概率,并利用物理學(xué)運動相關(guān)知識,提出了線性預(yù)測與Cam-shift算法相結(jié)合的方法,改進的方法既能保證在復(fù)雜背景下的成功跟蹤,又能減少計算時間,具有更好的實時性.

1 Cam-shift算法原理分析

Cam-shift算法是在Mean-shift算法的基礎(chǔ)上提出的改進算法[8],該方法對連續(xù)圖像序列的每一幀都做Mean-shift算法處理,當(dāng)前幀的處理結(jié)果作為下一幀Mean-shift算法搜索窗口的初始值,依次進行迭代運算,完成跟蹤.具體實現(xiàn)步驟如下:

1) 顏色模型的建立

Cam-shift算法采用顏色模型做特征進行目標跟蹤.RGB顏色模型產(chǎn)生或顯示色彩,HSV顏色模型能反應(yīng)顏色的本質(zhì)特征,它可以將色度,飽和度,明度分開處理,提高算法的穩(wěn)定性.因此,選擇HSV顏色空間H分量作為跟蹤目標的特征,建立顏色直方圖,這樣會比完整的RGB和HSV模型計算量減少很多.RGB與HSV模型的轉(zhuǎn)換公式如下:

V=max(R,G,B)

(1)

S=(V-min(R,G,B))/V

(2)

(3)

2) 反向投影圖的生成

將生成的H分量信息直方圖轉(zhuǎn)換成顏色的概率分布圖像,即將像素值為255的點概率對應(yīng)設(shè)置為1,將像素值為0的點的概率設(shè)置為0,這樣得到的顏色概率投影圖像即為原顏色直方圖的反向投影圖像.

3) 利用Mean-shift算法尋找質(zhì)心

初始化搜索窗口,設(shè)I(x,y)為像素點(x,y)反向投影圖的對應(yīng)像素點,通過計算搜索窗口的零階矩和一階矩得到搜索窗口的質(zhì)心,將搜索窗口的中心移到質(zhì)心位置,并根據(jù)零階矩M00更新窗口大小.具體公式如下[9]:

(4)

搜索窗口的質(zhì)心為:

(5)

更新窗口大小為:

(6)

當(dāng)窗口移動到質(zhì)心的距離大于預(yù)設(shè)值時,重新計算窗口質(zhì)心的位置,直至滿足收斂條件,再進行下一幀的追蹤計算,依次循環(huán),完成整個追蹤過程.

圖1顯示了利用Cam-shift算法在復(fù)雜背景下移動目標序列的的跟蹤結(jié)果,a圖為第10,20,30,40幀序列正常無遮擋情況下的跟蹤結(jié)果,b圖為第50,60,70,80幀序列在有遮擋情況下的跟蹤結(jié)果.容易看出,Cam-shift算法可以自動的實時的調(diào)整搜索窗口的大小,在無干擾的背景下可以準確地跟蹤目標,但當(dāng)遇到遮擋等因素影響時,很容易由于顏色特征不明顯,迭代過程繁雜而造成計算失誤,進而導(dǎo)致跟蹤失敗.因此,針對這一缺點引入估計器預(yù)測移動目標的位置,減少迭代次數(shù),進而減少失誤率.

圖1 傳統(tǒng)Cam-shift算法跟蹤結(jié)果

2 Cam-shift改進算法的研究

2.1 Kalman與Cam-shift算法結(jié)合

2.1.1 Kalman濾波

卡爾曼濾波器是通過最小均方誤差準則對移動目標實現(xiàn)的預(yù)測估計方法[10],它是通過狀態(tài)方程和觀測方程的關(guān)系進行建模來構(gòu)建一個離散的時間線性系統(tǒng).系統(tǒng)的狀態(tài)方程和觀測方程[11]分別為:

X(k)=AX(k-1)+BU(k)+W(k)

(7)

Z(k)=HX(k)+V(k)

(8)

其中,X(k)為K時刻系統(tǒng)的狀態(tài)向量,可定義為:

X(k)=[x(k)y(k)v(k)u(k)]T

(9)

x(k)與y(k)分別表示目標中心在x,y軸的坐標分量;v(k),u(k)分別表示目標中心在x,y軸的速度;U(k)Z(k)分別為K時刻系統(tǒng)的控制量和觀測向量,xz(k)與yz(k)分別代表目標中心在x,y軸的坐標值.

Kalman濾波算法[12]為:

(10)

其中,X(k|k-1)為下一狀態(tài)的預(yù)測結(jié)果,X(k-1|k-1)為系統(tǒng)當(dāng)前狀態(tài)的最優(yōu)估計,P(k|k-1)為X(k|k-1)的誤差協(xié)方差,X(k|k)為優(yōu)估計值,K(k)為卡爾曼增益.完成上述過程后返回(10)即進行k+1狀態(tài)的預(yù)測,依次循環(huán)即可完成完整的過程.

本文中,Kalman系統(tǒng)的狀態(tài)方程和觀測方程構(gòu)建時根據(jù)隨機加速運動方程,可得到:

由此,Kalman濾波器建模完成.

2.1.2 Kalman與Cam-shift算法結(jié)合實現(xiàn)過程

由于應(yīng)用Kalman濾波算法進行預(yù)測跟蹤時是基于像素的全局搜索,計算量大,當(dāng)應(yīng)用于復(fù)雜背景時,全局搜索抗干擾能力弱,容易丟失跟蹤目標.本文根據(jù)Kalman算法和Cam-shift算法的優(yōu)缺點,將其進行結(jié)合,即可將全局搜素轉(zhuǎn)變成局部搜索,從而減少計算量,提高準確率.

具體方法如下:

1)首先,設(shè)置追蹤目標的初始值,例如速度,位置等;

2)計算下一幀圖像的方差,代入公式求出此時的目標狀態(tài),利用Kalman相關(guān)公式預(yù)測協(xié)方差和狀態(tài)的更新,估計出追蹤目標在下一幀最可能出現(xiàn)的位置和運動速度;

3)將上述結(jié)果導(dǎo)入Cam-shift算法中,在預(yù)測估計的目標位置附近,進行局部的目標搜索及匹配,將搜索后的窗口中心位置作為Kalman的測量值;

4)更新跟蹤窗口;

5)更新目標的協(xié)方差矩陣和目標狀態(tài)方程,重復(fù)步驟(2),直至結(jié)束.

2.2 線性預(yù)測與Cam-shift算法結(jié)合

2.2.1 線性預(yù)測

從物理學(xué)可知,當(dāng)描述系統(tǒng)中的目標物體運動狀態(tài)方程為線性方程時,給定目標運動狀態(tài)的初始條件,即可預(yù)見該目標之后的任意時刻的運動狀態(tài).而從運動學(xué)角度分析,曲線運動可以看作是由短時間的勻速直線運動構(gòu)成的,當(dāng)移動物體的速度及運動方向和前一時刻保持大體相同時,可以看作是勻速直線運動.特別的,當(dāng)目標的移動速度平緩,由于每一幀的時間間隔很短,可以將每幀間的物體運動看作是勻速直線運動.

線性預(yù)測方法的計算過程為:已知目標的初始位置,根據(jù)目標的當(dāng)前位置坐標與初始位置坐標,計算出運動速度與方向的坐標偏移差,然后根據(jù)所得的坐標偏移差,計算出下一幀的期望位置,即假設(shè)目標在上一幀的中心位置坐標為(xi-1,yi-1),當(dāng)前幀的中心位置坐標為(xi,yi),則坐標偏移差可近似為(Δx,Δy)=(xi-xi-1,yi-yi-1),由于兩幀間的移動目標移動時間很短,可以近似看成是勻速直線運動,所以可以根據(jù)運動學(xué)公式,得到下一幀中目標的期望位置為:(xi+1,yi+1)=(xi+Δx,yi+Δy).

圖2 跟蹤流程圖

2.2.2 線性預(yù)測與Cam-shift算法結(jié)合的實現(xiàn)

本文根據(jù)線性預(yù)測的思想,將其與Cam-shift算法結(jié)合,將得到的目標期望位置作為搜索窗口的中心,代入Cam-shift算法中,進而在局部迭代收斂出真實的移動目標質(zhì)心,更新新的中心位置坐標,依次循環(huán),很好的完成追蹤過程.

跟蹤流程圖如圖2所示:

3 實驗結(jié)果與分析

本文通過對Kalman與Cam-shift算法結(jié)合與上述的線性預(yù)測與Cam-shift算法結(jié)合的對比分析,來驗證上述線性預(yù)測與Cam-shift算法結(jié)合的有效性和實時性.本文采用復(fù)雜背景下有遮擋過程的人直立行走序列圖像(大小為360*640)進行跟蹤實驗,跟蹤窗口為矩形窗口,初始窗口由背景差分法檢測出第一幀移動目標的位置確定,分別選取第30,60,90,130幀跟蹤序列圖像以示說明.

下圖為Kalman與Cam-shift算法結(jié)合和線性預(yù)測與Cam-shift算法結(jié)合的跟蹤結(jié)果:

從圖3可以看出,Kalman與Cam-shift算法結(jié)合的方法和線性預(yù)測與Cam-shift算法結(jié)合的方法均可以自動實時的更新窗口大小,當(dāng)有遮擋過程時,這兩種改進的方法與傳統(tǒng)的Cam-shift方法比較,受遮擋因素影響較小,均能保證追蹤的準確性,很好的完成跟蹤.

本文又在復(fù)雜背景下進行了50次跟蹤實驗,分析比較了三種算法的跟蹤正確率,從表1中可以直觀地看出,本文提出的線性預(yù)測與Cam-shift結(jié)合算法和Kalman與Cam-shift結(jié)合算法跟蹤正確率比傳統(tǒng)的Cam-shift算法高很多.通過跟蹤連續(xù)30幀無遮擋干擾情況的序列圖像,分析比較了傳統(tǒng)Cam-shift算法與改進算法的迭代次數(shù)與消耗時間,可以看出,本文提出的線性預(yù)測與Cam-shift結(jié)合的算法與Kalman與Cam-shift結(jié)合的算法的總迭代次數(shù)相差很少,比傳統(tǒng)的Cam-shift算法減少一半左右;而本文提出的線性預(yù)測與Cam-shift結(jié)合的算法單次迭代平均耗時與傳統(tǒng)的Cam-shift算法相差很少,但由于迭代次數(shù)是傳統(tǒng)Cam-shift算法的一半,所以總耗時比傳統(tǒng)的Cam-shift算法少很多.而Kalman與Cam-shift結(jié)合的算法構(gòu)建的預(yù)測系統(tǒng)復(fù)雜,單次迭代平均耗時較長,所以總耗時高于本文提出的算法的花費時間,但仍然低于傳統(tǒng)Cam-shift算法的耗用時間.因此,本文提出的算法既能滿足遮擋等干擾的準確追蹤,又能保證更好的實時性.

圖3 改進的算法跟蹤結(jié)果

跟蹤正確率總迭代次數(shù)總耗時單次迭代平均耗時傳統(tǒng)Cam-shift算法84%4568.5ms1.52msKalman與Cam-shift結(jié)合100%2141.7ms1.98ms線性預(yù)測與Cam-shift結(jié)合100%2335.4ms1.54ms

4 結(jié)論

由于傳統(tǒng)的Cam-shift算法在復(fù)雜背景下存在受遮擋因素影響較大、跟蹤不精準的可能性,本文從研究Kalman與Cam-shift算法結(jié)合的方法中受到啟發(fā),用線性預(yù)測代替Kalman濾波簡化了線性估計系統(tǒng)的構(gòu)成,提出了一種線性預(yù)測與Cam-shift算法結(jié)合的預(yù)測跟蹤算法.跟蹤實驗表明,該算法既能滿足移動目標在遮擋過程中的成功跟蹤,又能減少單次迭代時間,進而提高跟蹤效率,更好的滿足了實時性的要求.

[1] Amiaz T,Kiryat N.Dense discontinuous optical flow via contour-based segment-ation[C].Proceedings of IEEE International Conference on Image Processing,2006,3:1264-1267.

[2] Suga A,Fukuda K,Takiguchi T,et al.Object recognition and segmentation using SIFT a-nd Graph Cuts[C].Proceedings of the 19th International Conference on Pattern Reco-gnition,2008:1-4.

[3] 陳立潮,牛玉梅,潘理虎,等.Snake模型的研究進展[J].計算機應(yīng)用研究,2014,31(7):1931-1936.

[4] Michael Kass,Andrew Witkin D T.Snake:Active contour models[J].Internatio-nal Journal ofComputer Vision,1988,1(4):321-331.

[5] 董春利,董育寧,劉杰.基于粒子濾波和GVF-Snake的目標跟蹤算法[J].儀器儀表學(xué)報:2009,30(4):828-833.

[6] Cheng Y Z.MeanShift,model seeking,a-nd clustering.IEEE Transactions on Pattern Analysis and Machine[J].Intelligence,1995,17(8):790-799.

[7] 閆鈞華,陳少華,艾淑芳.基于 Kalman 預(yù)測器的改進的 CAMShift 目標跟蹤[J].中國慣性技術(shù)學(xué)報,2014,22(4):536-542.

[8] Zhang R,Zhang S,Yu S.Moving objects detection method based on brightness d-istortion and chromaticity distortion [J].Consumer Electronics,IEEE Transactions on,2014,53(3):1177-1185

[9] 王澤楷,吳黎明,蔡文.基于Camshift改進算法的視頻目標跟蹤方法[J].自動化與信息工程,2014,35(1):27-31

[10] Liu R M,Li X L,Han L,et al.Track infrared point targets based on projection coefficient templat-es and non-linear correlation combined with Kalman prediction[J].Infrared Physi-cs & Technology,2013,57(3):68-75.

[11] 袁勝智,謝曉芳,李洪周.一種基于Kalman-mean shift 的自適應(yīng)跟蹤算法[J].激光與紅外,2009,39(5):558-561

[12] 黃曉麗,楊國為,吳少龍.一種改進的Cams-hift和Kalman相結(jié)合的運動目標跟蹤算法[J].工業(yè)控制計算機,2016,29(1):80-81.

(責(zé)任編輯李超)

AnalysisandImprovementofPredictiveTrackingAlgorithmbasedonCam-shiftMethod

LIU Zhen-yu,ZHANG Bai-ying

(SchoolofInformationScienceandEngineering,ShenyangUniversityofTechnology,Shenyang110870,China)

In order to finish the position tracking of the moving target accurately in complex backgrounds which have occlusion interference,the article has studied Kalman filter combined with Cam-shift algorithm.Using Kalman filter could make the prediction of moving target more accurate and speed,when combined with the Cam-shift algorithm could achieve good tracking.On this basis,then proposed a new tracking algorithm based on linear prediction and Cam-shift algorithm,the linear prediction method is used as filtering estimation to instead of Kalman filter,and the prediction results would be substituted into Cam-shift estimation algorithm for tracking.The experimental results show that the method can not only ensure the accuracy of tracking,but also reduce the iteration time.

cam-shift;kalman filter;linear prediction;moving target tracking;position prediction

2017-02-20

遼寧省自然科學(xué)基金(2015020162)

劉振宇(1973-)，男，遼寧瓦房店人，博士，副教授，從事視覺伺服、模式識別的研究.

TN 912

A

1000-5846(2017)03-0234-07