用于運動目標跟蹤的改進Camshift算法的研究

秦勇 商萌萌 趙曉紅 蓋建新

摘 要：Camshift是一種應用顏色特性來對目標實施跟蹤的算法，所以當背景過于復雜、目標被遮擋或做加速運動時很容易發生目標跟丟的情況。針對以上缺點，提出首先采用幀間差分法自動的選取搜索窗口，然后引入加權顏色概率直方圖排除相似背景顏色的干擾，最后采用Kalman濾波器預測和Camshift算法相結合的方法準確跟蹤做加速運動的物體。實驗表明，此方法能夠準確定位做加速運動或被遮擋的目標。

關鍵詞：Camshift；幀間差分；加速運動；Kalman濾波

DOI：10.15938/j.jhust.2018.03.006

中圖分類號： TP391

文獻標志碼： A

文章編號： 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 引 言

視頻序列中移動目標的跟蹤是計算機視覺研究中的一個重要分支，在安全監控，智能感知等領域應用比較廣泛[1]。它能夠為場景分析和目標運動分析提供必要的信息來源，同時也是目標識別、行為描述等高級處理的基礎。Camshift算法簡單，運行效率相對較高且計算量較小，在背景顏色過于單一的情況下跟蹤的效果良好。但是傳統的Camshift算法需要手動初始化搜索窗口，如果背景顏色和目標物體相似容易受到干擾，不適應遮擋環境，不能夠對目標模型實時更新并且對高速運動的物體容易跟蹤失敗。針對以上缺點，本文提出了用四幀差分和Kalman算法相結合的方法對Camshift進行改進。

1 目標檢測算法

1.1 四幀差分法

幀間差分法運算簡單且便于計算，比較適于改進Camshift算法。但是二幀差分和三幀差分都比較容易產生空洞現象且三幀差分不能夠準確的檢測出目標重疊部分，使目標難以提取。所以，本文運用連續四幀差分算法通過交叉差分以及二值化處理來精確的得到前景目標。

讀取視頻中四幀連續的圖像I1（x，y），I2（x，y），I3（x，y），I4（x，y），經過預處理后分別對I1（x，y）與I3（x，y）以及I2（x，y）與I4（x，y）做差分運算，得到差分結果：

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

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

然后將g1，g2進行二值化處理，并對其執行“與”運算，得到結果H=g1g2，“與”運算能夠很好的抑制目標重疊的現象。

1.2 連通區域檢測

經過四幀差分得到的二值化圖像仍不可避免的存在一些噪聲及空洞，可以通過連通性檢測的方法消除小的空洞和殘留的噪聲斑點。

前景圖像中具有相同像素值的像素點構成連通區域。判斷圖像是否具有連通性用的是鄰接性，經常運用的鄰接性是四鄰接以及八鄰接。本文應用四鄰接性對連通域進行檢測，選取能夠連通的區域最大面積的4%作為分割值，留下面積大于此分割值的連通域作為我們感興趣的目標區域，清除面積小于此分割值的干擾區域，最終得到運動前景圖像。

2 改進Camshift算法

2.1 Camshift算法

Camshift算法的核心是在視頻圖像所有幀中的顏色概率分布圖的基礎上運行meanshift算法，并運用目標概率直方圖的特性來識別單一幀中的運動目標。Camshift算法首先初始化一個搜索窗口的大小和位置，使其可以恰好包含整個運動物體；其次對圖像的顏色直方圖的模型進行反向投影獲得顏色概率的分布圖；然后執行meanshift算法并得到新的搜索窗口對應的質心和大小；最后根據上一幀得到的結果重新調整搜索窗口的位置和大小，以此為基礎進入到下一幀的跟蹤。迭代這個過程，實現移動目標的連續跟蹤。

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

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

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

搜索框零階距：

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

x和y的一階距：

M10=∑x∑yxI（x，y）

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

搜索窗口的質心：

x0=M10M00 y0=M01M00（4）

搜索窗口的寬度：

S=M00256（5）

2.2 改進Camshift算法

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

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

u=1，…，m（6）

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

3 Kalman濾波運動估計

傳統的Camshift算法比較簡單的以上一幀的搜索窗口的結果為基礎初始化下一幀的搜索窗口。所以當目標做加速運動時，很容易跟丟運動目標。針對這一問題，本文引入Kalman濾波。卡爾曼濾波器是一種動態系統中狀態變量最小方差的估計算法。它可以精確的預測移動物體的質心和速度。所以，我們用卡爾曼濾波器來估計運動目標的參數，該系統的狀態方程和觀測方程分別為：

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

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

其中A（k）是狀態轉移矩陣，Y（k）是觀測變量，H（k）是觀測矩陣，W（k）和V（k）分別為激勵白噪聲和觀測白噪聲，它們是互不相關的零均值白噪聲，協方差矩陣分別為Q和R。由于在跟蹤做平拋運動的目標的過程中，前后兩幀的間隔時間較短，所以可以把目標在兩幀之間的運動看做勻速運動。令系統狀態向量為X（k）=[x（k），y（k），vx（k），vy（k）]，觀測向量為Y（k）=[x（k），y（k）]。其中x（k），y（k）為目標區域質心在X軸、Y軸的位置坐標，vx（k），vy（k）為目標在X軸、Y軸的速度。根據式（7）、（8）我們可以分別得到狀態轉移矩陣A（k）和觀測矩陣H（k）分別為：

