基于SURF特征提取和FLANN搜索的圖像匹配算法

馮亦東， 孫 躍

(溫州大學城市學院，浙江 溫州 325000)

基于SURF特征提取和FLANN搜索的圖像匹配算法

馮亦東， 孫 躍

(溫州大學城市學院，浙江 溫州 325000)

針對傳統圖像匹配算法存在特征信息少和誤匹配率高的問題，提出基于SURF特征提取和FLANN搜索的圖像匹配算法。通過Hessian矩陣獲取圖像局部最值，并使用不同尺寸特征描述器，同時處理尺度空間多層圖像的向量特征，最后采用FLANN搜索算法進行特征匹配。試驗表明，該算法比傳統的圖像匹配算法在效果和效率方面都表現得更好。

加速魯棒特征；Hessian；FLANN；圖像匹配

圖像匹配即通過一定的匹配算法在兩幅或多幅影像之間識別同名點的過程。圖像特征提取與匹配一直是計算機視覺中的一個關鍵問題，在目標檢測、物體識別、三維重建、圖像配準、圖像理解等具體應用中發揮著重要作用[1]。由于圖像的成像條件和所記錄的內容復雜多樣，而且應用需求各有不同，對圖像特征提取和圖像匹配的研究一直都是視覺領域中一個極具挑戰性的問題。

文獻[2-5]提出了采用小波變換來實現圖像的快速匹配，其具有良好的時頻局部化、多分辨分析和抑制高頻噪聲的優點，但圖像在特征提取方面受選取的小波基影響較大。1988年 Harris和Stephens[6]提出Harris角點檢測特征匹配算法，是一種直接基于灰度圖像的角點提取，穩定性高，對 L型的角點檢測敏感，但是運算速度較慢，存在角點信息丟失和位置偏移和聚簇現象。在此基

礎上，文獻[7-9]對 Harris匹配算法進行了改進，但是無法適應圖像尺度變化的問題。Lowe[7]在2004年提出尺度不變特征(scale invariant feature transform，SIFT)算法，即在尺度空間尋找極值點，提取位置、尺度、旋轉不變特征量。SIFT算法通過采用金字塔分層方式，大幅降低了計算量，并提取出了圖像中大量的特征點，但是由于SIFT算法沒有考慮空間的幾何約束信息，因而導致誤匹配率高，易出現明顯的錯配和亂配情況。2006年Bay等[10]提出加速魯棒特征(speed up robust features，SURF)提取算法。SURF特征由SIFT特征改進而來，通過Harris特征和積分圖像(integral image)相結合，大大加快了程序的運行速度，在圖像尺度和仿射變換下都可以保持不變性，在多幅圖片下具有更好的魯棒性，同時也存在誤匹配率高的問題。文獻[11-12]結合其他算法對SURF進行進一步改進，取得了不錯的效果。

基于上述研究，本文提出了基于SURF特征提取和快速近似最近鄰查找(fast library for approximate nearest neighbors, FLANN)搜索的圖像匹配算法。利用SURF算法中的Hessian矩陣來提取圖像中的局部最大值，采用不同尺寸的框式濾波器，同時處理尺度空間多層圖像獲取特征矢量，最后采用 FLANN中 KD-TREE快速搜索匹配SURF特征矢量。該算法不僅對兩幅圖像之間局部特征、平移、旋轉、尺度縮放、亮度變化、遮擋和噪聲等具有良好地匹配適應能力，而且速度也相對較快。

1 SURF特征提取算法

1.1 Hessian矩陣

Hessian矩陣是SURF算法的核心，其行列式的局部最大值可以確定特征點的位置和尺度[13]。SURF算法通過Hessian矩陣求極值點來獲取穩定點，用矩陣行列式的最大值來標記塊狀特征結構(blob-like structure)的位置。

假設函數 f(x,y)，Hessian矩陣H是由函數偏導數組成，可以表示為式(1)：

