張乘龍,夏筱筠,柏 松,姚愷豐

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 沈陽計(jì)算技術(shù)研究所,沈陽110168)

3(中航工業(yè)沈陽黎明航空發(fā)動(dòng)機(jī)(集團(tuán))有限責(zé)任公司,沈陽 110043)

4(國家電網(wǎng)公司東北分部 國網(wǎng)東北電力調(diào)度中心,沈陽 110180)

基于KCF跟蹤算法的目標(biāo)軌跡記錄系統(tǒng)①

張乘龍1,2,夏筱筠2,柏 松3,姚愷豐4

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 沈陽計(jì)算技術(shù)研究所,沈陽110168)

3(中航工業(yè)沈陽黎明航空發(fā)動(dòng)機(jī)(集團(tuán))有限責(zé)任公司,沈陽 110043)

4(國家電網(wǎng)公司東北分部 國網(wǎng)東北電力調(diào)度中心,沈陽 110180)

為了確保跟蹤算法能夠?qū)崟r(shí)跟蹤上高速移動(dòng)的目標(biāo)并且記錄目標(biāo)的三維坐標(biāo).本系統(tǒng)使用了一種基于KCF(Kernelized Correlation Filters)的高速跟蹤算法來保證系統(tǒng)能夠跟蹤到移動(dòng)速度較快的目標(biāo).首先,使用KCF跟蹤算法來跟蹤目標(biāo);然后,利用ORB特征點(diǎn)檢測(cè)來計(jì)算目標(biāo)特征點(diǎn)從而找到多攝像機(jī)中對(duì)應(yīng)的點(diǎn),找到對(duì)應(yīng)點(diǎn)之后利用多攝像機(jī)的三維重建原理計(jì)算出每一幀中目標(biāo)物體的三維坐標(biāo)點(diǎn);最后,用多項(xiàng)式對(duì)每一幀運(yùn)動(dòng)軌跡的離散點(diǎn)進(jìn)行擬合得到最終的運(yùn)行軌跡.實(shí)驗(yàn)結(jié)果證明該算法能夠有效跟蹤目標(biāo),整個(gè)系統(tǒng)能夠滿足實(shí)際的需求.

KCF跟蹤算法;ORB特征檢測(cè);PROSAC特征點(diǎn)匹配;三維重建;運(yùn)動(dòng)軌跡記錄

目標(biāo)的跟蹤是計(jì)算機(jī)視覺的一個(gè)重要研究領(lǐng)域.隨著科技的發(fā)展,目標(biāo)跟蹤以及目標(biāo)軌跡記錄在交通監(jiān)控、行人流量、天文觀測(cè)、導(dǎo)航制導(dǎo)、武器裝備的研發(fā)等領(lǐng)域有著很實(shí)用的價(jià)值.針對(duì)目標(biāo)跟蹤,國內(nèi)外大量學(xué)者做了很多工作:注重邊跟蹤邊學(xué)習(xí)目標(biāo)特性的TLD跟蹤算法[1];基于壓縮感知的跟蹤算法CT跟蹤算法[2]等.這些算法幾乎已經(jīng)能夠達(dá)到實(shí)時(shí)跟蹤的目的.不過在一些領(lǐng)域,例如飛行器的研發(fā)領(lǐng)域,或者對(duì)目標(biāo)跟蹤實(shí)時(shí)性要求較高的領(lǐng)域中.由于目標(biāo)速度較快,或者實(shí)時(shí)性要求較高,那些傳統(tǒng)傳統(tǒng)的跟蹤方法不能夠達(dá)到實(shí)時(shí)跟蹤的目的.針對(duì)以往跟蹤系統(tǒng)不能跟跟蹤快速移動(dòng)的目標(biāo)或者系統(tǒng)本身實(shí)時(shí)性不夠好等問題本系統(tǒng)提出采用KCF[3]高速跟蹤算法來跟蹤目標(biāo),最終達(dá)到記錄目標(biāo)軌跡的目的.KCF跟蹤算法是一種新型的高速跟蹤算法.通過構(gòu)建目標(biāo)與背景之間的分類器來判別目標(biāo),是一種具有快速訓(xùn)練、快速檢測(cè)等特性的高速算法.因此,在實(shí)時(shí)性要求較高或目標(biāo)移動(dòng)速度較快的跟蹤算法應(yīng)用中,具有廣闊的前景.本文利用核相關(guān)濾波器計(jì)算量較小、實(shí)時(shí)性較好的特性將其應(yīng)用在實(shí)時(shí)的目標(biāo)移動(dòng)跟蹤里,取得了比較理想的效果.

