一種基于SIFT特征的快速圖像匹配算法

摘要：針對(duì)SIFT算法運(yùn)行速度較慢、時(shí)間效率不高的問(wèn)題，本文提出了一種與Harris角點(diǎn)檢測(cè)算法相結(jié)合的快速圖像匹配算法。該方法利用Harris角點(diǎn)檢測(cè)算法計(jì)算量小，運(yùn)行速度快的優(yōu)點(diǎn)，并改進(jìn)SIFT算法描述子，通過(guò)調(diào)整描述子的結(jié)構(gòu)達(dá)到特征向量降維的目的，進(jìn)一步提高算法的時(shí)間效率。實(shí)驗(yàn)結(jié)果證明，該算法既保留了SIFT算法的穩(wěn)定性以及旋轉(zhuǎn)不變性，也提高了SIFT算法的運(yùn)行速度。

關(guān)鍵詞：圖像匹配；SIFT特征；Harris角點(diǎn)檢測(cè)

中圖分類(lèi)號(hào)：TP391.41

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.3969/j.issn.1003-6970.2015.06.011

本文著錄格式：任忠良，一種基于SIFT特征的快速圖像匹配算法[J].軟件，2015，36（6）：53-57

AFastImageMatchingAlgorithmBasedonSIFTFeatures

RENZhong-liang[Abstract]：AnewalgorithmisproposedcombinedwithHarriscornerdetectionalgorithm，inordertoimprovetheefficiencyofSIFTwhichrunsslowlyandhaslowefficiencyonfeaturesextracting.ItmakesfulluseofHarris'lowcalculationfastoperation.BychangingtheSIFTdescriptor，itachievesthegoalofdecreasingtheeigenvectorthroughimprovingthestructureofthedescriptor.Astheexperimentalresultsshow，thisalgorithm，notonlyretainsthestabilityandrotationinvarianceofSIFT，butalsoimprovesthespeedofSIFTalgorithm.

[Keywords]：Imagematching；SIFTfeatures，Harriscornerdetection

0引言

隨著人T智能的不斷發(fā)展，圖像匹配技術(shù)逐漸成為模式識(shí)別領(lǐng)域中一項(xiàng)非常重要的技術(shù)，其在諸多領(lǐng)域有著廣泛的應(yīng)用，如遙感衛(wèi)星地圖和地形匹配、醫(yī)學(xué)診斷、人臉識(shí)別等等?；趫D像局部特征的匹配算法是圖像匹配技術(shù)中較為常見(jiàn)的算法，該類(lèi)算法的思想是將圖像映射為包含該圖像局部特征信息的集合，以此來(lái)進(jìn)行圖像匹配。其中，SIFT（Scale-invariantfeaturetransform，尺度不變特征轉(zhuǎn)換）算法是一種較為經(jīng)典的利用圖像局部特征的匹配算法。SIFT算法[1-2]由Lowe于1999年提出，它基于尺度空間理論，具有穩(wěn)定性好、特征點(diǎn)準(zhǔn)確性強(qiáng)等優(yōu)點(diǎn)，對(duì)旋轉(zhuǎn)、尺度、光照等保持較好的不變性。