Hessian矩陣判別式為：

式(2)中，d (H )是H矩陣的特征值，可以利用判定結果的符號將所有點進行分類，根據判別式取正負，判別該點是否為極值點。在SURF算法中，用圖像像素 X(x,y)代替函數值 f(x,y)，選用二階標準高斯函數作為濾波器，通過特定核間的卷積計算二階偏導數，這樣便能計算出在尺度σ下的H矩陣的 3個矩陣元素 L xx (X,σ), L yy(X,σ) , L xy(X,σ)從而計算出H矩陣，如式(3)、(4)：

其中， g(t)為高斯函數，t為高斯方差。 L xx(X,σ)是高斯二階導數與圖像I在X點處的卷積。 L xy (x,σ)， L yy(x,σ)同樣也是高斯濾波后圖像在y和xy方向上的二階偏導數和二維圖像的卷積。

通過計算得到圖像中每個像素其H行列式的決定值，并用此值來判別特征點。根據 Lowe[14]成功地用高斯差分(difference of Gaussian，DoG)算法近似拉普拉斯高斯算子(Laplacian of Gaussian，LoG)的經驗，Bay等[10]提出采用框式濾波器來代替L在x、y、xy三個方向的近似值，分別記為 Dx x、 Dy y和 D xy。為平衡準確值與近似值間的誤差引入權值，則 H矩陣判別式的近似計算可表示為式(5)：

其中，w為權重系數，其值與尺度σ相關，主要是為平衡準確值與近似值之間的誤差，在實際的應用中，通常取0.9。

1.2 SURF尺度空間及特征提取

圖像的尺度空間是一幅圖像在不同解析度下的表示，可以利用高斯核的卷積來實現，圖像的尺度大小一般用高斯標準差來表示[15]。在計算視覺領域，尺度空間需要對輸入圖像函數反復與高斯函數的核卷積并反復對其進行二次抽樣，被象征性地表述為一個圖像金字塔。SURF算

法采用不同尺寸的框式濾波器進行處理，允許尺度空間多層圖像同時被處理，只改變濾波器大小不需要進行二次采樣，從而提高算法性能。圖1(a)是傳統方式建立金字塔結構，濾波器尺寸不變，圖像的尺寸隨尺度變化，需要反復使用高斯函數對子層進行平滑處理；圖1(b) SURF算法保持原始圖像不變而只改變濾波器大小。

SURF特征提取利用了插值技術在亞像素精度上尋找空間和尺寸的位置，可通過 Brown和Lowe[16]提出的三維二次方程得到。假設 Hessian的行列式函數記為 H(x,y,s)，并且 x = (x,y,s)T，根據泰勒展開式可以得到：

其函數導數可以利用相鄰像素間的差異來近似得到。如果x?在x、y、σ三個方向中的值大于0.5，則需要調整特征點的位置并再次實用插值算法，直到在所有方向上x?小于0.5或者預先設定的插值算法使用次數溢出。圖2為使用Hessian矩陣獲取特征點的效果，其中圓圈點表示被檢測出的特征點位置，共檢測出32個特征點。

圖2 SURF特征檢測

2 Flann特征緊鄰像素匹配

Muja和Lowe[17]于2009年提出FLANN算法，該方法基于K均值樹或KD-TREE搜索操作所實現的，可以根據數據集的分布特點、對映射精度和空間資源消耗的要求來推薦索引類型和檢索參數，在高維空間最近鄰查找不受局部敏感哈希[18]影響。FLANN算法模型的特征空間一般是n維實數向量空間 Rn，核心在于使用歐式距離找到實例點的鄰居。特征點p和q的特征分向量可記為 Dp和 D q，則 d(p,q)的歐氏距離可以表示為式(8)：

本文通過 KD-TREE將數據點在n維空間 Rn劃分為特定的幾個部分，其目的是檢索在KD-TREE中與查詢點距離最近的歐氏距離[19]。圖3中所標的A～J表示被搜索范圍中的點，將圖3(a)中被搜索區域按一定規則分割后，就可以建立圖3(b)所示的樹型結構。

