利用快速傅里葉變換的雙層搜索目標跟蹤算法

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

(空軍工程大學信息與導航學院,陜西西安 710077)

利用快速傅里葉變換的雙層搜索目標跟蹤算法

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

(空軍工程大學信息與導航學院,陜西西安 710077)

針對視覺跟蹤中目標表觀變化、尺度及旋轉變化問題,提出了利用快速傅里葉變換的雙層搜索目標跟蹤算法.算法在直角坐標系和對數極坐標系分別構建目標核嶺回歸模型并進行目標雙層搜索,同時利用快速傅里葉變換將時域運算轉換到頻域運算提高跟蹤效率.首先在直角坐標系中建立目標核嶺回歸模型并構建循環結構矩陣進行窮搜索得到目標中心位置;然后以目標中心位置為原點將跟蹤區域變換到對數極坐標系再次建立目標核嶺回歸模型,并窮搜索得到目標在對數極坐標系的平移量;最后依據搜索結果確定目標狀態并進行模型更新.實驗結果表明,這種算法不僅對表觀變化、尺度及旋轉變化具有較強的魯棒性,而且跟蹤實時性較好.

視覺跟蹤;雙層搜索;對數極坐標;快速傅里葉變換

隨著計算機視覺和多媒體技術的迅速發展,目標跟蹤問題受到越來越多學者的關注[1-3].目標運動過程中表觀、尺度及旋轉角度不斷變化是跟蹤失敗的重要原因,因此如何構建魯棒的表觀模型及實現目標的快速搜索是當前研究的熱點.Mean Shift算法[4]利用顏色直方圖特征構建目標模型,但容易匹配到具有相似顏色直方圖特征的背景中去;文獻[5]提出融合多種特征進行目標跟蹤,增強了對背景變化的適應性;文獻[6]提出利用局部分塊構建目標模型,能有效地解決遮擋問題;文獻[7]增強了目標分塊的自適應能力,能較好地適應目標形變問題;基于循環結構的檢測跟蹤法[8-9]提出利用循環結構矩陣建立目標回歸跟蹤模型,但算法對于復雜背景干擾及遮擋變化比較敏感.近年來,基于壓縮感知和稀疏子空間理論為構建目標模型提供了新思路.文獻[10]通過目標的正負樣本集建立目標的稀疏相似圖,然后利用該相似圖搜索與目標最相似的候選目標.文獻[11]將目標模型映射到一組由特征基張成的子空間,并利用稀疏理論對目標進行壓縮感知描述.

筆者提出在直角坐標系和對數極坐標系分別構建目標核嶺回歸模型,并利用快速傅里葉變換進行雙層搜索.利用目標表觀信息在直角坐標系構建表觀模型精確搜索目標位置,進而利用對數極坐標的尺度旋轉不變性確定目標的尺度和旋轉變化量.同時,算法通過構造循環結構矩陣將時域運算變換到頻域運算以提高跟蹤效率.實驗結果表明,該算法不僅能較好地適應表觀、尺度及旋轉變化,而且跟蹤實時性較好.

1　相關理論介紹

筆者采用在直角坐標系和對數極坐標系分別構建目標核嶺回歸模型,并利用快速傅里葉變換進行雙層搜索.先介紹核嶺回歸及對數極坐標理論.

1.1基于快速傅里葉變換的核嶺回歸

線性回歸是利用數理統計中的回歸分析,輸出變量是輸入變量的線性組合[8]:

其中,wTx是變量之間的內積;ζ表示預測值與真實值的偏差,一般服從標準正態分布,即ζ∝N(0,δ2).

通過構造代價函數并求解得到嶺回歸解:

其中,λ為正則化參數.

利用核技巧,可將線性回歸轉化為非線性回歸.將內積x xT用核矩陣K代替,得到核嶺回歸的解:

對于新的圖像樣本x′,根據模型可以預測該樣本屬于目標的響應:

類似一維序列構造循環結構矩陣原理,通過構造循環結構矩陣可將式(4)從時域變換到頻域求解[8]:

需要注意的是,二維矩陣循環沿水平和垂直兩個方向進行[9],其示意圖如圖1所示.

圖1　構造循環結構示意圖

