基于多核融合的目標大面積遮擋處理方法

肖 鵬 段洣毅

(北京航空航天大學 計算機學院，北京 100191)

趙 琪

(北京圖形研究所，北京 100029)

基于多核融合的目標大面積遮擋處理方法

肖 鵬 段洣毅

(北京航空航天大學 計算機學院，北京 100191)

趙 琪

(北京圖形研究所，北京 100029)

提出了一種基于多核融合的目標遮擋處理方法，用于提高大面積遮擋情況下視覺目標跟蹤算法的魯棒性和準確性.與現(xiàn)有基于單個對稱核加權(quán)直方圖的mean shift跟蹤算法不同，該方法以目標區(qū)域內(nèi)的多個非中心位置為核函數(shù)中心，構(gòu)建多個非對稱核加權(quán)直方圖.由于這些直方圖對目標的不同區(qū)域賦予了不同的權(quán)重，使得在遮擋發(fā)生時總存在一些直方圖受影響較小.依據(jù)各個直方圖分別進行mean shift迭代獲得一組目標位置估計后，利用DS證據(jù)理論融合判定最終的目標位置.實驗結(jié)果表明，該方法在目標被大面積遮擋時仍能夠獲得準確的跟蹤.

目標跟蹤;視覺跟蹤;均值漂移;遮擋處理;多核;證據(jù)理論

視覺目標跟蹤一直是計算機視覺領(lǐng)域的研究熱點，在智能監(jiān)控、輔助駕駛、引導打擊等諸多領(lǐng)域都有廣泛的應用.由于目標本身及周邊環(huán)境復雜多變，提高視覺目標跟蹤的魯棒性依然是一個極具挑戰(zhàn)性的課題.本文主要研究目標被遮擋情形下，尤其是大面積遮擋情形下的跟蹤魯棒性問題.核跟蹤算法，又稱mean shift跟蹤算法，由Comaniciu［1］等人提出.該算法基于 Fukunaga［2］等人提出的非參概率密度估計算法，利用核函數(shù)加權(quán)直方圖描述目標模型和候選目標，將目標定位問題轉(zhuǎn)換為沿梯度方向求局部極值問題.該算法簡潔實用，實時性好，近年來被廣泛地研究、應用和改進.由于核函數(shù)的剖面函數(shù)具有單調(diào)遞減的特性，核函數(shù)加權(quán)直方圖中目標邊沿點對直方圖的貢獻較小，目標邊沿的小部分遮擋對直方圖影響不大，因此核跟蹤算法對部分遮擋具有一定的魯棒性.但是，遮擋發(fā)生時核跟蹤算法輸出的目標位置將被“擠”向目標未被遮擋的部分，跟蹤準確度有所下降，而且，如果遮擋面積過大，特別是被遮擋位置接近目標中心時，直方圖將發(fā)生顯著改變，跟蹤往往會失敗.

為此，研究者提出了多種針對遮擋問題的改進方法.這些方法大致可分為2類:基于預測的方法和基于分塊的方法.基于預測的方法［3－5］引入Kalman濾波器等工具，通過目標的運動軌跡預測目標在下一幀中的可能位置，此方法可以在一定程度上防止遮擋情形下視覺特征突變引起的跟蹤窗口飄離目標，但該類方法并沒有改善視覺特征的匹配程度.基于分塊的方法［5－7］將目標劃分為若干子塊，以各子塊的相似度加權(quán)求和得到總的相似度函數(shù);此類方法實際上是在一定程度上引入了目標的形狀信息，可以降低部分遮擋對目標相似度判定的影響，但是當被遮擋面積過大時依然難以保證效果;而且，由于目標被劃分為若干個相似的子塊，跟蹤過程中可能發(fā)生子塊之間交叉錯誤關(guān)聯(lián)，降低算法可靠性.

