唐坤，韓斌（江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇鎮(zhèn)江212000）

一種自適應(yīng)搜索范圍的SIFT特征點(diǎn)快速匹配算法

唐坤，韓斌
（江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇鎮(zhèn)江212000）

針對(duì)SIFT特征向量匹配時(shí)間成本高的問(wèn)題，提出了一種自適應(yīng)搜索范圍的快速匹配算法－AutoARV＆DP。該算法首先根據(jù)特征向量集合計(jì)算一個(gè)合適的參考向量，然后自適應(yīng)確定一個(gè)搜索范圍，最后在一個(gè)通過(guò)距離過(guò)濾后的較小搜索空間中進(jìn)行特征向量匹配。實(shí)驗(yàn)結(jié)果表明，與經(jīng)典的BBF算法相比較，AutoARV＆在獲得滿(mǎn)意匹配效果的同時(shí)，能夠有效地降低SIFT特征點(diǎn)匹配的時(shí)間成本。

SIFT；AutoARV＆DP；特征點(diǎn)匹配；搜索范圍；BBF算法

尺度不變特征變換［1］（scale invariant feature transform，SIFT）作為一種穩(wěn)定性好、魯棒性強(qiáng)的局部特征點(diǎn)提取算法，在目標(biāo)識(shí)別、三維重建、圖像拼接、運(yùn)動(dòng)分析等領(lǐng)域得到廣泛的應(yīng)用［2］。然而，由于SIFT算法的時(shí)間復(fù)雜度較高，制約了該算法在實(shí)時(shí)性較高場(chǎng)合的應(yīng)用。近年來(lái)，針對(duì)SIFT算法時(shí)間成本較高的問(wèn)題，提出了一些改進(jìn)方法。Bay等［3］提出的SURF（speeded up robust features）算法，Yan等［4?5］提出的PCA?SIFT算法，都在特征點(diǎn)檢測(cè)和描述方面進(jìn)行了改進(jìn)。而SIFT特征點(diǎn)的匹配實(shí)質(zhì)上是高維空間中特征向量的最近鄰搜索問(wèn)題。并且，在很多情況下，搜索某個(gè)特征向量的最近鄰并不是必須的［6］，只要得到它的近似最近鄰就可以了?；诖?，目前常用于SIFT特征點(diǎn)匹配近似最近鄰搜索算法有最優(yōu)節(jié)點(diǎn)優(yōu)先算法［7］（best bin first，BBF）、局部敏感哈希［8?9］（locality sensitive hashing，LSH）以及近似最近鄰搜索快速算法庫(kù)［10?11］（fast library for ap?proximate nearest neighbors，F(xiàn)LANN）等。

本文在大量SIFT特征點(diǎn)快速匹配算法的研究基礎(chǔ)上，基于參考向量夾角和點(diǎn)距離，提出了一種自適應(yīng)搜索范圍的近似最近鄰搜索算法—AutoARV＆DP（auto angle of reference vector＆dis?tance of point）用于SIFT特征點(diǎn)匹配。與BBF算法的對(duì)比實(shí)驗(yàn)表明，使用AutoARV＆DP算法進(jìn)行SIFT特征點(diǎn)匹配能夠獲得滿(mǎn)意的匹配效果，同時(shí)有效地降低了SIFT特征點(diǎn)匹配的時(shí)間成本。

1 問(wèn)題描述

使用SIFT作用圖像I1（x，y），檢測(cè)出m個(gè)特征點(diǎn)，各特征點(diǎn)對(duì)應(yīng)的特征向量構(gòu)成向量集合：

若在圖像I1（x，y）與圖像I2（x，y）之間進(jìn)行特征點(diǎn)匹配，即是對(duì)?Vx∈F1（或者?Px∈F1′），從集合F2（或者F2′）中搜索與Vx（或者Px）的最近鄰的向量Vx_nearest（或者Px_nearest）。其中，近鄰度一般用歐式空間距離來(lái)度量。

2 自適應(yīng)搜索范圍的快速匹配算法?AutoARV＆DP

2.1 AutoARV＆DP算法基本原理

