用于運(yùn)動(dòng)目標(biāo)跟蹤的改進(jìn)Camshift算法的研究

秦勇 商萌萌 趙曉紅 蓋建新

摘 要：Camshift是一種應(yīng)用顏色特性來(lái)對(duì)目標(biāo)實(shí)施跟蹤的算法，所以當(dāng)背景過(guò)于復(fù)雜、目標(biāo)被遮擋或做加速運(yùn)動(dòng)時(shí)很容易發(fā)生目標(biāo)跟丟的情況。針對(duì)以上缺點(diǎn)，提出首先采用幀間差分法自動(dòng)的選取搜索窗口，然后引入加權(quán)顏色概率直方圖排除相似背景顏色的干擾，最后采用Kalman濾波器預(yù)測(cè)和Camshift算法相結(jié)合的方法準(zhǔn)確跟蹤做加速運(yùn)動(dòng)的物體。實(shí)驗(yàn)表明，此方法能夠準(zhǔn)確定位做加速運(yùn)動(dòng)或被遮擋的目標(biāo)。

關(guān)鍵詞：Camshift；幀間差分；加速運(yùn)動(dòng)；Kalman濾波

DOI：10.15938/j.jhust.2018.03.006

中圖分類號(hào)： TP391

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

文章編號(hào)： 1007-2683（2018）03-0034-05

Research on Improving Camshift Algorithm about Target Tracking

QIN Yong， SHANG Meng-meng， ZHAO Xiao-hong， GAI Jian-xin

（School of Measurement and Control Technology and Communications Engineering，

Harbin University of Science and Technology， Harbin 150080，China）

Abstract：

The target is easily lost by using Camshift when the target is blocked or accelerated in complex background. The reason for this is Camshift is an algorithm that uses color characteristics to track the target. For solving above shortcomings， the improving Camshit algorithm is proposed in this paper. Firstly， the search window is automatically selected using frame difference method. Then， the weighted color histogram is introduced to eliminate the interference of similar background colors. Finally， the accelerating object can be tracked accurately based on Camshift algorithm combined with Kalman filter prediction. It is shown with experimental data that the blocked or accelerating target can be accurately located by used the method proposed in this paper.

Keywords：Camshaft；frame difference；accelerated motion；Kalman filter

0 引 言

視頻序列中移動(dòng)目標(biāo)的跟蹤是計(jì)算機(jī)視覺(jué)研究中的一個(gè)重要分支，在安全監(jiān)控，智能感知等領(lǐng)域應(yīng)用比較廣泛[1]。它能夠?yàn)閳?chǎng)景分析和目標(biāo)運(yùn)動(dòng)分析提供必要的信息來(lái)源，同時(shí)也是目標(biāo)識(shí)別、行為描述等高級(jí)處理的基礎(chǔ)。Camshift算法簡(jiǎn)單，運(yùn)行效率相對(duì)較高且計(jì)算量較小，在背景顏色過(guò)于單一的情況下跟蹤的效果良好。但是傳統(tǒng)的Camshift算法需要手動(dòng)初始化搜索窗口，如果背景顏色和目標(biāo)物體相似容易受到干擾，不適應(yīng)遮擋環(huán)境，不能夠?qū)δ繕?biāo)模型實(shí)時(shí)更新并且對(duì)高速運(yùn)動(dòng)的物體容易跟蹤失敗。針對(duì)以上缺點(diǎn)，本文提出了用四幀差分和Kalman算法相結(jié)合的方法對(duì)Camshift進(jìn)行改進(jìn)。

1 目標(biāo)檢測(cè)算法

1.1 四幀差分法

幀間差分法運(yùn)算簡(jiǎn)單且便于計(jì)算，比較適于改進(jìn)Camshift算法。但是二幀差分和三幀差分都比較容易產(chǎn)生空洞現(xiàn)象且三幀差分不能夠準(zhǔn)確的檢測(cè)出目標(biāo)重疊部分，使目標(biāo)難以提取。所以，本文運(yùn)用連續(xù)四幀差分算法通過(guò)交叉差分以及二值化處理來(lái)精確的得到前景目標(biāo)。

