包 旭，杜 凱，田 浩

1.淮陰工學(xué)院 交通工程學(xué)院，江蘇 淮安223003

2.長(zhǎng)安大學(xué) 電子與控制工程學(xué)院，西安710064

1 引言

運(yùn)動(dòng)對(duì)象跟蹤是計(jì)算機(jī)視覺領(lǐng)域的一個(gè)重要研究方向，在視頻監(jiān)控、機(jī)器人導(dǎo)航、自動(dòng)駕駛、交通流量監(jiān)測(cè)、天文觀測(cè)、視頻圖像壓縮和傳輸?shù)确矫娑加袕V泛的應(yīng)用。Mean Shift 最初作為一種聚類分析的方法由K.Fukunaga等人提出[1]。Yizong Cheng 等人對(duì)Mean Shift 算法進(jìn)行推廣[2]。Dorin Comaniciu 等人將Mean Shift引入到目標(biāo)跟蹤算法中，提出了基于核（Kernel-based）的跟蹤算法[3-4]。

基于核的跟蹤算法使用目標(biāo)的歸一化加權(quán)顏色直方圖作為目標(biāo)模式。由于顏色直方圖是目標(biāo)的整體統(tǒng)計(jì)特征，沒有包含目標(biāo)的空間信息，當(dāng)目標(biāo)和背景顏色分布相近時(shí)，容易導(dǎo)致不準(zhǔn)確跟蹤或跟蹤丟失。文獻(xiàn)[5]采用內(nèi)中外三層的分塊方法，空間信息結(jié)合顏色信息，生成空間顏色直方圖，各塊采用等權(quán)值法加權(quán)處理。文獻(xiàn)[6]采用上下二分的分塊方法跟蹤曲棍運(yùn)動(dòng)員，這種分塊方法適合于柱狀對(duì)象。文獻(xiàn)[7]提出了7 部分的分法，各塊Bhattacharyya系數(shù)采用了算法平均值的方法，沒有考慮各塊相似度的變化對(duì)總體相似度的不同影響。文獻(xiàn)[8]在文獻(xiàn)[7]的基礎(chǔ)上，結(jié)合人體特征，提出了適合人體的分塊方法，且各塊采用非等權(quán)值的方法加權(quán)處理。文獻(xiàn)[9]提出了顯著性加權(quán)的方法，根據(jù)目標(biāo)中不同區(qū)域與背景的差別大小，賦予不同區(qū)域不同的權(quán)值。由于SURF、SIFT 等特征具有旋轉(zhuǎn)、尺度不變性，對(duì)三維視角、光照變化具有很強(qiáng)的適應(yīng)性，在遮擋和場(chǎng)景混亂時(shí)仍保持不變性等優(yōu)勢(shì)[10-12]，文獻(xiàn)[13]在MS 跟蹤結(jié)果的基礎(chǔ)上，采用SIFT 特征匹配尋找SIFT 匹配點(diǎn)集，通過計(jì)算仿射變換參數(shù)修正MS 跟蹤結(jié)果。文獻(xiàn)[14]結(jié)合顏色特征和SIFT 特征，通過MS 算法迭代，采用EM 框架尋找最相似區(qū)域，實(shí)現(xiàn)跟蹤。文獻(xiàn)[15]引入仿射變換，采用Bhattacharyya 系數(shù)將目標(biāo)跟蹤問題轉(zhuǎn)化成仿射變換參數(shù)的最優(yōu)化問題，實(shí)際中取得了不錯(cuò)的跟蹤效果，但耗時(shí)較長(zhǎng)。文獻(xiàn)[16]中提出了自適應(yīng)分塊顏色直方圖的跟蹤算法，該算法能較好地解決部分遮擋、目標(biāo)對(duì)象矩形變化時(shí)的跟蹤問題，但在光照變化和快速運(yùn)動(dòng)的情況下，跟蹤效果未能得到明顯提高。

受文獻(xiàn)[4-13，16]啟發(fā)，本文提出一種融合改進(jìn)MS 和SURF 的跟蹤算法，該方法由改進(jìn)的Mean Shift 跟蹤算法（初定位）和SURF 特征匹配和校正（微調(diào)）組成。前者根據(jù)目標(biāo)對(duì)象的最新外接矩形尺寸，確定對(duì)象的分塊方法，根據(jù)各塊的相似度大小，確定各塊的權(quán)重系數(shù)；后者在前者跟蹤結(jié)果的基礎(chǔ)上，采用SURF 特征匹配和校正。最后，通過線性加權(quán)的方法融合改進(jìn)MS 和SURF 的跟蹤結(jié)果。實(shí)驗(yàn)表明，本文算法在目標(biāo)發(fā)生旋轉(zhuǎn)、尺度變化、光照變化和部分遮擋等情況下，都有很好的跟蹤效果。