1 KCF跟蹤算法

核相關(guān)濾波器跟蹤算法的核心思想是將跟蹤目標(biāo)區(qū)域進(jìn)行循環(huán)移位,以此構(gòu)造大量的樣本來訓(xùn)練分類器.通過分類器來計(jì)算候選區(qū)域與跟蹤目標(biāo)的相似程度,選取相似度最大的候選區(qū)域?yàn)樾碌母櫮繕?biāo),同時(shí)利用離散傅里葉變換降低分類器訓(xùn)練和檢測(cè)過程中的運(yùn)算量[3].

1.1 HOG特征

HOG(Histogram of Oriented Gradient,HOG)即梯度方向直方圖特征,是用于在計(jì)算機(jī)視覺和圖像處理領(lǐng)域,目標(biāo)檢測(cè)的特征描述子,該項(xiàng)技術(shù)是計(jì)算圖像局部出現(xiàn)的方向梯度作為圖像特征[4].

HOG特征計(jì)算方法分成以下幾步:1)分割圖像,將目標(biāo)區(qū)域劃分成一定大小相連接的小區(qū)域,每個(gè)小區(qū)域稱為細(xì)胞(cell);2)計(jì)算每個(gè)區(qū)塊的方向梯度以及梯度的方向,在圖像中像素位置(x,y)的水平與豎直方向梯度定義為:

像素位置(x,y)的梯度值跟梯度方向的定義為:

3)根據(jù)cell(細(xì)胞)單元中的每一個(gè)像素點(diǎn)的梯度值跟梯度方向利用雙線性內(nèi)插法進(jìn)行加權(quán)計(jì)算,得出每個(gè)細(xì)胞中的梯度方向直方圖;4)把各個(gè)直方圖組合起來組成特征向量.

在實(shí)際過程中由于局部光照的變化,以及前景和背景對(duì)比度的變化,使得梯度強(qiáng)度的變化范圍非常大,通常需要對(duì)梯度強(qiáng)度做歸一化.

1.2 正則化最小二乘分類器

由于正則化最小二乘分類器模型具有實(shí)現(xiàn)簡(jiǎn)單訓(xùn)練速度較快等特性,因此,正則化最小二乘分類器經(jīng)常使用在一些實(shí)際項(xiàng)目中在一些實(shí)際問題中此模型的分類器效果可以跟SVM分類器相同[5].

正則化最小二乘分類器訓(xùn)練的目標(biāo)就是用過樣本x訓(xùn)練得出一個(gè)使得正則化風(fēng)險(xiǎn)最小:

其中的λ為控制過擬合的參數(shù),由于這個(gè)公式是封閉式的,其解已經(jīng)被文章[5]給出:

1.3 循環(huán)矩陣

為了使用位移的樣本來訓(xùn)練最小二乘分類器,我們可以使用循環(huán)矩陣.假設(shè)C(x)是一個(gè)n×n的矩陣,則它可以通過一個(gè)1*n的向量的循環(huán)移位獲得,則有:

所有的循環(huán)矩陣都可以對(duì)角化,并且可以由向量x的離散傅里葉變換(Discrete Fourier Transform,DFT)轉(zhuǎn)換[6],其過程可以寫成以下公式:

其中F是不依賴于x的常數(shù)矩陣,?x是向量x的離散傅里葉變換.等式(6)表示了普通循環(huán)矩陣的特征分解,其中的常數(shù)矩陣F代表離散傅里葉變換的常數(shù)矩陣,并且通過這個(gè)矩陣我們能夠計(jì)算任意輸入的向量的離散傅里葉變換,公式為:

由于循環(huán)矩陣有這些的性質(zhì)[6,7],我們可以在核相關(guān)濾波器中使用它,從而大大提高算法的速度.

1.4 利用循環(huán)矩陣的最小二乘分類器