由于一幅圖像對應一個像素矩陣,則對一個圖像塊x,通過對原始圖像進行水平及垂直方向循環移位,可得到一系列訓練樣本,從而構造循環結構矩陣并建立目標模型.筆者取圖像塊x為目標區域的M倍,定義y為與x等大小且滿足高斯分布的函數,y的每個取值對應不同訓練樣本的響應值,通過構造循環結構建立目標訓練樣本與對應響應值的映射關系,并利用快速傅里葉變換將模型構建從時域運算轉換到頻域運算.需注意,循環結構矩陣由原始圖像矩陣循環移位得到,其頻域運算可快速求得所有訓練樣本與響應值映射關系.在下一幀圖像塊x′中,利用目標模型在頻域進行模型學習,可快速實現對所有位置遍歷窮搜索.

1.2對數極坐標變換(LBP)

一幅圖像可以用直角坐標系(x,y)描述,也可以用對數極坐標(ξ,ψ)描述,它們的關系如下[12]:

圖像的對數極坐標表示具有重要性質,在直角坐標系下的尺度和旋轉變化可轉化為對數極坐標系下沿半徑和角度軸的平移變化.假設圖像在直角坐標系下以目標為中心變為原來的k倍、旋轉φ弧度時,則

可以看出,在對數極坐標系中,圖像的尺度變化表現為沿極半徑平移,旋轉變化表現為沿極角平移.

圖2　對數極坐標變換原理圖

2　跟蹤算法

算法實現分兩步:首先,在直角坐標系中,在包含目標的跟蹤區域建立目標核嶺回歸模型,構造循環結構矩陣進行窮搜索得到目標中心位置;然后,在對數極坐標系中,將以目標中心為原點的跟蹤區域變換到對數極坐標再次建立核嶺回歸模型,并利用對數極坐標系的尺度旋轉不變性估計目標的尺度和旋轉變化.

2.1直角坐標系目標窮搜索

在直角坐標系中,筆者采用基于快速傅里葉變換的目標窮搜索方法.由于利用目標表觀信息構建目標模型,算法對表觀變化、背景干擾等適應性較好.目標模型通過在第一幀圖像中手動標注獲得訓練樣本,然后利用上述介紹的核嶺回歸理論建立模型.目標的直角坐標系模型表示為

其中,(x,y)表示手動標注的目標中心位置.

在對目標進行搜索時,該算法將搜索區域設定為以上幀跟蹤結果為中心的4倍目標尺寸的區域,通過構建循環結構矩陣并將時域運算轉換到頻域運算進行快速窮搜索,得到目標的中心位置(x′,y′).

2.2對數極坐標系目標窮搜索

對數極坐標具有尺度旋轉不變性,但很少有好的模型能利用該性質來估計目標的尺度和旋轉變化.筆者將基于快速傅里葉變換的窮搜索方法引入對數極坐標域,通過搜索目標在對數極坐標系的平移量來精確估計尺度和旋轉變化.以目標中心位置為原點將跟蹤區域變換到對數極坐標并建立目標對數極坐標系模型:

其中,(i,j)表示目標對數極坐標區域中心位置.

通過對數極坐標窮搜索得到目標在對數極坐標系的平移(m,n),則其在直角坐標系的尺度和角度為

其中,Wt和θt分別為目標在t幀的尺度和角度,k1和k2分別為極半徑與極角的映射因子.

2.3模型更新

為適應目標變化及減少背景的干擾,采用線性加權機制來對目標模型進行更新.算法設置兩個模型更新因子α和β分別對直角坐標系模型wcar和對數極坐標系模型wlog進行實時更新:

其中,wt表示第t幀的直角坐標系模型wcar或對數極坐標系模型wlog,υ為對應的模型更新因子.

2.4算法流程

基于快速傅里葉變換的雙層搜索目標跟蹤算法如下.

輸入:圖像Ik,初始目標位置O0,初始跟蹤框Obb0.

輸出:當前幀目標狀態(Ok,Obbk).

如果k=1:

第1步 根據初始條件確定目標區域,并變換到對數極坐標系.

第2步 在直角坐標系和對數極坐標系分別建立目標核嶺回歸模型wcar和wlog.

如果k＞1:

第1步 在直角坐標系中,根據輸入條件確定搜索區域,構造循環結構矩陣窮搜索得目標中心位置Ok.

第2步 將以Ok為中心的目標區域變換到對數極坐標系,并利用模型wlog搜索目標的平移量(m,n).

