基于数据聚类的鲁棒SIFT特征匹配方法

摘要

基于数据聚类的鲁棒图像SIFT特征匹配方法，步骤如下：(1)获取参考图像序列，提取SIFT特征集，采用合成k-d数据结构对全部SIFT特征集进行聚类，合并重复特征集为聚类特征，聚类特征的特征描述子采用重复特征平均描述子表示，(2)利用SIFT方法获取实时图像序列特征集，将参考图像序列与实时图像序列进行鲁棒匹配，选择包含特征点最多的对应参考图像作为关键图像，完成第一阶段特征匹配，(3)利用关键图像完成第二阶段特征匹配，采用RANSAC、基本矩阵等技术进行外点剔除。最后合并两阶段特征匹配结果。本匹配方法能够降低噪声信息干扰，极大提高特征匹配的鲁棒性。

说明书

技术领域

本发明属于计算机增强现实技术领域，具体地说是对大数据量条件下的SIFT特征集进行鲁棒匹配，消除匹配过程的噪声影响，提高特征匹配的鲁棒性。

背景技术

SIFT特征匹配技术是计算机图像与视觉中的重要研究内容，在诸如图像检索、目标识别、三维重建以及相机姿态恢复等众多领域都得到了广泛的应用。

通过将SIFT特征描述子看作高维欧氏空间笛卡尔坐标并采用欧氏距离作为相似性度量标准，SIFT特征匹配问题可以转化为欧氏空间最邻近几何点的查询问题。作为最重要的分支界定(branch and bound)方法之一，k-d数据结构能够有效实现空间剖分并被广泛用于最邻近特征查询工作。但是随着特征维度的增加，由于需要遍历每一分支以精确定位匹配特征，该方法的匹配效率会迅速下降。针对该问题，Beis等人提出了一种使用优先队列的近似最邻近方法，称为BBF(Best Bin First)方法。该方法能够在仅损失极少精度前提下极大提高高维特征的匹配速度，被广泛用于SIFT特征的匹配工作。但是由于SIFT特征描述子对噪声信息非常敏感，随着特征数据量的增加以及分布于欧氏空间特征点密度的增大，该方法特征匹配的鲁棒性会迅速下降。

与k-d数据结构空间剖分方式不同，vocabulary数据结构通过层次化k-means聚类方式实现空间分割，这种方式使得vocabulary树状结构构造过程实际上等价于空间嵌套voronoi胞腔生成过程，从而进一步推广了分支界定方法的应用范围。Nister等人将vocabulary数据结构应用于SIFT特征匹配，给出了一种基于vocabulary树的海量图像查询方法，但该匹配方法仅存在统计学意义，无法有效实现SIFT特征最邻近查询工作。Schindler等人进一步将vocabulary树应用于基于图像的城市定位问题，给出了一种类似BBF的GNP(Greedy N-Best Paths)方法，用以实现基于vocabulary树的SIFT特征最邻近特征匹配。但随着数据量的增大，该方法也存在着匹配鲁棒性降低的问题。最近，Dong等人给出了一种基于vocabulary树的两阶段匹配方法，该方法首先通过vocabulary树查找关键图像，然后利用关键图像进行两图像间的特征匹配，有效避免了大数据量条件下特征匹配鲁棒性降低的问题，但该方法本质上是两图像间的特征匹配，仍然无法解决SIFT特征噪声敏感问题。

发明内容

本发明要解决的技术问题：克服现有技术的不足，提供一种具有消除噪声干扰和提高鲁棒性的SIFT特征匹配方法。

本发明采用的技术方案：基于数据聚类的鲁棒SIFT特征匹配方法，其特点在于步骤如下：

(1)提取参考图像序列SIFT特征集，对全部SIFT特征集，区分普通特征与聚类特征，通过聚类过程合并重复普通特征集为聚类特征，聚类特征描述子采用重复普通特征描述子均值表示，均值优化策略能够极大消除噪声对SIFT特征的影响，提高特征匹配的鲁棒性；

