一種基于參考點(diǎn)距離的SIFT特征點(diǎn)匹配算法

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150402.1518.001.html

一種基于參考點(diǎn)距離的SIFT特征點(diǎn)匹配算法

唐坤1，韓斌2

(1.東南大學(xué) 交通學(xué)院，江蘇 南京 210096；2.江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212000)

摘要：針對(duì)SIFT特征點(diǎn)匹配時(shí)間消耗大的問(wèn)題，提出了一種基于參考點(diǎn)距離的SIFT特征點(diǎn)匹配算法—DRP算法。該算法首先計(jì)算一次所有待匹配特征點(diǎn)到參考點(diǎn)之間的距離，對(duì)之進(jìn)行快速排序并保存。然后計(jì)算待查詢特征點(diǎn)到參考點(diǎn)的距離，并在已排序的距離中使用二分法搜索返回此距離的最近鄰。最后以此最近鄰為中心，在有限范圍內(nèi)搜索待查詢特征點(diǎn)的近似最近鄰。VGG實(shí)驗(yàn)室ACF圖片庫(kù)的測(cè)試結(jié)果表明，相比于經(jīng)典的SIFT算法，DRP算法可以在不損失匹配效果的前提下，有效降低SIFT特征點(diǎn)匹配的時(shí)間消耗。

關(guān)鍵詞：SIFT；DRP算法；特征點(diǎn)匹配；最近鄰；參考點(diǎn)

DOI:10.3969/j.issn.1673-4785.201311020

中圖分類號(hào)：TP319 文獻(xiàn)標(biāo)志碼：A

收稿日期：2013-11-28. 網(wǎng)絡(luò)出版日期：2014-04-02.

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61374195)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目；江蘇省普通高校研究生科研創(chuàng)新計(jì)劃資助項(xiàng)目(KYLX_0180).

作者簡(jiǎn)介：

中文引用格式：唐坤，韓斌. 一種基于參考點(diǎn)距離的SIFT特征點(diǎn)匹配算法[J]. 智能系統(tǒng)學(xué)報(bào), 2015, 10(3): 376-380.

英文引用格式：TANG Kun, HAN Bin. A SIFT matching algorithm based on the distance to reference point[J]. CAAI Transactions on Intelligent Systems, 2015, 10(3): 376-380.

A SIFT matching algorithm based on the distance to reference point

TANG Kun1, HAN Bin2

(1. School of Transportation, Southeast University, Nanjing 210096, China; 2. School of Computer Science and Engineering, Jiangsu University of Science and Technology, Zhenjiang 212000, China)

Abstract：To address the high time cost of feature point matching in scale invariant feature transform (SIFT), a new SIFT feature point matching algorithm based on the distance to reference point—DRP algorithm is put forward. Firstly, distances from the reference point to every feature point to be matched is computed using DRP algorithm. Then, these distances computed previously is ordered and saved in a dataset named as distance of ordering. Next, distances from the reference point to the feature point to be queried is also computed. After that, the nearest neighbor of the distance in distance of ordering is retrieved with binary search and returned as index of center. Finally, the nearest neighbor of feature point to be queried is searched one by one in a certain range whose center is index of center. It is proven by experiment tested on ACF (affine covariant features) pictures from VGG(visual geometry group) laboratory that DRP algorithm can effectively decrease the time cost of SIFT feature points matching without loss of matching results compared with the classical SIFT algorithm.

Keywords：scale invariant feature transform (SIFT); distance to reference point (DRP) algorithm; feature point matching; nearest neighbor; reference point

通信作者：唐坤. E-mail: tkpaperzc@sina.cn.