在跟蹤過程中利用循環(huán)矩陣的性質(zhì),在對(duì)分類器進(jìn)行訓(xùn)練時(shí),KCF算法利用目標(biāo)的基本樣本作為正樣本,對(duì)基本樣本循環(huán)位移之后的樣本為負(fù)樣本.只需對(duì)基樣本進(jìn)行計(jì)算,速度比較快.由等式(6)可以得出:

由于對(duì)角矩陣是對(duì)稱的,對(duì)其進(jìn)行埃爾米特轉(zhuǎn)換就會(huì)剩下復(fù)共軛.另外由于F的特性,我們可以得到HF F=I,這樣我們就可以把公式(8)轉(zhuǎn)換為:

由于操作在對(duì)角矩陣上,公式(8)可以寫成:

將公式(10)帶入公式(4)我們可以得出線性回歸的權(quán)值w的變換形式[3]:

這樣我們可以將最小二乘分類器的訓(xùn)練時(shí)間復(fù)雜度從原本的矩陣求逆運(yùn)算轉(zhuǎn)換為矩陣的相對(duì)元素相乘與離散傅里葉變換[3].

1.5 非線性回歸的核相關(guān)濾波器

我們可以采用核函數(shù)將輸入的向量x映射到特征空間φ(x)中,則可以把公式(3)的解表示為輸入的線性組合[8],系數(shù)為α:

通過文獻(xiàn)[5]我們可以得到公式(12)中的α變?yōu)?

其中Kij是核矩陣K的第一行,k?ij表示Kij的離散傅里葉變換[3].

1.6 核相關(guān)濾波器的響應(yīng)

當(dāng)我們訓(xùn)練好分類器之后,將新的一幀里的圖像特征輸入分類器,來判斷目標(biāo)位置.這樣,分類器的相應(yīng)結(jié)合之前的公式,我們可以得到:

2 特征提取與匹配算法

2.1 ORB特征提取

OBR(Oriented FAST and Rotated BRIEF)特征提取算法是進(jìn)年提出的一種改進(jìn)的新型算法.其特點(diǎn)是使用o-FAST特征點(diǎn)提取算法和rBRIEF特征值描述子. ORB算法運(yùn)用灰度質(zhì)心法在FAST特征點(diǎn)檢測(cè)的基礎(chǔ)上加上了方向檢測(cè),又通過在BRIEF描述子的點(diǎn)對(duì)集矩陣上加入旋轉(zhuǎn)矩陣變?yōu)閞BRIEF描述子,使得ORB算法加上了旋轉(zhuǎn)不變性,使算法具備了平移、旋轉(zhuǎn)、的不變性.該算法的特征提取速度相對(duì)于SIFT[10]等算法有著一個(gè)數(shù)量級(jí)以上的提高[11].

2.2.1 O-FAST特征點(diǎn)檢測(cè)

O-FAST相對(duì)FAST的主要改進(jìn)之處就在于加入了方向特性,這一特性會(huì)讓此特征描述算子具備旋轉(zhuǎn)不變性.使用的是 Rosin的灰度質(zhì)心法[12](intensity centroid).首先對(duì)一個(gè)圖像區(qū)域定義一個(gè)矩:

通過這個(gè)我們可以找到圖像區(qū)域的質(zhì)心.

在ORB中,這個(gè)圖像區(qū)域?yàn)镕AST關(guān)鍵點(diǎn)的鄰域,即以關(guān)鍵點(diǎn)O為圓心,以3個(gè)像素為半徑的圓形區(qū)域.即x,y的取值范圍是[3,3],且在該圓形區(qū)域內(nèi).這樣就可以得到一個(gè)向量用向量的方向θ表示FAST的關(guān)鍵的方向:

2.1.2 rBRIEF特征描述

ORB算子在特征描述部分采用的是基于BRIEF算子的改進(jìn)算法.BRIEF[13]特征描述子描述簡(jiǎn)單、占用存儲(chǔ)空間小、速度快,但缺陷也很明顯:不具備旋轉(zhuǎn)不變性,ORB中的rBRIEF特征描述子正是解決了這一點(diǎn).