對(duì)于任一查詢(xún)向量?Vq∈F1，需要在集合F2中搜索Vq的最近鄰Vq_nearest。引入一個(gè)參考向量Vr∈R128，對(duì)于?Vi∈F2，i＝1，2，…n，計(jì)算其與Vr的夾角并排序保存。求出Vq與參考向量Vr之間的夾角θ，然后在向量集合F2″中搜索，就可能得到Vq的真正最近鄰［12］。

如圖1所示的三維歐式空間，只需要在Vr為軸心，頂角為θ－Δθ的圓錐以外和頂角為θ＋Δθ的圓錐以?xún)?nèi)的圓錐環(huán)Π空間內(nèi)搜索，就可能得到向量Vq的真正最近鄰。并且隨著Δθ的增大，搜索到Vq_nearest的概率也隨之增大。

2.2 自適應(yīng)搜索范圍

由以上分析可知，選取一個(gè)合適的搜索范圍Δθ是搜索到查詢(xún)向量Vq最近鄰的關(guān)鍵。Δθ太大，導(dǎo)致較多的無(wú)效搜索，增加了算法的時(shí)間成本，Δθ太小，可能無(wú)法找到Vq的真正最近鄰。針對(duì)此，本文提出了一種自適應(yīng)搜索范圍的搜索方法。參考圖1，若集合F2中，Vm與Vr的夾角〈Vr，Vm〉最接近Vq與Vr的夾角〈Vr，Vq〉，則Vq的真實(shí)最近鄰必定落在以Vq為中心，VqVm為半徑的球Ω中，據(jù)以上分析可知，若球Ω在圓錐環(huán)Π中，則必定能搜索到Vq的真實(shí)最近鄰。對(duì)此，本文分2種情形分析。

1）Vm落在以Vq為中心，VqVr為半徑的球中以向量Vq與Vr構(gòu)成的平面α截取圖1，截面圖如圖2所示。

圖1 鄰域內(nèi)搜索最近鄰Fig.1 Search in the neighborhood area

圖2 情形1截面圖Fig.2 Sectional view of situation one

2）Vm落在以Vq為中心，VqVr為半徑的球外，以向量Vq與Vr構(gòu)成的平面α截取圖1，截面圖如圖3所示。

圖3 情形2截面圖Fig.3 Sectional view of situation two

2.3 距離篩選

經(jīng)過(guò)2.2中的自適應(yīng)角度篩選后，一般來(lái)講，對(duì)于?Vq∈F1，都需要對(duì)角度篩選后的向量集合F″angle中的所有向量進(jìn)行比較。然而，由圖1可知，Vq的真實(shí)最近鄰必定落在以Vq為中心，VqVm為半徑的球Ω中。設(shè)點(diǎn)Px為球Ω中的點(diǎn)，則有

OPx∈[Vq－VqVm，Vq＋VqVm]，因此，為了進(jìn)一步減少無(wú)效搜索，對(duì)于以上角度篩選后的向量集合F″angle，只需要考慮其中模值在上述范圍中的向量即可。也即將搜索范圍進(jìn)一步縮小為

也就是說(shuō)，只需要在F″angle＋dist中搜索，便可以找到Vq的真實(shí)最近鄰。直觀上來(lái)看，經(jīng)過(guò)角度和距離篩選后的搜索空間如圖4所示，為一個(gè)以Vq為中心，VqVm為半徑的球在以Vr為法線且經(jīng)過(guò)Vq的平面上繞Vr旋轉(zhuǎn)一周形成的類(lèi)似于泳圈的空間。

2.4 參考向量選取

由于對(duì)于?Vq∈F1，都需要計(jì)算查詢(xún)向量Vq與參考向量Vr時(shí)間的夾角〈Vq，Vr〉，并依此為依據(jù)在集合F2中搜索Vm，繼而搜索Vq的最近鄰。因此，參考向量Vr的選取關(guān)系到最終的匹配效果。設(shè)參考向量Vr與集合F2中所有向量之間構(gòu)成的夾角構(gòu)成集合