Lowe提出的尺度不變特征變換(scale invariant feature transform, SIFT)[1]是一種魯棒性強(qiáng)的圖像局部特征提取算法，具有對(duì)旋轉(zhuǎn)、光照、尺度變化等保持不變性[2]，廣泛應(yīng)用于三維重建、目標(biāo)識(shí)別、圖像融合等領(lǐng)域[3]。SIFT算法由特征點(diǎn)檢測(cè)及描述與特征點(diǎn)匹配兩部分構(gòu)成，其中，SIFT特征點(diǎn)匹配實(shí)質(zhì)上可以轉(zhuǎn)化為在高維空間中搜索特征點(diǎn)最近鄰的問(wèn)題，并且在很多情況下，只需要得到查詢特征點(diǎn)的近似最近鄰就足夠了[4]。據(jù)此近年來(lái)提出了一些相關(guān)算法，其中，Lowe提出的最優(yōu)節(jié)點(diǎn)優(yōu)先算法(best bin first, BBF)[5]在K-D樹(shù)索引的基礎(chǔ)上，使用優(yōu)先隊(duì)列和限制回溯查詢次數(shù)來(lái)提高搜索最近鄰的效率。va+-file算法[6]將數(shù)據(jù)集轉(zhuǎn)換到KLT域，然后采用均勻量化劃分來(lái)提高va-file算法[7]的過(guò)濾效率。iDistance算法[8]對(duì)高維數(shù)據(jù)空間進(jìn)行劃分，使用B+-tree結(jié)果來(lái)組織參考點(diǎn)并搜索最近鄰。LSH(locality sensitive hashing, LSH)算法[9-10]通過(guò)Hash函數(shù)將鄰近高維點(diǎn)集映射到Hash表的同一個(gè)桶中，從而提高搜索最近鄰效率?；诰垲惙治龅腂+-tree算法[11]采用類B+-tree索引結(jié)構(gòu)，通過(guò)更加細(xì)致的劃分?jǐn)?shù)據(jù)來(lái)加快搜索速度。MRSVQH[12]根據(jù)選擇子向量的L2范數(shù)來(lái)量化和散列特征向量，僅考慮具有與查詢向量相同Hash值的集合，從而提高了搜索速度。

本文在以上研究的基礎(chǔ)上，提出了一種基于參考點(diǎn)距離的SIFT特征點(diǎn)匹配算法—DRP算法，并通過(guò)實(shí)驗(yàn)與經(jīng)典的BBF算法相比，來(lái)驗(yàn)證基于DRP算法的SIFT特征點(diǎn)匹配效果。

1DRP算法

1.1DRP算法原理

設(shè)d維歐式空間Rd中2個(gè)點(diǎn)P1=(x1,x2,…,xd)，P2=(y1,y2,…,yd)，兩點(diǎn)對(duì)應(yīng)的向量分別為V1=[x1x2…xd]，V2=[y1y2…yd]。則P1、P2兩點(diǎn)之間的歐式距離D(P1,P2)為

(1)

若集合Fd中所有特征點(diǎn)與設(shè)定參考點(diǎn)Pr構(gòu)成的向量PrPi與PrPquery之間的夾角不都為θ時(shí)，即不相等時(shí)，上述結(jié)論并不一定成立。如圖1的三維空間所示。

圖1　不同夾角時(shí)的最小距離 Fig. 1　The minimum distance of different angle

圖2　在一定區(qū)域內(nèi)搜索最近鄰 Fig. 2　Search the nearest neighbor in a specified area

1.2DRP算法描述

設(shè)d維歐式空間Rd中的2個(gè)點(diǎn)集合：

圖3　DRP算法搜索最近鄰 Fig. 3　Search the nearest neighbor with DRP algorithm

基于以上分析，在向量集合Fd中搜索向量Vq的最近鄰的步驟如下：

1)在d維歐式空間Rd中任意選取一點(diǎn)Pr作為參考點(diǎn)，設(shè)定一個(gè)閾值th(正整數(shù))。

2)對(duì)于任一屬于集合Fd中的點(diǎn)Pi(i=1,2,…,m)，計(jì)算其與參考點(diǎn)Pr之間的距離，保存于數(shù)組Dri中，并建立Dri與Pi的映射。

