0 引言

    在計(jì)算機(jī)視覺(jué)領(lǐng)域中的一個(gè)重要研究方向是對(duì)運(yùn)動(dòng)目標(biāo)的跟蹤，而應(yīng)用在運(yùn)動(dòng)目標(biāo)跟蹤方向的一種常用方法是Mean Shift算法,，它是指通過(guò)均值漂逸^[1]的方法,，從目標(biāo)前一幀的真實(shí)位置逐步迭代至當(dāng)前幀目標(biāo)位置的過(guò)程,。FUKUNAGA K等^[2]人在1975年最早提出了該算法,，并由CHENG Y Z^[3]在1995年加入核函數(shù)后改進(jìn)推廣，之后被運(yùn)用到運(yùn)動(dòng)目標(biāo)的跟蹤領(lǐng)域,。

    Mean Shift算法以復(fù)雜度小,、易于集成等優(yōu)點(diǎn)在運(yùn)動(dòng)目標(biāo)跟蹤領(lǐng)域應(yīng)用非常廣泛。并且它采用核函數(shù)直方圖模型,，能夠有效應(yīng)對(duì)目標(biāo)邊緣被遮擋,、目標(biāo)的變形等問(wèn)題。但是單一的Mean Shift算法也存在一些缺點(diǎn),，如在跟蹤過(guò)程中,，由于Mean Shift的核函數(shù)窗口大小是固定不變的，當(dāng)目標(biāo)尺寸變化時(shí)就會(huì)導(dǎo)致跟蹤失敗,。文獻(xiàn)[4]針對(duì)這一點(diǎn)提出了基于運(yùn)動(dòng)矢量分析的Mean Shift核窗寬動(dòng)態(tài)更新模型,，達(dá)到了一定的效果,；COLLINS R T^[5]提出了一種Lindbeger圖像多尺度理論，它在迭代過(guò)程中會(huì)不斷計(jì)算DOG算子與核窗的卷積,，計(jì)算量較大,；文獻(xiàn)[6]提出了三步法，即用正負(fù)10%的核窗口大小與原核窗進(jìn)行3次搜索,，并選擇巴氏距離^[7]最小的為最佳核窗大小,。3次的搜索大大增加了搜索時(shí)間，影響實(shí)時(shí)性,，并且核窗口調(diào)整范圍有限,。彭寧嵩^[8]等提出用形心進(jìn)行配準(zhǔn)來(lái)檢測(cè)角點(diǎn)的方法以及覃劍^[9]提出用邊界力來(lái)約束Mean Shift核窗寬的算法，一定程度上緩解了目標(biāo)變大帶來(lái)的影響,，但是算法仍然都比較復(fù)雜,。文獻(xiàn)[10]針對(duì)目標(biāo)尺寸變化以及目標(biāo)運(yùn)動(dòng)速度快和遮擋問(wèn)題，提出一種結(jié)合光流場(chǎng)的自適應(yīng)Mean Shift跟蹤算法,，提高了跟蹤可靠性,，但它局限于透視變化的先驗(yàn)基礎(chǔ)上，仍然會(huì)出現(xiàn)諸多問(wèn)題,。文獻(xiàn)[11]加權(quán)目標(biāo)區(qū)域像素點(diǎn)空域后,，利用Mean Shift算法搜索其彩色圖像實(shí)現(xiàn)對(duì)快速運(yùn)動(dòng)目標(biāo)的定位，再根據(jù)目標(biāo)縮放因子實(shí)現(xiàn)對(duì)尺寸變化的目標(biāo)的跟蹤,，大大提高了準(zhǔn)確度,，但是增加了計(jì)算量。文獻(xiàn)[12]針對(duì)相似背景顏色干擾問(wèn)題提出多特征自適應(yīng)融合的Mean Shift目標(biāo)跟蹤方法,，但是它的尺寸自適應(yīng)效果并不理想,，影響跟蹤準(zhǔn)確性。綜合前人的方法以及問(wèn)題,，本文提出一種基于邊緣特性的Mean Shift核窗口自動(dòng)調(diào)節(jié)方法,，它是檢測(cè)目標(biāo)區(qū)域的邊緣，根據(jù)形心求取核窗口大小,，核窗口大小會(huì)實(shí)時(shí)地根據(jù)目標(biāo)的尺度變化而變化,，提高跟蹤準(zhǔn)確度，并且算法復(fù)雜度大大減小,。

