一種camshift算法與brisk特征點相結合的運動目標跟蹤方法

陳 佳，朱長仁，羅 賓

(1.國防科技大學 電子科學與工程學院 ATR重點實驗室，長沙 410073；2.武警福建總隊直屬支隊，福州 350001)

一種camshift算法與brisk特征點相結合的運動目標跟蹤方法

陳 佳1，2，朱長仁2，羅 賓2

(1.國防科技大學 電子科學與工程學院 ATR重點實驗室，長沙 410073；2.武警福建總隊直屬支隊，福州 350001)

傳統的camshift算法中，當目標移動過快或背景同目標相似時容易導致目標跟蹤丟失，在各種復雜情況下，如何保持跟蹤的有效性及連續性成為眾多研究人員不斷努力的方向。為此，提出了一種brisk特征點檢測與camshift算法相結合的目標跟蹤方法，以及簡化的搜索窗口修正方法，在camshift算法基礎上，通過不同幀的目標上brisk特征點匹配來防止局部最大值的出現以及目標移動過快導致的跟蹤窗口丟失。實驗結果表明：該方法有效地提高了目標跟蹤的連續性和穩定性，與其他特征點結合的算法相比有更好的實時性及精確性。

目標跟蹤;camshift;meanshift;brisk特征點

目標跟蹤是智能視頻研究領域的一個熱點，吸引著越來越多研究人員的關注。傳統的目標跟蹤方法通常分為基于檢測的跟蹤算法，基于模板匹配的跟蹤算法，以及基于統計學習的跟蹤算法。幀差分法是最簡單的一種檢測方法，但其不適用于移動背景下的目標檢測[4]。模板匹配方法采用目標圖像模板同待匹配區域進行相似度計算，把相似度最高的區域作為匹配結果，雖然算法簡單，計算速度快，但相似度匹配的計算受噪音影響比較明顯，對非剛體目標適應性差。基于統計學習的跟蹤方法中，粒子濾波方法采用一系列帶有權值的隨機采樣點來表示所求的目標模型的后驗概率密度函數，再利用這些采樣點和權值來估算目標的最終概率密度，但是不斷的重采樣過程中容易出現粒子的退化現象，導致跟蹤結果的不穩定[5]。均值漂移是一種基于核函數的概率密度方法，其代表性的camshift算法通過計算當前跟蹤窗口中目標模型概率密度最大的方向來不斷調整搜索窗口的中心位置，最終得到運動目標在窗口中的穩定位置。

Camshift[8]算法是一種基于顏色直方圖模型的跟蹤算法，但在目標直方圖模型的建立及目標跟蹤過程中極易受到諸如光線、視角、攝像機參數等環境因素的影響，導致跟蹤誤差或丟失目標，于是，針對camshift的各種改進方法被提出來。文獻[6]將目標的顏色直方圖同LBP紋理特征相結合，通過定義加權融合的函數來表示目標模型，提高了跟蹤的魯棒性。文獻[7]提出了一種融合H、S分量的多維直方圖來表示目標模型，該方法比單純采用一維直方圖能更加精確地表示目標模型。近年來，由于快速局部特征檢測算法的提出，不少研究人員嘗試在跟蹤過程中通過提取目標特征點的方式來防止camshift跟蹤過程中對目標的誤判及丟失。文獻[9]提出了將sift特征融合色彩概率模型來進行目標的匹配，提高了目標跟蹤的魯棒性。文獻[12]采用速度較快的快速魯棒特征(surf特征)提高算法的實時性，但在初次化時必須預先提取目標的特征點，該方法適用于對已知目標的跟蹤。文獻[11]在文獻[9-12]的基礎上，提出了將orb特征檢測同camshift結合起來，通過orb特征點匹配來修正窗口漂移的誤差，并計算特征點尺度和方向的變化來重計算窗口的大小和位移。