向量空間 Rn中所有歐氏距離 d(p,q)通過KD-TREE結構存儲后，便可以有效搜索與參考點距離最鄰近的點。整個搜索過程是KD-TREE由上至下的遞歸過程。首先以某一特定維數為基準將目標點和分割點的值進行比較，判別目標點是在左區域還是右區域；然后循環和對應節點進行比較，直到目標搜索成功為止。

3 試驗分析

本 次 實 驗 以 Visual studio 2010 和OPenCV2.4.6為開發平臺，在PIV 2.4 GHz，1 GB內存的微機上實現。測試圖像圖4(a)為223×324大小灰度圖像，測試圖像圖4(b)為512×384灰度圖像。

圖3 KD-TREE結構

圖 4為兩幅測試圖像分別采用不同方法進行特征提取和匹配的試驗，圖 4(a)、(b)是測試圖像采用SIFT算法提取圖像的特征；圖4(c)為對SIFT提取的圖像特征采用Flann匹配后得出的結果；圖4(d)、(e)是本文采用的SURF特征提取算法獲得的試驗結果，圖4(f)是對SURF算法提取的特征進行Flann匹配后得出的效果。從視覺效果上來分析，圖 4(a)、(b)和圖 4(d)、(e)都不同程度地提取了兩幅圖像的特征信息，但本文SURF提取出來的特征信息點更多，表達的信息量也更豐富。圖4(c)和(f)對特征信息進行Flann快速匹配后的效果，從匹配速度和成功率來看也比較理想。

本文統計了SIFT算法和SURF算法的特征點個數、匹配點數、匹配成功率和運行時間 4個指標，并對兩種不同的算法進行了質量評價。特征點個數反映了算法特征提取能力，特征點越多，表明圖像細節信息更豐富；匹配點數量和匹配成功率反映圖像匹配的質量，值越高，效果越理想；運行時間體現了算法的效率。從表1中可以看到，本文提出的 SURF算法的特征點個數和匹配點數更多，匹配成功率也較高，并且運行時間更短。

圖4 SIFT 和SURF特征匹配對比

表2是圖4(c)和圖4(f)通過FLANN匹配算法對前面特征向量進行的KD-TREE搜索對比分析，從數據中可以看到，圖4(f)SURF算法的鄰近標準

差值比較大，說明該算法提取的特征細節表達較SIFT更為明顯；由于圖 4(f)特征點數量較多，所以KD-TREE搜索算法用時較圖4(c)長0.03 s。

表1 SIFT和SURF特征匹配數據對比

表2 Flann匹配分析

4 總 結

本文針對目前圖像特征匹配算法中存在圖像提取特征量少、特征誤匹配率高和匹配速度慢的問題，提出基于SURF特征提取和FLANN搜索的圖像匹配算法。利用SURF算法提取大量的圖像特征信息，同時采用FLANN的KD-TREE搜索相似的特征矢量，在不影響圖像匹配速度的前提下，提高特征匹配率準確率。實驗結果表明，本文提出的算法在匹配的效果、穩定性和速度方面表現更好。

[1] 譚博怡. 圖像特征提取與匹配[D]. 北京: 中國科學院研究生院, 2008.

[2] 洪小偉, 石守東, 康 丹. 一種基于小波模極大值的圖像特征匹配算法[J]. 寧波大學學報, 2009, 22(1): 66-69.

[3] 范新南, 朱佳媛. 基于小波變換的快速圖像匹配算法與實現[J]. 計算機工程與設計, 2009, 30(20): 1674-1676.

[4] 郭豐俊, 楊 新, 施鵬飛. 基于小波變換的多尺度圖像匹配算法[J]. 紅外與激光工程, 1999, 28(4): 30-33.

