劉延飛，何燕輝，張 薇，崔智高

火箭軍工程大學，西安 710025

1 引言

視覺目標跟蹤是計算機視覺領域中最具挑戰(zhàn)的課題之一，廣泛應用于視頻監(jiān)控、人機交互、智能汽車、醫(yī)療圖像等領域[1-2]。視覺目標跟蹤問題研究自20世紀80年代開始到現(xiàn)在經(jīng)歷30多年發(fā)展[2]，取得了驕人的成就，涌現(xiàn)出了大量的跟蹤算法。盡管如此，依然不存在一種能夠適應任意自然場景的跟蹤算法，光照變化、目標形變、遮擋、出視野等問題仍舊是影響跟蹤算法性能的主要因素，也是跟蹤領域需要突破的難點問題。

視覺目標跟蹤分類方法有多種，目前比較流行、公認度比較高的分類方法是根據(jù)目標外觀模型的表達策略，將跟蹤方法分為生成類方法和判別類方法。

生成類方法[3-8]就是在當前幀對目標區(qū)域建模，在下一幀尋找與模型最相似的區(qū)域就是預測目標的位置，比較經(jīng)典的有卡爾曼濾波、粒子濾波、Mean-Shift。

判別類方法[9-19]則是將跟蹤問題看作目標和背景的分類問題，此類方法同時提取目標和背景信息，增強了模板的判別力。比較經(jīng)典的算法有基于核化的結(jié)構(gòu)化輸出（Struck）算法[20]、跟蹤-學習-檢測（Tracking-Learning-Detection，TLD）算法[21]等。Struck是2012年之前性能最好的算法之一；TLD將檢測和學習融入到跟蹤的整個過程，使得其具備長期跟蹤的能力，由于每幀都需要進行檢測和學習，耗時比較大，極大地影響了其跟蹤的速度，盡管在實時性方面勉強能實現(xiàn)，但其引入學習和檢測機制的思想對之后的一些算法改進提供了有益借鑒。

判別類方法的最新發(fā)展方向就是相關(guān)濾波類方法。相關(guān)濾波類方法最主要的特點是算法復雜度低，運算速度快，滿足實時要求。最早將相關(guān)濾波器應用到跟蹤領域的是Bolme等人，他們提出一種最小輸出平方誤差和（Minimum Output Sum of Squared Error，MOSSE）相關(guān)濾波器跟蹤方法[22]，該算法只采用一個目標區(qū)域樣本圖像來訓練目標外觀模型，通過離散傅里葉變換將目標模型與候選區(qū)域之間的相似度計算轉(zhuǎn)換到頻域，顯著地提升了跟蹤算法的運行速度，跟蹤速度達到了615 frame/s，但跟蹤的精確度和成功率還有待進一步提高。Henriques等[23]提出了循環(huán)結(jié)構(gòu)的檢測跟蹤（CSK）算法，該算法通過對基準訓練樣本進行循環(huán)移位的方式構(gòu)造大量的訓練樣本，用于訓練分類器，同時，利用同樣的方式構(gòu)造大量的待測樣本，用于目標檢測過程。利用循環(huán)矩陣可以傅氏對角化的性質(zhì)將分類器訓練和目標檢測的計算轉(zhuǎn)換到頻域?qū)崿F(xiàn)了快速計算。Henriques等[24]在CSK的基礎上提出核相關(guān)濾波器（Kernel Correlation Filter）跟蹤算法，使用方向梯度直方圖（Histogram of Oriented Gradient，HOG）[25]特征代替原來的灰度值特征，將相關(guān)濾波器由單通道擴展到多通道，提升了跟蹤性能。

盡管KCF算法跟蹤性能得到了提升，但當目標受尺度變化、嚴重遮擋、相似目標干擾和出視野等因素影響時，KCF算法仍會出現(xiàn)目標丟失現(xiàn)象。一旦目標丟失，跟蹤器本身無法察覺，不具有目標丟失檢測的能力，這是KCF跟蹤算法固有的缺陷。目前不少學者針對這一問題提出了改進的措施，主要是對響應峰值進行檢測，用檢測的結(jié)果判斷目標是否丟失，檢測方法有求取局部極小值法[26]、設定閾值法[27]等。由于峰值的相對雜亂性，檢測方法都面臨兩個問題：一是計算的時間和空間復雜度；二是很難同時滿足高檢測成功率和低誤檢率要求。同時已有的檢測方法缺乏性能分析與評估。本文在KCF的基礎上，引入異常值檢測方法作為目標丟失檢測機制，對每幀的峰值進行檢測，發(fā)現(xiàn)異常峰值，則判定目標丟失，解決了KCF跟蹤器在跟蹤過程中目標丟失不能察覺的問題，同時還引入了檢測成功率和誤檢率作為本文方法的性能評估標準。