(2)基于合成k-d数据结构的SIFT特征聚类过程，对给定n幅参考图像，首先选取参考图像1包含特征集FS[1]并将其赋予聚类特征集FCS，生成合成k-d数据结构。然后遍历参考图像2包含特征集FS[2]并依次与聚类特征集FCS进行基于合成k-d数据结构的匹配。若匹配成功，则合并参考图像2包含特征集与聚类特征集对应特征为新聚类特征。否则将该参考图像2包含特征作为普通特征加入聚类特征集FCS。完成参考图像2包含特征集FS[2]与参考图像1包含特征集FS[1]的特征聚类后，对于参考图像3～n包含特征集FS[3]～FS[n]重复进行该聚类过程直到完成所有特征集。该过程仅需要n-1次迭代步骤，避免两两图像匹配过程较高的时间复杂度；

(3)两阶段SIFT特征匹配方法，分别包括第一阶段基于合成k-d数据结构的聚类特征匹配选择关键图像过程与第二阶段基于关键图像的图像间特征匹配过程。通过两阶段匹配特征集的合并，进一步提高了特征匹配的鲁棒性。

所述步骤(1)的合并重复普通特征集为聚类特征的方法为：首先将特征分为普通特征与聚类特征。然后针对普通特征中存在的大量重复特征，通过算术平均化过程合并重复特征集为聚类特征，聚类特征描述子采用重复特征描述子的算术均值表示。

所述步骤(2)中基于合成k-d数据结构的SIFT特征聚类方法为：对给定n幅图像，首先选取参考图像1包含特征集FS[1]并将其赋予聚类特征集FCS，生成合成k-d数据结构。然后遍历参考图像2包含特征集FS[2]并依次与聚类特征集FCS进行基于合成k-d数据结构的匹配。若匹配成功，则合并参考图像2包含特征集与聚类特征集对应特征为新聚类特征。否则将该参考图像2包含特征作为普通特征加入聚类特征集FCS。完成参考图像2包含特征集FS[2]与参考图像1包含特征集FS[1]的特征聚类后，对于参考图像3～n包含特征集FS[3]～FS[n]重复进行该聚类过程直到完成所有特征集。

所述步骤(3)中两阶段特征匹配方法为：第一阶段通过基于k-d数据结构的特征匹配方式进行。对于每一次匹配成功的图像特征，首先判断其特征类型，若为普通特征，则仅为其所属图像投票；若为聚类特征，则投票过程需要对其包含全部普通特征依次进行。完成全部匹配特征投票后，选择票数最多图像作为关键图像。第二阶段特征匹配过程首先进行基于关键图像的图像间特征匹配，然后对第一阶段匹配特征集进行提纯，将属于关键图像的匹配特征集直接传给第二阶段匹配特征集。最后利用RANSAC等技术作外点剔除工作，提高特征匹配的鲁棒性。

本发明与现有技术相比的优点在于：

(1)允许存在大量重复特征集。通过区分普通特征点与聚类特征点并通过聚类过程合并重复特征集为聚类特征，有效达到降低数据量目的。均值优化求解聚类特征描述子策略能够消除噪声对SIFT特征的影响，极大提高了特征匹配的鲁棒性；

(2)通过扩展k-d数据结构以使其能够容纳聚类特征，相比于标准k-d数据结构，合成k-d数据结构有着更好的异构数据类型适应性，基于该类数据结构的特征聚类过程，不但能够达到有效聚类的目的，而且能够提高聚类过程效率。

(3)基于计数投票策略的关键图像选择方法不但能够正确选择关键图像，而且可以有效完成SIFT特征匹配工作。通过将第一阶段匹配特征集传递给第二阶段匹配特征集，两阶段匹配特征集的级联合并能够在大数据量条件下有效提高特征匹配的鲁棒性。

附图说明

图1为本发明合成k-d数据结构示意图。

图2为本发明特征匹配鲁棒性比较示意图。

图3(a)、(b)为本发明路政匹配鲁棒性直观示意图。

具体实施方式

表1给出了本发明的具体步骤：

表1

1.离线阶段合成k-d数据结构构建及特征聚类

图1给出了合成k-d数据结构示意图。