但SIFT算法也有其一些弊端，其中建立尺度空間需要較大的系統(tǒng)開(kāi)銷(xiāo)，時(shí)間效率較低。國(guó)內(nèi)外基于SIFT算法的改進(jìn)也有大量的研究。如KeandSukthankar[3]提出的PCA-SIFT算法，利用PCA（Principlecomponentanalysis，主要成分分析）將特征點(diǎn)描述向量降至36維；MikolajczykandSchmid[4]提II+Il-種SIFT變體描述子-GLOH（TheGradientLocation-OrientationHistogram，梯度定位方向直方圖），利用對(duì)數(shù)極坐標(biāo)代替Lowe使用的坐標(biāo)象限；HerbertBay等人[5]提出的SURF（Speed-upRobustFeatures，快速魯棒特征）算法選用二階標(biāo)準(zhǔn)高斯函數(shù)作為濾波器，通過(guò)改變?yōu)V波器大小來(lái)建立尺度空間，可以有效提高算法的效率；張春美等人[6]對(duì)SIFT描述子進(jìn)行改進(jìn)，利用同心網(wǎng)環(huán)描述特征點(diǎn)，保持旋轉(zhuǎn)不變性的前提下降低了描述子的維度；陳抒珞等人[7]提出Contourlet-SIFT變換，對(duì)特征及其鄰域先進(jìn)行Contourlet變換，構(gòu)建全局紋理描述向量，以提升匹配速度；范志強(qiáng)等人[8]將SIFT與數(shù)據(jù)聚類(lèi)做結(jié)合，提高了特征匹配的魯棒性。本文主要針對(duì)SIFT算法提取特征點(diǎn)時(shí)效性差這一缺點(diǎn)進(jìn)行改進(jìn)，結(jié)合Harris角點(diǎn)[9]提取算法，能夠有效的提高關(guān)鍵點(diǎn)的提取速度，并適當(dāng)降低描述子維度，以此來(lái)降低算法運(yùn)行所需的時(shí)間，增強(qiáng)算法的實(shí)時(shí)性。

1SIFT算法原理

SIFT算法基于Lindeberg等人[10]提出的尺度空間理論，利用高斯核建立尺度金字塔，在尺度空間尋找極值點(diǎn)，并賦予該點(diǎn)對(duì)尺度、旋轉(zhuǎn)保持不變性的特征向量，并利用這些特征向量間的歐氏距離來(lái)進(jìn)行匹配，以達(dá)到圖像匹配的目的。

1.1查找關(guān)鍵點(diǎn)

文獻(xiàn)[10]證明了高斯卷積核是生成尺度空間的唯一變換核。一幅圖像/（x，y）的尺度空間定義為L(zhǎng)（x，y，б），是由不同尺度的高斯函數(shù)與原圖像卷積運(yùn)算生成的[10]。

L（x，y，б）=G（x，y，б，）*（x，y）

（1）

其中，

高斯核的尺度б是連續(xù)變化的，將其與原圖像進(jìn)行卷積運(yùn)算，得到一組尺度空間圖像。將得到的圖像進(jìn)行降采樣作為相鄰組高斯圖像的基準(zhǔn)圖像，繼續(xù)與高斯核進(jìn)行卷積運(yùn)算得到新一組尺度空間圖像。如此反復(fù)直至圖像大小小于某個(gè)預(yù)定值。將相鄰層的高斯圖像進(jìn)行相減便得到DOG（DifferenceofGaussian）圖像D（x，y，б）。

Lowe在DOG尺度空間中尋找極值點(diǎn)，將其中每個(gè)點(diǎn)與相鄰尺度的對(duì)應(yīng)位置包括其相鄰位置以及本尺度的八個(gè)相鄰位置共計(jì)26個(gè)點(diǎn)逐個(gè)進(jìn)行比較，得到的局部極值位置和尺度即為極值點(diǎn)的位置和對(duì)應(yīng)的尺度。極值點(diǎn)即為后文敘述中的關(guān)鍵點(diǎn)。

1.2分配方向

SIFT算法中為每個(gè)關(guān)鍵點(diǎn)分配主方向時(shí)采用關(guān)鍵點(diǎn)鄰域的梯度分布，并且在1.3章節(jié)中描述符構(gòu)造也以此方向作為參照。

各像素梯度的模與方向的計(jì)算公式如下：

1.3生成描述符

