周宇浩崴，應(yīng)忍冬，蔣樂天

上海交通大學電子工程系，上海 200240

SURF算法在小尺寸圖像拼接中參數(shù)配置的優(yōu)化

周宇浩崴，應(yīng)忍冬，蔣樂天

上海交通大學電子工程系，上海 200240

1 引言

圖像拼接分為直接拼接和融合技術(shù)，在目前融合技術(shù)中主要分為基于灰度信息和基于特征信息兩種模式。基于特征信息的圖像融合技術(shù)對圖像的分辨率、旋轉(zhuǎn)、平移、光照變化的敏感度較小，在處理復(fù)雜圖像拼接以及圖像受外界影響較大的情況下準確率較高。該技術(shù)的大致流程分為：圖像中特征的選?。ㄈ缣卣鼽c、邊緣特征等），圖像與圖像之間的特征匹配，通過匹配特征建立圖像與圖像之間的映射變化關(guān)系，并最終生成融合后的圖像。

SURF算法是2006年由Bay等人提出的基于特征信息的圖像拼接算法，它的提出是針對Lowe等人提出的SIFT算法數(shù)據(jù)量大，時間復(fù)雜度高，時效性差等問題。SURF算法通過對高斯拉普拉斯算子的歸一化近似來選取圖像中的特征點，然后通過DoH（Determinant of Hessian）簡化了SIFT算法中對特征點的描述，最后用最近鄰匹配得到兩幅圖像中的匹配特征點，利用RANSAC和最小二乘法擬合出圖像間的變換關(guān)系，獲得拼接圖像。SURF算法在保證了SIFT算法的魯棒性的基礎(chǔ)上，提高了運算效率，降低了時間復(fù)雜度，目前在實時圖像拼接領(lǐng)域被廣泛采用。

但由于SURF算法參數(shù)配置固定，對于不同應(yīng)用領(lǐng)域并不能完全發(fā)揮出算法優(yōu)秀的特性。為滿足不同拼接環(huán)境對實時性與拼接準確性的個性化要求，本文針對SURF算法的三類參數(shù)提出了優(yōu)化方法。這三類參數(shù)是：近似高斯拉普拉斯算子來選取特征點窗口濾波（Box Filter）方法中權(quán)值；生成描述子時，特征點子區(qū)域選取的范圍；通過DoH對所選取特征點子區(qū)域內(nèi)Haar小波變換的采樣空間范圍。基于目前主流的流媒體尺寸圖像，分析研究了這三方面配置對算法性能的影響，進而提出SURF算法參數(shù)選擇策略。該策略消除SURF算法參數(shù)固定的局限性，通過個性化的參數(shù)配置，在不同應(yīng)用領(lǐng)域達到算法的最優(yōu)化。

圖1 對積分圖像進行濾波，利用窗口濾波器近似離散化的高斯二階偏導(dǎo)

2 SURF算法

（1）特征點選取

SURF算法選擇了基于Hessian矩陣的檢測子，將Hessian矩陣行列式的局部極值作為特征點。算法先對高斯卷積核做二次偏導(dǎo)數(shù)，再利用偏導(dǎo)數(shù)構(gòu)成核卷積圖像。

對圖像I上的一點X(x，y)，在尺度空間σ上的Hessian矩陣表示為：

用Dxx、Dyy、Dxy代替Lxx、Lyy、Lxy，得到近似的Hessian矩陣Happrox，行列式為：

其中w為Hessian矩陣補償誤差，根據(jù)文獻[1]，w一般取值為0.9。

遍歷整幅圖像不同尺度空間，進行非極大值抑制，對每個點的Hessian行列式的值與其周圍3×3×3空間內(nèi)26的值進行比較，如果該值為27個點中值最大的即確定為特征點。然后在特征點附近用三維二次函數(shù)進行擬合，以函數(shù)極值作為特征點精確位置的描述。

但是由于利用窗口濾波器近似高斯二階導(dǎo)數(shù)與圖像卷積后，會導(dǎo)致圖像丟失一部分深度信息，根據(jù)文獻[2]提出的方法，通過改進窗口濾波器的權(quán)值來對丟失的深度信息進行彌補。下面，將在第3章對這種改進進行分析。