离线阶段首先获取参考图像SIFT特征集，对全部参考图像SIFT特征集进行聚类。在特征聚类方法中，普通特征由SIFT算法直接从图像中获得，可以表示为F_s＝{b_i，d_d}，其中b_i为隶属图像，d_d是特征描述子。聚类特征为普通特征的集合，表示为F_c＝{F_ss，d_md}，其中F_ss为普通特征集合，d_md为聚类平均描述子，其值为：其中k为聚类特征包含普通特征数，(d_d)_i为第i个普通特征描述子。该值相当于聚类特征包含普通特征集的几何中心点，因此能够较好地表达聚类特征。如图1所示，合成k-d数据结构中每一节点都能够容纳聚类特征。

对于n幅图像来说，重复特征集可以通过两两匹配计算获得，但该过程需要进行次匹配。随着图像数的增加，该计算过程过于复杂。因此本文给出了一种基于合成k-d数据结构的特征聚类方法。如算法1所示。

聚类方法采用迭代方式进行，首先选取参考图像1包含SIFT特征集FS[1]并将其赋予聚类特征集FCS，生成合成k-d数据结构。然后遍历参考图像2包含SIFT特征集FS[2]，依次与聚类特征集FCS进行基于合成k-d数据结构的匹配。若匹配成功，则合并参考图像2包含的特征集与聚类特征集中对应特征为新聚类特征，聚类特征描述子为两特征描述子的算术平均值。否则将该特征作为普通特征加入聚类特征集FCS。完成参考图像2包含SIFT特征集FS[2]与参考图像1包含SIFT特征集FS[1]的特征聚类后，对于后继参考图像3～n包含SIFT特征集FS[3]～FS[n]，重复上述过程，依次与聚类特征集FCS进行聚类过程。对于n幅图像，本文提出的递增聚类方法仅需要n-1次匹配过程，相对于两两匹配大幅节省了计算开销。

2.在线两阶段级联匹配

第一阶段特征匹配选择关键图像过程，如算法2所示：

算法通过基于合成k-d数据结构的特征匹配方式进行。对于每一次匹配成功的参考图像特征，算法首先判断其特征类型，若为普通特征，则仅为其所属参考图像投票；若为聚类特征，则投票过程需要对其包含全部普通特征依次进行。完成全部匹配特征投票后，选择票数最多图像作为关键图像。

通过上述概率最优化方法选择关键图像能够较好地保证关键图像选择的准确性，可以进一步利用该关键图像进行第二阶段匹配。如算法3所示。

第一阶段特征匹配过程中关键图像选择方法表明第一阶段匹配聚类特征集中包含大量属于关键图像的普通特征。算法2在利用实时图像SIFT特征集与聚类特征集匹配选择关键图像的同时，实际上也部分地完成了实时图像SIFT特征集与关键图像对应SIFT特征集的匹配工作，因此在算法3的第二阶段特征匹配过程中，对于第一阶段匹配过程匹配成功的特征集，可以将其直接传给第二阶段匹配特征集，从而避免了两阶段重复匹配造成的时间开销。完成两阶段特征匹配后，可以利用RANSAC等技术作外点剔除工作，进一步获取鲁棒特征集。

图2为基于数据聚类的鲁棒SIFT特征匹配效果示意图。演示效果在一台普通桌面PC机器上实现，硬件配置环境为Intel Core 2Duo 2.66GHz处理器，软件环境为Windows XP平台，采用VC2005.NET平台开发，开发过程中使用了OpenCV库。图像序列统一采用640×480像素大小图片。

为执行该演示，整个过程选择了60幅图像作为参考图像序列，300幅图像作为实时匹配图像序列，每幅图像包含大约1500～2000特征点。图像间存在大量重叠关系，保证全部特征集合中包含大量重复特征点。为验证方法的鲁棒性，我们进一步从中随机选取了两幅匹配效果直观示意图，如图3所示。

在图3(a)、(b)中，无箭头线段代表图像-图像匹配方法生成的匹配特征集，圆形箭头线段代表本文提出的匹配方法生成的新匹配特征集，图3(a)中图像-图像匹配方法匹配特征数为344；图3(b)中本文提出的匹配方法匹配特征数为88。上述数据表明，本发明方法能够有效减少噪声影响，极大提高SIFT特征匹配的鲁棒性。