包 旭，杜 凱，田 浩

1.淮陰工學院 交通工程學院，江蘇 淮安223003

2.長安大學 電子與控制工程學院，西安710064

1 引言

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

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

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

2 改進的Mean Shift跟蹤算法

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

2.1 自適應分塊方法

不同的運動對象常常具有不同的外觀尺寸，同一運動對象也會隨著運動的變化而發(fā)生方位和尺寸上的變化。因此，固定尺度和固定分塊的方法常常不能滿足變化的、復雜的情況?；诖?，本文采用自適應的分塊方法，自適應分塊對于運動目標跟蹤的實驗效果，參見文獻[16]。

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

圖1 目標對象的外接矩形

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

圖2 自適應分塊方法

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

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

2.3 改進的Mean Shift算法步驟

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

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

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

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

步驟4計算位置候選目標的直方圖2,…,S，計算

步驟5如果，則

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

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

3 融合改進Mean Shift和SURF 的跟蹤算法

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

圖3 融合改進的MS 和SURF 的跟蹤算法流程

3.1 SURF 特征提取

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

3.2 SURF 特征匹配

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

3.3 特征點重心偏移量計算

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

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

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

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

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

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

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

4 實驗與分析

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

表1 實驗視頻數(shù)據(jù)簡要描述

4.1 改進的Mean Shift算法初步跟蹤

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

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

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

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

4.2 SURF 特征匹配和校正

（1）SURF 特征匹配和特征點重心偏移量計算

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

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

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

圖5 SURF 特征匹配和特征點重心偏移量計算

表2 平均跟蹤誤差（均值±標準差）和跟蹤時間比較

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

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

5 結(jié)束語

本文提出了一種融合改進MS 和SURF 的跟蹤算法，改進的MS 算法能根據(jù)目標對象的最新外接矩形尺寸確定對象分塊方法，根據(jù)各塊的Bhattacharyya 系數(shù)值，確定各塊的權(quán)重系數(shù)；在改進的MS 跟蹤結(jié)果的基礎(chǔ)上，采用SURF匹配和校正獲得校正跟蹤結(jié)果；最后，對兩結(jié)果進行線性加權(quán)，獲得最終的跟蹤結(jié)果。實驗表明，本文算法可以有效地跟蹤部分遮擋、復雜背景、光照變換和仿射變換情況下目標對象，改善了傳統(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 算法的運動人體跟蹤[J].計算機工程與科學，2008，30（4）：46-49.

[9] 張恒，李由，李立春，等.基于顯著性加權(quán)的Mean Shift 跟蹤方法[J].光學技術(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的相似性變換和仿射變換目標跟蹤算法[J].中國圖象圖形學報，2011，16（2）：258-266.

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