基于改進幀間差分與局部Camshift相結合的目標跟蹤算法

周文靜　陳瑋

摘要：

為了能夠準確、快速地跟蹤運動目標，提出了改進幀間差分與局部Camshift相結合的目標跟蹤算法。針對傳統(tǒng)幀間差分法在運動目標提取過程中容易產生“空洞”的現(xiàn)象，并且對噪聲敏感的問題，提出了三幀差分的運動目標檢測算法。首先，利用三幀差分法，將相鄰的三幀圖像作為一組進行再差分，從而檢測出中間幀運動目標的形狀輪廓，然后將該區(qū)域作為運動目標的模板區(qū)域，并將該區(qū)域進行適當擴充，最后采用局部Camshift算法進行目標跟蹤。實驗結果表明，改進的幀間差分可以有效地彌補“空洞”現(xiàn)象，對噪聲也起到了一定的抑制作用。同時，該方法克服了傳統(tǒng)Camshift算法需要人為選擇跟蹤區(qū)域和容易發(fā)散的缺點，達到了預期的目標檢測和跟蹤效果。

關鍵詞：

局部Camshift算法；三幀差分法；目標檢測；目標跟蹤

DOIDOI：10.11907/rjdk.172531

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2018）003006704

英文摘要Abstract：The target tracking algorithm based on improved interframe difference and local Camshift were put forward to quickly and exactly track moving object. The three frame difference target detection algorithm is proposed for the traditional interframe difference method， which is prone to “empty” phenomenon in the process of moving object extraction and is sensitive to noise. Firstly， the three frame difference method is used to discriminate the adjacent threeframe image as a group to detect the shape contour of the moving target of the intermediate frame， and the region is used as the template area of the moving object， and the area is appropriately expanded， with local Camshift algorithm for target tracking. Experimental results show that the improved interframe difference can effectively compensate for the “hole” phenomenon， the noise also played a certain degree of inhibition. At the same time， this method overcomes the shortcomings of the traditional Camshift algorithm that requires artificial selection of tracking areas and easy divergence to achieve the desired target detection and tracking.

英文關鍵詞Key Words：local Camshift algorithm； three frame difference； target detection； target tracking

0引言

隨著計算機與通信技術及圖像處理技術的發(fā)展，計算機視覺已成為目前的研究熱點，而運動目標檢測與跟蹤是計算機視覺研究的核心課題之一[1]。Camshift是一種基于顏色直方圖的跟蹤算法，利用顏色的相關信息跟蹤運動目標。該算法繼承了MeanShift算法在實時性和魯棒性方面的優(yōu)點[2]，同時可根據上一幀的結果自適應調整搜索窗口位置和大小，從而得到目標在當前幀的位置[3]。

Camshift算法在背景單一，且跟蹤目標與背景顏色差別較大時，具有很好的跟蹤效果。然而，傳統(tǒng)的Camshift算法在目標檢測階段需手動選取跟蹤目標，而不能實現(xiàn)目標的全自動檢測和跟蹤。同時，傳統(tǒng)的Camshift算法在反向投影時，需對后續(xù)整幅視頻圖像進行全局計算，增加了額外的計算負擔，并且全局計算也會大大降低跟蹤質量。比如在亮度不強的區(qū)域，反向投影會產生噪聲點。

文獻[3]提出了幀間差分與Camshift相結合的目標跟蹤算法，但幀間差分所提取的目標區(qū)域有“空洞”現(xiàn)象，區(qū)域信息獲取不完整，可能導致跟蹤區(qū)域發(fā)散[3]。針對以上問題，本文提出改進幀間差分與局部Camshift相結合的跟蹤算法。

1Camshift目標跟蹤算法

Camshift （Continuously Adaptive MeanShift），即連續(xù)自適應的MeanShift算法。MeanShift是一種基于梯度計算的均值漂移跟蹤算法。在D維空間中，均值移動矢量沿著概率密度增大的方向逐步搜尋，從而得到該空間概率密度的局部最大值。Meanshift算法是在一張指定的圖片上計算最優(yōu)迭代結果，而Camshift是面向連續(xù)的視頻序列，逐一對每一幀圖像進行Meanshift運算，求出最優(yōu)搜索結果[45]。Camshift算法具體操作步驟如下：

（1）讀取視頻幀圖像，并將該圖像由RGB顏色空間轉至HSV空間。為了實現(xiàn)色彩空間的降維，需將H（hue）分量分離出來，即由原來的（R，G，B，X，Y）5維降為（H，X，Y）3維，從而減少計算復雜度。