1 Mean Shift跟蹤技術(shù)

    Mean Shift算法運(yùn)用在運(yùn)動(dòng)目標(biāo)跟蹤時(shí),，首先根據(jù)目標(biāo)特征的概率直方圖建立初始模板，一般選取目標(biāo)的顏色特征,，為了使跟蹤效果更好,，也會(huì)選擇多種特征的結(jié)合；然后在當(dāng)前幀中選擇以前一幀的目標(biāo)真實(shí)位置點(diǎn)為中心,，以固定設(shè)置的Mean Shift搜索半徑為半徑的區(qū)域建立候選目標(biāo)模板,；再對(duì)兩模板進(jìn)行相似性度量,。如果沒(méi)滿足預(yù)設(shè)要求，則以搜索到的新位置為起點(diǎn)繼續(xù)搜索下一位置,，直到滿足預(yù)設(shè)的條件為止,。

    令目標(biāo)模板在前一幀的真實(shí)位置為y₀，在以當(dāng)前幀對(duì)應(yīng)位置y₀為中心的候選目標(biāo)特征概率集合為{p_t(y)|t=1,，…,，d}，由于相鄰兩幀之間間隔很小,，目標(biāo)中心位移不會(huì)發(fā)生很大的跳躍性變化,，所以y總是在y₀附近，則有巴氏系數(shù)ρ(y)在當(dāng)前幀位置y₀的泰勒展開(kāi)近似為：

    按照這個(gè)方法反復(fù)搜索下去,，直到Mean Shift向量滿足||M_h,，g(x)||<ε條件，ε為預(yù)先設(shè)定的允許誤差閾值,，這時(shí)就完成了從上一幀到當(dāng)前幀的目標(biāo)跟蹤任務(wù),。連續(xù)不斷地執(zhí)行上一幀到當(dāng)前幀的搜索，就完成了運(yùn)動(dòng)目標(biāo)的連續(xù)跟蹤,。

2 Mean Shift核窗口自適應(yīng)方法

    Mean Shift算法在運(yùn)動(dòng)目標(biāo)跟蹤領(lǐng)域得到了廣泛的應(yīng)用,，但其固定的核窗口會(huì)導(dǎo)致跟蹤準(zhǔn)確度降低，甚至?xí)?dǎo)致跟蹤失敗,。文中就這個(gè)問(wèn)題提出了一種基于邊緣特性的Mean Shift搜索核半徑自適應(yīng)目標(biāo)的跟蹤方法,。

