目標(biāo)跟蹤中巴氏系數(shù)誤差的分析及其消除方法

1、目標(biāo)跟蹤中巴氏系數(shù)誤差的分析及其消除方法*國(guó)家自然科學(xué)基金(60234030, 60773110), 國(guó)家基礎(chǔ)研究項(xiàng)目(A1420060159)作者簡(jiǎn)介：文志強(qiáng)(1973),男,湖南湘鄉(xiāng)人,博士研究生,主要研究領(lǐng)域?yàn)槟繕?biāo)檢測(cè)目標(biāo)跟蹤. Email:zhqwen20001,聯(lián)系地址:湖南長(zhǎng)沙中南大學(xué)鐵道校區(qū)研究生樓310號(hào),郵編:410075.聯(lián)系電話0731-2655993;蔡自興(1938),男,福建莆田人,教授,博士生導(dǎo)師, 主要研究領(lǐng)域?yàn)槿斯ぶ悄?進(jìn)化計(jì)算,智能控制,移動(dòng)機(jī)器人協(xié)作與導(dǎo)航等.文志強(qiáng)1,2 蔡自興11 (中南大學(xué) 信息科學(xué)與工程學(xué)院 湖南 長(zhǎng)沙 4

2、10083)2 (湖南工業(yè)大學(xué) 計(jì)算機(jī)與通信學(xué)院 湖南 株洲 412008)摘要：在mean shift 的目標(biāo)跟蹤方法中，Taylor公式的近似展開會(huì)造成優(yōu)化過程中Bhattacharyya系數(shù)值的誤差，這種誤差會(huì)給目標(biāo)跟蹤帶來偏差，同時(shí)不適合快速運(yùn)動(dòng)目標(biāo)的跟蹤。針對(duì)Bhattacharyya系數(shù)的Taylor公式近似表示情形，研究了這種近似表示引起的系數(shù)誤差和對(duì)目標(biāo)跟蹤的影響，在此基礎(chǔ)上，將Bhattacharyya系數(shù)的優(yōu)化問題轉(zhuǎn)化為求解約束優(yōu)化問題，從而提出一種改進(jìn)的目標(biāo)跟蹤方法，以達(dá)到提高目標(biāo)跟蹤的精度，而且證明了該改進(jìn)方法的收斂性。實(shí)驗(yàn)表明本文方法對(duì)于快速運(yùn)動(dòng)目標(biāo)的跟蹤具有更好的跟

3、蹤精度。關(guān)鍵字：mean shift, 目標(biāo)跟蹤, 目標(biāo)模型, Bhattacharyya系數(shù)中圖法分類號(hào):TP3011引言Mean shift是一個(gè)由Fukunaga和Hostetler在1975年提出的一種無監(jiān)督聚類方法，它使每一個(gè)點(diǎn)“漂移”到密度函數(shù)的局部極大值點(diǎn)。1995年，Cheng1重新研究了mean shift，提出了更一般的表達(dá)形式并預(yù)示該算法在聚類和全局優(yōu)化方面的巨大潛力。Comaniciu在1999年對(duì)mean shift做了應(yīng)用方面的研究2。自此以后，mean shift已廣泛應(yīng)用于目標(biāo)跟蹤3-5、圖像分割6、聚類分析7等領(lǐng)域，已成為當(dāng)前研究的熱點(diǎn)問題。Comaniciu

4、在34中首先將mean shift算法應(yīng)用到目標(biāo)跟蹤領(lǐng)域中來，他利用Bhattacharyya系數(shù)作為目標(biāo)模型與候選目標(biāo)之間的相似性度量標(biāo)準(zhǔn)，用mean shift算法來搜索最優(yōu)候選目標(biāo)，獲得了很好的跟蹤效果。此后，有更多的研究者投入到了此項(xiàng)研究之中816。文獻(xiàn)4中給出的mean shift算法采用核直方圖作為圖像特征的描述方式，沒有考慮圖像的空間信息。為了克服特征信息不足造成偏差缺點(diǎn)，需要尋找一種可行的圖像空間信息和顏色信息的綜合表達(dá)方法，很多文獻(xiàn)在這方面做了大量工作810。文獻(xiàn)8提出一種空域特征空間中的相似性度量方法，允許mean shift算法跟蹤更一般的運(yùn)動(dòng)目標(biāo)；文獻(xiàn)9提出了一個(gè)魯棒的