2 KCF跟蹤算法

KCF算法的主要思想是利用循環(huán)移位的方式構(gòu)造大量的訓練樣本和待測樣本。利用訓練樣本訓練一個核相關(guān)濾波分類器，然后通過分類器計算待測樣本的響應值，選取響應值最大的待測樣本為新的跟蹤目標，同時利用循環(huán)矩陣可以傅氏對角化的性質(zhì)，大大降低了分類器訓練和檢測過程中的運算量。

2.1 采集樣本

KCF跟蹤算法利用循環(huán)矩陣的思想，在目標區(qū)域設定的采樣窗口進行循環(huán)移位，產(chǎn)生大量的正負樣本，用以訓練分類器和檢測目標。設為基準樣本，利用置換矩陣P對基準樣本x進行循環(huán)移位，移位一次得到的樣本記為，所以經(jīng)過n次移位能得到n個樣本，樣本集合{Pux|u=0,1,…,n-1}，其中置換矩陣：

將得到的所有樣本按循環(huán)矩陣的定義組合成循環(huán)矩陣 X ，如式（2）：

式（2）中，x表示基準樣本，即為矩陣X的第一行。

因為循環(huán)矩陣都能夠在傅氏空間中使用離散傅里葉矩陣進行對角化，所以循環(huán)矩陣X可以化簡為：

其中，F(xiàn)為離散傅里葉變換矩陣；x?為向量x=[x1,x2,…,xn]T的離散傅里葉變換，也就是循環(huán)矩陣X的第一行的離散傅里葉變換；H表示矩陣共軛轉(zhuǎn)置。KCF跟蹤算法正是利用了循環(huán)矩陣能夠傅氏對角化避免了矩陣求逆，從而大大降低了運算量。

2.2 訓練分類器

對上式求導，并令導函數(shù)為0，可求得：

其中，φ(X)φ(X)T為核矩陣，用 K表示，那么就有 K=φ(X)φ(X)T。這里定義核函數(shù) κ(x,x′)=φ(x)φ(x′)T，因此核矩陣K中的各個元素表示為：

這里以Kij為元素的核矩陣K是循環(huán)矩陣，在文獻[24]的定理1中有說明，這里不做證明。因此有K=C(kxx)，其中kxx為K矩陣的第一行，將K矩陣傅氏對角化為 K=F diag(k?xx)FH，化簡式（5）得到：

2.3 目標檢測

分類器訓練完成后，在下一幀圖像的預測框內(nèi)采集基準待測樣本z，由基準樣本經(jīng)循環(huán)移位產(chǎn)生大量待測樣本，樣本集為{zj=pjz|0,1,…,n-1}，然后計算每個待測樣本的響應值，響應值最大的樣本所對應的位置即為目標所在的位置。計算響應的公式如下：

其中，κ(z,xi)為核函數(shù)。令Kz為訓練樣本與待測樣本之間的核空間的核矩陣，由文獻[24]中定理1可知Kz是循環(huán)矩陣，記Kz=C(kxz)。因此式（8）寫成矩陣形式為：

因為Kz是循環(huán)矩陣，根據(jù)循環(huán)矩陣的性質(zhì)，可將其傅氏對角化：

其中，kxz是 Kz矩陣的第一行。將式（10）代入式（9）化簡后得到：

3 目標丟失預警機制

傳統(tǒng)的KCF算法在跟蹤目標的時候，對于目標丟失的現(xiàn)象算法本身無法檢測與判斷，目標一旦丟失，跟蹤器依然會將背景信息作為目標繼續(xù)跟蹤。之所以會出現(xiàn)這種情況，原因就在于KCF跟蹤算法快速檢測過程中總是將待測樣本中響應值最大的作為目標，假設目標丟失了，不在采樣窗口內(nèi)或者在采樣窗口內(nèi)但被遮擋了，這種情況下所有待測樣本中依然會有一個最大響應值，即峰值，而顯然這個峰值所對應的位置并非真實目標所在的位置。

