核函數自適應的Mean Shift目標跟蹤算法

趙 瑜，黃 山，2，王 凱

（1.四川大學 電氣信息學院，四川 成都610065；2.四川大學 計算機學院，四川 成都610065）

0 引 言

運動目標跟蹤［1］如今在各個領域都有廣泛的應用。Mean Shift算法中帶寬是由初始目標模板的尺寸決定并且整個跟蹤過程中帶寬不變，目標尺寸在逐漸增大或減小的過程中很容易導致在跟蹤過程中的目標丟失。針對此問題，目前一般方法為先運用卡爾曼濾波［2］對下一幀進行預測，然后結合Mean Shift算法［3］進行迭代。文獻 ［4］提出一種運動矢量與Mean Shift算法結合的方法。針對傳統Mean Shift算法中核函數無法自適應跟新的問題，本文提出一種目標質心的分布散度與多級正方形匹配結合的核函數帶寬的更新策略。實驗結果表明了本文策略的有效性。

1 Mean Shift算法

1.1 初始目標模型的建立

本文采用目標感興趣的最小外接矩形標識目標區域，該矩形窗口含有n個像素點，區域的尺寸就是核函數的帶寬大小。假設初始目標區域，且用 ｛xi｝來表示，其中i＝1，2，...，n，其中心為x0。那么初始目標模型的特征值u概率密度如下所示

1.2 候選目標模型描述

同理，如果在當前幀中得到的運動目標的質心點的坐標為y0，那么在下一幀及以后的圖像序列中，可能包含有運動目標的區域稱之為候選模型區域，而且候選區域的質心點的坐標為y1，該候選區域中的像素用 ｛xi｝來表示，其中i＝1，2，…，nh

參照式 （1）

它也是歸一化常數。

1.3 相似性度量函數

本文相似性度量函數采用Bhattacharyya系數，其定義為

1.4 目標定位

為使收斂到最大值，先以第N－1幀的質心坐標為第N幀中目標區域的質心點坐標，再以該點作為起始位置的領域內搜索運動目標。將式 （3）在模板的起始位置質心點處做泰勒展開如下所示

其中權值為

式 （4）中第一項泰勒項為常量與要搜索的新的質心y無關，因此要求得最大，只需第二項泰勒項最大即可，第二項泰勒項其實也是一個核函數密度估計。為了獲得最大的，我們可以計算第二項泰勒項的Mean Shift向量，即候選區域質心向真實的目標區域的質心移動的向量

其中g（x）＝－k′（x），算法還得經過一系列迭代運算，最終找到最優的質心。

2 核函數帶寬的改進

2.1 傳統自適應帶寬選擇策略

第一種方法為增量試探法：先假設一個變換量α（0 ＜α＜1），然后對原帶寬H 進行增加和減小α得H1和H2，分別計算帶寬H、H1和H2對應的Bhattacharyya系數，選擇其中使Bhattacharyya系數取得最大值的帶寬值作為新的帶寬值作為最佳跟蹤窗口尺寸。但此方法在目標尺寸逐漸增大時效果不明顯。原因是采用Bhattacharyya系數對兩個模板進行相似性測量，Bhattacharyya系數經常會在小的跟蹤窗口中達到局部的最大值。

另一種尺度變換方法：仿射變換法自適應帶寬選擇策略，其原理是如果運動目標運動過程投影近似一個平面運動過程或運動目標本身為剛性物體，那么相鄰倆幀之間目標的尺度變化采用仿射變化來表示，之后采用一些特征匹配手段獲得到運動目標運動過程中的仿射變換的參數，進而計算出帶寬。但此方法需要分別針對尺度、角度等做多點相關的計算，計算過程繁瑣，運算量太大，難以滿足實時性的實際要求。

2.2 本文帶寬跟新方法

分析了傳統帶寬跟新的方法，本文提出一種可以預先分析出運動目標尺度變化趨勢的方法。