第3步 根據上述搜索結果確定目標狀態(Ok,Obbk),并進行模型更新.

筆者提出算法的流程圖如圖3所示.

圖3　算法流程圖

3　實驗結果與分析

為驗證上述跟蹤算法的有效性,進行了大量的實驗仿真.實驗中設置直角坐標系目標窮搜索范圍為目標大小的4倍,對數極坐標系窮搜索范圍為目標大小的2倍,核嶺回歸模型正則化參數λ=0.01,高斯核方差δ=0.1,直角坐標系和對數極坐標系的模型更新因子為α(0.05≤α≤0.15)和β(0.05≤β≤0.15).α和β取值區間是經過大量實驗得到的,對不同視頻需人為設定最佳值.

為說明該算法在處理目標表觀變化、尺度及旋轉變化等的優勢,有針對性地選取了6組具有挑戰性的測試視頻和4種對比算法:除Sylvester-2008視頻、Cliffbar視頻及目標真實位置來自文獻[10]外,其余視頻及真實位置均來自文獻[3];4種對比算法分別為BHT[7],CSK[8],CT[11]和DSSM[10].為保證對比試驗的公平性,CSK算法和CT算法的跟蹤結果直接使用文獻[3]的公開結果,其余算法均為多次實驗取最優結果.所有實驗都在聯想CPU-E5300,2.60 GHz,3.25 GB內存的臺式機進行,算法通過MATLAB 2009a實現.

3.1定性對比

3.1.1Boy序列

“Boy序列”的跟蹤難點是快速運動、尺度和旋轉變化.如圖4(a)所示,當目標快速運動時,BHT算法出現跟蹤丟失,CT算法出現一定程度偏差;與CSK算法相比,雖都進行了窮搜索,筆者提出的算法通過雙層搜索具有更好的魯棒性,而CSK算法跟蹤丟失,如第602幀所示;DSSM算法和筆者提出的算法均能較好地跟蹤目標.

3.1.2Dog1序列

“Dog1序列”的跟蹤難點是目標表觀變化和明顯的尺度變化.如圖4(b)所示,當目標尺度發生明顯的變化時,BHT算法和CSK算法由于不能適應尺度變化而出現一定程度的偏差;DSSM算法雖然也具有尺度自適應能力,但也未能較好地適應尺度的明顯變化,如第1 001幀所示(圖左上角為當前幀數);筆者提出的算法通過建立核嶺回歸模型進行雙層窮搜索,不僅能較準確地搜索目標位置,而且能較好地適應目標尺度的變化.

3.1.3David2序列

“David2序列”的跟蹤難點是目標表觀變化、背景干擾及平面內的旋轉變化.如圖4(c)所示,由于背景的干擾,CT算法未能正確地區分目標和背景而導致跟蹤目標丟失;當目標進行連續的轉動時,BHT算法也丟失跟蹤目標;CSK算法、DSSM算法及筆者提出的跟蹤算法均能成功地跟蹤目標,但是筆者提出的算法通過雙層窮搜索能更好地適應目標的變化,跟蹤精度更高,如第485幀所示.

3.1.4Cliffbar序列

“Cliffbar序列”的跟蹤難點是目標表觀變化、復雜背景干擾及尺度和旋轉變化.如圖4(d)所示,由于目標表觀不斷變化及背景干擾,BHT算法、CT算法和CSK算法均丟失跟蹤目標,如第342幀所示;筆者提出的算法和DSSM算法均能成功地跟蹤目標,但后段序列目標尺度和旋轉的快速變化,使筆者提出的算法亦出現一定誤差.

3.1.5Sylvester-2008b序列

“Sylvester-2008b序列”的跟蹤難點是由平面外旋轉導致的表觀變化及光照變化.如圖4(e)所示,當目標在燈光下運動時,由于存在平面外的轉動,目標表觀姿態改變較大,CT算法跟蹤丟失,BHT算法、CSK算法及DSSM算法均出現一定程度的偏差,如第343幀所示;筆者提出的算法相對能更好地跟蹤目標.

3.1.6Singer序列

