改進型Mean-Shift算法在行人目標跟蹤中的應用

李亞文，王博

（商洛學院電子信息與電氣工程學院，陜西商洛726000）

改進型Mean-Shift算法在行人目標跟蹤中的應用

李亞文，王博

（商洛學院電子信息與電氣工程學院，陜西商洛726000）

針對傳統(tǒng)Mean-Sshift算法對于運動目標特征變化較快、某些干擾和遮擋等問題而引起目標定位偏差的情況，提出了一種基于改進型的顏色直方圖的Mean-Shift算法，該算法是將顏色直方圖和三重幀間差分的方法相結(jié)合的一種目標跟蹤算法。實驗結(jié)果表明，應用改進后的算法思想，可以較準確的對視頻流中的行人目標進行實時跟蹤，新算法能較好的解決運動目標特征變化較快而引起跟蹤不準確的問題，實現(xiàn)對行人目標進行準確定位跟蹤。

Mean-Shift算法；顏色直方圖；目標跟蹤；核函數(shù)

隨著交通安全和人居環(huán)境等情況的不斷復雜，視頻監(jiān)控技術已經(jīng)廣泛應用于城市道路、地鐵、小區(qū)安防，銀行監(jiān)控等領域，視頻監(jiān)控技術只要實現(xiàn)對感興趣運動目標進行檢測、跟蹤、識別和行為理解等4個步驟[1]，實現(xiàn)對視頻中的運動目標運動估測。其中運動目標的跟蹤技術是視頻監(jiān)控技術的關鍵，檢測出感興趣的運動目標后，進行特征提取、模型建立，并不斷地更新運動目標的位置信息，實現(xiàn)對運動目標的跟蹤。

在20世紀90年代，視頻中的運動目標跟蹤技術得到了快速發(fā)展，其中具有代表性的包括：Condensation算法，粒子濾波算法、Kalman濾波算法和Mean Shift等算法[2-4]，我國視頻檢測跟蹤技術起步較晚，但也取得了一些成果，李源[5]提出了一種層級粒子濾波的跟蹤方法，中科院北京自動化研究所對行人的運動跟蹤、城市交通狀況的視覺監(jiān)控等方面都進行了深入的研究，并取得了一定的研究成果；此外，國防科技大學、電子科技大學、西安電子科技大學等也對視頻監(jiān)控中的目標跟蹤技術做了大量研究，取得了一批研究成果。

目前常見的目標跟蹤算法主要包括5種：區(qū)域的跟蹤、活動輪廓的跟蹤、模型的跟蹤、特征的跟蹤和機器學習的跟蹤[6]等，而Mean-Shift算法就是基于模型的運動目標跟蹤算法，由于其運算量較好，迭代次數(shù)較少，定位準確，因此在運動目標跟蹤中得到了廣泛的應用，傳統(tǒng)的Mean-Shift算法對于運動目標較快，背景變化復雜的物體很難進行跟蹤，因此，為了實時跟蹤運動狀態(tài)變化較快的目標，本文提出了一種改進型的顏色直方圖的Mean-Shift算法，該算法是一種顏色直方圖和三重幀間差分相結(jié)合的行人目標檢測算法，并在實驗中進行了算法實現(xiàn)。

1 Mean-Shift算法原理

設二維實數(shù)空間中有樣本點則位于點的向量定義[7]為：

式(1)中，是以xi為原點，x為半徑的球形區(qū)域內(nèi)的點的集合，該集合可以表示為式(2)。

其中，h是偏移向量，即落入半徑為x的區(qū)域內(nèi)的樣本點的數(shù)目，也是樣本點對應于點的偏移向量求和后的平均向量。如圖1箭頭所示，Mean-Shift向量的方向是樣本分布較多的方向，圖1中，偏移向量用箭頭線段表示，整個區(qū)域的范圍用大圓圈表示，小圓圈內(nèi)的黑點表示基準點，而小圓圈表示樣本點，且基準點朝著樣本分布最多的方向。

圖1 Mean-Shift向量指示圖

設d維歐式空間中存在點x，用列向量表示x的模：||x||2=XTx，若函數(shù)K的剖面函數(shù)為k，k∈[0，∞]，則核函數(shù)[7-8]可以用式(3)表示，其剖面函數(shù)在有限區(qū)間內(nèi)是連續(xù)且非增的函數(shù)。

由于受到到原點距離不同的影響，每個樣本點重要性不一樣，因此引入了權重系數(shù)的概念，基本的向量擴展[9]如式(4)所示：

