楊　松　邵龍?zhí)丁∷尉S波　劉　威

1(大連理工大學工業(yè)裝備結(jié)構(gòu)分析國家重點實驗室　遼寧 大連 116024)2(大連海洋大學信息工程學院　遼寧 大連 116023)

?

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

楊松1,2邵龍?zhí)?宋維波2劉威2

1(大連理工大學工業(yè)裝備結(jié)構(gòu)分析國家重點實驗室遼寧 大連 116024)2(大連海洋大學信息工程學院遼寧 大連 116023)

摘要經(jīng)典的SIFT算法具有良好的尺度、旋轉(zhuǎn)、光強不變特性而廣泛應用于圖像匹配。圖像特征點較少時，匹配過程使用窮舉法查找最近鄰匹配點；當圖像特征點較多時采用KD-Tree結(jié)構(gòu)，而其檢索過程存在“回溯”現(xiàn)象，這兩種方法的匹配效率都不高。為了提高特征點的匹配速度，提出改進的SP-Tree結(jié)構(gòu)解決“回溯”問題。在結(jié)點集分割時設(shè)置參數(shù)合理確定左右超平面位置，引入平衡因子作為結(jié)點分割方法選擇的依據(jù)，采用近似最近鄰搜索算法加快特征點匹配速度。給出算法的詳細實現(xiàn)過程，并應用兩幅圖像進行驗證。實驗結(jié)果表明：SIFT特征向量采用改進SP-Tree結(jié)構(gòu)在損失少部分匹配點的同時，提高了SIFT特征點的整體匹配速度，適合于圖像特征的實時匹配過程。

關(guān)鍵詞圖像匹配SIFT特征KD-TreeSP-Tree最近鄰搜索

0引言

圖像匹配是一種研究同一場景中兩個不同視角下的圖像之間對應關(guān)系的技術(shù)，是計算機視覺應用研究的起點和基石，已廣泛應用于圖像的拼接與融合、目標的識別與跟蹤、攝像機標定、圖像檢索以及三維重構(gòu)等領(lǐng)域[1-4]。目前，圖像匹配[5]方法主要有基于面積、比值和相位等算法，它們存在著共同的缺點：圖像拍攝的焦距要相同，且圖像旋轉(zhuǎn)角度和變形不能太大，這極大地限制了它們的廣泛應用。近年來，基于圖像局部不變性特征的圖像匹配算法以其計算簡單、精度高和魯棒性好等特點成為目前研究的熱點。哥倫比亞大學的Lowe在1999年提出并逐步完善的SIFT算法[6,7]。該算法是通過構(gòu)建金字塔和利用高斯核濾波差分來實現(xiàn)的，該算法不僅具有圖像旋轉(zhuǎn)、尺度變換、仿射變換和視角變化條件下的不變性特征，對目標的運動、遮擋、噪聲等因素影響也能達到較好的匹配效果。Mikolajczyk提出了基于Harris-Laplace和Hessian-Laplace特征匹配算法[8]，該算法具有仿射不變性，但檢測到的特征點數(shù)較少。Bay在2006年提出SURF(Speed-up Robust Feature)算法[9]，進一步提高了特征的提取速度，但在尺度和旋轉(zhuǎn)的適應性方面不及SIFT算法。優(yōu)秀的圖像匹配算法不僅要求圖像特征點具有穩(wěn)定的表征形式，而且還需要有快速的特征點配準算法。SIFT算子通過計算特征向量間的歐式距離來衡量其相似度。其特征向量的維數(shù)為128維，相似度計算的速度會較慢，而且特征點配對過程采用全局搜索法，其搜索過程的效率不高，尤其特征點數(shù)目較多時，整個圖像匹配過程將非常耗時。為此，學者們從兩個方面研究和改進SIFT算子：一個研究方面是降低特征向量的維數(shù)[10，11]，如PCA、SPCA算法，運用主成分分析法提取特征向量的主成分，壓縮向量數(shù)據(jù)，降低特征向量的維數(shù)，從而減少特征點相關(guān)性計算時間，但會導致匹配準確率的降低。此外，一些算法[12-14]引入其他一些特征點的表征形式，可以在降低特征向量維數(shù)的同時保持較好的匹配準確率。研究的另一方面是采用特殊的結(jié)構(gòu)[15]，如KD-Tree[16]、改進KD-Tree[17]等。通過構(gòu)建特征點存儲的二叉樹，同時結(jié)合最近鄰搜索算法，加快特征向量的匹配搜索速度，從而縮短圖像特征點的匹配時間。

