Lowe提出的尺度不变特征变换(scale invariant feature transform,SIFT)^[1]是一种鲁棒性强的图像局部特征提取算法，具有对旋转、光照、尺度变化等保持不变性^[2]，广泛应用于三维重建、目标识别、图像融合等领域^[3]。SIFT算法由特征点检测及描述与特征点匹配两部分构成，其中，SIFT特征点匹配实质上可以转化为在高维空间中搜索特征点最近邻的问题，并且在很多情况下，只需要得到查询特征点的近似最近邻就足够了^[4]。据此近年来提出了一些相关算法，其中，Lowe提出的最优节点优先算法(best bin first,BBF)^[5]在K-D树索引的基础上，使用优先队列和限制回溯查询次数来提高搜索最近邻的效率。va+-file算法^[6]将数据集转换到KLT域，然后采用均匀量化划分来提高va-file算法^[7]的过滤效率。iDistance算法^[8]对高维数据空间进行划分，使用B+-tree结果来组织参考点并搜索最近邻。LSH(locality sensitive hashing,LSH)算法^{[9, 10]}通过Hash函数将邻近高维点集映射到Hash表的同一个桶中，从而提高搜索最近邻效率。基于聚类分析的B+-tree算法^[11]采用类B+-tree索引结构，通过更加细致的划分数据来加快搜索速度。MRSVQH^[12]根据选择子向量的L₂范数来量化和散列特征向量，仅考虑具有与查询向量相同Hash值的集合，从而提高了搜索速度。

本文在以上研究的基础上，提出了一种基于参考点距离的SIFT特征点匹配算法—DRP算法，并通过实验与经典的BBF算法相比，来验证基于DRP算法的SIFT特征点匹配效果。

设d维欧式空间R^d中2个点P₁=(x₁,x₂,…,x_d)，P₂=(y₁,y₂,…,y_d)，两点对应的向量分别为V₁=[x₁ x₂ … x_d]，V₂=[y₁ y₂ … y_d]。则P₁、P₂两点之间的欧式距离D(P₁,P_2)为

由式(1)可知，若|V₁|确定且V₁与V₂的夹角一定时，当|V₂|→|V₁|cos〈V₁,V₂〉时，向量V₁与V₂对应的P₁与P₂两点之间的距离D(P₁,P₂)取最小值。

设d维欧式空间R^d中的一个点集合F_d={P_i|P_i∈R^d,i=1,2,…,n}，对于∀P_query∈R^d，需要在F_d中搜索P_query的最近邻。设定一个参考点P_r，则对于每一个需要搜索的P_query，P_query与参考点P_r构成向量P_rP_query是确定的(长度和方向)，若F_d中所有点与设定参考点P_r构成的向量P_rP_i与P_rP_query之间的夹角都为θ时，则使向量|P_rP_i|→|P_rP_query|cosθ的点P_i就是P_query的最近邻。

若集合F_d中所有特征点与设定参考点P_r构成的向量P_rP_i与P_rP_query之间的夹角不都为θ时，即不相等时，上述结论并不一定成立。如图 1的三维空间所示。

图 1 不同夹角时的最小距离 Fig. 1 The minimum distance of different angle

图选项

尽管|P_rP₁|=cos〈P_rP₁,P_rP_query〉|P_rP_query|，而|P_rP₂|>cos〈P_rP₁,P_rP_query〉|P_rP_query|。但是，P₂相对于P₁更靠近P_query。

为了尽可能的得到P_query的最近邻，本文将搜索范围扩大到集合F_d^′中的所有点。如图 2所示。

图 2 在一定区域内搜索最近邻 Fig. 2 Search the nearest neighbor in a specified area

图选项

若将搜索范围扩大到以P_r为球心，R_th^－为半径的球外，R_th⁺为半径的球内区域，则可得到P_query的真正最近邻P₂。随着R_th^－的减小和R_th⁺的增大，搜索到P_query的真正最近邻的概率也随之增大。由此可知，当F_d中所有点与设定参考点P_r构成的向量P_rP_i与P_rP_query之间的夹角不相等时，只需要选择一个合适的搜索范围R_th^－与R_th⁺，仍然可以搜索到P_query的真正最近邻。

设d维欧式空间R^d中的2个点集合：

对于∀P_q∈Q_d^′，需要在集合Q_d中搜索其最近邻。引入一个参考点(可随机选取)P_r∈R^d，若P_nearest(P_nearest∈Q_d)是P_q的最近邻，则P_nearest应该出现在P_q的附近，即向量P_rP_q与向量P_rP_nearest之间的夹角〈P_rP_q,P_rP_nearest〉应该趋向于零，此时|P_rP_nearest|=|P_rP_q|×cos〈P_rP_q,P_rP_nearest〉→|P_rP_q|。因此，当|P_rP_nearest|=|P_rP_q|时，点P_nearest为查询点P_q的最近邻。由此，对于∀P_q∈Q_d^′，不需要逐一计算P_q与Q_d集合中所有点的距离，而只要计算P_q与参考点P_r之间的距离D_rq，然后在点集合Q_d^″中搜索，就可能得到P_q的真正最近邻，即P_q的真正最近邻落在集合Q_d^″所表示的范围中。

以图 3所示的三维空间为例，如果搜索向量P_q的最近邻，只需要在P_r为球心，半径为d_rq－Δd_th^－的球以外和半径为d_rq+Δd_th^－以内的空间搜索，就可以得到P_q的真正最近邻。

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

图选项

基于以上分析，在向量集合F_d中搜索向量V_q的最近邻的步骤如下：

1)在d维欧式空间R^d中任意选取一点P_r作为参考点，设定一个阈值th(正整数)。

