侯志強 張 浪 余旺盛 許婉君

?

基于快速傅里葉變換的局部分塊視覺跟蹤算法

侯志強 張 浪*余旺盛 許婉君

(空軍工程大學(xué)信息與導(dǎo)航學(xué)院 西安 710077)

針對視覺跟蹤中目標表觀變化、局部遮擋、背景干擾等問題，該文提出一種基于快速傅里葉變換的局部分塊視覺跟蹤算法。通過建立目標分塊核嶺回歸模型并構(gòu)建循環(huán)結(jié)構(gòu)矩陣進行分塊窮搜索來提高跟蹤精度，利用快速傅里葉變換將時域運算變換到頻域運算提高跟蹤效率。首先，在包含目標的初始跟蹤區(qū)域建立目標分塊核嶺回歸模型；然后，提出通過構(gòu)造循環(huán)結(jié)構(gòu)矩陣進行分塊窮搜索，并構(gòu)建目標分塊在相鄰幀位置關(guān)系模型；最后，利用位置關(guān)系模型精確估計目標位置并進行分塊模型更新。實驗結(jié)果表明，該文算法不僅對目標表觀變化、局部遮擋以及背景干擾等問題的適應(yīng)能力有所增強，而且跟蹤實時性較好。

視覺跟蹤；核嶺回歸模型；快速傅里葉變換；分塊窮搜索；位置關(guān)系模型

1 引言

目標跟蹤問題是當前計算機視覺領(lǐng)域中的一個熱點問題，由于廣泛應(yīng)用于視頻監(jiān)控，圖像壓縮，3維重構(gòu)等領(lǐng)域，其受到越來越多學(xué)者的關(guān)注。目標在運動過程中表觀的不斷變化、局部遮擋以及復(fù)雜背景的干擾常常導(dǎo)致跟蹤失敗。因此，構(gòu)建合適的目標表示模型是決定跟蹤成功與否的關(guān)鍵環(huán)節(jié)。

Mean Shift算法[4,5]利用目標顏色直方圖特征構(gòu)建目標模型，由于忽略了目標的空間結(jié)構(gòu)信息，容易匹配到具有相似顏色直方圖特征的背景中去。文獻[6]采用修正的背景加權(quán)直方圖對目標建模，能降低背景的干擾，但在復(fù)雜背景中跟蹤效果不佳。多示例學(xué)習(xí)[7]利用目標正負樣本構(gòu)建目標的判別式模型，提高了算法對表觀變化及復(fù)雜背景的適應(yīng)性?；谘h(huán)結(jié)構(gòu)的檢測跟蹤法[8,9]提出利用循環(huán)結(jié)構(gòu)矩陣建立目標回歸跟蹤模型，但算法不能處理遮擋變化問題。近年來，基于局部分塊模型的跟蹤算法由于能很好地檢測和處理遮擋問題而成為研究熱點，局部分塊可以分為規(guī)則分塊和非規(guī)則分塊。文獻[10]提出的Fragments-based 分塊方法是最具代表性的規(guī)則分塊算法，但算法利用積分直方圖進行窮搜索容易受到背景的干擾。文獻[11-13]提高了分塊的自適應(yīng)能力，增強了算法對遮擋的處理能力。不規(guī)則分塊以超像素[14,15]最具有代表性，由于超像素能很好地保持目標結(jié)構(gòu)信息，跟蹤魯棒性較好。局部分塊模型通過分塊搜索提高了算法對目標變化的適應(yīng)性。然而，現(xiàn)有局部分塊跟蹤算法對目標表觀變化、局部遮擋及背景干擾等的適應(yīng)能力有限。

針對以上問題，本文受分塊跟蹤啟發(fā)提出一種基于快速傅里葉變換的局部分塊窮搜索視覺跟蹤算法，算法采用規(guī)則分塊，保持了目標的空間結(jié)構(gòu)信息，充分利用目標的表觀信息并構(gòu)建循環(huán)結(jié)構(gòu)矩陣建立分塊核嶺回歸模型，提高了算法對表觀變化、背景干擾等情況的適應(yīng)能力，通過求解目標分塊在相鄰幀位置關(guān)系模型有效剔除了分塊誤匹配，利用快速傅里葉變換將時域運算變換到頻域運算有效提高了跟蹤效率，實驗結(jié)果驗證了本文算法跟蹤精確性和實時性。

