一種改進的CAMShift目標跟蹤算法

摘 要:為了實現(xiàn)復雜背景下對運動目標的快速準確跟蹤，在闡述CAMShift算法的原理和實現(xiàn)的基礎上，提出一種改進的CAMShift目標跟蹤算法。經(jīng)實踐驗證，改進的算法可以實現(xiàn)復雜背景下對運動目標快速準確的跟蹤，并且跟蹤效果很好。關鍵詞:目標跟蹤; CAMShift算法; 顏色概率分布;運動目標

中圖分類號:TN911-34;TP39141文獻標識碼:A

文章編號:1004-373X(2010)16-0106-03

Improved CAMShift Algorithm of Target Tracking

LI Hong-hai

(Huaiyin Institute of Technology， Huai’an 223003， China)

Abstract: To realize the rapid and accurate tracking of moving objects， an improved CAMShift algorithm of target tracking is brought forward based on the elaboration for the principle of CAMShift algorithm. The practical application proves that the improved algorithm can realize the rapid and accurate tracking of moving objects in the complicated background， and its tracking effect is good.Keywords: target tracking; CAMShift algorithm; color probability distribution; moving object

收稿日期:2010-03-26

運動目標跟蹤的目的就是通過對傳感器拍攝到的圖像序列進行分析，計算出目標在每幀圖像上的位置，給出目標速度的估計。可靠性和精度是跟蹤過程中的2個重要指標。對于尺寸較小，機動性要求不高的目標，利用質心跟蹤可以獲得很好的效果，在保證跟蹤效果的精度和穩(wěn)定性的同時，跟蹤的實時性要求也可以得到滿足。CAMShift(continuously adaptive mean-shift)目標跟蹤算法是質心跟蹤算法中運用較多，效果較好的一種，CAMShift算法的含義是連續(xù)自適應均值平移，它主要通過視頻圖像中運動物體的顏色信息來達到跟蹤的目的。

文中文獻均介紹CAMShift算法的應用，其中文獻[1-2]將CAMShift應用于文字識別;文獻[3]將CAMShift算法應用于臉部部分遮擋的頭部姿勢確定;文獻[4-6]將CAMShift算法應用于實時的臉部和物體跟蹤;文獻[7-12]將CAMShift算法應用于快速二維手跟蹤和手勢識別。但是幾乎很少有將CANSHIFT算法應用于較為復雜背景下的目標跟蹤。本文在闡述CANSHIFT算法的基礎上，對原有算法進行適當改進，用于復雜背景下的運動目標跟蹤。經(jīng)實踐證明，跟蹤效果較好。

1 算法關鍵部分論述

1.1 色彩空間

首先需要建立顏色概率模型。在計算機圖像處理中常用的顏色空間有RGB，YUB，HSV，HIS等。多數(shù)目標物對HSV(色調、色飽和度、亮度)空間的H分量比較敏感，所以在此用H分量的直方圖建立色彩概率模型。

將被跟蹤目標的每個像素從RGB空間轉換到HSV空間(對于輸入是JPEG圖情況，需要先把JPEG圖轉換為RGB圖)，統(tǒng)計其H分量的直方圖，并對直方圖進行歸一化處理，即可以得到被跟蹤目標的色彩在H空間的概率分布，稱之為色概率查找表。利用色概率查找表，就可以將當前圖像轉化為色彩概率分布圖。HSV色彩空間存在的問題是:當色飽和度S過低，亮度V過低或過高時，H分量容易受到噪聲的干擾，導致跟蹤失敗。解決的方法是對S分量設最低閾值，對V分量設最低、最高閾值，忽略掉不滿足閾值條件的像素點，使跟蹤更加可靠。

1.2 Mean Shift算法

Mean Shift(即均值平移算法)是一種計算最優(yōu)解的實用算法，具有快速和有效的特點。利用Mean Shift算法可以確定搜索區(qū)域中心，通過多次迭代，最終使搜索區(qū)域的質心收斂到某個位置(即相鄰2次迭代結果之差小于設定閾值)，該位置被定為搜索區(qū)域的中心，也就是算法得出的被跟蹤目標的中心。

質心可通過計算零階矩和一階矩得到[1]，在此不加贅述。

該算法僅用于靜態(tài)圖像的目標的搜索，當被跟蹤目標大小改變或角度旋轉后就無法保證正確的跟蹤。所以對于實時的目標跟蹤系統(tǒng)，必須動態(tài)地改變搜索窗口的大小。

1.3 自適應改變窗口大小

在用Mean Shift算法求得被跟蹤目標中心后，適當擴大搜索窗口的區(qū)域，然后通過計算二階矩，可得到被跟蹤目標的長軸、短軸和方向角，公式如下所示。