在式(4)中，w(xi）是賦給采樣點的權重系數(shù)，Gh(x)是半徑為h的單位核函數(shù)。假設在d維空間中存在n個采樣點xi(i=1，…，n)，則概率密度函數(shù)f(hx)的核函數(shù)估計為：

其中W(xi)是賦給采樣點xi(i=1，…，n)的權重系數(shù)，k(x)是核函數(shù)K(x)的剖面函數(shù)，它們之間的關系可以表示為：

g(x)是k(x)的負導函數(shù)，即，g(x)=-k′(x)是核函數(shù)為G(x)的剖面函數(shù)，即：

f(x)的梯度[10]為：

代入g(x)和G(x)函數(shù),則概率密度函數(shù)梯度又可以表示為：

在式(9)中，Mh(x)是Mean-Shift向量，fG(x)是以G(x)為核函數(shù)的概率密度函數(shù)[11-12]，這樣，得到Mh(x)為：

從式（10）中可以看出，概率密度增加的最大的方向即Mh(x)的指向，通過核函數(shù)G(x)在x點計算就可以得到Mean-Shift，向量Mh(x)跟與核函數(shù)K(x)估計的概率密度函數(shù)f(x)的梯度之間是正比例關系，Mean-Shift算法也就是迭代的步驟[13]，變換Mh(x)為：

在初始點x給定時，G(x)為核函數(shù)，容許的最小誤差就是ε，那么Mean-Shift算法歩驟可以表示3步：

Step1：計算m(x)；

Step2：將m(x)值賦給x；

Step3：如果滿足||m(x)-x||＜ε，跳出循環(huán)，若不滿足，則繼續(xù)執(zhí)行Step1。

Mean-Shift算法的3步實現(xiàn)步驟都是不斷地移向概率密度梯度方向，直到歩長||m(x)-x||＜ε時，移動才會結(jié)束，跳出循環(huán)，這個時候Mean-Shift算法收斂達到概率密度的最高點，歩長的大小與密度成反比關系。

2 改進型的顏色直方圖模型的Mean-Shift算法

2.1 算法思想

本文提出基于顏色直方圖模型的Mean-Shift算法，該算法是一種將顏色直方圖和三重幀間差分的方法相結(jié)合的行人目標跟蹤算法，行人目標建模是通過RGB顏色空間中的顏色直方圖來完成的。所建立的目標模板一般是由一個規(guī)則的閉合線條所包圍的子圖來確定。減少計算量就需要將每個通道的灰度值量化到M區(qū)間中。量化后的特征值取值范圍可以用U=1，…，N來表示，子圖像素信息可抽象為{xi*}，i=1，…，n來表示?？梢杂檬?12)來表示目標模型[13-14]：

在式(12)中，h代表的是帶寬函數(shù)，是跟蹤框大小的二分之一。k(xi)可以通過弱化邊緣像素，增強算法的抗遮擋能力，從而突出中心像素，在一定程度上，可以抑制由于背景變換較快而引起的跟蹤誤差。目標模型的概率密度分布用q表示，qu表示q的第u特征分量的概率密度，δ具有判斷b(xi*)所屬特征區(qū)間的作用。C為標準化常量系數(shù)使，因此。

在后續(xù)幾幀中目標可能出現(xiàn)的候選區(qū)域的內(nèi)容可抽象為nh個像素點，用{xi}，i=1，…，nk表示，用y表示其中心位置。那么候選目標模板的概率可以用核函數(shù)直方圖分布來表示為：

ρ的取值范圍是由0到1之間，候選模型與目標模型越是相似度越高，ρ的值也就越大，在有限步驟求得合適的y使得ρ(y)值最大計算ρ(y)在y0處的泰勒級數(shù)展開式，能夠得到：

在式(15)中可以看到，該子項表示在當前圖像中y點處核函數(shù)的密度估計，并通過{xi}，i=1，…，nh進行了加權。只要最大化式（15）中的第二項就可以使得p(y)變得最大，所以這個問題轉(zhuǎn)化為求解wi表示的核密度估計函數(shù)的問題。在求解過程中，核函數(shù)逐步遞歸會向y1移動：其中核函數(shù)選擇了Epanechnikov核，所以y1可以表示為：

根據(jù)分析的算法思想，提出的改進型的顏色直方圖模型的Mean-Shift算法實現(xiàn)流程（見圖2）。

圖2 改進型的顏色直方圖模型的Mean-Shift算法流程圖

2.2 改進型的Mean-Shift算法在運動目標跟蹤中的應用