2 改進(jìn)的Mean Shift跟蹤算法

與傳統(tǒng)的MS 跟蹤算法[3-4]相比，改進(jìn)的MS 算法主要由自適應(yīng)分塊方法和加權(quán)Bhattacharyya系數(shù)組成。

2.1 自適應(yīng)分塊方法

不同的運(yùn)動(dòng)對(duì)象常常具有不同的外觀尺寸，同一運(yùn)動(dòng)對(duì)象也會(huì)隨著運(yùn)動(dòng)的變化而發(fā)生方位和尺寸上的變化。因此，固定尺度和固定分塊的方法常常不能滿足變化的、復(fù)雜的情況。基于此，本文采用自適應(yīng)的分塊方法，自適應(yīng)分塊對(duì)于運(yùn)動(dòng)目標(biāo)跟蹤的實(shí)驗(yàn)效果，參見文獻(xiàn)[16]。

假設(shè)包圍運(yùn)動(dòng)對(duì)象的外接矩形如圖1 所示。矩形的寬度為w，高度為h，定義目標(biāo)對(duì)象寬度/高度比例因子k ，k=w/h，k 反映了目標(biāo)對(duì)象外接矩形的外形特征，當(dāng)k ＞1 時(shí)，外接矩形呈現(xiàn)“寬矩形”；當(dāng)k=1 時(shí)，外接矩形為“正方形”；當(dāng)k ＜1時(shí)，外接矩形呈現(xiàn)“窄矩形”；則k 有式（1）三種情況。

圖1 目標(biāo)對(duì)象的外接矩形

考慮到實(shí)際運(yùn)動(dòng)中，目標(biāo)對(duì)象外接矩形常常處于“寬矩形”和“窄矩形”兩種狀態(tài)，正方形僅是動(dòng)態(tài)目標(biāo)對(duì)象外接矩形的臨界狀態(tài)，故此，結(jié)合文獻(xiàn)[1，3，6]的分塊方法和實(shí)驗(yàn)的需要，本文取參數(shù)kc為2，將目標(biāo)對(duì)象劃分為三種不同類型的分塊方式，如圖2 所示。

圖2 自適應(yīng)分塊方法

2.2 加權(quán)Bhattacharyya 系數(shù)

Bhattacharyya 系數(shù)用來衡量目標(biāo)模式和候選目標(biāo)模式的相似程度。文獻(xiàn)[7]中Bhattacharyya 系數(shù)采用了平均值的方法，沒有考慮各塊相似度的變化對(duì)整體相似度的不同影響。借鑒文獻(xiàn)[8-9]中各塊加權(quán)處理的思想，本文根據(jù)各塊的Bhattacharyya 系數(shù)的大小，相似度大的塊，權(quán)重系數(shù)大，相似度小的，權(quán)重系數(shù)小。按照式（2）對(duì)各塊進(jìn)行加權(quán)處理，各塊的權(quán)值由式（3）確定。

2.3 改進(jìn)的Mean Shift算法步驟

初始第一幀，設(shè)當(dāng)前目標(biāo)對(duì)象外接矩形的尺寸為w0×h0，矩形中心為，計(jì)算寬度/高度比例因子k0=w0/h0，根據(jù)式（1）確定初始目標(biāo)對(duì)象的分塊方法，總的分塊數(shù)記為S。根據(jù)文獻(xiàn)[3]中式（21）計(jì)算目標(biāo)模板的直方圖s=1,2,…,S 。

步驟1讀取下一幀圖像，計(jì)算該幀圖像位置候選目標(biāo)的直方圖，s=1,2,…,S，并計(jì)算

步驟2采用文獻(xiàn)[3]中式（25）計(jì)算{wi},i=1,2,…,Np，其中和取整塊的特征情況。

步驟3采用文獻(xiàn)[3]中式（14）計(jì)算新的迭代位置，本文采用的是Epanechnikov 核函數(shù)。

步驟4計(jì)算位置候選目標(biāo)的直方圖2,…,S，計(jì)算

步驟5如果，則

步驟6若＜ε，執(zhí)行步驟7；否則，，執(zhí)行步驟2。