（1）根據與初始模型的相似度來確定點的權值，按權值來統計中心點位置和分布廣度

式中：H、W 為初始目標模上標示運動目標區域的高和寬，h、w 為預估計當前幀圖像中標示運動目標區域的高和寬；devorig為初始目標模板質心點的分布廣度，dev為候選目標模型的質心點的分布廣度。

（2）本文提出四級同心正方形法對目標尺寸變化趨勢預測機制。

四級正放形區域劃分與變長如圖1所示。

圖1 四級正放形區域劃分與變長

四級同心正方形組以初始目標模型的質點為中心，建立4級同心的正方形組，本文約定從外向內，分別為第一層、第二層、第三層、第四層。四層正方形的邊長比例設定為1∶2∶3∶4。

本文中最外層正方形的邊長為初始模板的中標示運動目標區域的矩形框的寬W 和高H 間的最小值。即

在初始運動目標模板上的質心點和下一幀中確定質心的候選模板區域上的質心點也處，分別建立四級同心正方形，四級同心正方形的中的第四層各自包圍了一個正方形區域Region＿A0 和Region＿B0。通過上述四級同心正方形組分割出4 個區域分別為Region＿A0、Region＿A1、Region＿A2、Region＿A3；同理Mean Shift算法收斂點（即候選模板）分割出4個區域分別為Region＿B0、Region＿B1、Region＿B2、Region＿B3。當運動目標尺寸變大，初始目標模板中的區域Region＿A1，對應的像素點應該大部分對應的擴散到候選目標區域Region＿B2；當運動目標尺寸變小，初始目標模板中的區域Region＿A1對應的像素點大部分收縮到候選目標區域的Region＿B0。用ρ10、ρ11、ρ12分別代表區域Region＿A1和區域Region＿B0、Region＿A1和區域Region＿B1、Region＿A1和區域Region＿B2建立的模型間的Bhattacharyya距離。類似我們可以取得到ρ21、ρ22、ρ23。

候選模板和初始模板間的正方形組匹配如圖2所示。

圖2 候選模板和初始模板間的正方形組匹配

根據上述目標尺度的變化和Region＿A1與 ｛Region＿Bi｝i＝0，1，2之間的變化關系，可以得出如下結論：當運動目標的尺度幾乎無變化時，ρ10、ρ11、ρ12三者之中應該ρ11最大，同時對于ρ21、ρ22、ρ23三者之中ρ22最大；同理，運動目標的尺度縮小時，相應區域Region＿A1中表征運動目標的特征收縮到區域Region＿B0中，因此ρ10和ρ21取到最大值；運動目標尺度增大時，ρ12和ρ23應該取到最大值。因此通過回字形區域的直方圖相似度間的關系可以用來確定運動目標的尺度變化的趨勢。ρ10、ρ11、ρ12之間最大值和運動目標尺度變化關系如圖3所示。

圖3 之間最大值和運動目標尺度變化關系

2.3 帶寬選擇

（1）在當前幀中找到Mean Shift算法找到收斂點，即當前幀中的候選目標的質心點，以該質心點為中心，分別以初始目標模板的寬Wpre和高Hpre，采用增量試探法中建立矩形的方式分別建立3個矩形。高分別為H1，H，H2，寬分別為W1，W，W2

再建立以式 （9）和式 （10）中預測的當前幀中目標模板的寬w 和高h，采用增量試探法中建立矩形的方式分別建立3 個矩形。高分別為h1，h，h2，寬分別為w1，w，w2。本文中α取值為10%。

（2）距離決策機制：首先我們在選取初始模板的同時要記錄其質心點的位置坐標 （xorigin，yorigin）。在當前幀中采用Mean Shift算法找到收斂點，即當前幀中的候選目標的質心點 （x1，y1）。在該點處，仿照式 （5）分別計算ρ10、ρ11、ρ12、ρ21、ρ22、ρ23。