（2）初始化搜索窗，并計算出搜索窗區(qū)域的顏色直方圖，進行反向投影操作，將原始圖像轉為色彩概率分布圖。

（3）利用MeanShift算法在概率分布圖上進行迭代漂移。假設I（x，y）是概率投影圖上（x，y）處的像素值，則搜索窗口的零階距為：

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

計算一階距為：

M10=∑x∑yxI（x，y），M01=∑x∑yyI（x，y）（2）

搜索窗的質心位置為：

Xc=M10M00，Yc=M01M00 （3）

（4）調整搜索窗大小，寬度為：

s=M00256（4）

長度為寬度的1.2s。

（5）將搜索窗的中心移至質心（Xc，Yc）處，如果移動距離大于預設的固定閾值，則重復步驟（3）～（5），直到搜索窗中心與質心間的移動距離小于預設的固定閾值，待其收斂或達到最大迭代次數，得到最終搜索窗口的位置和大小。

（6）讀入下一幀圖像，根據新得到的搜索窗口參數信息，跳轉至步驟（2）繼續(xù)執(zhí)行，直至視頻播放結束。

2局部Camshift目標跟蹤算法

為了克服傳統(tǒng)Camshift算法在反向投影時帶來的額外計算和噪聲點，將算法全局計算改為局部計算[6]，讓反向投影限制在搜索窗口內部進行，提出了局部Camshift目標跟蹤算法。，該算法有效地改善了Camshift算法的計算量和無關的計算容易讓更多無關的物體干擾跟蹤算法。局部Camshift算法具體操作步驟如下：①對給定的圖像作直方圖運算，初始化窗口，設定初始窗口的位置，準備跟蹤；②對當前窗口作適當擴充，并計算擴充后窗口的反向投影；③使用Meanshift算法進行迭代，待收斂后，返回跟蹤目標的零階距M00和收斂位置；④以收斂位置為中心建立窗口，由式（4）進行窗口的尺寸計算，并根據計算結果更新窗口大??；⑤將更新的窗口作為下一幀視頻圖像的初始窗口，并將Meanshift算法的迭代窗口中心重新作為目標初始位置，跳轉至步驟（2）繼續(xù)執(zhí)行，直至視頻播放結束，返回。

3三幀差分算法

3.1三幀差分法原理與框架

三幀差分算法是兩幀差分算法的改進算法[7]。該算法的基本原理是對兩次幀間差的差分圖像再進行相關操作，即將當前幀與前一幀作差分運算，下一幀與當前幀作差分運算，然后對兩次差分結果通過選擇適當的閾值進行二值化處理，最后將經過二值化處理的兩次差分結果再進行邏輯“與”操作[8]。其算法框架如圖1所示。

3.2三幀差分法流程

（1）灰度化。輸入的視頻文件是彩色的，一般采用的是RGB顏色模型。由于三幀差分法是基于像素點的運動目標檢測算法，它通過對視頻圖像序列中的連續(xù)三幀圖像分別進行相鄰的差分運算，判斷背景中像素點的灰度值是否發(fā)生了變化，然后根據灰度值的變化得到運動目標，所以對輸入的彩色視頻進行灰度化處理，將彩色圖像轉化為灰度圖像?；叶忍幚聿捎肶UV與RGB顏色空間變化的方法，如式（5）所示：

Y=0.3R+0.59G+0.11B（5）

（2）分幀處理。從視頻序列中t時刻選取連續(xù)三幀視頻圖像，記為Ik-1（x，y）、Ik（x，y）、Ik+1（x，y），分別表示前一幀、當前幀和后一幀圖像。其中，x、y是像素位置。

（3）差分處理。分別計算相鄰兩幀圖像的差值：

diff1（k，k-1）（x，y）=|Ik（x，y）-Ik-1（x，y）|（6）

diff2（k+1，k）（x，y）=|Ik+1（x，y）-Ik（x，y）|（7）

因為視頻幀與幀之間時間間隔較短，而運動目標的運動速度不快，所以可以對運動目標進行準確定位[9]。因此，采用此算法進行目標定位。實驗中，選取視頻序列Car中連續(xù)的3幀圖像，分別為第7幀、8幀和9幀。差分實驗如圖2所示。

（4）二值化。通過選擇合理的閾值T，對得到的差值圖像進行二值化處理，如式（8）、式（9）所示：

g1（k，k-1）（x，y）=255，diff1（k，k-1）（x，y）≥T0， diff1（k，k-1）（x，y）

g2（k+1，k）（x，y）=255，diff2（k+1，k）（x，y）≥T0， diff2（k+1，k）（x，y）

