一种基于GPU与级联哈希的快速图像SIFT特征匹配方法

摘要

本发明公开了一种基于GPU与级联哈希的快速图像SIFT特征匹配方法，属于计算机视觉领域。本发明根据GPU全局显存大小限制、内存大小限制，建立GPU、内存、硬盘三级交换机制；同时采用改进的GPU并行规约方法，将图像的所有SIFT特征点进行两次编码长度不同的哈希映射；提出并使用上三角矩阵分块读取方法；通过局部敏感哈希算法进行粗略筛选；通过计算海明距离对候选点进行精细筛选；最后通过计算筛选点和待匹配点的欧氏距离找到最合适匹配点；利用CPU与GPU的异步并行方法，使得图像对的匹配结果数据在GPU运算的同时，从GPU显存中拷贝至内存并保存至磁盘。本发明极大的缩短了SIFT特征点匹配时间，在海量数据的情况下也能在短时间之内完成特征匹配。

说明书

技术领域

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

背景技术

图像特征匹配是图像之间特征点对应的关系，在图像识别、图像配准与三维重建等方面中具有广泛的应用。SIFT特征具有尺度不变性和旋转不变性，因此抗干扰能力强，匹配精度高，因此是图像特征匹配常用的特征。然而每一个SIFT特征点是由128维向量表示的，SIFT特征点的相似性度量为欧氏距离，在高维向量情况下欧氏距离计算时间较长，线性查找方法在两张图像之间匹配的计算复杂度为O(N²)，这里的N为图像的平均特征点数目。因此为了加快一对图像匹配时的查找速度，一系列基于树的查找方法被提出来，例如KD-Tree、M-Tree等，这些基于查找树的方法的算法复杂度为O(NlogN)，在同等设备情况下相比线性查找具有10倍左右的匹配加速。在2014年提出了三维重建中基于级联哈希的快速图像特征匹配方法，利用局部敏感哈希算法的O(1)查找性能与海明距离的快速运算，进一步缩短一对图像的匹配时间，在同等设备情况下相比线性查找具有10²左右的匹配加速。然而在待匹配图像数量较大的情况，例如大场景三维重建，有些场景需要图像之间两两匹配，那么就有数量级的匹配对需要处理，其中N_p是图像的数量，也即在海量图像匹配任务的情况下，级联哈希匹配方法依然需要大量运算时间。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种基于GPU与级联哈希的快速图像SIFT特征匹配方法，其目的在于使用将级联哈希匹配算法进行了GPU并行化，提出了改进GPU并行规约方法和GPU哈希排序方法，由此解决传统图像SIFT匹配方法较慢的技术问题。

为实现上述目的，按照本发明的一个方面，提供了一种基于GPU与级联哈希的快速图像SIFT特征匹配方法，所述方法包括：

将图像SIFT特征数据以图像为单位存储在硬盘中，以组为单位存储在内存中，以块为单位存储在GPU全局显存中，建立GPU全局显存、内存和硬盘三级存储交换机制；

采用GPU并行规约方法和局部敏感哈希算法，对所有图像的所有SIFT特征点进行短编码的哈希映射和长编码的哈希映射，使得每个SIFT特征点映射一个短哈希编码和一个长哈希编码；其中，短编码长度取值范围为8到10，优选8；长编码长度取值范围为100到200，优选128；

在匹配图像对中，图像I中SIFT特征点Si的短哈希编码分别和另一个图像J中所有SIFT特征点的短哈希编码进行对比，找出图像J中短哈希编码和Si的短哈希编码相同的SIFT特征点组成粗匹配集合；

分别计算Si的长哈希编码和粗匹配集合中所有SIFT特征点长哈希编码的海明距离，将计算得到的海明距离进行排序，筛选出海明距离最小的N个粗匹配集合中的SIFT特征点组成精细匹配集合；其中N的取值范围为6到10，优选10；

采用GPU并行规约方法分别计算Si和精细匹配集合中所有SIFT特征点的欧氏距离，筛选出欧氏距离最小的两个SIFT特征点，进行显著性检验，通过显著性检验的欧式距离最小的SIFT特征点，作为SIFT特征点Si的匹配点。

进一步地，所述三级存储交换机制具体包括：

将所有图像SIFT特征点数据分数据块存放，每个数据块的大小小于GPU全局显存一次最多能载入数据量大小的一半；

将所有数据块分数据组存放，每个数据组的大小小于内存大小的一半；

