張京愛，李群，李鵬飛，王江濤

（淮北師范大學(xué)物理與電子信息學(xué)院，安徽淮北235000）

在視頻序列中對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行持續(xù)跟蹤是計(jì)算機(jī)視覺的一個(gè)重要任務(wù)，其被廣泛應(yīng)用在人機(jī)交互、智能監(jiān)控、醫(yī)學(xué)圖像處理等領(lǐng)域。目標(biāo)跟蹤的本質(zhì)是在圖像序列中識(shí)別出目標(biāo)的同時(shí)對(duì)其進(jìn)行精確定位，為了克服噪聲、遮擋、背景的改變等對(duì)目標(biāo)識(shí)別帶來的困難，出現(xiàn)了很多的跟蹤算法。基于區(qū)域的跟蹤算法通過使一個(gè)損耗函數(shù)最小化來對(duì)連續(xù)圖像序列間的目標(biāo)區(qū)域進(jìn)行跟蹤，而基于特征的跟蹤算法則通過特征抽?。ū热缌炼取㈩伾?、邊緣、輪廓等）來建立模型圖像與目標(biāo)圖像間的對(duì)應(yīng)關(guān)系，進(jìn)而確定目標(biāo)的位置。多數(shù)算法采用了統(tǒng)計(jì)手段對(duì)圖像中的被跟蹤的區(qū)域或像素進(jìn)行表達(dá)，在有參的情況下，目標(biāo)物體通常假定為一高斯混合模型，通過非線性估計(jì)即可獲得目標(biāo)模型的各項(xiàng)參數(shù)。然而在實(shí)際應(yīng)用中，高斯混合模型并不適用于實(shí)際中多峰、復(fù)雜的概率密度情形；與之相比，非參數(shù)密度估計(jì)手段則能克服高斯混合模型的缺點(diǎn)，對(duì)復(fù)雜的概率密度進(jìn)行精確的估計(jì)。在非參數(shù)密度估計(jì)手段中，直方圖對(duì)于跟蹤可變化的非剛性物體具有較好的柔性和魯棒性，然而由于受到維數(shù)的限制（維數(shù)隨著顏色數(shù)目指數(shù)增加），其只適合于低維空間，而基于核的密度估計(jì)，只要給定足夠的樣本，就可以適用于低維和高維空間，與前者相比具有更大的應(yīng)用空間。

Mean-Shift（均值偏移）算法最先由Fukunaga和Hostetler提出[1]，其后Comaniciu成功地將其應(yīng)用于計(jì)算機(jī)視覺領(lǐng)域中[2-3]，近年來，Mean-shift算法以其無需參數(shù)、快速模式匹配的特性[4]被廣泛應(yīng)用到目標(biāo)跟蹤領(lǐng)域，其作為一個(gè)基于梯度分析的優(yōu)化算法被有效地用來對(duì)目標(biāo)定位。目前在Mean-Shift框架下的研究主要集中于核窗寬的自適應(yīng)選擇[5-6]，以及采用新的目標(biāo)表達(dá)模型和相似函數(shù)等領(lǐng)域[7-8]；然而對(duì)于如何減少算法的迭代次數(shù)，增強(qiáng)算法對(duì)實(shí)時(shí)性的適應(yīng)能力的研究卻不多見。本文在介紹和分析基于核密度估計(jì)的Mean-Shift跟蹤基礎(chǔ)上，提出了一種新的偏移向量求解方法，對(duì)偏移加權(quán)系數(shù)進(jìn)行二次加權(quán)，以提高跟蹤算法的實(shí)時(shí)性能。

1 基于核密度估計(jì)的模型表達(dá)

由于非參數(shù)估計(jì)方法不需要指明樣本所服從的概率密度模型，因而其更適用于樣本分布未知的情形，特別是在計(jì)算機(jī)視覺領(lǐng)域中，很多情況下由于數(shù)據(jù)在特征空間中不規(guī)則的聚類而導(dǎo)致樣本的概率密度分布不能用通用的參數(shù)估計(jì)手段精確的表達(dá)，基于核函數(shù)的概率密度估計(jì)作為最有效的非參數(shù)估計(jì)手段之一，已被廣泛的應(yīng)用到各個(gè)領(lǐng)域中。

其中Kh為核函數(shù)，其窗寬為h，多元情況下，上式可以改寫為：

這里x，xi，i=1...N均為d維向量。

