改進的SURF 算法及其在目標跟蹤中的應用

劉少鵬，郎躍東，丁祝順

(北京航天控制儀器研究所，北京100039)

0 引 言

基于局部不變特征匹配的目標跟蹤算法得到了廣泛研究。作為性能最好的局部不變特征之一，SURF 特征描述子應用在目標跟蹤中也獲得了良好的效果［1～3］。

與 GLOH，SIFT［4，5］等經(jīng)典局部不變特征描述子相比較，SURF 具有區(qū)分度好，運算速度快等優(yōu)點。但是在描述子生成階段，SURF［6］需要求取特征點鄰域像素的主方向，在區(qū)域內(nèi)以主方向為基準求取采樣點的Haar 小波響應，從而生成局部特征描述子，運算過程包含大量浮點運算，并且邏輯復雜，優(yōu)化難度大，基于SURF 的算法難于在嵌入式系統(tǒng)中實時實現(xiàn)。而在實際應用中目標跟蹤算法常常需要在嵌入式系統(tǒng)中實現(xiàn)，這也限制了SURF 特征描述子更廣泛的應用。

針對以上問題，本文利用三角和對角線特征對SURF特征描述子生成過程進行了改進，避免了對特征點鄰域像素的Haar 特征求取與Haar 小波向主方向旋轉(zhuǎn)的運算。所提算法保留了SURF 算子的旋轉(zhuǎn)、尺度不變性，對模糊圖像的特征點匹配性能更好，簡化了實現(xiàn)過程，有效提高了運算速度，可以滿足目標跟蹤算法的應用要求。

1 SURF 特征描述子介紹

基于SURF 的特征點［7］匹配主要包括3 個步驟:1)SURF 特征點檢測;2)SURF 特征描述子生成;3)前后幀特征描述子匹配與提純。本文對SURF 算法的改進主要體現(xiàn)在SURF 特征描述子生成方面。首先利用SURF 特征點檢測算法獲取SURF 特征點。在獲取圖像特征點后，求取特征點鄰域主方向，以特征點為中心，沿主方向構(gòu)建一個正方形區(qū)域，區(qū)域尺寸大小為20 s ×20 s，s 為特征點的尺度值。將此區(qū)域分為4 ×4 個子塊，每個子塊中有5 s×5 s 個像元，使用尺寸2 s 的Haar 小波濾波器對子塊內(nèi)的圖像進行小波響應計算，共進行25 次采樣計算，分別得到以主方向為基準的dx 和dy 響應。如圖1 所示。

圖1 特征描述子求取Fig 1 Calculation of SURF descriptor

然后，以特征點為中心，對dy 和dx(以主方向為基準)進行高斯加權(quán)計算(σ=3.3 s)。最后對每個子塊的小波響應進行統(tǒng)計，為了體現(xiàn)不同的極性，同時也對每個子塊小波響應的絕對值進行統(tǒng)計，得到每個子塊的特征矢量

V= ［∑dx，∑ | dx|，∑dy，∑ | dy|］.

由于共有4 ×4 個特征子塊，因此，特征描述子為一個4 ×4 ×4 =64 維的特征矢量，即為特征點的描述表達。

為了簡化運算，SURF 特征描述子在積分圖像中利用盒子算法求取水平和垂直方向的Haar 響應，然后根據(jù)主方向?qū)x 和dy 進行旋轉(zhuǎn)，即得到旋轉(zhuǎn)后的Haar 小波響應。

為了求得旋轉(zhuǎn)后的Haar 小波響應，需要將旋轉(zhuǎn)前的點坐標進行二維旋轉(zhuǎn)［3］。如圖2 所示，旋轉(zhuǎn)前圖像坐標為(l，k)，旋轉(zhuǎn)后坐標為(x，y)，旋轉(zhuǎn)后的坐標可以通過坐標旋轉(zhuǎn)公式得到

得到點(l，k)在旋轉(zhuǎn)后圖像中的坐標(x，y)后，利用積分圖像求得水平和垂直方向的 Haar 小波 dx'，dy'，對 dx'，dy'進行加權(quán)處理，并將dx'，dy'按照式(2)旋轉(zhuǎn)到特征點主方向，從而得到旋轉(zhuǎn)后的dx，dy。

2 改進的SURF 算法

針對SURF 算法需進行坐標旋轉(zhuǎn)和特征點計算優(yōu)化難度大等問題，本文利用三角特征和對角線特征設計了改進的SURF 特征描述子，利用子塊的三角特征和對角線特征取代圖1 所示子塊內(nèi)像素的Haar 小波特征，圖像子塊三角算子和對角線算子的實現(xiàn)如圖3 所示。

圖2 利用積分圖像求取Haar 響應示意圖Fig 2 Diagram of obtain Haar response using integral image

圖3 利用三角、對角線特征生成描述子Fig 3 SURF descriptor generation using triangle and diagonal featrues