下面用一段視頻序列做實驗，采用OTB-2013[28]視頻序列集中的一段，序列名稱Jogging。視頻中目標由于遮擋導致跟蹤失敗，目標在第72幀后丟失。

圖1是視頻序列Jogging部分跟蹤結(jié)果及相應幀的待測樣本響應值分布，從圖中可以得出以下信息：

（1）目標跟蹤狀況良好時，峰值較大，例如第55幀，該幀的響應值分布圖中只有一個駝峰，而且非常尖銳，峰值為0.453 1。

（2）由于遮擋等因素的影響導致目標跟蹤狀況較差時，峰值較小，例如第68幀和第72幀，峰值分別是0.310 9、0.160 1。

（3）在目標由于遮擋等因素影響導致目標丟失的過程中，峰值會急劇下降，例如從第68幀到第72幀的峰值變化可以看出。

圖1 視頻序列部分跟蹤結(jié)果及響應值分布圖

（4）目標丟失后，跟蹤器會錯將背景信息作為目標繼續(xù)進行跟蹤，峰值會逐漸變大，例如第84幀，此時峰值是0.429 8。

由上述實驗可知目標丟失與響應峰值的變化有關(guān)聯(lián)，因此本文想利用每幀響應峰值的變化情況來評判目標是否丟失。圖2是利用視頻序列Jogging得到的跟蹤響應峰值序列圖，橫坐標表示幀數(shù)，縱坐標表示每幀對應的峰值。從圖中可以更直觀地看出，在目標發(fā)生跟丟的第72幀附近峰值出現(xiàn)了急劇下降，之后峰值逐漸升高（峰值之所以升高是跟蹤器將背景信息作為目標繼續(xù)進行跟蹤的原因?qū)е碌模?。因此可以將此處附近急劇下降的峰值視為異常值，利用異常值檢測原理對跟蹤過程中每幀的響應峰值進行檢測，如若發(fā)現(xiàn)峰值異常，則判斷目標丟失或即將丟失。

圖2 峰值序列圖

具體的檢測方法如下：

令Vpre為當前幀的響應峰值，集合{Vi|i=1,2,…,n}表示當前幀之前一段時期內(nèi)的峰值集合。

其中，u表示當前幀之前一段時期內(nèi)峰值的平均值；σ表示其標準差。如果當前幀的峰值距離均值u超過了λσ，那么這個值就可以被簡單地標記為一個異常值，此時可以判斷目標已丟失或即將丟失。

4 實驗與分析

為了驗證本文目標丟失檢測方法的有效性，本文選取OTB-2013[28]中20段視頻序列進行測試。視頻序列參數(shù)如表1所示。實驗平臺為Matlab R2012a，KCF目標跟蹤及跟蹤過程中得到的峰值數(shù)據(jù)的處理均使用Matlab R2012a平臺，實驗所用電腦配置：CPU是Intel Core i5，主頻2.0 GHz，內(nèi)存4 GB。實驗中，KCF算法參數(shù)保持不變，式（12）中n取50。

4.1 評估標準

為了能夠更加科學準確地評估本文目標丟失檢測方法的有效性，本文采用了檢測成功率和誤檢率作為評估標準。檢測成功率就是檢測到目標丟失的次數(shù)占實際目標丟失次數(shù)的百分比；所謂誤檢就是檢測算法錯誤地判斷目標丟失，而實際上目標并沒有丟失，誤檢率就是誤檢的次數(shù)占視頻總幀數(shù)的百分比。檢測到目標丟失的成功率當然是最重要的評估標準，但是如果單方面追求高成功率，而將檢測條件設置過于苛刻，勢必會導致誤檢率升高；相反，單方面追求低誤檢率，而將檢測條件設置過于寬泛，就會導致成功率降低。因此性能好的檢測方法既要求高成功率，又要確保低誤檢率。

表1 測試視頻參數(shù)

4.2 目標丟失與峰值變化相關(guān)性驗證實驗

為了驗證目標丟失與峰值變化的相關(guān)性具有普遍性，本文選取表1中的6段視頻進行了實驗，視頻序列名稱分別是Box、David3、Human4、Human6、Biker、Lemming。在KCF跟蹤過程中，6段視頻分別在第470幀、第133幀、第337幀、第360幀、第72幀、第970幀出現(xiàn)目標丟失。圖3是6段視頻響應峰值序列圖，紅色圓圈標記處為目標丟失處，從圖中可以看出目標丟失處附近峰值都出現(xiàn)了急劇下降現(xiàn)象。實驗進一步驗證了目標丟失與峰值變化的相關(guān)性。