（2）特征點描述

SURF算法特征點描述子確定首先以特征點為中心構(gòu)造一個邊長為20s（s為特征點尺度）的窗口區(qū)域，使用主方向為y軸，并將窗口區(qū)域分為4×4個子區(qū)域，每個子區(qū)域中取5×5個采樣點，在每個采樣點分別求X和Y方向的Haar小波響應(yīng)，分別記為dx和dy。把每個子區(qū)域的dx和dy用高斯函數(shù)加權(quán)，再累積得到成描述子中的4維。而4×4個子區(qū)域里都有4維向量，因此一共得到一個4×4×4的64維向量，就是SURF算法的描述子。描述子構(gòu)造過程如圖2所示。

圖2 SURF算法生成64維描述子

SURF算法在描述子生成中涉及到兩個參數(shù)，是本文討論的重點：第一為特征點周圍子區(qū)域范圍的選擇，這將直接影響到SURF描述子的維數(shù)，SURF算法默認如上文所述，選取4×4的子區(qū)域，生成64維描述子。第二為在子區(qū)域內(nèi)采樣點范圍的選擇，如上文所述，SURF算法默認為在子區(qū)域選擇5×5個采樣點。

3 SURF算法中參數(shù)分析

實驗中圖像的分辨率為640×480，是目前主流流媒體如監(jiān)視攝像頭、網(wǎng)絡(luò)攝像頭等采用的分辨率。通過最近相鄰距離以及RANSAC算法實現(xiàn)兩幅圖像匹配，從特征點選取數(shù)量、特征點匹配數(shù)量、運算時間三個方面來對算法的窗口濾波器權(quán)值的選取，描述子生成的子區(qū)域范圍，即描述子維數(shù)以及子區(qū)域內(nèi)采樣空間的范圍三方面參數(shù)進行評估。在不同的應(yīng)用領(lǐng)域，對算法的準確性和時效性要求不同，如實時視頻拼接對實時性的要求比一般靜態(tài)圖像要高，為保證實時性，犧牲一部分準確性也是可行的。

圖3 窗口濾波器的權(quán)值的改進

3.1 窗口濾波器權(quán)值設(shè)置

根據(jù)文獻[2]中所提到的SURF算法窗口濾波器卷積后會導(dǎo)致圖像部分深度信息丟失的問題，提出豐富窗口濾波器的權(quán)值彌補損失的圖像深度信息，以增加特征點選取的精確性及算法的穩(wěn)定性，具體細節(jié)如圖3所示，在圖像上的淺灰色的區(qū)域以0.5權(quán)值標定，在中心區(qū)域以-1和+1權(quán)值標定。由于利用了積分圖像，所以圖像在和濾波器卷積的時間復(fù)雜度并沒有增加，而利用更加細化的窗口濾波器，達到了補充圖像中深度信息，精確特征點選取的目的。

用豐富后的窗口濾波器選取特征點，并與原SURF算法的結(jié)果進行對比，如圖4，同時引入了特征點匹配率的概念：

圖4 改進窗口濾波器權(quán)值后SURF算法特征點選取及匹配結(jié)果

特征點匹配率越大說明圖像匹配的效率越高，見表1。

表1 改進窗口濾波器后算法在特征點匹配上的比較

由表1可以看出，改進窗口濾波器權(quán)值后算法在特征點選取的數(shù)量上明顯少于SURF算法。這是由于豐富了窗口濾波器的權(quán)值以后，圖像各像素點與濾波器卷積時得出的結(jié)果較原算法平滑，各像素點間的Hessian行列式值差距較小，故在遍歷尺度空間內(nèi)的點取極大值時選出的點的數(shù)量有所減少，但是特征點匹配率較高，有效特征點數(shù)目較多，說明特征點選取的準確度有所提升。

3.2 SURF特征點子區(qū)域范圍選擇

選取特征點以后，在生成特征點描述子的過程中，標準的SURF算法采用的是在特征點周圍選取4×4的16個子區(qū)域，然后對每個子區(qū)域求取采樣點的小波變換的高斯加權(quán)，形成4維向量這樣整個16個子區(qū)域就構(gòu)成了該特征點的64維向量，即為SURF描述子，根據(jù)文獻[1]中的命名規(guī)范，稱為SURF-64描述子。

