密度峰值聚類的全尺度相關濾波跟蹤方法

肖振久，李 鑫

遼寧工程技術大學 軟件學院，遼寧 葫蘆島 125105

目標跟蹤是計算機視覺研究領域的一個重要課題，有著重要的研究意義，一般指對一段視頻圖像序列中預先選擇的目標對象進行連續(xù)的跟蹤定位，以獲得目標尺度和位置信息的研究方向，在視頻監(jiān)控、人機交互等方面有著重要應用[1]。隨著研究的發(fā)展，基于相關濾波的跟蹤方法和基于深度學習[2]的跟蹤方法都在跟蹤領域取得了重大成績[3]。雖然主流的目標跟蹤算法已經(jīng)能在一些數(shù)據(jù)集上取得較好的跟蹤效果，但在一些特殊情況下還面臨如目標遮擋、光照變換[4]等很多困難。如何解決這些挑戰(zhàn)，是目標跟蹤領域亟待解決的問題。

目標跟蹤算法在建模上可分為生成式方法[5]和判別式方法[6]，生成式跟蹤方法主要通過建立模型后直接與跟蹤目標進行匹配，經(jīng)典的方法有均值漂移算法[7]（Mean-Shift），Mean-Shift算法實現(xiàn)簡單，速度較快，但是沒有考慮背景信息，在面對背景復雜、快速運動、尺度變換等問題時跟蹤效果較差。判別式跟蹤方法將目標跟蹤問題轉(zhuǎn)化為目標與背景信息的二分類問題，區(qū)分目標與背景以實現(xiàn)目標的跟蹤。經(jīng)典的判別式算法有Struck[8]、TLD[9]等，盡管判別式算法具有較快的跟蹤速度，依然不能滿足目標實時性的要求。尋找一種效率與精準度更高的算法依然是該領域研究的重要方向。最小平方和誤差濾波器[10（]MOSSE）首次將相關濾波方法用于目標跟蹤領域，通過卷積（CNN）的方法，快速將目標與背景信息的相似程度進行對比，對目標進行采樣與學習。核循環(huán)結構跟蹤方法[11（]CSK）在MOSSE的基礎上引入了循環(huán)矩陣和核的概念，通過密集采樣大幅擴充了訓練樣本的容量，從而提升了跟蹤精度，同時由于采用了核技巧，導致訓練時間并沒有因為訓練樣本的增加而延長，解決了MOSSE中采用稀疏矩陣造成的樣本冗余問題。核相關濾波算法[12（]KCF）引入高斯核函數(shù)，利用訓練樣本的周期性假設來對目標鄰域中的分類器進行有效地學習，并在CSK的基礎上擴展了多通道梯度特征[13]，提高了濾波器的跟蹤效果。背景感知相關濾波算法[14（]BACF）在傳統(tǒng)相關濾波的跟蹤方法上增加了樣本數(shù)量，同時通過裁剪操作提高了樣本質(zhì)量，解決了相關濾波跟蹤中目標背景不能隨時間建模導致的次優(yōu)性問題，并在實現(xiàn)過程中對求解過程進行了優(yōu)化，較大地提高了跟蹤器的跟蹤效果。然而，傳統(tǒng)的相關濾波器在對尺度預測上依然存在較大的缺陷，文獻[15]提出了快速尺度估計的增強型多核相關濾波算法，在KCF的基礎上引入一種快速判別式尺度估計的目標跟蹤方法。文獻[16]針對尺度突變問題，提出了一種先檢測后跟蹤的自適應尺度突變的跟蹤算法。在尺度方面做了改進，提出了尺度自適應核相關濾波目標跟蹤。文獻[17]通過尺度池在線學習判別式尺度濾波器，在目標位置估計最佳目標尺寸，提出了自適應尺度的上下文感知相關濾波跟蹤算法。

