文章快速检索 高级检索

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
Abstract: Aiming at the high time cost of feature vectors matching in scale invariant feature transform(SIFT), a fast algorithm, called auto angle of reference vector & distance of point(Auto ARV & DP), of self-adaptive search scope for SIFT matching 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, the matching of SIFT is performed in a small feature vectors set, which is filtered by Norm. Experimental results showed that compared with the classical best bin first(BBF) algorithm, Auto ARV & DP can effectively decrease the time cost of feature vector matching of SIFT with no loss of matching performance when the size of feature vector set is large.
Key words: SIFT     Auto ARV & DP     feature points matching     search scope     BBF

1 问题描述

 ${F_1} = \left\{ {{V_i}\left| {{V_i} = \left[ {V_i^1V_i^2 \ldots V_i^{128}} \right],i = 1,2, \ldots ,m} \right.} \right\}$

 $F_{1}^{'}=\left\{ {{p}_{i}}\left| {{p}_{i}}=\left[ p_{i}^{1}p_{i}^{2}\ldots p_{i}^{128} \right],i=1,2,\ldots ,m \right. \right\}$

 ${F_2} = \left\{ {{V_j}\left| {{V_j} = \left[ {V_j^1V_j^2 \ldots V_j^{128}} \right],j = 1,2, \ldots ,m} \right.} \right\}$

 $F_{2}^{'}=\left\{ {{p}_{j}}\left| {{p}_{j}}=\left[ p_{j}^{1}p_{j}^{2}\ldots p_{j}^{128} \right],j=1,2,\ldots ,m \right. \right\}$

2 自适应搜索范围的快速匹配算法—AutoARV & DP 2.1 AutoARV & DP算法基本原理

 $F_2^{''} = \left\{ {{V_i}\left| \begin{array}{l} {V_i} \in {F_2},\\ \left\langle {{V_{i,}}{V_r}} \right\rangle \in \left[ {\theta - \Delta \theta ,\theta + \Delta \theta } \right],\\ i = 1,2 \ldots ,k,k < n \end{array} \right.} \right\}$

 图 1 邻域内搜索最近邻 Fig. 1 Search in the neighborhood
2.2 自适应搜索范围

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

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

 ${F_{angle}}'' = \left\{ \begin{array}{l} {V_i}\left| {{V_i} \in {F_2}} \right.\\ \left\langle {{V_i},{V_r}} \right\rangle \in \left[ {\theta - \Delta \theta ,\theta + \Delta \theta } \right],\\ i = 1,2 \ldots ,k,k < n \end{array} \right\}$

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

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

 ${F^{''}}_{angle} = \left\{ {{V_i}} \right.\left| \begin{array}{l} {V_i} \in {F_2},\\ \left\langle {{V_i},{V_r}} \right\rangle \in \left[ {0,\theta + \Delta \theta } \right],\\ i = 1,2, \ldots ,k,k < n \end{array} \right.$
2.3 距离筛选

 ${F^{''}}_{angle + dist} = \left\{ {{V_x}} \right.\left| \begin{array}{l} {V_x} \in F_{angle}^{''},\left| {{V_x}} \right| \in \left[ \begin{array}{l} \left| {{V_q}} \right| - \left| {{V_q}{V_m}} \right|,\\ \left| {{V_q}} \right| + \left| {{V_q}{V_m}} \right| \end{array} \right]\\ x = 1,2, \ldots ,p,p < k \end{array} \right.$

 图 4 距离筛选后的搜索空间 Fig. 4 The search area after distance filtering
2.4 参考向量选取

 ${Q_{angle}} = \{ < {V_r},{V_i} > {V_i} \in {F_2},i = 1,2, \cdots ,n\}$

 $\begin{array}{l} d = \sum\limits_{i = 1}^n {\left| {p_r^{128}{p_i}} \right|} = \\ \sum\limits_{i = 1}^n {\sqrt {{{\left( {x_r^1 - x_i^1} \right)}^2} + {{\left( {x_r^2 - x_i^2} \right)}^2} + \ldots + \left( {x_r^{128} - x_i^{128}} \right)} } \end{array}$

 $\begin{array}{l} \min \left( {\sum\limits_{i = 1}^n {\left| {p_r^{128}{p_i}} \right|} } \right) = \\ \min \left( {\sum\limits_{i = 1}^n \begin{array}{l} \left( - \right)2 + \left( - \right)2\\ + \ldots + \left( {x_r^{128} - x_i^{128}} \right) \end{array} } \right) \end{array}$

 $x_{_r}^j = \frac{1}{n}\sum\limits_{i = 1}^n {x_i^j} ,i = 1,2, \ldots ,n.j = 1,2, \ldots ,128$

2.5 算法描述

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

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

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

2) 对于VqF1，基于本文描述，使用AutoARV & DP算法在F2中搜索得到Vq的最近邻特征向量Vq_nearest，对应的最近邻距离为distnearest，次近邻特征向量Vq_nearest2，对应的次近邻距离distnearest2，若$\frac{{dis{t_{nearest}}}}{{dis{t_{nearest}}_{_2}}}$小于设定的阈值ratioth，则认为Vq与Vq_nearest正确匹配[1]

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

4 实验及结果分析

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

 图片 特征点总数 td>BBF算法 AutoARV & DP算法 Img1 Img3 正确匹配总数 正确匹配率/% 匹配时间/s 正确匹配总数 正确匹配率 匹配时间/s Bike 3 215 1 381 534 93.2 0.392 426 94.5 0.316 Graf 2 821 3 595 382 92.5 0.420 275 93.3 0.352 Boat 7 909 5 574 1 265 94.7 1.139 1 054 94.1 0.797 Leuven 2 218 1 600 747 94.2 0.264 682 94.8 0.285 Ubc 4 563 6 833 1 586 95.8 0.717 1 248 94.6 0.688 书架图 6 933 7 873 650 93.4 1.170 427 93.2 0.824

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

 数据规模k BBF算法 AutoARV & DP算法 正确匹配率/% 匹配时间/s 正确匹配率/% 匹配时间/s 11.6 94.8 1.91 95.1 1.13 13.5 95.2 2.27 95.0 1.31 15.8 95.0 2.82 95.3 1.53 18.3 94.7 3.19 94.8 1.74 20.7 94.3 3.71 94.6 1.94 24.1 93.8 4.39 94.5 2.17 27.7 93.7 5.22 94.6 2.38 31.2 93.4 5.92 94.2 2.54 35.6 92.8 6.80 94.0 2.70 38.6 93.0 7.53 94.3 2.78

5 结束语

 [1] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision,2004, 60 (2) : 91 –110. [2] KRYSTIAN M, CORDELIA S. A performance evaluation of local descriptors[J]. IEEE Trans on Pattern Analysis and Machine Intelligence,2005, 27 (10) : 1615 –1630. [3] BAY S H, TUYTELAARS T, GOOL L V. SURF: speed up robust features[C]//Proceedings of the European Conference on Computer Vision. Graz, 2006: 404-417. [4] FARAJ A, DANIJELA R D, AXEL G. VF-SIFT: very fast sift feature matching[C]//Proc of the 32nd DAGM Symposium. Darmstadt, Germany, 2010: 222-231. [5] FARAJ A, DANIJELA R D, AXEL G. VF-SIFT: very fast sift feature matching[C]//Proc of the 32nd DAGM Symposium. Darmstadt, Germany, 2010: 222-231. [6] GIONIS A, INDYK P, MOTWANI R. Similarity search in high dimensions via hashing[C]//Proc of the 25th International Conference on Very Large Data Bases. San Francisco, USA, 1999: 518-529. [7] BEIS J S, 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 finding nearest neighbors[J]. IEEE Signal Processing Magazine,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, LOWE D G. Fast approximate nearest neighbors with automatic algorithm configuration[C]//International Conference on Computer Vision Theory and Applications. 2009: 331-340. [11] MUJA M, LOWE D G. Fast matching of binary features[C]//Conference on Computer and Robot Vision. : 2012: 404-410. [12] 吴伟交, 王敏, 等. 基于向量夹角的SIFT特征点匹配算法[J]. 模式识别与人工智能,2013, 26 (1) : 123 –127. WU Weijiao, WANG Min. SIFT feature matching algorithm based on vector angle[J]. Pattern Recognition and Artificial Intelligence(PR & AI),2013, 26 (1) : 123 –127. [13] 同济大学数学系. 高等数学. 北京: 高等教育出版社[M]. 2007 : 109 -113.
DOI: 10.3969/j.issn.1673-4785.201309037

0

文章信息

TANG Kun, HAN Bin

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

CAAI Transactions on Intelligent Systems, 2014, 9(6): 723-728
http://dx.doi.org/10.3969/j.issn.1673-4785.201309037