讀取視頻中四幀連續(xù)的圖像I1（x，y），I2（x，y），I3（x，y），I4（x，y），經(jīng)過(guò)預(yù)處理后分別對(duì)I1（x，y）與I3（x，y）以及I2（x，y）與I4（x，y）做差分運(yùn)算，得到差分結(jié)果：

g1=|I1（x，y）-I3（x，y）|

g2=|I2（x，y）-I4（x，y）|

然后將g1，g2進(jìn)行二值化處理，并對(duì)其執(zhí)行“與”運(yùn)算，得到結(jié)果H=g1g2，“與”運(yùn)算能夠很好的抑制目標(biāo)重疊的現(xiàn)象。

1.2 連通區(qū)域檢測(cè)

經(jīng)過(guò)四幀差分得到的二值化圖像仍不可避免的存在一些噪聲及空洞，可以通過(guò)連通性檢測(cè)的方法消除小的空洞和殘留的噪聲斑點(diǎn)。

前景圖像中具有相同像素值的像素點(diǎn)構(gòu)成連通區(qū)域。判斷圖像是否具有連通性用的是鄰接性，經(jīng)常運(yùn)用的鄰接性是四鄰接以及八鄰接。本文應(yīng)用四鄰接性對(duì)連通域進(jìn)行檢測(cè)，選取能夠連通的區(qū)域最大面積的4%作為分割值，留下面積大于此分割值的連通域作為我們感興趣的目標(biāo)區(qū)域，清除面積小于此分割值的干擾區(qū)域，最終得到運(yùn)動(dòng)前景圖像。

2 改進(jìn)Camshift算法

2.1 Camshift算法

Camshift算法的核心是在視頻圖像所有幀中的顏色概率分布圖的基礎(chǔ)上運(yùn)行meanshift算法，并運(yùn)用目標(biāo)概率直方圖的特性來(lái)識(shí)別單一幀中的運(yùn)動(dòng)目標(biāo)。Camshift算法首先初始化一個(gè)搜索窗口的大小和位置，使其可以恰好包含整個(gè)運(yùn)動(dòng)物體；其次對(duì)圖像的顏色直方圖的模型進(jìn)行反向投影獲得顏色概率的分布圖；然后執(zhí)行meanshift算法并得到新的搜索窗口對(duì)應(yīng)的質(zhì)心和大小；最后根據(jù)上一幀得到的結(jié)果重新調(diào)整搜索窗口的位置和大小，以此為基礎(chǔ)進(jìn)入到下一幀的跟蹤。迭代這個(gè)過(guò)程，實(shí)現(xiàn)移動(dòng)目標(biāo)的連續(xù)跟蹤。

在反向投影的計(jì)算中，我們首先選擇包括移動(dòng)目標(biāo)的初始窗口，再統(tǒng)計(jì)得到HSV空間的H分量的直方圖。選取直方圖的最大值作為目標(biāo)的亮度值，并按照式（1）計(jì)算與目標(biāo)的亮度值相似的亮度值的概率。其中，n代表直方圖的橫坐標(biāo)表示亮度值，h（n）代表直方圖的縱坐標(biāo)表示像素的統(tǒng)計(jì)值。為了便于計(jì)算，我們把橫坐標(biāo)取值范圍規(guī)定為0～255，并最終得到類似目標(biāo)概率的查找表。獲得類似目標(biāo)概率的查找表后，計(jì)算后續(xù)每一幀中的像素并與查找表對(duì)照，最終得到反向投影圖。

p（n）=h（n）max[h（n）]n=0，1，…，255（1）