本文提出了一種基于多核融合的跟蹤方法以解決目標大面積遮擋問題，該方法改變了以目標中心點為核函數(shù)中心的常規(guī)方法，而是以目標區(qū)域內(nèi)的多個非中心位置為核函數(shù)中心，構(gòu)建多個非對稱核函數(shù)，分別進行mean shift跟蹤，并利用D-S證據(jù)理論融合判定目標位置.實驗結(jié)果證明該方法在目標大面積遮擋情形下仍然具有較強的魯棒性.

1 基于多核融合的跟蹤算法框架

本文提出的基于多核融合的跟蹤方法如圖1所示.首先，以目標區(qū)域內(nèi)的多個不同點為中心，構(gòu)造多個核函數(shù)，計算獲得目標模型和候選區(qū)域的一組核函數(shù)加權(quán)直方圖;然后，將每組對應的直方圖組合用mean shift算法進行目標定位，得到一組目標位置估計及相應的相似度，再利用D-S證據(jù)理論構(gòu)造mass函數(shù)，對目標位置進行融合判定，給出最終的跟蹤結(jié)果.

圖1 算法流程圖

該算法與經(jīng)典的mean shift算法［1］的主要區(qū)別在于:①采用了多個而不是單個核函數(shù).各個核函數(shù)以目標區(qū)域內(nèi)的不同位置為中心，也就是說，目標中的各個像素在不同的直方圖中的權(quán)重是不同的，當目標被部分遮擋時，總有某個或某些直方圖受到的影響較小.②對多個跟蹤結(jié)果進行了融合判定.正因為有了多個核函數(shù)，當目標被部分遮擋時，各組mean shift算法給出的目標位置必然會有較大差異，簡單的平均顯然得不到準確的結(jié)果，必須采用更具合理性的融合判定方法.

2 基于非對稱核函數(shù)的跟蹤方法

2.1 核跟蹤簡介

在核跟蹤中，首先要提取圖像的某種特征，將目標模型和候選區(qū)域以核函數(shù)加權(quán)直方圖的形式表示.設(shè)目標包含 n 個像素{xi}i=1，2，…，n，區(qū)域中心為x0，特征值量化為m個等級，則目標模型可表示為

其中，k(x)為核函數(shù)對應的剖面函數(shù)，它是一個單調(diào)遞減函數(shù)，使得目標中心的像素對直方圖的貢獻比邊沿像素大;h為核函數(shù)的帶寬，即目標尺度;δ為delta函數(shù)，用于判斷像素xi的特征值是否屬于第u個bin;C為歸一化系數(shù):

同樣，包含 nh個像素{xi}i=1，2，…，nk的候選區(qū)域也表示為類似的形式:

目標模型和候選區(qū)域間的相似度定義為這2個直方圖的Bhattacharyya系數(shù):

跟蹤的目的就是在每幀中尋找使式(3)最大的候選區(qū)域位置.在目標的初始位置，利用Taylor展開，式(3)可以近似為

其中

式(4)中只有第2項與y有關(guān)，最大化式(4)可以通過最大化其第2項來實現(xiàn)，利用mean shift算法，以初始位置為起始的位移矢量可計算為

其中，g(r)=－k'(r).由于Epanechnikov核函數(shù)的剖面函數(shù)的導數(shù)為常數(shù)，故經(jīng)常選用它作為核函數(shù)，式(6)可簡化為

利用式(7)進行若干次迭代即可定位目標位置.

2.2 針對非對稱核函數(shù)的跟蹤算法修正

由于核函數(shù)的剖面函數(shù)具有單調(diào)遞減的性質(zhì)，核函數(shù)加權(quán)直方圖中，目標邊沿區(qū)域?qū)χ狈綀D的貢獻較小，邊沿小部分的遮擋對直方圖影響不大，因此核跟蹤算法對部分遮擋具有一定的魯棒性.但是，如果遮擋面積過大，特別是被遮擋位置接近目標中心時，直方圖將發(fā)生顯著改變.

