摘 要:为了提升图像在三维重建过程中特征点匹配时的准确率,提出了一种基于改进SURF(speeded-up robust features)的图像特征点匹配算法。首先,将SURF的64维度描述符提升至128维度;其次,在SURF算法引入KD-Tree模块,利用BBF(best bin first)最近邻查询机制实现特征点匹配;最后,通过对同一数据集进行旋转、缩小,并利用传统算法和改进SURF算法分别对图像进行特征点匹配实验,验证改进SURF算法的有效性。结果表明:改进SURF算法的特征点匹配正确率达到了89.19%,相较于传统SURF算法提高了17.62个百分点;特征错误匹配数由85减少至31,显著降低了特征点的匹配误差;运行时间由1.956 s缩短至1.647 s,进一步提升了算法的运行速度。改进后的SURF算法具备正确率高、误差小、速度快的特点,可为三维重建特征匹配工作提供重要的参考。
关键词:图像处理;特征点匹配;SURF算法;KD-Tree;三维重建
中图分类号:TP391" 文献标识码:A""文章编号:1008-1534(2024)06-0418-08
Image feature point matching algorithm based on improved SURF
WANG Zhenzhou, ZHANG Sen, NING Chao, WANG Jianchao
(School of Information Science and Engineering, Hebei University of Science and Technology,Shijiazhuang, Hebei 050018, China)
Abstract:
In order to improve the accuracy of feature point matching in 3D reconstruction of images, an image feature point matching algorithm based on improved SURF was proposed. Firstly, the 64-dimension descriptor of SURF was upgraded to 128 dimensions. Secondly, the KD-Tree module was introduced into the SURF algorithm, and the BBF (best bin first) nearest neighbor query mechanism was used to implement feature point matching. Finally, after rotating and scaling changes on the same data set, feature point matching experiments were performed on the images by using the traditional algorithm and the improved SURF algorithm, respectively, and then the effectiveness of the improved SURF (speeded-up robust features) algorithm was verified. The results show that the improved SURF algorithm achieves a feature matching accuracy of 8919%, which is improved 1762 percentage points, and the number of feature 1 matches decreases from 85 to 31, significantly reducing the matching error of feature points. The running time is shortened from 1956 seconds to 1647 seconds, further improving the running speed of the algorithm. The improved SURF algorithm has the characteristics of high accuracy, less errors and fast speed, which can provide reference for 3D reconstruction feature matching.
Keywords:
image processing;feature point matching;SURF algorithm;KD-Tree;3D reconstruction
随着计算机与先进制造技术的快速发展,高效建立物体三维几何模型的需求越来越旺盛[1-3],因此三维重建技术逐渐成为学术界研究的热点。图像特征点提取与匹配是三维重建的关键步骤,直接影响到重建结果的准确性。在三维重建过程中,由于拍摄距离与角度多变等问题,使得图像的尺度与真实数据存在较大误差,导致图像特征点的数量和密度分布不均,一些特征点无法匹配到正确的位置[4-6]。因此,改进图像特征点的匹配算法,提高特征点的匹配精度,对推动三维重建技术在各个领域的应用具有重要意义[7-8]。
目前常用的特征点提取和匹配算法包括SUSAN(smallest univalue segment assimilating nucleus)[9-10]算法、SIFT(scale-invariant feature transform)[11-12]算法和SURF[13-14]算法等,都具备各自的特点。SUSAN算法适用于图像边缘和角点检测,对噪声和光照变化鲁棒性较强,但应用于多尺度和复杂的场景时存在一定的误差;SIFT算法是一种基于局部特征点的描述和匹配算法,对计算资源要求较高,不适用于实时应用场景;SURF算法适用于视频处理等动态场景,对旋转变化和视角变化具有很好的适应性。由于三维重建过程对图像尺度变化有极高的要求,因此部分科研工作者对缩放、旋转、平移能力较强的SURF算法进行了深入研究。江智等[15]针对传统SURF算法在拼接高分辨率图像时运行速度慢、特征匹配正确率低的问题,结合无人机定位定姿系统,提出了一种基于IB-SURF(image block-SURF)技术的图像拼接算法,显著提高了算法的运行速度及准确率,但其应用领域仅限于图像拼接,普遍性较差。张蕾等[16]为了解决结构光三维重建中特征点匹配错误、匹配缺失和匹配重复等问题,将SURF算法中高斯滤波改进为自适应中值滤波结合小波变换,并提出了一种基于OKG(oriented k-nearest neighbors with gaussian weight)算法的二次特征匹配方法,基本满足了结构光三维重建系统的实验要求。WEN等[17]通过简化海森行列式的方法提升了SURF算法的运算速度,但导致其精度有所下降。王卫兵等[18]结合SURF与RANSAC(random sample consensus)算法进行特征匹配,并采用KNN(k-nearest neighbors)算法优化匹配效果,显著提高了匹配速度,但仍存在正确率较低的问题。赵谦等[19]采用自适应阈值方法进行初步匹配特征点的提取,并提出了一种改进的SURF-RANSAC图像匹配算法,提高了特征点的匹配速度,但特征点的匹配正确率仍有待提高。
SURF作为图像特征点匹配常用的算法之一,有着鲁棒性高、稳定性好等优点,但仍然存在着特征点匹配正确率较低等问题。本文对SURF算法进行改进,在优化运行速度的同时,降低了计算的复杂度,提升了图像特征点匹配的正确率。
1 传统SURF算法相关理论
SURF算法是基于SIFT算法优化所得,解决了SIFT算法的计算复杂度高和处理速度慢等问题[20-23]。
运行SURF算法时,首先,输入灰度图像构建用于特征检测的积分图像尺度空间[24-26],通过检测高斯差分图像的局部极值点来定位特征点[27];其次,将检测到的特征点确定主方向,并使用特征点周围的图像区域来生成描述该特征点的特征向量;最后,使用特征向量进行特征匹配,并通过欧式距离或其他相似度度量值来比较2个特征描述子之间的相似性,从而找到图像之间的对应关系。SURF算法流程图如图1所示。
2 基于改进SURF的图像匹配算法
2.1 改进后的SURF算法
本文在传统SURF算法基础上,提出一种基于改进SURF的图像特征点匹配算法。首先,将SURF算法描述子的维度扩展至128维,获得高维度特征向量;其次,通过计算欧氏距离,并建立KD-Tree特征结构集,减少特征点匹配过程中的计算复杂度,对于图像的尺度、旋转、光照等变化具有更好的适应性;最后,改进KD-Tree的最近邻查询机制,减少不必要的搜索路径和节点访问次数,能够更精确地搜索到最近邻点,从而提高查询的准确性,有效地提升SURF算法的匹配精确度。改进SURF算法流程图如图2所示。
2.2 基于SURF的特征点描述向量优化
基于传统SURF的特征描述向量通常为64维度,这些描述向量用于表示检测到的图像中关键点的局部特征信息。为了确保局部特征的稳定性,需要为检测到的特征点分配基准方向。首先,在特征点周围选取一个固定大小的局部区域,构建一个方向直方图来统计不同方向上的梯度响应;其次,对局部区域内的每个子区域计算Haar小波响应,每个小波响应代表了局部区域内的特征信息;最后,通过分析方向直方图中的峰值,确定特征点周围的主方向。SURF算法利用主方向对局部区域内的特征进行描述,将局部区域划分为子区域,并计算每个子区域的Haar小波响应。根据计算得到的Haar小波响应,通过分析得到主要的峰值,其方向即为特征点的基准方向。Haar小波响应如图3所示。
选定特征点的基准方向后,以特征点为中心,沿着基准方向选取矩形区域,将矩形区域划分为4×4的16个小区域,每个小区域的边长为5s(s为该特征点对应的尺度),设计2s×2s的Haar模板,分别对每个小区域进行基于x,y方向的响应值计算,响应值结果分别记为dx和dy。最后对每个小区域的响应值统计4个梯度值,得到在每个小区域的四维向量如式(1)所示。
V=∑dx,∑dy,∑dx,∑dy,(1)
式中:∑dx为x方向响应值之和;∑dy为y方向响应值之和;∑dx为x方向响应值的绝对值之和;∑dy为y方向响应值的绝对值之和。最终得到区域的四维向量。每个小区域都包含水平、垂直、对角线和反对角线4个方向的Haar小波响应,因此每个小区域生成了4个特征值。对于1个16×16像素的窗口,总共有4×4=16个小区域,每个小区域生成了4个特征值,从而形成了一个64维的特征向量。在统计每个小区域的∑dx和∑dx时,分别考虑了dxlt;0和dx≥0的2种情况。同样地,在求取∑dy和∑dy时也采取了相同的计算方式。这样,在每个子区域都会产生8个梯度值,从而将SURF算法描述符扩展至128维。高维度能够提供丰富的特征信息,使得图像的局部特征更加清晰,从而增强了特征点之间的区分度,进而提升了匹配的精确度。尽管更高的特征维度可能会导致计算时间的增加,但这种特征点描述向量在后续的特征匹配过程中更易被准确地检测和匹配,因此在实际应用中具有更高的应用价值。
2.3 基于KD-Tree的BBF算法优化
KD-Tree是一种高效的数据结构,能够快速准确地找到距离最近的特征点,实现特征点之间的匹配。通过利用KD-Tree,SURF算法能够更加精确地在特征空间中搜索匹配点,提高图像特征点的匹配效率。如果匹配时的维度过高,距离计算、数据存储和索引构建等操作都会变得困难和耗时,边缘特征也会存在模糊不清、难以区分的情况,导致特征匹配的准确性下降。因此,在进行匹配搜索时,采用了KD-Tree索引的最近邻搜索方法BBF来实现特征匹配,能够以最高优先级搜索最相关的特征点,从而加速匹配过程并提高匹配的准确性。BBF算法对查询路径进行了一系列优化。传统的KD-Tree只是简单地取回根节点,忽略了数据节点本身的特征。与传统的KD-Tree不同,BBF算法结合了数据节点的特点,确保回溯检查点总是从优先级最高的树节点开始。BBF算法的主要作用是将KD-Tree的快速计算应用到高维数据集。 BBF算法通过将查询路径上节点对应的相反子节点存储到优先级队列中来优化搜索队列。例如,如果查询路径指向右子树,则将该层对应的左节点放入优先队列中,并进行回溯检查,这样做有2个好处:1)搜索路径上的点不会在优先队列中重新出现;2)减少了很多无用的重复计算。算法的这种优先级排列顺序可以保证有更高的可能性搜索到离目标点最近的点。通过BBF搜索算法,SURF算法能够智能地在特征空间中选择候选点,从而有效地减少了搜索时间和计算成本,弥补了高特征维度所增加的计算时间成本,提高了图像特征点匹配的性能。BBF算法流程图如图4所示。
在进行BBF查询时,将已查询的节点和待查询的节点进行记录,具体来说,已查询的节点是指已经评估且不再考虑的节点,待查询的节点是指在当前查询过程中可能会成为最近邻的节点。根据这些节点与目标点的距离大小进行排列,自动构建一个优先序列,这样在查询时就可以从最高优先级的节点进行查询,完成整个序列查询后把返回结果当作最近邻节点。通过这种方式,BBF算法在每一轮搜索中都会优先搜索距离较近的点,以最短的时间找到最近邻点。最后,在满足停止条件时,BBF算法会将找到的最近邻点作为搜索结果返回。在整个过程中,BBF算法通过优先搜索距离较近的点,有效解决高维度数据的搜索问题,提高搜索效率。
3 实验与分析
3.1 实验环境
本次实验使用基于64位Windows10操作系统,仿真软件为MATLAB(2018a)。主机硬件配置中:CPU为Intel Core i9-13900HX 2.20 GHz(英特尔公司提供);显卡为NVIDA RTX4060(英伟达公司提供);内存为16 GB(金士顿科技公司提供)。
3.2 特征点匹配实验
为了验证改进后的SURF算法在图像特征点匹配准确性上的效果,针对同一组不同尺度的实验图像,分别使用传统SURF算法和改进SURF算法进行特征点匹配对比实验。实验考虑了同一物体在不同尺度下的影响因素,实验结果如图5所示。图5 a)展示了基于传统SURF算法的特征点匹配结果。该算法在非目标物体上也提取了特征点并进行了匹配,导致匹配结果混乱,图像匹配误差率较高。图5 b)展示了基于改进SURF算法的特征点匹配实验结果。相较于传统SURF算法,改进后的SURF算法的特征点匹配结果更为有序,匹配误差率也有显著改善。改进后的SURF算法能够更准确地匹配目标物体的特征点。
为了全面探究改进后的SURF算法相对于传统SURF算法的差异,本文对2种算法进行了更详细的比较,针对正确匹配数、错误匹配数、正确率和运行时间这4个方面进行了分析,结果如表1所示。在特征点匹配正确率方面,改进的SURF算法表现出了更高的正确率,达到了89.19%,而传统SURF算法的正确率仅为71.57%。此外,在错误匹配数方面,改进SURF算法明显优于传统SURF算法,错误匹配数仅为31个,而传统SURF算法的错误匹配数为85个。综合对比结果可以看出,本文设计的改进SURF算法在运行速度和特征点匹配正确率方面都有显著提高。
3.3 特征点匹配对比实验
本文采用公开数据集”Mikolajcyzk”进行实验。该数据集由Krystian Mikolajczyk等人创建,包含了城市景观、树木、墙面纹理等多种类型的图像,广泛用于评估特征提取、描述符匹配、目标识别等计算机视觉任务的性能。为了使模型更具普遍性,本文采用3组图像集,将其中2组图像集进行旋转和缩小处理。每组图像集含有6幅图像,第1幅图像为标准图像,其余5幅图像为待匹配图像,对3组图像集分别使用SITF算法、SURF算法、文献[17]提出的SURF-OKG算法及本文提出的改进的SURF算法进行图像特征点匹配。匹配结果如图6—图8所示。
通过对比匹配结果可知,SIFT算法虽然在缩小图像的匹配结果中正确率较高,但在旋转图像的匹配结果中相比于其他算法不够稳健,误匹配率仍然较高;SURF算法虽然可以较好地将特征点均匀化并剔除多余的错误匹配点,但同时也很明显地减少了正确匹配点,特征匹配结果较为稀疏;SURF-OKG算法提取到的特征点匹配数更多,但存在大量的误匹配点;改进SURF算法展现出更为有序的特征匹配结果,匹配误差率也有显著改善,在旋转和缩小方面都有较好的适应性,特征点分布更加密集且均匀,匹配正确率更高。针对3组图像集,SIFT,SURF,SURF-OKG和改进SURF算法的匹配正确率结果如图9所示。
通过对数据集图像的匹配结果进行分析,改进的SURF算法在匹配正确率上整体优于其他算法,尤其在缩小图像的特征点匹配中优势更为显著。不同算法的平均匹配正确率如表2所示。
由表2可知,改进SURF算法在缩小图像与原始图像中均达到了90%以上的平均匹配正确率。相比于SURF-OKG算法,改进SURF算法在旋转图像、缩小图像和原始图像中的平均匹配正确率分别提高了1.6,6.2和11.2个百分点。总的来说,本文提出的改进SURF算法在匹配正确率方面相较于传统算法有明显提升。
3.4 三维重建实验
为了进一步验证改进的SURF算法性能,并进行清晰地可视化分析,本文采用传统SURF和改进SURF的特征点匹配算法分别对同一图像序列进行三维重建实验。结果如图10所示。
在图10 a)中,展示了基于传统SURF算法的三维重建点云结果,可以观察到,3D点云呈现出较为稀疏的结果,想要清晰地呈现实际物体的轮廓比较困难。而在图10 b)中,展示了基于改进SURF算法的三维重建点云结果,从实验结果可以观察到,改进SURF算法的点云重建结果能够更好地凸显物体的形状和结构特征,同时减少了重建过程中的噪声和误差,产生了更真实和精确的三维重建结果。
综上所述,通过对改进SURF算法和传统SURF算法在三维重建中的对比分析可以得出,改进SURF算法在捕捉实际物体的细节和形状方面表现更加出色。改进SURF算法在特征点匹配精确度、重建完整性、形状准确性和稳定性方面均有了显著提升,这为三维重建技术的进一步发展提供了有力支持。
4 结 语
本文提出了一种改进的SURF图像特征点匹配算法,旨在提高特征点匹配的正确率和运行速率。该算法应用于三维重建技术的特征匹配具有一定的参考价值。主要结论如下。
1)改进后的SURF算法通过提高特征向量的维度,能够更准确地描述图像的局部特征,提高特征的表达能力。通过引入改进的KD-Tree特征匹配方法降低了计算复杂度,使得KD-Tree能够更准确地搜索最近邻点,从而提高了算法的性能。
2)相较于传统的SURF算法,改进后的SURF算法在特征点匹配正确率方面提高了17.62个百分点,相较于SURF-OKG算法,本文改进算法在旋转图像、缩小图像和原始图像中的匹配正确率分别提高了1.6,6.2和11.2个百分点。
本文的图像特征点匹配算法可以提高特征点的匹配正确率,减少运算时间,但当图像处于高曝光背景下时,在提取特征点的准确性方面仍显得有些乏力,使得匹配效果欠佳。今后将致力于继续提升算法在不同光照下的适配性,以增强算法的鲁棒性。
参考文献/References:
[1] 唐灿,唐亮贵,刘波.图像特征检测与匹配方法研究综述[J].南京信息工程大学学报(自然科学版),2020,12(3):261-273.
TANG Can,TANG Lianggui,LIU Bo.A survey of image feature detection and matching methods[J].Journal of Nanjing University of Information Science amp; Technology(Natural Science Edition),2020,12(3):261-273.
[2] 董鹏辉,柯良军.基于图像的三维重建技术综述[J].无线电通信技术,2019,45(2):115-119.
DONG Penghui,KE Liangjun.Overview of 3D reconstruction techniques based on images[J].Radio Communications Technology,2019,45(2):115-119.
[3] 黄海波,李晓玲,熊文怡,等.基于SIFT算法的图像配准综述[J].软件导刊,2019,18(1):1-4.
HUANG Haibo,LI Xiaoling,XIONG Wenyi,et al.A survey of image registration based on SIFT[J].Software Guide,2019,18(1):1-4.
[4] LI Yalan,HUANG Jianquan,DENG Fuming,et al.An image stitching algorithm based on SIFT and DAISY descriptor[C]//2020 4th Annual International Conference on Data Science and Business Analytics (ICDSBA).Changsha:IEEE,2020:271-274.
[5] 吴越,李胜旺,白宇.用于三维重建的改进特征匹配策略[J].河北科技大学学报,2019,40(5):423-430.
WU Yue,LI Shengwang,BAI Yu.Improved feature matching strategy for 3D reconstruction[J].Journal of Hebei University of Science and Technology,2019,40(5):423-430.
[6] 孟帅.基于SURF的图像拼接技术研究[D].湘潭:湖南科技大学,2019.
MENG Shuai.Research on Image Mosaic Technology Based on SURF[D].Xiangtan:Hunan University of Science and Technology,2019.
[7] 吴清辉.基于改进SURF特征点的模板匹配算法[J].机电工程技术,2021,50(6):208-211.
WU Qinghui.Template matching algorithm based on improved SURF feature points[J].Mechanical amp; Electrical Engineering Technology,2021,50(6):208-211.
[8] 肖明,鲍永亮,颜仲新.基于点特征的图像配准方法综述[J].兵工学报,2015(增刊2):326-340.
XIAO Ming,BAO Yongliang,YAN Zhongxin.A review of image registration methods based on point features[J].Acta Armamentarii,2015(sup2):326-340.
[9] WANG Wentong,WANG Changyuan,SI Lipeng.Infrared thermal imaging face expression recognition based on Harris algorithm[J].International Journal of Pattern Recognition and Artificial Intelligence,2023,37(12):2350021.
[10]ZHAO Peng,DUAN Suolin.SIFT image matching algorithm in view of improved SUSAN operator and affine invariance[J].IOP Conference Series:Materials Science and Engineering,2019,490(7):072001.
[11]GURRALA K V,TALASILA S,MADHURI P,et al.Enhancing safety and security:Face tracking and detection in dehazed video frames using KLT and Viola-Jones algorithms[J].International Journal of Safety and Security Engineering,2023,13(4):693-700.
[12]LIM I.Brief paper:Simplified tag identification algorithm by modifying tag collection command in active RFID system[J].Journal of Multimedia Information System,2020,7(2):137-140.
[13]ELORABI K A, ZEKRY A,MOHAMED W.Optimizing SIFT algorithm parameters for better matching UAV and satellite images[J].Journal of Physics:Conference Series,2023,2616:012044.
[14]CHEN Xuang,HAN Yan,DENG Heng,et al.Rail profile matching method based on stepped calibration plate and improved SURF algorithm[J].Engineering Research Express,2023,5(2):025061.
[15]江智,江德港,黄子杰,等.基于IB-SURF算法的无人机图像拼接技术研究[J].计算机工程与应用,2024,60(3):263-269.
JIANG Zhi,JIANG Degang,HUANG Zijie,et al.Research on UAV image stitching technology based on IB-SURF algorithm[J].Computer Engineering and Applications,2024,60(3):263-269.
[16]张蕾,石岩,卢文雍.基于SURF-OKG特征匹配的三维重建技术[J].光学精密工程,2024,32(6):915-929.
ZHANG Lei,SHI Yan,LU Wenyong.3D reconstruction technique based on SURF-OKG feature matching[J].Optics and Precision Engineering,2024,32(6):915-929.
[17]GOON L W,ENG S K.Offline signature verification system using SVM classifier with image pre-processing steps and SURF algorithm[J].Journal of Physics:Conference Series,2021,2107:012069.
[18]王卫兵,白小玲,徐倩.SURF和RANSAC的特征图像匹配[J].哈尔滨理工大学学报,2018,23(1):117-121.
WANG Weibing,BAI Xiaoling,XU Qian.Features image matching of SURF and RANSAC[J].Journal of Harbin University of Science and Technology,2018,23(1):117-121.
[19]赵谦,童申鑫,贺顺,等.改进的SURF-RANSAC图像匹配算法[J].计算机工程与设计,2021,42(10):2902-2909.
ZHAO Qian,TONG Shenxin,HE Shun,et al.Improved SURF-RANSAC image matching algorithm[J].Computer Engineering and Design,2021,42(10):2902-2909.
[20]吴学礼,闫枫,甄然,等.基于小波变换和K-SVD的探地雷达杂波抑制研究[J].河北科技大学学报,2021,42(2):111-118.
WU Xueli,YAN Feng,ZHEN Ran,et al.Research on adaptive clutter suppression for ground penetrating radar based on wavelet transform and K-SVD[J].Journal of Hebei University of Science and Technology,2021,42(2):111-118.
[21]XU Sixiang,DONG Chenchen,ZHOU Shuhua,et al.Binocular measurement method for the continuous casting slab model based on the improved BRISK algorithm[J].Applied Optics,2022,61(11):3019-3025.
[22]LI Jinqing,SHENG Yaohui,DI Xiaoqiang,et al.Range-gated laser image compression and encryption scheme based on bidirectional diffusion[J].Optoelectronics Letters,2021,17(10):630-635.
[23]徐瑞瑞,雷添杰,程结海,等.一种改进SURF算法的无人机影像快速配准方法[J].水利水电技术,2021,52(4):22-31.
XU Ruirui,LEI Tianjie,CHENG Jiehai,et al.AN improved SURF algorithm-based UAV image fast registration method[J].Water Resources and Hydropower Engineering,2021,52(4):22-31.
[24]BOTTANI E,VIGNALI G.Augmented reality technology in the manufacturing industry:A review of the last decade[J].IISE Transactions,2019,51(3):284-310.
[25]LIU Jinliang,BU Fanliang.Improved RANSAC features image-matching method based on SURF[J].The Journal of Engineering,2019,2019(23):9118-9122.
[26]GU Jiawei,LIU Gang,YANG Qingshan,et al.Improved SURF method in digital image correlation for estimation of large rotation angle[J].Measurement,2023,207:112372.
[27]MOGHIMI A,CELIK T,MOHAMMADZADEH A,et al.Comparison of keypoint detectors and descriptors for relative radiometric normalization of bitemporal remote sensing images[J].IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing,2021,14:4063-4073.
责任编辑:丁军苗
基金项目:河北省教育厅青年基金(QN2023185); 河北省高等学校科学技术重点研究项目(ZD2020318)
第一作者简介:王震洲(1978—),男,河北张家口人,教授,博士,主要从事智能制造及人工智能算法方面的研究。
通信作者:王建超博士。E-mail:wjc107960@163.com
王震洲,张森,宁超,等.基于改进SURF的图像特征点匹配算法[J].河北工业科技,2024,41(6):418-425.
WANG Zhenzhou,ZHANG Sen,NING Chao,et al."Image feature point matching algorithm based on improved SURF[J]. Hebei Journal of Industrial Science and Technology,2024,41(6):418-425.