5、、實(shí)時(shí)的高斯圓柱形顏色模型，通過mean shift實(shí)現(xiàn)目標(biāo)跟蹤以抗不規(guī)則光照變化；文獻(xiàn)10在顏色矩方圖中引入旋轉(zhuǎn)方向參數(shù)，采用5-degrees of freedom(DOF)的顏色矩方圖，可以跟蹤旋轉(zhuǎn)的運(yùn)動(dòng)目標(biāo)。另外，不同的圖像特征描述方法適合于不同的場(chǎng)合或背景，因此根據(jù)場(chǎng)景來自適應(yīng)選擇特征描述方法是非常值得研究的內(nèi)容，如文獻(xiàn)11提出一種目標(biāo)跟蹤中適合于評(píng)價(jià)多特征的在線特征選擇機(jī)制，自適應(yīng)調(diào)整特征集以提高跟蹤性能。其次，目標(biāo)特征的構(gòu)造、組合及更新需要根據(jù)實(shí)際情況來確定，在目標(biāo)跟蹤中引入機(jī)器學(xué)習(xí)方法是一種行之有效的方法。對(duì)場(chǎng)景進(jìn)行一定時(shí)間的學(xué)習(xí)后確定相應(yīng)特征和參數(shù)，可提高對(duì)周圍環(huán)境的適應(yīng)性，

6、例如文獻(xiàn)12對(duì)目標(biāo)的顏色進(jìn)行聚類分析，通過矩陣分解和正交變換建立一種新的顏色模型來提高mean shift跟蹤的性能；文獻(xiàn)13把跟蹤問題看成是二分類問題，結(jié)合adaBoost和弱分類器構(gòu)成一個(gè)強(qiáng)分類器，通過在線訓(xùn)練來提高mean shift跟蹤對(duì)不同場(chǎng)景的適應(yīng)性。最后，研究集中在窗口自動(dòng)選取，如Comaniciu14和彭寧嵩15分別提出了針對(duì)mean shift算法的窗口自動(dòng)選取方法。雖然對(duì)mean shift跟蹤算法進(jìn)行了大量研究，但是該算法仍然存在跟蹤偏差或者完全跟不上目標(biāo)的情況?；趍ean shift的目標(biāo)跟蹤方法3, 4通過對(duì)Bhattacharyya系數(shù)作Taylor近似展開獲得m

7、ean shift的迭代公式，當(dāng)跟蹤目標(biāo)的位置在兩幀圖像之間變化不大時(shí)，這種Taylor近似展開可以獲得好的跟蹤效果，但是當(dāng)目標(biāo)快速運(yùn)動(dòng)或突然轉(zhuǎn)向時(shí)，這種系數(shù)近似的誤差就較大，應(yīng)用mean shift算法計(jì)算所得到的局部最優(yōu)位置和應(yīng)用原始的Bhattacharyya系數(shù)窮舉搜索得到的位置之間存在誤差。為了克服這種誤差，本文對(duì)由于Bhattacharyya系數(shù)的Taylor近似公式表示所引起的誤差進(jìn)行了分析和研究，并在此基礎(chǔ)上推導(dǎo)出一種降低誤差方法。與原始的mean shift 方法不同的是，該方法僅僅更改了權(quán)值的計(jì)算方法，不會(huì)增加算法的時(shí)間復(fù)雜度。提出的方法適合于目標(biāo)突然改變方向或快速運(yùn)動(dòng)的情

8、形。本文的安排如下：第1節(jié)是全文的引言；第2節(jié)介紹基于mean shift的目標(biāo)跟蹤方法；第3節(jié)對(duì)Bhattacharyya系數(shù)誤差進(jìn)行了分析；第4節(jié)提出目標(biāo)跟蹤方法；第5節(jié)為實(shí)驗(yàn)結(jié)果及分析；第6節(jié)是全文的結(jié)束語。2基于mean shift的目標(biāo)跟蹤方法2.1目標(biāo)模型視頻目標(biāo)跟蹤是mean shift算法應(yīng)用的一個(gè)重要方面，大多文獻(xiàn)沿用Comaniciu3, 4的方法，采用Bhattacharyya系數(shù)作為相似性度量標(biāo)準(zhǔn)，使用mean shift算法來獲取目標(biāo)位置。基于mean-shift的跟蹤算法將顏色核直方圖作為目標(biāo)特征的描述，假定目標(biāo)模型和候選目標(biāo)特征分別表示為：和，其中y是候選目標(biāo)區(qū)域