步驟7根據(jù)當(dāng)前目標(biāo)對(duì)象外接矩形尺寸w×h，計(jì)算寬度/高度比例因子k=w/h，根據(jù)式（1）確定運(yùn)動(dòng)對(duì)象的分塊方法，總的分塊數(shù)記為S，執(zhí)行步驟1。

3 融合改進(jìn)Mean Shift和SURF 的跟蹤算法

融合改進(jìn)Mean Shift 和SURF 的跟蹤算法由改進(jìn)的Mean Shift（初定位）和SURF 特征匹配和校正（微調(diào)）組成，最終跟蹤結(jié)果由兩部分線性加權(quán)獲得。其改進(jìn)的MS 算法如上文1 章描述；SURF 特征匹配和校正（微調(diào)）由SURF 特征提取、SURF 特征匹配、特征點(diǎn)重心位移偏移量計(jì)算和跟蹤結(jié)果校正四部分組成。其算法流程如圖3 所示。

圖3 融合改進(jìn)的MS 和SURF 的跟蹤算法流程

3.1 SURF 特征提取

SURF（Speed Up Robust Features）特征是由Bay 等人[11-12]提出，借鑒了SIFT 簡(jiǎn)化近似的思想，對(duì)DoH 高斯二階模板進(jìn)行簡(jiǎn)化近似處理，使得模板對(duì)圖像的濾波只需要進(jìn)行簡(jiǎn)單的加減法運(yùn)算，又因?yàn)椴捎梅e分圖像的方法，其運(yùn)算時(shí)間與濾波模板的尺寸無關(guān)。實(shí)驗(yàn)表明，SURF 算法的運(yùn)算速度是SIFT 的3 倍，綜合性能優(yōu)于SIFT 算法，其詳細(xì)的算法詳見文獻(xiàn)[11-12]。

3.2 SURF 特征匹配

SURF 特征匹配采用特征點(diǎn)向量間的歐式距離作為相似性度量。設(shè)目標(biāo)區(qū)中某個(gè)特征點(diǎn)向量為Va，找出與其MeanShift 跟蹤結(jié)果（待校正區(qū)）中歐式距離最近的前2 個(gè)關(guān)鍵點(diǎn)向量Vb和Vc，如滿足式（4），則接受該對(duì)匹配點(diǎn)，否則去除。其中t是一個(gè)給定的閾值，取為0.8[10]。

3.3 特征點(diǎn)重心偏移量計(jì)算

經(jīng)過2.2 節(jié)SURF 特征匹配，目標(biāo)區(qū)和待校正區(qū)對(duì)應(yīng)的特征點(diǎn)集分別為P={(xi,yi),Vi}，i=1,2,…,N和P′={(x′i,y′i),V′i}，i=1,2,…,N。本文采用平均值的方法，計(jì)算待校正區(qū)對(duì)象相對(duì)于目標(biāo)區(qū)對(duì)象的重心平均偏移量，如式（5）所示。

3.4 改進(jìn)的MS 跟蹤結(jié)果校正

設(shè)改進(jìn)的MS 算法的跟蹤結(jié)果為：

其中(xo,yo)表示矩形跟蹤區(qū)域的中心坐標(biāo)，vRadius表示矩形垂直方向的半徑，hRadius表示跟蹤矩形水平方向的半徑。結(jié)合公式（5），校正后的結(jié)果如式（6）所示，其中rectSURF表示SURF 匹配和校正后的跟蹤結(jié)果。

3.5 融合改進(jìn)MS 和SURF 的跟蹤結(jié)果

融合改進(jìn)MS和SURF跟蹤結(jié)果為rect，如公式（7）所示。

α為權(quán)值系數(shù)，介于0～1 之間，當(dāng)改進(jìn)的MS 算法Bhattacharyya 值較大時(shí)，則MS 算法跟蹤結(jié)果較好，此時(shí)α取較大值；反之，α取較小值。實(shí)驗(yàn)中，為了簡(jiǎn)化融合算法的計(jì)算難度，本文α參數(shù)取為0.5，更進(jìn)一步的自適應(yīng)調(diào)節(jié)α參數(shù)的取值方法，有待于在后續(xù)研究中展開。

4 實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)采用Epanechnikov 核，RGB 各子空間采用16個(gè)bin，共使用16×16×16 個(gè)bin，每幀圖像的最大迭代次數(shù)設(shè)為10 次，實(shí)驗(yàn)視頻數(shù)據(jù)簡(jiǎn)要描述如表1 所示。

表1 實(shí)驗(yàn)視頻數(shù)據(jù)簡(jiǎn)要描述

4.1 改進(jìn)的Mean Shift算法初步跟蹤