A（k）=10dt0

010dt

0010

0001

H（k）=10010000

4 本文算法

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

ε=S_now/S_bef（9）

μ=S_now/S_beg（10）

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

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

5 實驗結果與分析

5.1 相似顏色背景干擾實驗

本實驗在白色實驗臺上進行，其中干擾背景為橙黃色書本，跟蹤目標為運動的黃色小球，跟蹤結果用黑色方框表示。

圖2為相似顏色背景干擾實驗的結果，其中圖2（a）為原始算法跟蹤結果，圖2（b）為改進算法跟蹤結果。當出現相似顏色背景干擾時，圖2（a）中搜索窗口的質心停留在干擾物橙黃色書本上，導致跟蹤失敗，而圖2（b）中由于運用了改進算法，能夠剔除背景書本的干擾，使書本與小球分離，能夠正常的跟蹤到黃色小球。

5.2 目標遮擋實驗

本實驗在木質實驗臺上操作，遮擋物為金色長方體，被跟蹤目標為運動的黃色小球，目標由右向左運動。

圖3為遮擋結果，其中圖3（a）為原始算法跟蹤結果，圖3（b）為改進算法跟蹤結果。從實驗結果可知，目標在被全部遮擋前兩種算法均可以跟蹤，但是當目標被全部遮擋再次出現后，只有改進算法可以連續追蹤目標。

5.3 物體平拋運動實驗

本實驗為平拋運動實驗，選取固定攝像頭拍攝視頻，其中背景為藍色木板，被跟蹤的目標為黃色小球，它被人為拋出。小球做平拋運動，其運動軌跡為一條拋物線。用黑色方框表示跟蹤結果。

如圖4所示，分別選取原始視頻的第1、7、12、14幀，在第1、7幀時兩種算法均可以準確跟蹤運動目標，但當追蹤到第12、14幀的時候，與原始算法不同，改進算法能夠精確定位每一幀中運動目標的位置，保證跟蹤要求。

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

6 結 論

針對傳統Camshift算法的不足，提出一種基于四幀差分目標檢測并結合Kalman預測模型對運動目標進行跟蹤的改進算法。首先在相似背景顏色干擾實驗中利用四幀差分和加權顏色概率直方圖排除顏色干擾。在遮擋和平拋實驗中利用Kalman濾波器預測每幀目標位置并結Camshift算法準確定位。通過實驗證明改進算法能很好的適應相似顏色干擾，目標遮擋，物體加速運動情況，有較好的魯棒性和實用性。

參 考 文 獻：

[1] 梁超， 史東承. 基于運動估計的CamShift移動目標跟蹤算法[J]. 吉林大學學報（工學版）， 2013， 43（增刊1）：169-172（S1）：169-172.

[2] 萬中田， 冼鐘業， 胡明宇，等. 基于Kalman預測器的多特征Camshift運動目標跟蹤算法[J]. 武漢大學學報：工學版， 2015， 48（5）：712-716.

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

[4] 鄔大鵬， 程衛平， 于盛林. 基于幀間差分和運動估計的Camshift目標跟蹤算法[J]. 光電工程， 2010， 37（1）：55-60.

[5] 張宇. 一種圖像確認目標的多目標跟蹤方法[J]. 電子測量與儀器學報， 2014， 28（6）：617-624.

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

[7] 陳東彥， 余永龍， 胡軍. 具有相關噪聲和不確定觀測系統的全局最優Kalman濾波[J]. 哈爾濱理工大學學報， 2015， 20（4）：1-10.

[8] 張鵬， 李思岑， 楊燕翔. 融合邊緣檢測的四幀差分運動目標檢測[J]. 電子技術與軟件工程， 2014（20）：106-107.

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

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

[11]賈茜， 謝勤嵐， 董蓓. 基于TMS320DM642的實時運動目標檢測與跟蹤系統[J]. 計算機測量與控制， 2009， 17（3）：469-471.

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

[13]莫林， 廖鵬， 劉勛. 一種基于背景減除與三幀差分的運動目標檢測算法[J]. 微計算機信息， 2009， 25（12）：274-276.

[14]白曉方， 楊衛， 陳佩珩. 一種改進的運動目標檢測與跟蹤方法[J]. 電視技術， 2014， 38（1）：180-182.

[15]鐘建冬， 蘇劍波. 基于視覺預測的運動目標實時跟蹤系統[J]. 機器人， 2010， 32（4）：516-521.

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

[17]紀青華， 禹素萍. 基于 Surendra背景減除法和四幀差分法的目標檢測算法[J]. 計算機應用與軟件， 2014（12）：242-244.

[18]劉士榮， 孫凱， 張波濤，等. 基于改進Camshift算法的移動機器人運動目標跟蹤[J]. 華中科技大學學報（自然科學版）， 2011， 39（s2）：223-226.

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

[20]萬琴， 王耀南. 基于卡爾曼濾波器的運動目標檢測與跟蹤[J]. 湖南大學學報（自然科學版）， 2007， 34（3）：36-40.