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

劉獻(xiàn)如，蔡自興

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

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

劉獻(xiàn)如，蔡自興

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

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

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

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

1 UKF濾波

在“近似任意非線性函數(shù)的概率分布比近似非線性函數(shù)更容易”的思想指導(dǎo)下，Julier等[11]提出了基于Unscented變換的卡爾曼濾波，即UKF。在確保隨機(jī)向量均值和協(xié)方差不變的前提下，選擇一組 Sigma樣點(diǎn)集，每個 Sigma 點(diǎn)通過非線性變換，即Unscented變換（U變換），由變換后樣點(diǎn)的統(tǒng)計(jì)量來估計(jì)隨機(jī)向量通過非線性變換后的均值及方差，避免了線性化所帶來的誤差，且不需要計(jì)算非線性方程的Jacobi 矩陣，比EKF類算法具有更強(qiáng)的穩(wěn)定性[12]。Mihaylova等[13]對UKF與PF的性能進(jìn)行了分析實(shí)驗(yàn)，結(jié)果表明：UKF的濾波性能與PF的濾波性能基本相同，但是，UKF的計(jì)算時間比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；γ為目標(biāo)的尺度因子，由目標(biāo)區(qū)域內(nèi)目標(biāo)特征的尺度變化確定其大小。設(shè)xc和yc為目標(biāo)中心的坐標(biāo)，其初始化由手動選取目標(biāo)區(qū)域完成，取X（0）=（xc,yc, 0, 0, 1）。

1.2 UKF濾波

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

（1） 初始化：

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

（2） 利用式（4）計(jì)算Sigma點(diǎn)：

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

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

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

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

2 Mean shift跟蹤

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

2.1 目標(biāo)描述

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

2.2 相似性函數(shù)

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

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

2.3 算法迭代過程

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

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

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

3 自適應(yīng)尺度

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

圖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每幀的目標(biāo)定位時間比較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由于其實(shí)時性好且具有一定的抗干擾能力，常用于復(fù)雜環(huán)境的目標(biāo)跟蹤。但是，它存在理論上的缺陷，導(dǎo)致其跟蹤快速大范圍內(nèi)運(yùn)動目標(biāo)容易丟失。而尺度UKF濾波器（即SUKF）具有較好濾波性能，實(shí)現(xiàn)簡單且較快，可以為Mean shift算法估計(jì)目標(biāo)的跟蹤迭代起始位置。將SUKF與Mean shift算法兩者結(jié)合起來，可實(shí)現(xiàn)對快速運(yùn)動目標(biāo)的實(shí)時跟蹤。

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

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

[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] 文志強(qiáng), 蔡自興. 目標(biāo)跟蹤中巴氏系數(shù)誤差的分析及其消除方法[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 李培華. 一種改進(jìn)的Mean shift跟蹤算法[J]. 自動化學(xué)報(bào), 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] 朱勝利, 朱善安, 李旭超. 快速運(yùn)動目標(biāo)的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]. 軟件學(xué)報(bào), 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

國家自然科學(xué)基金重大專項(xiàng)項(xiàng)目（90820302）；國家自然科學(xué)基金面上項(xiàng)目（60805027）；國家博士點(diǎn)基金資助項(xiàng)目（200805330005）

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