圖4 距離篩選后的搜索空間Fig.4 The search area after distance filtering

顯然，Qangle中的任一元素滿(mǎn)足∈［0，π］。若Qangle中的元素服從［0，π］上均勻分布，即Qangle～U［0，π］。則能避免向量集中搜索增加搜索的時(shí)間成本，同時(shí)保證以較快的速度和較大的概率搜索到Vq的真實(shí)最近鄰?；诖?，參考向量Vr在128維空間中對(duì)應(yīng)的點(diǎn)＝（，，…，應(yīng)該處于F2′的中心，即要求點(diǎn)到中各點(diǎn)的距離和最小，即要求d最小。

由于距離均大于零，要最小化d，即

對(duì)上式求導(dǎo)并另其等于零［13］，則可解得

直觀上來(lái)看，即當(dāng)點(diǎn)P1r28的各維取樣本各維的均值時(shí)，其對(duì)應(yīng)的向量為最佳參考向量Vr。

2.5 算法描述

基于以上分析，對(duì)于?Vq∈F1，在向量集合F2中搜索向量Vq的最近鄰的步驟如下：

1）根據(jù)集合F2，計(jì)算參考向量Vr。

2）對(duì)于任一屬于集合F2中向量Vi，計(jì)算其與參考向量Vr之間的夾角，保存于數(shù)組Angleri中，并建立Angleri與Vi的映射。然后對(duì)Angleri中的元素按照升序（或降序）進(jìn)行排序得到Angleri_order。

3）對(duì)于?Vq∈F1，計(jì)算其與Vr之間的夾角θ。然后從Angleri_order中搜索并返回與θ最相近的元素對(duì)應(yīng)的向量Vm。

4）計(jì)算Vq與Vm之間的距離VqVm以及Vq，得到Δθ＝arcsin(VqVm／Vq)

5）在Angleri_order中，保留所有夾角在范圍[θ－Δθ，θ＋Δθ]中的對(duì)應(yīng)向量，得到角度篩選后的向量集合Vangle。

6）計(jì)算集合Vangle中所有向量的模，若模屬于范圍[Vq－VqVm，Vq＋VqVm]，則保留，否則剔除。得到模篩選后的向量集合Vangle＋norm。

7）使用窮舉搜索法在Vangle＋norm中搜索待匹配向量Vq的最近鄰Vq_nearest。

6）中，若向量Vx的前i（i∈［1，128］）維的模已經(jīng)大于Vq＋VqVm，則無(wú)需進(jìn)行后面維度的計(jì)算，直接剔除，且Vangle中所有向量的模只需計(jì)算一次。7）中，若向量Vy與Vq的前j（j∈［1，128］）維的歐式距離已經(jīng)超過(guò)上一次比較的最小距離時(shí)，直接剔除跳出，進(jìn)行下一向量的比較。7）中，為了避免可能由于集合Vangle＋norm中特征向量分布過(guò)于集中而導(dǎo)致的過(guò)多無(wú)效搜索，本文設(shè)定一個(gè)搜索次數(shù)上限值Seektimesth

3 基于AutoARV＆DP的SIFT特征點(diǎn)快速匹配算法

本文的基本思想是首先利用SIFT算法分別提取含有同一目標(biāo)的2幅圖像的特征點(diǎn)，然后使用本文介紹的AutoARV＆DP算法進(jìn)行特征點(diǎn)的匹配。SIFT算法提取的特征點(diǎn)包括極大值點(diǎn)與極小值點(diǎn)2種類(lèi)型［1］，正確匹配的特征點(diǎn)之間具有相同的極值類(lèi)型，基于此，在進(jìn)行特征點(diǎn)匹配之前，首先進(jìn)行特征點(diǎn)類(lèi)型的判斷，如同類(lèi)型，才進(jìn)行后續(xù)的匹配計(jì)算，否則直接跳出進(jìn)行下一個(gè)特征點(diǎn)比較，這可進(jìn)一步提高匹配的速度。

對(duì)于含有同一目標(biāo)的2幅圖像I1（x，y）和I2（x，y），本文介紹的特征點(diǎn)快速匹配算法具體步驟如下所述：