生成描述符時(shí)，為保證其旋轉(zhuǎn)不變性，首先將關(guān)鍵點(diǎn)周?chē)鷧^(qū)域旋轉(zhuǎn)順時(shí)針旋轉(zhuǎn)θo，與主方向相同。在旋轉(zhuǎn)后的區(qū)域內(nèi)，對(duì)關(guān)鍵點(diǎn)周?chē)?6x16矩形窗口采樣。Lowe建議將其分成16個(gè)4x4的子區(qū)域，并在每個(gè)子區(qū)域中將方向投影至8個(gè)方向的梯度累加值，則共生成4x4x8共計(jì)128維向量，該向量即為SIFT算法的128維描述符，如圖1（以其中8x8為例）所示。

至此，SIFT特征描述符已具有尺度、旋轉(zhuǎn)不變性，將描述符進(jìn)一步做歸一化處理后可去除光照影響。并且SIFT算法中的鄰域方向也提供了較好的穩(wěn)定性，使得SIFT算法具有較高的魯棒性。

1.4特征向量的匹配

Lowe在原文中建議利用兩幅圖像檢測(cè)到的特征向量之間的歐式距離之間的比值作為匹配依據(jù)，具體步驟如下：在其中一幅圖像取關(guān)鍵點(diǎn)，并在另一幅圖像中根據(jù)歐式距離選取最近的前兩個(gè)關(guān)鍵點(diǎn)，若最近的距離除以次近的距離少于某個(gè)比例閾值，則接受這一對(duì)匹配點(diǎn)。歐氏距離定義及判定閾值公式如下：

根據(jù)公式（7）不難看出，將比例閾值Threshold增大，SIFT算法的匹配點(diǎn)對(duì)會(huì)增多。反之，降低比例閾值Threshold，匹配點(diǎn)對(duì)會(huì)減少，但匹配更加穩(wěn)定。文獻(xiàn)[2]中建議該閾值取值為0.8，本文算法根據(jù)經(jīng)驗(yàn)值將該閾值設(shè)為0.75。

2改進(jìn)的快速SIFT圖像匹配算法

由于在1.1章節(jié)中介紹的尺度空間中查找極值點(diǎn)的系統(tǒng)開(kāi)銷(xiāo)較大，導(dǎo)致算法效率較低，其目的是為了能夠找到較多、較為穩(wěn)定的極值點(diǎn)，并且保證其尺度不變性。但是在實(shí)際應(yīng)用中，若圖像獲取設(shè)備能夠保證較好的對(duì)焦情況，則進(jìn)行匹配的圖像尺度就不需進(jìn)行過(guò)多考慮，因此我們考慮與較為快速的犄征點(diǎn)提取算法做結(jié)合，以提高SIFT算法的效率。

2.1Harris角點(diǎn)提取算法

Harris算法是以Moravec算法[11]為基礎(chǔ)的，而其原理是將以目標(biāo)像素點(diǎn)（x，∥）為中心的窗口向任何方向移動(dòng)（μ，v）后計(jì)算灰度變化，Harris在此基礎(chǔ)上，利用微分運(yùn)算和白相關(guān)矩陣來(lái)檢測(cè)角點(diǎn)，能夠有效區(qū)分角點(diǎn)與邊緣。Harris算法具有計(jì)算簡(jiǎn)單的特點(diǎn)，所以運(yùn)行速度較快，并且算法具有較高的穩(wěn)定性和魯棒性，能夠在圖像旋轉(zhuǎn)、灰度變化以及噪聲干擾等情況下準(zhǔn)確的檢測(cè)特征點(diǎn)，具有較高的點(diǎn)重復(fù)度和較低的誤檢率。

2.2改進(jìn)的SIFT描述符

在經(jīng)過(guò)Harris角點(diǎn)提取算法提取特征點(diǎn)，計(jì)算并分配方向，以及對(duì)齊主方向之后，在關(guān)鍵點(diǎn)周?chē)?5x15的區(qū)域上采樣計(jì)算方向，其中將每個(gè)Sx5的區(qū)域方向投影到八個(gè)方向上，這樣生成的描述子有3x3x8共計(jì)72維向量，代替原文的128維向量，以達(dá)到降維的目的，如圖2（以其中一個(gè)5x5的區(qū)域?yàn)槔┧尽?/p>

