劉獻如，蔡自興

（中南大學 信息科學與工程學院，湖南 長沙，410083）

UKF與Mean shift算法相結(jié)合的實時目標跟蹤

劉獻如，蔡自興

（中南大學 信息科學與工程學院，湖南 長沙，410083）

針對Mean shift （即MS）算法理論上的不足以及跟蹤目標時的鄰域跟蹤局限性，提出將Mean shift算法與尺度無跡卡爾曼濾波器（Scaled unscented Kalman filter, SUKF）相結(jié)合的實時目標跟蹤算法。該算法利用尺度無跡卡爾曼濾波器獲取Mean shift算法的初始位置，然后，利用Mean shift算法獲取跟蹤位置。通過分析跟蹤區(qū)域內(nèi)橫縱向直線的統(tǒng)計變化獲取目標的尺度變化，依此自適應(yīng)調(diào)節(jié)Mean shift跟蹤算法中核函數(shù)帶寬，并對高速公路上快速運動的車輛進行跟蹤實驗。研究結(jié)果表明：該算法與固定核窗寬Mean shift算法相比，對目標跟蹤更準確；SUKF濾波使MS的迭代次數(shù)減少，跟蹤的實時性提高；核窗寬自適應(yīng)調(diào)節(jié)可使跟蹤誤差降低到50%以下。

SUKF；Mean shift算法；自適應(yīng)尺度；目標跟蹤

Mean shift（簡稱為MS）算法是一種密度梯度的無參估計方法，于1975年由Fukunage等[1]提出。1995年，Cheng[2]重新研究了Mean shift，提出了更一般的表達式并預(yù)示該算法在聚類和全局優(yōu)化方面的巨大應(yīng)用潛力。Comaniciu等[3]對Mean shift在圖像分割和跟蹤中的使用進行了論述。Mean shift廣泛應(yīng)用于目標跟蹤[4?6]、圖像分割[7]、聚類[8]分析等領(lǐng)域。朱勝利等[9]將Mean shift算法引入卡爾曼濾波（Kalman filter，簡稱為KF），提高了算法的速度，但是，KF只適用于線性系統(tǒng)。近年來，有研究將粒子濾波和Mean shift相結(jié)合應(yīng)用于目標跟蹤[10]，但是，粒子濾波本身的復雜計算降低了跟蹤的實時性。Mean shift應(yīng)用于目標跟蹤具有一些優(yōu)良性能，如：算法實時性較好；參數(shù)單一，可將其作為一個功能模塊與其他算法集成；采用歸一化核函數(shù)直方圖建模，對邊緣遮擋、目標形變以及背景變化不敏感。但是，也存在一些不足，如：由于Mean shift在目標起始點位置進行泰勒展開，即Mean shift是在起始位置尋找目標，當目標運動較快時，算法跟蹤效果將會受到影響。采用濾法算法可解決這一問題，即首先對目標的狀態(tài)空間進行濾波，Mean shift算法在濾波估計位置進行迭代跟蹤。針對跟蹤系統(tǒng)的非線性及實時性要求，本文作者提出將Mean shift與尺度UKF濾波器（SUKF）結(jié)合起來實現(xiàn)對快速運動目標的實時跟蹤與定位。在Mean shift算法中核窗寬不但決定了參與迭代的樣本數(shù)量，也反映了跟蹤窗口的大小。由于運動目標的尺度變化，固定不變的核窗寬常導致Mean shift迭代次數(shù)增加或跟蹤丟失。通過對前一幀跟蹤窗口中目標直線特征的分析，結(jié)合SUKF濾波，估計當前幀中目標尺度，并依此自適應(yīng)調(diào)節(jié)核窗寬，并將提出的算法應(yīng)用于高速公路車輛跟蹤實驗。

1 UKF濾波