9、的中心位置，且，m為特征值bin的個(gè)數(shù)。目標(biāo)模型與候選目標(biāo)的相似性采用Bhattacharyya系數(shù)來衡量，即。為了得到一個(gè)相對(duì)于空間位置y平滑的相似函數(shù)，目標(biāo)模型的特征分布表示為：，其中()為Kronecker delta函數(shù)，是歸一化的目標(biāo)模型像素位置，歸一化后目標(biāo)模型中心像素的位置為0，為像素點(diǎn)到像素特征的映射，是歸一化常數(shù)。相應(yīng)的候選目標(biāo)的特征分布為：，其中Ch是歸一化常數(shù)，nh為候選目標(biāo)區(qū)域中的像素總數(shù)，這里k(·)稱為核函數(shù)，h為帶寬。2.2基于Bhattacharyya系數(shù)的目標(biāo)跟蹤相似函數(shù)定義了目標(biāo)和候選目標(biāo)的距離，為了提供各種目標(biāo)的比較，距離應(yīng)有一個(gè)度量函數(shù)。定義兩

10、個(gè)離散分布之間的距離如下： （1）式中，為q和p之間的Bhattacharyya系數(shù)。最小化（1）式相當(dāng)于最大化Bhattacharyya系數(shù)。在處使用Taylor展開式，得到的線性近似式如下： （2）當(dāng)候選目標(biāo)從初始值不發(fā)生急劇變化時(shí)，上述近似成立。假設(shè)，對(duì)于所有的成立，可得 （3）式中，。（3）式的第二部分最大化，可得mean shift算法的迭代公式如下： （4）式中，g(x)= - k(x)。首先初始化y0，計(jì)算wi，并重復(fù)(4)式的計(jì)算，直到|yi+1-yi|<或大于預(yù)定的最大迭代次數(shù)，為預(yù)先設(shè)定的大于0的正數(shù)，得到的最終位置即為目標(biāo)所在的位置。在目標(biāo)跟蹤時(shí)，目標(biāo)模型必須進(jìn)行自

11、適應(yīng)更改，以適應(yīng)光照、環(huán)境的變化，如采用Kalman濾波更新目標(biāo)模型16。3系數(shù)誤差分析（2）式雖然對(duì)運(yùn)動(dòng)目標(biāo)不發(fā)生急劇變化的情形不會(huì)產(chǎn)生很大影響，但對(duì)于急劇變化的情形，（2）的近似表示會(huì)造成很大的偏差。為了對(duì)Taylor近似表示造成的誤差進(jìn)行研究，給出下面兩個(gè)定理。定理1：如果Bhattacharyya系數(shù)用（2）式近似表示，設(shè)系數(shù)誤差為，則，當(dāng)且僅當(dāng)y=y0時(shí)等號(hào)成立。證明在處根據(jù)Taylor展開式，并作一些轉(zhuǎn)換可得(5)式 （5）其中。（2）引起誤差的原因是省略項(xiàng)。設(shè)，易知，因此 （6）在（2）式中系數(shù)誤差分下列三種情況討論：1) 時(shí)，則；2) 時(shí)，則；3) 時(shí)，則；只有當(dāng)y=y0時(shí)，成

12、立。 下面利用圖形來進(jìn)一步說明上述結(jié)論。設(shè)，假設(shè)，分別取不同的值，得到u(u)曲線如圖1所示，由圖1可見，。所以。由定理1知，Bhattacharyya系數(shù)的Taylor近似表示使得系數(shù)的值偏大。-1 0 110.50圖1u(u)曲線, 其中1,2,3,4代表=0.02,0.05,0.1,0.15u(u)定理2：設(shè)為每次mean shift迭代時(shí)的系數(shù)誤差，如果迭代次數(shù)時(shí)，則證明設(shè)第n次迭代時(shí)，對(duì)于（6）右邊的第u項(xiàng)，分兩種情況討論1）當(dāng)時(shí)，2）當(dāng)時(shí)，所以故 從定理2可得出結(jié)論：從理論上看，Bhattacharyya系數(shù)用（2）式近似表示，利用mean shift來實(shí)現(xiàn)跟蹤，這種方法并不影響跟