1）若ρ12＞ρ10，ρ12＞ρ11且ρ23＞ρ21，ρ23＞ρ22；表明運動目標的尺度變大，對H、H2、h、h2進行對比，Bhattacharyya距離最大者就是尺度最優，即作為當前幀中運動目標的尺度也就是新的核函數的帶寬。

2）若ρ11＞ρ10，ρ11＞ρ12且ρ22＞ρ21，ρ22＞ρ23；表明當前的目標尺度無較大變化，因此對H、H1、H2、h、h1、h2進行對比，Bhattacharyya距離最大者作為當前幀中運動目標的尺度也就是新的核函數的帶寬。

3）若ρ10＞ρ11，ρ10＞ρ12且ρ21＞ρ22，ρ21＞ρ23；表明運動目標的尺度變小，對H、H1、h、h1這4個尺度對比，Bhattacharyya距離最大者作為當前幀中運動目標的尺度也就是新的核函數的帶寬。

（3）減小計算量的改進方法：在采用Mean Shift算法進行目標跟蹤時，需要在每一幀圖像上進行迭代收斂計算，運算量太大導致跟蹤系統時效性降低。本文在跟蹤過程中由于權重涉及到開平方運算，在每幀Mean Shift算法迭代收斂時需要多次計算權重，因此希望找到一種有效的方法降低權重計算時的運算量。本文中采用＝代替，由式 （5）可得

3 實驗與結果分析

本文以車輛和行人兩類監控場景進行實驗，來驗證本文算法的效果。

實驗一為對車輛采用Mean Shift算法進行跟蹤的結果。本文分別對視頻序列中的第851 幀、第1050 幀、第1075幀、第1750幀進行了展示，并且相對初始幀750幀時目標尺度呈逐漸增大的趨勢。其中圖4 （a）～ （d）的左邊實驗圖為核函數的帶寬固定時的Mean Shift算法的跟蹤效果，居中實驗圖為核函數的帶寬采用增量試探法時的Mean Shift算法的跟蹤效果，右邊實驗圖為核函數的帶寬采用多級正方形法時Mean Shift算法的跟蹤效果。

從上述結果中可以得出，本文算法所得效果最好。當目標靠近攝像頭時，目標尺度變大，Mean Shift算法不能很好的標識運動目標。圖4 （b）、（c）顯示核函數帶寬采用增量試探法時，Mean Shift算法可能在局部區域得到極大值，即局部收斂。而核函數帶寬采用多級正方形法時，則不會出現突然收斂到局部極大值處，同時也避免了核函數帶寬固定的弊端。

表1數據表明當目標尺度在逐漸增大時，該幀相對應的ρ12＞ρ10，ρ12＞ρ11，ρ23＞ρ21，ρ23＞ρ22是完全成立的。

實驗二該實驗是對行人目標進行跟蹤的過程，實驗過程目標遠離攝像頭。

3種帶寬更改策略下的行人跟蹤效果如圖5所示。

表2數據表明當目標尺度在逐漸增大時，該幀相對應的ρ10＞ρ11，ρ10＞ρ12，ρ21＞ρ22，ρ21＞ρ23是完全成立的。

圖4 3種帶寬更改策略下的車輛跟蹤效果

表1 車輛視頻幀不同回字形區域相對應的ρ值

圖5 3種帶寬更改策略下的行人跟蹤效果

表2 行人視頻幀不同回字形區域相對應的ρ值

4 結束語

本文分析了傳統Mean Shift算法中核函數帶寬的固有缺陷，分析了現有方法的不足，提出了本文的算法。新算法首先采用目標質心點的分布散度和增量試探法計算出幾個目標的可能變化尺度，然后采用多級正方形匹配的方法對目標的運動趨勢進行預測，然后把Bhattacharyya距離最大者的尺度作為當前幀中核函數的帶寬，減少了每幀中所需計算的像素的數量和背景噪聲的影響，實現了對運動目標的有效跟蹤。