針對實時圖像處理領(lǐng)域圖像尺寸小，對速度要求高的特點，本文嘗試縮小特征點周圍子區(qū)域選擇的范圍，利用3×3的9個子區(qū)域生成36維描述子對特征點進行描述。比較了SURF-36描述子和傳統(tǒng)的SURF-64描述子在特征點匹配以及圖像拼接準確性上的差異，并相對于算法速度的提高，從描述子效率的角度進行分析。

在特征點選取上，為了保證準確性，仍采用原始SURF算法提供的窗口濾波器。由于特征點選取過程不變，所以兩種方法在特征點的數(shù)量上是完全一樣的。為了更清楚地比較描述子的效率，引入了匹配效率的概念：匹配效率越高，算法的效率越高。

從圖5以及表2中的結(jié)果可以看出，SURF-36在對640× 480級別的圖像處理上，匹配成功的特征點數(shù)量與SURF-64的差異很小，而在運算速度上提升卻非常顯著，減少了約25%，特征點匹配率上提高了近1/3?？梢钥闯?6維描述子在對圖像分辨率要求不高的情況下，完全可以代替64維描述子，而且在圖像拼接的速度上有很大提高。

圖5 SURF-36描述子特征點匹配結(jié)果

表2 SURF-64與SURF-36描述子比較

3.3 子區(qū)域中采樣點范圍選擇

本文嘗試在子區(qū)域中使用不同的采樣范圍，比較特征點匹配的準確率以及運行的速度。根據(jù)SURF算法，子區(qū)域的采樣范圍越大，計算出的子區(qū)域內(nèi)的描述特征向量的容錯性越佳，特征點描述子的魯棒性越好。對64維描述子的SURF算法和36維描述子的SURF算法分別進行了測試，從特征點子區(qū)域采樣范圍3×3到12×12進行，對兩幅640×480圖像之間特征點匹配時間以及匹配成功的特征點的數(shù)目進行比較，并繪制了曲線，如圖6所示。

圖6 SURF-36和SURF-64描述子，特征點子區(qū)域采樣范圍的特征點匹配曲線

從圖6中可以看出，隨著對特征點周圍子區(qū)域內(nèi)采樣點范圍的增加，運算時間增加較為平滑，接近線性，在之后采樣范圍9×9每增加一級采樣空間的范圍，兩幅圖像中匹配特征點數(shù)量幾乎不增加，而運算時間卻增加較多，這是由于圖像分辨率有限，子區(qū)域在9×9采樣時已經(jīng)接近極限，所以此時即使再增加采樣范圍，只是增加了無謂的運算量，子區(qū)域內(nèi)采樣點密度沒有實質(zhì)改變。從圖中可以直觀地看出5×5、6×6采樣范圍左右的效率較高，即圖中用紅色線段最長，說明匹配的數(shù)量時間比較高。在低采樣范圍時，SURF-36與SURF-64差異較大，這是因為SURF-64描述子選取特征點周圍的子區(qū)域較多，每個子區(qū)域?qū)ψ罱K描述子的貢獻比例較小，而SURF-36由于采樣的子區(qū)域只有9個，在子區(qū)域內(nèi)的低采樣范圍容易造成特征點描述子魯棒性降低，所以在低采樣范圍如3×3、4×4時，匹配的特征點數(shù)量較低。

對于分辨率較低的圖像，如本例采用的640×480的圖像，子區(qū)域內(nèi)采樣點范圍在5×5、6×6時效果較好；另外比較圖6中縱軸“拼接特征點數(shù)”，可以發(fā)現(xiàn)采樣點范圍在5×5、6×6以上時，SURF-36描述子對于SURF-64描述子在匹配成功的特征點數(shù)量上沒有明顯劣勢，而運算速度卻有明顯的提升。

4 SURF算法中參數(shù)配置的選擇策略

采用控制變量的方法，綜合比較以上三方面對SURF算法的參數(shù)配置在特征點匹配中的功效。圖4中所示的640×480的圖像分別對是否改進窗口濾波器、特征點子區(qū)域的范圍和子區(qū)域內(nèi)采樣范圍進行控制，得到表3中測試結(jié)果。其中子區(qū)域采樣范圍分別取9×9、5×5、3×3，由于在子區(qū)域采樣范圍在3×3時匹配特征點數(shù)量已經(jīng)很少，所以沒有對其進行改進窗口濾波器測試。