2.1 固定核窗口跟蹤問(wèn)題 

    視頻畫(huà)面中物體的運(yùn)動(dòng)方式各種各樣，有的保持與攝像機(jī)的距離做各種速度的運(yùn)動(dòng),；有的可能遠(yuǎn)離攝像機(jī)運(yùn)動(dòng),；有的靠近攝像機(jī)運(yùn)動(dòng)。這3種情況下,，目標(biāo)會(huì)存在目標(biāo)形狀不變,、變小、變大的情況,。目標(biāo)的大小改變以后,，核窗口固定的Mean Shift搜索會(huì)影響到目標(biāo)跟蹤的準(zhǔn)確度,，甚至是跟丟目標(biāo),。

    分析遠(yuǎn)離和靠近攝像頭的情況如圖1所示。圖1(a)是在目標(biāo)遠(yuǎn)離第1幀的跟蹤情況,，由于采用的核窗口大小與跟蹤的目標(biāo)大小基本吻合,，所以定位跟蹤效果準(zhǔn)確。圖1(b)是目標(biāo)遠(yuǎn)離第300幀的跟蹤情況,，Mean Shift核搜索窗口大小沒(méi)變,，而跟蹤的目標(biāo)因遠(yuǎn)離或其他原因逐漸變小,，當(dāng)附近存在特征類似的物體噪聲時(shí)，定位中心不準(zhǔn)確,，還能勉強(qiáng)跟蹤到目標(biāo),。可是當(dāng)目標(biāo)變得更小,，而類似干擾物體卻更加明顯,，這時(shí)的跟蹤效果如圖1(c)目標(biāo)遠(yuǎn)離800幀所示，完全跟丟目標(biāo),。這樣的情況很有可能存在,，比如在高速公路上，跟蹤的目標(biāo)車輛遠(yuǎn)離攝像機(jī),，類似干擾車輛迎面開(kāi)來(lái)的情況?，F(xiàn)又假設(shè)跟蹤的目標(biāo)是迎面靠近攝像機(jī)的情況，就會(huì)發(fā)生圖1(d)～(f)的情況,，為了能夠分辨出搜索框,，圖1(f)的搜索框調(diào)成了黑色。目標(biāo)越來(lái)越大會(huì)導(dǎo)致Mean Shift在搜索匹配時(shí)有很大的隨機(jī)性,，并且不能真實(shí)反映出完整的目標(biāo)特征,。可見(jiàn),，搜索的核窗口在Mean Shift算法中的重要性,。所以尋求一種能自動(dòng)調(diào)節(jié)核窗口大小的Mean Shift搜索算法是本節(jié)研究的重要內(nèi)容。

2.2 以目標(biāo)形心為中心的最小外“接”圓

    目標(biāo)的最小外“接”圓的半徑可認(rèn)為是Mean Shift搜索算法的核半徑,，這里的外“接”圓的含義是指：無(wú)論目標(biāo)是什么形狀,，都可以用一個(gè)最小的圓把它“圈”起來(lái)，如圖2所示,。

    但是以形心為圓點(diǎn)中心的外“接”圓才是Mean Shift搜索算法的最佳核半徑，如圖3所示,。

    當(dāng)運(yùn)動(dòng)的目標(biāo)在Mean Shift算法的搜索窗口中心時(shí),，搜索的視覺(jué)效果與準(zhǔn)確度是最佳的，且在保證目標(biāo)特征都在搜索窗口內(nèi)的情況下要使搜索半徑越小越好,，以減少外界的影響,。由數(shù)學(xué)知識(shí)可知，在相同大小的鈍角三角形中,，圖3(a)的外接圓的半徑要比圖3(b)以形心為中心的外“接”圓半徑大,，所以圖3(b)的半徑才是最佳的Mean Shift算法的搜索半徑。

2.3 基于目標(biāo)邊緣特性的形心求解

    由上一小節(jié)得知，Mean Shift算法的最佳搜索半徑應(yīng)是以形心為中心的外“接”圓半徑,，那么本章算法在求此半徑之前需先求出運(yùn)動(dòng)目標(biāo)的形心位置,。

    面的形心為截面圖形的幾何中心，這里的面不一定是完整的面,，空心的面,、甚至是出現(xiàn)缺口的面都能準(zhǔn)確求解出其形心，如圖4所示,。

    所以不需要得到完整的目標(biāo)形狀就可以求出形心,，由于邊緣的特殊性，算法選擇檢測(cè)出運(yùn)動(dòng)目標(biāo)的邊緣,，得到大致的輪廓,，獲取出邊緣特性的二值圖像，然后進(jìn)行形心的求解,。

    為了簡(jiǎn)單方便,，算法不再求取整個(gè)圖像幀的二值圖像，而只需要在僅包含運(yùn)動(dòng)目標(biāo)區(qū)域及其領(lǐng)域內(nèi)邊緣檢測(cè)得到二值圖像,。由于目標(biāo)可能與相似移動(dòng)的物體接壤,，所以這里要通過(guò)連通域分析及形態(tài)學(xué)處理后才能得到目標(biāo)較準(zhǔn)確的二值圖像。 

    令(x₀,，y₀)為目標(biāo)模板在前一幀的真實(shí)中心位置,，設(shè){f(x，y)|x²+y²≤(1+10%)h}為以當(dāng)前幀位置(x₀,，y₀)為中心,、(1+10%)h為半徑區(qū)域內(nèi)的二值圖像集合，h為Mean Shift初次搜索的核窗口大小,，該大小范圍包含了前一幀運(yùn)動(dòng)目標(biāo)模板的所有特征,。算法把范圍擴(kuò)大是為了解決運(yùn)動(dòng)目標(biāo)變大的情況。由于相鄰兩幀之間間隔很小,，目標(biāo)區(qū)域不會(huì)發(fā)生很大的跳躍性變化,，所以擴(kuò)大綽綽有余，由于：