在“近似任意非線性函數(shù)的概率分布比近似非線性函數(shù)更容易”的思想指導下，Julier等[11]提出了基于Unscented變換的卡爾曼濾波，即UKF。在確保隨機向量均值和協(xié)方差不變的前提下，選擇一組 Sigma樣點集，每個 Sigma 點通過非線性變換，即Unscented變換（U變換），由變換后樣點的統(tǒng)計量來估計隨機向量通過非線性變換后的均值及方差，避免了線性化所帶來的誤差，且不需要計算非線性方程的Jacobi 矩陣，比EKF類算法具有更強的穩(wěn)定性[12]。Mihaylova等[13]對UKF與PF的性能進行了分析實驗，結(jié)果表明：UKF的濾波性能與PF的濾波性能基本相同，但是，UKF的計算時間比PF的少。

1.1 UKF建模

其中：Φ=[1, 0,t, 0, 0; 0, 1, 0,t, 0; 0, 0, 1, 0, 0; 0, 0, 0, 1, 0; 0, 0, 0, 0,γ]；Γ=[t2/2,t2/2,t,t,0]T；Ξ=[1,1]T；R=[1, 0, 0, 0, 0; 0, 1, 0, 0, 0]；wk和vk分別為狀態(tài)轉(zhuǎn)移與觀測模型的高斯白噪聲；t為相鄰幀時間間隔，取t=1；γ為目標的尺度因子，由目標區(qū)域內(nèi)目標特征的尺度變化確定其大小。設(shè)xc和yc為目標中心的坐標，其初始化由手動選取目標區(qū)域完成，取X（0）=（xc,yc, 0, 0, 1）。

1.2 UKF濾波

UKF算法中的Unscented變換（U變換）是其算法的核心，也是實現(xiàn)對非線性進行狀態(tài)估計的重要手段。尺度U變換的SUKF（Scaled unscented Kalman filter）比UKF具有更好的濾波性能[14]，且當狀態(tài)的維數(shù)高于3時不存在Sigma點“爆炸”等問題，由式（1）和（2）可知：狀態(tài)空間的維數(shù)為5，因此，采用SUKF算法對狀態(tài)空間進行濾波估計。假設(shè)L維狀態(tài)向量X在k?1時刻的狀態(tài)均值和方差為SUKF的狀態(tài)向量為X與噪聲向量合成的擴增向量其相應(yīng)的Sigma點向量為SUKF濾波估計具體實現(xiàn)步驟如下。

（1） 初始化：

其中：Pv為狀態(tài)轉(zhuǎn)移噪聲協(xié)方差；Pn為觀測噪聲。

（2） 利用式（4）計算Sigma點：

（3） 時間更新。將Sigma點代入狀態(tài)轉(zhuǎn)移和觀測方程式（5）和（6），并通過式（7）計算此時狀態(tài)向量的均值：

（4） 觀測更新方程。將式（5）和（6）代入式（8）和（9），并利用式（10）計算增益：將增益代入式（11）和（12），對狀態(tài)向量的均值和方差進行更新。

在近期發(fā)表的一份研究報告中，一個由200多名研究人員組成的國際團隊展示了第一個高質(zhì)量、完整的面包小麥基因組序列。就像一幅巨大的基因組物理圖譜——小麥的DNA比人類多5倍——完整注釋的序列涉及107 000個基因位點，21條染色體展示了400多萬個基因標記。對于養(yǎng)活了世界1/3人口的農(nóng)作物來說，這是一個里程碑事件，與9 000年前人類首次種植小麥的那一天一樣，有著同樣的劃時代意義。

通過SUKF濾波，預(yù)測快速運動目標的位置，由于物體運動的不確定性，故其運動模型也具有不確性，因此，在跟蹤起動以后，將每次Mean shift中定位出來的目標位置與上次的目標位置進行比較，更新并校正SUKF的狀態(tài)模型。

2 Mean shift跟蹤

Mean shift算法又常被稱為均值漂移算法，它對跟蹤?quán)徲蚰繕司哂休^好的性能，但是，當目標快速運動時，該算法容易出現(xiàn)跟丟的現(xiàn)象。因此，引入SUKF算法對目標狀態(tài)進行濾波估計，并將估計的位置作為Mean shift算法迭代跟蹤起始位置。

2.1 目標描述

