一种自适应搜索范围的SIFT特征点快速匹配算法

唐坤，韩斌（江苏科技大学计算机科学与工程学院，江苏镇江212000）

一种自适应搜索范围的SIFT特征点快速匹配算法

唐坤，韩斌
（江苏科技大学计算机科学与工程学院，江苏镇江212000）

针对SIFT特征向量匹配时间成本高的问题，提出了一种自适应搜索范围的快速匹配算法－AutoARV＆DP。该算法首先根据特征向量集合计算一个合适的参考向量，然后自适应确定一个搜索范围，最后在一个通过距离过滤后的较小搜索空间中进行特征向量匹配。实验结果表明，与经典的BBF算法相比较，AutoARV＆在获得满意匹配效果的同时，能够有效地降低SIFT特征点匹配的时间成本。

SIFT；AutoARV＆DP；特征点匹配；搜索范围；BBF算法

尺度不变特征变换［1］（scale invariant feature transform，SIFT）作为一种稳定性好、鲁棒性强的局部特征点提取算法，在目标识别、三维重建、图像拼接、运动分析等领域得到广泛的应用［2］。然而，由于SIFT算法的时间复杂度较高，制约了该算法在实时性较高场合的应用。近年来，针对SIFT算法时间成本较高的问题，提出了一些改进方法。Bay等［3］提出的SURF（speeded up robust features）算法，Yan等［4⁃5］提出的PCA⁃SIFT算法，都在特征点检测和描述方面进行了改进。而SIFT特征点的匹配实质上是高维空间中特征向量的最近邻搜索问题。并且，在很多情况下，搜索某个特征向量的最近邻并不是必须的［6］，只要得到它的近似最近邻就可以了。基于此，目前常用于SIFT特征点匹配近似最近邻搜索算法有最优节点优先算法［7］（best bin first，BBF）、局部敏感哈希［8⁃9］（locality sensitive hashing，LSH）以及近似最近邻搜索快速算法库［10⁃11］（fast library for ap⁃proximate nearest neighbors，FLANN）等。

本文在大量SIFT特征点快速匹配算法的研究基础上，基于参考向量夹角和点距离，提出了一种自适应搜索范围的近似最近邻搜索算法—AutoARV＆DP（auto angle of reference vector＆dis⁃tance of point）用于SIFT特征点匹配。与BBF算法的对比实验表明，使用AutoARV＆DP算法进行SIFT特征点匹配能够获得满意的匹配效果，同时有效地降低了SIFT特征点匹配的时间成本。

1 问题描述

使用SIFT作用图像I1（x，y），检测出m个特征点，各特征点对应的特征向量构成向量集合：

若在图像I1（x，y）与图像I2（x，y）之间进行特征点匹配，即是对∀Vx∈F1（或者∀Px∈F1′），从集合F2（或者F2′）中搜索与Vx（或者Px）的最近邻的向量Vx_nearest（或者Px_nearest）。其中，近邻度一般用欧式空间距离来度量。

2 自适应搜索范围的快速匹配算法⁃AutoARV＆DP

2.1 AutoARV＆DP算法基本原理

对于任一查询向量∀Vq∈F1，需要在集合F2中搜索Vq的最近邻Vq_nearest。引入一个参考向量Vr∈R128，对于∀Vi∈F2，i＝1，2，…n，计算其与Vr的夹角并排序保存。求出Vq与参考向量Vr之间的夹角θ，然后在向量集合F2″中搜索，就可能得到Vq的真正最近邻［12］。

如图1所示的三维欧式空间，只需要在Vr为轴心，顶角为θ－Δθ的圆锥以外和顶角为θ＋Δθ的圆锥以内的圆锥环Π空间内搜索，就可能得到向量Vq的真正最近邻。并且随着Δθ的增大，搜索到Vq_nearest的概率也随之增大。

2.2 自适应搜索范围

由以上分析可知，选取一个合适的搜索范围Δθ是搜索到查询向量Vq最近邻的关键。Δθ太大，导致较多的无效搜索，增加了算法的时间成本，Δθ太小，可能无法找到Vq的真正最近邻。针对此，本文提出了一种自适应搜索范围的搜索方法。参考图1，若集合F2中，Vm与Vr的夹角〈Vr，Vm〉最接近Vq与Vr的夹角〈Vr，Vq〉，则Vq的真实最近邻必定落在以Vq为中心，VqVm为半径的球Ω中，据以上分析可知，若球Ω在圆锥环Π中，则必定能搜索到Vq的真实最近邻。对此，本文分2种情形分析。

1）Vm落在以Vq为中心，VqVr为半径的球中以向量Vq与Vr构成的平面α截取图1，截面图如图2所示。

图1 邻域内搜索最近邻Fig.1 Search in the neighborhood area

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

2）Vm落在以Vq为中心，VqVr为半径的球外，以向量Vq与Vr构成的平面α截取图1，截面图如图3所示。

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

2.3 距离筛选

经过2.2中的自适应角度筛选后，一般来讲，对于∀Vq∈F1，都需要对角度筛选后的向量集合F″angle中的所有向量进行比较。然而，由图1可知，Vq的真实最近邻必定落在以Vq为中心，VqVm为半径的球Ω中。设点Px为球Ω中的点，则有