根據(jù)式（2）～（5）可以得到0階矩和1階矩，然后確定新的搜索窗口的質(zhì)心和大小。

搜索框零階距：

M00=∑x∑yI（x，y）（2）

x和y的一階距：

M10=∑x∑yxI（x，y）

M01=∑x∑yyI（x，y）（3）

搜索窗口的質(zhì)心：

x0=M10M00 y0=M01M00（4）

搜索窗口的寬度：

S=M00256（5）

2.2 改進(jìn)Camshift算法

HSV顏色空間中的H分量用于樹立目標(biāo)的直方圖模型，它是有限的追蹤有簡(jiǎn)單背景的特定顏色的目標(biāo)。為了追蹤目標(biāo)顏色復(fù)雜的情況，在HSV空間中建立基于H和S兩個(gè)元素的2-D直方圖。目標(biāo)的外部采樣點(diǎn)的可靠性往往受到噪聲的影響，所以用加權(quán)直方圖的方法使具有不同位置的像素點(diǎn)具有不同權(quán)重，距離目標(biāo)中心的位置越近權(quán)重相應(yīng)的越大。目標(biāo)的加權(quán)直方圖計(jì)算方法如下：

q^u（y）=∑ni=1k（‖xi‖2）δ[b（xi-u）]

u=1，…，m（6）

其中{xi}i=1，…，n為目標(biāo)圖像像素坐標(biāo)，b和δ的作用是確定顏色值xi是否屬于特征值u。k（x）為核函數(shù)。移動(dòng)目標(biāo)用矩形框來(lái)表示，在某些情況下當(dāng)目標(biāo)被跟蹤時(shí)矩形框不僅包含目標(biāo)也會(huì)包含一部分背景。因此矩形框的統(tǒng)計(jì)目標(biāo)直方圖應(yīng)該包含背景顏色的特征。將上面所用的加權(quán)直方圖變換成彩色的概率分布圖使目標(biāo)區(qū)域更精確的被檢測(cè)到。所以該方法可以減小背景像素的影響更好的跟蹤目標(biāo)。

3 Kalman濾波運(yùn)動(dòng)估計(jì)

傳統(tǒng)的Camshift算法比較簡(jiǎn)單的以上一幀的搜索窗口的結(jié)果為基礎(chǔ)初始化下一幀的搜索窗口。所以當(dāng)目標(biāo)做加速運(yùn)動(dòng)時(shí)，很容易跟丟運(yùn)動(dòng)目標(biāo)。針對(duì)這一問(wèn)題，本文引入Kalman濾波。卡爾曼濾波器是一種動(dòng)態(tài)系統(tǒng)中狀態(tài)變量最小方差的估計(jì)算法。它可以精確的預(yù)測(cè)移動(dòng)物體的質(zhì)心和速度。所以，我們用卡爾曼濾波器來(lái)估計(jì)運(yùn)動(dòng)目標(biāo)的參數(shù)，該系統(tǒng)的狀態(tài)方程和觀測(cè)方程分別為：

X（k）=A（k）X（k-1）+W（k）（7）

Y（k）=H（k）X（k）+V（k）（8）

其中A（k）是狀態(tài)轉(zhuǎn)移矩陣，Y（k）是觀測(cè)變量，H（k）是觀測(cè)矩陣，W（k）和V（k）分別為激勵(lì)白噪聲和觀測(cè)白噪聲，它們是互不相關(guān)的零均值白噪聲，協(xié)方差矩陣分別為Q和R。由于在跟蹤做平拋運(yùn)動(dòng)的目標(biāo)的過(guò)程中，前后兩幀的間隔時(shí)間較短，所以可以把目標(biāo)在兩幀之間的運(yùn)動(dòng)看做勻速運(yùn)動(dòng)。令系統(tǒng)狀態(tài)向量為X（k）=[x（k），y（k），vx（k），vy（k）]，觀測(cè)向量為Y（k）=[x（k），y（k）]。其中x（k），y（k）為目標(biāo)區(qū)域質(zhì)心在X軸、Y軸的位置坐標(biāo)，vx（k），vy（k）為目標(biāo)在X軸、Y軸的速度。根據(jù)式（7）、（8）我們可以分別得到狀態(tài)轉(zhuǎn)移矩陣A（k）和觀測(cè)矩陣H（k）分別為：