將顏色核直方圖作為目標特征的描述，假定目標模型和候選目標特征分別表示為：q={qu}u=1,…,m和其中：y為候選目標區(qū)域的中心位置，且；m為核直方圖的級數(shù)。為了得到一個相對于空間位置y平滑的相似函數(shù)，目標模型的特征分布表示為：相應(yīng)的候選目標的特征分布為：其中：δ（?）為Kronecker delta函數(shù)；為歸一化的目標模型像素位置，歸一化后目標模型中心像素的位置為0；b：R2→{1,…,m}為像素點到像素特征的映射；C為歸一化常數(shù)；Ch為歸一化常數(shù)；nh為候選目標區(qū)域中的像素總數(shù)；k（·）為核函數(shù)；h為帶寬。

2.2 相似性函數(shù)

目標模型與候選目標的相似性用Bhattacharyya系數(shù)來度量，定義為為了使ρ（y）最大，以SUKF預(yù)測的位置作為當前幀的搜索窗口中位置y0，在y0鄰域內(nèi)尋找局部最優(yōu)目標位置y1。對上式在p（y0）處進行泰勒展開，相似性函數(shù)可近似為：

項獨立于y，所以，要使式（13）最大化，也就是使式（13）的第2項最大化，則第2項最大化可通過Mean shift 算法迭代實現(xiàn)，使核中心點不斷從起始點往新的y1方向移動。

2.3 算法迭代過程

Mean shift 算法在每一幀的定位的迭代起始位置為SUKF算法濾波估計的位置。Mean shift算法定位目標實現(xiàn)如下。

（6） 否則，y0←y1并轉(zhuǎn)至步驟（2）。

在Mean shift跟蹤過程中，將每次找到位置與先前若干幀的位置進行比較，估計目標的速度，并依此更新SUKF的狀態(tài)模型。將SUKF與Mean shift算法兩者結(jié)合起來，形成一個閉環(huán)跟蹤系統(tǒng)，可以對快速運動目標進行實時而有效地跟蹤。

3 自適應(yīng)尺度

Comaniciu等[3?4]采用3種不同尺度在當前幀中進行迭代運算，比較它們所得到的Bhattachayya系數(shù)，認為其中具有最大Bhattacharyya系數(shù)的尺度是最優(yōu)的尺度。該方法具有盲目性。彭寧嵩等[15]采用匹配相鄰幀的目標區(qū)域內(nèi)角點，求仿射變換模型參數(shù)獲取目標伸縮系數(shù)。但是，該方法角點的獲取以及匹配相對于目標來說計算量較大，不適合實時性要求高的場合。

針對上述問題，本文作者提出一種簡單快速的目標尺度估計方法。該方法采用相鄰兩幀中水平直線和垂直直線的長度變化估計目標的尺度變化，并依此調(diào)節(jié)核函數(shù)帶寬，實現(xiàn)自適應(yīng)核窗寬選取。其步驟是：首先，采用Sobel水平直線檢測算子{1, 2, 1; 0, 0, 0; ?1,?2, ?1}和垂直檢測算子{1, 0, ?1; 2, 0, ?2; 1, 0, ?1}檢測當前窗口中所有的水平直線集合{lk,i}和{vk,i} （i=1, 2, …,m）。其中：下標k表示時刻；i表示第i條直線。然后，計算它們與前一幀的平均長度之比；最后，采用式（7）獲取目標的尺度變化因子γ：

4 實驗結(jié)果與分析

為了驗證本研究方法的有效性，通過采集高速公路一段視頻進行跟蹤測試。所用微機的內(nèi)存為1 G，CPU容量為1.8 G，雙核，編程語言為Matlab。

視頻參數(shù)如下：采集速率25幀/s，圖像格式為位圖，大小為192×240。進行實驗時，將圖像從紅綠藍彩色空間映射到特征空間，并量化為16×16×16 個特征級。目標的初始化由手動完成。采用上述提出算法（簡稱SUKF-MS算法）對視頻中的白色轎車進行實時跟蹤，并與固定尺度Mean shift算法跟蹤結(jié)果進行比較。圖1所示為從其中隨機抽取第40，48，60，66，72，80和89幀的跟蹤結(jié)果，其中：白色框為SUKF-MS的跟蹤結(jié)果，黑色框為傳統(tǒng)MS算法的跟蹤結(jié)果。從圖1可見：在跟蹤初始階段，傳統(tǒng)MS與SUKF-MS的跟蹤框基本上重合，但是，隨著目標的變化和快速離去，SUKF-MS算法的優(yōu)越性逐漸顯示出來；MS跟蹤的目標不再位于跟蹤框中心，即出現(xiàn)了較大的跟蹤誤差，而SUKF-MS保留著目標位置于跟蹤框中心。