如果能夠?qū)⒑撕瘮?shù)中心偏移到目標區(qū)域的某一側(cè)，則相對側(cè)的函數(shù)值將會較低，發(fā)生在相對側(cè)的遮擋對直方圖的影響將會較小.圖2所示為以灰度等級形式表示的2個核函數(shù)，圖2a中核函數(shù)中心位于目標中心，圖2b中核函數(shù)中心偏左上角，右下角的遮擋對直方圖的影響將較小.

圖2 不同中心位置的核函數(shù)

以圖3所示圖像為例，圖3a為初始選定的目標，圖3b為后續(xù)幀中被部分遮擋的目標，表1所示采用不同的核函數(shù)中心時，這2幅圖像以直方圖Bhattacharyya系數(shù)表征的相似性測度.

圖3 原始目標及被遮擋的目標

表1 核函數(shù)中心對直方圖Bhattacharyya系數(shù)的影響

可見，當目標下半部分被遮擋時，傳統(tǒng)的以目標中心為核函數(shù)中心的直方圖受影響較大，相似性測度降至0.6左右，而以左上角和右上角為核函數(shù)中心的直方圖受影響較小，相似性測度依然保持0.9以上.

但是，當核函數(shù)中心與目標中心不重疊時，目標區(qū)域內(nèi)的樣本點分布將不對稱，必須對mean shift算法進行修正.

Comaniciu［8］證明了 mean shift 算法的收斂性，即在迭代過程中，有

另一方面，隨著候選區(qū)域與目標模型相似度的遞增，wi將趨近于1，根據(jù)式(7)，將有

則有

由式(7)和式(9)得

因此，在樣本點不關(guān)于核函數(shù)中心對稱時，只要將迭代公式修正為如下形式，也可以滿足mean shift算法的收斂性.

3 基于證據(jù)理論目標位置融合判定

通過定義一組中心位置各不相同的核函數(shù)加權(quán)直方圖，即可使得目標被部分遮擋時，總有某個或某些直方圖受影響較小，可以相對準確的跟蹤目標位置.接下來要解決的問題是如何對一組跟蹤結(jié)果進行融合判定，從中選出最優(yōu)的目標位置估計.

直觀的想法，可以將目標模型與候選區(qū)域的相似度作為判別準則，采信相似度最高的跟蹤結(jié)果.但是，實驗證明這種方法往往并不能獲得準確的結(jié)果.為此，本文利用基于D-S證據(jù)理論的融合判定方法.

D-S 證據(jù)理論是由 Dempster［9］和 Shafer［10］建立的一套數(shù)學理論，是對概率論的進一步擴充，是一種被廣泛應用的決策級信息融合工具.D-S證據(jù)理論的特點是不僅可以對假設(shè)進行概率賦值，還可以對假設(shè)的集合進行概率賦值，通過合理設(shè)置焦元結(jié)構(gòu)，可以使分辨能力強的證據(jù)在組合過程中得到更大程度的采信.

假設(shè)在跟蹤中采用了N個核函數(shù){k1，k2，…，kN}，分別利用mean shift算法，得到N個目標位置估計{l1，l2，…，lN}.建立相似度矩陣 ρ，其中 ρij表示在候選位置lj，用核函數(shù)ki加權(quán)的候選區(qū)域直方圖與目標模型直方圖的相似度.

對某個核函數(shù)ki，按照相似度ρij遞減的順序?qū)⑾嗨贫刃蛄信帕袨閧ρ(1)，ρ(2)，…，ρ(N)}，對應的目標位置序列為{l(1)，l(2)，…，l(N)}，按如下焦元結(jié)構(gòu)定義一組N個mass函數(shù):

對全部N個核函數(shù)，可得到N×N個mass函數(shù).

在上述嵌套式的焦元結(jié)構(gòu)下，分類能力強(相似度值差異大)的特征將賦予單個元素或小集合較多的概率分配，而分類能力弱(相似度值差異小)的特征將賦予大集合較多的概率分配，也就是說，特征的分類能力在概率分配上得以體現(xiàn).