A（k）=10dt0

010dt

0010

0001

H（k）=10010000

4 本文算法

首先運(yùn)用四幀差分算法檢測(cè)出比較完整的前景區(qū)域，根據(jù)得到的前景區(qū)域自動(dòng)的選取初始搜索框。然后引用Kalman濾波器，用其預(yù)測(cè)Camshift算法里第二幀以后的搜索框的質(zhì)心和大小，最后用Camshift算法得出移動(dòng)目標(biāo)區(qū)域的準(zhǔn)確的位置和大小。判斷是否出現(xiàn)相似顏色干擾或者目標(biāo)被遮擋情況，如果出現(xiàn)那么用前景區(qū)域與Kalman濾波相相結(jié)合的預(yù)測(cè)值作為觀測(cè)值來(lái)更新Kalman濾波器，否則用Camshift的結(jié)果作為觀測(cè)值。本文運(yùn)用ε，μ，φ（k）來(lái)分別判斷視頻中是否出現(xiàn)顏色相似干擾或目標(biāo)被遮擋，計(jì)算公式為：

ε=S_now/S_bef（9）

μ=S_now/S_beg（10）

φ（k）=（x（k）-x^（k））2+（y（k）-y^（k））2（11）

其中S_now是通過(guò)camshift得到的搜索框的大小，S_bef是上一幀中搜索框大小，S_beg是最初搜索框大小，（x（k），y（k）），（x^（k），y^（k））分別表示目標(biāo)質(zhì)心的觀測(cè)值和預(yù)測(cè)值。當(dāng)ε>2時(shí)，判定存在大面積相似背景顏色的干擾；當(dāng)μ<0.4并且φ（k）>10的時(shí)候，判定移動(dòng)目標(biāo)被大面積遮擋。算法流程圖如圖1所示：

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

5.1 相似顏色背景干擾實(shí)驗(yàn)

本實(shí)驗(yàn)在白色實(shí)驗(yàn)臺(tái)上進(jìn)行，其中干擾背景為橙黃色書本，跟蹤目標(biāo)為運(yùn)動(dòng)的黃色小球，跟蹤結(jié)果用黑色方框表示。

圖2為相似顏色背景干擾實(shí)驗(yàn)的結(jié)果，其中圖2（a）為原始算法跟蹤結(jié)果，圖2（b）為改進(jìn)算法跟蹤結(jié)果。當(dāng)出現(xiàn)相似顏色背景干擾時(shí)，圖2（a）中搜索窗口的質(zhì)心停留在干擾物橙黃色書本上，導(dǎo)致跟蹤失敗，而圖2（b）中由于運(yùn)用了改進(jìn)算法，能夠剔除背景書本的干擾，使書本與小球分離，能夠正常的跟蹤到黃色小球。

5.2 目標(biāo)遮擋實(shí)驗(yàn)

本實(shí)驗(yàn)在木質(zhì)實(shí)驗(yàn)臺(tái)上操作，遮擋物為金色長(zhǎng)方體，被跟蹤目標(biāo)為運(yùn)動(dòng)的黃色小球，目標(biāo)由右向左運(yùn)動(dòng)。

圖3為遮擋結(jié)果，其中圖3（a）為原始算法跟蹤結(jié)果，圖3（b）為改進(jìn)算法跟蹤結(jié)果。從實(shí)驗(yàn)結(jié)果可知，目標(biāo)在被全部遮擋前兩種算法均可以跟蹤，但是當(dāng)目標(biāo)被全部遮擋再次出現(xiàn)后，只有改進(jìn)算法可以連續(xù)追蹤目標(biāo)。