在對Metric-Tree結(jié)構(gòu)進行研究的基礎(chǔ)上，采用SP-Tree[18]結(jié)構(gòu)存儲圖像特征點。SP-Tree是一種高效查詢的二叉樹，其檢索過程不會產(chǎn)生“回溯”問題。SP-Tree的建樹過程通過設(shè)置參數(shù)合理確定左右超平面位置，引入平衡因子作為結(jié)點分割方法選擇的依據(jù)，采用近似最近鄰搜索算法加快特征點的匹配過程。文中給出SP-Tree結(jié)點的結(jié)構(gòu)定義、二叉樹建樹的過程和最近鄰結(jié)點搜索算法的具體實現(xiàn)過程，并將其應用在圖像特征點的實時匹配過程中，取得較好的效果。

1SIFT特征描述

SIFT圖像匹配算法的特征描述子提取過程[17]包括：首先利用變尺度高斯核函數(shù)與圖像通過卷積運算建立圖像的高斯差分多尺度空間，將同一尺度下的8個相鄰點和上下相鄰尺度對應的18個點共26個點進行比較，找出圖像的局部極值點作為候選關(guān)鍵點；然后通過二次函數(shù)計算特征點的精確位置，再通過計算該位置的高斯差分響應值及曲率去除對比度低的極值點和不穩(wěn)定的邊緣響應點，確定特征點的主方向，使算子獲得更好的旋轉(zhuǎn)不變性。以特征點為中心取16×16個像素的鄰域范圍(圖1以8×8為例)，進而分成16個4×4的子塊，提取8個方向(45°間隔)上的梯度值，構(gòu)成128維的SIFT算子的特征向量，對其進行向量歸一化后并對梯度幅值進行限制，以去除光照變化的影響。

圖1　SIFT特征點示意圖

2特征向量匹配算法

通過上述過程生成圖像的特征點描述子，包含每個特征點的位置、尺度和方向等信息。在理想狀態(tài)下的兩幅圖像相同部分的特征點應具有相同的特征描述子，它們之間的距離應該最近，因而可以采用最近鄰搜索方法尋找圖像特征點的對應關(guān)系。衡量特征點相似程度的度量有歐式距離[17]、斜面距離[19]等。

近年來，KD-Tree結(jié)構(gòu)被用于特征向量的匹配過程，可以加快搜索速度，其搜索過程包括兩部分時間開銷：一部分是一個特征點集合的建樹時間，這部分是固定的，且較為耗時，這也是當特征點規(guī)模較小時不采用KD-Tree搜索的原因。另一部分是在建好的KD-Tree中進行最近鄰搜索時間。在KD-Tree中進行最近鄰搜索時容易產(chǎn)生“回溯”搜索過程，KD-Tree在第S維度上的空間劃分的示意圖如圖2(a)所示，在分割超平面兩邊分布有數(shù)目相當?shù)臄?shù)據(jù)點。當查詢點位于分割超平面附近時，因為其最近鄰有可能落在分割超面的另一邊，其“回溯”操作必須進行。針對這個問題，近年來研究人員提出了不少改進方案，如回溯搜索從優(yōu)先級最高的樹結(jié)點開始，確保優(yōu)先搜索包含最近鄰點可能性較高的空間[17]等。本文針對KD-Tree的“回溯”問題，提出改進SP-Tree算法，縮短了最近鄰特征向量的搜索時間。

