融合相似性檢測的抗遮擋粒子濾波跟蹤算法

鄧利平，肖 何，王 娟

西華師范大學 計算機學院，四川 南充 637002

運動目標跟蹤是計算機視覺研究的基本課題和研究熱點，應用的領域涉及智能視頻監控、無人機偵察、精準制導和交通監測等。

通常，可將目標跟蹤算法分為生成式方法和判別式方法，本文研究的粒子濾波算法屬于生成式方法[1-2]。Nummiaro等在文獻[3]中首次提出完整的粒子濾波跟蹤框架，取得了良好的跟蹤效果，后文將該算法簡稱為ACPF。針對粒子濾波跟蹤過程中的遮擋問題，文獻[4-8]通過分塊跟蹤的方法提高算法的魯棒性。文獻[4]在檢測到遮擋時對目標分塊，并選擇匹配最好的子塊進行重采樣和跟蹤。文獻[5]融合顏色和LBP（local binary pattern）紋理特征；當檢測到遮擋時，首先判斷遮擋的類型，如果是部分遮擋，對有效塊跟蹤；如果是完全遮擋，利用前期跟蹤結果結合最小二乘法估計目標位置；由于目標重新出現在場景中的位置具有很大的不確定性，估計位置容易出錯。文獻[6]將跟蹤目標分塊，并對每個塊賦予不同的權重，同時采用局部模板更新策略，提高了模板更新的準確性。文獻[7]提出了基于顏色和角點特征的分塊粒子濾波跟蹤算法，提高了算法的定位精度和魯棒性。文獻[8]融合顏色和邊緣特征建立目標的觀測模型，并將每個分塊作為圖的一個頂點，建立圖模型；跟蹤過程中，遮擋部分的狀態通過圖模型中的可見部分估計。分塊跟蹤在復雜環境下搜索效率低，處理小目標和完全遮擋情況下的跟蹤性能不理想，不適合長時跟蹤。文獻[9-10]將卷積神經網絡提取的深度特征融合到粒子濾波跟蹤算法，提高了算法在復雜環境條件下的跟蹤精度和魯棒性。文獻[11]在粒子濾波框架下使用顏色分布和KAZE特征融合來跟蹤目標，利用顏色分布和KAZE特征分別描述目標外觀和結構輪廓，提高了跟蹤算法的性能。文獻[12]結合粒子濾波和均值漂移跟蹤算法，以粒子濾波為基礎，發現遮擋時，使用均值漂移查找目標位置。文獻[13]在粒子重采樣階段引入K均值聚類算法，根據粒子的平均距離對跟蹤窗尺寸自適應修正，提升了算法對局部遮擋和目標尺度變化的魯棒性。文獻[14]利用雞群優化解決粒子貧化問題，提高粒子濾波跟蹤算法的抗遮擋性能。文獻[15]提出了一種檢測和處理遮擋的策略，當跟蹤算法檢測到遮擋時，通過SURF（speeded up robust features）特征進行恢復。但是，當跟蹤視頻分辨率較低，跟蹤目標遠小于待搜索圖像時，目標的SURF特征點少或無特征點，容易匹配失敗，且SURF算子對跟蹤目標形變敏感。文獻[16]提出了對目標及場景同時建模的T-S（target-scene）粒子濾波，需要對目標、相似干擾和場景強特征三類粒子分別描述，通過場景中輔助特征提升算法抗遮擋以及抗相似目標干擾的跟蹤性能。該算法計算量大，需要更新場景信息。文獻[17]利用目標SSD（sum of squared difference）殘差所生成的高似然區域，自適應地調整粒子集采樣范圍和數量，提高粒子狀態空間質量，解決粒子濾波算法在遮擋情況下的跟蹤問題。文獻[18]將改進的紋理LBP與顏色特征相結合，對于部分遮擋使用局部三值模式（local ternary patterns，LTP）判定最優跟蹤區域，在1.1倍判定區域內重采樣；對于完全遮擋使用狀態轉移方程直接預測目標區域，然后在2倍預測區域內重采樣。文獻[19-21]將相關濾波與粒子濾波相結合，提高相關濾波跟蹤的抗遮擋性能。文獻[22]通過粒子濾波改善均值漂移算法對遮擋和尺度變化的跟蹤性能。但是，文獻[19-22]沒有討論粒子濾波跟蹤的抗遮擋處理方法。

