改進(jìn)的SURF 算法及其在目標(biāo)跟蹤中的應(yīng)用

劉少鵬，郎躍東，丁祝順

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

0 引 言

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

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

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

1 SURF 特征描述子介紹

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

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

然后，以特征點(diǎn)為中心，對(duì)dy 和dx(以主方向?yàn)榛鶞?zhǔn))進(jìn)行高斯加權(quán)計(jì)算(σ=3.3 s)。最后對(duì)每個(gè)子塊的小波響應(yīng)進(jìn)行統(tǒng)計(jì)，為了體現(xiàn)不同的極性，同時(shí)也對(duì)每個(gè)子塊小波響應(yīng)的絕對(duì)值進(jìn)行統(tǒng)計(jì)，得到每個(gè)子塊的特征矢量

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

由于共有4 ×4 個(gè)特征子塊，因此，特征描述子為一個(gè)4 ×4 ×4 =64 維的特征矢量，即為特征點(diǎn)的描述表達(dá)。

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

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

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

2 改進(jìn)的SURF 算法

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

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

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

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

V=［T1T2C1C2］.

T1，T2分別對(duì)應(yīng)圖3 中對(duì)圖像子塊運(yùn)用2 個(gè)三角算子得到的結(jié)果，C1，C2分別表示對(duì)圖3 中圖像子塊運(yùn)用對(duì)角線算子得到的運(yùn)算結(jié)果。

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

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

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

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

3 算法性能測(cè)試

3.1 匹配測(cè)試

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

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

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

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

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

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

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

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

對(duì)比圖8 中的匹配準(zhǔn)確率，可見兩者的匹配準(zhǔn)確率基本相當(dāng)。

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

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

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

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

3.2 計(jì)算復(fù)雜度測(cè)試

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

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

4 目標(biāo)跟蹤應(yīng)用實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)的SURF 特征描述子實(shí)際應(yīng)用效果，基于SURF 特征點(diǎn)匹配設(shè)計(jì)了目標(biāo)跟蹤策略，以驗(yàn)證改進(jìn)SURF 特征描述子在目標(biāo)跟蹤中的應(yīng)用效果。

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

圖11 改進(jìn)的SURF 特征描述子跟蹤試驗(yàn)1Fig 11 Tracking test 1 for improved SURF feature descriptor

圖12 改進(jìn)的SURF 特征描述子跟蹤試驗(yàn)2Fig 12 Tracking test 2 for improved SURF feature descriptor

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

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

5 結(jié)束語

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

［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］ 周志強(qiáng)，汪 渤.尺度不變特征在自主尋的電視制導(dǎo)中的應(yīng)用［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.