目標位于位置ln的概率利用D-S合成公式獲得［11］:

其中

概率賦值最大的目標位置即作為融合后的目標位置.

4 算法實現(xiàn)與實驗結(jié)果

4.1 遮擋檢測

顯然，采用多個核函數(shù)分別進行迭代將增加計算復雜度，為此，本文設(shè)計了一種遮擋檢測算法，只有在檢測到遮擋發(fā)生時才啟用多核融合跟蹤，否則采用傳統(tǒng)的單核跟蹤方法.遮擋檢測的方法如下:

定義 R=B(pak，qak)/B(pk，qk).其中 B(x，y)表示 Bhattacharyya系數(shù);pk，qk分別表示目標模型和候選區(qū)域以常規(guī)核函數(shù)K(x)加權(quán)直方圖，即目標中心部分權(quán)值較高，邊沿部分權(quán)值較低;pak，qak分別表示目標模型和候選區(qū)域以1－K(x)加權(quán)的直方圖，即目標中心部分權(quán)值較低，邊沿部分權(quán)值較高.在正常情況下，R值應接近于1，但當目標被遮擋時，其可視面積將急劇減小，無法充滿跟蹤窗口，如圖4所示.

圖4 目標被遮擋時的跟蹤窗口

此時跟蹤窗口內(nèi)包含大量的背景區(qū)域，R值將顯著偏離于1，因此可以將|R－1|＞T作為判斷遮擋的依據(jù)，其中T為預設(shè)的閾值，T值過小將增加誤檢率，T值過大將增加漏檢率，由于漏檢對跟蹤準確性的影響較大，故T值設(shè)定時應以降低漏檢為主要考慮因素，實驗中取T=0.15.由于目標尺度變化等其它因素也可能導致R值改變，但尺度變化過程一般比較緩慢，而遮擋對目標可視面積的改變則非常迅速.因此，以當前幀跟蹤窗口R值相對之前若干幀發(fā)生突變作為附加條件，以降低誤檢率.

4.2 跟蹤算法實現(xiàn)

本文提出的跟蹤算法與具體的視覺特征無關(guān)，為了方便算法實現(xiàn)和比較，采用RGB顏色直方圖作為視覺特征.本文提出的以證據(jù)理論作為判別準則的多核融合跟蹤算法稱為MKDS(object tracking based on Multiple Kernel fusion by D-Sevidence theory);以相似度最高作為判別準則的多核融合跟蹤方法稱為MKLM(object tracking based on Multiple Kernel fusion by Likelihood Maximization);經(jīng)典的單核mean shift跟蹤算法稱為SK(object tracking based on Single Kernel).

實驗環(huán)境為:筆記本電腦 Thinkpad T400;CPU:Intel Core2 2.5 GHz;內(nèi)存3 GB;操作系統(tǒng):Windows 7 Professional;軟件環(huán)境:Matlab 2009.目標初始位置以手工方式輸入，跟蹤結(jié)果在視頻畫面上以矩形框顯示.

核函數(shù)選用Epanechnikov核，RGB每個顏色通道量化為8個等級，即顏色直方圖共有512維.設(shè)目標寬度為w，高度為h，以目標中心位置為坐標原點，以(0，0)，(－w/2，－h(huán)/2)，(w/2，－h(huán)/2)，(－w/2，h/2)，(w/2，h/2)5 個點為中心，構(gòu)建5個核函數(shù)，以目標區(qū)域內(nèi)各像素距核函數(shù)中心的最大距離為核函數(shù)窗寬，分別生成5個核函數(shù)加權(quán)直方圖，如圖5所示.

利用證據(jù)理論對5個跟蹤結(jié)果進行融合判定，選擇概率賦值最大的位置作為輸出.

4.3 實驗結(jié)果

圖5 核函數(shù)加權(quán)直方圖