假設(shè)給定兩幅圖像，其中一幅包含有被跟蹤的目標(biāo)，稱之為“模型圖像“，另一幅圖像則稱之為“候選圖像“；目標(biāo)跟蹤的任務(wù)就是在“候選圖像“中找出被跟蹤的目標(biāo)，并對(duì)其精確定位。模型圖像中的采樣點(diǎn)表示為Ix={xi，ui}，此處xi為像素在圖像中的二維坐標(biāo)，而ui則為該像素對(duì)應(yīng)的特征向量。物體的顏色特征因其不易受光照的影響具有較強(qiáng)的魯棒性，且計(jì)算量小的優(yōu)點(diǎn)，因而采用顏色作為目標(biāo)的特征空間得到了廣泛的重視，本文中模型的特征空間為量化后的顏色空間。候選圖像中的采樣點(diǎn)表示為Iy={yi，vi}Mj=1，同樣給出了采樣點(diǎn)的二維坐標(biāo)和對(duì)應(yīng)的特征向量。將目標(biāo)的顏色空間量化為m個(gè)互不相交的特征子空間，則采樣點(diǎn)的坐標(biāo)和其所屬的特征向量可以通過函數(shù)b:R2→{1...m}相互關(guān)聯(lián)b（xi），給出了位于xi的像素在量化后的特征空間中所隸屬的特征子空間。

假定目標(biāo)在模型圖像中中心坐標(biāo)為0，且經(jīng)過正則化后其窗寬為1。采用核函數(shù)估計(jì)，則顏色u=1...m在目標(biāo)模型中的概率，即核函數(shù)直方圖，可以由下式給出：

這里δ為Kronecker delta函數(shù)，C則為歸一化參數(shù)，其保

同理，采用同樣的核剖面函數(shù)k（x），令核窗寬為h，則在候選圖像中中心坐標(biāo)位置為y的核窗口內(nèi)，其核函數(shù)直方圖可以表示為：

其中Ch為歸一化參數(shù)。

則由式（3）和式（5）可得目標(biāo)和候選目標(biāo)的表達(dá)模型分別為：

隨著信息技術(shù)的飛速發(fā)展和大數(shù)據(jù)時(shí)代的到來，“徐玉玉案”的發(fā)酵、熱議，越來越多的傳統(tǒng)犯罪模式逐漸轉(zhuǎn)變?yōu)樾滦途W(wǎng)絡(luò)犯罪模式，即利用信息數(shù)據(jù)進(jìn)行違法和犯罪活動(dòng)？

2 Mean-Shift跟蹤算法

Mean-Shift算法以其無需參數(shù)、快速模式匹配的特性被廣泛應(yīng)用到目標(biāo)跟蹤領(lǐng)域，其通過分析當(dāng)前區(qū)域概率密度的梯度來不斷向某個(gè)概率密度的極值偏移，最終達(dá)到收斂點(diǎn)，該點(diǎn)即為所尋找的模式的位置。采用Mean-Shift算法進(jìn)行目標(biāo)跟蹤時(shí)，首先在第一幀圖像中對(duì)目標(biāo)模型進(jìn)行初始化，然后在相鄰圖像序列中對(duì)目標(biāo)模型所在位置的周圍進(jìn)行搜索，相似函數(shù)最大化的候選區(qū)域即為跟蹤目標(biāo)在當(dāng)前幀中所處的位置。選擇一個(gè)參照目標(biāo)模型，然后選擇該模型的特征空間，使用該模型在特征空間中的概率密度函數(shù)作為其表達(dá)。

在前1節(jié)中已知目標(biāo)和候選目標(biāo)的表達(dá)模型為：

將上式重新寫為如下形式：

其中wi為加權(quán)系數(shù)。

由Mean-Shift算法可得偏移后的坐標(biāo)位置如下：

這里g（x）=-k′（x），采用Epanechnikov核，則上式變?yōu)椋?/p>

3 算法的分析及改進(jìn)

當(dāng)視頻序列中目標(biāo)緩慢運(yùn)動(dòng)時(shí)，Mean-Shift算法只需要進(jìn)行一次或少數(shù)幾次迭代便可對(duì)目標(biāo)進(jìn)行準(zhǔn)確定位；然而當(dāng)目標(biāo)運(yùn)動(dòng)速度較快，或者目標(biāo)的核函數(shù)直方圖維數(shù)較低不能高鑒別性的與背景圖像進(jìn)行區(qū)別時(shí)，算法需要數(shù)10次迭代才能對(duì)目標(biāo)收斂，為了克服迭代次數(shù)對(duì)算法實(shí)時(shí)性的影響，有必要對(duì)算法進(jìn)行改進(jìn)以減少均值偏移的迭代次數(shù)。

