一种基于几何约束与GPU级联哈希的图像特征匹配方法

摘要

本发明公开了一种基于几何约束与GPU级联哈希的图像特征匹配方法，属于计算机视觉技术领域。本发明首先使用基于GPU的级联哈希快速图像特征匹配算法，先对图像部分特征点进行两两匹配和极线几何估计，只保留几何估计结果较好的和匹配数目较多的图像对；然后将极线几何约束加入基于GPU的级联哈希图像匹配中，进一步将低GPU级联哈希图像匹配算法的时间复杂度，减少了运算量，进一步加快了图像匹配的速度；另一方面算法全部使用CUDA并行计算架构进行编写，充分利用GPU并行运算能力，使得相比传统的CPU匹配算法具有10

说明书

技术领域

本发明属于计算机视觉技术领域，更具体地，涉及一种基于几何约束与GPU级联哈希的图像特征匹配方法。

背景技术

图像特征匹配是寻找图像之间特征点的对应关系，广泛应用图像拼接、目标检测和三维重建等方面。SIFT特征是图像特征匹配最常用的特征之一，因为它的尺度不变性和旋转不变性的特点，抗干扰能力强，匹配精度高。然而随着互联网和信息技术的发展，如今的计算机视觉应用中，需要处理图像的数量越来越大，比如在大规模城市场景三维重建中，需要匹配的图像是数万甚至数十万的数量级，使用传统的匹配方法和设备需要花费数月。为了加快图像匹配时的查找速度，在2014年提出的三维重建中基于级联哈希的快速图像特征匹配方法，利用局部敏感哈希算法的O(1)查找性能与海明距离的快速运算，进一步缩短一对图像的匹配时间，在同等设备情况下相比线性查找具有10²左右的匹配加速。然而在待匹配图像数量较大的情况，例如大场景三维重建，有些场景需要图像之间两两匹配，那么就有数量级的匹配对需要处理，其中N_p是图像的数量，也即在海量图像匹配任务的情况下，级联哈希匹配方法依然需要大量运算时间，依旧无法满足目前不断增长的运算需求。

近几年也有很多方法通过图像之间相似性来预先剔除匹配对来加快图像匹配，然而相似性与真正的图像匹配并不是完全的对应关系。因此抢占式匹配方法通过一小部分点进行快速的两两匹配，然后剔除匹配关系不好的匹配对，最后进行指导性匹配，既避免了真正匹配对被剔除，也大量减少了匹配对的数量。但是减少匹配对之后，这些方法使用匹配速度较慢的算法进行最后的匹配，因此总体的匹配时间还是比较长。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种基于几何约束与GPU级联哈希的图像特征匹配方法，将GPU级联哈希匹配与抢占式匹配结合，避免了对所有图像所有特征点进行两两匹配，还将极线约束加入GPU，极大的缩短了SIFT特征点匹配时间，使得在海量高维数据的情况下也能在短时间之内完成匹配。

为实现上述目的，本发明提供了一种基于几何约束与GPU级联哈希的图像特征匹配方法，所述方法包括：

(1)选取图像中SIFT特征点对所有图像进行两两匹配；

(2)对匹配点数目大于设定值B的匹配对，计算匹配对的基础矩阵和内点率，内点率小于设定值C的匹配对和匹配点数目不大于设定值B的匹配对将被剔除；其中，设定值B的取值范围为15～20，优选15；设定值C的取值范围为60％～70％，优选66.7％；

(3)根据通过筛选的匹配对的基础矩阵计算极线，设定极线阈值D，剔除到极线距离大于D的匹配点；其中D的取值范围为5～15个像素，优选为10个像素

(4)计算通过筛选的匹配点之间的欧氏距离，对欧氏距离最小和欧式距离次小的匹配点对进行显著性检验，通过显著性检验且欧式距离最小的匹配点之间相互匹配，并对剩下的匹配点进行匹配。

进一步地，所示步骤(1)中具体采用GPU级联哈希图像匹配算法，同时对所有的图像进行两两匹配。