實驗1 選擇一段遮擋程度較輕的視頻進行實驗.實驗數(shù)據(jù)為PETS2001測試集第1組中的一段(第541幀～第592幀)，視頻中行人下半身被汽車遮擋，遮擋面積約占目標總面積的一半.SK，MKLM和MKDS的跟蹤結(jié)果如圖6所示(視頻分辨率為768像素×576像素，圖中只截取了每幀畫面右下1/4部分).

圖6可見，在第563幀目標被部分遮擋時，SK算法丟失了目標，MKLM和MKDS在后續(xù)幀中都跟住了目標.同時也可以看出，相對于MKLM算法，MKDS獲得了更好的目標覆蓋.分析其原因發(fā)現(xiàn)，由于初始選定的目標框中包含了少量背景區(qū)域，加之與目標顏色相似的背景點的影響，當遮擋發(fā)生時，簡單的相似度最大原則往往不能獲得最優(yōu)的目標位置.如圖6第2列所示，由于目標框下半部分包含的背景點較多，且行人的褲子顏色與背景相似，導致在該幀的跟蹤過程中，以左下角為中心的核函數(shù)獲得了最大的相似度，故MKLM算法采信了該位置;而基于證據(jù)理論的MKDS算法綜合了相似度與分辨能力2項指標，獲得的跟蹤結(jié)果更加準確.

實驗1中發(fā)生遮擋的情況下，MKDS算法的平均處理速率為0.0440 s/幀，即每秒22.73幀.

實驗2 選擇一段遮擋較嚴重的視頻進行實驗，視頻中坦克模型被障礙物遮擋了大部分面積.視頻分辨率640像素×480像素，共126幀.SK和MKDS的跟蹤結(jié)果如圖7所示.

可以看出，隨著目標被遮擋程度不斷加劇，在第77幀時SK算法丟失了目標，而本文提出的MKDS算法始終保持正確跟蹤.

圖8所示為跟蹤過程中核函數(shù)采信情況，在初始階段，未檢測到較嚴重的遮擋，沒有觸發(fā)多核融合跟蹤算法.從第65幀開始，目標下半部分遮擋逐漸加劇，MKDS算法一直采信受遮擋影響較小的左上角和右上角核函數(shù)，直至遮擋結(jié)束，獲得了較好的跟蹤效果.

實驗2中，在發(fā)生遮擋的情況下，MKDS算法的平均處理速率為0.049 8 s/幀，即每秒20.08幀.

圖6 實驗1部分跟蹤結(jié)果

圖7 實驗2部分跟蹤結(jié)果

圖8 跟蹤過程中核函數(shù)采信情況

5 結(jié)論

針對大面積遮擋情況下的魯棒跟蹤問題，本文提出了一種多核融合的跟蹤方法.該方法構(gòu)造多個以不同位置為中心的核函數(shù)，分別進行mean shift迭代，使得在遮擋發(fā)生時，總存在某個或某些核函數(shù)加權(quán)直方圖受影響較小，在此基礎(chǔ)上，利用D-S證據(jù)理論，從中選出最“可信”的目標位置估計，給出準確的跟蹤結(jié)果.

為了進一步提高魯棒性和準確性，本文的方法可以與基于位置預測的遮擋處理方法結(jié)合使用，例如可以將Kalman濾波器預測的結(jié)果作為mean shift迭代的起始位置，或者將預測的結(jié)果也作為“證據(jù)”之一參與融合.此外，由于采用多核融合將顯著提高計算復雜度，還可以考慮利用以往若干幀中核函數(shù)的采信情況自適應地預測下一幀中可能有效的核函數(shù)，以降低計算復雜度.后續(xù)工作中將對上述思路進行進一步研究.

References)

［1］ Comaniciu D，Ramesh V，Meer P.Kernel-based object tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(5):564 －577

［2］ Fukunaga K，Hostetler L.The estimation of the gradientof a density function，with applications in pattern recognition［J］.IEEE Trans on Inform Theory，1975，21(1):32