在進(jìn)行特征描述前用積分圖像法對(duì)圖像進(jìn)行平滑處理.為了給BRIEF加入方向信息,首先需要將點(diǎn)的集合改寫為矩陣形式.對(duì)于一個(gè)n比特的點(diǎn)的集合定義一個(gè)矩陣S:

根據(jù)FAST特征點(diǎn)提取算法計(jì)算出來的方向角θ,求出這個(gè)點(diǎn)它對(duì)應(yīng)的旋轉(zhuǎn)矩陣Rq,這樣就得到了帶有方向特性的點(diǎn)的集合:這種新型的描述子具有更大的方差,描述特征的能力更強(qiáng).

2.2 PROSAC特征點(diǎn)匹配

PROSAC(Progressive Sample Consensus)[14]算法是一種全局匹配的算法,用來匹配不同圖片的對(duì)應(yīng)點(diǎn).對(duì)于N個(gè)采樣點(diǎn)的集合,可以表示為是UN中兩采樣點(diǎn).采樣點(diǎn)依照他們的相關(guān)性降序排列,其中相關(guān)性函數(shù)為q(u):

算法的采樣策略為現(xiàn)存概率更高的點(diǎn)被再次采樣的概率更大.設(shè)ui為正確的數(shù)據(jù)點(diǎn)代表采樣到該點(diǎn)的概率,可以有如下推斷:

記Un為有 n個(gè)高質(zhì)量?jī)?nèi)點(diǎn)的集合,記Tn為中包含Un中的高質(zhì)量點(diǎn)的平均數(shù)則:

這樣我們可以得到Tn的遞推關(guān)系式:

如果集合中內(nèi)點(diǎn)數(shù)量符合以下兩個(gè)條件時(shí),算法退出循環(huán)迭代:(1)若某次抽樣得到的內(nèi)點(diǎn)數(shù)量超過95%時(shí);(2)經(jīng)過k次抽樣內(nèi)點(diǎn)數(shù)量增長(zhǎng)小于5%時(shí).在本系統(tǒng)中k=5.這樣遞推一直到退出條件為止,Tn這個(gè)集合就只包含Un中高質(zhì)量的內(nèi)點(diǎn).

3 三維坐標(biāo)記錄

3.1 雙目視覺測(cè)量模型

雙目視覺測(cè)量模型是兩個(gè)相機(jī)在同一時(shí)刻進(jìn)行拍攝,這兩個(gè)相機(jī)獲得的相同目標(biāo)的不同角度的成像.然后通過這種相機(jī)成像的區(qū)別,利用雙目視覺中的視差原理,計(jì)算該目標(biāo)的三維空間坐標(biāo).如圖1所示.

圖1 雙目視覺測(cè)量視差原理

雙目視覺視差深度信息計(jì)算公式:

通常情況下雙目視覺測(cè)量系統(tǒng)可以分為兩種形式:一種是兩個(gè)相機(jī)的光軸平行狀態(tài)下的比較理想的理想模型;靈位一種則是兩個(gè)相機(jī)光軸不平行放置的測(cè)量模型.大多數(shù)情況下,光軸絕對(duì)平行是無法做到的.所以大多數(shù)雙目視覺測(cè)量的應(yīng)用中,用的是不平行放置的模型,而是利用了相機(jī)隨意擺放的模型,例如圖2所示.

圖2 雙目視覺系統(tǒng)

其中矩陣M為相機(jī)標(biāo)定后的已知數(shù),這樣我們聯(lián)立公式(25)的1r跟r2,計(jì)算出三維空間中的點(diǎn)跟兩張圖片中投影的點(diǎn)的關(guān)系:

簡(jiǎn)化之后為:

因?yàn)閮蓮垐D片對(duì)應(yīng)兩點(diǎn)在跟其相機(jī)焦距的延長(zhǎng)線在空間交于同一點(diǎn)P,所以Ms是滿秩矩陣,公式(26)的方程有解.從而得到P的世界坐標(biāo).

4 算法實(shí)例與結(jié)果