载入一图像的SIFT特征点数据到显存进行处理时，先从硬盘中载入该图像的SIFT特征点数据所在的数据组至内存，再从内存载入该图像的SIFT特征点数据所在的数据块至GPU全局显存。

进一步地，所述GPU并行规约方法具体为最后M轮规约计算在GPU寄存器中进行，其他轮规约计算在GPU共享内存中进行；其中M的取值范围为2到4，优选3。

进一步地，所述短编码的哈希映射具体采用多次随机函数不同的哈希映射，同一SIFT特征点得到多组哈希编码，选择多组哈希编码中相同次数最多的哈希编码最为SIFT特征点映射的短哈希编码。

进一步地，所述SIFT特征数据的读取方法具体为将需要匹配的对比的SIFT特征数据所在数据块载入GPU共享内存，按数据块编号和所在数据组的编号与自身建立一个上三角矩阵读取任务序列，当两个数据块中的图像两两匹配完成之后，检测下一个读取任务是否继续需要这两个数据块和数据组，不需要的则释放所在GPU共享内存空间和内存空间。

进一步地，所述海明距离进行排序具体为：根据海明距离大小构造排序索引表，排序索引表中构建L个桶，桶号分别为0，1，2，…，L-1，将海明距离和桶号相等的SIFT特征点放入桶号对应的桶内；其中，L的取值范围为20至120，优选40。

进一步地，利用GPU进行图像匹配运算，利用CPU将匹配结果从GPU显存中拷贝至内存并保存至磁盘。

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

(1)本发明将级联哈希匹配算法进行了GPU并行化，提出了改进GPU并行规约方法和GPU哈希排序方法，使得相比传统的KD-Tree等匹配算法具有了10³倍左右的加速；

(2)本发明针对大数据情况下提出了GPU、内存、硬盘三级交换机制和上三角矩阵分块读取方法，使得算法在大数据情况下也能够不降低运算速度；极大的缩短了SIFT特征点匹配时间，使得在海量高维数据的情况下也能在短时间之内完成匹配；

(3)本发明利用了GPU具有强大并行运算能力的特点，在同等算法的情况下，数据集相同的情况下，性能较强的显卡中运行的GPU程序相比CPU单线程程序能达到几十倍甚至一百倍左右的加速。

附图说明

图1为本发明技术方案的总体流程示意图；

图2为本发明实施例中GPU中局部敏感哈希算法向量內积快速计算示意图；

图3为本发明实施例中GPU快速规约操作示意图；

图4为本发明实施例中上三角矩阵分块读取方法示意图；

图5为本发明实施例中GPU并行哈希排序运算瓶颈示意图。

具体实施方式

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

如图1所示为本发明实施例方法的总体流程示意图。从图1可以看出，本方法包含建立硬盘、内存、GPU三级交换机制，上三角分块读取方法，粗略哈希筛选模块，精细哈希筛选与输出模块等几个步骤的前提条件。其具体实施方式如下：

(1)根据GPU全局显存大小限制、内存大小限制，将所有图像特征点数据进行分块和分组，建立计算机层面的GPU、内存、硬盘三级交换机制；

(2)提出并使用改进的GPU并行规约方法，充分利用GPU内部层面的全局显存、共享内存、寄存器三级缓存机制，将图像的所有SIFT特征点进行两次编码长度不同的哈希映射；

(3)根据匹配是图像之间进行的，提出并使用上三角矩阵分块读取方法，每次读取两块数据，利用短哈希编码的局部敏感哈希方法，待匹配图像对中图像I中每个SIFT特征点(查询点)，在另一个图像J的所有特征点中进行粗略筛选；

(4)在GPU中计算图像I中每个查询点在图像J中通过(3)中筛选的候选点之间的海明距离，提出并使用改进的GPU哈希排序方法对海明距离进行快速排序，精细筛选出海明距离最小的几个最近邻。

(5)使用改进的GPU并行规约方法计算图像I中每个查询点在图像J中的几个最近邻之间的欧氏距离，选出欧氏距离最小的和欧式距离次小的点进行显著性检验，通过显著性检验的欧式距离最小的点，作为图像I中该查询点的匹配点。

(6)利用CPU与GPU的异步并行方法，使得图像对的匹配结果数据在GPU运算的同时，从GPU显存中拷贝至内存并保存至磁盘。

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

