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

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

?

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

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

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

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

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

0引言

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

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

1SIFT特征描述

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

圖1　SIFT特征點(diǎn)示意圖

2特征向量匹配算法

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

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

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

3最近鄰搜索算法

3.1Metric-Tree[20]

Metric-Tree是一棵二叉樹(shù)，它的結(jié)點(diǎn)都是點(diǎn)的集合，根結(jié)點(diǎn)代表了所有點(diǎn)的集合。對(duì)于非葉子結(jié)點(diǎn)v所代表的集合N(v)被分割成兩個(gè)子集，分別用v的兩個(gè)孩子結(jié)點(diǎn)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é)點(diǎn)分割算法

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

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

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

(3)

步驟3每個(gè)結(jié)點(diǎn)包含一個(gè)中心點(diǎn)為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ǔ)上改進(jìn)的，在超平面L左右兩側(cè)以距離τ為間距分別作平行于超平面L的超平面LL和LR。

N(v)中LL右側(cè)的點(diǎn)劃分到v.rc中，LR左側(cè)的點(diǎn)劃分到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改進(jìn)的SP-Tree搜索

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

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

4.3近似的最近鄰搜索

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

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

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

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

structSpTreeNode

{

set N;

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

SpTreeNode *lc;

//左孩子指針

SpTreeNode *rc;

//右孩子指針

HyperplanehPlane;

//超平面

HyperplanelhPlane;

//左超平面

HyperplanerhPlane;

//右超平面

Point center;

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

int radius;

//該特征點(diǎn)集空間的超球半徑，初始值為0

bool overlapping;

//是否重疊劃分標(biāo)志，初始值為false

boolisleaf;

//是否為葉子結(jié)點(diǎn)標(biāo)志，初始值為false

};

structHyperplane

{Point PointOnPlane;

//超平面上一點(diǎn)，默認(rèn)值為空間原點(diǎn)

NormalVectornVector;

//超平面法向量，默認(rèn)值為零向量

};

//用超平面上一點(diǎn)和其法向量表示該超平面

(2) SP-Tree的建立算法

步驟1初始化一個(gè)SpTreeNode隊(duì)列；

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

步驟3若隊(duì)列非空，取出隊(duì)首元素SpCurNode，判斷該結(jié)點(diǎn)包含的特征點(diǎn)集合大?。蝗舸笥谌~子結(jié)點(diǎn)允許包含的最大特征點(diǎn)數(shù)，則按照分割算法來(lái)分割該結(jié)點(diǎn)為兩個(gè)結(jié)點(diǎn)lcNode和rcNode，SpCurNode.lc = &lcNode，SpCurNode.rc = &rcNode，并將lcNode和rcNode入隊(duì)；否則，修改結(jié)點(diǎn)的isleaf標(biāo)志，隊(duì)首元素直接出隊(duì)；若隊(duì)列為空，則退出算法；

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

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

步驟1初始化一個(gè)SpTreeNode型變量RootNode；

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

步驟3計(jì)算RootNode.center(為了減小時(shí)間復(fù)雜度，取所有特征向量對(duì)應(yīng)維度上最大最小值的平均值作為中心點(diǎn)在該維度上的值)；

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

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

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

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

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

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

(5) 結(jié)點(diǎn)分割算法

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

步驟1初始化兩個(gè)SpTreeNode：lcNode、rcNode；

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

步驟3分別作如下操作：

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

② 首先用lcN、rlN分別記錄rhPlane和lhPlane的右側(cè)和左側(cè)的特征點(diǎn)，并計(jì)算點(diǎn)數(shù)rhpCount、lhpCount；可以通過(guò)特征點(diǎn)與超平面上的點(diǎn)組成的向量在超平面上法向量上的投影的正負(fù)來(lái)判斷在超平面的哪一側(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è)的特征點(diǎn)；

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

(6) 最近鄰查詢

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

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

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

圖3　Lena圖像

圖4　三種匹配算法的比較

圖5　Building圖像

圖6　三種匹配算法的比較

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

表1　三種匹配方法實(shí)驗(yàn)結(jié)果對(duì)比(匹配時(shí)間:s)

6結(jié)語(yǔ)

本文給出SP-Tree結(jié)構(gòu)的定義，并對(duì)特征點(diǎn)建樹(shù)、最近鄰匹配點(diǎn)搜索過(guò)程進(jìn)行詳細(xì)說(shuō)明，消除KD-Tree樹(shù)搜索過(guò)程的“回溯”問(wèn)題。通過(guò)對(duì)標(biāo)準(zhǔn)圖像進(jìn)行SIFT特征匹配實(shí)驗(yàn)，并與原有的匹配算法和BBF-KD-Tree匹配算法進(jìn)行比較得出，本文算法在減少部分匹配點(diǎn)對(duì)的同時(shí)，其匹配速度有顯著的提升，可應(yīng)用于特征點(diǎn)實(shí)時(shí)匹配過(guò)程。

參考文獻(xiàn)

[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].計(jì)算機(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] 王劍,周?chē)?guó)民.圖像三維重建中的特征點(diǎn)匹配方法研究[J].計(jì)算機(jī)工程與應(yīng)用,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].寧波大學(xué)學(xué)報(bào):理工版,2005,18(3):336-339.

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

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

[14] 石釗銘,耿伯英,董銀文.基于改進(jìn)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].計(jì)算機(jī)與數(shù)字工程,2012,40(2):96-98,126.

[17] 王永明,王貴錦.圖像局部不變性特征與描述[M].北京:國(guó)防工業(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算法的圖形目標(biāo)匹配與定位[J].儀器儀表學(xué)報(bào),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。國(guó)家自然科學(xué)基金項(xiàng)目(50905022，5130 9047)；國(guó)家高技術(shù)研究發(fā)展計(jì)劃項(xiàng)目(2010CB7315022)；工業(yè)裝備結(jié)構(gòu)分析國(guó)家重點(diǎn)實(shí)驗(yàn)室專(zhuān)項(xiàng)基金項(xiàng)目(S09104)。楊松，副教授，主研領(lǐng)域：數(shù)字圖像處理，模式識(shí)別。邵龍?zhí)?，教授。宋維波，講師。劉威，講師。

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

文獻(xiàn)標(biāo)識(shí)碼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