5.3 物體平拋運(yùn)動(dòng)實(shí)驗(yàn)

本實(shí)驗(yàn)為平拋運(yùn)動(dòng)實(shí)驗(yàn)，選取固定攝像頭拍攝視頻，其中背景為藍(lán)色木板，被跟蹤的目標(biāo)為黃色小球，它被人為拋出。小球做平拋運(yùn)動(dòng)，其運(yùn)動(dòng)軌跡為一條拋物線。用黑色方框表示跟蹤結(jié)果。

如圖4所示，分別選取原始視頻的第1、7、12、14幀，在第1、7幀時(shí)兩種算法均可以準(zhǔn)確跟蹤運(yùn)動(dòng)目標(biāo)，但當(dāng)追蹤到第12、14幀的時(shí)候，與原始算法不同，改進(jìn)算法能夠精確定位每一幀中運(yùn)動(dòng)目標(biāo)的位置，保證跟蹤要求。

由于相似顏色、遮擋、加速運(yùn)動(dòng)等原因都會(huì)對(duì)每幀圖片在收斂過(guò)程中的迭代次數(shù)有所影響，本文分別根據(jù)Camshift算法和本文算法對(duì)平拋運(yùn)動(dòng)實(shí)驗(yàn)進(jìn)行了跟蹤，對(duì)前30幀的迭代次數(shù)統(tǒng)計(jì)如圖5所示。圖中黑色實(shí)線代表Camshift算法，紅色實(shí)線代表本文算法，相比之下文中改進(jìn)算法的迭代次數(shù)明顯要少，即改進(jìn)算法的收斂性強(qiáng)于傳統(tǒng)Camshift算法，有效提升了跟蹤系統(tǒng)的實(shí)時(shí)性。

6 結(jié) 論

針對(duì)傳統(tǒng)Camshift算法的不足，提出一種基于四幀差分目標(biāo)檢測(cè)并結(jié)合Kalman預(yù)測(cè)模型對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行跟蹤的改進(jìn)算法。首先在相似背景顏色干擾實(shí)驗(yàn)中利用四幀差分和加權(quán)顏色概率直方圖排除顏色干擾。在遮擋和平拋實(shí)驗(yàn)中利用Kalman濾波器預(yù)測(cè)每幀目標(biāo)位置并結(jié)Camshift算法準(zhǔn)確定位。通過(guò)實(shí)驗(yàn)證明改進(jìn)算法能很好的適應(yīng)相似顏色干擾，目標(biāo)遮擋，物體加速運(yùn)動(dòng)情況，有較好的魯棒性和實(shí)用性。

參 考 文 獻(xiàn)：

[1] 梁超， 史東承. 基于運(yùn)動(dòng)估計(jì)的CamShift移動(dòng)目標(biāo)跟蹤算法[J]. 吉林大學(xué)學(xué)報(bào)（工學(xué)版）， 2013， 43（增刊1）：169-172（S1）：169-172.

[2] 萬(wàn)中田， 冼鐘業(yè)， 胡明宇，等. 基于Kalman預(yù)測(cè)器的多特征Camshift運(yùn)動(dòng)目標(biāo)跟蹤算法[J]. 武漢大學(xué)學(xué)報(bào)：工學(xué)版， 2015， 48（5）：712-716.

[3] 袁偉， 王朝立， 張旭飛. 混合高斯模型與CamShift算法結(jié)合的臺(tái)球跟蹤方法[J]. 微型電腦應(yīng)用， 2013， 29（2）：10-12.

[4] 鄔大鵬， 程衛(wèi)平， 于盛林. 基于幀間差分和運(yùn)動(dòng)估計(jì)的Camshift目標(biāo)跟蹤算法[J]. 光電工程， 2010， 37（1）：55-60.