[5] 王俊卿, 黃沙白, 史澤林. 基于復數小波能量特征和支持向量機的圖像匹配算法[J]. 中國圖象圖形學報, 2004, 9(9): 1075-1079.

[6] Harris C, Stephens M. A combined corner and edge detector [C]//Manchester: Proceedings of the 4th Alvey Vision Conference. Manchester, UK, 1988: 147-151.

[7] Lowe D G. Distinctive image features form scale-invariant keypoints [J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[8] 魏志強, 黃 磊, 紀筱鵬. 基于點特征的序列圖像匹配方法研究[J]. 中國圖象圖形學報, 2009, 14(3): 525-530.

[9] 邱建國, 張建國, 李 凱. 基于Harris與SIFT的圖像匹配方法[J]. 測試技術學報, 2009, 23(3): 271-274.

[10] Bay H, Tuytelaars T, Van Gool L. SURF: speeded up robust features [C]//Proceedings of European Conference on Computer Vision. Graz, Austria, 2006: 404-407.

[11] 顧大龍, 曾 巒, 翟 優. 基于 SURF的圖像匹配算法改進[J]. 現代電子技術, 2012, 35(14): 79-82.

[12] 趙璐璐, 耿國華, 李 康, 等. 基于SURF和快速近似最近鄰搜索的圖像匹配算法[J]. 計算機應用研究, 2013, 30(3): 921-923.

[13] 時 磊, 謝曉方, 喬勇軍. 基于SURF算法和OPenCV的人臉特征檢測技術研究[J]. 計算機與數字工程, 2010, 38(2): 124-126.

[14] Lowe D G. Object recognition from local scale-invariant features [C]//International Conference on Computer Vision. Corfu, Greece, 1999: 1150-1157.

[15] 高 健, 黃心漢, 彭 剛, 等. 一種簡化的 SIFT圖像特征點提取算法[J]. 計算機應用研究, 2008, 25(7): 2213-2215.

[16] Brown M, Lowe D. Invariant features from interest point groups [C]//British Machine Vision Conference. Cardiff, Wales, 2002: 656-665.

[17] Muja M, Lowe D G. Fast approximate nearest neighbors with automatic algorithm configuration [C]//Proceedings of IEEE Conference on Computer Vision Theory and Applications. Lisbon, Portugal: IEEE Computer Society, 2009: 331-340.

[18] Chum O, Philbin J, Zisserman A. Near duplicate image detection: min-hash and tf-idf weighting [C]// Proceedings of the 19th British Machine Vision Conference. London, UK, 2008: 493-502.

[19] 劉樹勇, 楊超慶, 位秀雷, 等. 鄰近點快速搜索方法在混沌識別中的應用[J]. 華中科技大學學報, 2012, 40(11): 89-92.

Image Matching Algorithm Based on SURF Feature Extraction and FLANN Search

Feng Yidong, Sun Yue
(City College of Wenzhou University, Wenzhou Zhejiang 325000, China)

The traditional algorithm of image matching exist the problems of little feature information and high rate false match. An image matching algorithm is presented based on SURF feature extraction and FLANN search. Firstly, the extremum value of local image is gotten using the Hessian matrix. Secondly, the feature vector is simultaneously processed in multilayer image scale space by using of different size feature description. Finally, the FLANN algorithm is used for feature matching. The experiments show that this algorithm is better than the traditional algorithm of image matching in the aspect of effectiveness and efficiency.

speed up robust features; Hessian; FLANN; image matching

TP 391.4

A

2095-302X(2015)04-0650-05

2014-10-30；定稿日期：2015-03-10

馮亦東(1986–)，女，浙江蒼南人，助理實驗師，碩士。主要研究方向為圖像處理。E-mail：graceyidong@163.com

通訊簡介：孫 躍(1961–)，男，浙江蒼南人，副教授，學士。主要研究方向為圖像處理和模式識別、可視化技術。E-mail：1053231712@qq.com