13、蹤的效果。但問題是在利用mean shift進(jìn)行迭代優(yōu)化時(shí)，迭代結(jié)束的條件是|y-y0|<或者迭代次數(shù)小于預(yù)先設(shè)定的次數(shù)，很難達(dá)到uà0的情形，因而導(dǎo)致目標(biāo)跟蹤誤差，特別是初始目標(biāo)位置離收斂位置比較遠(yuǎn)時(shí)，誤差更大。這就是（2）式不適合于運(yùn)動(dòng)目標(biāo)發(fā)生急劇變化情形的原因，如圖2所示，在乒乓球下落較快時(shí)，跟蹤不上目標(biāo)。 圖2 mean shift目標(biāo)跟蹤的實(shí)驗(yàn)結(jié)果4目標(biāo)跟蹤方法基于第3節(jié)的分析，為了適合于運(yùn)動(dòng)目標(biāo)發(fā)生急劇變化的情形，本節(jié)提出一種改進(jìn)目標(biāo)跟蹤方法，以消除系數(shù)誤差。4.1改進(jìn)的跟蹤方法根據(jù)上節(jié)分析，將Bhattacharyya系數(shù)優(yōu)化問題轉(zhuǎn)化為求解約束優(yōu)化問題：其中c(y

14、)=，由于某次迭代時(shí)，故取構(gòu)造新的目標(biāo)求解函數(shù)，如下將上式轉(zhuǎn)化為忽略分母中的項(xiàng)，得取，則可求得改進(jìn)mean shift的迭代公式如（7）式。 （7a） （7b）其中 （8） 式(7)與式(4)相比，只是wi的計(jì)算方法不同，當(dāng)u趨于0時(shí)，這兩種方法具有相同的效果。改進(jìn)的mean shift目標(biāo)跟蹤方法如下：第1步：初始化位置y0,0,和第2步：根據(jù)(8)式用yt代替y0計(jì)算權(quán)重wi，用近似代替。第3步：根據(jù)(7a)計(jì)算下一個(gè)目標(biāo)位置yt+1第4步：根據(jù)(7b)更新參數(shù)t+1，假如i+1<0，則t+1=0；第5步：假如|yt+1-yt|<和|t+1-t|<，則結(jié)束；否則，令yt=

15、yt+1，t =t+1，轉(zhuǎn)至第2步。4.2收斂性分析(7a)式經(jīng)過一些轉(zhuǎn)換得到下式 （9）式中，（為歸一化常數(shù)），為迭代步長(zhǎng)，其值隨迭代過程自適應(yīng)地修改。式（9）體現(xiàn)了mean shift算法沿梯度方向迭代。為了分析上述mean shift算法的收斂性，首先證明上述改進(jìn)的目標(biāo)跟蹤方法在12,=t+1情形下的收斂性，為此下面先給出一個(gè)引理。引理 當(dāng)k(×)為高斯核函數(shù)時(shí)，令由mean shift算法產(chǎn)生的點(diǎn)列為yt，則有下式成立證明：根據(jù)文獻(xiàn)17的方法，易證當(dāng)k(·)為高斯核函數(shù)時(shí)，帶權(quán)的mean shift算法迭代時(shí)滿足式中，通過一些轉(zhuǎn)換得到，代入上式得即. 引理說明當(dāng)固定

16、時(shí)，相鄰兩步之間的迭代方向的夾角在(0,90)內(nèi),保證沿著梯度上升的方向收斂.下面給出mean shift迭代收斂性定理。定理3 設(shè)SÍRd為非空開凸集，在S上具有二階連續(xù)偏導(dǎo)數(shù)，如果"ytÎS，k(×)為高斯核函數(shù)且在yt處的Hessian矩陣，t=1,2,.為負(fù)定矩陣,則序列收斂并且嚴(yán)格單調(diào)遞增，而且序列yt收斂。證明:從核函數(shù)的性質(zhì)可知k(x)有界，可知有界，只需證明單調(diào)遞增，就已說明的收斂性。對(duì)t³0，在yt處一階Taylor公式展開，并令y=yt+tdtÎS，得, 設(shè)，則下列極限成立 (由引理得)連續(xù)且可導(dǎo)，則(因?yàn)?易知單