圖2　KD-Tree和SP-Tree空間劃分示意圖

3最近鄰搜索算法

3.1Metric-Tree[20]

Metric-Tree是一棵二叉樹，它的結(jié)點都是點的集合，根結(jié)點代表了所有點的集合。對于非葉子結(jié)點v所代表的集合N(v)被分割成兩個子集，分別用v的兩個孩子結(jié)點v.lc和v.rc表示，滿足式(1)和式(2):

N(v)=N(v.lc)∪N(v.rc)

(1)

?=N(v.lc)∩N(v.rc)

(2)

3.2結(jié)點分割算法

建立Metric-Tree的關(guān)鍵是如何分割結(jié)點v，方法如下：

步驟1從N(v)中選擇兩個樞紐點v.lpv和v.rpv，滿足:

‖v.lpv-v.rpv‖=maxp1,p2∈N(v)‖p1-p2‖

(3)

步驟3每個結(jié)點包含一個中心點為v.center，半徑為v.r的超球B，滿足N(v)∈B(v.center,v.r)。

4SP-Tree結(jié)構(gòu)

4.1SP-Tree定義

如圖1(b)所示，SP-Tree在Metric-Tree的基礎(chǔ)上改進的，在超平面L左右兩側(cè)以距離τ為間距分別作平行于超平面L的超平面LL和LR。

N(v)中LL右側(cè)的點劃分到v.rc中，LR左側(cè)的點劃分到v.lc中，即：

N(v.lc)={x|x∈N(v),d(x,LR)+2τ>d(x,LL)}

(4)

N(v.rc)={x|x∈N(v),d(x,LL)+2τ>d(x,LR)}

(5)

4.2改進的SP-Tree搜索

在SP-Tree的基礎(chǔ)上，做出改進如下：在結(jié)點分割算法中需要確定左右超平面，可以在超平面左右距離為τ建立左右超平面。但是在進行結(jié)點超平面確定時為了保證左右孩子結(jié)點中包含的特征點數(shù)相等，而使得超平面并非過中心點，超平面左右并不對稱，超平面法向量在超平面左右的長度分別為ll和lr，且ll！=lr，這里引入?yún)?shù)α(0<α<1)，設(shè)置左右超平面距離分別為ll×α和lr×α，這種設(shè)置方法更為合理。

不是所有的結(jié)點都要進行重疊劃分，定義一個平衡因子ρ(一般取0.7)，如果對于取定的τ(已被上式替換)，劃分后結(jié)點v的任一孩子結(jié)點包含的點數(shù)大于ρ‖N(v)‖時，則按Metric-Tree的分割方式對結(jié)點v重新進行劃分；否則，保留原先的劃分方式，繼續(xù)對其孩子結(jié)點按上述方法進行分割，直到結(jié)點包含的點數(shù)達到葉子結(jié)點的要求為止，近似最近鄰查詢與SP-Tree相同。

4.3近似的最近鄰搜索

對于查詢q，如果當前結(jié)點為v，q在v結(jié)點超平面L的左側(cè)，則遞歸地查詢v的左孩子v.lc；否則遞歸地查詢v的右孩子v.rc，直到查詢到葉子結(jié)點，則認定該葉子結(jié)點為q的最近鄰結(jié)點。

4.4具體的算法實現(xiàn)

給出算法的具體定義和實現(xiàn)過程，采用Matlab語言表示：

(1)SP-Tree的二叉搜索樹結(jié)構(gòu)和超平面的定義

structSpTreeNode

{

set N;

//該結(jié)點包含的特征點集合

SpTreeNode *lc;

//左孩子指針

SpTreeNode *rc;

//右孩子指針

HyperplanehPlane;

//超平面

HyperplanelhPlane;

//左超平面

HyperplanerhPlane;

//右超平面

Point center;

//特征向量組成的超球的中心點，初始值為空間原點

int radius;

//該特征點集空間的超球半徑，初始值為0

bool overlapping;

//是否重疊劃分標志，初始值為false

boolisleaf;

//是否為葉子結(jié)點標志，初始值為false

};