OPx∈[Vq－VqVm，Vq＋VqVm]，因此，为了进一步减少无效搜索，对于以上角度筛选后的向量集合F″angle，只需要考虑其中模值在上述范围中的向量即可。也即将搜索范围进一步缩小为

也就是说，只需要在F″angle＋dist中搜索，便可以找到Vq的真实最近邻。直观上来看，经过角度和距离筛选后的搜索空间如图4所示，为一个以Vq为中心，VqVm为半径的球在以Vr为法线且经过Vq的平面上绕Vr旋转一周形成的类似于泳圈的空间。

2.4 参考向量选取

由于对于∀Vq∈F1，都需要计算查询向量Vq与参考向量Vr时间的夹角〈Vq，Vr〉，并依此为依据在集合F2中搜索Vm，继而搜索Vq的最近邻。因此，参考向量Vr的选取关系到最终的匹配效果。设参考向量Vr与集合F2中所有向量之间构成的夹角构成集合

图4 距离筛选后的搜索空间Fig.4 The search area after distance filtering

显然，Qangle中的任一元素满足∈［0，π］。若Qangle中的元素服从［0，π］上均匀分布，即Qangle～U［0，π］。则能避免向量集中搜索增加搜索的时间成本，同时保证以较快的速度和较大的概率搜索到Vq的真实最近邻。基于此，参考向量Vr在128维空间中对应的点＝（，，…，应该处于F2′的中心，即要求点到中各点的距离和最小，即要求d最小。

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

对上式求导并另其等于零［13］，则可解得

直观上来看，即当点P1r28的各维取样本各维的均值时，其对应的向量为最佳参考向量Vr。

2.5 算法描述

基于以上分析，对于∀Vq∈F1，在向量集合F2中搜索向量Vq的最近邻的步骤如下：

1）根据集合F2，计算参考向量Vr。

2）对于任一属于集合F2中向量Vi，计算其与参考向量Vr之间的夹角，保存于数组Angleri中，并建立Angleri与Vi的映射。然后对Angleri中的元素按照升序（或降序）进行排序得到Angleri_order。

3）对于∀Vq∈F1，计算其与Vr之间的夹角θ。然后从Angleri_order中搜索并返回与θ最相近的元素对应的向量Vm。

4）计算Vq与Vm之间的距离VqVm以及Vq，得到Δθ＝arcsin(VqVm／Vq)

5）在Angleri_order中，保留所有夹角在范围[θ－Δθ，θ＋Δθ]中的对应向量，得到角度筛选后的向量集合Vangle。

6）计算集合Vangle中所有向量的模，若模属于范围[Vq－VqVm，Vq＋VqVm]，则保留，否则剔除。得到模筛选后的向量集合Vangle＋norm。

7）使用穷举搜索法在Vangle＋norm中搜索待匹配向量Vq的最近邻Vq_nearest。

6）中，若向量Vx的前i（i∈［1，128］）维的模已经大于Vq＋VqVm，则无需进行后面维度的计算，直接剔除，且Vangle中所有向量的模只需计算一次。7）中，若向量Vy与Vq的前j（j∈［1，128］）维的欧式距离已经超过上一次比较的最小距离时，直接剔除跳出，进行下一向量的比较。7）中，为了避免可能由于集合Vangle＋norm中特征向量分布过于集中而导致的过多无效搜索，本文设定一个搜索次数上限值Seektimesth

3 基于AutoARV＆DP的SIFT特征点快速匹配算法

本文的基本思想是首先利用SIFT算法分别提取含有同一目标的2幅图像的特征点，然后使用本文介绍的AutoARV＆DP算法进行特征点的匹配。SIFT算法提取的特征点包括极大值点与极小值点2种类型［1］，正确匹配的特征点之间具有相同的极值类型，基于此，在进行特征点匹配之前，首先进行特征点类型的判断，如同类型，才进行后续的匹配计算，否则直接跳出进行下一个特征点比较，这可进一步提高匹配的速度。

对于含有同一目标的2幅图像I1（x，y）和I2（x，y），本文介绍的特征点快速匹配算法具体步骤如下所述：

1）使用SIFT算法提取图像I1（x，y）的特征点，生成的特征向量构成集合F1，提取图像I2（x，y）的特征点，生成的特征向量构成集合F2。

2）对于∀Vq∈F1，基于本文描述，使用AutoARV＆DP算法在F2中搜索得到Vq的最近邻特征向量Vq_nearest，对应的最近邻距离为distnearest，次近邻特征向量Vq_nearest2，对应的次近邻距离distnearest2，若小于设定的阈值ratio，则认为V与thq正确匹配［1］。

3）使用随机抽样一致性（RANSAC）算法消除误匹配的特征点。

4 实验及结果分析