[5] 張宇. 一種圖像確認(rèn)目標(biāo)的多目標(biāo)跟蹤方法[J]. 電子測(cè)量與儀器學(xué)報(bào)， 2014， 28（6）：617-624.

[6] 修春波， 魏世安. 顯著性直方圖模型的Camshift跟蹤方法[J]. 光學(xué)精密工程， 2015， 23（6）：1749-1757.

[7] 陳東彥， 余永龍， 胡軍. 具有相關(guān)噪聲和不確定觀測(cè)系統(tǒng)的全局最優(yōu)Kalman濾波[J]. 哈爾濱理工大學(xué)學(xué)報(bào)， 2015， 20（4）：1-10.

[8] 張鵬， 李思岑， 楊燕翔. 融合邊緣檢測(cè)的四幀差分運(yùn)動(dòng)目標(biāo)檢測(cè)[J]. 電子技術(shù)與軟件工程， 2014（20）：106-107.

[9] 胡波， 陳懇， 徐建瑜，等. 基于Kalman預(yù)測(cè)和Mean-shift算法的視頻目標(biāo)跟蹤[J]. 光電子：激光， 2009（11）：1517-1522.

[10]楊明極， 范希冀， 于舒春. 基于三維混沌映射的HSV空間圖像加密算法研究[J]. 哈爾濱理工大學(xué)學(xué)報(bào)， 2015， 20（6）：103-106.

[11]賈茜， 謝勤嵐， 董蓓. 基于TMS320DM642的實(shí)時(shí)運(yùn)動(dòng)目標(biāo)檢測(cè)與跟蹤系統(tǒng)[J]. 計(jì)算機(jī)測(cè)量與控制， 2009， 17（3）：469-471.

[12]柴華， 任洪娥， 張俊卿. 利用Sobel算子結(jié)合蟻群算法提取竹材的內(nèi)外輪廓[J]. 哈爾濱理工大學(xué)學(xué)報(bào)， 2014， 19（1）：54-58.

[13]莫林， 廖鵬， 劉勛. 一種基于背景減除與三幀差分的運(yùn)動(dòng)目標(biāo)檢測(cè)算法[J]. 微計(jì)算機(jī)信息， 2009， 25（12）：274-276.

[14]白曉方， 楊衛(wèi)， 陳佩珩. 一種改進(jìn)的運(yùn)動(dòng)目標(biāo)檢測(cè)與跟蹤方法[J]. 電視技術(shù)， 2014， 38（1）：180-182.

[15]鐘建冬， 蘇劍波. 基于視覺(jué)預(yù)測(cè)的運(yùn)動(dòng)目標(biāo)實(shí)時(shí)跟蹤系統(tǒng)[J]. 機(jī)器人， 2010， 32（4）：516-521.

[16]庾鵬， 王旭， 仝天樂(lè)，等. 基于GrabCut算法和四幀差分法的目標(biāo)提取算法[J]. 微型機(jī)與應(yīng)用， 2016， 35（11）：40-42.

[17]紀(jì)青華， 禹素萍. 基于 Surendra背景減除法和四幀差分法的目標(biāo)檢測(cè)算法[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2014（12）：242-244.

[18]劉士榮， 孫凱， 張波濤，等. 基于改進(jìn)Camshift算法的移動(dòng)機(jī)器人運(yùn)動(dòng)目標(biāo)跟蹤[J]. 華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2011， 39（s2）：223-226.

[19]楊玲， 甄志明， 劉國(guó)紅，等. 基于多尺度邊緣提取的薄霧圖像處理方法[J]. 哈爾濱理工大學(xué)學(xué)報(bào)， 2014， 19（5）：94-98.

[20]萬(wàn)琴， 王耀南. 基于卡爾曼濾波器的運(yùn)動(dòng)目標(biāo)檢測(cè)與跟蹤[J]. 湖南大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2007， 34（3）：36-40.