structHyperplane

{Point PointOnPlane;

//超平面上一點，默認值為空間原點

NormalVectornVector;

//超平面法向量，默認值為零向量

};

//用超平面上一點和其法向量表示該超平面

(2) SP-Tree的建立算法

步驟1初始化一個SpTreeNode隊列；

步驟2創(chuàng)建根結(jié)點RootNode，入隊；

步驟3若隊列非空，取出隊首元素SpCurNode，判斷該結(jié)點包含的特征點集合大??；若大于葉子結(jié)點允許包含的最大特征點數(shù)，則按照分割算法來分割該結(jié)點為兩個結(jié)點lcNode和rcNode，SpCurNode.lc = &lcNode，SpCurNode.rc = &rcNode，并將lcNode和rcNode入隊；否則，修改結(jié)點的isleaf標志，隊首元素直接出隊；若隊列為空，則退出算法；

步驟4轉(zhuǎn)向步驟3執(zhí)行。

(3) SP-Tree的根結(jié)點建立算法

步驟1初始化一個SpTreeNode型變量RootNode；

步驟2將所有特征點的索引值加入RootNode.N中(為了節(jié)省空間，對所有特征點集合只保留一個全局副本，樹結(jié)點中的成員變量N只保存該結(jié)點中特征點在副本中的索引值)；

步驟3計算RootNode.center(為了減小時間復雜度，取所有特征向量對應維度上最大最小值的平均值作為中心點在該維度上的值)；

步驟4計算超球半徑RootNode.radius(超球空間中所有特征向量距中心點的距離最大值)；

步驟5確定超平面RootNode.hPlane；

步驟6左右超平面RootNode.lhPlane；RootNode.rhPlane初始化為默認值，RootNode.overlapping初始化為false，左右孩子指針初始化為NULL。

(4) 確定超平面RootNode.hPlane算法

步驟1在RootNode.N找到距離最遠的兩個特征向量lpv和rpv，采用近似算法：先找到距離中心點最遠的特征點lpv，再以lpv為基準找到距離lpv最遠的點rpv，RootNode.hPlane.nVector=rpv-lpv;

步驟2對所有屬于RootNode.N的特征向量v，統(tǒng)計v-lpv在RootNode.hPlane.nVector上的投影值，找出所有投影值的中位數(shù)median，則RootNode.hPlane.PointOnPlane = lpv+median/dist(RootNode.hPlane.nVector)*RootNode.hPlane.nVector。

(5) 結(jié)點分割算法

不是所有的結(jié)點都要進行重疊劃分，定義一個平衡因子(一般取0.7)，如果對于取定的、重疊劃分后結(jié)點的任一孩子結(jié)點包含的點數(shù)大于*SpCurNode.N.size()時，則按Metric-Tree的分割方式對結(jié)點進行劃分；否則進行重疊劃分，具體步驟如下：

步驟1初始化兩個SpTreeNode：lcNode、rcNode；

步驟2在當前結(jié)點超平面SpCurNode.hPlane左右兩側(cè)作超平面的平行平面lhPlane、rhPlane，超平面法向量在超平面左右的長度分別為ll和lr，分別在距離ll×ratio和lr×ratio (0

步驟3分別作如下操作：

① 用兩個集合lcN、rcN記錄分割后左右孩子中包含的特征點索引；

② 首先用lcN、rlN分別記錄rhPlane和lhPlane的右側(cè)和左側(cè)的特征點，并計算點數(shù)rhpCount、lhpCount；可以通過特征點與超平面上的點組成的向量在超平面上法向量上的投影的正負來判斷在超平面的哪一側(cè)；

③ 判斷(lhpCount>pho*SpCurNode.N.size()|| rhpCount>pho*SpCurNode.N.size())，若為假，則：

SpCurNode.lhPlane = lhPlane，SpCurNode.rhPlane=rhPlane，SpCurNode.overlapping = true；

若為真，則SpCurNode.overlapping = false，修改lcN、rlN分別記錄lPlane左右兩側(cè)的特征點；

④ lcNode.N = lcN，rcNode.N = rcN，再分別計算lcNode.center、rcNode.center、lcNode.radius、rcNode.radius、lcNode.hPlane、rcNode.hPlane，其他成員仍為默認值，返回。

(6) 最近鄰查詢

給定一個特征向量，先查詢根結(jié)點，若在根結(jié)點超平面的左側(cè)則遞歸地查詢左孩子結(jié)點；否則，遞歸地查詢右孩子結(jié)點，直到當前結(jié)點為葉子結(jié)點。順序查詢?nèi)~子結(jié)點中包含的特征向量，找到最近點和次近點后返回。

