0 引言

    在計算機視覺領域中的一個重要研究方向是對運動目標的跟蹤，而應用在運動目標跟蹤方向的一種常用方法是Mean Shift算法，它是指通過均值漂逸^[1]的方法，從目標前一幀的真實位置逐步迭代至當前幀目標位置的過程。FUKUNAGA K等^[2]人在1975年最早提出了該算法，并由CHENG Y Z^[3]在1995年加入核函數后改進推廣，之后被運用到運動目標的跟蹤領域。

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

1 Mean Shift跟蹤技術

    Mean Shift算法運用在運動目標跟蹤時，首先根據目標特征的概率直方圖建立初始模板，一般選取目標的顏色特征，為了使跟蹤效果更好，也會選擇多種特征的結合；然后在當前幀中選擇以前一幀的目標真實位置點為中心，以固定設置的Mean Shift搜索半徑為半徑的區域建立候選目標模板；再對兩模板進行相似性度量。如果沒滿足預設要求，則以搜索到的新位置為起點繼續搜索下一位置，直到滿足預設的條件為止。

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

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

2 Mean Shift核窗口自適應方法

    Mean Shift算法在運動目標跟蹤領域得到了廣泛的應用，但其固定的核窗口會導致跟蹤準確度降低，甚至會導致跟蹤失敗。文中就這個問題提出了一種基于邊緣特性的Mean Shift搜索核半徑自適應目標的跟蹤方法。

2.1 固定核窗口跟蹤問題 

    視頻畫面中物體的運動方式各種各樣，有的保持與攝像機的距離做各種速度的運動；有的可能遠離攝像機運動；有的靠近攝像機運動。這3種情況下，目標會存在目標形狀不變、變小、變大的情況。目標的大小改變以后，核窗口固定的Mean Shift搜索會影響到目標跟蹤的準確度，甚至是跟丟目標。

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

2.2 以目標形心為中心的最小外“接”圓

    目標的最小外“接”圓的半徑可認為是Mean Shift搜索算法的核半徑，這里的外“接”圓的含義是指：無論目標是什么形狀，都可以用一個最小的圓把它“圈”起來，如圖2所示。

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

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

2.3 基于目標邊緣特性的形心求解

    由上一小節得知，Mean Shift算法的最佳搜索半徑應是以形心為中心的外“接”圓半徑，那么本章算法在求此半徑之前需先求出運動目標的形心位置。

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

    所以不需要得到完整的目標形狀就可以求出形心，由于邊緣的特殊性，算法選擇檢測出運動目標的邊緣，得到大致的輪廓，獲取出邊緣特性的二值圖像，然后進行形心的求解。

    為了簡單方便，算法不再求取整個圖像幀的二值圖像，而只需要在僅包含運動目標區域及其領域內邊緣檢測得到二值圖像。由于目標可能與相似移動的物體接壤，所以這里要通過連通域分析及形態學處理后才能得到目標較準確的二值圖像。 

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

2.4 自適應核窗口半徑

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

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

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

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

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

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

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

    利用Mean Shift算法在當前幀進行搜索前，先通過以上步驟，根據當前幀目標邊緣特性的二值圖像，求得實時更新的搜索半徑，再進行后面的搜索步驟，從而達到了Mean Shift可自動調節核窗大小的目的。

3 實驗結果對比分析

    本實驗在OpenCV3.0+VC++6.0+MATLAB平臺上完成，實驗主要驗證文中所提出的Mean Shift核窗自動調節的跟蹤算法的優點及跟蹤效果。選取一段在廣西大學大禮堂外的道路與同學合作拍攝的運動目標逐漸靠近攝像機的視頻圖像，當時多云天氣，光線較好。視頻中把測試者與電動車看成一個待跟蹤的運動目標，測驗者駕駛電動車，從遠處逐步的向鏡頭開來，測試者與電動車這個目標逐漸的變大，甚至還從正面轉到了側面，最后從鏡頭的后邊開出。實驗結果如圖6所示。

    圖6(a)中圓圈表示固定核窗的Mean Shift算法跟蹤效果，圖6(b)中圓圈表示本文改進的可自動調節核窗大小的Mean Shift跟蹤效果。對比可以看出，由于目標的迎面靠近會逐漸變大，固定跟蹤的核窗口根本無法確定出目標的正確中心位置，并且不能包含全部的目標特征，會逐步遺失運動目標的特征；根據目標的變化情況而自動調節搜索核窗大小的新跟蹤算法能夠包含全部的目標特征，且能準確定位目標位置，對目標實施有效跟蹤。

    為了使結果更具說服力，本文對圖6中最后一幅圖的跟蹤效果進行詳細分析，利用運動目標的二值圖像來分析Mean Shift搜索核窗口所能夠包含的真實運動目標的點，如圖7所示。

    根據圖7二值圖像的特征點數，分析原始Mean Shift固定核窗口跟蹤算法與文中新提出的基于邊緣自適應的Mean Shift目標跟蹤方法的搜索錯誤率σ、搜索準確率η以及目標信息完整度δ。搜索錯誤率表示在Mean Shift搜索過程中，搜索到的背景特征點與搜索總特征點的比率；搜索準確率表示在Mean Shift搜索過程中，搜索到的目標特征點與搜索總特征點的比率；搜索目標信息完整度表示搜索到的目標特征點與目標總特征點數的比率。搜索準確率和搜索目標信息完整度共同來表征對目標的跟蹤準確度，對目標信息包含越完整跟蹤的目標越準確，搜索的準確率越高，對目標特征的跟蹤越高。

    經過處理后圖像的分辨率是800×600，480 000個像素點。二值圖像特征點中，令目標總特征點為M個，Mean Shift搜索窗口所包含像素點為N個(其中目標特征像素點有N₁個，背景特征像素點有N₂個)。則搜索錯誤率σ為：

    把實驗的數據統計在表1中，對其數據分析可以得出：

    (1)原有的Mean Shift固定搜索窗口算法搜索到的特征錯誤率有20.079%，而文中新提出的方法，即可自動調節的搜索核窗口雖然包含的背景錯誤特征點數略多于Mean Shift固定核窗算法，但其包含了大量的運動目標特征，特征錯誤率只有5.718%，從而使搜索準確率達到了94.282%；

    (2)Mean Shift算法固定搜索窗僅包含了22.494%的運動目標特征信息點，而文中算法高達97.714%的目標信息，進而使跟蹤目標的準確度大大提高。

4 結束語

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

參考文獻

[1] 周芳芳，樊曉平，葉榛.均值飄逸算法的研究與應用[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目標跟蹤計算研究[D].武漢：武漢大學，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] 宣國榮，柴佩琪.基于巴氏距離的特征選擇[J].模式識別與人工智能，1996，9（4）：324-329.

[8] 彭寧嵩，楊杰，劉志，等.Mean Shift跟蹤算法中核函數窗寬的自動選取[J].軟件學報，2005，16(9）：1542-1550.

[9] 覃劍.視頻序列中的運動目標檢測與跟蹤研究[D].重慶：重慶大學，2008.

[10] 李劍峰，黃增喜，劉怡光.基于光流場估計的自適應Mean-Shift目標跟蹤算法[J].光電子激光，2013，23（10）：1996-2002.

[11] 楊志菊，劉寶華.基于Mean Shift的變尺寸快速運動目標自適應跟蹤算法[J].太赫茲科學與電子信息學報，2015，13(2)：240-244.

[12] 劉苗，黃朝兵.基于多特征自適應融合的Mean Shift目標跟蹤方法[J].現代計算機（專業版），2016(4)：68-72.

作者信息:

周  楊，胡桂明，黃東芳

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