然而，對實時跟蹤系統來說，速度與準確性是制約系統性能的兩大問題。傳統的sift、surf特征提取方法雖然精度高，但由于其檢測方法及描述符生成算法較為復雜，在現實應用中對硬件提出了較高的要求。orb算法雖然同surf、sift算法一樣具有尺度不變性，運算速度也有不少改進，但其特征點精確度較易受到噪音影響，不如sift特征點穩固。本文受文獻[10]啟發，提出一種結合brisk特征檢測算法的改進的camshift算法，在提高特征點精度的前提下，進一步優化搜索窗口的修正，可有效避免目標的誤判及跟蹤丟失。

1 camshift跟蹤算法

Camshift算法全稱為連續自適應目標跟蹤算法(continuously adaptive mean-SHIFT)，其本質是在序列圖像上反復調用meanshift算法來實現目標跟蹤。Meanshift算法作為一種非參數的概率密度估計方法，最早在文獻 [2]于1975年提出，當時主要是作為一種聚類方法用于單幅圖像的分割。文獻 [3]對其進行了改進，并用來尋找相似概率密度的模型。文獻[8]通過改進meanshift算法，第一次把camshift算法用于人臉跟蹤過程，至此camshift算法被引入目標跟蹤領域并被廣泛應用。

1.1 Meanshift算法基本原理

Meanshift算法的中心思想是通過建立目標的顏色概率密度模型，在待匹配模板上反復迭代，不斷往概率密度最近似的位置移動，以此尋找相似像素的區域中心。具體為：從每個像素開始，首先估計有相似顏色的鄰近像素點的密度(局部密度)的梯度，而后利用迭代算法求出局部密度的峰值(即重心點)，最后以該峰值為中心，并把位置作為結果輸出。Meanshift作為一種高效的模式匹配算法，不需要進行全局搜索，搜索精度高，其基本流程如下：

1) 選擇跟蹤窗口的大小和初始位置。在meanshift跟蹤算法中，核窗寬的大小(即核函數的定義域大小，即搜索框的大小)起著非常重要的作用。它不但決定了參與meanshift迭代的樣本數量，而且也反映了跟蹤窗口的大小。通常，核窗寬由初始跟蹤窗口的尺寸決定，且在整個跟蹤過程中不再發生變化。

2) 計算跟蹤窗口內的質心或重心。在離散二維(2D)概率分布圖像中，計算某窗口的質心同物理上計算某物體的質心一樣，即利用窗口零階矩M00和(x,y)的一階矩(M10,M01)之間的關系，計算得到窗口的質心。則跟蹤窗口的質心(Xc,Yc)計算公式為

(1)

其中，跟蹤窗口的零階矩為

(2)

跟蹤窗口的一階矩為

(3)

式中 Ic(x,y) 是(x,y)坐標的像素值，x,y的變化范圍為搜索窗大小。

3) 調整跟蹤窗口的中心到質心。

4) 重復第2)步和第3)步，直到跟蹤窗口中心和質心“會聚”，即每次窗口移動的距離小于一定的閾值。

由此，得到的輸出結果為圖像上同目標模板最相似的區域。

1.2 Camshift算法基本原理

Camshift作為基于meanshift改進的一種自適應跟蹤算法，與meanshift的區別是： meanshift每次迭代搜索后，搜索框大小都不會改變，而camshift每次搜索及匹配完畢后，都會根據最近一次目標匹配結果重新計算搜索框大小，來進行下一次meanshift計算。這樣，當非剛體目標在運動中外觀尺寸發生細微變化，或者當跟蹤場景受到光照等其他因素影響時，camshift算法就能在跟蹤過程中表現出比meanshift更好的適應性。其算法步驟如下：

1) 在顏色概率分布圖中初始化一個搜索窗W，其大小為S；

2) 利用meanshift 算法使搜索窗口“收斂”。在概率分布圖像中，通過計算搜索窗口的質心，調整搜索窗口的中心到計算的質心位置。重復該過程，直到“收斂”(即中心的位移動小于給定的閾值)。

3) 重新設置搜索窗口的大小S并計算跟蹤目標的輸出參數。對于顏色概率分布圖像，零階矩代表了跟蹤目標在圖像中的面積，又因為顏色概率分布圖像是256個量化級別的灰度圖像，因此，更新搜索窗口的寬度s和零階矩M00的關系為

(4)

其中零階矩M00由式(3)～(7)給出。并用該窗口初始化下一幀meanshift 的搜索窗口。