［1］ZHANG Juan，MAO Xiaobo，CHEN Tiejun.Summary of moving target trac－king algorithm ［J］.Application Research of Computer，2009，26 （12）：4407－4410 （in Chinese）. ［張娟，毛曉波，陳鐵軍.運動目標跟蹤算法研究綜述 ［J］.計算機應用研究，2009，26 （12）：4407－4410.］

［2］YU Dan，WEI Wei，ZHANG Yuanhui.Dynamic target tracking with Kalman filter as predictor ［J］.Opto－Electronic Engineering，2009，36 （1）：52－56 （in Chinese）. ［虞旦，韋巍，張遠輝.一種基于卡爾曼預測的動態目標跟蹤算法研究［J］.光電工程，2009，36 （1）：52－56.］

［3］YUAN Shengzhi，XIE Xiaofang，LI Hongzhou.Bandwidthadaptive tracking algorithm based on Kalman－Mean Shift method ［J］.Laser and Infrared，2009，29 （5）：558－561 （in Chinese）. ［袁勝智，謝曉方，李洪周.一種基于Kalman－Mean Shift的自適應跟蹤算法 ［J］.激光與紅外，2009，29（5）：558－561.］

［4］TIAN Gang，HU Ruimin，WANG Zhongyuan.A Mean Shift target tracking algorithm based on motion vector analysis［J］.Journal of Image and Graphics，2010，15 （1）：85－90 （in Chinese）.［田綱，胡瑞敏，王中元.一種基于運動矢量分析的Mean Shift目標跟蹤算法 ［J］.中國圖象圖形學報，2010，15（1）：85－90.］

［5］YAN Jia，WU Minyuan，CHEN Shuzhen，et al，Adaptive tracking window Mean Shift tracking algorithm ［J］.Optics and Precision Engineering，2009，17 （10）：2606－2611 （in Chinese）.［顏佳，吳敏淵，陳淑珍，等.跟蹤窗口自適應的Mean Shift 跟蹤 ［J］.光學精密工程，2009，17 （10）：2606－2611.］

［6］LIU Xin，LIU Hui，QIANG Zhenping，et al.Adaptive Background modeling based on mixture Gaussian model and frame subtraction ［J］.Journal of Ima－ge and Graphics，2008，13（4）：729－734 （in Chinese）. ［劉鑫，劉輝，強振平，等.混合高斯模型和幀間差分相融合的自適應背景模型 ［J］.中國圖象圖形學報，2008，13 （4）：729－734.］

［7］Chen Y T，Chen C S，Huang C R.Efficient hierarchical method for background subtraction ［J］.Pattern Recognition，2007，40（10）：2706－2715.

［8］LI Peihua，XIAO Lijuan.Mean Shift based object tracking with similarity and affine transformations ［J］.Journal of Image and Graphics，2011，16 （2）：258－266 （in Chinese）.［李培華，肖麗娟.基于Mean Shift的相似性變換和仿射變換目標跟蹤算法 ［J］.中國圖象圖形學報，2011，16 （2）：258－266.］

［9］BAI Xiangfeng，LI Aihua，LI Xilai.Mean－Shift tracking algorithm based on adaptive bandwidth ［J］.Journal of Computer Applications，2011，31 （1）：254－257 （in Chinese）. ［白向峰，李艾華，李喜來.窗寬自適應Mean－Shift跟蹤算法 ［J］.計算機應用，2011，31 （1）：254－257.］

［10］WANG Wenjiang，HUANG Shan，ZHANG Hongbin.Bandwidth－adaptive tracking algorithm based on Mean Shift and Kalman prediction ［J］.Computer Engineering＆Science，2013，35 （5）：87－92 （in Chinese）. ［王文江，黃山，張洪斌.一種基于Mean Shift和Kalman預測的帶寬自適應跟蹤算法 ［J］.計算機工程與科學，2013，35 （5）：87－92.］