為了比較2種算法在時間上的性能，分別對它們的Mean shift迭代次數(shù)和每一幀定位目標所用時間進行比較，實驗結(jié)果分別如圖2和圖3所示。從圖2可看出：SUKF-MS的每幀的迭代次數(shù)小于或等于傳統(tǒng)的MS的迭代次數(shù)。

由于文中所述算法加入了SUKF，相應(yīng)地會增加計算時間，但是，從圖3可以看出：SUKF-MS每幀的定位時間都要比MS的小。這是由于SUKF的引入減少了MS的迭代次數(shù)，使得算法整體上的計算時間比MS的小，這也體現(xiàn)了SUKF濾波較好的濾波性能。

SUKF-MS和MS算法兩者的平均迭代次數(shù)、定位時間及定位平均相對誤差見表1。從表1可知：SUKFMS每幀的迭代次數(shù)減少為MS算法的70%左右，這也使得SUKF-MS算法每幀搜集目標的時間大為減少；同時，其定位誤差減少為MS算法的50%（跟蹤誤差計算項中的目標真實位置是通過手動得到的，由于X方向的坐標變化不大，故只對Y方向平均每幀跟蹤誤差進行分析）。

圖1 傳統(tǒng)MS 與文中方法跟蹤效果比較Fig.1 Tracking results comparison between MS and proposed algorithm

圖2 MS 與UKF-MS的迭代次數(shù)比較Fig.2 Iternation times comparison between MS and SUKF-MS

圖3 MS與UKF-MS每幀的目標定位時間比較Fig.3 Object location time for each frame between MS and SUKF-MS

表1 MS與SUKF-MS的跟蹤性能比較Table 1 Comparison of MS and SUKF-MS tracking performance

5 結(jié)論

（1） Mean shift由于其實時性好且具有一定的抗干擾能力，常用于復雜環(huán)境的目標跟蹤。但是，它存在理論上的缺陷，導致其跟蹤快速大范圍內(nèi)運動目標容易丟失。而尺度UKF濾波器（即SUKF）具有較好濾波性能，實現(xiàn)簡單且較快，可以為Mean shift算法估計目標的跟蹤迭代起始位置。將SUKF與Mean shift算法兩者結(jié)合起來，可實現(xiàn)對快速運動目標的實時跟蹤。

（2） 由于運動目標尺度變化要求核函數(shù)帶寬相應(yīng)地進行調(diào)整，通過對跟蹤窗口區(qū)域內(nèi)目標水平與垂直直線特征進行統(tǒng)計平均分析，估計目標尺度的變化，并依此自適應(yīng)調(diào)節(jié)核函數(shù)帶寬和跟蹤窗口的大小。這樣，對于逐漸變小的目標跟蹤可以減少搜索時間，而對于逐漸增大的目標可以避免目標丟失。

（3） SUKF濾波方法同樣存在隨著維數(shù)的增加，Sigma點傳播的計算時間會增大的問題。其中有些Sigma點對最后的均值和方差產(chǎn)生的影響很小，可以通過分析這些點的特征，在傳播前進行相應(yīng)刪除，從而提高SUKF的濾波速度而不影響其濾波性能，以便進一步提高跟蹤系統(tǒng)的實時性。

[1] Fukunage K, Hostetler L D. The estimation of the gradient of a density function with application in pattern recognition[J]. IEEE Transaction on Information Theory, 1975, 21（1）： 32?40.

