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

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

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

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

3(中航工業(yè)沈陽黎明航空發(fā)動機(集團)有限責任公司,沈陽 110043)

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

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

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

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

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

3(中航工業(yè)沈陽黎明航空發(fā)動機(集團)有限責任公司,沈陽 110043)

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

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

KCF跟蹤算法;ORB特征檢測;PROSAC特征點匹配;三維重建;運動軌跡記錄

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

1 KCF跟蹤算法

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

1.1 HOG特征

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

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

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

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

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

1.2 正則化最小二乘分類器

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

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

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

1.3 循環(huán)矩陣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 特征提取與匹配算法

2.1 ORB特征提取

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

2.2.1 O-FAST特征點檢測

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

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

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

2.1.2 rBRIEF特征描述

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

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

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

2.2 PROSAC特征點匹配

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

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

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

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

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

3 三維坐標記錄

3.1 雙目視覺測量模型

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

圖1 雙目視覺測量視差原理

雙目視覺視差深度信息計算公式:

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

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

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

簡化之后為:

因為兩張圖片對應(yīng)兩點在跟其相機焦距的延長線在空間交于同一點P,所以Ms是滿秩矩陣,公式(26)的方程有解.從而得到P的世界坐標.

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

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

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

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

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

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

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

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

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

圖4 系統(tǒng)測量的目標運行軌跡

5 結(jié)語

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

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邱茂林,馬頌德,李毅.計算機視覺中攝像機定標綜述.自動化學(xué)報,2000,26(1):43–55.

16王輝,肖建,嚴殊.關(guān)于模糊系統(tǒng)辨識近年來的研究與發(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;收到修改稿時間:2016-10-17

10.15888/j.cnki.csa.005780