为了验证本文算法的性能，本文以GitHub上Rob Hess维护的Opensift库（http：／／robwhess.github.io／opensift／）为基础，修改相应代码并进行实验。实验采用的测试图片部分来自Affine Covariant Features（ACF）测试图片库（http：／／www.robots.ox.ac.uk／～vgg／research／affine／index.html），部分来自现场拍摄。实验硬件环境：Inter（R）Core（TM）2 Duo CPU T6600，2.20GHz，2.00GBRAM。实验软件环境：MicrosoftWindows7 OS，Microsoft Visual Studio 2010 IDE，Opencv2.4机器视觉库，GTK＋2.24图形工具包。

为了验证AutoARV＆DP算法的有效性，本文进行了AutoARV＆DP算法与BBF算法在不同变化环境下的特征匹配对比实验以及两算法在不同规模特征向量集合下的匹配性能对比实验。其中，交叉验证得到两算法的最近邻与次近邻距离阈值比为0.56，且保持不变；AutoARV＆DP算法中的最大搜索次数阈值Seektimesth＝100；BBF算法中kdtree_bbf_ knn函数的参数k＝2（最近邻和次近邻），max_nn_ chks＝200，其他参数保持默认。

4.1.不同变化环境下的特征匹配性能对比实验

本实验比较了在不同的变化环境下，AutoARV＆DP算法和BBF算法的匹配性能。实验图像采用ACF测试库中的Bike（Blur），Graf（View⁃Point），Boat（Zoom＋Rotation），Leuven（Light），Ubc（JPEG Compression）5组图片以及一组现场拍摄的书架图片，每组图片包含6张图片，分别使用BBF算法以及AutoARV＆DP算法对每组图片中的img1和img3各进行5次匹配实验，最后使用RANSAC剔除误匹配，分别求取两算法平均每次匹配的正确匹配总数、正确匹配率以及匹配时间3个指标。实验结果如下：

表1 不同变化环境下的匹配性能Table 1 Performance of matching in different situation

由表1可知，在正确匹配总数方面，AutoARV＆DP算法稍逊于BBF算法，这可以通过适当增大Seektimesth来增加匹配总数；在正确匹配率方面，AutoARV＆DP与BBF算法的表现相差无几，前者甚至更加稳定；在匹配时间方面，当特征向量集合规模较小时，AutoARV＆DP算法与BBF算法相差不大，随着特征向量集合规模的增大，前者较后者有明显的优势。这是由于AutoARV＆DP仅需在较小的空间中搜索有限的近似最近邻，而BBF算法基于kd⁃tree索引进行优先队列查询，不但受特征向量集合分布的影响，而且需要较多的回溯查询，导致时间成本较高。由此可知，本文所提出的AutoARV＆DP算法能够满足不同变化环境下的特征点匹配需求，且当特征向量集合规模较大时，时间成本上由于BBF算法。

4.2 不同规模特征向量集合下的性能对比实验

本实验比较了在不同规模特征向量集合下AutoARV＆DP算法与BBF算法的时间成本。实验采用实验室现场拍摄图片，共2组，其中，每组20张，10张查询图像，对应10张搜索图像，特征向量集合的大小10 k～40 k不等。分别使用BBF算法以及AutoARV＆DP算法对2组图片进行匹配实验，求取在不同特征向量集合规模N下，平均每次匹配的时间消耗。实验结果如表2所示：由表2可知，随着特征向量集合规模N的增大，BBF算法的匹配时间急剧增加，本文的AutoARV＆DP算法虽然也有所增加，但其增长速率远低于BBF算法。这是由于本文的AutoARV＆DP算法仅需在较小的空间中搜索有限的近似最近邻，随着数据规模的增长，需要求取更多的夹角和距离来建立待匹配样本集，但是，经过AutoARV＆DP算法的夹角和距离筛选后，落在该搜索空间的样本并不会急剧增长，从而降低了时间消耗。由此可知，在特征向量集合规模较大的情况下，AutoARV＆DP算法在时间成本上优于BBF算法。

表2 不同特征集合规模下的匹配性能Table 2 Performance of matching in d ifferent sizes of fea⁃ture vector set

5 结束语

本文基于参考向量夹角和点距离，提出了一种自适应搜索范围的近似最近邻搜索算法AutoARV＆DP用于SIFT特征点匹配。VGG实验室的ACF测试图片库与现场图片的测试结果表明，AutoARV＆DP能够适应不同变化环境，取得较好结果的同时，降低时间成本，尤其在数据集规模较大的情况下，时间消耗明显优于经典的BBF算法。此外，若结合数据集的分布特点，搜索空间还有进一步缩小的可能，从而进一步提高算法的性能，这将是后期的研究工作重点。

［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］何周灿，王庆，杨恒.一种面向快速图像匹配的扩展LSH算法［J］.四川大学学报：自然科学版，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特征点匹配算法［J］.模式识别与人工智能（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］同济大学数学系.高等数学［M］.（6版）（下册）.高等教育出版社，2007：109⁃113.

唐坤，男，1988年生，硕士研究生，主要研究方向为数字图像处理，人工智能。

韩斌，男，1968年生，教授，博士，主要研究方向为数字图像处理、智能检测、并行计算。

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

唐坤，韩斌.一种自适应搜索范围的SIFT特征点快速匹配算法［J］.智能系统学报，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.