17、調(diào)遞減且, ，即.所以序列嚴(yán)格單調(diào)遞增且收斂，設(shè)收斂于點(diǎn)，根據(jù)到凸集的性質(zhì)，故.又，得(10)(11)(10)式和(11)式的左邊相乘得則,即，所以收斂.考慮到連續(xù)性，易知收斂于，且. 由定理3知對(duì)于正常數(shù)，都有，由此得到以下定理4。定理4 令目標(biāo)跟蹤方法產(chǎn)生的序列yt,t，則序列yt,t收斂，即，。 證明：由(7)式知，因此由于為有界函數(shù)，故收斂，則有根據(jù)定理3得：，故，即。又故又有下界，故故即. 上述目標(biāo)跟蹤方法是一種采用迭代方法來求解約束優(yōu)化問題的方法。求解約束優(yōu)化問題的方法有很多，如罰函數(shù)法，乘子法等18。相當(dāng)于罰函數(shù)，如果采用罰函數(shù)法或者乘子法，則罰函數(shù)前面的系數(shù)會(huì)急劇增大(外罰函數(shù)

18、法)或者減小(內(nèi)罰函數(shù)法)，容易引起求解的目標(biāo)位置收斂到錯(cuò)誤位置，從而引起跟蹤目標(biāo)的丟失，因此不宜使用這些方法。4.3方法的實(shí)施 采用上述基于mean shift 的跟蹤方法外，在實(shí)施過程中還有一些因素需要考慮。1）核函數(shù)的選擇 在mean shift中，比較常用的核函數(shù)有高斯核函數(shù)k(x) = e-x；Epanechnikov ；截?cái)喔咚购瘮?shù)。本文選擇截?cái)喔咚购瘮?shù)作為核函數(shù)。選擇的理由有以下三點(diǎn)：（1）對(duì)于高斯核函數(shù)來說，當(dāng)x較大時(shí)，高斯函數(shù)的值很小，對(duì)目標(biāo)跟蹤的精度影響很小，但會(huì)增加了計(jì)算量。（2）而對(duì)于Epanechnikov核4，mean shift算法就變成了，這就相當(dāng)于每次迭代時(shí)求

19、目標(biāo)的質(zhì)心點(diǎn)坐標(biāo)，體現(xiàn)不出核函數(shù)對(duì)目標(biāo)跟蹤的影響。（3）截?cái)嗟母咚购瘮?shù)是通過參數(shù)來限制截尾的范圍，相比高斯核函數(shù)來說計(jì)算量要大大減少，而且能保證算法的收斂性17,19。2）帶寬的確定 在文獻(xiàn)4中，令是前一幀的帶寬，分別使用三個(gè)不同的帶寬, 和通過mean shift算法獲得具有最大Bhattacharyya系數(shù)的。典型選擇是。為了避免對(duì)尺度變化的敏感，帶寬通過下式濾波獲?。?。這種方法的缺點(diǎn)是三次使用mean shift算法，會(huì)增加目標(biāo)跟蹤的計(jì)算時(shí)間，降低實(shí)時(shí)性。為提高目標(biāo)跟蹤的實(shí)時(shí)性，本文在使用mean shift算法找到目標(biāo)的中心坐標(biāo)(x, y)后，搜索最優(yōu)h使得最大。帶寬搜索區(qū)域不能太大，

20、否則實(shí)時(shí)性差，本文采用h伸縮10%進(jìn)行搜索最優(yōu)帶寬，這樣只需要一次使用mean shift算法，兩次帶寬搜索就可以完成目標(biāo)跟蹤的任務(wù)。3）迭代初始點(diǎn)的確定 以上幀目標(biāo)的中心位置作為下幀mean shift迭代的起始點(diǎn)。5實(shí)驗(yàn)及分析實(shí)驗(yàn)中，為了準(zhǔn)確直觀地比較跟蹤效果，使用下式來計(jì)算第i幀位置跟蹤的偏差：errori=|Ti-Ci|，Ti表示跟蹤的第i幀位置，Ci表示準(zhǔn)確的第i幀位置，計(jì)算出來的errori表示偏離準(zhǔn)確位置的偏差，可用來衡量跟蹤定位的準(zhǔn)確性。另外用下式來衡量目標(biāo)跟蹤的平均偏差：。分別用上兩式來計(jì)算各幀中目標(biāo)位置在x，y方向的偏差和平均偏差。實(shí)驗(yàn)中Ci的確定是通過采取手動(dòng)方法獲得每幀

21、中目標(biāo)的準(zhǔn)確中心位置，雖然這種方法對(duì)單幀中目標(biāo)精確定位帶有很強(qiáng)的主觀性，會(huì)帶來一些誤差，但從整體上來看對(duì)比較結(jié)果不會(huì)有太大影響，特別是對(duì)計(jì)算的平均偏差幾乎不會(huì)有影響。另外假設(shè)已知目標(biāo)及其初始位置，通過mean shift算法，來實(shí)現(xiàn)目標(biāo)的跟蹤。5.1實(shí)驗(yàn)一從stennis序列(/cil/v-images.html)中截取80幀視頻來進(jìn)行目標(biāo)跟蹤實(shí)驗(yàn)。視頻中乒乓球在接觸球拍前運(yùn)動(dòng)速度快，接觸球拍后會(huì)突然改變方向，本文的方法適合于這種場(chǎng)合。本文方法與mean shift方法的實(shí)驗(yàn)比較結(jié)果如圖3、圖4。圖3分別表示視頻中第8，18，30，58，77，78幀跟蹤