程序使用VS2013跟OPENCV2.4.9開源庫編寫,背景復(fù)雜而且有擾動(dòng).系統(tǒng)首先由使用了高斯背景模型來檢測(cè)前景物體.當(dāng)物體出現(xiàn)在攝像頭中以后,對(duì)目標(biāo)進(jìn)行特征的提取.根據(jù)目標(biāo)的HOG特征,使用KCF跟蹤算法跟蹤進(jìn)入雙目攝像機(jī)視野范圍的物體.使用 HOG特征的 KCF算法是在 CSK(Circulant Structure with Kernels)算法上擴(kuò)展出來的.使用了HOG特征并且將CSK算法擴(kuò)展到多通道并行.這樣使得KCF算法計(jì)算速變快,適合跟蹤快速目標(biāo),其中分類器核函數(shù)使用了作者默認(rèn)的高斯核函數(shù).表1為系統(tǒng)中使用KCF跟蹤算法平均耗時(shí)與其他跟蹤算法的比較.數(shù)據(jù)表明KCF跟蹤算法實(shí)時(shí)性較好能夠滿足我們的實(shí)際需求.

表1 系統(tǒng)中跟蹤算法在速度上的比較

由于KCF跟蹤算法使用了HOG特征,在一些時(shí)候HOG的塊劃分會(huì)使得跟蹤效果有一點(diǎn)不夠準(zhǔn)確.為了提高跟蹤效果的精確度,系統(tǒng)使用前5幀的位置以及速度跟梯度等信息來修正新一幀中KCF算法得到的的目標(biāo)位置,使得跟蹤結(jié)果更加精確.

識(shí)別并跟蹤目標(biāo)之后使用ORB特征提取提取出目標(biāo)特征點(diǎn),使用PROSAC來計(jì)算對(duì)應(yīng)的匹配點(diǎn).并且進(jìn)行初步的數(shù)據(jù)處理.SIFT等算法在尺度不變以及旋轉(zhuǎn)的情況下有很好的效果,但是由于系統(tǒng)使用雙目攝像頭,其成像是平行的而且距離相似目標(biāo)尺度變化較小.ORB特征提取算法不但能夠滿足我們系統(tǒng)的需求,而且速度很快,更適合系統(tǒng)使用.表2為系統(tǒng)中使用ORB特征提取以及PROSAC特征匹配花費(fèi)的平均時(shí)間跟其他算法的比較.數(shù)據(jù)表明ORB+PROSAC花費(fèi)的時(shí)間最少,而且效果能夠滿足我們的需求.

表2 系統(tǒng)中跟蹤算法在速度上的比較

然后根據(jù)雙目視覺系統(tǒng)的三維重建模型利用匹配過的應(yīng)點(diǎn)的坐標(biāo).得到每幀中離散的三維坐標(biāo)之后,系統(tǒng)需要對(duì)這些離散的三維坐標(biāo)進(jìn)行處理,去掉每一幀中對(duì)應(yīng)點(diǎn)的離群數(shù)據(jù).最后針對(duì)離散的坐標(biāo)數(shù)據(jù)進(jìn)行模糊辨識(shí)[16].得到目標(biāo)距離軌跡的平滑運(yùn)動(dòng)曲線.整個(gè)系統(tǒng)的處理流程如圖3所示.

圖3 系統(tǒng)的處理流程

實(shí)驗(yàn)結(jié)果為跟中系統(tǒng)計(jì)觀測(cè)后計(jì)算出來的目標(biāo)運(yùn)行軌跡.坐標(biāo)系以雙目攝像頭為原點(diǎn),三個(gè)坐標(biāo)軸分別為X,Y,Z軸.單位為mm.藍(lán)色為觀測(cè)數(shù)據(jù),紅色為擬合數(shù)據(jù).系統(tǒng)跟蹤記錄的目標(biāo)運(yùn)行軌跡結(jié)果為圖4所示.

圖4 系統(tǒng)測(cè)量的目標(biāo)運(yùn)行軌跡

5 結(jié)語

本文以為了滿足跟蹤并記錄快速移動(dòng)目標(biāo)的軌跡,采用KCF高速跟蹤算法對(duì)目標(biāo)進(jìn)行跟蹤;ORB特征檢測(cè)用來計(jì)算對(duì)應(yīng)點(diǎn)的三維坐標(biāo),最后使用模糊辨識(shí)將離散的三維坐標(biāo)進(jìn)行擬合得到了較好目標(biāo)運(yùn)行軌跡.實(shí)驗(yàn)結(jié)果表明,該方法能夠在滿足速度較快的目標(biāo)運(yùn)動(dòng)條件的跟蹤,并由分析錄像夠得到較理想的運(yùn)動(dòng)軌跡,說明此方法有效可行并能滿足實(shí)際要求的需要.