由式（12）可以看出，核窗口的偏移方向跟距離完全取決于加權(quán)系數(shù)wi，核窗口總是向wi比較大的區(qū)域偏移。在當(dāng)前核窗口所包圍的區(qū)域與目標(biāo)模型完全一致時(shí)，兩者具有相同的特征分布，即=（y）=，此時(shí)所有的wi=1，因此偏移量為0，核窗口位置保持不變。然而，當(dāng)相鄰兩楨圖像中目標(biāo)位置發(fā)生變動(dòng)時(shí)，當(dāng)前核窗口所包圍的區(qū)域與目標(biāo)模型的特征分布存在差異，此時(shí)在當(dāng)前核窗口所包圍的區(qū)域中目標(biāo)所處的位置具有較大的權(quán)值，而其余背景部分則權(quán)值較小，從而使核窗口向目標(biāo)最可能存在的位置偏移，進(jìn)而在局部極大值處收斂。圖1給出了目標(biāo)模型位置發(fā)生移動(dòng)時(shí)，核窗口內(nèi)的顏色分布和權(quán)值分布的示意圖，在圖（a）中實(shí)線矩形框所示的區(qū)域?yàn)楹蜻x模型所在的位置，而虛線矩形框則給出了當(dāng)前目標(biāo)所在的位置，圖（b）和圖（c）則分別給出了當(dāng)前楨中候選目標(biāo)所包含區(qū)域的權(quán)值和特征分布圖，從圖中可以看出，目標(biāo)所在的區(qū)域具有較大的權(quán)值，而背景區(qū)域則權(quán)值較小，從而令候選目標(biāo)的核窗口向權(quán)值大的目標(biāo)區(qū)域偏移。

圖1 候選目標(biāo)模型中的特征分布和加權(quán)系數(shù)Fig.1Feature distribution and weights for candidate target model

顯然，要想能夠準(zhǔn)確地對(duì)目標(biāo)進(jìn)行識(shí)別和定位，目標(biāo)模型的特征分布要明顯的區(qū)別于背景以及其他非目標(biāo)物體的特征分布。在實(shí)際應(yīng)用中，目標(biāo)模型往往可以表征為一種或幾種主要的顏色特征，此時(shí)核窗口區(qū)域內(nèi)的像素點(diǎn)在總體上可以由其所隸屬的顏色特征來區(qū)分是否為目標(biāo)像素或背景像素。令目標(biāo)模型所屬的主要顏色特征集合為F，則可近似的用如下的判別函數(shù)來判斷像素點(diǎn)xi是否屬于目標(biāo)模型。

即如果在當(dāng)前核窗口區(qū)域中像素點(diǎn)xi所隸屬的特征b（xi）屬于集合F，則點(diǎn)xi屬于目標(biāo)模型區(qū)域，否則將點(diǎn)xi視為背景區(qū)域。

對(duì)于屬于當(dāng)前核窗口中的任意像素點(diǎn)xi，有如下定理成立：

證明：

將wnew代入式（12）有：

yc為目標(biāo)模型的形心，得證。

由上述定理得，可以通過調(diào)整式（12）中的權(quán)值來加速對(duì)目標(biāo)的收斂，如果令任意f（xi）不為零的像素點(diǎn)的權(quán)值重新加權(quán)為一足夠大的正數(shù)，則可以一次性的收斂到目標(biāo)模型的形心；然而，為了消除非主要顏色特征對(duì)目標(biāo)定位準(zhǔn)確度的影響，以更加準(zhǔn)確地對(duì)目標(biāo)進(jìn)行定位，在每一次目標(biāo)定位時(shí)均采用2次迭代來完成：第一次迭代為目標(biāo)的粗定位，此時(shí)采用作為權(quán)值求取目標(biāo)形心的近似位置；然后進(jìn)行第二次迭代對(duì)目標(biāo)進(jìn)行精確定位，此時(shí)采用wi作為權(quán)值進(jìn)行位置求解，以消除非主要特征對(duì)定位準(zhǔn)確度的影響，這樣每一次偏移僅需要兩次迭代即可完成對(duì)目標(biāo)的定位。在實(shí)際跟蹤中目標(biāo)物體的主特征和二次加權(quán)的權(quán)值s在目標(biāo)初始化時(shí)可根據(jù)實(shí)際經(jīng)驗(yàn)選定。

4 跟蹤試驗(yàn)