其中，T為設定閾值，g1（k，k-1）（x，y）、g2（k+1，k）（x，y）為二值化處理結果。

閾值的選擇采用最佳閾值法，即迭代法[10]。它是一種不斷用變量的舊值遞推新值的過程，即無限趨近于“真值”的過程[11]。迭代閾值的獲取步驟歸納如下：

步驟1：選擇適當的初始閾值T（j），一般情況下可以選取整幅圖像的平均灰度值作為迭代的初始閾值，j為總迭代次數，初始化時j=0。

步驟2：用T（j）分割圖像，將圖像分為2個區(qū)域C（j）1和C（j）2。

步驟3：計算兩區(qū)域的平均灰度值，其中N（j）1、N（j）2為第j次迭代時區(qū)域C1和C2的像素點個數，f（x，y）表示圖像中（x，y）點的灰度值。

u（j）1=1N（j）1∑f（x，y）∈C（j）1f（x，y）（10）

u（j）2=1N（j）2∑f（x，y）∈C（j）2f（x，y）（11）

步驟4： 計算新的門限值，即：

T（j+1）=u（j）1+u（j）22（12）

步驟5：令j=j+1，重復步驟2-4，直到T（j+1）與T（j）的差小于規(guī)定值或j達到最大的迭代次數。

（5）與運算。通過與運算提取二值化圖像的交集，從而得到運動目標前景圖像[12]：

X=g1（k，k-1）（x，y）g2（k+1，k）（x，y）（13）

其中，*為與運算。

（6）腐蝕與膨脹。對獲得的二值圖像進行形態(tài)學的腐蝕與膨脹操作。腐蝕的作用是為了消除干擾點或噪聲點，使跟蹤目標變小，從而消除小于結構元素的點[13]。而膨脹的作用是將與目標接觸的所有背景點合并到目標上，使目標增大，可彌補目標的“空洞”現(xiàn)象[14]。實驗如圖3所示。

4三幀差分與局部Camshift算法相結合

利用三幀差分可以檢測出運動目標區(qū)域，然后利用局部Camshift算法進行目標跟蹤[15]，具體操作步驟如下：

（1）讀取視頻幀序列，將第一幀圖像拷貝給pre_frame，再將第二幀圖像拷貝給frame，并分別進行灰度化處理，記為pre_gray，fra_gray。

（2）將第三幀圖像拷貝給next_frame，并進行灰度化處理，記為next_gray。

（3）將第一幀灰度圖像pre_gray與第二幀灰度圖像fra_gray進行差分運算，得到差分圖像，記為gray_image1；第二幀灰度圖像fra_gray與第三幀灰度圖像next_gray進行差分運算，得到差分圖像，記為gray_image2[16]；最后，對gray_image1和gray_image2進行二值化處理，通過迭代法選擇適當的閾值T，得到大于閾值T的像素點個數，進而判斷是否已檢測到目標。

（4）若得到的像素點個數大于預先設置好的個數，則表示此時已檢測到跟蹤目標，然后求取這些像素點的最小外接矩形，并在此基礎上對得到的矩形進行適當的外擴處理。此時，即完成了運動目標檢測。

（5）再對gray_image1和gray_image2進行與運算，得到大于閾值T的中間幀二值圖像，記為gray_image。為了消除邊緣和噪聲對目標的干擾，本文采用圖像形態(tài)學中對二值圖像腐蝕和膨脹的方法解決這個問題[17]。

（6）對檢測出的運動目標區(qū)域采用局部Camshift算法進行跟蹤，同時，將第二幀拷貝給第一幀，第三幀拷貝給第二幀，讀取下一幀，跳至步驟（2）執(zhí)行，直至視頻播放結束，返回。

5實驗與仿真

本次仿真實驗是在處理器型號為 Intel Corei5-2430M，主頻2.40GHz，內存4GB，操作系統(tǒng)為Windows 7專業(yè)版的PC機上使用Visual Studio2015以及OpenCV 3.2.0版本實現(xiàn)的。

如圖4、圖5所示是一組汽車行駛視頻序列，選取汽車作為跟蹤目標，跟蹤結果顯示在藍色矩形框內。畫面中，周圍小草的顏色與汽車顏色相似，因而對跟蹤目標有一定干擾。視頻序列是從第1幀開始框選跟蹤目標。圖4采用傳統(tǒng)的幀間差分與Camshift相結合的跟蹤算法，圖5采用改進的幀間差分與局部Camshift相結合的跟蹤算法。從圖5可以看出，改進的跟蹤算法在跟蹤過程中可以保證跟蹤目標整體上的完整性（彩圖見封二）。