在步驟6)中涉及到距離的計(jì)算，為進(jìn)一步提高算法的效率，均采用如下所述的距離累計(jì)算法。當(dāng)d維點(diǎn)Px與Pquery的前i(i∈[1,d])維的歐式距離已經(jīng)超過(guò)上一次比較的最小距離時(shí)，無(wú)論后面d-i維的距離情況如何，將必定大于已經(jīng)產(chǎn)生的最小距離。因此，也無(wú)需計(jì)算它們后面d-i維的距離，直接剔除跳出，進(jìn)行下一特征點(diǎn)的比較。

2SIFT特征點(diǎn)快速匹配算法

SIFT算法提取的圖像特征點(diǎn)包括極大值與極小值2種類型，顯而易見(jiàn)，只有極值類型相同的特征點(diǎn)才可能正確匹配。因此，本文在特征點(diǎn)匹配之前進(jìn)行特征點(diǎn)類型的判斷，僅當(dāng)2個(gè)特征點(diǎn)具有相同類型時(shí)，才進(jìn)行接下來(lái)的匹配運(yùn)算，否則直接跳出，轉(zhuǎn)而比較下一個(gè)特征點(diǎn)。這在一定程度上可以提高匹配的效率。

對(duì)于2幅含有同一場(chǎng)景的圖像Iq(x,y)和Is(x,y)，本文介紹的DRP算法按如下步驟進(jìn)行。

3)采用隨機(jī)抽樣一致性原則(randomsampleconsensus,RANSAC)算法剔除誤匹配的特征點(diǎn)。

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

本文實(shí)驗(yàn)采用的代碼由GitHub上Rob Hess維護(hù)的Opensift庫(kù)[13]改進(jìn)而來(lái)。實(shí)驗(yàn)采用的測(cè)試圖片來(lái)自牛津大學(xué)VGG實(shí)驗(yàn)室的Affine Covariant Features(ACF)圖片庫(kù)[14]。實(shí)驗(yàn)硬件環(huán)境為CPU Inter(R) Core(TM)2 T6600，主頻2.20 GHz，內(nèi)存2 GB DDR3 RAM；軟件環(huán)境為OS Windows7 32 bit、IDE Microsoft Visual Studio 2010、 GTK+2.24圖形工具包和Opencv2.4機(jī)器視覺(jué)庫(kù)。

(a) 特征點(diǎn)正確匹配率與搜索閾值th的關(guān)系

(b)正確匹配特征點(diǎn)總數(shù)與搜索閾值th的關(guān)系

(c)平均匹配時(shí)間與搜索閾值th的關(guān)系

由圖4(a)可知，在特征點(diǎn)正確匹配率方面，DRP算法與BBF算法具有相同的趨勢(shì)。當(dāng)搜索閾值th小于200時(shí)，隨著th的增大而增大；當(dāng)搜索閾值th大于200時(shí)，特征點(diǎn)正確匹配率很難得到進(jìn)一步的改善，趨于穩(wěn)定。總體來(lái)看，這2個(gè)算法在特征點(diǎn)匹配率的表現(xiàn)上相差無(wú)幾。由圖4(b)可知，在正確匹配特征點(diǎn)總數(shù)方面，DRP的算法略遜于BBF算法，但是，隨著搜索閾值th的增大，兩者的差距逐漸縮小。由圖4(c)可知，在匹配時(shí)間上，DRP算法與BBF算法都隨著搜索閾值th的增大而呈線性增長(zhǎng)趨勢(shì)，但是，BBF的增長(zhǎng)速率顯著大于DRP算法，由此可知，在匹配時(shí)間上，DRP算法較BBF算法具有明顯的優(yōu)勢(shì)。綜上所述，相對(duì)于經(jīng)典的BBF算法，本文介紹的DRP算法能獲得滿意匹配效果的同時(shí)，有效降低匹配時(shí)間。

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