這些方法著重于算法的精確度，對濾波器的訓練速度并沒有大幅的提升，為了有效解決濾波器的訓練跟蹤速度，在保證跟蹤效果的同時盡可能提高跟蹤效率，本文在傳統(tǒng)跟蹤方法中引入密集峰值聚類算法[18（]DPC），并將其應用于BACF跟蹤框架。（1）對目標區(qū)域與背景區(qū)域分別進行聚類。（2）使用單尺度傳統(tǒng)目標跟蹤方法對位置進行粗定位。（3）在定位過程中，取消了圖像金字塔的跟蹤訓練方法，通過DPC方法進行尺度回歸，最終得到目標的尺度與位置。（4）對目標函數(shù)問題進行優(yōu)化求解，通過構造輔助因子，利用增廣拉格朗日乘子法和ADMM方法進行求解，在數(shù)據(jù)集OTB2013、OTB2015和DTB70上評估本文算法，實驗結果表明，與當前主流算法相比，在保證準確率的情況下，本文算法的跟蹤速度能夠達到47.09幀/s。

1 背景感知算法相關原理

傳統(tǒng)相關濾波器在當前幀構造一個濾波器模板，以求得下一幀圖像中目標的響應圖，相應圖峰值為目標的中心位置。核檢測跟蹤的循環(huán)結構目標跟蹤算法（CSK），采取嶺回歸的方法對問題進行求解，通過密集采樣擴大了樣本容量，提高了跟蹤精度與跟蹤效率，其目標函數(shù)如下：

式中，m是訓練樣本數(shù)量，h是濾波器權重矩陣，是正則項，防止濾波器模板出現(xiàn)過擬合現(xiàn)象，L(y,f(x))=(y-f(x) )2是損失函數(shù)，f(x)是線性分類器，記為f(x)=w,x+b，λ是正則項系數(shù)。

核相關濾波算法（KCF）通過訓練樣本的周期性假設來對目標鄰域中的分類器進行高效學習。并在CSK的基礎上增加了HOG特征以提高跟蹤效果，其目標函數(shù)如下：

式中，h為濾波器權重矩陣，yi為真實響應矩陣，f(xi)為濾波器響應矩陣，為正則項，訓練的目標是找到一個函數(shù)f(z)=wTz，使其能夠最小化樣本及其回歸目標yi的平方誤差，λ是控制過擬合的正則化參數(shù)。

背景感知相關濾波算法（BACF）使用由真實位移產(chǎn)生的負樣本，擴充了樣本容量，并通過ADMM方法對濾波器模型進行求解，極大地降低了求解過程的時間復雜度，其目標函數(shù)如下：

其中，P是一個D×T的二進制矩陣，它剪裁信號xk的中間元素。

2 密度峰值聚類的全尺度跟蹤模型

本文提出一種基于密度峰值聚類的全尺度相關濾波跟蹤方法，通過聚類模型代替圖像金字塔進行尺度預測，使用單尺度相關濾波器對目標進行粗定位，再根據(jù)聚類模型對目標中的樣本點進行預測，以得到尺度置信度最高的預測框。

如圖1（a），黃色框區(qū)域內(nèi)側為前景區(qū)域，本算法在前景內(nèi)進行間隔隨機前景采樣，得到目標的前景特征集合，如圖1（b）藍色框與黃色框之間的區(qū)域為Padding區(qū)域，在Padding區(qū)域內(nèi)對背景進行間隔隨機采樣。采樣后對前景區(qū)域與背景區(qū)域分別進行聚類運算。為了減少前景樣本空間中的背景點對前景聚類產(chǎn)生干擾影響，在聚類過程中，需要從前景信息點中剔除與背景特征近似的點，以此對前景點的聚類進行更合理的劃分，從而得到更準確的前景點聚類中心。

圖1 前背景采樣示意圖Fig.1 Schematic diagram of front background sampling

2.1 密度峰值聚類的尺度預測方法

2.1.1 密度峰值聚類方法

由于數(shù)字圖像的特征矩陣滿足在聚類時，簇中心的局部密度大于圍繞它的鄰距的局部密度，且不同簇中心之間的距離相對較遠。因此本文算法通過引入局部密度來對前景點和背景點進行聚類分析。在聚類過程中，通過局部密度的定義來計算簇中心，計算方法如下：

式中，ρi是樣本點xi的局部密度，dij是特征維度為K的樣本點xi與xj的閔氏距離，dc為樣本點的截斷距離，χ(·)為邏輯判斷函數(shù)，同時，可以得到距離δi的表達式：

