基于運動粒子的粒子群目標跟蹤算法

劉 博，蘇成志，溫迎晨，張小忱，王恩國*

（1.長春理工大學 機電工程學院，吉林 長春130022；2.長春理工大學 人工智能研究院，吉林 長春130022）

目標跟蹤是機器視覺領域中比較重要和熱門的研究方向，也是各種視頻應用中的一個基本任務。目標跟蹤是指對視頻序列中的運動目標進行跟蹤，即通過給定第一幀的目標位置預測目標在后續視頻序列中的位置[1]。目標跟蹤在無人駕駛、無人機監測、水上智能監控、視頻監控、數據檢索、醫學治療以及軍事偵察等諸多領域有著廣泛的應用[2-5]，存在很高的應用價值和廣闊的應用前景。

在目標跟蹤領域，Isard首先提出CONDENSATION算法并利用粒子濾波算法解決目標跟蹤問題[6]。經典粒子濾波算法容易實現且簡單有效，對噪聲干擾和目標遮擋具有較強的處理能力，但粒子濾波算法在目標遮擋情況下跟蹤精度降低，并且存在計算量大和實時性不好等問題[7-10]。近年來，隨著深度學習和卷積網絡的飛速發展，Seunghoon等人[11]通過使用卷積神經網絡學習辨別顯著性圖提出在線視覺跟蹤算法，提高了準確度。Heng等人[12]提出利用循環神經網絡（RNNs）對目標結構進行建模，采用級聯策略融合CNN與RNN，提高了魯棒性。由于深度學習的深層結構，計算復雜度高，導致很難達到實時跟蹤的要求。

針對以上算法存在的不能兼顧目標跟蹤時的處理速度與準確性的問題，本文另提出一種基于運動粒子的粒子群目標跟蹤算法。該算法首先提取目標的HSV特征得到目標特征向量；然后為了提高跟蹤的準確度在跟蹤點周圍撒下n個粒子構成粒子群，用梯度收斂算法來找到粒子群中單個粒子的最優解和粒子群的最優解，以種群的最優解作為下幀跟蹤的跟蹤點進行目標的跟蹤。

1 提取目標HSV特征

在跟蹤過程中，目標模型的建立可以為后續跟蹤提供數據支撐，因此針對跟蹤目標建立模型是目標跟蹤算法首先要解決的問題。直方圖作為一種經典統計模型，具有計算簡便且易于實現的特點，廣泛應用于機器視覺領域，是一種很好的圖像特征表示手段。本文算法在首幀圖像中選取所要進行跟蹤的目標區域（通常為矩形窗口），以窗口中心為跟蹤點，對目標區域進行直方圖統計建立目標特征模型，從而得到目標特征向量。

1.1 建立HSV顏色特征模型

RGB模型作為應用最廣泛的彩色模型，雖然能很好地吻合人眼強烈感知紅、綠、藍三原色的事實，但不適用顏色的直觀描述；HSV模型采用色調（Hue）、飽和度（Saturation）和明度（Value）來描述物體，更符合于人類視覺的直觀感受。相較于RGB模型，HSV模型各個通道的相關性較小。因此，本文算法通過提取HSV特征得到目標特征向量。

如圖1所示，將圖像由RGB模型轉為HSV模型進行描述。為方便偽彩色顯示，對HSV三通道取值范圍進行量化處理，將取值區間由[0，360]、[0，1]和[0，1]分別拉伸或者壓縮至區間[0，255]。由于V通道對光照變化非常敏感，為了盡量減少明暗變化的影響，在對目標建立顏色特征模型過程中，僅針對H通道和S通道建立直方圖模型。

圖1 HSV模型的偽彩色顯示

如圖2所示，首先對從源圖像劃分的目標區域分別建立H直方圖模型和S直方圖模型；假設目標區域中共有N個像素，第i個像素點的坐標為（xi，y）i，則第i個像素點的H通道信息為H（xi，y）i，S通道信息為S（xi，y）i。由于經過量化處理后H和S通道數據的取值范圍均為0~255，為盡可能將數據離散化和方便統計，將直方圖組數（Bins）設置為128。通過式（1）和式（2）計算可得H直方圖模型H={Hu}和S直方圖模型S={Su}。

圖2 提取顏色特征模型

其中：如式（3）所示，δ為克羅內克函數（Kronecker delta）；u=0，1，…，127；w為目標區域寬度；h為目標區域高度。

1.2 目標特征向量