如圖6、圖7所示，類似于攝像頭監(jiān)控下的視頻序列，選取人作為跟蹤目標。第26幀為相對靜止的場景，無運動目標。從圖6可以看出，傳統(tǒng)跟蹤算法在第85幀和117幀出現(xiàn)跟蹤目標大部分缺失的情況，而改進的跟蹤算法表現(xiàn)出較好的跟蹤性能（彩圖見封二）。

仿真實驗結果表明，改進的跟蹤算法具有更好的跟蹤效果，跟蹤準確度得到明顯提高。同時，局部Camshift大大降低了算法的計算復雜度，使跟蹤速度得到明顯提高。

6結語

本文在傳統(tǒng)Camshift跟蹤算法的基礎上，提出了基于改進幀間差分與局部Camshift相結合的目標跟蹤算法[17]。通過三幀差分對運動目標進行了很好的定位，有效避免了幀間差分帶來的“空洞”現(xiàn)象，克服了傳統(tǒng)Camshift算法需人為框選跟蹤區(qū)域和易發(fā)散的缺點，實現(xiàn)了一種全自動的目標跟蹤。局部Camshift算法使目標跟蹤速度得到很大提高，降低了計算復雜度。但在特定場景下，本文算法也存在一定局限，比如跟蹤目標運動速度過快時，易于出現(xiàn)跟蹤丟失的情況等[18]。隨著深度學習的迅速發(fā)展，利用深度學習進行目標跟蹤，是目前該領域的一個研究熱點，如何使用該方法提高跟蹤效果是接下來的研究方向。

參考文獻參考文獻：

[1]尹紅娟，欒帥.三幀差分運動目標檢測算法分析與驗證[J].計算機與數字工程，2017，328（1）：6971，87.

[2]張春林，李小堅.基于幀間差分和背景差分結合的Camshift目標跟蹤算法[J].工業(yè)控制計算機，2014，27（6）：118120.

[3]張宏志，張金換，岳卉，等.基于Camshift的目標跟蹤算法[J].計算機工程與設計，2006，27（11）：20122014.

[4]湯泉.基于AdaBoost和Camshift的人臉檢測與跟蹤[J].電子科技，2016，29（12）：166169.

[5]儲珺，杜立輝，汪凌峰，等.基于局部背景感知的目標跟蹤[J].自動化學報，2012，38（6）：19851995.

[6]劉毅，楚楊杰.局部Camshift跟蹤算法[C].武漢：武漢理工大學，2007：2829.

[7]XIAOWEI HAN，YUAN GAO，ZHENG LU，et al. Research on moving object detection algorithm based on improved three frame difference method and optical flow[C].Fifth International Conference on Instrumentation and Measurement， Computer， Communication and Control，2015.

[8]HONGKUN LIU，JIALUN DAI，RUCHEN WANG，et al. Combining background subtraction and threeframe difference to detect moving object from underwater video[C]. Oceans， 2016：15.

[9]HONGXIA CHU，SHUJIANG YE，QINGCHANG GUO，et al. Object tracking algorithm based on Camshift algorithm combinating with difference in frame[C]. International Conference on Automation and Logistics，2007.

[10]周帥，秦明偉，侯寶臨.結合局部差分的CamShift動目標跟蹤算法[J].自動化儀表，2017，38（2）：14.

[11]司艷麗.膠體推進劑燃燒特性的圖像分析技術[D].南京：南京理工大學，2011：3435.

[12]劉紅，周曉美，張震.一種改進的三幀差分運動目標檢測[J].安徽大學學報：自然科學版，2014，38（6）：5559.

[13]丁亞軍，謝可夫.改進型中值濾波和形態(tài)學組合降噪方法[J].計算機與現(xiàn)代化，2007，138（2）：4142，45.

[14]杜厚鵬，盧官明.基于監(jiān)控視頻的運動車輛檢測與違章分析[D].南京：南京郵電大學，2014：1315.

[15]楊杰，穆平安，戴曙光.一種改進Camshift算法的研究[J].計算機應用與軟件，2014，31（2）：167170.

[16]李萌，鄭娟毅，門瑜.基于幀差法的運動車輛陰影去除算法[J].電視技術，2016，40（10）：1114.

[17]初紅霞，宋起超，王希鳳，等.基于幀間差分與Camshift相結合的目標跟蹤算法[J].彈箭與制導學報，2008，28（3）：8588.

[18]趙春暉，包玉剛，姚冰.基于Kim與Camshift結合的運動目標跟蹤算法[J].黑龍江大學自然科學學報，2010，27（1）：126130.

責任編輯（責任編輯：黃?。?