2 基于快速傅里葉變換的核嶺回歸模型

核嶺回歸(Kernel Ridge Regression, KRR)是一種以結(jié)構(gòu)風險最小化為學(xué)習(xí)準則，解決在原始樣本空間中不能用線性方法求解的非線性問題的算法，該算法具有高泛化能力。

2.1核嶺回歸

線性回歸是利用數(shù)理統(tǒng)計中的回歸分析，可以用來確定兩個或兩個以上變量之間映射關(guān)系的一種統(tǒng)計分析方法，輸出變量是輸入變量的線性組合：

對于不適定問題，最小二乘法的解是病態(tài)的，構(gòu)造式(2)所示代價函數(shù)：

定義變量：

模型解可重寫為

2.2 核空間的循環(huán)卷積

本節(jié)先介紹1維序列構(gòu)造循環(huán)結(jié)構(gòu)矩陣將時域運算轉(zhuǎn)換到頻域運算的原理，其結(jié)論可以推廣至2維序列。假設(shè)有兩個向量和，其卷積結(jié)果為一個+-1的向量：

于是，式(5)可由時域變換到頻域求解：

式(7)預(yù)測值為

同理，有

可以證明，式(5)式(7)可推廣到2維矩陣[9]。2維矩陣循環(huán)沿水平和垂直兩個方向進行，其示意圖1如圖所示。

2.3 循環(huán)窮搜索

圖1 構(gòu)造循環(huán)結(jié)構(gòu)示意圖

3 分塊模型的構(gòu)建

當前分塊方式可以分為規(guī)則分塊和非規(guī)則分塊，文獻[10]給出了一種簡單的規(guī)則分塊方式，本文采用的規(guī)則分塊，并對每個分塊分別建立核嶺回歸模型來對目標進行描述表示。圖2和圖3分別為文獻[10]和本文算法的分塊示意圖。

4 位置關(guān)系模型及模型更新

通過構(gòu)建的目標分塊模型進行分塊窮搜索，可以得到目標分塊在當前幀的位置，已知目標分塊在上一幀位置的情況下，通過構(gòu)建目標分塊在相鄰幀間位置點集的位置關(guān)系模型即可精確估計出目標位置。本文為方便表示，以六邊形頂點表示目標各分塊位置，六邊形中心表示目標中心位置，示意圖如圖4示。其中，和分別表示第幀圖像和第幀圖像的對應(yīng)分塊位置點集，為和分別為對應(yīng)目標中心位置，為分塊數(shù)。

本文選取目標分塊對應(yīng)位置計算位置平移，相鄰幀位置關(guān)系模型表示為

圖2 文獻[10]分塊方法 ?????? 圖3 本文算法目標分塊示意圖

圖4 目標分塊在相鄰幀位置關(guān)系模型

遍歷所有分塊的的位移量，保留滿足上述條件的分塊位移量并由此可以得到目標在當前幀的位置。同時，記錄所有分塊相鄰幀匹配關(guān)系，若不滿足約束條件，則可能發(fā)生目標表觀較大變化、局部遮擋或背景干擾等情況，因而不進行模型更新，否則，設(shè)置模型更新因子對分塊模型進行融合更新：

5 算法流程

基于FFT的局部分塊窮搜索算法如表1所示。

表1基于FFT的局部分塊窮搜索算法

輸入：圖像，初始目標位置，分塊數(shù)目。輸出：當前幀目標位置及分塊中心位置點集。如果k=1，則(1)根據(jù)輸入的初始條件對目標進行分塊，獲得目標分塊位置點集；(2)對目標各分塊構(gòu)造循環(huán)結(jié)構(gòu)矩陣，建立回歸模型，得到目標的分塊模型。如果k>1，則(1)根據(jù)輸入條件確定目標分塊的搜索區(qū)域；(2)利用已經(jīng)構(gòu)建的分塊模型，對各分塊進行模型學(xué)習(xí)，確定各分塊位置；(3)計算目標分塊的位置關(guān)系模型，精確估計出目標位置，并進行模型更新。

本文跟蹤算法流程圖如圖5所示。

圖5 本文算法跟蹤過程示意圖