該算法主要可以應用于監(jiān)控視頻包括交通安全、小區(qū)安防、居家安全、ATM監(jiān)控等視頻流中對行人的跟蹤，具體的實現(xiàn)過程如圖3所示，主要包括5步完成。

圖3 視頻流中行人目標的跟蹤

1）首先輸入視頻文件解開為多幀圖像序列，判斷是否為首幀圖像，如果是，則提取首幀圖像進行灰度化處理、膨脹腐蝕模板設置和閾值設置等相關的初始化操作。

2）如果不是首幀圖像，則先對圖像進行合理的背景建模。包括背景差分、二值化、形態(tài)學處理、前景輪廓檢測等操作。對運動區(qū)域進行檢測和提取所采用的方法是改進三幀差分算法。

3）從待檢測候選區(qū)域提取的有效運動區(qū)域進行檢測，采用SVM分類器進行判斷。這樣可以較為精確的定位行人目標的運動信息，包括大小、速度等。

4）當運動目標進行有效候選待測區(qū)域，就對其進行基于改進型的Mean-Shift的行人跟蹤算法，用矩形框框出行人目標，并進行實時跟蹤。當行人目標離開有效檢測區(qū)域后就會產(chǎn)生計數(shù)，并輸出目標跟蹤的矩形跟蹤結(jié)果。

5）重復上述步驟2）至步驟4）一直判斷、跟蹤、計數(shù)，直到判斷是否為末幀，如果為末幀，就可以結(jié)束程序了，如果不是末幀，那么就返回到步驟2），繼續(xù)執(zhí)行各個步驟。

3 實驗仿真與結(jié)果分析

3.1 傳統(tǒng)的Mean-Shift的行人跟蹤

實驗中對現(xiàn)有的一段室內(nèi)羽毛球館的視頻進行分析，將18 s的視頻文件解開為511幀圖像，應用傳統(tǒng)的Mean-Shift的算法對室內(nèi)羽毛球館的一個運動員進行實時行為跟蹤，如圖4所示，提取第4幀、第15幀和第46幀，實驗結(jié)果表明，傳統(tǒng)的Mean-Shift算法對于目標運動特征變換緩慢時可以實現(xiàn)對藍色服裝的運動員的準確跟蹤與定位，然而，當運動員進入比賽狀態(tài)后，運動速度比較快時，傳統(tǒng)的Mean-Shift算法已經(jīng)不能對目標進行跟蹤了，如圖5所示，對視頻流中的第115幀、第222幀和第464幀進行目標跟蹤時，矩形框內(nèi)已將不能準確跟蹤藍色服裝的運動員的運動情況。

圖4 傳統(tǒng)Mean-Shift的行人跟蹤

圖5 目標變化較快時的跟蹤

3.2 改進型Mean-Shift的行人跟蹤

實驗環(huán)境為Matlab2014（a），對錄制的一段監(jiān)控視頻流進行實驗，應用本文提出的基于顏色直方圖模型的Mean-Shift算法對視頻流中的行人進行跟蹤。這里選取的是RGB顏色空間，核函數(shù)釆用Epanechnikov核。在實驗中，對視頻流中運動著的行人進行了全程跟蹤。將采集的監(jiān)控視頻move.avi，解開為298幀圖像，實驗中任意選取視頻流中的第1、13幀圖像，進行行人目標跟蹤，如圖6(c)，圖7(a)所示。其中在第1幀中手動選取了一個矩形框，這個矩形框包含了所有的行人目標的具體特征，主要包括目標的大小、運動的方向和速度的大小等，將該矩形框所包含的行人目標的特征信息作為跟蹤模板，在后續(xù)的多幀圖像中以此模板為基礎進行特征信息的更新，實現(xiàn)對運動目標的跟蹤。由于行人在運動過程中，外界環(huán)境變換較少，主要是運動中的行人胳膊，腿的不斷變化，應用顏色特征具有旋轉(zhuǎn)不變的特性，可以較準確的跟蹤行人的運動軌跡。如圖6(c)，圖7(a)所示分別為對第1幀和第13幀中行人的跟蹤情況，并對視頻流中的不連續(xù)圖像幀第78幀和第106幀中的行人運動進行了跟蹤，如圖7中(b)、(c)所示，應用改進的直方圖模型的Mean-Shift算法，可以實現(xiàn)對視頻流中的行人運動目標進行清晰、準確的跟蹤。

圖6 原視頻流中的圖像幀

圖7 行人運動目標跟蹤

4 結(jié)語