4) 跳轉到第二步進入下一幀的循環。直到中心的位移小于閾值。

1.3 Camshift算法的不足之處

Camshift算法盡管采用了動態的跟蹤窗口對跟蹤過程進行優化，但在其跟蹤過程中依靠預先建立的目標顏色概率模型，通過不斷迭代來靠近概率密度最高的點(即目標的質心)，其搜索窗口尺寸的自動調整策略是在上一幀窗口大小的基礎上，長和寬分別向外擴張一定距離，在更大的空間范圍內重新計算目標的質心并估計目標面積。因此，在運動目標經過的背景區域中，如果存在和目標顏色近似的物體或背景塊，且其面積大于或等于當前運動目標尺寸，算法容易在“虛假的目標”上得到概率密度的最大值，搜索框因此不再跟隨真正的目標移動，導致了跟蹤丟失。此外，當運動目標速度突變或過快時，由于超出了搜索框的計算范圍，也容易導致跟蹤目標的丟失。

圖1顯示了序列視頻中，當運動目標接近顏色相似的物體時，camshift算法對目標進行了錯誤的判定，導致目標跟蹤失敗。

圖1 Camshift算法導致的目標跟蹤丟失

2 brisk特征點

Brisk特征點[1]是由Leutenegger于 2011年提出的一種快速的、具有旋轉及縮放尺度不變性的特征點描述及檢測方法。同sift、surf特征點一樣，brisk具有旋轉及尺度變化適應性，但在特征點檢測及描述符生成上都比sift、surf算法更為迅速，同時彌補了orb特征點不具有尺度變化適應性的不足。文獻[13-14]中有詳細的性能對比，下面對原理進行描述。

在特征點檢測方面，brisk算法首先構建尺度空間金字塔，并通過Adaptive and Generic Accelerated Segment Test (AGAST) 角點檢測算子提取連續尺度空間中亞像素級精度的穩定極值點。AGAST 角點檢測算法是對著名的 FAST 角點檢測算法[9]的改進。 AGAST算法流程如下：在一個像素點周邊半徑3的區域里，通過預設閾值T、N，然后對比該像素點同周邊像素點的亮度。假設中心像素點為P,其亮度為Ip,如果周邊有連續N個像素點其亮度大于Ip+T,或有連續N個像素點其亮度小于Ip-T,就把點P標識為空間中的一個角點。

在描述符生成方面，brisk描述符作為一種二進制描述符，主要由2個步驟組成：① 周邊像素采樣對生成；② 特征點描述符生成。首先選取周邊采樣對，即通過選擇合適的角點周邊像素信息來描述角點的唯一性。不同于surf、sift特征點通過將角點周邊區域分塊計算直方圖方式來進行描述，也不同于orb特征點對周邊區域隨機采樣來建立二進制描述符，brisk算法通過以角點為中心40×40 像素塊(見圖2)內構建多個同心圓，對這些圓進行均衡配對。

圖2 以角點為中心40×40像素塊內的同心圓

圖3為角點周邊均衡選取采樣點對，每一對點之間用紅色實線相連表示。brisk特征點的方向是其在匹配過程中具有旋轉不變特性的關鍵，其計算方法如下：

1) 求出角點周邊區域的不變矩

(5)

2) 計算不變矩的重心

(6)

3) 計算特征點的方向，特征點的方向為中心角點同重心的連線所表示的方向，其同水平線夾角表示為

(7)

最后，生成二進制描述符。規則為按照周邊采樣點對先后順序，若左邊的點大于右邊的點，則該采樣對的值設為1；若小于右邊的點，則該采樣對的值設為0。根據選取采樣對的數量及精度要求，一個特征點最終可由128位、256位或512位bit串來表示。

由于brisk特征點在計算速度及精度上顯示出來的優越性，本文采用brisk特征點同camshift算法相結合的方法來進行運動目標的實時跟蹤。

圖3 以角點為中心周邊采樣點對

3 結合brisk特征點匹配的改進的camshift算法

