一種改進(jìn)的CAMShift目標(biāo)跟蹤算法

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

中圖分類號(hào):TN911-34;TP39141文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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

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

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

1 算法關(guān)鍵部分論述

1.1 色彩空間

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

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

1.2 Mean Shift算法

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

質(zhì)心可通過(guò)計(jì)算零階矩和一階矩得到[1]，在此不加贅述。

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

1.3 自適應(yīng)改變窗口大小

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

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

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

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

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

θ=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

可以得出被跟蹤目標(biāo)的長(zhǎng)軸l和短軸w。

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

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

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

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

1.4 算法流程圖

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

本算法在建立被跟蹤目標(biāo)的顏色概率模型后，可將視頻圖像轉(zhuǎn)化為顏色概率分布圖，然后在第一幀圖像初始化一個(gè)矩形搜索窗，對(duì)以后的每一幀圖像，CAMShift能夠自動(dòng)調(diào)節(jié)搜索窗的大小和位置，定位被跟蹤目標(biāo)的中心和大小，并且用當(dāng)前幀定位的結(jié)果來(lái)預(yù)測(cè)下一幀圖像中目標(biāo)的中心和大小。

圖1 CAMShift算法流程圖

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

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

(2) 計(jì)算零階矩;

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

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

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

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

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

2.1 軟件參數(shù)調(diào)整

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

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

2.2 硬件參數(shù)調(diào)整

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

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

3 本文算法改進(jìn)

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

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

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

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

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

通過(guò)實(shí)踐表明，改進(jìn)的CAMShift算法能長(zhǎng)時(shí)間地穩(wěn)定跟蹤某一目標(biāo)，實(shí)時(shí)性能好，提高了抗噪性能，防止了錯(cuò)誤跟蹤，并提高了跟蹤的準(zhǔn)確度，跟蹤效果比較理想。

4 算法驗(yàn)證及分析

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

圖2 目標(biāo)跟蹤結(jié)果圖

5 結(jié) 語(yǔ)

本文提出一種改進(jìn)的CAMShift目標(biāo)跟蹤算法。經(jīng)實(shí)踐驗(yàn)證，改進(jìn)的算法可以實(shí)現(xiàn)復(fù)雜背景下對(duì)運(yùn)動(dòng)目標(biāo)的快速準(zhǔn)確的跟蹤，跟蹤效果很好。

參考文獻(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的目標(biāo)跟蹤算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27(11):2012-2014.

[6]吳慧敏，鄭曉勢(shì).改進(jìn)的高效CAMShift跟蹤算法[J].計(jì)算機(jī)工程與應(yīng)用，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]徐力群，吳曉娟.基于顏色概率模型的實(shí)時(shí)手勢(shì)跟蹤算法[J].計(jì)算機(jī)工程與科學(xué)，2005，27(10):44-47.

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

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

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