通過上述方法得到HSV顏色特征模型后，然后對H直方圖模型和S直方圖模型進行串聯處理，如式（4）所示，便可得到目標特征向量C=（C0，C1，...，C127），C0~C63為H通道統計信息，C64~C127為S通道統計信息。

其中：Hu是H直方圖模型，Su是S直方圖模型，u=0，1，…，127。

1.3 特征提取的快速算法

1.3.1 快速算法的原理

在提取特征時，本文在原有特征提取的基礎上提出一種快速算法。如圖3所示，當粒子P的特征提取完后，對運動位置M2進行特征提取時，由于M2是P向上移動一行像素，只有首行像素是新信息，因此只需要在P特征提取信息的基礎上添加M2首行信息，刪除P最后一行的無用統計信息，這樣就能得到運動位置M2的特征提取信息。

圖3 快速算法

同理依次對M3、M5、M8、M7、M6、M4、M1運動位置的特征提取信息進行處理，就可以得到粒子P所有鄰近位置的特征向量。

1.3.2 快速算法的優勢

從算法原理可知該算法通過重復利用已知區域信息，可以很大程度上減小計算量，提高算法效率，如式（5）所示。

其中：v為快速算法對傳統算法的倍數，w為目標區域寬度，h為目標區域高度。該快速算法與傳統特征提取算法相比，在邊長為5的正方形區域內提高了3.5倍，而寬度30，高度70的目標區域，提高了7.7倍。由此可知，當目標區域越大時，該算法的提升速率越高。

現在已經得到了目標特征向量，接下來先撒下n個粒子，然后通過以目標特征向量為核心的梯度收斂算法使每個粒子進行收斂運動。

2 結合梯度收斂算法的粒子群算法

首幀圖像提取HSV特征得到目標特征向量后，在下一幀圖像中，首先，通過粒子群算法在跟蹤點周圍撒下n個粒子，以此來增加算法的準確度；然后，通過梯度收斂算法尋找單個粒子的最優解和整個粒子群的最優解，單個粒子的最優解稱為個體極值，整個粒子群的最優解稱為全局極值。用全局極值更新跟蹤點的坐標，進行下一幀的跟蹤。

2.1 粒子群分布

本文根據式（6）在跟蹤點周圍撒下n個粒子形成粒子群，其中撒下的粒子中距離跟蹤點越近粒子數越多，在目標跟蹤過程中，當相似因子ε較小時，為了更好地跟蹤目標，本文采用擴大粒子群分布區域的方法，該方法通過式（7）建立相似因子ε和σ的函數關系來控制分布區域的大小。

如圖4所示，圖中的白色矩形框為目標區域，（a）圖為目標未被遮擋的跟蹤效果圖，此時粒子群分布都收斂到一個區域；（b）圖為目標被遮擋時的跟蹤效果圖，為了能夠重新找到目標，此時的粒子群分布發散。

圖4 粒子群分布變化

2.2 尋找個體和全局極值的梯度收斂算法

2.2.1 相似因子ε

相似因子用來表征搜索區域與目標區域的相似程度。如圖5所示，假設粒子P為粒子群中的某一粒子，5行5列的正方形區域為粒子的窗口區域，在某一幀圖像中粒子P除了停止運動外，有8個運動方向分別為：M1、M2、M3、M4、M5、M6、M7、M8。

圖5 單粒子移動

對當前位置窗口區域和鄰近的8個區域進行特征向量提取，可以得到當前位置窗口區域的特征向量S0和鄰近的8個區域的特征向量S1、S2、S3、S4、S5、S6、S7、S8。通過式（8）對當前位置窗口區域和鄰近的8個區域進行相關性計算，得到當前位置窗口區域的相似因子ε0和鄰近的8個區域的相似因子 ε1、ε2、ε3、ε4、ε5、ε6、ε7、ε8。

其中0≤ε<1，ε值越大，與目標區域相似程度越大，該區域為目標區域的可能性越大，反之可能性越小。

2.2.2 梯度收斂算法

單粒子的運動采用梯度下降法不斷沿著相似因子梯度最大的方向進行運動直至收斂。

如圖6所示，假設粒子P當前位置（像素坐標）為（x0，y）0，通過式（8）得到粒子P周圍位置及當前位置的相似因子后，通過式（9）計算梯度信息，與像素坐標信息構成三元組（x，y，g），得到信息集合A={ai|ai=（xi，yi，g）i，0≤i≤8}。

圖6 位置梯度信息三元組

利用式（10）計算得出g最大的三元組信息，并利用其中的像素坐標信息更新P粒子的像素坐標，則P粒子向g最大的位置運動；若當前位置的g最大，即g=0為最大值，則P粒子收斂。