通過(guò)對(duì)新的描述符的分析我們可以發(fā)現(xiàn)，改進(jìn)后的描述符在盡可能多的保留采樣區(qū)域（16x16改為15x15）的前提下，通過(guò)改進(jìn)描述符的結(jié)構(gòu)來(lái)對(duì)描述符降維。這樣做既有利于保持SIFT算法的魯棒性，又能夠進(jìn)一步提高后續(xù)匹配的速度。

2.3改進(jìn)的SIFT算法過(guò)程

根據(jù)2.2章節(jié)的分析，我們現(xiàn)對(duì)SIFT算法做如下改進(jìn)：首先利用Harris角點(diǎn)提取算法對(duì)圖像進(jìn)行關(guān)鍵點(diǎn)查找，接著對(duì)得到的關(guān)鍵點(diǎn)進(jìn)行主方向分配，并生成72維的改進(jìn)SIFT描述符，最后利用歐氏距離對(duì)兩幅圖像進(jìn)行匹配，得到匹配結(jié)果。算法過(guò)程如圖3所示：

3實(shí)驗(yàn)結(jié)果與分析

采用MATLABR2013a構(gòu)建實(shí)驗(yàn)平臺(tái)，將本文算法與SIFT算法在匹配效果與時(shí)效性方面進(jìn)行了比較與分析。算法運(yùn)行環(huán)境為CPU：InteI（R）Xeon（R）E3-1230v33.3GHz，內(nèi)存：8GB。

3.1具有一般場(chǎng)景的圖像匹配

圖4為使用SIFT算法進(jìn)行匹配的效果圖，而圖5為使用本文算法的匹配效果圖。經(jīng)分析，不難發(fā)現(xiàn)本文方法在特征點(diǎn)的提取方面更接近于視覺(jué)角點(diǎn)，特征點(diǎn)的數(shù)量雖然較少，但匹配正確率較高，效果較好。使用SIFT算法與本文算法進(jìn)行圖片匹配的運(yùn)行時(shí)間如表1所示。

由表1可以看出，本文算法在運(yùn)行時(shí)間上相對(duì)于SIFT算法有著較為明顯的提升，算法的時(shí)間效率較高，尤其是提取極值點(diǎn)的步驟，由于利用了速度較快的Harris算法，使得該步驟所需時(shí)間大大降低。并且由于描述子維度降低，使得匹配時(shí)間也得以縮短，同時(shí)保持較高的正確率。說(shuō)明本文算法具有較強(qiáng)的魯棒性。

3.2具有較大旋轉(zhuǎn)角度的圖像匹配

圖6中，圖（a）是經(jīng)典的Lena圖像，大小為512×512，圖（b）是對(duì)其進(jìn)行30。旋轉(zhuǎn)后得到的。由于本文主要是針對(duì)SIFT算法的速度進(jìn)行改進(jìn)，所以將速度較快的經(jīng)典SURF算法拿來(lái)作為參照，似驗(yàn)證本文所提出算法的時(shí)效性，算法運(yùn)行環(huán)境同上。圖6是原SIFT算法的匹配效果圖，從圖中可以看出原SIFT算法匹配效果較好，信息較為豐富，且正確率較高。圖7是SURF算法的匹配效果圖，從圖中可以看出SURF算法匹配雖然信息較為豐富，但就旋轉(zhuǎn)圖像而言，誤匹配率較高，匹配效果較差。圖8是本文算法的匹配效果圖，從圖中可以看出本文算法匹配效果較好，正確率較高。使用SIFT算法，SURF算法與本文算法進(jìn)行圖片匹配的運(yùn)行時(shí)間如表2所示。