之后可以根據(jù)上述定義通過構造δi和ρi的決策圖，對數(shù)字圖像的前景點和背景點進行快速聚類。

2.1.2 前背景依存度κ

在不同視頻序列中，被跟蹤的目標區(qū)域內(nèi)，有可能因為遮擋或動態(tài)模糊出現(xiàn)與背景特征相似的像素點，如圖2，對于不同位置的點，不僅從聚類方法上對點的前背景歸屬屬性進行判斷，也需要從點的鄰域環(huán)境對點的歸屬進行分類。

圖2 前背景依存度計算示意圖Fig.2 Schematic diagram of front background dependency calculation

在這種情況下，本文引入前背景依存度的概念來對目標區(qū)域中相似于背景點的前景點來進行分類，點p(x,y)的前背景依存度表示如下：

式中，κ(x,y)為點p(x,y)的前背景依存度，Ψ(d,x,y)表示以p(x,y)為中心點且寬度為d的正方形檢測區(qū)域內(nèi)前景點的數(shù)量，d為待檢測點的鄰域?qū)挾取?/p>

2.1.3 自由尺度

在目標跟蹤的數(shù)據(jù)集中，部分視頻序列會出現(xiàn)前景背景特征相似的問題，為避免在前景和背景相似時，跟蹤目標出現(xiàn)劇烈的尺度變化，本文通過引入自由尺度π和尺度置信度?來提高對前背景特征相似時尺度預測的精確度，提高尺度預測的魯棒性。

在對目標尺度進行預測搜索時，本文算法僅在Boxout和Boxin的范圍之間對目標進行尺度預測，這樣能夠避免在前背景顏色相似時，或出現(xiàn)光照變換時，尺度進行波動的情況。

如圖3，上一幀中目標的尺度為Boxtraget，以當前幀目標響應值為最大點，在Boxout和Boxin的范圍之間對目標進行尺度預測，其中Boxout和Boxin的中心位置為當前幀目標響應值最大點，搜索區(qū)域的尺寸計算方法為：

圖3 自由尺度示意圖Fig.3 Schematic diagram of auto-scale

式中，width(·)為box區(qū)域的寬度，Scale(·)為box區(qū)域的縮放因子，length(·)為box區(qū)域的長度。

2.1.4 尺度置信度?

自由尺度只能從尺度的最大變換范圍給出一個限制，但在面對相似背景或邊緣分割模糊的情況下就難以預測目標的真實尺度。為解決這個問題，本文引入尺度置信度的概念，來對一個目標的尺度進行更精準的預測，尺度置信度?表示如下：

式中，?為當前預測框的尺度置信度，Areaf為預測區(qū)域的前景點面積，Areab為預測區(qū)域的整體面積，Δd為上一幀中目標區(qū)域與當前幀中預測區(qū)域的差值，a為置信度系數(shù)。如圖4所示，在預測過程中，本方法通過尋找尺度置信度最大的預測框，來對目標區(qū)域進行定位搜索。

圖4 尺度置信度計算示意圖Fig.4 Schematic diagram of scale confidence calculation

如圖4，兩幀之間進行尺度預測的過程中，虛線框為上一幀中的目標區(qū)域，實線框為下一幀的目標區(qū)域。在繼續(xù)減小目標長度時，由于目標是一個不規(guī)則圖形而非矩形，雖然區(qū)域中前景面積與區(qū)域面積的比值會繼續(xù)增大，但目標置信度?反而會由于面積的減小而縮小，從而使目標跟蹤的尺度預測更為精準。

2.1.5 間隔采樣

考慮到聚類方法的聚類速度較慢，在同一個視頻序列中顏色的分布情況近似，在一片搜索區(qū)域內(nèi)做等距離的區(qū)域分割，每個區(qū)域的顏色分布將會近似，因此，在聚類過程中本文采取間隔采樣的方法，分別對前景和背景的樣本點進行采樣。在采樣過程中，目標的尺寸為W×H，搜索區(qū)域的縮放因子為β，采樣間隔為ψ，如圖5（a）綠色區(qū)域為前景采樣區(qū)域，如圖5（b）綠色區(qū)域為背景采樣區(qū)域。