從表3中可以分析，可以通過比較表3中的“SURF-64 9×9”、“SURF-64 5×5”、“SURF-64 5×5方”、“SURF-36 5×5”四列，以SURF算法最初始的配置“SURF-64 5×5”為基準，單純從整個運算時間上考慮，擴大特征點子區(qū)域內(nèi)采樣范圍的時間代價最大，運算時間增加了45%；其次為特征點選取中使用改進權(quán)值后窗口濾波器，總運算增加了20%；而降低特征點描述子維數(shù)（從64到36）則使時間減少了約18%?？梢娮訁^(qū)域內(nèi)采樣范圍對整個算法的運算時間影響最大。

表3 控制變量法對SURF算法中不同參數(shù)方案的比較1）

從算法特征點匹配數(shù)量上考慮，特征點描述子維數(shù)越多，子區(qū)域內(nèi)采樣范圍越大，匹配的特征點數(shù)目越多，而改進后的窗口濾波器，對特征點的匹配數(shù)量上沒有提升。從特征點匹配率上來看，豐富窗口濾波器的權(quán)值，補償圖像中部分深度信息的方法，提高了特征點選取的準確程度；64維描述子比36維描述子的匹配率高；子區(qū)域采樣范圍大的匹配率高。因為圖像中特征點選取數(shù)量不變，而維數(shù)高，采樣范圍大的描述子使得匹配成功的特征點數(shù)量增加。從匹配效率上來講，SURF-36整體上要高于SURF-64，這是因為對于本例中640×480的圖像，36維描述子已經(jīng)足夠滿足精度，所以描述子維度雖然降低了，但是匹配的特征點數(shù)目卻沒有大幅減少，反而省去了多余的計算，使運算時間大幅減少。

綜上所述，可以總結(jié)出如圖7所示的SURF算法在處理低分辨率圖像上參數(shù)選擇策略，對于實時性要求較高的應(yīng)用，為提高算法運算速度，首先考慮降低SURF描述子維數(shù)，因為在低分辨率的圖像上，低維數(shù)的描述子準確度降低不明顯但運算速度更快；其次考慮縮小特征點周圍子區(qū)域內(nèi)采樣點的范圍。若特征點相對密集，圖像間重合部分較小，兩幅圖像相對角度較大，對拼接準確性要求較高的情況下，可以擴大特征點周圍子區(qū)域內(nèi)采樣點范圍。若錯誤匹配特征點較多，則可以通過改進窗口濾波器權(quán)值補償像素點的深度信息來精確對特征點的遴選。

圖7 SURF算法在實時低分辨率處理上參數(shù)策略

5 結(jié)束語

本文討論了SURF算法中一些可配置參數(shù)對算法時效性、準確性和魯棒性的影響。在特征點選取中對窗口濾波器的選擇，特征點描述時對特征點周圍子區(qū)域的選擇以及子區(qū)域內(nèi)采樣點范圍的選擇三方面，基于目前視頻流中最常采用的分辨率為640×480的圖像進行特征點匹配，采用控制變量法，從特征點匹配率和匹配效率分別對不同配置對特征點匹配的結(jié)果進行分析與比較，提出針對低分辨率實時圖像處理中SURF算法參數(shù)配置策略。

后續(xù)研究將針對于重合區(qū)域較小的圖像以及分辨率較高的圖像在利用SURF算法拼接過程中相應(yīng)參數(shù)的配置，從而完善SURF算法參數(shù)配置理論，使得算法在不同側(cè)重點的應(yīng)用中都能最大地發(fā)揮優(yōu)越性。

[1]Bay H，Ess A，Tuytelaars T，et al.Speeded-Up Robust Features（SURF）[J].Computer Vision and Image Understanding（CVIU），2008，110（3）：346-359.

[2]Huang Xiangsheng，Wang Jie，Zhang Mandun，et al.Gradual-SURF[C]//Proceedings of the 4th International Congress on Image and Signal Processing，2011：906-909.