2.4 自適應(yīng)核窗口半徑

    求出視頻圖像當(dāng)前幀中運(yùn)動(dòng)目標(biāo)的形心坐標(biāo)以后,，本文算法用一個(gè)包含目標(biāo)所有輪廓的圓去一步一步地夾逼目標(biāo)二值圖像,，從而得到以形心為中心的最小外“接”圓，進(jìn)而得出其半徑,，這個(gè)半徑就是更新后的Mean Shift搜索算法的核窗口半徑,，如圖5所示。

    圖5中初始大小的圓半徑為(1+10%)h,，二值圖像中,，易知在圓上的所有像素值為0，減小圓半徑,，當(dāng)圓上的像素值首次大于0時(shí),，認(rèn)定此時(shí)的圓為所求“夾”住目標(biāo)的圓，此時(shí)的半徑為所需要求出的半徑,，即為Mean Shift搜索算法的新核窗半徑,。

    令以形心(x_poid，y_poid)為中心的初始圓半徑為h₀=(1+10%)h,，h為Mean Shift初始搜索核半徑,，則該圓可表示為：

    設(shè)在圓上所有像素點(diǎn)的像素值為f(x，y),，那么求取新核窗半徑的算法步驟為：

    (1)設(shè)初始圓半徑為h₀=(1+10%)h,，h為Mean Shift初始搜索核半徑；

    (2)圓{(x-x_poid)²+(y-y_poid)²=[(1-j%)h₀]²|j=0,，…,，n}上的所有像素點(diǎn)為(x，y),，其中j為小于100的循環(huán)次數(shù),，這些像素點(diǎn)對(duì)應(yīng)二值圖像上的像素值為f(x，y),；

    (3)如果滿足f(x,，y)>0條件，則循環(huán)結(jié)束,，此時(shí)得到新核窗半徑為h_auto=(1-j%)h0,，即h_auto=(1-j%)(1+10%)h，否則返回第(2)步繼續(xù)循環(huán),。

    利用Mean Shift算法在當(dāng)前幀進(jìn)行搜索前,，先通過(guò)以上步驟，根據(jù)當(dāng)前幀目標(biāo)邊緣特性的二值圖像,，求得實(shí)時(shí)更新的搜索半徑,，再進(jìn)行后面的搜索步驟，從而達(dá)到了Mean Shift可自動(dòng)調(diào)節(jié)核窗大小的目的,。