6 實驗結(jié)果與分析

為驗證本文跟蹤算法的有效性，進行了大量實驗仿真。實驗中使用的分塊數(shù)目，每個分塊的局部窮搜索范圍為該分塊大小的倍，核嶺回歸模型正則化參數(shù)，高斯核方差，模型更新因子，模型更新因子取值區(qū)間是經(jīng)過大量實驗得到，在不同視頻需人為設(shè)定最佳值。

為了充分說明本文算法在處理目標表觀變化、背景干擾、局部遮擋及光照變化等方面的優(yōu)勢，本文有針對性地選取了9組具有挑戰(zhàn)性的測試視頻和4種對比算法：9組視頻及目標真實位置均來自文獻[3], 4種對比算法分別是：Frag[10], CBWH[6], MIL[7]和SPT[14]。為保證對比實驗的公平性，F(xiàn)rag和MIL算法跟蹤結(jié)果直接使用文獻[3]公布的公開結(jié)果，其余算法均進行了多次實驗并取最優(yōu)結(jié)果。所有實驗都在聯(lián)想CPU-E5300 @2.60 GHz, 3.25 GB內(nèi)存的臺式機進行，算法通過MATLAB2009a實現(xiàn)。9組視頻序列，4種算法的跟蹤對比結(jié)果如圖6所示。

圖6 跟蹤算法性能的定性比較

6.1定性對比

(1)局部遮擋目標跟蹤 局部遮擋使得跟蹤算法不能獲得足夠的目標信息而導(dǎo)致跟蹤偏差或丟失；本文選取了Faceocc1序列、Subway序列及Jogging序列來驗證本文算法對遮擋的適應(yīng)能力。MIL 算法和CBWH 算法對局部遮擋的適應(yīng)能力較差，跟蹤誤差較大；Frag算法、SPT算法以及本文算法都采用的了分塊模型來處理遮擋問題，但當目標被嚴重遮擋后，F(xiàn)rag算法和SPT算法均出現(xiàn)丟失或明顯偏差情況，而本文算法由于利用目標的表觀模型進行局部窮搜索，當目標再次出現(xiàn)時仍能成功跟蹤目標，如Jogging序列第61幀所示。

(2)背景干擾目標跟蹤 背景干擾是目標跟蹤中最常見的跟蹤問題，由于背景中具有與目標特征相似的背景物而導(dǎo)致跟蹤丟失或偏差；本文選取Basketball序列、Walking序列和Mountainbike序列來驗證本文算法與其他幾種對比算法適應(yīng)背景干擾的能力；當出現(xiàn)復(fù)雜背景干擾時，MIL算法丟失目標，F(xiàn)rag算法和CBWH算法都出現(xiàn)一定程度的跟蹤偏差；如Basketball序列472幀所示；SPT算法和本文算法均能較好適應(yīng)背景干擾問題，但SPT算法會由于跟蹤過程模型誤差的累積，最終出現(xiàn)一定程度的跟蹤誤差，本文算法具有更好的跟蹤目標。

(3)快速運動目標跟蹤 快速運動常常導(dǎo)致圖像模糊，使得跟蹤算法難以獲得目標的表觀信息而導(dǎo)致跟蹤丟失。如圖Boy序列266幀所示，當目標快速運動出現(xiàn)圖像模糊時， Frag算法、CBWH算法和SPT算法均出現(xiàn)目標丟失情況；MIL算法和本文算法均能成功跟蹤目標，但本文算法充分利用目標表觀信息建模,能更好適應(yīng)目標表觀變化。

(4)光照變化目標跟蹤 光照變化常常導(dǎo)致目標的顏色信息發(fā)生明顯變化，因而容易出現(xiàn)跟蹤丟失或偏差；本文選取Trellis序列和David序列來對比本文算法和其他算法對光照變化的適應(yīng)能力。當光照發(fā)生明顯的非線性變化時，F(xiàn)rag算法和MIL算法丟失跟蹤目標，CBWH亦存在較大跟蹤偏差，如Trellis序列363幀所示，當目標從較暗環(huán) 境移動到較亮環(huán)境時，SPT算法跟蹤丟失，如David序列221幀所示，而本文算法能較好成功跟蹤目標。

6.2定量分析