4.3 目標丟失檢測算法性能測試

檢測條件設置過于苛刻，會導致誤檢率升高，而設置過于寬泛，又會導致檢測成功率下降。由式（12）可知：當λ取值越大，檢測條件就越寬泛，反之則越苛刻，因此，分別對λ=3，λ=3.5，λ=4時進行實驗。

將KCF跟蹤算法程序在表1中20段視頻序列上運行，得到20組響應峰值序列，再用Matlab分別對這20組峰值序列進行處理，得到如圖4～圖6所示的結(jié)果。圖4～圖6分別是λ=3，λ=3.5，λ=4時部分視頻序列的檢測結(jié)果。圖中黑色曲線表示峰值，紅色曲線表示峰值的平均值(u)，綠色曲線表示均值減去λ倍的標準差(u-λσ)，紅色矩形標記處表示出現(xiàn)誤檢的幀，紅色圓圈標記處表示實際目標丟失的處。從圖中可以看出，總體上黑色曲線在綠色曲線之上，同時也出現(xiàn)了這兩條曲線相交的情況，相交處的下一幀峰值即滿足式（12），根據(jù)目標丟失檢測方法原理，此時可以判定該幀目標丟失或即將丟失。

圖3 6段視頻集峰值序列圖

圖4 λ=3時部分視頻序列目標丟失檢測結(jié)果

根據(jù)實際的跟蹤結(jié)果，20段測試視頻共出現(xiàn)10次目標跟丟的情況，分別發(fā)生在視頻Biker的第72幀、視頻Box的第470幀、視頻Coke的第40幀、視頻David3的第133幀、視頻Girl2的第898幀、視頻Human4的第337幀、視頻Human6的第360幀、視頻Jogging的第72幀、視頻Lemming的第970幀、視頻Panda的第400幀。如果上述幀的峰值滿足式（12），則表示目標丟失預警成功；反之則表示預警失敗。如果除上述幀外其他幀的峰值滿足式（12），則表示誤檢。

通過實驗對比發(fā)現(xiàn)，λ取值越大，越容易發(fā)生預警失敗，例如在視頻Lemming的第970幀處，當λ取3和3.5時，目標丟失預警成功，取值4時，預警失??；λ取值越小，越容易發(fā)生誤檢，例如視頻David3和Boy，λ=3時誤檢次數(shù)分別是3、3，λ=3.5時誤檢次數(shù)分別是2、2，λ=4時誤檢次數(shù)分別是0、1；目標出現(xiàn)部分遮擋、尺度變化等情況時，容易發(fā)生誤檢，例如視頻FaceOcc1、Lemming和Suv，當λ=4時，仍出現(xiàn)了誤檢，誤檢次數(shù)分別是3、4、3。

圖5 λ=3.5時部分視頻序列目標丟失檢測結(jié)果

圖6 λ=4時部分視頻序列目標丟失檢測結(jié)果

表2是實驗得出的評估結(jié)果，當λ=4時，目標丟失預警效果最好，成功率最高，達到100%，誤檢率比較低，僅為0.202%。

表2 評估結(jié)果

根據(jù)實驗結(jié)果與分析情況，得出以下結(jié)論：

（1）在KCF目標跟蹤效果不理想的情況下易發(fā)生誤檢。

（2）在遮擋物多、攝像機抖動頻繁、尺度變化頻繁且明顯等情況下，可以適當?shù)卣{(diào)高λ的取值，從而放寬檢測條件，降低誤檢率。

5 結(jié)束語

針對目標丟失后KCF算法本身不能察覺，并且跟蹤器會將背景信息作為目標繼續(xù)進行跟蹤的問題，本文在KCF的基礎上，引入異常值檢測方法作為目標丟失預警機制，檢測方法時間空間復雜度低，不影響KCF目標跟蹤的實時性。實驗結(jié)果表明，本文方法在λ=3.5的情況下，能夠正確預警目標丟失，成功率達到100%，誤檢率僅為0.202%，具有較高的可靠性和魯棒性。實驗中僅使用了網(wǎng)絡上標準的測試視頻，方法在實際場景中的應用效果還需要進一步驗證。下一步需要結(jié)合目標丟失重檢測定位機制，檢驗本文方法的應用效果。