“PETS2006S2-T3-C4”序列#784 幀圖像，人體受到他人遮擋，文獻(xiàn)[4]算法調(diào)整自身尺度，順利實(shí)現(xiàn)跟蹤，但跟蹤大小小于對(duì)象實(shí)際大小，如圖4（a1）所示；文獻(xiàn)[7]算法跟蹤大小基本保持與對(duì)象大小相同，但跟蹤中心與對(duì)象實(shí)際中心有較大偏差，如圖4（b1）所示；而本文提出的改進(jìn)的MS算法采用加權(quán)Bhattacharyya 系數(shù)法，受遮擋的塊相似度較小，其對(duì)應(yīng)的權(quán)重系數(shù)較小，未遮擋塊相似度較大，其權(quán)重系數(shù)較大，有效地削弱了受遮擋塊對(duì)整體相似度的影響，保持了與對(duì)象相同的大小，跟蹤中心與對(duì)象實(shí)際中心也較好地吻合，如圖4（c1）所示。

圖4 改進(jìn)的Mean Shift算法與文獻(xiàn)[4]、文獻(xiàn)[7]算法在發(fā)生遮擋，復(fù)雜背景，光照變化和仿射變換情況下的跟蹤性能對(duì)比

“OneBagBoy.avi”視頻#3 057 幀圖像，人體褲子的顏色與背景車輛顏色相同，文獻(xiàn)[4]算法只考慮了整體區(qū)域顏色的統(tǒng)計(jì)信息，沒有考慮空間信息，所以跟蹤結(jié)果出現(xiàn)較大偏差，跟蹤結(jié)果向上偏移，如圖4（a2）；文獻(xiàn)[7]算法采用圖2（c）～（e）的分塊方法，其跟蹤大小基本保持與對(duì)象大小相同，但因各塊取平均值的方法，其跟蹤中心與對(duì)象實(shí)際中心存在一定偏差，如圖4（b2）；而本文提出的改進(jìn)的MS 算法根據(jù)人體外接矩形尺寸，采用上下二分的方法，有效地避免了文獻(xiàn)[4]向上偏移的跟蹤結(jié)果，且因?yàn)椴捎眉訖?quán)Bhattacharyya 系數(shù)的方法，有效地保證了改進(jìn)的MS 算法跟蹤中心與對(duì)象實(shí)際中心較好地吻合，如圖4（b3）。

“DavidIndoor.avi”視頻#755 幀圖像，人臉發(fā)生光照變化，可以看出，文獻(xiàn)[4，7]和改進(jìn)的MS 算法均存在不同程度的跟蹤精度或跟蹤丟失，分別如圖4（a3）、（b3）、（c3）。

4.2 SURF 特征匹配和校正

（1）SURF 特征匹配和特征點(diǎn)重心偏移量計(jì)算

在改進(jìn)的MS 算法跟蹤結(jié)果的基礎(chǔ)上，提取待校正區(qū)的SURF 特征，作目標(biāo)區(qū)和待校正區(qū)的SURF 特征匹配，其匹配效果如圖5 所示。右側(cè)圖內(nèi)部藍(lán)色矩形為改進(jìn)的MS算法的跟蹤結(jié)果，考慮到改進(jìn)的MS 算法跟蹤結(jié)果（待校正區(qū)）與實(shí)際的對(duì)象有位置上的偏移，實(shí)驗(yàn)中，將待校正區(qū)擴(kuò)大0.5 倍，即右側(cè)圖外部虛線的矩形區(qū)域，保證搜索區(qū)中包含目標(biāo)對(duì)象，以增加匹配的魯棒性。

（2）本文算法與文獻(xiàn)[4]和文獻(xiàn)[14]的跟蹤性能比較

表2 是文獻(xiàn)[4]，文獻(xiàn)[14]與本文跟蹤算法平均跟蹤誤差（均值±標(biāo)準(zhǔn)差）和跟蹤時(shí)間的比較結(jié)果。圖6（a1）～（a3）是文獻(xiàn)[4]算法的跟蹤結(jié)果；圖6（b1）～（b3）是文獻(xiàn)[14]算法的跟蹤結(jié)果；圖6（c1）～（c3）是本文算法的跟蹤結(jié)果。

圖5 SURF 特征匹配和特征點(diǎn)重心偏移量計(jì)算

表2 平均跟蹤誤差（均值±標(biāo)準(zhǔn)差）和跟蹤時(shí)間比較

