基于異常值檢測(cè)的KCF目標(biāo)丟失預(yù)警方法研究

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

火箭軍工程大學(xué)，西安 710025

1 引言

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

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

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

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

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

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

2 KCF跟蹤算法

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

2.1 采集樣本

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

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

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

因?yàn)檠h(huán)矩陣都能夠在傅氏空間中使用離散傅里葉矩陣進(jìn)行對(duì)角化，所以循環(huán)矩陣X可以化簡(jiǎn)為：

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

2.2 訓(xùn)練分類器

對(duì)上式求導(dǎo)，并令導(dǎo)函數(shù)為0，可求得：

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

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

2.3 目標(biāo)檢測(cè)

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

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

因?yàn)镵z是循環(huán)矩陣，根據(jù)循環(huán)矩陣的性質(zhì)，可將其傅氏對(duì)角化：

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

3 目標(biāo)丟失預(yù)警機(jī)制

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

下面用一段視頻序列做實(shí)驗(yàn)，采用OTB-2013[28]視頻序列集中的一段，序列名稱Jogging。視頻中目標(biāo)由于遮擋導(dǎo)致跟蹤失敗，目標(biāo)在第72幀后丟失。

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

（1）目標(biāo)跟蹤狀況良好時(shí)，峰值較大，例如第55幀，該幀的響應(yīng)值分布圖中只有一個(gè)駝峰，而且非常尖銳，峰值為0.453 1。

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

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

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

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

由上述實(shí)驗(yàn)可知目標(biāo)丟失與響應(yīng)峰值的變化有關(guān)聯(lián)，因此本文想利用每幀響應(yīng)峰值的變化情況來(lái)評(píng)判目標(biāo)是否丟失。圖2是利用視頻序列Jogging得到的跟蹤響應(yīng)峰值序列圖，橫坐標(biāo)表示幀數(shù)，縱坐標(biāo)表示每幀對(duì)應(yīng)的峰值。從圖中可以更直觀地看出，在目標(biāo)發(fā)生跟丟的第72幀附近峰值出現(xiàn)了急劇下降，之后峰值逐漸升高（峰值之所以升高是跟蹤器將背景信息作為目標(biāo)繼續(xù)進(jìn)行跟蹤的原因?qū)е碌模Ｒ虼丝梢詫⒋颂幐浇眲∠陆档姆逯狄暈楫惓Ｖ?，利用異常值檢測(cè)原理對(duì)跟蹤過(guò)程中每幀的響應(yīng)峰值進(jìn)行檢測(cè)，如若發(fā)現(xiàn)峰值異常，則判斷目標(biāo)丟失或即將丟失。

圖2 峰值序列圖

具體的檢測(cè)方法如下：

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

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

4 實(shí)驗(yàn)與分析

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

4.1 評(píng)估標(biāo)準(zhǔn)

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

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

4.2 目標(biāo)丟失與峰值變化相關(guān)性驗(yàn)證實(shí)驗(yàn)

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

4.3 目標(biāo)丟失檢測(cè)算法性能測(cè)試

檢測(cè)條件設(shè)置過(guò)于苛刻，會(huì)導(dǎo)致誤檢率升高，而設(shè)置過(guò)于寬泛，又會(huì)導(dǎo)致檢測(cè)成功率下降。由式（12）可知：當(dāng)λ取值越大，檢測(cè)條件就越寬泛，反之則越苛刻，因此，分別對(duì)λ=3，λ=3.5，λ=4時(shí)進(jìn)行實(shí)驗(yàn)。

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

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

圖4 λ=3時(shí)部分視頻序列目標(biāo)丟失檢測(cè)結(jié)果

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

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

圖5 λ=3.5時(shí)部分視頻序列目標(biāo)丟失檢測(cè)結(jié)果

圖6 λ=4時(shí)部分視頻序列目標(biāo)丟失檢測(cè)結(jié)果

表2是實(shí)驗(yàn)得出的評(píng)估結(jié)果，當(dāng)λ=4時(shí)，目標(biāo)丟失預(yù)警效果最好，成功率最高，達(dá)到100%，誤檢率比較低，僅為0.202%。

表2 評(píng)估結(jié)果

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

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

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

5 結(jié)束語(yǔ)

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