5實驗結(jié)果與分析

本文提取圖像SIFT特征進行點匹配實驗，所有編程都在Matlab 7.0環(huán)境下，實驗用計算機的配置如下：CPU：Intel Core i3-370，主頻2.4 GHz，內(nèi)存2 GB，操作系統(tǒng)為Windows 7。實驗采用標準圖像Lena、Building進行測試，搜索到最近鄰特征點后，采用比值提純法[17]剔除實際未匹配的特征點。如圖3-圖6所示。

圖3　Lena圖像

圖4　三種匹配算法的比較

圖5　Building圖像

圖6　三種匹配算法的比較

通過表1的對比可知，采用改進SP-Tree結(jié)構(gòu)進行特征點匹配具有很快的速度。若圖像特征點較少，則采用窮舉算法則取得較好的效果，因為KD-Tree結(jié)構(gòu)建樹還需要花費較多時間。當圖像特征點較多時(超過2500個[17])，選用KD-Tree+BBF效果較好。本文的SP-Tree算法執(zhí)行時間包括建SP -Tree的過程和在二叉樹中進行近似最近鄰搜索的過程，在損失少部分匹配特征點的情況下，匹配速度有較大的提升，適合對圖像特征點匹配要求不高的情況。

表1　三種匹配方法實驗結(jié)果對比(匹配時間:s)

6結(jié)語

本文給出SP-Tree結(jié)構(gòu)的定義，并對特征點建樹、最近鄰匹配點搜索過程進行詳細說明，消除KD-Tree樹搜索過程的“回溯”問題。通過對標準圖像進行SIFT特征匹配實驗，并與原有的匹配算法和BBF-KD-Tree匹配算法進行比較得出，本文算法在減少部分匹配點對的同時，其匹配速度有顯著的提升，可應用于特征點實時匹配過程。

參考文獻

[1] Brown M,Lowe D G.Recognizing panoramas[C]//Proceeding of the 9thInternational Conference on Computer Vision(ICCV03),Nice,France:IEEE,2003:1218-1225.

[2] 楊云濤,馮瑩,曹毓,等.基于SURF的序列圖像快速拼接方法[J].計算機技術(shù)與發(fā)展,2011,21(3):6-9,14.

[3] Jegou H,Harzallah H,Schmid C.A contextual dissimilarity measure for accurate and efficient image search[C]//Proceeding of the Conference on Computer Vision & Pattern Recognition.Minneapolis,USA,2007:1-8.

[4] 王劍,周國民.圖像三維重建中的特征點匹配方法研究[J].計算機工程與應用,2009,45(2):10-12.

[5] Zitova B,Flusser J.Image registration methods:a survey[J].Image and Vision Computing,2003,21(11):977-1000.

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

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

[8] Mikolajczyk K,Schmid C.Indexing based on scale invariant interest points[C]//The Proceeding of the 8thInternational Conference on Computer Vision(ICCV01),Vancouver,2001:525-531.

[9] Bay H,Tuytelaars T,VanGool L.Surf:Speeded up robust features[C]//The 9thEuropean Conference on Computer Vision(ECCV06),GRAZ,2006:404-417.