[2] Cheng Y. Mean shift, mode seeking and clustering[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1995, 17（8）： 790?799.

[3] Comaniciu D, Meer P. Mean shift analysis and applications[C]// Proceeding of the IEEE International Conference on Computer Vision. Kerkyra, Greece, 1999： 1197?1203.

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

[5] 文志強, 蔡自興. 目標跟蹤中巴氏系數(shù)誤差的分析及其消除方法[J]. 計算機學報, 2008, 31（7）： 1165?1171.

WEN Zhi-qiang, CAI Zi-xing, Errors of Bhattacharyya coefficient and its reduction in object tracking[J]. Journal of Computer, 2008, 31（7）： 1165?1171.

[6] 李培華. 一種改進的Mean shift跟蹤算法[J]. 自動化學報, 2007, 33（4）： 347?354.

LI Pei-hua. An improved Mean shift algorithm for object tracking[J]. Acta Automatica Sinica, 2007, 33（4）： 347?354.

[7] Unnikrishnan R, Pantofaru C, Hebert M. Toward objective evaluation of image segmentation algorithms[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29（6）： 929?944.

[8] Wu K, Yang M. Mean shift-based clustering[J]. Pattern Recognition, 2007, 40（11）： 3035?3052.

[9] 朱勝利, 朱善安, 李旭超. 快速運動目標的Mean shift跟蹤算法[J]. 光電工程, 2006, 33（5）： 66?70.

ZHU Sheng-li, ZHU Shan-an, LI Xu-chao. Algorithm for tracking of fast motion objects with Mean shift[J]. Opto-Electronic Engineering, 2006, 33（5）： 66?70.

[10] Shan C, Tan T, Wei Y. Real-time hand tracking using a mean shift embedded particle filter[J]. Pattern Recognition, 2007, 40（7）： 1958?1970.

[11] Julier S J, Uhlmann J K, Durrant-Whyte H F. A new method for the nonlinear transformation of means and covariance in filters and estimators[J]. IEEE Transaction on Automatic Control, 2000, 45（3）： 477?482.

[12] Daum F. Nonlinear filters： Beyond the Kalman filter[J]. IEEE Aerospace and Electronic Systems Magazine, 2005, 20（8）： 57?69.

[13] Mihaylova L, Boel R, Hegyi A. An unscented Kalman filter for freeway traffic estimation[C]//Proceedings of 11st IFAC Symposium on Control in Transportation Systems. Netherlands, 2006： 31?36.

[14] Julier S J. The scaled unscented transformation[C]//Proceeding of the American Control Conference. Anchorage, USA, 2002： 4555?4559.

[15] 彭寧嵩, 楊杰, 劉志, 等. Mean shift跟蹤算法中核核函數(shù)窗寬的自動選取[J]. 軟件學報, 2005, 16（9）： 1542?1550.

PENG Ning-song, YANG Jie, LIU Zhi, et al. Automatic selection of Kernel-Bandwidth for Mean-shift object tracking[J]. Journal of Software, 2005, 16（9）： 1542?1550.

（編輯 陳燦華）

Real time object tracking using Mean shift combined UKF

LIU Xian-ru, CAI Zi-xing
（School of Information Science and Engineering, Central South University, Changsha 410083, China）

Aiming at theoretic and neighborhood tracking limitation of Mean shift （MS）, a real-time target tracking algorithm combined with Mean shift and scaled unscented Kalman filter （SUKF） was proposed. The algorithm firstly used SUKF to estimate the starting position of the Mean shift in every frame. And then the Mean shift was used to locate the target position. The target scale changing was estimated by analyzing the statistical changes of the horizontal and vertical lines in the tracking region. According to the estimated scale, the kernel-band width changed adaptively for Mean shift object tracking. Experiments on the highway vehicle tracking were done. The results show that the proposed tracking algorithm can locate the target more accurately than the traditional Mean shift; the SUKF can reduce the iteration times of MS and improve the real time of tracking. Adaptive adjustment of kernel-band width further can reduce the tracking errors to less than 50% of the MS algorithms.

SUKF; Mean shift, adaptively scale; object tracking

TP242

A

1672?7207（2011）05?1338?06

2010?05?11；

2010?07?25

國家自然科學基金重大專項項目（90820302）；國家自然科學基金面上項目（60805027）；國家博士點基金資助項目（200805330005）

劉獻如（1977?），女，湖南婁底人，博士研究生，從事計算機視覺等研究；電話：13548986493；E-mail：lxrcsu@163.com