22、的對(duì)比結(jié)果，黑色框表示本文方法的跟蹤結(jié)果，紅色框表示mean shift跟蹤4的結(jié)果。從中可看出本文方法的優(yōu)越性。在x，y方向每幀的定位偏差的比較如圖4，圖中IMS表示本文方法，MS表示mean shift方法。本文方法與mean shift方法在x，y方向的平均定位偏差如表1。從實(shí)驗(yàn)結(jié)果可看出本文方法對(duì)于快速運(yùn)動(dòng)的目標(biāo)具有好的跟蹤效果，因此而付出的代價(jià)是該方法的迭代次數(shù)比文獻(xiàn)方法多，平均迭代次數(shù)分別31.2，19.3。另外無跡粒子濾波(UPF)方法利用了無跡卡爾曼濾波( UKF)的狀態(tài)估計(jì)結(jié)果計(jì)算出重要密度函數(shù)并產(chǎn)生試探性分布，是當(dāng)前一種較新的算法20；而正則粒子濾波器(RPF)21是為了解

23、決重采樣導(dǎo)致粒子失去多樣性問題而提出的，是一種較好的方法；另外混合粒子濾波和mean shift的方法(HPFMS)22也是當(dāng)前較好的一種跟蹤方法。本文方法分別與UPF、RPF和HPFMS三種方法的比較見表1。從比較結(jié)果可看出本文方法對(duì)于運(yùn)動(dòng)目標(biāo)的跟蹤具有好的效果。 圖3 stennis序列的跟蹤實(shí)驗(yàn)比較結(jié)果，上述分別為第8,18,30,58,77,78幀的結(jié)果，黑色框表示本文方法的跟蹤結(jié)果，紅色框表示mean shift跟蹤的結(jié)果。error (pixels)error (pixels)(b)(a)FramesFrames 圖4 在x, y方向的位置偏差比較, (a)x方向的偏差,(b) y

24、方向的偏差.圖中IMS表示本文方法，MS表示mean shift方法表1 x, y方向的平均誤差(單位：象素)平均誤差I(lǐng)MSMSRPFUPFHPFMSx方向平均誤差1.011.582.562.82.42y方向平均誤差1.252.393.363.32.565.2實(shí)驗(yàn)二從室外獲取的一段汽車運(yùn)動(dòng)視頻中截取60幀（car序列）來進(jìn)行目標(biāo)跟蹤實(shí)驗(yàn)，視頻中汽車的運(yùn)動(dòng)速度較快，適合于本文方法的要求。本文方法與mean shift方法的實(shí)驗(yàn)比較結(jié)果如圖5、圖6。圖5分別表示視頻中第9, 21, 27, 46幀跟蹤的對(duì)比結(jié)果，白色框表示本文方法的跟蹤結(jié)果，黑色框表示mean shift跟蹤4的結(jié)果。在x，y方向

25、每幀的定位偏差的比較如圖6，本文方法與mean shift方法在x，y方向的定位平均偏差如表2。從實(shí)驗(yàn)結(jié)果可看出本文方法對(duì)于快速運(yùn)動(dòng)的目標(biāo)具有好的跟蹤效果。另外，本文方法與UPF、RPF和HPFMS三種方法的比較見表2。整體上看，本文方法對(duì)于運(yùn)動(dòng)目標(biāo)的跟蹤具有好的效果。 圖5 car序列的跟蹤實(shí)驗(yàn)比較結(jié)果，上述分別為第9,21,27,46幀的結(jié)果，白色框表示本文方法的跟蹤結(jié)果，黑色框表示mean shift跟蹤的結(jié)果error (pixels)error (pixels)(b)(a)FramesFrames 圖6 在x, y方向的位置偏差比較, (a)x方向的偏差,(b) y方向的偏差。圖中I

26、MS表示本文方法，MS表示mean shift方法表2 x, y方向的平均誤差(單位：象素)平均誤差I(lǐng)MSMSRPFUPFHPFMSx方向平均誤差5.75.9y方向平均誤差 參數(shù)的影響實(shí)驗(yàn)中采用截?cái)喔咚购瘮?shù)作為核函數(shù)，因此參數(shù)對(duì)于算法性能有很大的影響，主要從三個(gè)方面影響著算法性能：定位精度(用x, y方向定位偏差表示，偏差越小，精度越好)，迭代次數(shù)和運(yùn)行時(shí)間，因此的選擇對(duì)于目標(biāo)跟蹤的穩(wěn)定性是非常重要的。下面對(duì)兩個(gè)視頻：car序列和man序列(見圖8)分別取不同的值來分析對(duì)跟蹤方法的影響，分析結(jié)果見圖7。圖7(a)，(b)分別表示對(duì)x，y方