目前，研究人員主要通過分塊跟蹤、特征融合、引入算法和擴大采樣范圍等方法來提高粒子質量，增強粒子濾波跟蹤算法的抗遮擋性能。但是，當目標大面積被遮擋或超出視野時，由于目標運動的非線性特性，這些方法仍然可能丟失目標。本文提出了一種結合匹配檢測和粒子濾波的跟蹤算法，當目標被遮擋或由于相似干擾造成判定丟失時，使用改進SSDA檢測整個圖像并重啟跟蹤算法，使得遮擋或干擾結束后，能夠正確地跟蹤原目標，提高了跟蹤性能。

1 粒子濾波跟蹤概述

1.1 算法原理

非線性系統狀態空間模型如圖1，其狀態轉移方程和觀測方程為：

式中，xk和yk分別是k時刻的狀態值和觀測值；f(·)是狀態轉移函數，在跟蹤算法中，主要包含x軸和y軸移動速度以及縮放因子sc；g(·)是觀測函數，在跟蹤算法中是一個高斯函數，,d為觀測點與目標的Bhattacharyya相似系數，1-d是Bhattacharyya距離，g(·)函數描述了觀測點與目標的相似度。uk和vk是相互獨立的噪聲。

圖1 非線性系統狀態空間模型Fig.1 State space model of nonlinear system

粒子濾波將目標狀態的估計問題轉換為利用貝葉斯公式求解后驗概率密度p(xk|y1:k)，進而獲得目標狀態的最優估計，其中y1:k={y1,y2,…,yk}。其核心思想是利用一系列隨機樣本的加權和表示條件后驗概率密度p(xk|y1:k)，假設從后驗概率密度p(xk|y1:k)中抽取N個獨立同分布的樣本,則有p(xk|y1:k)≈，其中δ(·)是狄拉克函數。然后計算，使用作為xk的估計值，這種方法在貝葉斯估計中稱為條件期望參數估計方法，也被稱為最小方差估計，是無偏一致估計。

抽取N個樣本點，則有：

式（3）代入式（2）中可得式（5），式（4）是權值公式。在粒子濾波跟蹤算法中，首先將權重遞推表示為，對應觀測函數對應狀態轉移函數f(·)，將提議分布q(xk|y1:k)設計為f(·)，則有。依據馬爾可夫模型，權重遞推公式簡化為。當第k-1次迭代完成后得到，進入第k次循環后，立即使用輪盤賭法重采樣，并重置，權重遞推公式進一步簡化為，即得到粒子濾波跟蹤算法。

上述公式推導過程中，通常假設觀測值相互獨立且目標的狀態轉移過程服從一階馬爾可夫模型：即觀測值yk只與k時刻的狀態xk有關，當前時刻的狀態xk只與上一時刻的狀態xk-1有關。

1.2 算法步驟

步驟1讀取第一幀，初始化目標狀態和顏色特征。

步驟2產生粒子集。

步驟3計算粒子權重。

步驟4從第2幀到結束幀執行以下操作：

（4.1）重采樣粒子集；

（4.2）讀入下一幀作為當前幀；

（4.3）粒子傳播；

（4.4）更新粒子權重；

（4.5）估計目標狀態；

（4.6）更新目標顏色特征。

步驟（4.3）對應在提議分布q(x|y)中采樣，提議分布定義為f(·)，即算法通過狀態轉移函數在當前幀上采樣，其輸入為上一代（幀）粒子去除退化粒子的重采樣集合。步驟（4.4）使用觀測函數g(·)，計算步驟（4.3）采樣粒子的權重，步驟（4.5）使用公式（6）估算目標位置。此外，跟蹤目標在移動過程中可能會發生某些變化，需要更新目標顏色特征。

1.3 研究問題分析

在粒子濾波跟蹤過程中，由于物體遮擋等原因，引起跟蹤目標丟失。此時，粒子濾波算法具有自恢復能力，能夠收斂到新的目標位置。但是，通常收斂到一個錯誤位置。如圖2所示，使用ACPF算法跟蹤行人，行人從右向左移動，通過障礙物后，后續幀完全丟失跟蹤目標。

圖2 ACPF算法丟失目標展示Fig.2 Case of ACPF algorithm losing target