圖5 間隔采樣示意圖Fig.5 Schematic diagram of interval sampling

2.2 密度峰值聚類跟蹤模型

2.2.1 模型目標函數(shù)

為了提高在目標跟蹤過程中粗定位的精度，增強濾波器跟蹤性能，本文將聚類后的距離δi用于指導濾波器的擬合程度，由此，模型的目標函數(shù)如下：

其中，T是樣本x的尺寸大小或者像素點的數(shù)量，P是一個D×T的二維矩陣，使樣本x的尺寸從T變?yōu)镈(D?T)，Δτj為循環(huán)矩陣的第j個樣本。ω為采樣區(qū)域中全部樣本中心距離δi的最大值，用來指導濾波器的擬合程度。

2.2.2 密度峰值聚類的全尺度跟蹤模型求解

為優(yōu)化求解速度，根據(jù)循環(huán)樣本的頻域能夠快速求解的特性，使用帕塞瓦爾定理將表達式（9）變換到頻域，并引入增廣拉格朗日乘子法（ALM）進行求解，公式如下：

得到式（10）后，對g和f進行分別優(yōu)化求解，可以簡化為兩個子問題如下：

由傅里葉變換解得：

將上式對g(t)求偏導的值為0，得到：

上式中求逆運算增加了計算的復雜度，為減少計算時間，引入Shernan-Morrison[19]求解逆矩陣，降低運算復雜度，可以得到如下式子：

2.2.3 拉格朗日因子更新

最后，拉格朗日乘子向量ξ更新方法為：

2.2.4密度峰值聚類的全尺度跟蹤模型跟蹤

為了應對目標跟蹤過程中，跟蹤目標可能遇到的形變、光照和旋轉(zhuǎn)等影響，本文采用自適應策略來提高跟蹤器的跟蹤魯棒性，幀h處的在線自適應公式如下：

2.2.5 尺度預測

跟蹤過程中，本文提供的方法將先通過濾波器對目標進行粗定位，之后結合上一幀目標大小、背景樣本空間和前景樣本空間對當前幀的目標進行尺度預測。預測時將會以尺度置信度?最高的區(qū)域的尺度標記為目標的最終尺度。

3 算法步驟

由于背景感知相關濾波（BACF）跟蹤算法具有較高的準確性和魯棒性，因此本文以背景感知相關濾波算法作為主體框架，在跟蹤過程中通過基于密度峰值聚類的全尺寸預測方法進行尺度預測，并引入前背景依存度、自由尺度和尺度置信度來對目標在當前幀的尺寸進行更加精準的定位，以提高在跟蹤過程中算法的準確率和成功率。如圖6基于度峰值 聚類的全尺度相關濾波跟蹤算法模型的算法步驟如下：

圖6 跟蹤器跟蹤階段流程圖Fig.6 Tracker tracking phase flow chart

步驟1初始化階段。（1）得到初始幀的圖像進行間隔采樣。（2）根據(jù)目標區(qū)域計算出目標區(qū)域鄰近背景的尺寸，對背景區(qū)域進行間隔采樣。（3）分別對目標區(qū)域與背景區(qū)域進行密度峰值聚類，剔除目標區(qū)域中與背景近似的樣本點。（4）由分離度較高的樣本點構成樣本空間。（5）提取前景外觀特征，通過訓練得到濾波器模型。

步驟2目標跟蹤階段。（1）根據(jù)上一幀濾波器，在當前幀的搜索區(qū)域進行相關運算，得到響應圖。（2）該響應圖為目標跟蹤的粗定位中心，通過前景樣本中心計算臨近點的前背景依存度。（3）根據(jù)前背景依存度判斷當前樣本點屬于前景樣本點還是背景樣本點。（4）循環(huán)計算當前尺度的尺度置信度，得到尺度置信度最高的區(qū)域，為被跟蹤目標的預測位置。（5）該區(qū)域中心為目標預測中心，該區(qū)域的尺寸即為目標的預測尺寸。