與標準SURF 算法類似，三角算子和對角線算子實現(xiàn)同樣需要在每個圖像子塊內(nèi)取25 個采樣點，但是不對采樣點求Haar 小波，而是對25 個采樣點應用圖3 中所示三角算子和對角線算子來表示每個圖像子塊的局部特性，同樣每個圖像子塊可以得到一個四維的描述矢量

V=［T1T2C1C2］.

T1，T2分別對應圖3 中對圖像子塊運用2 個三角算子得到的結(jié)果，C1，C2分別表示對圖3 中圖像子塊運用對角線算子得到的運算結(jié)果。

以三角算子計算為例，求取過程如圖4 所示。圖4 左圖為旋轉(zhuǎn)后的圖像，如欲求取某子塊的三角特征，須首先利用式(1)獲取旋轉(zhuǎn)后的坐標值(x1，y1)和(x2，y2)，并根據(jù)(x1，y1)和(x2，y2)的坐標所屬區(qū)域分別乘以三角算子對應的正負系數(shù)，然后進行累加，即得到某子塊的一個三角算子描述。

如上所述，在計算圖像子塊的三角特征和對角線特征時，只需將圖像的灰度值乘以對應的系數(shù)后直接進行累加運算，圖像的灰度值為標量，不存在旋轉(zhuǎn)的問題，避免了x和y 方向的Haar 小波求解和旋轉(zhuǎn)操作，節(jié)約了大量浮點運算的運算量。

類似可以獲得另外一種三角算子和2 個對角線算子的特征表示。

圖4 圖像子塊三角特征求取示意圖Fig 4 Calculation diagram of triangle feature of image sub-block

3 算法性能測試

3.1 匹配測試

本文對SURF 和改進SURF 算法的匹配效果進行了測試;測試主要包括旋轉(zhuǎn)、模糊和縮放。

測試圖片如圖5 ～圖7 所示。每組圖中，第一張圖為基準圖，后續(xù)圖片為相對原圖發(fā)生旋轉(zhuǎn)、模糊以及縮放等變化的圖片。因為每組圖片較多，圖中所示僅為部分圖片，以作示意。圖8 ～圖10 為測試結(jié)果，其中，實線表示本文改進SURF 算法的測試結(jié)果。

圖5 旋轉(zhuǎn)測試圖片F(xiàn)ig 5 Images of rotation test

圖6 模糊測試圖片F(xiàn)ig 6 Images of blur test

圖7 尺度變化測試圖片F(xiàn)ig 7 Images of scale variation test

圖8 旋轉(zhuǎn)圖像匹配比較Fig 8 Matching comparison of rotation images

圖5 為對旋轉(zhuǎn)不變性進行測試所用的圖片，測試圖片旋轉(zhuǎn)角度分別為 10°，20°，直到 80°。從圖 8 中可見 2 種算法都出現(xiàn)了旋轉(zhuǎn)角度變大時，匹配點數(shù)反而增加的情況。這說明所謂旋轉(zhuǎn)不變并不是完全不受旋轉(zhuǎn)影響。通過對SURF 特征算子提取過程，以及隨圖片旋轉(zhuǎn)，特征點數(shù)量發(fā)生變化的情況進行分析可以發(fā)現(xiàn)，SURF 算法的旋轉(zhuǎn)不變性體現(xiàn)在描述子生成階段，而在 SURF 特征點［6，7］檢測階段仍然受到旋轉(zhuǎn)影響，即旋轉(zhuǎn)有可能影響某一像素點是否是SURF 特征點，同時也可能影響SURF 特征點的尺度。因此會造成隨旋轉(zhuǎn)角度不同，特征點匹配數(shù)目發(fā)生變化的情況，從而間接影響了旋轉(zhuǎn)圖像中特征點的匹配數(shù)目。

對比2 種算子的匹配點數(shù)，可看到改進SURF 的性能在旋轉(zhuǎn)角度小于40°時匹配效果和SURF 算法接近，但隨旋轉(zhuǎn)角進一步變大，改進SURF 的效果較經(jīng)典SURF 算法略差。這說明在相同匹配準則下，三角算子和對角線算子構(gòu)建的SURF 特征描述子對旋轉(zhuǎn)圖像的區(qū)分能力略低于經(jīng)典SURF 特征描述子。

對比圖8 中的匹配準確率，可見兩者的匹配準確率基本相當。

圖9 為對模糊圖片進行特征點匹配的匹配結(jié)果。可以看到，隨著模糊程度的加深，2 種特征描述子的匹配點數(shù)均發(fā)生下降，匹配準確率也發(fā)生下降。對比2 種特征描述子匹配的具體數(shù)據(jù)可見，改進的SURF 特征描述子不論在匹配點數(shù)和匹配精度方面均顯著高于經(jīng)典SURF 特征描述子。經(jīng)典SURF 特征描述子基于Haar 小波構(gòu)建，Haar 小波體現(xiàn)了像素的邊緣特征，而隨著模糊程度加深，圖像的邊緣特征逐漸變得不明顯。因此，經(jīng)典SURF 算子性能出現(xiàn)了下降，而改進的SURF 算子中的三角和對角線特征，主要體現(xiàn)了特征點鄰域子窗口的整體特征，受局部像素點邊緣模糊影響較小，性能下降程度要小于經(jīng)典SURF 算子。

