馮亦東， 孫 躍

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

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

馮亦東， 孫 躍

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

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

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

圖像匹配即通過(guò)一定的匹配算法在兩幅或多幅影像之間識(shí)別同名點(diǎn)的過(guò)程。圖像特征提取與匹配一直是計(jì)算機(jī)視覺(jué)中的一個(gè)關(guān)鍵問(wèn)題，在目標(biāo)檢測(cè)、物體識(shí)別、三維重建、圖像配準(zhǔn)、圖像理解等具體應(yīng)用中發(fā)揮著重要作用[1]。由于圖像的成像條件和所記錄的內(nèi)容復(fù)雜多樣，而且應(yīng)用需求各有不同，對(duì)圖像特征提取和圖像匹配的研究一直都是視覺(jué)領(lǐng)域中一個(gè)極具挑戰(zhàn)性的問(wèn)題。

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

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

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

1 SURF特征提取算法

1.1 Hessian矩陣

Hessian矩陣是SURF算法的核心，其行列式的局部最大值可以確定特征點(diǎn)的位置和尺度[13]。SURF算法通過(guò)Hessian矩陣求極值點(diǎn)來(lái)獲取穩(wěn)定點(diǎn)，用矩陣行列式的最大值來(lái)標(biāo)記塊狀特征結(jié)構(gòu)(blob-like structure)的位置。

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

Hessian矩陣判別式為：

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

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

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

其中，w為權(quán)重系數(shù)，其值與尺度σ相關(guān)，主要是為平衡準(zhǔn)確值與近似值之間的誤差，在實(shí)際的應(yīng)用中，通常取0.9。

1.2 SURF尺度空間及特征提取

圖像的尺度空間是一幅圖像在不同解析度下的表示，可以利用高斯核的卷積來(lái)實(shí)現(xiàn)，圖像的尺度大小一般用高斯標(biāo)準(zhǔn)差來(lái)表示[15]。在計(jì)算視覺(jué)領(lǐng)域，尺度空間需要對(duì)輸入圖像函數(shù)反復(fù)與高斯函數(shù)的核卷積并反復(fù)對(duì)其進(jìn)行二次抽樣，被象征性地表述為一個(gè)圖像金字塔。SURF算

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

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

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

圖2 SURF特征檢測(cè)

2 Flann特征緊鄰像素匹配

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

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

向量空間 Rn中所有歐氏距離 d(p,q)通過(guò)KD-TREE結(jié)構(gòu)存儲(chǔ)后，便可以有效搜索與參考點(diǎn)距離最鄰近的點(diǎn)。整個(gè)搜索過(guò)程是KD-TREE由上至下的遞歸過(guò)程。首先以某一特定維數(shù)為基準(zhǔn)將目標(biāo)點(diǎn)和分割點(diǎn)的值進(jìn)行比較，判別目標(biāo)點(diǎn)是在左區(qū)域還是右區(qū)域；然后循環(huán)和對(duì)應(yīng)節(jié)點(diǎn)進(jìn)行比較，直到目標(biāo)搜索成功為止。

3 試驗(yàn)分析

本 次 實(shí) 驗(yàn) 以 Visual studio 2010 和OPenCV2.4.6為開(kāi)發(fā)平臺(tái)，在PIV 2.4 GHz，1 GB內(nèi)存的微機(jī)上實(shí)現(xiàn)。測(cè)試圖像圖4(a)為223×324大小灰度圖像，測(cè)試圖像圖4(b)為512×384灰度圖像。

圖3 KD-TREE結(jié)構(gòu)

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

本文統(tǒng)計(jì)了SIFT算法和SURF算法的特征點(diǎn)個(gè)數(shù)、匹配點(diǎn)數(shù)、匹配成功率和運(yùn)行時(shí)間 4個(gè)指標(biāo)，并對(duì)兩種不同的算法進(jìn)行了質(zhì)量評(píng)價(jià)。特征點(diǎn)個(gè)數(shù)反映了算法特征提取能力，特征點(diǎn)越多，表明圖像細(xì)節(jié)信息更豐富；匹配點(diǎn)數(shù)量和匹配成功率反映圖像匹配的質(zhì)量，值越高，效果越理想；運(yùn)行時(shí)間體現(xiàn)了算法的效率。從表1中可以看到，本文提出的 SURF算法的特征點(diǎn)個(gè)數(shù)和匹配點(diǎn)數(shù)更多，匹配成功率也較高，并且運(yùn)行時(shí)間更短。

圖4 SIFT 和SURF特征匹配對(duì)比

表2是圖4(c)和圖4(f)通過(guò)FLANN匹配算法對(duì)前面特征向量進(jìn)行的KD-TREE搜索對(duì)比分析，從數(shù)據(jù)中可以看到，圖4(f)SURF算法的鄰近標(biāo)準(zhǔn)

差值比較大，說(shuō)明該算法提取的特征細(xì)節(jié)表達(dá)較SIFT更為明顯；由于圖 4(f)特征點(diǎn)數(shù)量較多，所以KD-TREE搜索算法用時(shí)較圖4(c)長(zhǎng)0.03 s。

表1 SIFT和SURF特征匹配數(shù)據(jù)對(duì)比

表2 Flann匹配分析

4 總 結(jié)

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

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

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

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

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

[5] 王俊卿, 黃沙白, 史澤林. 基于復(fù)數(shù)小波能量特征和支持向量機(jī)的圖像匹配算法[J]. 中國(guó)圖象圖形學(xué)報(bào), 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] 魏志強(qiáng), 黃 磊, 紀(jì)筱鵬. 基于點(diǎn)特征的序列圖像匹配方法研究[J]. 中國(guó)圖象圖形學(xué)報(bào), 2009, 14(3): 525-530.

[9] 邱建國(guó), 張建國(guó), 李 凱. 基于Harris與SIFT的圖像匹配方法[J]. 測(cè)試技術(shù)學(xué)報(bào), 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] 顧大龍, 曾 巒, 翟 優(yōu). 基于 SURF的圖像匹配算法改進(jìn)[J]. 現(xiàn)代電子技術(shù), 2012, 35(14): 79-82.

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

[13] 時(shí) 磊, 謝曉方, 喬勇軍. 基于SURF算法和OPenCV的人臉特征檢測(cè)技術(shù)研究[J]. 計(jì)算機(jī)與數(shù)字工程, 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] 高 健, 黃心漢, 彭 剛, 等. 一種簡(jiǎn)化的 SIFT圖像特征點(diǎn)提取算法[J]. 計(jì)算機(jī)應(yīng)用研究, 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] 劉樹(shù)勇, 楊超慶, 位秀雷, 等. 鄰近點(diǎn)快速搜索方法在混沌識(shí)別中的應(yīng)用[J]. 華中科技大學(xué)學(xué)報(bào), 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–)，女，浙江蒼南人，助理實(shí)驗(yàn)師，碩士。主要研究方向?yàn)閳D像處理。E-mail：graceyidong@163.com

通訊簡(jiǎn)介：孫 躍(1961–)，男，浙江蒼南人，副教授，學(xué)士。主要研究方向?yàn)閳D像處理和模式識(shí)別、可視化技術(shù)。E-mail：1053231712@qq.com