為衡量跟蹤算法的跟蹤性能，本文采用平均每幀運行時間(單位：s)、中心位置誤差(單位：像素)和跟蹤成功率來對本文算法和對比算法進行對比分析。平均每幀運行時間衡量跟蹤效率，值越小跟蹤效率越高。中心位置誤差和跟蹤成功率衡量跟蹤精度。誤差值越小跟蹤精度越好，成功率值越大跟蹤精度亦越好。

6.2.1跟蹤效率 表2所示為本文算法與對比算法平均每幀運行時間比較結(jié)果，其中粗體表示最優(yōu)算法，粗斜體表示次優(yōu)算法(下同)。可以看出，由于構(gòu)造循環(huán)結(jié)構(gòu)矩陣，利用快速傅里葉變換將時域運算轉(zhuǎn)換到頻域運算有效地提高了跟蹤效率，本文算法在所有測試序列中均具有最好的跟蹤實時性。

表2平均每幀運行時間(s)

序列Frag[10]CBWH[6]MIL[7]SPT[14]本文算法 Faceocc10.421.081.456.860.23 Subway0.310.271.185.130.09 Jogging0.410.371.396.730.11 Basketball0.460.521.325.210.12 Walking0.400.321.365.200.14 Mountainbike0.550.521.575.450.10 Boy0.380.361.215.020.13 Trellis0.330.861.416.330.17 David0.431.011.336.110.15 平均值0.410.651.365.780.14

6.2.2跟蹤精度

(a)中心位置誤差 圖7所示為本文算法與對比算法的中心位置誤差對比曲線圖，可以看出，F(xiàn)rag算法在Faceocc1序列具有較小的跟蹤誤差；CBWH在Trellis序列和Jogging等序列中跟蹤誤差相對較小且穩(wěn)定；MIL算法在Walking序列、Boy序列、Subway序列和David序列的跟蹤結(jié)果較為準確，SPT算法除在Boy序列和David序列跟蹤效果較差外，其余序列都取得了較好的跟蹤效果；本文算法在所有序列中都具有較小的中心位置誤差。

表3所示為目標中心位置平均誤差值比較結(jié)果，其中粗體表示最優(yōu)算法，粗斜體表示次優(yōu)算法?？梢钥闯?，F(xiàn)rag 算法在Faceocc1序列的具有最優(yōu)跟蹤結(jié)果，MIL算法在Boy序列和Walking序列取得次優(yōu)跟蹤結(jié)果，SPT算法在Basketball序列取得最優(yōu)跟蹤效果，在Subway序列和Trellis序列取得次優(yōu)跟蹤結(jié)果，本文算法在9組測試序列中取得7組最優(yōu)結(jié)果和2組次優(yōu)結(jié)果，在平均跟蹤誤差上取得最優(yōu)跟蹤結(jié)果。

表3目標中心位置平均誤差比較(像素)

序列Frag[10]CBWH[6]MIL[7]SPT[14]本文算法 Faceocc111.219.229.816.616.2 Subway15.713.57.55.94.3 Jogging37.46.8132.711.84.3 Basketball13.118.291.96.58.9 Walking9.516.16.49.36.0 Mountainbike106.813.763.213.212.1 Boy40.352.412.868.84.6 Trellis59.519.071.412.37.1 David82.323.617.035.110.2 平均值41.720.348.119.98.2

(b)跟蹤成功率 表4所示為跟蹤成功率比較結(jié)果。Frag 算法在Faceocc1序列取得很好的跟蹤結(jié)果，CBWH 在Jogging 序列取得不錯的跟蹤結(jié)果，MIL算法SPT 算法分別在幾組序列中取得較好跟蹤結(jié)果，其中SPT算法在Basketball序列和Faceocc1序列取得最優(yōu)跟蹤結(jié)果，在Trellis序列和Mountainbike序列具有次優(yōu)跟蹤結(jié)果，本文算法在9組測試序列中取得8組最優(yōu)結(jié)果和1組次優(yōu)結(jié)果，在平均跟蹤成功率上取得最優(yōu)結(jié)果。

6.3 分塊方式及與 Frag算法和SPT算法的對比分析