圖10 為對尺度變化進行測試的結(jié)果，從圖中可以看到，改進的SURF 算子匹配點數(shù)略低于經(jīng)典算子，而匹配準確率則與經(jīng)典算子十分接近。這說明雖然改進的SURF 特征描述子對尺度變化特征的區(qū)分能力略有下降，但是仍然保留了尺度不變性的特點。

圖9 模糊圖像匹配比較Fig 9 Matching comparison of blur images

圖10 尺度變化圖像匹配比較Fig 10 Matching comparison of scale variation images

3.2 計算復雜度測試

本文對SURF 算子的改進主要目的是嵌入式應用，因此，將SURF 算子和改進的SURF 算子計算移植到主頻為1GHz 的TMS320C6416 處理器中實現(xiàn)，采用相同的優(yōu)化策略，以比較改進算法和經(jīng)典算法的運行速度。測試過程對相同視頻圖像求SURF 特征點，并計算特征點的特征描述子，實驗過程中將特征點數(shù)量設定為60 個。測試結(jié)果表明:改進SURF 算法實現(xiàn)了28f/s 的運算速度，而標準SURF算法運算速度約為19f/s。采用三角特征和對角特征對SURF 算法進行改進后，運算速度提高了約47%。

從3.1，3.2 小節(jié)的測試結(jié)果來看，改進SURF 特征描述子保留了經(jīng)典SURF 特征描述子的旋轉(zhuǎn)、尺度不變性，對模糊圖像魯棒性增強，運算速度有了顯著提升，比經(jīng)典SURF特征描述子更適合嵌入式系統(tǒng)應用。

4 目標跟蹤應用實驗

為了驗證改進的SURF 特征描述子實際應用效果，基于SURF 特征點匹配設計了目標跟蹤策略，以驗證改進SURF 特征描述子在目標跟蹤中的應用效果。

手動控制波門鎖定跟蹤區(qū)域，然后控制目標區(qū)域移動，移動包括平移、旋轉(zhuǎn)以及視角變化等。跟蹤過程視頻截圖如圖11、圖12 所示。

圖11 改進的SURF 特征描述子跟蹤試驗1Fig 11 Tracking test 1 for improved SURF feature descriptor

圖12 改進的SURF 特征描述子跟蹤試驗2Fig 12 Tracking test 2 for improved SURF feature descriptor

圖11 中目標在移動過程中發(fā)生了角度旋轉(zhuǎn)和比較嚴重的模糊，但是跟蹤波門始終鎖定在正確的位置上，實現(xiàn)了在目標快速移動中的跟蹤功能。充分證明了改進算子在圖像旋轉(zhuǎn)和模糊情況下的魯棒性。

圖12 中目標首先發(fā)生了角度旋轉(zhuǎn)，到第716 幀時和初始情況相比，目標旋轉(zhuǎn)角度、視角、尺度均發(fā)生了較大變化，第850 幀目標在尺度上又回到和第一幀接近的狀態(tài)，但是仍然存在旋轉(zhuǎn)角度的差異。整個過程波門始終鎖定在正確位置上，證明了算子在目標旋轉(zhuǎn)和尺度發(fā)生變化情況下的有效性。

5 結(jié)束語

針對SURF 特征描述子運算復雜，難于滿足嵌入式系統(tǒng)實時運算要求的不足，對SURF 特征描述子提取算法進行了改進。利用三角特征和對角線特征設計了新的SURF特征描述子。對2 種算子的匹配性能和運行速度進行了對比分析，充分討論了改進SURF 特征描述子的優(yōu)勢和不足。利用改進的SURF 特征描述子設計了目標跟蹤算法，通過實驗驗證了改進SURF 特征描述子在目標跟蹤應用中的有效性。

［1］ Miao Quan，Wang Guijin，Shi Chenbo.A new framework for online object tracking based on SURF［J］.Pattern Recognition Letters，2011，31:1564 －1571.

［2］ 周志強，汪 渤.尺度不變特征在自主尋的電視制導中的應用［J］.電光與控制，2009，16(9):6 －8.

［3］ 王永明，王貴錦.圖像局部不變特征與描述［M］.北京:國防工業(yè)出版社，2010.

［4］ Mikolajczyk K，Schmid C.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10):1615 －1630.

［5］ Lowe D G.Object recognition from local scale－invariant features［C］∥Proceedings of the International Conference on Computer Vision，Corfu，Greece，1999:1150 －1157.

［6］ Herbert Bay，Tinne Tuytelaars，Luc Van Gool.SURF:Speeded up robust features［C］∥Lecture Notes in Computer Science，Graze:ECCV，2006:404 － 417.

［7］ Herbert Bay，Andreas Ess，Tinne Tuytelaars，et al.Speed－up robust features(SURF)［J］.Computer Vision and Image Understanding，2008，110(3):346 －359.