［3］朱勝利.Mean Shift及相關(guān)算法在視頻跟蹤中的研究［D］.杭州:浙江大學電氣工程學院，2006 Zhu Shengli.A study ofmean shift and correlative algorithm in Visual Tracking［D］.Hangzhou:College of Electrical Engineering，Zhejiang University，2006(in Chinese)

［4］ Wang Jiangtao，Yang Jingyu.Object tracking based on Kalmanmean shift in occlusions［J］.Journal of System Simulation，2007(9):4216－4220

［5］劉少華，張茂軍，熊志輝，等.一種魯棒高效的視頻運動目標檢測與跟蹤算法［J］.自動化學報，2009，35(8):1055 －1062 Liu Shaohua，Zhang Maojun，Xiong Zhihui，et al.A robust and efficient video moving object detection and tracking algorithm［J］.Acta Automatica Sinica，2009，35(8):1055 － 1062(in Chinese)

［6］賈慧星，章毓晉.基于梯度方向直方圖特征的多核跟蹤［J］.自動化學報，2009，35(10):1283 －1289 Jia Huixing，Zhang Yujin.Multiple kernels based object tracking using histograms of oriented gradients［J］.Acta AutoMatica Sinica，2009，35(10):1283 －1289(in Chinese)

［7］顏佳，吳敏淵，陳淑珍，等.應用Mean Shift和分塊的抗遮擋跟蹤［J］.光學精密工程，2010，18(6):1413 －1419 Yan Jia，Wu Minyuan，Chen Shuzhen，et al.Anti-occlusion tracking algorithm based on Mean Shift and fragments［J］.Optics and Precision Engineering，2010，18(6):1413 －1419(in Chinese)

［8］ Comaniciu D，Meer P.Robustanalysis of feature space:color image segmentation［C］//Proc 1997 IEEE Conf Computer Vision and Pattern Recognition.Puerto Rico:IEEE Computer Society，1997

［9］ Dempster A P.Upper and lower probabilities induced by amultivalued mapping［J］.Annual Mathematical Statistics，1967，38(4):325－339

［10］ Shafer G.A mathematical theory of evidence［M］.Princeton，NJ:Princeton University Press，1976

［11］韓崇昭，朱洪艷，段戰(zhàn)勝.多源信息融合［M］.北京:清華大學出版社，2006:86－88 Han Chongzhao，Zhu Hongyan，Duan Zhansheng.Multi-source information fusion［M］.Beijing:Tsinghua University Press，2006:86－88(in Chinese)

(編 輯:文麗芳)

Occlusion handling approach in visual tracking based on multiple-kernel fusion

Xiao Peng Duan Miyi
(School of Computer Science and Technology，Beijing University of Aeronautics and Astronautics，Beijing100191，China)

Zhao Qi

(Beijing Institute of Graphics，Beijing 100029，China)

A novel visual tracking approach based on multiple-kernel fusion was proposed to improve robustness and accuracy of tracking under large-area occlusion.Unlike traditional single symmetric kernel weighted histogram used in mean shift tracking，this approach adopted several asymmetric kernel functions centered at different positions within target region to build a set of asymmetric kernel weighted histograms.Because these histograms weighted each part of the target region differently，there must be some less influenced histograms during occlusion.Based on each histogram，a set of target location estimations were provided respectively by mean shift iteration，and the target location was obtained by fusing these estimations using Dempster-Shafer evidence theory.The experimental results demonstrate the effectiveness of the proposed approach under large-area occlusion.

target tracking;visual tracking;mean shift;occlusion handling;multiple kernels;evidence theory

TP 391

A

1001-5965(2012)06-0829-06

2011-03-22;網(wǎng)絡出版時間:2012-06-15 15:43

www.cnki.net/kcms/detail/11.2625.V.20120615.1543.025.htm l

國家自然科學基金資助項目(61005084)

肖 鵬(1980－)，男，湖南長沙人，博士生，xiaopeng2010@gmail.com.