步驟3模型更新階段。（1）對目標區(qū)域進行裁剪，根據(jù)目標區(qū)域的尺寸計算出目標區(qū)域鄰近背景的尺寸。（2）對目標區(qū)域和鄰近背景分別進行間隔區(qū)域采樣。（3）對目標區(qū)域和鄰近背景聚類，更新前景和背景的樣本空間。（4）提取前景外觀特征，訓練得到前景濾波器模型。

4 實驗結果及分析

為了驗證改進后目標跟蹤方法的有效性，本章進行性能測試。這一部分中，將本文算法與其他目標跟蹤方法進行對比，在OTB2013、OTB2015、DTB70這三個數(shù)據(jù)集上進行實驗分析。其中數(shù)據(jù)集中包含了光照變化、尺度放縮變化、遮擋等11種不同類別的跟蹤場景。采用一次通過評估方法來計算本文方法的成功率和準確率。同時，由于本文方法著重考慮通過對搜索區(qū)域內(nèi)樣本點的分類來進行目標尺度的預測，避免圖像金字塔對搜索方法速度的影響，因此在跟蹤過程中算法的運行速度也在本次實驗的討論范圍之內(nèi)。

4.1 實驗環(huán)境及參數(shù)配置

本文實驗是在處理器為Intel Core i9-9900K，操作系統(tǒng)為Ubuntu，編程軟件為Matlab2018b。

本文算法有5個參數(shù)：前背景依存度的鄰域?qū)挾萪=5，自由尺度scale-min=0.8，scale-max=1.2，置信系數(shù)α=0.5，采樣率為0.2，HOG單元大小為4×4，HOG特征通道數(shù)為31，迭代求解次數(shù)為2，其余參數(shù)與BACF的默認配置相同。

4.2 整體性能分析

在實驗中，本文選取了KCF、SRDCF[20]、Staple[21]、BACF、ASRCF[22]、LDES[23]、AutoTrack[24]、CSK、DSST[25]共9種同類型的算法進行對比實驗。圖7為10種算法在OTB2013、OTB2015以及DTB70三種數(shù)據(jù)集上面的成功率曲線和精確率曲線。在成功率上，本文算法分別超越BACF 6.80、0.70、0.10個百分點。在精確率上，本文算法在DTB70和OTB2013數(shù)據(jù)集上分別超越BACF 0.90和0.70個百分點。雖然在部分數(shù)據(jù)集上本文算法的成功率或精確率并未有超過，但在跟蹤速度上，本文算法較BACF有一個較大的提升。通過聚類DPC對尺度進行預測，能夠從一定程度上改善跟蹤器的跟蹤速度。

圖7 10種算法在不同數(shù)據(jù)集上的對比實驗Fig.7 Comparative experiments of 10 algorithms on different data sets

從表1中可以看出，本文算法的跟蹤速度相較于BACF有所提高，對比于傳統(tǒng)跟蹤算法，該算法在一定程度上減少了傳統(tǒng)圖像金字塔的跟蹤訓練方法對算法速度的影響，在保證準確率和成功率的基礎上提升速度。

表1 10種算法的平均跟蹤速度Table 1 Average tracking speed of 10 algorithms 單位：幀/s

4.3 定性分析

為了能更直觀地對算法進行定性分析，本文在OTB2015上的100個視頻序列進行實驗并選取了5組具有代表性的視頻序列進行結果展示，圖8為10種不同跟蹤算法下視頻序列的結果對比。這5組視頻序列包括目標遮擋、尺度變換等11種指標，本文選取其中5種指標，具體分析如下：

圖8 各種算法在部分序列上的跟蹤結果對比Fig.8 Comparison of tracking results of various algorithms on partial sequences

（1）目標遮擋（OCC）是目標跟蹤中最常見的挑戰(zhàn)之一。在David、Tiger2和Jogging的視頻序列中均發(fā)生了目標遮擋現(xiàn)象，在Jogging的第54和71幀中，本文方法、LDES、Auto track、SRDCF方法跟蹤到了目標，其他算法的跟蹤目標漂移到了遮擋物上面，導致跟蹤失敗。