行人跟蹤相比車輛等形狀固定的物體跟蹤來說具有復雜性，主要表現(xiàn)在行人的運動速度大小不定，周圍環(huán)境復雜多變等，這些不定因素的存在都使得行人目標跟蹤的難度有所加大。針對傳統(tǒng)Mean-Shift算法對于運動目標特征變化較快、某些干擾和遮擋等問題而引起目標定位偏差的情況，本文在綜合各種算法的優(yōu)缺點的基礎上，提出了一種基于改進型的顏色直方圖的Mean-Shift算法，改進型的算法是將顏色直方圖和三重幀間差分的方法相結(jié)合的行人目標跟蹤算法。通過對錄制一段視頻流進行行人目標跟蹤，基于顏色直方圖的Mean-Shift算法應用Epanechnikov核作為核函數(shù)，通過建立候選模型向量，計算模型權重，確定候選模型目標位置，送入SVM分類器進行判斷，對有效檢測區(qū)域的行人目標進行準確跟蹤，實驗結(jié)果表明，該算法能較好的跟蹤行人的運動軌跡，即使在行人目標運動變化時，依然能準確的鎖定運動目標，實現(xiàn)準確定位與跟蹤。

[1]楊輝,劉軍,阮松,等.基于Mean-Shift算法視頻跟蹤研究[J].計算機工程與設計,2013,34(6)：2062-2066.

[2]鄒青志,黃山.一種基于Mean-Shift的快速跟蹤算法[J].計算機科學,2017,44(3)：278-282.

[3]張賽鈺,朱小玲,汪衍廣,等.基于幀差法與Mean-shift算法相結(jié)合的運動熔滴識別與跟蹤方法[J].上海交通大學學報,2016,50(10)：1605-1608.

[4]鄭鵬.基于改進Mean-shift算法的目標跟蹤技術研究[D].鄭州：華北水利水電大學,2015：6-8.

[5]梁新華,潘泉,楊峰,等.基于兩級采樣的粒子濾波檢測前跟蹤算法[J].系統(tǒng)工程與電子技術,2011,33(9)：1921-1926.

[6]劉晴,唐林波,趙保軍,等.改進的Mean-shift目標跟蹤算法[J].系統(tǒng)工程與電子技術,2013,35(6)：1318-1323.

[7]武海巍,于海業(yè),田彥濤,等.基于核函數(shù)與可見光光譜的大豆植株群體凈光合速率預測模型[J].光譜學與光譜分析,2016,36(6)：1831-1836.

[8]李華亮,錢志鴻,田洪亮,等.基于核函數(shù)特征提取的室內(nèi)定位算法研究[J].通信學報,2017,38(1)：158-167.

[9]汪海燕,黎建輝,楊風雷,等.支持向量機理論及算法研究綜述[J].計算機應用研究,2014,31(5)：1281-1286.

[10]郭明瑋,趙宇宙,項俊平,等.基于支持向量機的目標檢測算法綜述[J].控制與決策,2014,29(2)：193-200.

[11]馬正華,顧蘇杭,戎海龍,等.基于SIFT特征匹配的CamShift運動目標跟蹤算法[J].計算機科學,2014,41(6)：291-294,323.

[12]惠國保,童一飛,李東波,等.基于改進的圖像局部區(qū)域相似度學習架構(gòu)的圖像特征匹配技術研究[J].計算機學報,2015,38(6)：1148-1161.

[13]尚明姝.基于改進SIFT特征匹配的快速圖像拼接算法[J].微電子學與計算機,2014,31(1)：64-67.

[14]余旺盛,田孝華,侯志強,等.基于關鍵區(qū)域特征匹配的視覺跟蹤算法[J].電子學報,2014,42(11)：2150-2156.

（責任編輯：李堆淑）

On Application of an Improved Mean-Shift Algorithm in Pedestrian Target Tracking

LI Ya-wen,WANG Bo
(School of Electronic Information and Electrical Engineering,Shangluo University,Shangluo726000,Shaanxi)

In traditional Mean-Shift algorithm,the target location has some deviation because of the rapidly changing characteristic,the disturbances and occlusion,therefore an advanced color histogram Mean-Shift algorithm is proposed,which combines the color histogram with the triple frame difference method.Simulation results show that the advanced new algorithm can track the pedestrian target accurately.In addition,it can avoid the problem of inaccurate location in the condition of quickly changing characteristics.

Mean-Shift algorithm;color histogram;target tracking；kernel function

TP273

：A

：1674-0033（2017）04-0010-05

10.13440/j.slxy.1674-0033.2017.04.003

2017-05-05

商洛學院科研基金項目（16SKY002）

李亞文，女，陜西華縣人，碩士，講師