為了便于分析，定義相似度Γ(i)，記錄第i幀采樣粒子集的最大Bhattacharyya系數，該值越大相似度越高，跟蹤過程的最大相似度曲線如圖3所示。該曲線先陡降，再緩慢上升恢復到穩定曲線，說明ACPF算法具有一定的自恢復能力，但是從跟蹤的結果上看，目標停留在一個錯誤位置。分析過程可以發現，當遮擋引起目標丟失時，會立即造成相似度降低，目標被全部遮擋時出現相似度極小值，之后由于ACPF算法步驟（4.6）更新目標特征，將使算法學習到更多的錯誤顏色分布。從程序的角度來看，相似度在逐步增加；從跟蹤結果看，和真實目標距離越來越大，跟蹤目標指示一個錯誤的位置。除非目標重新進入跟蹤框，否則ACPF算法將停留在一個錯誤位置。

圖3 行人跟蹤過程相似度變化曲線Fig.3 Similarity curve of pedestrian tracking process

2 序貫相似性檢測算法概述

序貫相似性檢測算法（sequential similiarity detection algorithm，SSDA）是對傳統模板匹配算法的改進。設Pic(x,y)是M×N的待搜索圖像，T(x,y)是m×n的模板圖，Ti,j∈Pic(x,y)是搜索圖中一個子圖，(i,j)是子圖的左上角坐標，且1≤i≤M-m,1≤j≤N-n。SSDA算法步驟如下：

步驟1初始化i=1,j=1，像素累積誤差閾值ξ，模板均值。

步驟2對?(i,j)執行如下操作，計算R(i,j)：

（1）計算(i,j)子圖均值：

（2）計算(i,j)子圖像素點絕對誤差：

（3）對(i,j)子圖，按照從上到下、從左到右的順序計算累積誤差，累積誤差超過閾值ξ，立即終止，記錄達到累積誤差閾值的最小點數R(i,j)：

步驟3取R(i,j)最大值點的坐標(i,j)，該點對應子圖為匹配圖像。

SSDA算法直接對比像素灰度值，易于實現，但是對旋轉、形變、縮放、遮擋和超出視野等情況敏感；考慮到跟蹤環境的復雜性，在粒子濾波跟蹤算法丟失目標的情況下，不能直接使用SSDA來恢復跟蹤目標。

3 抗遮擋粒子濾波跟蹤算法

3.1 算法描述

本文提出的抗遮擋粒子濾波跟蹤算法見算法1。

算法1融合改進序貫相似性檢測的抗遮擋粒子濾波跟蹤算法

1.讀取視頻第一幀，選取跟蹤目標，初始狀態X0=(centerx,centery,0,0,Hx,Hy,1)

3.初始化粒子集S={pli,1≤i≤N}，權重W={wi=1/N,1≤i≤N},粒子數N=100，且

4.初始化權重，基于第一幀計算每個粒子和目標模板的Bhattacharyya距離di，然后使用高斯函數更新權重wi,i∈{1,2,…,N},并歸一化，其中σ2=0.01，令Γ(1)=max(di)，i∈{1,2,…,N}

5.重采樣過程，S=resample(S,W)，采用輪盤賭法，選擇權重較大的粒子

7.觀測過程，讀入下一幀nf,對?pli∈S,計算pli在幀nf上對應區域的顏色特征pli,histo，使用pli,histo和Thisto計算粒子pli和目標模板的Bhattacharyya距離di，并更新wi,令Γ(n)=max(di)，i∈{1,2,…,N}，其中n是當前幀的序號

8.使用算法2檢測目標丟失并處理

10.更新目標模板，計算狀態Xnew在nf幀相應區域的顏色特征Tnew,histo，目標模板更新公式為Thisto=(1-α)Thisto+αTnew,histo，學習因子α=0.01

11.如nf是視頻最后一幀，退出；否則轉步驟5

首先從視頻序列中讀入第一幀，由用戶選擇目標初始狀態X0,其結構包括目標矩形框中心坐標(centerx,centery)、橫縱向移動速度(vx,vy)、寬度Hx、高度Hy和縮放因子sc。目標特征使用帶權顏色直方圖，靠近目標框中心點的像素權重大，是X0的顏色分布。顏色分布是8×3矩陣，8是直方圖通道數，3是RGB顏色分量，每列之和為1。設粒子pli的顏色分布為pli,histo，其Bhattacharyya系數計算公式為，式中矩陣乘法為點乘，和值的范圍是0～3，所以0≤di≤1。