當所有粒子完成收斂運動后，此時的所有粒子并不一定都收斂到同一位置，比較所有收斂位置的相似因子，將相似因子最大的位置作為下幀跟蹤的跟蹤點。

3 實驗與分析

3.1 實驗過程及中間結果

3.1.1 粒子群的分布結果

粒子群分布情況如圖7所示，圓為目標跟蹤點，黑點是分布的每個粒子。由圖7可知，粒子的分布與前面的描述相同，離跟蹤點越近粒子數越多。

圖7 粒子分布

3.1.2 粒子群的運動

任取一幀圖像，單個粒子單步運動過程及結果如圖8所示，其中（46，48）是粒子P的坐標位置，Col表示當前位置的相似因子大小，（46，49）坐標位置對應圖5的M2位置，可知M2位置的相似因子最大，因此粒子P向M2位置運動，下一步以M2為中心點，繼續判斷粒子的運動方向。

圖8 單粒子運動軌跡

所有粒子的總體運動軌跡及結果如圖9所示，圖中小圓是上幀圖像的目標點，每個黑點代表一個粒子，黑色線是粒子進行收斂運動的軌跡，三角形是粒子收斂后的位置，Col是相似因子的大小。從圖9中可以看到最終收斂到三個位置，比較這三個位置的相似因子，將相似因子最大的位置作為下幀跟蹤的跟蹤點。

圖9 所有粒子運動軌跡

3.2 實驗分析

為了評估算法性能，先從速度、準確度兩個角度與CSK、KCF、MS、CPF、Struck、DFT算法進行實驗對比，然后從兼顧速度與準確度角度與其他算法進行跟蹤性能評價，本算法在實驗過程中以Ours命名。

如表1所示，在OTB2013中選取5組彩色序列作為測試序列，所有算法保持原有參數不變。計算機硬件配置為Inter Core i7 CPU，內存8G，實驗平臺環境為Matlab 2016b。

表1 實驗的視頻序列

3.2.1 速度分析

各個算法對OTB2013中選取的5組實驗序列的處理速度結果如表2所示，表中數據單位為幀/秒，其中Av列為各個算法對5組視頻序列的平均處理速度，計算公式如式（11）所示。

表2 不同跟蹤算法的處理速度

從Av列數據可知，本文算法處理速度為199.0幀/秒，比CSK慢了1.54倍，與MS算法比較接近，而其他算法皆低于本文算法。

3.2.2 準確度分析

為評估算法的準確度，本次實驗使用OPE（One Pass Evaluation）模式，采用中心位置誤差標準作為評價標準，繪制精確度曲線（precision plot）。其中，如式（12）所示，中心位置誤差P是指算法的目標中心位置（xr，y）r和真實目標中心位置（xs，y）s的平均歐式距離值。精確度描述的是給定的中心位置誤差閾值之內跟蹤正確的幀數占總幀數的比例，本次實驗采用的閾值為20個像素。

如圖10所示，在實驗的7種算法中，本文算法精確度最高為0.790，高出CSK1.52倍、高出MS1.57倍。為更直觀地評估算法的跟蹤性能，選取精確度前五的算法在Couple、Doll和Lemming三組序列下的運行結果。

圖10 OPE精確度對比曲線

如圖11所示，在第18幀中CSK算法脫離目標；在第36幀中KCF算法脫離目標；在第92幀中CPF算法和Struck算法都脫離目標，只有本文算法能一直有效地跟蹤目標。

圖11 Couple序列部分跟蹤結果

如圖12所示，在第1628幀中CSK算法脫離目標；在第3750幀中CPF算法偏離目標；在第3774幀中Struck算法脫離目標，CPF算法重新找到目標，本文算法和KCF始終附著在目標上。

圖12 Doll序列部分跟蹤結果

如圖13所示，在第388幀中當目標被遮擋再次出現時，KCF算法脫離目標；第885幀中CSK算法脫離目標，當目標未被遮擋地運動到KCF算法丟失目標的位置時，KCF算法重新找到目標；第970幀中Struck算法脫離目標，本文算法和CPF算法一直穩定地跟蹤目標。從該序列跟蹤過程可知該算法可以克服目標短暫遮擋問題。

圖13 Lemming序列部分跟蹤結果

3.2.3 綜合分析

對速度和準確度單獨分析后，對速度和準確度進行綜合分析。如表3是各算法速度和精確度的對比。解決了其他算法在目標跟蹤時速度和精確度不能兼顧的問題。

表3 不同算法處理速度和精確度