“Singer序列”的跟蹤難點是存在尺度變化及復雜背景干擾.如圖4(f)所示,由于復雜的背景干擾,BHT算法和CT算法均出現偏差;當目標尺度不斷縮小時,CSK算法雖能成功地跟蹤目標,但不能適應目標的尺度變化;DSSM算法和筆者提出的算法均能較好地跟蹤目標,但筆者提出的算法對目標的變化適應性更好.

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

3.2定量分析

為衡量跟蹤算法的跟蹤性能,筆者采用中心位置誤差、跟蹤成功率和平均每幀運行時間來對筆者提出的算法和對比算法進行對比分析.中心位置誤差和跟蹤成功率衡量跟蹤精度.誤差值越小,跟蹤精度越好;成功率值越大,跟蹤精度亦越好.平均每幀運行時間衡量跟蹤效率,時間值越小,跟蹤效率越高.

3.2.1中心位置誤差

圖5所示為中心位置誤差對比曲線.BHT算法在Sylvester-2008b序列跟蹤誤差相對較小,CT算法在David2序列和Cliffbar等序列跟蹤誤差較大.除了Boy序列和Cliffbar序列,CSK算法在其他序列跟蹤精度較高,這是由于算法通過構建循環結構矩陣進行目標窮搜索,能在一定程度適應目標表觀變化.DSSM算法通過正負樣本構建目標模型,增強了算法對表觀變化及背景干擾等的適應能力,除了Dog1序列,DSSM算法在其他序列跟蹤結果均較理想.筆者提出的算法分別在直角坐標系和對數極坐標系構建目標核嶺回歸模型,并進行雙層搜索,增強了算法對目標表觀變化、尺度和旋轉變化等的適應能力,因此在所有序列均取得較小的中心位置誤差.

圖5　中心位置誤差比較

表1中每種算法第1列所示為目標中心位置平均誤差值(CLE),其中粗正體表示最優算法,粗斜體表示次優算法.可以看出,筆者提出的算法除在Boy序列和Cliffbar序列取得次優跟蹤結果外,在其他視頻序列均取得最優跟蹤結果,具有最優的平均跟蹤誤差值.

表1　中心位置誤差和跟蹤成功率比較

3.2.2跟蹤成功率

表1中每種算法第2列所示為跟蹤成功率(SR).筆者提出的算法在所有測試視頻序列中取得4組最優結果和2組次優結果,在平均跟蹤成功率上取得最優結果.DSSM算法在Boy序列和Cliffbar序列取得最優結果,在Singer序列取得次優結果,在平均跟蹤成功率上取得次優結果.

表1中最后一行是算法平均每幀運行時間.筆者提出的算法和CSK算法都具有較高的跟蹤效率,主要是這兩種算法均利用快速傅里葉變換將時域運算轉換到頻域運算,雖然筆者提出的算法在直角坐標系與對數極坐標系分別構建目標模型進行雙層窮搜索增加了算法復雜度,但跟蹤效率較一般算法仍具有較大優勢.

3.3討 論

實驗發現,筆者提出的算法相比其他算法在跟蹤精度和跟蹤效率上具有一定優勢,但是在極坐標系的窮搜索模型是以在直角坐標系的目標定位為前提的.當目標定位誤差較大時,在極坐標系窮搜索得到的目標平移量將不準確,由此估計目標尺度和旋轉變化量將存在一定誤差,如圖4中Cliffbar序列第342幀和Sylvester-2008b序列的343幀所示,這是筆者提出的跟蹤算法的不足.

4　總 結

筆者提出了一種利用快速傅里葉變換的雙層窮搜索目標跟蹤算法,在直角坐標系和對數極坐標系分別構建目標核嶺回歸模型,并利用快速傅里葉變換進行雙層窮搜索.首先,在直角坐標系構建目標表觀模型并窮搜索得到目標中心位置,然后在對數極坐標系搜索目標平移量,進而利用對數極坐標的尺度旋轉不變性確定目標的尺度和旋轉變化量,同時,算法通過構造循環結構矩陣將時域運算變換到頻域運算,有效地提高了跟蹤效率.實驗結果表明,筆者提出的算法能較好地處理目標表觀變化、尺度及旋轉變化等問題,取得較好的跟蹤精度和跟蹤效率.需要指出的是,筆者提出算法的跟蹤精度對直角坐標系目標位置定位依賴度較大,當目標位置定位誤差較大時,對目標尺度和旋轉估計誤差較大,從而在模型更新時會引入較多的背景信息,這是筆者提出算法的不足.下一步工作將考慮通過跟蹤檢測判斷機制來避免上述問題發生,進一步提高算法的有效性和魯棒性.