傳播過程就是對重采樣后的粒子集執行狀態轉移操作，其中狀態轉移矩陣為：

算法1展示了本文算法的整體框架，算法2為目標丟失檢測和恢復算法。

算法2丟失目標檢測與恢復算法

輸入：n,Γ,,Xnew,α,Thisto

輸出：S,W,n,re

1.去除Γ中為1的元素，對Γ做差分運算，令dΓ(1:n-1)=diff(Γ(1:n)),n為當前幀序號，初始化re=0

3.跳過Δ幀，令n′=n+Δ，讀取第n′幀，ifn′＞NumOfFramesthen退出endif；

5.REPEAT

6.ifn′＞NumOfFramesthen退出；else讀取n-1和n′幀，分別為ff和sf；endif

7.當前位置檢查：計算當前位置相似度dc；ifdc＞λ，令(cx,cy)等于當前位置，dmax=dc；break；else順序執行；endif

8.幀差法：frameSub=im2bw(abs(ff-sf))，初始化相似度di,j=0，1≤i≤M，1≤j≤N

9.對于?(i,j),1≤i≤M,1≤j≤N,ifframeSub(i,j)==1 then以(i,j)為窗口左上角，窗口大小與Xnew一致(如果窗口超越圖像邊界，減小窗口到最大邊界值)，計算窗口顏色分布Ti,j和相似度，di,j=Bhattacharyya(Ttarget,Ti,j)endif

10.dmax=max(di,j),ifdmax≤λ,thenn′=n′+Δ;continue;else(I,J)=find(di,j＞dmax×0.95);?(k,l)∈(I,J),計算點(k,l)到Xnew狀態位置的幾何距離disk,l,dismin=min(disk,l),(K,L)=find(disk,l＜d ismin×1.1),cx=(int)mean(K),cy=(int)mean(L),flag=1 endif

11.UNTILflag==1

12.使Γ(n:n′-1)=1,Γ(n′)=dmax,X(n:n′-1)位置均勻定義在Xnew到(cx,cy)的直線上

13.在(cx,cy)位置重新初始化粒子集S，基于n′幀更新權重W,re=1,n=n′，退出

其主要工作包括：（1）目標丟失判定；（2）改進SSDA匹配檢測；（3）重建目標狀態和重啟跟蹤算法。算法2中，步驟2和步驟12“退出”指的是從算法2返回算法1；步驟3和步驟“6退出”是結束整個跟蹤算法，NumOfFrames表示視頻總幀數。返回re=1表示檢測到目標丟失且恢復成功，否則表示沒有丟失目標。

3.2 目標丟失判定

通過OTB-100數據集中human6視頻序列，分析ACPF算法跟蹤過程中Γ參數的變化過程。該視頻序列在380幀之后出現目標遮擋、縮放和超出鏡頭視野范圍等情況。圖4展示了隨機運行三次ACPF算法的Γ曲線，由于算法的隨機性，曲線的細節處略有不同，但三條曲線的變化趨勢是一致的。共同特點是前半部分曲線變化緩慢，后半部分出現鋸齒狀下降。由于后半部分視頻序列跟蹤環境復雜，造成反復丟失目標，Γ曲線多次出現陡降和緩慢上升過程。

對圖4（a）曲線對應的Γ(1:N)序列做差分運算得到dΓ(2:N)，其中dΓ(n)=Γ(n)-Γ(n-1)，2≤n≤N，“:”與MATLAB中的冒號運算語義一致。繪制dΓ曲線如圖5所示，可以發現，差分序列在0值附近上下振蕩。當出現目標丟失時，出現劇烈振蕩。據此，定義τ=為失真強度，其中n為當前幀，mean(·)函數求向量均值，若τ大于閾值th且Γ(i)＜λ時，則判定當前幀檢測到目標丟失。

圖4 隨機3次跟蹤Human6序列相似度變化曲線Fig.4 Similarity curve of tracking Human6 sequence three times

圖5 圖4（a）中Γ參數差分結果Fig.5 Difference ofΓ parameter in curve of Fig.4（a）

3.3 改進SSDA匹配檢測