針對camshift算法在相似顏色背景下由于誤判導致跟蹤丟失的問題，本文擬結合brisk特征點對camshift算法進行改進。改進的思路基于以下假設：首先，在大多數日常監控場景中，目標由遠及近運動，或者由近及遠運動，這樣會導致目標尺寸大小的改變，但這種改變一定是平滑漸進的。在基于camshift算法的跟蹤過程中，如果跟蹤窗口的尺寸突然出現了大范圍的變化，則有可能是因為出現局部極大值而導致搜索窗口出現錯判，需要加以驗證。其次，大多數情況下運動目標的移動速度及速度改變量也是平滑漸進的，如果目標運動速度過快，搜索窗口無法有效追蹤目標，那么搜索窗口極有可能在當前窗口的背景區域內就近尋找概率密度最相似的背景區域，并把該區域誤判為目標區域，從而導致跟蹤窗口的尺寸出現較大變化或者跟蹤窗口的位移量超過之前的平均值。為此，本文提出的改進方法是：通過搜索窗口內的brisk特征點匹配來對搜索窗口的大小和位置進行修正。

具體思路為：首先在每一幀跟蹤窗口內先提取brisk特征點，并對跟蹤窗口的尺寸及位移變化量進行記錄；然后在任一幀中，當跟蹤窗口的尺寸或位移變化量超過預設的閾值時，就把當前幀的brisk特征點同上一幀的brisk特征點進行匹配，以重新計算出當前跟蹤窗口的大小和位置，并作為下一次camshift計算的輸入參數。

3.1 特征點提取及匹配

對序列圖像中每一幀中camshift的搜索框內,采用brisk算法提取特征點。

如圖4所示，(a)為對行人目標進行特征提取；(b)為對運動中的車輛目標進行特征提取。通過合適的參數，brisk特征點檢測方法能夠在小尺寸的畫面內提取足夠多的特征點，以利于圖像處理中后續階段的分析和應用。

如圖5所示，提取連續兩幀搜索框內的特征點后，對其進行匹配計算并通過ransac算法剔除錯誤匹配對，保留正確匹配對Matches(left,right)。

圖4 對運動目標提取特征點

圖5 前后兩幀搜索窗口內的特征點匹配

3.2 重新計算搜索窗口大小及位置

3.2.1 觸發條件

為了防止跟蹤誤判，當前幀的搜索窗口尺寸同上一幀相比發生突變時，比如窗口面積變化大于10%或位移加速度超過20%(通過設定閾值T)時，根據當前有效匹配特征點計算投影變換矩陣，觸發條件的公式表示如下：

條件1

(8)

其中：Sn為當前幀跟蹤窗口面積；Sn-1為上一幀跟蹤窗口面積；Ts為面積改變量預設閾值。

當前幀搜索窗口的位移(以窗口中心坐標為依據)變化速率改變大于一定閾值時(比如前幾幀的平均位移量的30%)，重新計算并確定當前跟蹤窗口大小及位置，公式表示如下：

條件2

計算絕對位移

(9)

計算位移改變量

(10)

其中：ΔP為當前跟蹤窗口中心同上一幀的跟蹤窗口中心的絕對位移量；Tp為預設的位移量改變閾值。當觸發條件滿足時，進行下一步計算投影變換矩陣并重新計算當前幀中跟蹤窗口的大小及位置。

3.2.2 計算投影變換矩陣

Homography變換矩陣是一個3×3的單應性矩陣，用來描述圖像A通過尺度、旋轉、仿射變換到圖像B后圖像上各點的對應關系。當求得兩幅圖像中的匹配點Maches(left)、Maches(right)后，如果匹配點對數大于等于3，即可以計算出兩幅圖像之間的Homography變換矩陣H。

3.2.3 修正窗口大小及位置

計算出變換矩陣H后，就可以直接通過前一幀搜索窗口4個角的坐標，計算出修正后搜索窗口4個角的新坐標。其公式為：

corner2(x,y,1)=H×corner1(x,y,1)

(11)

3.3 簡化的窗口大小及位置計算方法

考慮到幀與幀之間運動目標自身運動及環境影響導致的形狀變化非常微小，對整個跟蹤窗口的影響不大，如果采用傳統的單映矩陣公式來計算需要耗費一定的計算資源。本文提出一種簡化的方法重新計算跟蹤窗口的大小及位置。

