李亞文，王博

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

改進(jìn)型Mean-Shift算法在行人目標(biāo)跟蹤中的應(yīng)用

李亞文，王博

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

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

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

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

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

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

1 Mean-Shift算法原理

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

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

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

圖1 Mean-Shift向量指示圖

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

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

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

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

g(x)是k(x)的負(fù)導(dǎo)函數(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點(diǎn)計(jì)算就可以得到Mean-Shift，向量Mh(x)跟與核函數(shù)K(x)估計(jì)的概率密度函數(shù)f(x)的梯度之間是正比例關(guān)系，Mean-Shift算法也就是迭代的步驟[13]，變換Mh(x)為：

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

Step1：計(jì)算m(x)；

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

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

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

2 改進(jìn)型的顏色直方圖模型的Mean-Shift算法

2.1 算法思想

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

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

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

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

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

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

圖2 改進(jìn)型的顏色直方圖模型的Mean-Shift算法流程圖

2.2 改進(jìn)型的Mean-Shift算法在運(yùn)動(dòng)目標(biāo)跟蹤中的應(yīng)用

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

圖3 視頻流中行人目標(biāo)的跟蹤

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

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

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

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

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

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

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

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

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

圖5 目標(biāo)變化較快時(shí)的跟蹤

3.2 改進(jìn)型Mean-Shift的行人跟蹤

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

圖6 原視頻流中的圖像幀

圖7 行人運(yùn)動(dòng)目標(biāo)跟蹤

4 結(jié)語(yǔ)

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

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

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

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

[4]鄭鵬.基于改進(jìn)Mean-shift算法的目標(biāo)跟蹤技術(shù)研究[D].鄭州：華北水利水電大學(xué),2015：6-8.

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

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

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

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

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

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

[11]馬正華,顧蘇杭,戎海龍,等.基于SIFT特征匹配的CamShift運(yùn)動(dòng)目標(biāo)跟蹤算法[J].計(jì)算機(jī)科學(xué),2014,41(6)：291-294,323.

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

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

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

（責(zé)任編輯：李堆淑）

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

商洛學(xué)院科研基金項(xiàng)目（16SKY002）

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