摘要：SIFT算子由于其较强的匹配能力和良好的健壮性成为图像匹配领域研究的热点与难点。但一般应用中SIFT算子提取的特征点的匹配都是在CPU上进行的，这对于维度高达128并且特别是海量的特征点的匹配是非常耗时的。本文提出将CPU上逐个特征点在KD树上进行的BBF搜索改为在GPU上并行进行，并通过实验进行了对比。结果表明，将BBF搜索部分放在GPU上实现，匹配速度会有所提升，这就为SIFT算子进行复杂影像的匹配提供了更广阔的的应用空间。
关键词：SIFT特征点；KD树；BBF搜索算法；GPU并行；快速匹配
1.绪论
D.G.Lowe于1999年提出SIFT算子[1-2]并于2004年对该算子做了完善总结。SIFT算法是利用提取的图像局部特征进行图像匹配的，在图像匹配、目标识别、遥感影像配准等领域得到了很好的应用[3]。本文针对SIFT算子提取出的海量特征点的快速匹配问题，考虑各SIFT特征点在KD树上的搜索是相互独立的，而GPU在并行数据运算上具有强大的计算能力，特别适合做大量并行化的问题[4]，特别是2007年6月NVIDIA公司推出了可作为数据据并行计算设备的软硬件体系[5]—CUDA并行架构，更将GPU的并行处理能力和应用范围推上一个新台阶，研究尝试利用KD树+BBF搜索，将特征点在KD树的上进行的BBF搜索部分的实现放在GPU上，以试图提高海量特征点匹配的速度。
2.SIFT特征点匹配的一般方法
（1）穷举法
假设参考影像A和待匹配影像分别提取出m和n个SIFT特征点。该算法思路为：将待匹配影像的一个特征点
与参考影像的所有m个特征点分别进行欧氏距离计算，得到
的一个包含m个欧式距离的集合，如果最邻近与次邻近距离的比值小于某一阈值，则
与最邻近距离所对应的特征点为一对匹配点对。将A的所有特征点依次都进行以上运算，即可得到所有的匹配点对。
（2）基于标准搜索的KD树匹配法
KD树是对数据点在k维欧几里得空间中进行划分的一种数据结构，由Jon Louis Bentley于1975年正式提出[6]。标准的KD树邻近距离搜索过程为：设分裂节点的分割超平面对应维度和分割中值分别为
和
。从根节点开始，比较待匹配点
的
维上的值
与
的大小。若
<=
，则进入左子树分支，否则进入右子树分支，一直向下搜索直至叶子节点，计算待匹配点与此叶子节点包含的特征点的欧式距离，比较出“当前最邻近与次邻近距离”；向上回溯搜索，判断搜索路径上没被搜索到的兄弟节点分支中是否有更近的点，在此过程中不断更新“当前最邻近与次邻近距离”直到回溯到根节点，此时的“当前最邻近距离与次邻近距离”即为最终搜索到的最邻近与次邻近距离；其余待匹配点执行相同操作。
（3）基于BBF搜索的KD树匹配法
BBF算法借助优先队列完成邻近距离的搜索。从根节点开始，按照与标准搜索算法相同的方法扫描到叶节点，不同的是需要将搜索路径上被搜索节点的兄弟节点依次压入优先队列，并且存储每个节点的关键值。然后按关键值从小到大排列节点，从中取最小节点重复以上过程，直至队列为空或扫描次数达到上限值。
（4）穷举法的GPU实现
此种算法是利用两个核函数，具体思路为：
将参考影像和待匹配影像的特征点维度数据集合分别看做是一个n1
128矩阵和一个128
n2矩阵，第一个核函数利用类似矩阵相乘形式计算出所有参考影像特征点与待匹配影像特征点间的欧式距离；第二个核函数完成每个待匹配点最邻近和次邻近距离的筛选，以及是否匹配的判断。
这种算法在特征点不是很多的时候速度很快，但对于海量特征点就会遇到内存不足的问题。对于海量的特征点的快速匹配问题仍需从KD树下手，寻找解决方法。
3.基于GPU的海量特征点快速匹配
KD树包括创建和遍历两个部分。本文将KD树的创建和遍历分别放在CPU和GPU上实现。遍历是将BBF搜索算法改为在GPU上实现，具体流程如图1所示。
图1 基于GPU的海量SIFT特征点快速匹配
BBF搜索的并行实现对其在CPU上的实现算法进行了一些修改。
（1）CPU上节点的结构为：
程序中将节点信息存储到纹理内存中，用3个元素类型为int，一个元素类型为float和一个元素类型为float4的纹理存储器分别存储的节点信息，如表1和表2所示。
表1 节点基本信息
表2 节点和其包含的前三个特征点索引信息
（2）在GPU程序中为了利用元素类型为int4纹理存储器存储叶节点及其所包含特征点的索引，如果叶节点中包含3个以上的特征点只存储前3个特征点的索引，如表2。
4.实验
4.1实验环境
硬件平台：CPU配置为Intel（R）Core（TM）i5-3230M @2.60GHz 双核，主存为4GB。
GPU配置为GeForce GT 650M，显存为2GB。
软件平台：采用Win7 64位操作系统，Visual Studio 2010，CUDA 5.0。
4.2实验结果及分析
本次实验利用CPU上BBF搜索实现的特征点匹配作为对比试验，选取不同复杂度的图像提取数量不同的SIFT特征点。实验用时如表3所示，表中的数值均为10次实验结果取平均值。
表3 实验结果
实验结果表明，本文所提出的GPU上实现BBF搜索算法在保证匹配结果与CPU上一致的前提下提高了特征点匹配速度。但是随着特征点的不断增加，搜索加速比和总加速比都没有持续增大，而是分别保持在2.10（表3 BBF搜索加速比平均值）和1.70（表3匹配总加速比平均值）左右。这是因为随着匹配点的不断增加，由于带宽的限制、存储器延迟以及线程间同步的延迟等都制约了GPU整体速度的提升，使GPU系统并行处理优势降低。
5.结束语
本文提出将基于KD树+BBF搜索的SIFT特征点匹配由原来的完全在CPU上实现改为在GPU上特征点进行BBF并行搜索。详细介绍了实现的细节，并通过编程实验验证了这种改进确实使特征点的匹配速度得到了一定程度的提升。但此方法对于海量的SIFT特征点匹配并不能达到实时的要求。同时3可以看出，KD树的创建大概占匹配总时间的60%左右，以下一步研究的重点是将KD树的创建也放在GPU上实现，以求速度的进一步提升。
参考文献：
[1]Lowe D G.Object Recognition from Local Scale-Invariant Feature[C].the International Conference on Computer Vision，Corfu greece，1999
[2]LOWE D G.Distinctive Image Features from Scale-Invariant Keypoints[J]. International Journal of Computer Vision，2004，60（2）：91-110
[3]王瑞，梁华，蔡宣平.基于GPU的SIFT特征提取算法研究[J].现代电子技术，2010，15：41-43
[4]厉旭杰.GPU加速的图像匹配技术.计算机工程与应用[J]，2012，48（2）：173-176
[5]杨铭，陈建峰.基于CUDA的海量点云数据KNN查询算法.测绘通报，2012（S1）：394-398
[6]J.L.Bentley.Multidimensional binary search trees used for associative searching[J].Communications of the ACM，1975，18（9）：509-517
论文作者:田一涵1,匡明星2,曹威3
论文发表刊物:《基层建设》2019年第14期
论文发表时间:2019/7/30
标签：特征论文; 节点论文; 算法论文; 距离论文; 海量论文; 算子论文; 影像论文; 《基层建设》2019年第14期论文;