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

楊　松　邵龍潭　宋維波　劉　威

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

?

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

楊松1,2邵龍潭1宋維波2劉威2

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

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

關鍵詞圖像匹配SIFT特征KD-TreeSP-Tree最近鄰搜索

0引言

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

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

1SIFT特征描述

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

圖1　SIFT特征點示意圖

2特征向量匹配算法

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

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

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

3最近鄰搜索算法

3.1Metric-Tree[20]

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

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

(1)

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

(2)

3.2結點分割算法

建立Metric-Tree的關鍵是如何分割結點v，方法如下：

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

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

(3)

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

4SP-Tree結構

4.1SP-Tree定義

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

N(v)中LL右側的點劃分到v.rc中，LR左側的點劃分到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的基礎上，做出改進如下：在結點分割算法中需要確定左右超平面，可以在超平面左右距離為τ建立左右超平面。但是在進行結點超平面確定時為了保證左右孩子結點中包含的特征點數相等，而使得超平面并非過中心點，超平面左右并不對稱，超平面法向量在超平面左右的長度分別為ll和lr，且ll！=lr，這里引入參數α(0<α<1)，設置左右超平面距離分別為ll×α和lr×α，這種設置方法更為合理。

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

4.3近似的最近鄰搜索

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

4.4具體的算法實現

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

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

structSpTreeNode

{

set N;

//該結點包含的特征點集合

SpTreeNode *lc;

//左孩子指針

SpTreeNode *rc;

//右孩子指針

HyperplanehPlane;

//超平面

HyperplanelhPlane;

//左超平面

HyperplanerhPlane;

//右超平面

Point center;

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

int radius;

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

bool overlapping;

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

boolisleaf;

//是否為葉子結點標志，初始值為false

};

structHyperplane

{Point PointOnPlane;

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

NormalVectornVector;

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

};

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

(2) SP-Tree的建立算法

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

步驟2創建根結點RootNode，入隊；

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

步驟4轉向步驟3執行。

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

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

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

步驟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，統計v-lpv在RootNode.hPlane.nVector上的投影值，找出所有投影值的中位數median，則RootNode.hPlane.PointOnPlane = lpv+median/dist(RootNode.hPlane.nVector)*RootNode.hPlane.nVector。

(5) 結點分割算法

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

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

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

步驟3分別作如下操作：

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

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

③ 判斷(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左右兩側的特征點；

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

(6) 最近鄰查詢

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

5實驗結果與分析

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

圖3　Lena圖像

圖4　三種匹配算法的比較

圖5　Building圖像

圖6　三種匹配算法的比較

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

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

6結語

本文給出SP-Tree結構的定義，并對特征點建樹、最近鄰匹配點搜索過程進行詳細說明，消除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].計算機技術與發展,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算法實現快速圖像匹配[J].紅外與激光工程,2008,37(1):181-184.

[13] 鄭永斌,黃新生,豐松江.SIFT和旋轉不變LBP相結合的圖像匹配算法[J].計算機輔助設計與圖形學學報,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].計算機與數字工程,2012,40(2):96-98,126.

[17] 王永明,王貴錦.圖像局部不變性特征與描述[M].北京:國防工業出版社,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] 傅衛平,秦川,劉佳,等.基于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)；國家高技術研究發展計劃項目(2010CB7315022)；工業裝備結構分析國家重點實驗室專項基金項目(S09104)。楊松，副教授，主研領域：數字圖像處理，模式識別。邵龍潭，教授。宋維波，講師。劉威，講師。

中圖分類號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