1）使用SIFT算法提取圖像I1（x，y）的特征點(diǎn)，生成的特征向量構(gòu)成集合F1，提取圖像I2（x，y）的特征點(diǎn)，生成的特征向量構(gòu)成集合F2。

2）對(duì)于?Vq∈F1，基于本文描述，使用AutoARV＆DP算法在F2中搜索得到Vq的最近鄰特征向量Vq_nearest，對(duì)應(yīng)的最近鄰距離為distnearest，次近鄰特征向量Vq_nearest2，對(duì)應(yīng)的次近鄰距離distnearest2，若小于設(shè)定的閾值ratio，則認(rèn)為V與thq正確匹配［1］。

3）使用隨機(jī)抽樣一致性（RANSAC）算法消除誤匹配的特征點(diǎn)。

4 實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證本文算法的性能，本文以GitHub上Rob Hess維護(hù)的Opensift庫(kù)（http：／／robwhess.github.io／opensift／）為基礎(chǔ)，修改相應(yīng)代碼并進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)采用的測(cè)試圖片部分來(lái)自Affine Covariant Features（ACF）測(cè)試圖片庫(kù)（http：／／www.robots.ox.ac.uk／～vgg／research／affine／index.html），部分來(lái)自現(xiàn)場(chǎng)拍攝。實(shí)驗(yàn)硬件環(huán)境：Inter（R）Core（TM）2 Duo CPU T6600，2.20GHz，2.00GBRAM。實(shí)驗(yàn)軟件環(huán)境：MicrosoftWindows7 OS，Microsoft Visual Studio 2010 IDE，Opencv2.4機(jī)器視覺(jué)庫(kù)，GTK＋2.24圖形工具包。

為了驗(yàn)證AutoARV＆DP算法的有效性，本文進(jìn)行了AutoARV＆DP算法與BBF算法在不同變化環(huán)境下的特征匹配對(duì)比實(shí)驗(yàn)以及兩算法在不同規(guī)模特征向量集合下的匹配性能對(duì)比實(shí)驗(yàn)。其中，交叉驗(yàn)證得到兩算法的最近鄰與次近鄰距離閾值比為0.56，且保持不變；AutoARV＆DP算法中的最大搜索次數(shù)閾值Seektimesth＝100；BBF算法中kdtree_bbf_ knn函數(shù)的參數(shù)k＝2（最近鄰和次近鄰），max_nn_ chks＝200，其他參數(shù)保持默認(rèn)。

4.1.不同變化環(huán)境下的特征匹配性能對(duì)比實(shí)驗(yàn)

本實(shí)驗(yàn)比較了在不同的變化環(huán)境下，AutoARV＆DP算法和BBF算法的匹配性能。實(shí)驗(yàn)圖像采用ACF測(cè)試庫(kù)中的Bike（Blur），Graf（View?Point），Boat（Zoom＋Rotation），Leuven（Light），Ubc（JPEG Compression）5組圖片以及一組現(xiàn)場(chǎng)拍攝的書(shū)架圖片，每組圖片包含6張圖片，分別使用BBF算法以及AutoARV＆DP算法對(duì)每組圖片中的img1和img3各進(jìn)行5次匹配實(shí)驗(yàn)，最后使用RANSAC剔除誤匹配，分別求取兩算法平均每次匹配的正確匹配總數(shù)、正確匹配率以及匹配時(shí)間3個(gè)指標(biāo)。實(shí)驗(yàn)結(jié)果如下：

表1 不同變化環(huán)境下的匹配性能Table 1 Performance of matching in different situation