當算法檢測到目標丟失，將對其進行處理，處理算法的框架基于SSDA。首先跳過Δ幀，然后使用改進SSDA做匹配檢測；若找到目標，進入下一步操作；否則繼續跳過Δ幀做匹配檢測，直到找到目標或視頻結束。改進SSDA算法首先利用幀差法找到兩幀間的變化位置，降低計算量；通過前景背景分析法可知，目標一定出現在像素點灰度值變化的位置。使用im2bw(·)函數將幀差法的結果轉化為二值圖像frameSub，后續匹配檢測只考慮frameSub中值為1的點。此外，改進SSDA算法使用Bhattacharyya系數代替像素累積誤差，見算法2步驟9。該步替換SSDA算法步驟2，是一個二重循環，計算每個變化點所確定窗口的顏色分布和相似度，當最大相似度大于閾值λ，就判定當前幀包含目標。

3.4 重建目標狀態和重啟跟蹤算法

圖6展示了改進SSDA檢測行人位置的過程，設第300幀的行人狀態已知，要求確定行人在第305幀中的位置。首先將兩幀做幀差法，變化的像素點對應c和d圖中的亮點；然后對變化點做相似檢測，取相似度大于dmax×0.95的點，形成如c圖中三個藍色點聚集區，圖中用方框圈起來；再取與第300幀中行人距離小于dmin×1.1的點作為候選聚集區，見d圖圓圈區域。取d圖圓圈內藍色點坐標值的平均值作為行人位置。

圖6 改進SSDA算法匹配檢測案例Fig.6 Example of improved SSDA matching

4 實驗及結果分析

為了驗證算法的優越性，將本文算法與ACPF、經典跟蹤算法和粒子濾波跟蹤最新研究成果作比較。實驗環境為Win10操作系統，Intel Core i5-7200，2.50 GHz CPU和MATLAB 2012b軟件。實驗數據集為OTB-100，其中前50個視頻序列，又被稱為OTB-50[23]。通過平均中心位置誤差（average center location error，ACE），單位為像素；平均跟蹤精度（average tracking accuracy，ATA）和跟蹤成功率（tracking success rate，TSR）對算法做性能評估。設第k幀的跟蹤位置誤差定義為errk=分別是跟蹤框的中心位置和目標的真實中心位置，假設視頻序列總共為N幀，則。第k幀的跟蹤精度定義為跟蹤邊框和真實邊框的重疊率，accuk=(sk?st)/(sk?st)，其中sk為跟蹤框面積，st為目標的真實框面積；平均跟蹤精度計算公式定義為。當某幀的跟蹤重疊率大于0.5時，判定該幀跟蹤成功，一個視頻序列的TSR定義為跟蹤成功的幀數除以總的跟蹤幀數。

實驗參數設置，粒子數N=100；隨機縮放因子sc∈[-0.1,0.1]；相似度閾值λ=0.8；跳過幀參數Δ=2，跳過幀的目標狀態根據重建的目標狀態與Xnew計算；失真強度閾值th直接影響目標重建的次數和算法的運行時間，取值在3到8之間，實驗中取5。考慮到算法的隨機性，對視頻序列運行三次本文算法和ACPF算法，取次優結果作為實驗結果。表1列舉了OTB-100中20個視頻序列的跟蹤結果，從平均結果看本文算法在ACE、ATA、TSR三個指標上都比ACPF好，幾乎所有視頻序列的跟蹤性能都得到提升。然而，不是每個視頻的跟蹤成功率得到顯著提升，如Ironman、Matrix和Tiger1等；這是因為算法僅使用圖像的顏色特征，當背景相似或雜亂時，將導致目標丟失檢測失敗或重啟錯誤。此外，值得注意的是Jump、Panda和CarScale序列的跟蹤成功率略有下降，這是因為ACPF算法對三個視頻序列的跟蹤成功率已經很高，檢測到目標丟失的概率低，造成結果差異的主要原因是算法的隨機性。

表2中SCM、ALSA、STRUCK、CSK、DFT和VTD是OTB-50測試基準中，抗遮擋性能排名前六的算法，表中列舉了它們對OTB-50數據集中含遮擋特性視頻的跟蹤成功率，數據來源于文獻[24]。實驗針對OTB-50中的含遮擋特性視頻運行ACPF和本文算法，得到ACE、ATA、TSR分別為88.3、0.361、0.429和44.4、0.5、0.586。提出算法比ACPF跟蹤成功率提升36.6%，比OTB-50（OTB-100子集）測試基準中抗遮擋最優算法SCM提升3.2%。