(11)由于GPU的全局显存相对于内存、硬盘较小，因此根据GPU全局显存一次最多能载入图像特征点数据数目的一半为一块，将所有图像特征点数据分成大小基本一致的数据块，在本发明的一个实施例中采用100个图像为一块，在内存中对它们的特征点数据进行整合。使得处理这部分数据的时候，可以一次性拷贝至GPU显存，减少了总的拷贝时间；在海量数据情况下，内存可能也无法载入全部特征点，因此将固定数目的相邻的几个数据块组成数据组，一个数据组的大小小于内存大小的一半，在本发明的一个实施例中采用1000个图像的特征点数据作为一个二进制文件，也能够较快的从硬盘中读取，减少了总的拷贝时间。

(12)在需要载入某图像数据到显存进行处理的时候，先从硬盘中载入该图像数据所在的数据组至内存，然后从内存载入该图像数据所在的数据块至GPU的全局显存。

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

(21)在本发明的一个实施例中，本次哈希映射将128维的SIFT描述符表示的特征点映射为8位二进制编码，也即一共有2⁸种不同的哈希编码，使得哈希编码相同的SIFT特征点较多。由于哈希编码具有一定的随机性，为了使得真正的匹配点的短哈希编码相同，进行多次随机函数不同的哈希映射，得到多组哈希编码，便于(3)中的第一次粗略筛选；

其中局部敏感哈希方法中需要计算随机函数与特征向量的內积，本发明提出并使用改进的GPU并行规约方法计算向量的內积，设d为向量的维数，n为编码长度，因此计算一个点的哈希映射的核函数形式为：

Hashing_kernel<<<n,d>>>(PR,PQ)

其中PR，PQ分别为显存中存储随机向量与特征点数据的指针。在实施例中，特征点为128维的SIFT特征点，编码长度为128，因此取n＝128与d＝128，也即调用GPU的n个线程块，每个线程块调用d个线程，內积运算是向量对应项两两相乘，d个乘积累加，而GPU访问显存较慢，在乘积相加的时候需要反复读取存储，因此为了减少访问存储延迟对运算效率的影响，采用GPU的共享内存，暂时存放乘积，然后在共享内存中计算累加。

计算方式如图2，在每个线程块中有128个线程同时参与运算，每个线程从PR中取出一个分量，然后再从PQ中取出一个分量，相乘之后放在共享内存中。数据在共享内存中的存取是很快的，但是每个线程块中如果采用一个一个串行累加的方式会浪费计算资源，因此一般的并行计算处理方式是规约求和方法，经典的GPU规约算法也是在共享内存中进行的。GPU的运算效率取决于两个方面，运算的并行程度还有存储延时，在近几年的GPU中，不仅共享内存等高速缓存的容量变大，每个线程可以使用的寄存器也增多了，在现代GPU中访问一次全局显存的时间，相当于几百个运算周期，而访问一次高速缓存的时间，相当于10多个运算周期，访问一次寄存器的时间，仅仅需要一个运算周期，因此使用寄存器会大大加快规约过程。

本文中采用的归约操作流程如图3，与经典的规约方法不同的是，本实施例在最后2轮规约中使用寄存器代替共享内存进行累加，原因是经典的规约方法在最后几轮计算中线程使用数目本来就非常低，这个时候使用寄存器代替共享内存，虽然也只能使用一个线程，但是减少了几次共享内存访问。在如图3中，在最后两轮计算中，经典的规约方法需要访问2次共享内存的时间，并且需要2次加法的时间，那么大概需要22个运算周期完成最后两轮计算；而使用寄存器之后，需要访问3次寄存器时间，还需要3次加法的时间，那么大概需要6个运算周期完成最后两轮计算，因此很大程度上提高了运算速度。

(22)用(21)相同的方法，在GPU中将图像的所有SIFT特征点进行编码长度较长的哈希映射，在本发明的一个实施例中，本次哈希映射将128维的SIFT描述符表示的特征点映射为128位二进制编码，也即一共有2¹²⁸种不同的哈希编码，使得编码相同的SIFT特征点极少，便于(3)中的第二次精细筛选。

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