由表1可知，在正確匹配總數(shù)方面，AutoARV＆DP算法稍遜于BBF算法，這可以通過(guò)適當(dāng)增大Seektimesth來(lái)增加匹配總數(shù)；在正確匹配率方面，AutoARV＆DP與BBF算法的表現(xiàn)相差無(wú)幾，前者甚至更加穩(wěn)定；在匹配時(shí)間方面，當(dāng)特征向量集合規(guī)模較小時(shí)，AutoARV＆DP算法與BBF算法相差不大，隨著特征向量集合規(guī)模的增大，前者較后者有明顯的優(yōu)勢(shì)。這是由于AutoARV＆DP僅需在較小的空間中搜索有限的近似最近鄰，而B(niǎo)BF算法基于kd?tree索引進(jìn)行優(yōu)先隊(duì)列查詢(xún)，不但受特征向量集合分布的影響，而且需要較多的回溯查詢(xún)，導(dǎo)致時(shí)間成本較高。由此可知，本文所提出的AutoARV＆DP算法能夠滿(mǎn)足不同變化環(huán)境下的特征點(diǎn)匹配需求，且當(dāng)特征向量集合規(guī)模較大時(shí)，時(shí)間成本上由于BBF算法。

4.2 不同規(guī)模特征向量集合下的性能對(duì)比實(shí)驗(yàn)

本實(shí)驗(yàn)比較了在不同規(guī)模特征向量集合下AutoARV＆DP算法與BBF算法的時(shí)間成本。實(shí)驗(yàn)采用實(shí)驗(yàn)室現(xiàn)場(chǎng)拍攝圖片，共2組，其中，每組20張，10張查詢(xún)圖像，對(duì)應(yīng)10張搜索圖像，特征向量集合的大小10 k～40 k不等。分別使用BBF算法以及AutoARV＆DP算法對(duì)2組圖片進(jìn)行匹配實(shí)驗(yàn)，求取在不同特征向量集合規(guī)模N下，平均每次匹配的時(shí)間消耗。實(shí)驗(yàn)結(jié)果如表2所示：由表2可知，隨著特征向量集合規(guī)模N的增大，BBF算法的匹配時(shí)間急劇增加，本文的AutoARV＆DP算法雖然也有所增加，但其增長(zhǎng)速率遠(yuǎn)低于BBF算法。這是由于本文的AutoARV＆DP算法僅需在較小的空間中搜索有限的近似最近鄰，隨著數(shù)據(jù)規(guī)模的增長(zhǎng)，需要求取更多的夾角和距離來(lái)建立待匹配樣本集，但是，經(jīng)過(guò)AutoARV＆DP算法的夾角和距離篩選后，落在該搜索空間的樣本并不會(huì)急劇增長(zhǎng)，從而降低了時(shí)間消耗。由此可知，在特征向量集合規(guī)模較大的情況下，AutoARV＆DP算法在時(shí)間成本上優(yōu)于BBF算法。

表2 不同特征集合規(guī)模下的匹配性能Table 2 Performance of matching in d ifferent sizes of fea?ture vector set

5 結(jié)束語(yǔ)

本文基于參考向量夾角和點(diǎn)距離，提出了一種自適應(yīng)搜索范圍的近似最近鄰搜索算法AutoARV＆DP用于SIFT特征點(diǎn)匹配。VGG實(shí)驗(yàn)室的ACF測(cè)試圖片庫(kù)與現(xiàn)場(chǎng)圖片的測(cè)試結(jié)果表明，AutoARV＆DP能夠適應(yīng)不同變化環(huán)境，取得較好結(jié)果的同時(shí)，降低時(shí)間成本，尤其在數(shù)據(jù)集規(guī)模較大的情況下，時(shí)間消耗明顯優(yōu)于經(jīng)典的BBF算法。此外，若結(jié)合數(shù)據(jù)集的分布特點(diǎn)，搜索空間還有進(jìn)一步縮小的可能，從而進(jìn)一步提高算法的性能，這將是后期的研究工作重點(diǎn)。

［1］LOWE D G.Distinctive image features from scale?invariant keypoints［J］.International Journal of Computer Vision，2004，60（2）：91?110.

［2］KRYSTIANM，CORDELIA S.A performance evaluation of local descriptors［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2005，27（10）：1615?1630.

［3］BAY SH，TUYTELAARS T，GOOL L V.SURF：speed up robust features［C］／／Proceedings of the European Confer?ence on Computer Vision.Graz，2006：404?417.