（2）尺度變換（SV）是目標在運動過程中的由遠及近或由近及遠而產(chǎn)生的尺度大小變化的現(xiàn)象。在David的第411和第460幀中均發(fā)生了明顯的尺度大小變化，其中KCF和CSK沒有精確地預測到目標框的大小導致跟蹤發(fā)生了偏移，本文算法通過背景感知的方法在目標框的預測上展現(xiàn)了很好的效果。

（3）平面內(nèi)旋轉(zhuǎn)（IPR）是指跟蹤目標發(fā)生了旋轉(zhuǎn)等現(xiàn)象。在Singer2、Trellis、David、Tiger2的視頻序列中均發(fā)生了平面內(nèi)旋轉(zhuǎn)，其中Trellis的第408幀中，旋轉(zhuǎn)改變了跟蹤目標的特征，使提取目標特征的難度增加，其中CSK方法跟蹤失敗，KCF跟蹤發(fā)生了偏移。在Tiger2的第111幀中發(fā)生了快速運動加上平面內(nèi)的旋轉(zhuǎn)，DSST、KCF、CSK方法均跟蹤失敗。本文方法對前景和背景分別提取特征并聚類，能在目標發(fā)生旋轉(zhuǎn)時跟蹤結果仍然準確。

（4）目標形變（DEF）指的是目標表觀的不斷變化。在Singer2中，第336幀跟蹤目標發(fā)生了形變，SRDCF、CSK和ARCF算法由于目標的形變導致在跟蹤過程中發(fā)生偏移最終跟蹤失敗，本文算法能在目標形變過程中很好地適應目標表觀變化并及時進行模型更新。

（5）光照變化（IV）指的是目標區(qū)域的光照發(fā)生顯著變化。在Trellis的第158和321幀中發(fā)生了明顯的明暗對比，CSK、KCF在光照的影響下出現(xiàn)了不同程度的跟蹤漂移，本文算法在面對光照影響時仍然能夠精準跟蹤到目標。

4.4 定量分析

表2為本文算法和其他9種對比算法在OTB2013、OTB2015、DTB70上的3個公開數(shù)據(jù)集上的實驗數(shù)據(jù)匯總。本文算法在OTB2013數(shù)據(jù)集的51個視頻序列上的成功率僅次于最高的LDES算法，精確率也與最高的LDES算法相差0.08。在OTB2015數(shù)據(jù)集的100個視頻序列上，本文算法的成功率優(yōu)于其他算法，OTB2015的精確率較最高的BACF稍差。

表2 10種跟蹤算法屬性Table 2 Attributes of 10 tracking algorithms

在表3和表4中，本文詳細地列出了10種跟蹤算法在OTB2015數(shù)據(jù)集上各種屬性上的成功率和準確率得分。本文方法在光照變化（IV）的視頻序列上的成功率和準確率表現(xiàn)效果一般，但在平面內(nèi)旋轉(zhuǎn)（IPR）和平面外旋轉(zhuǎn)（OPR）上優(yōu)于其他同屬性算法，說明本文算法能很好地應對跟蹤目標的旋轉(zhuǎn)。由于本文算法引入了前景依存度概念，使跟蹤算法在尺度變換（SV）和低分辨率（LR）上也展現(xiàn)了很好的跟蹤效果。

表3 10種跟蹤算法在OTB2015上精確率得分Table 3 Accuracy scores of 10 tracking algorithms on OTB2015

表4 10種跟蹤算法在OTB2015上成功率得分Table 4 Success rate scores of 10 tracking algorithms on OTB2015

5 結束語

本文提出一種基于密度峰值聚類的全尺度相關濾波跟蹤方法，通過聚類模型代替圖像金字塔進行尺度預測，先使用單尺度相關濾波器對目標進行粗定位，再根據(jù)聚類模型對目標中的樣本點進行前景背景預測，以得到尺度置信度最高的預測框。在OTB2013、OTB2015和DTB70共三個數(shù)據(jù)集上進行的大量對比實驗，本文算法在BACF的基礎上提高了跟蹤速度，并且相較于BACF，本文方法的平均成功率和平均精確率有較大提升。下一步可以考慮引入深度特征以提高跟蹤精度與成功率，并且可以考慮結合卡爾曼濾波方法為搜索區(qū)域計算空間正則項，實現(xiàn)更好的跟蹤效果與魯棒性。