M20=∑x∑yx2I(x，y)(1)

M02=∑x∑yy2I(x，y)(2)

M11=∑x∑yxyI(x，y)(3)

式中:I(x，y)為色彩概率圖中坐標為(x，y)的像素值。由此可得，被跟蹤目標與水平方向夾角為:

θ=12arctan2(M11/M00-xcyc)(M20/M00-x2c)-(M02/M00)-y2c)(4)

令:

a=M20M00-x2c，b=2M11M00-xcyc，c=M02M00-y2c

可以得出被跟蹤目標的長軸l和短軸w。

l=(a+c)+b2+(a-c)22(5)

w=(a+c)-b2+(a-c)22(6)

由此可精確定位出被跟蹤目標所在的位置、大小和方向。

當用CAMShift算法對特定顏色的目標進行跟蹤時，不必計算每幀圖像所有像素點的顏色概率分布，只需計算比當前搜索窗大一些區(qū)域內(nèi)像素點的顏色概率分布，這樣可節(jié)省很多的計算量。視頻序列一幀一幀變化時，就形成了連續(xù)的跟蹤。

1.4 算法流程圖

CAMShift算法的流程圖如圖1所示。由流程圖可以看出，為了使用CAMShift算法跟蹤特定的目標，需要把每幀圖像轉化為顏色概率分布圖。

本算法在建立被跟蹤目標的顏色概率模型后，可將視頻圖像轉化為顏色概率分布圖，然后在第一幀圖像初始化一個矩形搜索窗，對以后的每一幀圖像，CAMShift能夠自動調節(jié)搜索窗的大小和位置，定位被跟蹤目標的中心和大小，并且用當前幀定位的結果來預測下一幀圖像中目標的中心和大小。

圖1 CAMShift算法流程圖

CAMShift算法是一種動態(tài)變化分布的密度函數(shù)梯度估計非參數(shù)方法。其算法主要過程如下:

(1) 在顏色概率分布圖中選取大小為s的搜索窗，W，H為搜索區(qū)域的長和寬;

(2) 計算零階矩;

(3) 計算搜索窗的質心;

(4) 將搜索區(qū)域中心移到該質心處，并大小不變，然后判斷質心是否收斂(質心變化小于給定的閾值);

(5) 重復(2)~(4)直到收斂;

(6) 返回x，y，W，H及搜索結果的主軸方向和長度，并輸出反映搜索結果的JPEG圖。

2 軟硬件參數(shù)調整

2.1 軟件參數(shù)調整

前面已經(jīng)提到，HSV色彩空間中當色飽和度S過低，亮度V過低或過高時，H分量容易受到噪聲的干擾，導致跟蹤失敗。在實際應用系統(tǒng)中可根據(jù)當時的光照條件設置相應的閾值。

在HSV色彩體系中，H分量的范圍是0～360，代表不同的色調。在目標跟蹤過程中，如果已經(jīng)知道被跟蹤目標的色調大致范圍，在計算該目標的色彩直方圖時可只取相應的某一段范圍。這樣既可減少跟蹤算法的計算量，又能提高跟蹤結果的可靠性。

2.2 硬件參數(shù)調整

攝像機的視野應該足夠大，使圖像始終包含被跟蹤目標。同時，攝像機的自動增益調節(jié)、曝光時間也應正確設置，保證拍攝圖像的亮度適中，從而提高后續(xù)算法的可靠性。

由于CAMShift算法具有相當?shù)聂敯粜裕⒉灰髷z像機針對某種特定的跟蹤色彩，也不需要特別校準鏡頭。

3 本文算法改進

在實際跟蹤過程中，當物體運動速度較慢，且目標背景較為簡單時，CAMShift算法可以實現(xiàn)對某些目標的良好跟蹤。但是在跟蹤過程中，由于某些原因，如目標的速度和姿態(tài)不斷變化，出現(xiàn)目標背景的對比度較低，目標的信噪比低等情況時，會出現(xiàn)錯誤。同時由于目標在一直運動，對選擇初始跟蹤目標的搜索區(qū)域中心比較困難，而且常會出現(xiàn)跟蹤失敗或跟蹤錯誤的情況。

在實時成像跟蹤系統(tǒng)中，可以根據(jù)目標以前的運動軌跡估計下一匹配點，并以估計的匹配點為中心，進行細致的匹配搜索，縮小匹配范圍，減少運算量，本文選用綜合預測器。

(k+1)=WL(k+1/k)+(1-W)Q(k+1/k)