27、向定位的平均誤差的影響。圖7(c)，(d)分別表示對(duì)平均迭代次數(shù)和平均計(jì)算時(shí)間（賽揚(yáng)處理器1.3GHZ，內(nèi)存256M）的影響。從圖7可看出，越小，則目標(biāo)的平均定位精度越差，迭代次數(shù)越少，計(jì)算速度越快。因此不能取得太大，否則計(jì)算時(shí)間太長(zhǎng)，實(shí)時(shí)性能差。一般=1.5-2.5，實(shí)驗(yàn)中取2。另外越大，算法的抗遮擋性更好一些，對(duì)man序列分別針對(duì)和的跟蹤結(jié)果如圖8，9所示。圖8表示具有一定的抗遮擋能力，圖9表示在存在遮擋時(shí)出現(xiàn)了目標(biāo)跟丟的現(xiàn)象。error (pixels)error (pixels) (a) 對(duì)平均定位偏差的影響 (b) 對(duì)平均定位偏差的影響iterationstime (ms) (c)

28、對(duì)平均迭代次數(shù)的影響 (d) 對(duì)平均計(jì)算時(shí)間的影響圖7 man, car序列實(shí)驗(yàn)中參數(shù)對(duì)算法的影響 圖8 man序列的實(shí)驗(yàn)結(jié)果（=2），圖中分別表示第20, 30, 70, 120的跟蹤結(jié)果 圖9 man序列的實(shí)驗(yàn)結(jié)果（=2），圖中分別表示第20, 30的跟蹤結(jié)果5.4復(fù)雜度分析標(biāo)準(zhǔn)的mean shift方法的平均時(shí)間代價(jià)是Nmax(ncs, m)，其中max(x, y)表示求x與y之間的最大者，N為平均迭代次數(shù)，n為目標(biāo)區(qū)域的像素個(gè)數(shù)，cs為額外的做除法和開方的代價(jià)。如果m與目標(biāo)區(qū)域的像素個(gè)數(shù)n在相同的范圍，則平均代價(jià)是Nncs4。改進(jìn)方法只是在計(jì)算權(quán)值wi時(shí)需要修改t并不改變方法的時(shí)間代價(jià)

29、，但就迭代的結(jié)束條件來說，相比標(biāo)準(zhǔn)的mean shift，改進(jìn)方法增加了一個(gè)結(jié)束條件|t+1-t|<，因此平均迭代次數(shù)會(huì)增加，可以通過增加限制最大迭代次數(shù)來解決此問題。6結(jié)束語雖然現(xiàn)存在許多mean shift跟蹤方法，但是這些跟蹤方法仍然存在跟蹤偏差或者完全跟不上目標(biāo)的情況，如對(duì)Bhattacharyya系數(shù)泰勒展開近似表示會(huì)引起目標(biāo)定位的偏差。本文針對(duì)Bhattacharyya系數(shù)Taylor公式的近似表示情形，研究了這種近似表示引起的系數(shù)誤差，并研究了系數(shù)誤差對(duì)目標(biāo)跟蹤效果的影響，在此基礎(chǔ)上，將Bhattacharyya系數(shù)的優(yōu)化問題轉(zhuǎn)化為求解約束問題，從而求出達(dá)到目標(biāo)跟蹤的目的。

30、在給出改進(jìn)跟蹤方法的同時(shí)，對(duì)方法的收斂性、參數(shù)的影響、復(fù)雜度進(jìn)行了分析。實(shí)驗(yàn)表明，本文方法對(duì)于快速運(yùn)動(dòng)目標(biāo)的跟蹤具有更好的跟蹤精度。雖然本文的方法實(shí)現(xiàn)的跟蹤效果有所改進(jìn)，但實(shí)際上還有其他一些因素會(huì)影響跟蹤的精度，如目標(biāo)模型中存在的背景信息會(huì)降低目標(biāo)跟蹤的精度；其次，當(dāng)目標(biāo)逐漸增大尺寸時(shí)，核窗寬很難被擴(kuò)大，反而經(jīng)常越變?cè)叫?；另外mean shift算法采用顏色核直方圖作為目標(biāo)模型的表示方式，沒有考慮目標(biāo)的空間信息或其他目標(biāo)內(nèi)在信息。這些都是下一步的工作。我們期待本文的研究能促進(jìn)mean shift算法的發(fā)展。參考文獻(xiàn)1 Cheng Y, Mean shift, mode seeking, and