1 Kalal Z,Mikolajczyk K,Matas J.Tracking learning detection. IEEE Trans.on Pattern Analysis&Machine Intelligence,2012, 34(7):1409–1422.

2 Zhang K,Zhang L,Yang MH.Real-time compressive tracking.European Conference on Computer Vision. Springer-Verlag.2012.864–877.

3 Henriques JF,Rui C,Martins P,et al.High-speed tracking with kernelized correlation filters.IEEE Trans.on Pattern Analysis&Machine Intelligence,2015,37(3):583–596.

4 Dalal N,Triggs B.Histograms of oriented gradients for human detection.IEEE Conference on Computer Vision& Pattern Recognition.2013.886–893.

5 Rifkin R,Yeo G,Poggio T.Regularized least-squares classification.Acta Electronica Sinica,2003,(190):93–104.

6 Gray RM.Toeplitz And Circulant matrices:A review (foundations and trends(R) in communications and information theory).Now Publishers Inc,2006.

7 Davis PJ.Circulant Matrices:Second Edition.1994.

8 Sch?lkopf B,Smola A.Learning with Kernels:Support vector machines,regularization,optimization,and beyond.Journal of theAmerican Statistical Association,2011,16(3):781.

9 Henriques JF,Rui C,Martins P,et al.Exploiting the Circulant Structure of Tracking-by-Detection with Kernels.European Conference on Computer Vision.2012.702–715.

10 Lowe DG.Distinctive Image Features from Scale-Invariant Keypoints.International Journal of Computer Vision,2004, 60(2):91–110.

11 Rublee E,Rabaud V,Konolige K,et al.ORB:An efficient alternative to SIFT or SURF.2011 IEEE International Conference on Computer Vision(ICCV).2011.2564–2571.

12 Rosin PL.Measuring corner properties.Computer Vision and Image Understanding,1999,73(2):291–307.

13 Calonder M,Lepetit V,Strecha C,et al.BRIEF:Binary robust independent elementary features. European Conference on Computer Vision.2010.778–792.

14 Chum O,Matas J.Matching with PROSAC–Progressive sample consensus.IEEE Computer Society Conference on Computer VisionAnd Pattern Recognition.2005,1.220–226.

15邱茂林,馬頌德,李毅.計(jì)算機(jī)視覺中攝像機(jī)定標(biāo)綜述.自動(dòng)化學(xué)報(bào),2000,26(1):43–55.

16王輝,肖建,嚴(yán)殊.關(guān)于模糊系統(tǒng)辨識(shí)近年來的研究與發(fā)展.信息與控制,2004,33(4):445–450.

Target Track Recording System Based on Kernelized Correlation Filters TrackingAlgorithm

ZHANG Cheng-Long1,2,XIAXiao-Jun2,BAI Song3,YAO Kai-Feng4

1(University of ChineseAcademy of Sciences,Beijing 100049,China)
2(Shenyang Institute of Computing Technology,Shenyang 110168,China)
3(AVIC Shenyang Liming Aero-engine(Group)Co.Ltd.,Shenyang 110043,China)
4(North-East Branch of State Grid,Shenyang 110180,China)

In order to ensure that our tracking algorithm can real-time capture the fast-moving target and record its three-dimensional coordinates,the system uses a high-speed tracking algorithm based on Kernelized Correlation Filters (KCF).First,use KCF tracking algorithm to track the target.Second,use ORB feature point detection algorithm to calculate the target feature point.Then find out the corresponding point in Multi-Camera.After finding the corresponding points,use three-dimensional reconstruction theory of Multi-Camera to calculate the three-dimensional coordinates of the target object in each frame.Finally,using polynomial to fit the discrete points of each frame and then get the final trajectory.The experimental results show that this algorithm can track target efficiently and the whole system can meet actual requirements.

KCF tracking;ORB feature descriptor;matching with PROSAC;three-dimensional reconstruction;target track recording

2016-08-29;收到修改稿時(shí)間:2016-10-17

10.15888/j.cnki.csa.005780