設當前幀跟蹤窗口內的特征點集為Fn,前一幀窗口內為fn(Fn,fn均為經過濾后完全匹配的特征點)。前一幀跟蹤窗口的寬、高分別為w，h,當前窗口的寬高分別為W，H,窗口旋轉角度為θ。

(12)

(13)

(14)

通過以上公式，可以近似得到新跟蹤窗口的大小，無需計算矩陣投影公式。該方法簡單、計算速度快，其誤差對新窗口在下一步camshift迭代運算的影響微小。

最后，把計算得到的新跟蹤窗口的尺寸及位置作為下一次camshift迭代的初始化窗口，繼續進行camshift運算。

跟蹤算法流程見圖6。

圖6 跟蹤算法流程

4 實驗

為進一步驗證本文提出算法的有效性，采用pets 2001 dataset 公開數據集，分別對dataset2視頻中的行人和車輛的跟蹤進行了測試。實驗環境為華碩筆記本電腦、intel p3處理器、2GB內存、vs2010平臺。

4.1 跟蹤效果對比

主要對比原始camshift算法同本文改進的算法對目標跟蹤的結果。

圖7為使用camshift算法對測試視頻中的車輛進行跟蹤的結果。如圖7所示，從2 530幀開始，由于受到背景停放車輛顏色相似的影響，搜索窗口在自適應過程中進行了錯誤的判定，導致目標跟蹤失敗。圖8為采用本文算法的跟蹤結果，通過采用特征點匹配進行窗口及位置的修正，有效避免了目標的錯誤判定。

圖8 本文算法對車輛跟蹤結果

圖9為使用camshift算法對行人進行跟蹤的結果。從第2 259幀開始，跟蹤窗口受到背景顏色的干擾出現了錯誤的判定。圖10為采用本文算法的跟蹤結果，通過特征點匹配及窗口重修正，有效避免了跟蹤錯誤。

圖9 原始camshift算法對行人跟蹤結果

圖10 本文算法對行人跟蹤結果

4.2 跟蹤速度及精度對比

為比較算法的跟蹤速度，本文采用結合不同特征檢測算子對同一測試視頻，同一跟蹤目標在有效跟蹤時段內每一幀的平均計算時間進行對比。如表1所示，通過對比可以看出：結合brisk特征點的算法在速度上超過surf特征點，但是會比orb特征點稍慢。

表1 結合不同特征檢測算法跟蹤速度對比

表2 不同算法跟蹤精確性對比

為比較算法精確性，本文參考文獻[15]中的運動目標軌跡精確性評估方法，提取運動目標在每一幀的質心坐標和跟蹤算法中每一幀跟蹤窗口的中心位置坐標，然后計算兩者之間的距離，最后計算出各自總測試幀數的平均值進行比較。如表2所示，通過對比可以看出，本文提出的算法在跟蹤精確性上比結合orb特征點的算法有明顯的提高。

5 結束語

本文主要針對傳統camshift算法的不足之處，結合最新的brisk特征點檢測方法，提出了一種改進的camshift算法。當目標同背景顏色近似導致跟蹤丟失時，能夠通過特征點匹配的方式進行驗證判斷，并通過前后特征點集重新計算搜索窗口的尺寸及位置。但是，brisk特征點僅從灰度圖像上尋找特征點，并且在運動目標尺寸過小或者序列圖像清晰度不高的情況下，難以提取出足夠數量有效的特征點實施檢測，影響了特征匹配及搜索窗口修正的精確性。如何使本文算法具有更多的適應性是下一步研究的方向。

[1] LEUTENEGGER S, CHLI M, SIEGWART R Y.BRISK:Binary robust invariant scalable keypoints[C]//2011IEEE International Conference on Computer Vision.2011.Spain:[s.n.],2011:2548-2555.

[2] FUKUNAGA K,HOSTETLER L.The estimation of the gradient of a density function,with applications in pattern recognition[J].IEEE Trans Info.Theory,1975,21:32-40.

[3] CHENG Y.Mean shift,mode seeking,and clustering[J].IEEE Trans.Pattern Anal Machine Intelligence,1995,17:790-799.