[3]Chen Xiaoming，Bao Jing，Jiang Letian，et al.Integrated multidirectional panoramic image processing system[C]//Proceedings of the World Congress on Engineering and Technology，2011.

[4]Senarathne C N，Ransiri S，Arangala P，et al.A faster image registration and stitching algorithm[C]//Proceedings of the 6th International Conference on Industrial and Information Systems，2011.

[5]林武，洪景新，張昊.快捷有效的視頻圖像序列拼接方法[J].計算機工程與應(yīng)用，2009，45（2）：173-175.

[6]時磊，謝曉方，喬永軍.基于SURF算法和OpenCV的人臉特征檢測技術(shù)研究[J].計算機與數(shù)字工程，2010，38（2）：124-126.

[7]張銳娟，張建奇，楊翠.基于SURF的圖像配準方法研究[J].紅外與激光工程，2009，38（1）：160-165.

[8]Ihme T，Wetzelsberger K，Speckert M，et al.Real-time image processing based on a task-pair scheduling concept[C]//Proceedings of the 2011 IEEE International Conference on Robotics and Automation，2011：5596-5601.

ZHOU Yuhaowei,YING Rendong,JIANG Letian

Department of Electronic Engineering,Shanghai Jiao Tong University,Shanghai 200240,China

In the field of image stitching,SURF algorithm is widely used for its excellent real-time procedure and robust.Due to the fixed parameter settings in interest point detection and description,the adjustability of SURF algorithm to different applying situation is relatively weak.In order to improve the range of SURF application,this paper looks into three aspects in the algorithm: the weight of box filter,the sub-region selection and the Haar wavelet sampling point range within the sub-region.In comparing the real-time quality,the stitching accuracy and the robust quality of the algorithm,the experiments using variable control method propose a parameter setting strategy based on small scale image which is widely used in nowadays stream media.In analyzing the interest points match rate and efficiency,the strategies proposed in characterizing the algorithm can extend the use of SURF in real-time field.

Speeded Up Robust Features（SURF）algorithm;image stitching;small scale image;parameter settings;interest points matching;box filter;sub-region of interest points

在圖像拼接領(lǐng)域，SURF算法因其出眾的時效性和魯棒性，有著十分廣泛的應(yīng)用。針對SURF算法中特征點提取和描述過程中參數(shù)固定，對側(cè)重點不同的圖像拼接應(yīng)用存在變通性較差的問題，提出了從窗口濾波器權(quán)值，特征點周圍子區(qū)域的選擇以及子區(qū)域內(nèi)Haar小波變換的采樣點范圍三方面進行參數(shù)配置優(yōu)化。針對目前主流的流媒體尺寸圖像，利用控制變量法在不同的SURF參數(shù)配置下，對算法的時效性、準確性和魯棒性等性能進行了分析；通過特征點匹配率和特征點匹配效率的比較，給出了SURF算法參數(shù)的選擇策略。仿真結(jié)果表明該策略可以有效提高SURF算法在圖像拼接中的運算速度和準確性，豐富算法在實時領(lǐng)域的應(yīng)用。

加速魯棒特征（SURF）算法；圖像拼接；小尺寸圖像；參數(shù)配置；特征點匹配；窗口濾波器；特征點子區(qū)域

A

TP391

10.3778/j.issn.1002-8331.1206-0003

ZHOU Yuhaowei,YING Rendong,JIANG Letian.Parameter setting optimization in SURF algorithm based on small scale image.Computer Engineering and Applications,2013,49（19）：191-195.

周宇浩崴（1987—），男，碩士，研究方向為圖像拼接算法；應(yīng)忍冬（1975—），男，博士，副教授，研究方向為導(dǎo)航信號處理，SoC芯片架構(gòu)，嵌入式系統(tǒng)；蔣樂天（1975—），男，博士，副教授，研究方向為系統(tǒng)可靠性與可用性研究，軟件可靠性研究，嵌入式系統(tǒng)與結(jié)構(gòu)。E-mail：yuhaowei.zhou@sjtu.edu.cn

2012-06-01

2012-08-29

1002-8331（2013）19-0191-05

CNKI出版日期：2012-09-25http://www.cnki.net/kcms/detail/11.2127.TP.20120925.1002.053.html

◎信號處理◎