分塊方式分為規(guī)則分塊和非規(guī)則分塊，由于需要構(gòu)造循環(huán)結(jié)構(gòu)矩陣，以便利用快速傅里葉變換將時域運算變換到頻域運算，因此目標狀態(tài)需采用矩形框描述，故本文算法分塊方式采用與Frag算法類似的分塊方式，相比超像素，超像素分塊方法通過聚類能更好地保持目標局部特征，其缺點是聚類時間長，影響跟蹤的實時性。本文分塊方式雖未能很好保持目標局部特征，但是通過構(gòu)造循環(huán)結(jié)構(gòu)矩陣建立目標分塊核嶺回歸模型，本文算法取得了更好的跟蹤精度和跟蹤效率。

表4跟蹤成功率比較

序列Frag[10]CBWH[6]MIL[7]SPT[14]本文算法 Faceocc11.000.930.761.001.00 Subway0.560.680.820.770.98 Jogging0.580.970.170.870.98 Basketball0.700.830.270.970.85 Walking0.830.410.990.861.00 Mountainbike0.130.740.480.800.88 Boy0.470.510.730.151.00 Trellis0.390.650.240.870.99 David0.160.700.770.390.97 平均值0.540.710.580.740.96

實驗發(fā)現(xiàn)，本文算法相比Frag算法和SPT算法在跟蹤效率和跟蹤精度上具有一定優(yōu)勢；Frag算法采用規(guī)則分塊來對目標進行描述，保持了目標的空間結(jié)構(gòu)信息，能較好處理局部遮擋問題，但是對分塊進行搜索時，該算法使用積分直方圖進行窮搜索容易受到復(fù)雜背景的干擾而出現(xiàn)跟蹤丟失情況，如圖6(f)所示；SPT 算法通過聚類對目標進行非規(guī)則分塊，有效利用了目標的中層視覺線索，能較好處理局部遮擋和表觀變化等問題，但是算法需要建立在上一幀跟蹤結(jié)果具有一定精度且運動空間連續(xù)的基礎(chǔ)上，當目標快速運動導(dǎo)致圖像模糊或跳躍運動時，算法因不能有效分割目標而跟蹤失敗，如圖6(c)所示，同時，該算法由于需要對目標進行聚類分析，實時性較差，如表2所示。

本文算法采用規(guī)則分塊，保持了目標的空間結(jié)構(gòu)信息，并充分利用目標的表觀信息建立分塊核嶺回歸模型，通過構(gòu)造循環(huán)結(jié)構(gòu)矩陣進行分塊窮搜索并構(gòu)建目標分塊在相鄰幀位置關(guān)系模型能準確定位目標位置，提高了算法對目標表觀變化、背景干擾及光照變化的適應(yīng)能力，將時域運算轉(zhuǎn)換到頻域運算能有效提高跟蹤效率，實驗結(jié)果驗證了本文算法跟蹤精確性和實時性。

圖7 中心位置誤差比較(單位：像素)

7 結(jié)束語

在傳統(tǒng)分塊目標模型的基礎(chǔ)上，本文提出了一種基于快速傅里葉變換的局部分塊視覺跟蹤算法。算法建立目標的分塊核嶺回歸模型，不僅保持了目標的空間結(jié)構(gòu)信息，而且充分利用了目標的表觀信息，能有效處理表觀變化、局部遮擋、背景干擾等問題，同時通過構(gòu)建循環(huán)結(jié)構(gòu)矩陣進行分塊窮搜索并建立目標位置關(guān)系模型，提高了跟蹤精度和跟蹤效率。實驗結(jié)果表明，本文算法能較好處理目標表觀變化、遮擋、背景干擾等問題，取得較好的跟蹤精度和跟蹤效率。然而，本文算法未考慮目標的尺度和旋轉(zhuǎn)變化問題，下一步工作將考慮算法對目標尺度和旋轉(zhuǎn)變化的自適應(yīng)問題，以進一步提高跟蹤算法的魯棒性。

[1] Yang H X, Shao L, Zheng F,.. Recent advances and trends in visual tracking: a review[J]., 2011, 74(18): 3823-3831.

[2] Smeulders A W, Chu D M, Cucchiara R,.. Visual tracking :an experimental survey[J]., 2014, 36(7): 1442-1468.

