胡旻涛, 彭 勇, 徐 赟
(江南大学 物联网工程学院,江苏 无锡 214122)
基于改进SURF的快速图像配准算法*
胡旻涛, 彭 勇, 徐 赟
(江南大学物联网工程学院,江苏无锡214122)
针对传统加速鲁棒特征(SURF)匹配算法存在实时性不高,误匹配等问题,提出了基于改进SURF特征提取快速的图像配准算法。利用快速黑塞(Hessian)矩阵提取图像特征点,根据图像熵信息对特征点进行筛选,采用改进的快速近邻搜索算法进行特征匹配,到用随机抽样一致(RANSAC)算法剔除误匹配对。实验表明:改进后的算法有效改善了匹配效率,提高了匹配准确度。
加速鲁棒特征; 图像熵; 最近邻搜索; 图像配准
图像配准是图像处理过程中的关键技术,在目标识别、图像拼接、变化检测、目标跟踪、三维重建等领域得到了广泛应用[1]。图像配准的算法主要分为基于灰度的匹配和基于特征的匹配两大类[2,3]。基于特征的匹配方法计算量小,鲁棒性强,是目前研究的主流。
2004年,Lowe D G提出了尺度不变特征变换 (scale invariant feature transform,SIFT)算法[4],通过构造尺度空间寻找极值点,提取极值点位置、尺度、旋转不变特征量对图片进行匹配。2006年,Bay H等人提出了加速鲁棒特征(speed up robust features,SURF)算法[5],该算法引入了积分图像和箱式滤波器,优化了特征点搜索的过程。Luo J等人通过测试验证了SURF算法,在图像发生尺度、光照、模糊变化时均有较好的鲁棒性并且提高了运算速度[6]。但在实际应用中,SURF算法有大量特征点未进行匹配,影响了匹配效率;高维数据的匹配开销也很大,占用了较多时间;同时也存在着匹配错误的情况。文献[7]将现有SURF特征改进,利用三角特征和对角线特征设计了新的描述算法,提高了算法的运算速度。文献[8]提出了一种改进算法,利用扩散距离代替欧氏距离进行匹配,利用随机抽样一致(RANSAC)算法从候选匹配中排除错误的匹配。文献[9]引入了扩展哈希算法,利用其较高的局部敏感性加速了高维特征向量的匹配。针对目前算法存在的问题,本文提出了一种改进的SURF算法,引入特征点筛选机制剔除冗余特征点,并结合改进的快速近邻搜索算法加速特征点匹配,并采用RANSAC算法减少误匹配对。
SURF算子的检测基于尺度空间,采用黑塞(Hessian)矩阵提取特征点。给定图像I中的某点(x,y),在该点处,尺度为σ的Hessian矩阵H(x,σ)定义为
(1)
SURF算子使用盒装滤波器,构造快速Hessian矩阵。根据图像的Hessian行列式值找出特征点的位置,并建立64位的特征描述向量,最后根据描述向量之间的欧氏距离实现特征点的匹配。
2.1 特征点检测算法改进
采用SURF算法提取特征点进行匹配时,当检测图像的细节比较丰富时,提取特征点的数量较大而且分布不均匀,导致后续特征描述和匹配的时间大幅增加,同时误匹配的数量也会增加,匹配效果变差[10]。通常,包含信息量较少的特征点成功匹配的几率远远小于信息量丰富的特征点。本文引入图像信息熵剔除冗余特征点。
对于一幅m×n的图像,信息熵[11,12]的近似公式为
(2)
pi,j=f(i,j)/σ2
(3)
为了尽可能保留图像细节,可将图像划分为不同区域,设定不同的图像熵阈值。区域中熵值大于该阈值的特征点则认为是有效的特征点,将其保留。具体特征点检测步骤:
1)利用快速Hessian矩阵遍历图像,计算每个点的行列式值,设定Hessian矩阵响应值阈值T,将图像中行列式值低的点去除。利用非最大值抑制法与插值法在其余的像素点中找到特征点;
2)将原图划分为3×3共9个区域,分别计算出每个区域的信息熵作为该区域的熵阈值,将每个区域中熵值小于熵阈值的特征点去除;
3)对保留的特征点采用原SURF算法构建成64位特征描述向量并进行归一化处理。
2.2 特征向量匹配算法改进
特征点匹配,通过某种相似性度量建立两类图像特征之间一一对应关系,一般采用欧式距离进行度量。欧氏距离越小,表明特征向量的相似度越高。特征向量P和Q的欧氏距离可以表示为
(4)
2009年,Muja M等人通过归纳总结提出了一种高维数据的快速最近邻匹配算法[13,14],但在实际应用中常常出现误匹配的问题。
本文提出了一种改进的快速近邻匹配算法。通过设定距离阈值删除相似度较低的匹配对,引入双向匹配机制确保匹配对的唯一性。算法步骤:
1)采用快速近邻匹配算法找到图像B中与图像A具有最小欧氏距离的初始匹配点并建立合集{p,p′};
2)根据所有匹配点对的欧氏距离d找出最小距离dmin,设置距离阈值D=μ×dmin。(本文μ=2);
3)判断匹配点对的距离与阈值的大小,若d≥D,则剔除该匹配点对;
4)按照上述方法再找出图像A中与图像B具有最小欧氏距离的匹配点对合集{q,q′},将两次匹配结果进行比较,只保留正反两次匹配结果一致的匹配点对。
根据最小距离dmin设定的距离阈值能有效过滤不相干的匹配点对,同时图像双向匹配策略能够保证匹配点对的唯一性,提高了匹配正确率。
2.3 随机样本一致性算法
上述初始计算得到的匹配集中仍包含有错误的匹配点对,可以使用随机样本一致性 (random sample consensus,RANSAC)算法去除误匹配对。RANSAC算法是一种基于概率的鲁棒的参数估计法,计算得到有效样本数据。具体步骤如下:
1)将匹配结果作为候选匹配特征集,从候选匹配特征点对中随机选取4组匹配点建立方程组,估计变换矩阵M的8个未知参数。
2)计算剩余特征点经过变换矩阵M的变换,并计算与其候选匹配点之间的距离,距离小于某一阈值,则该候选特征点为内点;否则,为外点。
3)找出内点数目最多的估计,将判断出的外点剔除,用所有内点进行最优参数估计。
实验硬件环境为Windows 10系统,CPU Intel(R) Core(TM)i5—4200 2.8 GHz,8 GB内存的PC机;软件开发平台为Visual studio 2010和OpenCV2.4.9。使用ukbench标准图像库[15]进行算法测试,所有图片分辨率均为640×480。
3.1 图像匹配效果实验
在标准图像库中选取4幅具有典型变换特征的图像进行实验,测试图像如图1所示。
图1 实验图像
为了验证算法的性能,引入recall vs 1-precision曲线作为评价标准。其中召回率(recall)指所有正确的特征点被检测出的比例,精度(precision)指检测出的点中正确的比例。当曲线越靠近Y轴时说明匹配效果越好。如图2为图像发生尺度、模糊、旋转、光照变化下2种算法的性能比较。可以看出:在不同的环境下本文的算法的曲线整体高于原SURF算法,更靠近Y轴,说明匹配效果更好,能更好地完成实际需求。但2种算法在旋转变换时匹配效果欠佳。
图2 不同环境情况下图像匹配性能比较
3.2 图像匹配效率实验
在标准数据库中选取50组图片进行测试。表1统计了2种算法检测出的平均匹配对数,平均准确率和平均匹配时间。分析数据可知:改进后的算法因为引入了基于图像熵的特征点筛选机制,删除了部分冗余的特征点,减少了特征向量描述和匹配的时间,提高了算法的速度,并且提高了匹配的准确率,证明了本文算法在各种情况下均能保持较好的鲁棒性。
表1 本文算法和SURF算法匹配效率比较
分析了目前SURF算法所存在的问题,提出了一种改进的SURF算法。利用快速Hessian矩阵检测特征点,引入图像信息熵筛选特征点,用改进的快速近邻算法进行特征向量匹配,采用RANSAC算法剔除误匹配,有效地减少了计算时间,并且提高了匹配准确率。实验表明:本文算法在缩放、旋转、光照、模糊变化下均有良好的鲁棒性。下一步工作将在运动目标跟踪和定位方面展开。
[1] 卢 浩,胡华平,刘谭博怡.图像特征提取与匹配[D].北京:中国科学院自动化研究所,2008.
[2] Goshtasby A A.References[M]∥2D and 3D image registration:For medical,remote sensing,and industrial applications.Hoboken:John Wiley & Sons Inc,2005.
[3] Duan C,Meng X,Tu C,et al.How to make local image features more efficient and distinctive[J].Iet Computer Vision,2008,2(3):178-189.
[4] Lowe D G.Distinctive image features from scale-invariant key-points[J].International Journal of Computer Vision,2004,60(2):91-110.
[5] Bay H,Tuytelaars T,Gool L V.SURF:Speeded up robust features[J].Computer Vision & Image Understanding,2006,110(3):404-417.
[6] Luo J,Gwun O.A comparison of SIFT,PCA-SIFT and SURF[J].International Journal of Image Processing,2009,3(4):143-152.
[7] 刘少鹏,郎跃东,丁祝顺.改进的SURF算法及其在目标跟踪中的应用[J].传感器与微系统,2012,31(12):148-152.
[8] 贡 超,蒋建国,齐美彬.基于扩散距离的SURF特征图像匹配算法[J].合肥工业大学学报:自然科学版,2015,38(4):474-478.
[9] 吴铭心.一种基于SURF和扩展哈希的空间约束图像匹配算法[J].重庆师范大学学报:自然科学版,2015,32(2):104-110.
[10] 高素青,谭勋军,黄承夏.一种基于SURF的图像配准改进算法[J].解放军理工大学学报:自然科学版,2013,14(4):372-376.
[11] 聂仁灿,周冬明,赵东风.基于Unit-Linking PCNN和图像熵的图像分割新方法[J].系统仿真学报,2008,20(1):222-227.
[12] 杨作廷,阮 萍,翟 波.基于图像熵的高动态范围场景的自动曝光算法[J].光子学报,2013,42(6):742-746.
[13] Muja M,Lowe D G.Scalable nearest neighbor algorithms for high dimensional data[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2014,36(11):2227-2240.
[14] 梁艳菊,李 庆,林蓁蓁,等.一种基于SURF的全景图像配准算法[J].传感器与微系统,2012,31(5):132-135.
[15] The University of Kentucky Center for Visualization & Virtual Environments.Object recognition benchmark[EB/OL].(2016—04—12)http:∥www.vis.uky.edu/~stewe/ukbench/.
FastimagematchingalgorithmbasedonimprovedSURF*
HU Min-tao, PENG Yong, XU Yun
(SchoolofInternetofThingsEngineering,JiangnanUniversity,Wuxi214122,China)
Aiming at problem of poor real-time and false matching of images matching algorithm based on speed up robust features(SURF),present an images matching algorithm based on improved SURF.Features point of image is extracted by using the Fast-Hessian matrix.Features point is sifting by image entropy information.RANSAC algorithm is used to exclude mistake matching pair.The experiments show that this algorithm improves matching efficiency,and improve matching accuracy.
speed up robust features(SURF); image entropy; nearest neighbor search; image matching
10.13873/J.1000—9787(2017)11—0151—03
TP 391.41
A
1000—9787(2017)11—0151—03
2016—11—28
江苏省交通运输厅资助项目(2012X08—2)
胡旻涛(1991-),男,硕士研究生,主要研究方向为机器视觉、嵌入式系统,E—mail:420855432@qq.com。