為了驗(yàn)證算法的可行性和有效性，對(duì)不同的圖像序列進(jìn)行了目標(biāo)跟蹤試驗(yàn)。在采用Mean-Shift算法進(jìn)行目標(biāo)定位時(shí)，每一次定位均進(jìn)行2次迭代，第一迭代采用二次加權(quán)后的權(quán)值wnewi，第二次則使用wi作為權(quán)值進(jìn)行均值偏移求解，跟蹤試驗(yàn)中二次加權(quán)系數(shù)均取s=100。

2次跟蹤實(shí)驗(yàn)分別采用了PETS04和PETS01視頻序列，目標(biāo)跟蹤的結(jié)果如圖2、3所示。圖2給出了PETS04視頻序列的跟蹤結(jié)果，該實(shí)驗(yàn)序列長度為100幀，每楨圖像大小為384×288，目標(biāo)核窗口寬度（hx，hy）=（50，70），跟蹤目標(biāo)為對(duì)走動(dòng)的行人，從圖中可以看出即使目標(biāo)突然做快速運(yùn)動(dòng)的時(shí)候（第452幀至470幀），文中給出的算法仍然能夠較為準(zhǔn)確的對(duì)目標(biāo)進(jìn)行定位；圖3則給出了PETS01序列的目標(biāo)跟蹤結(jié)果，該實(shí)驗(yàn)序列長度為50幀，每幀圖像大小為768×576，目標(biāo)核窗口寬度（hx，hy）=（20，50），跟蹤目標(biāo)同樣為對(duì)走動(dòng)的行人，在該序列中目標(biāo)由于對(duì)面行駛來的汽車而發(fā)生了部分的遮擋，但是跟蹤核窗口還是較好地對(duì)目標(biāo)進(jìn)行了定位。

圖2 PETS04序列的跟蹤結(jié)果Fig.2Tracking results of sequence PETSO4

圖3 PETS01序列的跟蹤結(jié)果Fig.3Tracking results of sequence PETS01

由上述兩個(gè)不同視頻序列的跟蹤結(jié)果可知，本文提出的算法具有較高的準(zhǔn)確性和可行性。與文獻(xiàn)[3]中的算法相比，本文的算法在對(duì)目標(biāo)進(jìn)行較為準(zhǔn)確的定位的同時(shí)，每次定位僅需要2次迭代，要明顯少于[3]中的平均4次迭代。

5 結(jié)論

本文提出了一種基于Mean-Shift的目標(biāo)跟蹤新方法。在新方法中，通過對(duì)均值偏移的原理進(jìn)行闡述，分析了偏移向

量與其權(quán)值之間的關(guān)系，根據(jù)不同的顏色特征與目標(biāo)之間的聯(lián)系對(duì)偏移向量的權(quán)值進(jìn)行了二次加權(quán)，這使改進(jìn)后的算法更加有效，只需2次迭代便可對(duì)目標(biāo)進(jìn)行準(zhǔn)確定位。實(shí)驗(yàn)結(jié)果表明，與經(jīng)典的Mean-Shift跟蹤算法相比，該算法在保證了準(zhǔn)確性的同時(shí)具有更好的實(shí)時(shí)性能。

[1]Fukunaga K，Hostetler L D.The estimation of the gradient of a density function，with applications 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，Ramesh V，Meer P.Kernel-based object tracking[J].IEEE Transaction on Pattern Analysis and Machine Intelligence，2003，25（5）:564-577.

[4]Comaniciu D，Meer P.Mean shift:A robust approach toward feature space analysis[J].IEEE Transaction on Pattern Analysis and Machine Intelligence，2002，24（5）:603-619.

[5]Collins R.Mean-shift blob tracking through scale space[C]//In Proceedings of IEEE Computer Society Conference on ComputerVisionandPatternRecognition（CVPR’03），2003:234-240.

[6]Bradski G R.Computer vision face tracking as a component of a perceptual user interface[C]//In Proceedings of IEEE Workshop on Applications of Computer Vision，1998：214-219.

[7]Elgammal A，Duraiswami R，Davis L.Probabilistic tracking in joint feature-spatial spaces[C]//In Proceedings of the IEEE Computer Society Conference on Computer Visionand Pattern Recognition（CVPR’03），2003:781-788.

[8]YANG Chang-jiang，Duraiswami R，Davis L.Efficient Mean-Shift tracking via a new similarity measure[C]//In ProceedingsofIEEEComputerSocietyConferenceon Computer Vision and Pattern Recognition（CVPR’05），2005：176-183.