3 實(shí)驗(yàn)結(jié)果對(duì)比分析

    本實(shí)驗(yàn)在OpenCV3.0+VC++6.0+MATLAB平臺(tái)上完成,，實(shí)驗(yàn)主要驗(yàn)證文中所提出的Mean Shift核窗自動(dòng)調(diào)節(jié)的跟蹤算法的優(yōu)點(diǎn)及跟蹤效果。選取一段在廣西大學(xué)大禮堂外的道路與同學(xué)合作拍攝的運(yùn)動(dòng)目標(biāo)逐漸靠近攝像機(jī)的視頻圖像,，當(dāng)時(shí)多云天氣,，光線較好。視頻中把測(cè)試者與電動(dòng)車看成一個(gè)待跟蹤的運(yùn)動(dòng)目標(biāo),，測(cè)驗(yàn)者駕駛電動(dòng)車,，從遠(yuǎn)處逐步的向鏡頭開(kāi)來(lái)，測(cè)試者與電動(dòng)車這個(gè)目標(biāo)逐漸的變大，甚至還從正面轉(zhuǎn)到了側(cè)面,，最后從鏡頭的后邊開(kāi)出,。實(shí)驗(yàn)結(jié)果如圖6所示。

    圖6(a)中圓圈表示固定核窗的Mean Shift算法跟蹤效果,，圖6(b)中圓圈表示本文改進(jìn)的可自動(dòng)調(diào)節(jié)核窗大小的Mean Shift跟蹤效果,。對(duì)比可以看出，由于目標(biāo)的迎面靠近會(huì)逐漸變大,，固定跟蹤的核窗口根本無(wú)法確定出目標(biāo)的正確中心位置,，并且不能包含全部的目標(biāo)特征，會(huì)逐步遺失運(yùn)動(dòng)目標(biāo)的特征,；根據(jù)目標(biāo)的變化情況而自動(dòng)調(diào)節(jié)搜索核窗大小的新跟蹤算法能夠包含全部的目標(biāo)特征,，且能準(zhǔn)確定位目標(biāo)位置，對(duì)目標(biāo)實(shí)施有效跟蹤,。

    為了使結(jié)果更具說(shuō)服力,，本文對(duì)圖6中最后一幅圖的跟蹤效果進(jìn)行詳細(xì)分析，利用運(yùn)動(dòng)目標(biāo)的二值圖像來(lái)分析Mean Shift搜索核窗口所能夠包含的真實(shí)運(yùn)動(dòng)目標(biāo)的點(diǎn),，如圖7所示,。

    根據(jù)圖7二值圖像的特征點(diǎn)數(shù)，分析原始Mean Shift固定核窗口跟蹤算法與文中新提出的基于邊緣自適應(yīng)的Mean Shift目標(biāo)跟蹤方法的搜索錯(cuò)誤率σ,、搜索準(zhǔn)確率η以及目標(biāo)信息完整度δ,。搜索錯(cuò)誤率表示在Mean Shift搜索過(guò)程中，搜索到的背景特征點(diǎn)與搜索總特征點(diǎn)的比率,；搜索準(zhǔn)確率表示在Mean Shift搜索過(guò)程中,，搜索到的目標(biāo)特征點(diǎn)與搜索總特征點(diǎn)的比率；搜索目標(biāo)信息完整度表示搜索到的目標(biāo)特征點(diǎn)與目標(biāo)總特征點(diǎn)數(shù)的比率,。搜索準(zhǔn)確率和搜索目標(biāo)信息完整度共同來(lái)表征對(duì)目標(biāo)的跟蹤準(zhǔn)確度,，對(duì)目標(biāo)信息包含越完整跟蹤的目標(biāo)越準(zhǔn)確，搜索的準(zhǔn)確率越高,，對(duì)目標(biāo)特征的跟蹤越高,。

    經(jīng)過(guò)處理后圖像的分辨率是800×600，480 000個(gè)像素點(diǎn),。二值圖像特征點(diǎn)中,，令目標(biāo)總特征點(diǎn)為M個(gè)，Mean Shift搜索窗口所包含像素點(diǎn)為N個(gè)(其中目標(biāo)特征像素點(diǎn)有N₁個(gè),，背景特征像素點(diǎn)有N₂個(gè)),。則搜索錯(cuò)誤率σ為：

    把實(shí)驗(yàn)的數(shù)據(jù)統(tǒng)計(jì)在表1中，對(duì)其數(shù)據(jù)分析可以得出：

    (1)原有的Mean Shift固定搜索窗口算法搜索到的特征錯(cuò)誤率有20.079%,，而文中新提出的方法,，即可自動(dòng)調(diào)節(jié)的搜索核窗口雖然包含的背景錯(cuò)誤特征點(diǎn)數(shù)略多于Mean Shift固定核窗算法,，但其包含了大量的運(yùn)動(dòng)目標(biāo)特征，特征錯(cuò)誤率只有5.718%,，從而使搜索準(zhǔn)確率達(dá)到了94.282%,；

    (2)Mean Shift算法固定搜索窗僅包含了22.494%的運(yùn)動(dòng)目標(biāo)特征信息點(diǎn)，而文中算法高達(dá)97.714%的目標(biāo)信息,，進(jìn)而使跟蹤目標(biāo)的準(zhǔn)確度大大提高,。