(31)根据匹配是图像之间进行的，本发明提出并使用上三角矩阵分块读取方法优化读取顺序，在(1)中建立的三级交换机制对数据进行了分块和分组，对所有的数据块进行编号，对所有的数据组也进行编号，数据块与自身建立一个上三角矩阵读取任务序列，并标注其所在的分组，按照如图4的箭头的顺序载入图像数据进行匹配，矩阵中的每一个点都是一个读取任务。每个读取任务的执行过程为：首先检测该点的两个下标对应的两个数据组是否在内存中，从硬盘中载入这两个数据组中没有被载入的数据组至内存，然后检测该点的两个下标对应的两个数据块是否在内存中，从内存中载入这两个数据块中没有被载入的数据块至GPU，两个数据块中的图像两两匹配完成之后，检测下一个读取任务是否继续需要这两个数据块和数据组，不需要的数据组和数据块则释内存空间和显存空间，则例如图4中A点是从硬盘中载入数据组0至内存，然后从内存中载入数据块0至GPU，由于下一个载入任务还需要数据组0还有数据块0，因此不释放空间；图4中B点是内存中已经有数据组0和数据块2，因此不需要载入，下一个载入任务需要数据组0，但不需要数据块2，因此在GPU中释放数据块2；图4中C点是内存中已经有数据组0，但需要从硬盘中载入数据组1，然后从内存中载入数据块3和数据块0到GPU，下一个载入任务不需要数据块3，因此在GPU中释放数据块3。

(32)在本发明的一个实施例中，利用短哈希编码，在待匹配图像对中图像I中每个SIFT特征点，在另一个图像J的所有特征点中使用局部敏感哈希方法进行粗略筛选。

在本发明的一个实施例中，上述步骤(4)具体包括：

(41)在GPU中计算图像I中每个查询点在图像J中通过(3)中筛选的候选点之间的海明距离。由于哈希编码本身就是二进制形式，海明距离在计算机中只需要首先进行按位异或操作，然后求1的个数操作，在本发明的一个实施例中调用计算机底层的函数popcount()在一个计算周期内完成海明距离的计算，而SIFT特征点具有128个描述子，因此计算欧氏距离至少需要做128次减法，128次平方，127次加法，一共需要383个计算周期。因此无论是在GPU中还是在CPU计算海明距离都比同等条件下计算欧氏距离的时间短很多，因此本步骤也从计算方式上节省了大量运算时间

(42)根据计算得到的海明距离大小构造排序索引表，本文中也称之为桶，在本发明的一个实施例中，由于长哈希编码有128位，得到的海明距离范围是从0到128，因此图像I中每个查询点q，都构造一个长度为129的索引表，本文中也称之为桶，桶号分别为0，1，……，128，排序索引表存放与查询点的海明距离等于桶号的候选点。

本文中每一个线程块处理一个图像中的候选点的海明距离排序，因此在一个线程块中构造哈希桶的过程如图5。

由于一个线程块中的所有线程都是并发执行的，因此如果有两个候选点的海明距离结果相同，那么这个时候在写入同一个哈希桶的时候就会产生存储冲突。为了避免存储冲突产生的错误，就需要使用CUDA的原子操作，在写冲突的线程任务串行执行，这样虽然避免了但是降低程序执行效率。而在实际的图像匹配实验中，候选点都集中在中间的哈希桶中，在中间的哈希桶的冲突次数是最多的。并行计算的时间效率遵循木桶原理，GPU并行构造哈希桶的时间取决于落在中间的哈希桶的点的数目。

但是最终只需要前几个最近邻，远小于哈希桶的数目，因此绝大部分位于前几个桶中。如图5，在GPU存放候选点到排序索引表的时候，设定一个阈值，不构造桶号大于该阈值的桶，只构造桶号小于该阈值的桶，会减少运算瓶颈，提高运算效率，但是如果构造的哈希桶数目太少，会导致取不出几个最近邻，匹配精度降低，在本发明的一个实施例中，该阈值设定为40。

(43)在本发明的一个实施例中，依次从桶0，1，2，…，40中取出10个候选点作为最近邻。

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

(51)使用与步骤(3)中相同的改进的GPU并行规约方法计算图像I中每个查询点在图像J中的几个最近邻之间的欧氏距离，用冒泡排序方法找出欧氏距离最小的和欧式距离次小的点。

(52)对欧氏距离最小的和欧式距离次小的点进行显著性检验，在本发明的一个实施例中，显著性检验的方法为似然比检验，通过显著性检验的欧式距离最小的点，作为图像I中该查询点的匹配点。

在本发明的一个实施例中，上述步骤(6)具体包括：

根据CPU与GPU属于不同的运算，在执行运算的时候是异步的。在GPU进行图像匹配运算的同时，CPU可以同时将图像匹配结构数据从GPU显存中拷贝至内存并保存至磁盘，从而隐藏了输出过程需要的时间，提高了整体的运算效率。

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