31、 clustering, IEEE Trans. on pattern analysis and machine intelligence, 1995,17(8):790-799. 2 Comaniciu D, Meer P. Mean shift analysis and applications, Proc. of the IEEE Intl Conf. on Computer Vision, 1999: 1197- 1203. /comanici/ 3 Comaniciu D, Ramesh V, and Meer P. Real-Ti

32、me tracking of non-rigid objects using mean shift, Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition,2000:142-149.4 Comaniciu D, Ramesh V, and Meer P. Kernel-based object tracking. IEEE Trans. on pattern analysis and machine intelligence. 2003, 25(5): 564-577.5 Collins R T. Mean Shi

33、ft blob tracking through scale space, Proc. of the Conf. on Computer Vision and Pattern Recognition, 2003:18-20.6 Comaniciu D. Image segmentation using clustering with saddle point detection, Proc. of the IEEE Intl Conf. on Image Processing,2002:297-300.7 Wua K, Yang M, Mean shift-based clustering,

34、Pattern Recognition 2007, 40: 3035-3052.8 Yang C, Duraiswami R, Davis L. Efficient Mean-Shift Tracking via a New Similarity Measure, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005, 1: 176-183.9 Jeong M, You B, Oh Y, et al. Adaptive Mean-Shif

35、t Tracking with Novel Color Model, Proceedings of the IEEE International Conference on Mechatronics & Automation , 2005, 3:1329 1333.10Zivkovic Z, Krose B. An EM-like algorithm for color-histogram-based object tracking, Proc. of the 2004 IEEE Comp. Society Conf. on Computer Vision and Pattern Re

36、cognition, 2004,1: 798-803.11 Collins R T, Liu Y, and Leordeanu M, Online Selection of Discriminative Tracking FeaturesJ. IEEE Trans. on pattern analysis and machine intelligence, 2005,27(10): 1631-1643.12 Li PH.An Improved Mean Shift Algorithm for Object Tracking, ACTA AUTOMATICA SINICA, 2007,33(4)

37、:347-354.(李培華.一種改進(jìn)的Mean Shift跟蹤算法,自動(dòng)化學(xué)報(bào), 2007,33(4):347-354.)13 Avidan S. Ensemble Tracking, IEEE Trans. on pattern analysis and machine intelligence, 2007,29(2):261-271.14 Comaniciu D. An algorithm for data-driven bandwidth selection. IEEE Trans. on pattern analysis and machine intelligence. 2003,2

38、5(2): 281-288.15Peng, N S,Yang J,Liu Z, et al. Automatic Selection of Kernel-Bandwidth for Mean-Shift Object Tracking, Journal of Software,2005, 16(9):1542-1550. (in Chinese) (彭寧嵩,楊杰,劉志等,Mean-Shift跟蹤算法中核函數(shù)窗寬的自動(dòng)選取,軟件學(xué)報(bào),2005, 16(9):1542-1550.)16Peng, N S,Yang J, Liu Z. Mean shift blob tracking with ke

39、rnel histogram filtering and hypothesis testing, Pattern Recognition Letters, 2005, 26(5): 605-614.17Comaniciu D, Meer P. Mean shift: A robust approach toward feature space analysis. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2002,24(5): 603-619.18Tang H, Qin X. Practical Methods of O

40、ptimization, Dalian University of Technology Press, 2004.(唐煥文,秦學(xué)志.實(shí)用最優(yōu)化方法,大連理工大學(xué)出版社,2004.)19Wen ZQ, Cai ZX. Convergence analysis of Mean Shift algorithm. Journal of Software, 2007,18(2):205-212.(文志強(qiáng), 蔡自興. Mean Shift 算法的收斂性分析,軟件學(xué)報(bào), 2007, 18(2):205-212.)20Merwe R V D, Doucet A., Wan N ,D. F, E., The U

41、nscented Particle Filter, Technical Report CUED/F-INFENG/TR 380, 2000, Cambridge University Engineering Department./cache/papers/cs/18337/http:zSzzSzSzjfgfzSzpaperszSzupfnips.pdf/vandermerwe00unscented.pdf21Arulampalam S, Maskell S, Gordan N, et al. A Tu

42、torial on Particle Filters for Online Non-linear/Non gaussian Bayesian Tracking. IEEE Trans. on Signal Processing, 2002, 50(2): 174188.22Maggio E, and Cavallaro A, Hybrid Particle Filter and Mean Shift tracker with adaptive transition model, Proc. of IEEE Signal Proc. Society Int. Conf. on Acoustics, Spe