4 結(jié)束語(yǔ)

    文中提出了一種基于邊緣自適應(yīng)的Mean Shift目標(biāo)跟蹤方法,，其思想是使Mean Shift搜索核窗口大小能夠根據(jù)目標(biāo)的形狀變化而自動(dòng)調(diào)節(jié),，利用目標(biāo)二值圖像邊緣信息，找出其形心,，通過(guò)逐步縮小的圓去夾逼目標(biāo),，進(jìn)而找出最適合的Mean Shift搜索核窗口。實(shí)驗(yàn)結(jié)果表明,，該方法能夠使Mean Shift搜索核窗口包含大量而完整的運(yùn)動(dòng)目標(biāo)特征信息,，降低搜索的錯(cuò)誤率，提高搜索準(zhǔn)確率,，從而精確地跟蹤運(yùn)動(dòng)目標(biāo),。此方法雖然能夠非常精確地跟蹤運(yùn)動(dòng)目標(biāo)，但當(dāng)有其他類似運(yùn)動(dòng)物體與運(yùn)動(dòng)目標(biāo)接壤時(shí),，求解目標(biāo)領(lǐng)域內(nèi)的二值圖像就變得困難,，從而會(huì)影響形心以及搜索核窗大小，這是今后要研究解決的問(wèn)題,。

參考文獻(xiàn)

[1] 周芳芳,，樊曉平，葉榛.均值飄逸算法的研究與應(yīng)用[J].控制與決策,，2007,，22(8)：841-847.

[2] FUKUNAGA K，HOSTETLER L.The estimation of the gradient of a density function with applications in Pattern Recognition[J].IEEE Transactions on Information Theory,，1975,，21(1)：32-40.

[3] CHENG Y Z.Mean Shift, mode seeking, and clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1995,，17(8)：790-799.

[4] 田綱.基于多特征融合的Mean Shift目標(biāo)跟蹤計(jì)算研究[D].武漢：武漢大學(xué),，2011.

[5] COLLLINS R T.Mean-shift blob tracking through scale space[C].In：Proc.Of the IEEE Conf. on Computer Vision and Pattern Recognition(CVPR’03)，2003：234-240.

[6] COMANICIU D,，RAMESH V,，MEER P.Kernel-Based object tracking[J].IEEE Trans.On Pattern Analysis and Machine Intelligence，2003,，25(5)：564-575.

[7] 宣國(guó)榮,，柴佩琪.基于巴氏距離的特征選擇[J].模式識(shí)別與人工智能,，1996，9（4）：324-329.

[8] 彭寧嵩,，楊杰,，劉志，等.Mean Shift跟蹤算法中核函數(shù)窗寬的自動(dòng)選取[J].軟件學(xué)報(bào),，2005,，16(9）：1542-1550.

[9] 覃劍.視頻序列中的運(yùn)動(dòng)目標(biāo)檢測(cè)與跟蹤研究[D].重慶：重慶大學(xué)，2008.

[10] 李劍峰,，黃增喜,，劉怡光.基于光流場(chǎng)估計(jì)的自適應(yīng)Mean-Shift目標(biāo)跟蹤算法[J].光電子激光，2013,，23（10）：1996-2002.

[11] 楊志菊,，劉寶華.基于Mean Shift的變尺寸快速運(yùn)動(dòng)目標(biāo)自適應(yīng)跟蹤算法[J].太赫茲科學(xué)與電子信息學(xué)報(bào)，2015,，13(2)：240-244.

[12] 劉苗,，黃朝兵.基于多特征自適應(yīng)融合的Mean Shift目標(biāo)跟蹤方法[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2016(4)：68-72.

作者信息:

周  楊,，胡桂明,，黃東芳

(廣西大學(xué) 電氣工程學(xué)院，廣西 南寧530004)