进一步地，所述步骤(1)中选取图像中SIFT特征点的具体选取方法具体为：采用GPU并行算法同时将所有图像中的SIFT特征点由大尺度到小尺度的进行队列排序，选取队列前百分之A的SIFT特征点，其中A的取值范围为10～30，优选20。

进一步地，所述步骤(2)中计算匹配对的基础矩阵和内点率具体为：

采用GPU并行算法同时对所有匹配对内的匹配点随机采样；再根据采样结果计算得到对应的候选基础矩阵和相应的内点数；最后在多个候选基础矩阵中选取内点数最大的候选矩阵作为最终的基础矩阵，内点数除以匹配点总数即为内点率。

进一步地，所述步骤(2)中首先剔除内点率小于设定值C的匹配对，然后再剔除匹配点数目小于等于设定值B的匹配对，剩下的匹配对保留。

进一步地，所述步骤(3)具体采用GPU级联哈希图像匹配算法，同时计算所有SIFT特征点到极线的距离。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，具有以下技术特征及有益效果：

本发明利用了GPU具有强大并行运算能力的特点进行加速，将GPU级联哈希匹配与抢占式匹配结合，避免了对所有图像的所有特征点进行两两匹配，还将极线约束加入GPU，极大的缩短了SIFT特征点匹配时间，使得在海量高维数据的情况下也能在短时间之内完成匹配。

附图说明

图1是本发明方法的整体流程示意图；

图2是本发明方法中极线约束筛选待匹配点方法示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

GPU(Graphics Process Unit，图像处理器)具有很强的并行运算能力，对于图像匹配这种运算任务重、数据相关性较小的算法，非常适合GPU进行并行化。配备高性能GPU的运算设备，运行这类适合并行化算法，能以单机的情况下达到只配备了CPU的多节点服务器集群的运算能力，而成本与占地面积却小很多。GPU并行化通常使用CUDA或者OpenCL架构。本发明方法采用CUDA进行算法编写，CUDA工具集的核心是基于C语言编译器，支持并配合C++语言的编写使用，具有极高的执行效率与运算速度。

如图1所示为本发明实施例方法的总体流程示意图。其具体实施方式如下：

(1)使用GPU级联哈希图像匹配算法，对所有的图像的前20％的SIFT特征点进行两两匹配；

(2)根据(1)的匹配结果，对匹配点数目大于15使用GPU极线几何估计，计算F矩阵和内点率，内点率小于2/3的匹配对将被剔除；

(3)将(2)中计算得到的F矩阵计算极线，将极线约束加入GPU级联哈希图像匹配中，进一步筛选候选点，降低了算法的时间复杂度。

优选地，在本发明的一个实施例中，步骤(1)具体包括：

(1.1)按照大尺度到小尺度的顺序，选取一部分的SIFT特征点，优选地，在本发明的一个实施例中，选取前20％的点作为第一次匹配的待匹配点。

(1.2)使用GPU级联哈希匹配对所有图像的一部分的SIFT特征点进行两两匹配，由于特征点数量很少，因此匹配速度很快。

优选地，在本发明的一个实施例中，步骤(2)具体包括：

(2.1)根据(1)的匹配结果，对匹配点数目大于15使用GPU极线几何估计，计算F矩阵和内点率；

(2.2)剔除内点率小于2/3的匹配对，然后再剔除匹配点数目小于等于15的匹配对，剩下的匹配对保留。

优选地，在本发明的一个实施例中，步骤(3)具体包括：

(3.1)将(2)中计算得到的图像对之间的F矩阵计算查询点到待匹配图像上的极线。

(3.2)如图2，根据对极几何，待匹配点会落在极线上，因此在本发明的一个实施例中，设定阈值d，距离极线距离小于d的点，图中为红色的点，通过筛选，而距离大于d的灰色的点被剔除。通过极线约束，进一步降低GPU级联哈希匹配的算法复杂度，减少匹配时间。极线约束筛选在GPU级联哈希匹配中的并行哈希排序之前，汉明距离计算之后。

(4)计算通过筛选的待匹配点与查询点的欧氏距离，对欧氏距离最小和欧式距离次小的待匹配点进行显著性检验，通过显著性检验的欧式距离最小的待匹配点则为所述查询点的匹配点。

以上内容本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。