圖6 本文算法與文獻(xiàn)[4]、文獻(xiàn)[14]算法在光照變化情況下的跟蹤性能對(duì)比

由表2 可以看出，在“DavidIndoor.avi”視頻序列中本文算法的誤差是最小的，跟蹤時(shí)間略高于文獻(xiàn)[4]，但低于文獻(xiàn)[14]。由圖6 可以看出，文獻(xiàn)[4]算法在視頻#475、#635 和#830幀均產(chǎn)生跟蹤漂移；文獻(xiàn)[14]采用Mean Shift融合SIFT的算法，在視頻#91 和#162 幀都能成功跟蹤，但由于整體框架仍是Mean Shift 算法，故而仍存在一定偏差；而本文算法由于采用改進(jìn)的MS 算法初步定位，采用SURF 匹配、校正對(duì)其MS 結(jié)果進(jìn)行微調(diào)，之后融合MS 和SURF 結(jié)果，故而在#475、#635 和#830 幀都能準(zhǔn)確地跟蹤。

5 結(jié)束語

本文提出了一種融合改進(jìn)MS 和SURF 的跟蹤算法，改進(jìn)的MS 算法能根據(jù)目標(biāo)對(duì)象的最新外接矩形尺寸確定對(duì)象分塊方法，根據(jù)各塊的Bhattacharyya 系數(shù)值，確定各塊的權(quán)重系數(shù)；在改進(jìn)的MS 跟蹤結(jié)果的基礎(chǔ)上，采用SURF匹配和校正獲得校正跟蹤結(jié)果；最后，對(duì)兩結(jié)果進(jìn)行線性加權(quán)，獲得最終的跟蹤結(jié)果。實(shí)驗(yàn)表明，本文算法可以有效地跟蹤部分遮擋、復(fù)雜背景、光照變換和仿射變換情況下目標(biāo)對(duì)象，改善了傳統(tǒng)MS 算法和固定分塊MS 算法的局限性，提高了跟蹤算法的魯棒性。

[1] Fukunaga K，Hostetler L D.The estimation of the gradient of a density function，with applications in pattern recognition[J].IEEE Trans on Information Theory，1975，21（1）：32-40.

[2] Cheng Y.Mean Shift，mode seeking，and clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1995，17（8）：790-799.

[3] Comaniciu D，Ramesh V，Meer P.Real-time tracking of nonrigid objects using Mean Shift[C]//Proc of IEEE Conf on CVPR，2000：142-149.

[4] Comaniciu D，Ramesh V，Meer P.Kernel-based object tracking[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2003，25（5）：564-575.

[5] Xu D，Wang Y，An J.Applying a new spatial color histogram in Mean-Shift based tracking algorithm[C]//Image and Vision Computing，New Zealand，2005.

[6] Okuma K，Taleghani A，De Freitas N，et al.A boosted particle filter：multitarget detection and tracking[C]//Proc of the European Conference on Computer Vision，2004：28-39.

[7] Maggio E，Cavallaro A.Multi-part target representation for color tracking[C]//Proc of IEEE Int Conference on Image Processing（ICIP），2005：729-732.

[8] 袁霄，王麗萍.基于MeanShift 算法的運(yùn)動(dòng)人體跟蹤[J].計(jì)算機(jī)工程與科學(xué)，2008，30（4）：46-49.

[9] 張恒，李由，李立春，等.基于顯著性加權(quán)的Mean Shift 跟蹤方法[J].光學(xué)技術(shù)，2008，34（3）：404-407.

[10] Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[11] Bay H，Tuytelaars T，van Gool L V.SURF：Speeded Up Robust Features[C]//ECCV，2006.

[12] Bay H，Tuytelaars T，Gool L V.SURF：Speeded Up Robust Features[J].Computer Vision and Image Understanding，2008，110（3）：346-359.

[13] Chen A H，Zhu M，Wang Y H.Mean Shift tracking combining SIFT[C]//Proc of ICSP’08，2008：1532-1535.

[14] Zhou H Y，Yuan Y，Shi C.Object tracking using SIFT features and Mean Shift[J].Computer Vision and Image Understanding，2009，113（3）：345-352.

[15] 李培華，肖莉娟.基于Mean Shift的相似性變換和仿射變換目標(biāo)跟蹤算法[J].中國圖象圖形學(xué)報(bào)，2011，16（2）：258-266.

[16] 杜凱，巨永鋒，靳引利，等.自適應(yīng)分塊顏色直方圖的Mean-Shift跟蹤算法[J].武漢理工大學(xué)學(xué)報(bào)，2012，34（6）：140-144.