由表2可以看出，SIFT算法具有旋轉(zhuǎn)不變性，對(duì)于旋轉(zhuǎn)圖片仍有較高的正確率。而SURF算法雖然時(shí)效性強(qiáng)，但針對(duì)旋轉(zhuǎn)圖像則不能保證較高的正確率。而本文算法在保證較高正確率的前提下，依然有著較快的速度表現(xiàn)，表明本文算法具有時(shí)效性和旋轉(zhuǎn)不變性。

4結(jié)論

本文針對(duì)SIFT算法時(shí)間效率較差這一缺陷進(jìn)行改進(jìn)，在極值點(diǎn)的提取部分針對(duì)較小尺度變換的圖片，采用速度較快，算法較為簡(jiǎn)單的Harris算法來(lái)代替原有的尺度空間的極值點(diǎn)提取。并在描述符生成時(shí)采用新的描述符結(jié)構(gòu)來(lái)達(dá)到降維的目的，從而進(jìn)一步提高算法運(yùn)行效率。從最終的實(shí)驗(yàn)結(jié)果圖以及與幾種算法對(duì)比的時(shí)間結(jié)果來(lái)看，本文算法既能保證穩(wěn)定性與正確性，又能降低算法的時(shí)間開(kāi)銷(xiāo)。在接下來(lái)的工作中，可以嘗試與一些其他模式識(shí)別與匹配算法[12-14]進(jìn)行結(jié)合，以設(shè)計(jì)出更加有效的算法。

參考文獻(xiàn)

[1]LoweDG.Objectrecognitionfromlocalscale-invariantfeatures[C]//Procofthe7thIEEEIntConfonComputerVision.Piscataway，NJ：IEEE，1999：1150-1157.

[2]LoweDG.Distinctiveimagefeaturesfromscale-invariantkeypoints[J].InternationalJournalofComputerVision，2004，60（2）：91-110。

[3]KeY，SukthankarR.PCA-SIFT：Amoredistinctiverepresentationforlocalimagedescriptors[C]//Procofthe2004IEEEComputerSocietyConfonComputerVisionandPatternRecognition.Piscataway，NJ：IEEE，2004：511-517.

[4]MikolajczykK，SchmidC.Aperformanceevaluationoflocaldescriptors[J].IEEETransonPatternAnalysisandMachineIntelligence，2005，27（10）：1615-1630.

[5]BayH，EssA，TuytelaarsT，etal.Speeded-uprobustfeatures（SURF）[J].ComputerVisionandImageUnderstanding，2008，110（3）：346-359。

[6]張春美，龔志輝，孫雷.改進(jìn)SIFT特征在圖像匹配中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用.2008.44（2）：95-97.

[7]陳抒珞，李勃，董蓉，等.Contourlet-SIFT特征匹配算法m.電子與信息學(xué)報(bào)，2013，35（5、：1215-1221.

[8]范志強(qiáng)，趙沁平.一種基于數(shù)據(jù)聚類(lèi)的魯棒SIFT特征匹配方法[J].計(jì)算機(jī)研究與發(fā)展，2012，49（5）：1123-1129.

[9]SchmidC，MohrR.Localgrayvalueinvariantsforimageretrieval[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，1997，19（5）：530-534.

[10]LindebergT.Featuredetectionwithautomaticscaleselection[J].InternationalJournalofComputerVision，1998，30（2）：79-116.

[11]MoravecHP.Towardsautomaticvisualobstacleavoidance[C]//ProceedingsofInternationalJointConferenceonArtificialIntelligence.Cambridge.MA.USA：fs.n.].1977：584-590.

[12]郝春媚、楊榆.面向涉密檢查系統(tǒng)的基于KMP思想的多模式匹配算法[J].軟件.2013.34（9）：57-60.[J].[13]楊沐，王晨升，陳志強(qiáng)，等.復(fù)雜背景下的字符模板匹配改進(jìn)算法研究[J].軟件，2012.33（12）：97-100.[J].[14]陳小星，陶志強(qiáng).一種基于車(chē)輛圖像的Keren配準(zhǔn)方法的改進(jìn)算法[J].軟件，2014，35（12）：20-25.