[4] 張娟,毛曉波,陳鐵軍.運動目標跟蹤算法研究綜述[J].計算機應用研究,2009(12):4407-4410.

[5] 黃凱奇,陳曉棠,康運鋒,等.智能視頻監控技術綜述[J].計算機學報,Chinese Journal of Computers,2015(6).

[6] YIN J,HAN Y,LI J,et al.Research on real-time object tracking by improved Camshift[Z].International Symposium on Computer Network and Multimedia Technology,Wuhan,2009:1-4.

[7] SUN L,WANG B R,IKENAGA T.Real-time non-rigid object tracking using CAMShift with weighted back projection[C]//International Conference on Computational Science and Its Applications.Fukuoka:[s.n.],2010:86-91.

[8] BRADSKI G R.Computer vision face tracking for use in a perceptual user interface[J].Intel Technology Journal,2nd Quarter,1998.

[9] QIU X N,LIU S R,LIU F.An adaptive kernel based target tracking method based on multiple features fusion[J].EEJ Transactions on Electrical and Electronic Engineering,January 2012,7(1):91-97.

[10]ELMAR MAIR,GREGORY D,HAGER,et al.Adaptive and Generic Corner Detection Based on the Accelerated Segment Test[J].Computer Vision-ECCV 2010 Lecture Notes in Computer Science,2010,6312:183-196.

[11]鐘華民,王偉,張慧華.結合ORB特征和色彩模型的視覺跟蹤算法[J].模式識別與人工智能，2005(1):90-96.

[12]YUNJI ZHAO,HAILONG PEI,HONGBO ZHOU.Improved Vision-Based Algorithm for Unmanned Aerial Vehicles Autonomous Landing[J].Journal of Multimedia,2013,8(2):90.

[13]SCHAEFFER C.A Comparison of Keypoint Descriptors in the Context of Pedestrian Detection:FREAK vs.SURF vs.BRISK[Z].International Journal of Computer Applications,2014.

[14]MIKSIK O,MIKOLAJCZYK K.Evaluation of Local Detectors and Descriptors for Fast Feature Matching[C]//Pattern Recognition (ICPR),2012 21st International Conference.Japan:[s.n.],2012.

[15]李鵬飛,陳朝武,李曉峰.智能視頻算法評估綜述[J].計算機輔助設計與圖形學學報,2010(2):352-360.

(責任編輯 楊黎麗)

A Combination of Camshift Algorithm and Brisk Feature Point for Real Time Moving Target Tracking

CHEN Jia1,2, ZHU Chang-ren2, LUO Bin2

(1.ATR Key Laboratory, College of Electronic Science and EngineeringNational University of Defense Technology, Changsha 410073, China;2.The Fujian Province Armed Police Corps Directly Under Detachment Team,Fuzhou 350001, China)

In traditional camshift algorithm, when the target moves too fast or the background has similar color, it will lead to the loss of target easily, and how to maintain the effectiveness and continuity of the tracking becomes the direction for many researchers under various complex situations. Therefore, we proposed a improved camshift algorithm based on combination of camshift and brisk feature point and a simplified search window correction method, which prevent the emergence of a local maximum and the loss of tracking window with matching different frames on the goal of your brisk feature point. Experiments show that our method effectively improve the continuity and stability of target tracking. In combination with other feature points algorithm, it has better real-time comparison and accuracy

target tracking; camshift; meanshift; brisk feature point

2015-4-20 作者簡介：陳佳(1983—),男,碩士研究生,主要從事圖像處理與模式識別研究。

陳佳，朱長仁,羅賓.一種camshift算法與brisk特征點相結合的運動目標跟蹤方法[J].重慶理工大學學報(自然科學版)，2015(12):112-119.

format：CHEN Jia, ZHU Chang-ren, LUO BinA Combination of Camshift Algorithm and Brisk Feature Point for Real Time Moving Target Tracking [J].Journal of Chongqing University of Technology(Natural Science)，2015(12):112-119.

10.3969/j.issn.1674-8425(z).2015.12.019

TP301.6

A

1674-8425(2015)12-0112-08