2)对于任一属于集合F_d中的点P_i(i=1,2,…,m)，计算其与参考点P_r之间的距离，保存于数组D_ri中，并建立D_ri与P_i的映射。

3)使用快速排序算法对D_ri中的距离按升序(或降序)进行排序，得到D_ri^order。

4)从待匹配点集合F_d^′中任取一待匹配点P_query，计算P_query与参考点P_r之间的距离D_qr=|P_rP_query|。

5)使用二分查找法从D_ri^order中快速查找D_rq的最近邻D_rj，并得到D_rj对应的点P_j^nearest及其索引index(j)。

6)对D_ri^order中索引范围在[index(j)－th,index(j)+th]对应的所有点中，利用穷举搜索法查找P_query的最近邻。

在步骤6)中涉及到距离的计算，为进一步提高算法的效率，均采用如下所述的距离累计算法。当d维点P_x与P_query的前i(i∈[1,d])维的欧式距离已经超过上一次比较的最小距离时，无论后面d－i维的距离情况如何，将必定大于已经产生的最小距离。因此，也无需计算它们后面d－i维的距离，直接剔除跳出，进行下一特征点的比较。

SIFT算法提取的图像特征点包括极大值与极小值2种类型，显而易见，只有极值类型相同的特征点才可能正确匹配。因此，本文在特征点匹配之前进行特征点类型的判断，仅当2个特征点具有相同类型时，才进行接下来的匹配运算，否则直接跳出，转而比较下一个特征点。这在一定程度上可以提高匹配的效率。

对于2幅含有同一场景的图像I_q(x,y)和I_s(x,y)，本文介绍的DRP算法按如下步骤进行。

1)使用SIFT算法分别提取图像I_q(x,y)与图像I_s(x,y)的特征点，生成的特征点构成的集合分别为P_q¹²⁸和P_s¹²⁸。

2)对于∀P_i∈P_q¹²⁸，使用本文介绍的DRP算法在集合P_s¹²⁸中搜索得到查询点P_i的最近邻特征点P_nearest，对应的最近邻距离为d_nearest，次近邻特征点P_nearest2，对应的次近邻距离d_nearest2，若比值d_nearest/d_nearest2小于已知的阈值r_th，则认为P_i与P_nearest两点之间正确匹配。

3)采用随机抽样一致性原则(random sample consensus,RANSAC)算法剔除误匹配的特征点。

本文实验采用的代码由GitHub上Rob Hess维护的Opensift库^[13]改进而来。实验采用的测试图片来自牛津大学VGG实验室的Affine Covariant Features(ACF)图片库^[14]。实验硬件环境为CPU Inter(R) Core(TM)2 T6600，主频2.20 GHz，内存2 GB DDR3 RAM；软件环境为OS Windows7 32 bit、IDE Microsoft Visual Studio 2010、 GTK+2.24图形工具包和Opencv2.4机器视觉库。

为了验证DRP算法的有效性，本文进行了在不同搜索阈值th下，DRP算法与经典BBF算法的对比实验。简便起见，所有实验中的参考点均采用坐标原点，即P_r=x_r^j，x_r^j=0,j=1,2,…,128。其中，交叉验证两算法的最近邻与次近邻距离阈值比r_th保持为0.56。BBF算法中除搜索阈值KDTREE_BBF_MAX_NN_CHKS变化外，其他所有参数保持默认。实验中搜索阈值th以50为步长在^{[50, 500]}范围内变化，在不同搜索阈值th条件下，对Bikes、Trees、Graf、Bark、Boat、Leuven 6组图片每组中的Img1/Img2、Img1/Img3、Img1/Img4 3对图片各进行10次SIFT特征点匹配实验。统计得到特征点的正确匹配率、正确匹配特征点总数以及平均每幅图像匹配时间与搜索阈值th的关系如图 4所示。

图 4 DRP算法与BBF算法实验对比结果 Fig. 4 The comparison results of DRP algorithm and BBF algorithm

图选项

由图 4(a)可知，在特征点正确匹配率方面，DRP算法与BBF算法具有相同的趋势。当搜索阈值th小于200时，随着th的增大而增大；当搜索阈值th大于200时，特征点正确匹配率很难得到进一步的改善，趋于稳定。总体来看，这2个算法在特征点匹配率的表现上相差无几。由图 4(b)可知，在正确匹配特征点总数方面，DRP的算法略逊于BBF算法，但是，随着搜索阈值th的增大，两者的差距逐渐缩小。由图 4(c)可知，在匹配时间上，DRP算法与BBF算法都随着搜索阈值th的增大而呈线性增长趋势，但是，BBF的增长速率显著大于DRP算法，由此可知，在匹配时间上，DRP算法较BBF算法具有明显的优势。综上所述，相对于经典的BBF算法，本文介绍的DRP算法能获得满意匹配效果的同时，有效降低匹配时间。

本文介绍了一种基于参考点距离的SIFT特征点匹配算法，并使用牛津大学VGG实验室的ACF图片库进行SIFT特征点匹配实验。实验结果表明，与经典BBF最近邻搜索算法相比，使用本文介绍的DRP算法进行SIFT特征点匹配，不仅可以获得满意的匹配效果，并且可以有效地降低匹配时间消耗，提高匹配速度。尤其在搜索阈值th较大的情况下，DRP算法在时间成本上较经典的BBF算法具有明显的优势。另外，DRP算法还有一些可以改进的地方，如对提取的SIFT特征点分布情况进行分析、参考点选择方法的分析等都可能进一步提高特征点的匹配效率。对于不同的特征点分布情况，如何选取一个合适的参考点，从而尽可能改善匹配效果是下一步的工作重心。