[10] Ke Y,Sukthankar R.PCA-SIFT:A more distinctive representation for local image descriptors[C]//Proceedings of IEEEComputer Society Conference on Computer Vision and Pattern Recognition,Washington,D.C.,2004:506-513.

[11] 吳賢偉,岑杰,邰曉英.一種快速圖像特征降維方法:SPCA[J].寧波大學學報:理工版,2005,18(3):336-339.

[12] 劉立,彭復員,趙坤,等.采用簡化SIFT算法實現(xiàn)快速圖像匹配[J].紅外與激光工程,2008,37(1):181-184.

[13] 鄭永斌,黃新生,豐松江.SIFT和旋轉(zhuǎn)不變LBP相結(jié)合的圖像匹配算法[J].計算機輔助設(shè)計與圖形學學報,2010,22(2):286-291.

[14] 石釗銘,耿伯英,董銀文.基于改進SIFT的航拍圖像快速匹配方法[J].指揮控制與仿真,2013,35(1):106-110.

[15] Bentley J L.Multidimensional binary search trees used for associative searching[J].Communications of the ACM,1975,18(9):509-517.

[16] 杜振鵬,李德華.基于KD-Tree搜索和SURF特征的圖像匹配算法研究[J].計算機與數(shù)字工程,2012,40(2):96-98,126.

[17] 王永明,王貴錦.圖像局部不變性特征與描述[M].北京:國防工業(yè)出版社,2010.

[18] Liu T,Moore A W,Gray A,et al.An investigation of practical approximate nearest neighbor algorithms[M].NIPS,MIT Press,Cambridge,2005.

[19] 傅衛(wèi)平,秦川,劉佳,等.基于SIFT算法的圖形目標匹配與定位[J].儀器儀表學報,2011,32(1):163-169.

[20] Ciaccia P,Patella M,Zezula P.M-Tree:An efficient access method for similarity search in metric spaces[C]//Proceedings of 23rdVLDB International Conference,Athens,Greece,1997:426-435.

收稿日期：2015-03-04。國家自然科學基金項目(50905022，5130 9047)；國家高技術(shù)研究發(fā)展計劃項目(2010CB7315022)；工業(yè)裝備結(jié)構(gòu)分析國家重點實驗室專項基金項目(S09104)。楊松，副教授，主研領(lǐng)域：數(shù)字圖像處理，模式識別。邵龍?zhí)?，教授。宋維波，講師。劉威，講師。

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.043

A QUICK IMAGE MATCHING ALGORITHM BASED ON SIFT FEATURE

Yang Song1,2Shao Longtan1Song Weibo2Liu Wei2

1(StateKeyLaboratoryofStructuralAnalysisofIndustrialEquipment,DalianUniversityofTechnology,Dalian116024,Liaoning,China)2(InstituteofInformationEngineering,DalianOceanUniversity,Dalian116023,Liaoning,China)

AbstractDue to its good invariant characteristics in scaling, rotation and light intensity, the classic SIFT algorithm has been widely used in image matching. If there are fewer image feature points, the exhaustion method is used to find the nearest matching point. If there are more image feature points, KD-tree will then be used, but the backtracking phenomenon exists in its retrieval process, so the matching efficiency of both methods are low. In order to improve feature points matching speed, we propose an improved SP-Tree structure to solve the backtracking problem. The parameter α is set to determine a reasonable location about hyper-plane in node set segmentation, and a balancing factors ρ is introduced as the choice basis for different node segmentation method, and the approximate nearest searching algorithm is adopted, which can accelerate the speed of feature points matching. In the paper we give the detailed implementation process of the algorithm and the validations with two standard images. Experimental results show that the SIFT feature vector, by using a modified SP-Tree structure, at the expense of few matching points, greatly improves the overall speed of SIFT feature points matching. It is suitable for image features matching in real time.

KeywordsImage matchingSIFT featureKD-TreeSP-TreeNearest neighbour search