本文介紹了一種基于參考點(diǎn)距離的SIFT特征點(diǎn)匹配算法，并使用牛津大學(xué)VGG實(shí)驗(yàn)室的ACF圖片庫(kù)進(jìn)行SIFT特征點(diǎn)匹配實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，與經(jīng)典BBF最近鄰搜索算法相比，使用本文介紹的DRP算法進(jìn)行SIFT特征點(diǎn)匹配，不僅可以獲得滿意的匹配效果，并且可以有效地降低匹配時(shí)間消耗，提高匹配速度。尤其在搜索閾值th較大的情況下，DRP算法在時(shí)間成本上較經(jīng)典的BBF算法具有明顯的優(yōu)勢(shì)。另外，DRP算法還有一些可以改進(jìn)的地方，如對(duì)提取的SIFT特征點(diǎn)分布情況進(jìn)行分析、參考點(diǎn)選擇方法的分析等都可能進(jìn)一步提高特征點(diǎn)的匹配效率。對(duì)于不同的特征點(diǎn)分布情況，如何選取一個(gè)合適的參考點(diǎn)，從而盡可能改善匹配效果是下一步的工作重心。

參考文獻(xiàn):

[1]LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[2]吳偉交, 王敏, 黃心漢, 等. 基于向量夾角的SIFT特征點(diǎn)匹配算法[J]. 模式識(shí)別與人工智能, 2013, 26(1): 123-127.

WU Weijiao, WANG Min, HUANG Xinhan, et al. SIFT feature matching algorithm based on vector angle. Pattern Recognition and Artificial Intelligence, 2013, 26(1): 123-127.

[3]KRYSTIAN M, CORDELIA S. A performance evaluation of local descriptors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10): 1615-1630.

[4]GIONIS A, INDYK P, MOTWANI R. Similarity search in high dimensions via hashing[C]//Proceedings of the 25th International Conference on Very Large Data Bases. San Francisco, USA, 1999: 518-529.

[5]BEIS J S, LOWE D G. Shape indexing using approximate nearest-neighbor search in high-dimensional spaces[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. San Juan, Puerto Rico, 1997: 1000-1006.

[6]FERHATOSMANOGLU H, TUNCEL E, AGRAWAL D, et al. Vector approximation based indexing for non-uniform high dimensional data sets[C]//Proceedings of the International Conference on Information and Knowledge Management. McLean, USA, 2000: 202-209.

[7]WEBER R, SCHEK H J, BLOTT S. A quantitative analysis and performance study for similarity-search methods in high dimensional spaces[C]//Proceedings of the International Conference on Very Large Databases. New York, 1998: 194-205.

[8]JAGADISH H V, OOI B C, TAN K L, et al. IDistance: an adaptive B+-tree based indexing method for nearest neighbor search[J]. ACM Transactions on Database Systems, 2005, 30(2): 364-398.

[9]AUCLAIR A, COHEN L D, VINCENT N. How to use SIFT vectors to analyze an image with database templates[C]//Proceedings of the 5thInternational Workshop on Adaptive Multimedia Retrieval. Paris, France, 2008: 224-236.

[10]SLANEY M, CASEY M. Locality-sensitive hashing for finding nearest neighbors[J]. IEEE Signal Processing Magazine, 2008, 25(2): 128-131.

[11]張軍旗, 周向東, 王梅, 等. 基于聚類分解的高維度量空間索引B+-tree[J]. 軟件學(xué)報(bào), 2008, 19(6): 1401-1412.

ZHANG Junqi, ZHOU Xiangdong, WANG Mei, et al. Cluster splitting based high dimensional metric space index B+-tree[J]. Journal of Software, 2008, 19(6): 1401-1412.

[12]楊恒, 王慶, 何周燦. 面向高維圖像特征匹配的多次隨機(jī)子向量量化哈希算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2010, 22(3): 494-502.

YANG Heng, WANG Qing, HE Zhoucan. Mutiple randomized sub-vectors quantization hashing for high-dimensional image feature matching[J]. Journal of Computer-Aided Deasign & Computer Graphics, 2010, 22(3): 494-502.

[13]LOWE D. OpenSIFT—An open-source SIFT library[EB/OL]. [2013-11-15]. http://robwhess.github.io/opensift/.

[14]The Visual Geometry Group. Affine covariant features[EB/OL]. (2007-07-15)[2013-11-15]. http://www.robots.ox.ac.uk/~vgg/research/affine/index.html.

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

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