［4］YAN K，SUKTHANKAR R.PCA?SIFT：amore distinctive representation for local image descriptors［C］／／Proc of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington，USA，2004：506?513.

［5］FARAJ A，DANIJELA R D，AXEL G.VF?SIFT：very fast sift featurematching［C］／／Proc of the 32nd DAGM Sympo?sium.Darmstadt，Germany，2010：222?231.

［6］GIONIS A，INDYK P，MOTWANIR.Similarity search in high dimensions via hashing［C］／／Proc of the 25th Interna?tional Conference on Very Large Data Bases.San Francisco，USA，1999：518?529.

［7］BEIS JS，LOWE D G.Shape indexing using approximate nearest?neighbor search in high?dimensional spaces［C］／／Proceedings of the CVPR.San Juan，1997：1000?1006.

［8］SLANEY M，CASEY M.Locality?sensitive hashing for find?ing nearest neighbors［J］.IEEE Signal Processing Maga?zine，2008，25（2）：128?131.

［9］何周燦，王慶，楊恒.一種面向快速圖像匹配的擴(kuò)展LSH算法［J］.四川大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，47（2）：269?274.HE Zhoucan，WANG Qin，YANG Heng.An extended local sensitivity hash algorithm for efficient image matching［J］.Journal of Sichuan University：Natural Science Edition，2010，47（2）：269?274.

［10］MUJA M，LOWEDG.Fastapproximate nearestneighbors with automatic algorithm configuration［C］／／International Conference on Computer Vision Theory and Applications（VISAPP’09）.2009：331?340.

［11］MUJA M，LOWE D G.Fastmatching of binary features［C］.Conference on Computer and Robot Vision（CRV）.2012：404?410.

［12］吳偉交，王敏等.基于向量夾角的SIFT特征點(diǎn)匹配算法［J］.模式識(shí)別與人工智能（PR＆AI），2013，26（1）：123?127.WUWeijiao，WANGMin.SIFT featurematching algorithm based on vector angle［J］.Pattern Recognition and Artifi?cial Intelligence（PR＆AI），2013，26（1）：123?127.

［13］同濟(jì)大學(xué)數(shù)學(xué)系.高等數(shù)學(xué)［M］.（6版）（下冊(cè)）.高等教育出版社，2007：109?113.

唐坤，男，1988年生，碩士研究生，主要研究方向?yàn)閿?shù)字圖像處理，人工智能。

韓斌，男，1968年生，教授，博士，主要研究方向?yàn)閿?shù)字圖像處理、智能檢測(cè)、并行計(jì)算。

A new fast algorithm of self?adaptive search scope for SIFT matching

TANG Kun，HAN Bin
（School of Computer Science and Engineering，Jiangsu University of Science and Technology，Zhenjiang 212000，China）

Aiming at the high time cost of feature vectors matching in SIFT，a new fast algorithm，called Auto ARV＆DP，of self?adaptive search scope for SIFTmatching is put forward.Firstly，an appropriate reference vector is computed based on the feature vectors set.Secondly，a self?adaptive search scope is determined by this reference vector.Finally，thematching of SIFT is performed in a small feature vectors set，which is filtered by norm.Experi?mental results showed that compared with the classical BBF algorithm，Auto ARV＆DP can effectively decrease the time cost of feature vectormatching of SIFTwith no loss ofmatching performance when the size of feature vector set is large.

SIFT；Auto ARV＆DP；feature pointsmatching；search scope；BBF

TP319

A

1673?4785（2014）06?0723?06

唐坤，韓斌.一種自適應(yīng)搜索范圍的SIFT特征點(diǎn)快速匹配算法［J］.智能系統(tǒng)學(xué)報(bào)，2014，9（6）：723?728.

英文引用格式：TANG Kun，HAN Bin.A new fast algorithm of self?adaptive search scope for SIFT m atching［J］.CAAI Transac?tions on Intelligent Systems，2014，9（6）：723?728.

10.3969／j.issn.1673?4785.201309037

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1673?4785.201309037.htm l

2013?09?11.

日期：2014?11?13.

唐坤.E?mail：tkpaperzc＠sina.cn.