[3] Wu Y, Lim J, and Yang M H. Online object tracking: a benchmark[C]. Proceedings of the Computer Vision and Pattern Recognition, Portland, United States, 2013: 2411-2418.

[4] Comaniciu D and Ramesh V. Kernel-based object tracking[J]., 2003, 25(5): 564-577.

[5] Collins R T. Mean-Shift blob tracking through scale space[C]. IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), Madison, United States,2003: 234-240.

[6] Ning J F, Zhang L,.. Robust mean shift tracking with corrected background-weighted histogram[J].,2012, 6(1): 62-69.

[7] Babenko B, Yang M H, and Belongie S. Robust object tracking with online multiple instance learning[J]., 2011, 33(8): 1619-1632.

[8] Henriques J F, Caseiro R, Martins P,.. Exploiting the circulant structure of tracking-by-detection with kernels[C]. Proceedings of European Conference on Computer Vision (ECCV),Florence, Italy, 2012: 702-715.

[9] Henriques J F,Caseiro R, Martins P,.. High-speed tracking with kernelized correlation filters[J]., 2015, 37(3): 583-596.

[10] Adam A, Rivlin E, and Shimshoni I. Robust fragments-based tracking using the integral histogram[C]. Proceedings of the Computer Vision and Pattern Recognition, New York, United States, 2006: 798-805.

[11] 董文會, 常發(fā)亮, 李天平. 融合顏色直方圖及SIFT特征的自適應(yīng)分塊目標跟蹤方法[J]. 電子與信息學(xué)報, 2013, 35(4): 770-776.

Dong W H, Chang F L, and Li T P. Adaptive fragments- based target tracking method fusing color histogram and SIFT features[J].&, 2013, 35(4): 770-776.

[12] Nejhum S, Ho J, and Yang M H. Online visual tracking with histograms and articulating blocks[J]., 2010, 114(8): 901-914.

[13] Yang F, Lu H C, and Chen Y W. Bag of feature tracking[C]. Proceedings of the International Conference on Pattern Recognition, Istanbul, Turkey, 2010: 153-156.

[14] Wang S, Lu H C, Yang F,.. Superpixel tracking[C]. Proceedings of the IEEE International Conference on Computer Vision, Barcelona, Spain, 2011: 1323-1330.

[15] Yang F, Lu H C, and Yang M H. Robust superpixel tracking[J]., 2014, 23(4): 1639-1651.

Local Patch Tracking Algorithm Based on Fast Fourier Transform

Hou Zhi-qiang Zhang Lang Yu Wang-sheng Xu Wan-jun

(,,710077,)

In order to solve the problems of appearance change, local occlusion and background distraction in the visual tracking, a local patch tracking algorithm based on Fast Fourier Transform(FFT)is proposed. The tracking precision can be improved by establishing object’s patch kernel ridge regression model and using patch exhaustive search based on circular structure matrix, and the efficiency can be improved by transforming time domains operation into frequency domains based on FFT. Firstly, patch kernel ridge regression model is constructed according to the initialized tracking area. Secondly, a patch exhaustive search method based on circular structure matrix is proposed, then the position model is constructed in adjoining frame. Finally, the position of the object is estimated accurately using the position model and the local patch model is updated.Experimental results indicate that the proposed algorithm not only can obtain a distinct improvement in coping with appearance change, local occlusion and background distraction, but also have high tracking efficiency.

Visual tracking; Kernel ridge regression model;Fast Fourier Transform (FFT); Patch exhaustive search; Position model

TP391.4

A

1009-5896(2015)10-2397-08

10.11999/JEIT150183

2015-02-02；改回日期：2015-06-03；

2015-07-06

張浪 zhanglangwy@126.com

國家自然科學(xué)基金(61175029, 61473309)和陜西省自然科學(xué)基金(2011JM8015)

The National Natural Science Foundation of China (61175029, 61473309); The Natural Science Foundation of Shaanxi Province (2011JM8015)

侯志強： 男，1973年生，教授，主要研究方向為圖像處理、計算機視覺和信息融合.

張 浪： 男，1990年生，碩士生，研究方向為視覺跟蹤.

余旺盛： 男，1985年生，講師，主要研究方向為圖像分割、視覺跟蹤.

許婉君： 女，1990年生，碩士生，研究方向為視覺跟蹤.