式中:L(k+1/k)為2點線性預測器;Q(k+1/k)為5點平方預測器，W為權函數(shù)。

同時，當被跟蹤目標移出屏幕或者有其他對象遮擋時，CAMShift跟蹤器的搜索窗口將會越來越小。這樣，即使跟蹤對象重新出現(xiàn)在屏幕上，跟蹤也無法繼續(xù)。為了進一步保證能夠實現(xiàn)實時準確的跟蹤，增加了一個啟發(fā)式規(guī)則來解決這個問題。因此當搜索窗口比較小(比如5像素×5像素)時，把搜索窗口設置為整個圖像。這樣一來，當對象再次出現(xiàn)時，逐漸變小的窗口會很快框住對象。

通過實踐表明，改進的CAMShift算法能長時間地穩(wěn)定跟蹤某一目標，實時性能好，提高了抗噪性能，防止了錯誤跟蹤，并提高了跟蹤的準確度，跟蹤效果比較理想。

4 算法驗證及分析

在對本文算法進行驗證時，跟蹤目標的背景相對復雜，在對比度較小的F117戰(zhàn)斗機飛行序列圖像跟蹤過程中，飛機按照一些隨機曲線進行飛行，它的飛行姿態(tài)也在不斷變化，跟蹤區(qū)域的亮度和對比度等也會發(fā)生一定的變化，飛機在飛行的過程中直接對跟蹤目標的區(qū)域進行選擇。從跟蹤的過程中選取其中6幀。圖2(a)是為開始跟蹤時的圖像，飛機向右上角飛并轉彎向右下角飛行，圖像如圖2(b)所示;飛機飛到右下角之后又折回向左上角飛行，圖像如圖2(c)所示;在圖2(d)、(e)、(f)各幀圖像中可以發(fā)現(xiàn)，飛機的飛行姿態(tài)或大小都發(fā)生了一定的變化，而且背景圖像的亮度和對比度也發(fā)生了一定的變化。同時，可以由圖像中看出，整個目標的對比度很低，但是本算法均能持續(xù)準確穩(wěn)定地完成跟蹤過程，且具有很好的實時性，也證明了本算法的有效性。

圖2 目標跟蹤結果圖

5 結 語

本文提出一種改進的CAMShift目標跟蹤算法。經(jīng)實踐驗證，改進的算法可以實現(xiàn)復雜背景下對運動目標的快速準確的跟蹤，跟蹤效果很好。

參考文獻

[1]KIM Kwang In， JUNG Keechul， KIM Jin Hyung. Texture-based approach for text detection in images using support vector machines and continuously adaptive mean shift algorithm[J]. IEEE Trans. on Pattern Analysis and Machine Intelligence， 2003， 25(12): 1631-1639.

[2]Mathias K， TURK Matthew. Fast 2D hand tracking with flocks of features and multi-cue integration[C]//proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops.[S.l.]: CVPRW， 2004: 1063-1069.

[3]WENZEL M T， SCHIFFMANN W H. Head pose estimation of partially occluded faces[C]//Proceedings of the Second Canadian Conference on Computer and Robot Vision. [S.l.]: CRV， 2005: 111-117.

[4]BRADSKI Gary R. Real-time face and object tracking as a component of a perceptual user interface[J/OL]. [2010-05-03]. http://d.wanfangdata.com.cn.

[5]張宏志，張金換，岳卉，等.基于 CAMShift的目標跟蹤算法[J].計算機工程與設計，2006，27(11):2012-2014.

[6]吳慧敏，鄭曉勢.改進的高效CAMShift跟蹤算法[J].計算機工程與應用，2009，45(27):178-180.

[7]CAUCHOIS Cyril， CHAUMONT Fabrice de， MARHIC Bruno， et al. Robotic assistance: an automatic wheelchair tracking and following functionality by omnidirectional vision[C]//2005 IEEE/RSJ International Conference on Intelligent Robots and Systems.[S.l.]: IEEE， 2005: 858-864.

[8]徐力群，吳曉娟.基于顏色概率模型的實時手勢跟蹤算法[J].計算機工程與科學，2005，27(10):44-47.

[9]吳曉娟，翟海亭，王磊，等.一種改進的CAMShift手勢跟蹤算法[J].山東大學學報:工學版，2004，34(6):120-124.

[10]湯志彥，馮哲，適用于機器人視覺的手勢識別系統(tǒng)[J].計算機工程與應用，2005，41(16):51-54.

[11]王亮亮，孫即祥，譚志國.基于人臉檢測和CAMShift算法的人臉跟蹤系統(tǒng)[J].微計算機應用，2008，29(2):14-17.