[1]SMEULDERS A W,CHU D M,CUCCHIARA R,et al.Visual Tracking:an Experimental Survey[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(7):1442-1468.

[2]侯志強,韓崇昭.視覺跟蹤技術綜述[J].自動化學報,2006,32(4):603-617. HOU Zhiqiang,HAN Chongzhao.A Survey of Visual Tracking[J].Acta Automatica sinica,2006,32(4):603-617.

[3]WU Y,LIM J,YANG M H.Online Object Tracking:a Benchmark[C]//International Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society,2013:2411-2418.

[4]COLLINS R T.Mean-shift Blob Tracking through Scale Space[C]//Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition.Los Alamitos:IEEE Computer Society,2003:234-240.

[5]李遠征,盧朝陽,李靜.一種基于多特征融合的視頻目標跟蹤方法[J].西安電子科技大學學報,2012,39(4):1-6. LI Yuanzheng,LU Chaoyang,LI Jing.Robust Video Object Tracking Algorithm based on Multi-feature Fusion[J]. Journal of Xidian University,2012,39(4):1-6.

[6]ADAM A,RIVLIN E,SHIMSHONI I.Robust Fragments-based Tracking Using the Integral Histogram[C]//Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition.Los Alamitos:IEEE Computer Society,2006: 798-805.

[7]NEJHUM S M S,HO J,YANG M H.Online Visual Tracking with Histograms and Articulating Blocks[J].Computer Vision and Image Understanding,2010,114(8):901-914.

[8]HENRIQUES J F,CASEIRO R,MARTINS P,et al.Exploiting the Circulant Structure of Tracking-by-detection With Kernels[C]//Proceedings of European Conference on Computer Vision.Heidelberg:Springer Verlag,2012:702-715.

[9]HENRIQUES J F,CASEIRO R,MARTINS P,et al.High-speed Tracking with Kernelized Correlation Filters[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2015,37(3):583-596.

[10]ZHUANG B H,LU H C,XIAO Z Y,et al.Visual Tracking via Discriminative Sparse Similarity Map[J].IEEE Transactions on Image Processing,2014,23(4):1872-1881.

[11]ZHANG K,ZHANG L,YANG M H.Real-time Compressive Tracking[C]//12th European Conference on Computer Vision.Heidelberg:Springer-Verlag,2012:864-877.

[12]METTA G,GASTERATOS A,SANDINI G.Learning to Track Colored Objects with Log-polar Vision[J].Mechatronics,2004,14(9):989-1006.

(編輯:郭 華)

Two-level searching tracking algorithm based on fast Fourier transform

ZH ANG Lang,HOU Zhiqiang,YU Wangsheng,XU Wanjun
(Information and Navigation College,Air Force Engineering Univ.,Xi’an 710077,China)

In order to solve the problems of appearance change,scale and rotation change in the visual tracking,a two-level searching tracking algorithm based on Fast Fourier Transform(FFT)is proposed.It achieves two-level searching by establishing the object’s kernel ridge regression model in the Cartesian coordinates and log-polar coordinates,respectively,and the efficiency can be improved by transforming the operation into the frequency domain based on FFT.First,the kernel ridge regression model is constructed in the Cartesian coordinate and the object’s center position is obtained by the exhaustive search method based on the circular structure matrix.Then,it transforms the object area to the log-polar coordinates and searches the shift using the kernel ridge regression model in the log-polar coordinates.Finally,the object’s state is calculated according to the searching results and the object’s model is updated.Experimental results indicate that the proposed algorithm not only can obtain a distinct improvement in coping with the appearance change,scale and rotation change,but also have a high tracking efficiency.

visual tracking;two-level searching;log-polar coordinate;fast Fourier transform

TP391

A

1001-2400(2016)05-0153-07

10.3969/j.issn.1001-2400.2016.05.027

2015-07-21 網絡出版時間:2015-12-10

國家自然科學基金資助項目(61175029,61473309);陜西省自然科學基金資助項目(2011JM8015,2015JM6269)

張 浪(1990-),男,空軍工程大學碩士研究生,E-mail:zhanglangwy@126.com.

網絡出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.054.html