表1 與ACPF算法比較Table 1 Results of comparing with ACPF algorithm

表2 不同算法跟蹤成功率比較Table 2 Comparison of TSR of different algorithms

表3列舉了在光照變化（IV）、尺度變化（SV）、形變（DEF）、運動模糊（MB）、快速移動（FM）、旋轉（PR）、超出視野（OV）、背景雜亂（BC）和低分辨率（LR）等復雜場景的跟蹤成功率TSR對比。統計數據表明本文算法在各種場景均表現出比ACPF更好的性能。

表3 OTB-50中不同場景跟蹤成功率對比Table 3 TSR of different scenarios in OTB-50

圖7展示本文算法在Human6、Jump、Girl和Liquor視頻序列上的跟蹤效果。其中紅色框是目標真實位置，綠色框為本文算法跟蹤到的位置。從圖中可以看出，五種算法都有脫靶的情況，本文算法表現較好。圖8展示了ACPF和本文算法的Γ變化情況，分別用藍色和紅色實線表示；從圖中可以看出，本文算法得到的Γ曲線比ACPF算法的Γ曲線陡降點少，較為平滑，說明本文算法的穩定性更好。

假設圖像尺寸為M×N，目標尺寸m×n，視頻序列長度為L，粒子數A，通常情況下有M×N＞m×n。粒子大小與目標一致，忽略讀取視頻文件等其他細節，則ACPF總時間復雜度為O(L(2mn+4)A)，與視頻序列長度及目標尺寸成正比，但是與每幀的圖像大小無關。令K=max(L,m,n)，忽略A等常數，算法時間度為O(K3)。改進SSDA算法的時間復雜度為O(2MNmn+MN)，設檢測到丟失目標的概率為α，則本文算法的時間復雜度為O(L(2mn+4)A)+O(αL(2MNmn+MN)),通常α?1。所以本文算法的時間復雜度與每幀的圖像大小有關。令K=max(L,M,N,m,n)，忽略A等常數，當a=0時，本文算法時間復雜度為O(K3)，當α=1時，時間復雜度為O(K5)。通常α很小，檢測幀數αL小，且幀差法之后，候選塊個數可以降低80%左右，總候選塊數約為0.2MN；所以，本文算法時間度約為O(K4)。本文算法與ACPF相比時間復雜度有所增加，表4展示了兩者在圖7視頻序列上的運行時間，單位為秒；其中目標尺寸是初始目標大小，運行過程中算法會自適應目標尺度變化。

表4 本文算法與ACPF運行時間對比Table 4 Comparison of running time between proposed argorithm and ACPF

圖7 五種算法的跟蹤效果圖Fig.7 Tracking results of five algorithms

圖8 ACPF和本文算法的Γ變化情況對比Fig.8 Change comparison ofΓ between ACPF and proposed algorithm

表5中MFFPF和PFOH分別為文獻[11]和[15]提出的算法；MFFPF是一種新的特征融合粒子濾波跟蹤算法，沒有引入抗遮擋處理；PFOH是一種基于SURF特征的抗遮擋粒子濾波跟蹤算法。表中MFFPF和PFOH列的跟蹤成功率數據來源于對應文獻。作者嘗試提取Human6初始目標框內圖像的SURF特征，由于目標太小和分辨率太低，提取出的SURF特征點個數為0，導致算法無法進行特征點匹配而失敗；此外，SURF特征對目標形變敏感，所以本文算法比PFOH抗遮擋的通用性更好。

表5 與最新粒子濾波跟蹤研究成果比較Table 5 Comparison with latest research results

5 結束語

本文首先分析了粒子濾波跟蹤過程中的丟失目標問題。為此，提出一種融合改進序貫相似性檢測的粒子濾波算法。該算法整體框架與傳統粒子濾波跟蹤算法相同，增加了丟失目標狀態檢測、改進序貫相似性檢測、目標狀態重建和重啟算法過程。通過標準測試數據集對比實驗表明，本文算法能夠有效提高遮擋環境下的跟蹤精度和穩定性。