一种改进的基于SURF特征匹配的图像拼接算法

李海洋,张睿哲

(1.绵阳师范学院 数学与计算机科学学院, 四川 绵阳 621000;

2.平顶山学院 计算机科学与技术学院,河南 平顶山 467002)



一种改进的基于SURF特征匹配的图像拼接算法

李海洋1,张睿哲2

(1.绵阳师范学院 数学与计算机科学学院, 四川 绵阳 621000;

2.平顶山学院 计算机科学与技术学院,河南 平顶山 467002)

摘要:针对快速鲁棒特征(SURF)算法的拼接结果图像，会出现明显的拼接线与过渡带的问题,提出一种改进的基于SURF特征匹配的图像拼接算法。在剔除误配点时,采用改进的随机抽样一致(RANSAC)算法调整采样概率,以更少的时间获取正确模型,提高算法效率。在图像融合时,先对输入图像进行亮度均衡预处理,然后再使用加权平滑算法进行融合,从而消除结果图的拼接线和过渡带,提高图像拼接质量。实验表明,改进算法能保持SURF算法的优良特性,进一步提高SURF算法匹配效率,并能有效消除拼接线和过渡带,使图像拼接质量得到显著提高。

关键词:图像拼接；快速鲁棒特征；随机抽样一致；加权平滑算法；亮度均衡

图像拼接是将相互间具有重叠区域的图像序列进行空间匹配对准,最终拼接为一幅具有较宽视角全景图像的技术[1]。目前被广泛应用和研究的图像拼接技术是基于特征点的图像拼接技术。2004 年,LOWE[2]提出了尺度不变特征描述算子(SIFT),对光照变化、几何变形、分辨率差异、旋转具有一定不变性；但SIFT 算法计算量大,难以满足实时性应用的要求。2006年,BAY，et al[3]提出了SURF算法,对SIFT算法进行了改进。SURF算法不但继承了SIFT算法的优点,而且具有更好的鲁棒性和更快的计算速度,因此被广泛应用于图像配准。2010年,刘奇，等[4]将SURF算法应用于图像拼接,取得了良好的拼接效果。2013年,韩天庆，等[5]基于SURF特征点匹配,采用空间约束方法,取得了较好的无人机影像拼接效果。桂振文，等[6]改进并提高了SURF算法的配准效率,并应用于智能手机,实现了对场景的实时识别。然而,以上算法仍然存在一些不足。有的算法提高了图像拼接质量,但却牺牲了拼接效率;有的算法提高了拼接效率,但却降低了拼接质量。因此,如何改进SURF算法,同时获取更好的图像拼接质量和拼接效率,还需要进一步研究。

RANSAC是由 FISCHLER，et al[7]提出的一种采用迭代法来估计参数的数学模型,具有精度高、鲁棒性强等优点,常常用于图像配准,对误配点进行剔除；但是,用RANSAC计算参数时,迭代次数多,运算耗时。刘坤，等[8]提出一种概率引导的RANSAC算法,通过调整每个样本点的采样概率,使得正确样本和正确模型被采样的概率得到提高,迭代次数较少,能有效提高RANSAC算法的效率。张红民，等[9]提出一种改进的相邻概率随机抽样一致性算法,在数据外点率较高的情况下,能有效减少迭代次数,缩短算法时间,从而提高了RANSAC算法效率。在图像融合时,张亚娟[10]对平均值法、加权平滑法、最大值法等常见融合算法进行了对比分析和综合改进,获得了较为满意的图像融合结果。闫莉萍，等[11]提出一种新的目标函数, 结合亮度最大值和加权平滑法,对目标函数进行迭代寻优, 能有效改善图像融合效果。

笔者提出了一种改进的基于SURF的图像拼接算法。在剔除误配点时,采用了文献[8-9]提出的改进的概率随机抽样一致性算法,通过不断调整采样概率,从而以更少的时间获取正确模型,提高算法效率。在图像融合时,借鉴文献[10-11]的思想,先对输入图像进行亮度均衡预处理,然后再使用加权平滑算法进行融合,从而消除结果图的拼接线和过渡带,提高图像拼接质量。

1基于SURF 的图像拼接算法

1.1SURF 特征点的提取与匹配

SURF特征点提取主要包括判断特征点位置,建立尺度空间,确定特征点主方向,构建特征向量等步骤。

SURF在判断特征点位置时,通过盒型滤波近似地代替二阶高斯滤波,然后利用积分图像来加速卷积速度。设Dxx，Dxy，Dyy为近似的不同方向的盒型滤波模板,w是个权重系数(一般取w=0.9),经简化近似后,Hessian矩阵的行列式如式(1)所示：

(1)

然后,采用不同尺度的滤波模板与图像做卷积运算,得到不同尺度下的滤波响应值,建立尺度空间。

通过对扇形滑动窗口内图像的Haar小波的响应值进行累加,从而得到向量(mw,θw),其中,

(2)

则特征点主方向为最长向量对应的方向,即:

(3)

在构建特征向量时,首先以特征点为中心,沿特征点主方向构造一个20s×20s的矩形区域,并划分为4×4 个子窗口,则每个子窗口中具有 5s×5s个像元。然后,每个子窗口用尺寸为2s的Haar小波模板计算其响应值。最后,统计出水平方向和竖直方向的Haar小波响应∑dx，∑|dx|，∑dy，∑|dy|,从而得到第i个子窗口的特征向量:

提取出图像的特征点后,SURF通过计算两个特征点描述向量的欧氏距离进行特征点匹配。设,某特征点描述符为pi,其最近和次近的两个相邻特征点的描述符为qi1和qi2。两组描述符pi与qi1、pi与qi2的欧氏距离比值如式(4)所示。

(4)

设,阈值为r0,若rr0,则点对(pi,qi1) 为匹配点,否则为非匹配点。

1.2图像配准

根据找到的匹配特点对,可计算出图像间的坐标转换关系,即两幅图像之间的变换矩阵。

设,图像间的变换为投影变换，那么，

若p=(x,y),q=(x′,y′)是匹配的特征点对,则投影变换公式为:

(5)

由投影变换公式可计算出H的各自由度参数hi(i=0,1,2,…,7),并以此作为初始值,通过迭代精炼H,可进一步确定特征点的对应,直到对应点数目不变为止,从而完成图像配准。

1.3误配点剔除

RANSAC 是一种采用迭代法来估计参数的数学模型,具有可靠、稳定、精度高、鲁棒性强等优点。因此,文献[4-6,10-11]在图像配准时,均采用RANSAC对图像变换矩阵进行精炼,以剔除误配点,提高图像配准精度。使用RANSAC剔除误配点时,首先在所有匹配点中任取两点确定一条直线进行直线拟合,在拟合误差距离范围内的点称为内点,否则为外点,如图1所示。

图1　RANSAC直线估计Fig.1　Linear estimates of RANSAC

然后,在内点集中重新计算出一条新的直线进行拟合,通过不断迭代,直到找到一个最大内点数量的拟合作为拟合结果,即可剔除误配点。

1.4图像融合

图像融合算法中常用的是加权平滑法。设,融合结果图为I,两幅待拼接图像的重叠区为I1和I2,则加权平滑法图像融合如式(6)所示。

(6)

2改进的基于SURF的图像拼接算法

用RANSAC来剔除图像配准的误配点时,迭代次数越多,参数估计的精度越高。但是,用RANSAC计算参数时,迭代次数越多,运算越耗时。另外,由于加权平滑法在输入图像接合部位采用了平滑过渡,因此可以有效消除拼接线。在输入图像亮度一致情况下,使用加权平滑法就能达到较好的融合效果。但是,在输入图像亮度差异较大情况下,由于加权平滑法只是对两幅待拼接图像的重叠区进行平滑处理,所以仍会在重叠区形成较为明显的过渡带。因此,需要对经典的基于SURF的图像拼接算法进行拼接效率和拼接质量的改进。

2.1RANSAC改进

在每次随机选取子样本时, RANSAC 算法的采样概率相等,并需要多次迭代采样才能保证至少有一次采样获得正确模型。所以,可以通过改进随机采样的过程,利用每次抽取的最小子样本来估计模型参数, 再根据该模型调整子样本在后面抽样中被选取的概率。 经过不断迭代抽取检验之后, 获得正确临时模型的概率逐渐被提高,从而花费较少的时间获取正确模型,就能提高算法效率。

概率阈值为p;临时内点集S, (Si,Sj)是S中任意点对,其欧氏距离d=‖Si-Sj‖,欧氏距离阈值为D。改进RANSAC算法流程[8-9]如图2所示。

图2改进RANSAC算法流程Fig.2　Process of improved RANSAC algorithm

2.2图像融合改进

为了获得自然的拼接结果图,笔者采用直方图均衡化方法对输入图像进行亮度预处理,使输入图像亮度达到均衡,然后再使用加权平滑法进行图像融合,这样既不会产生过渡带,又能有效消除拼接线。具体操作方法如下。

1) 将重叠区图像直方图归一化,获得重叠区像素值的概率密度函数的均衡化公式。首先进行重叠区图像直方图计算,由于重叠区图像直方图表示重叠区像素值频率,所以将其每个频率除以重叠区总的像素就可得每个像素值出现的概率p(w),由此得到重叠区像素值的累积分布函数如下:

(7)

式中：w为任意变量。

2) 根据式(7),建立输入图像像素值映射关系,对图像的每个像素进行映射调整。

设,输入图像为I1、I2,取直方图较为平和的图像(如I1)作为参考图像,对I2的每个像素值(0≤g≤255)进行调整,使I2按I1的光照调整,如图3所示。

图3　图像光照均衡的累积分布函数图Fig.3　Cumulative distributed functionof the luminance equilibrium image

由图3可知,参考图和待调整图分别在g1和g2像素值下具有相同的累积分布函数值,即:FCD(g1)=FCD(g2)。然后,把I2图像中所有像素值为g1的像素映射为g2。按照以上类似操作,对I2所有灰度级进行调整。如果待调整图和参考图具有相同的累积分布函数值,则将待调整图像素值调整为参考图对应的像素值;如果参考图和待调整图没有相同的累积分布函数值(图3所示的长横虚线),则待调整图在该灰度级保持原有像素值。

3) 将调整后图像作为输入图,使用加权平滑法对其进行融合。由于经过映射调整后的输入图具有基本一致的亮度,因此能消除拼接线和过渡带,生成较为自然的拼接结果图。

3实验结果和分析

3.1实验环境与数据

本研究在多幅图像上对SURF算法和本文算法进行了图像拼接实验。实验环境如下:CPU为IntelCorei7 @ 2.67GHz,内存4GB,显卡NvidiaNVS3100M,操作系统Windows7,开发软件为MatlabR2012a。下面以其中一组实验图像为例给出实验结果。实验图像原图如图4所示,原图4-a图像大小为61KB,尺寸527*393像素;原图4-b图像大小为167KB,尺寸522*387像素。这一组图像是通过手机在不同视角手持拍摄,保证了待拼接图像在尺度和亮度上的差异。

图4　实验原图Fig.4　Original images of experments

3.2图像配准实验

为了证明对RANSAC改进的有效性,本文给出了SURF+RANSAC及SURF+改进RANSAC的图像配准实验结果,如图5所示。

图5　不同算法的图像配准实验结果Fig.5　Image matching experiment results of different algorithms

其中,图5-a是经典的SURF+RANSAC配准结果,图5-b是本文SURF+改进RANSAC配准结果。通过这两幅结果图像的比较可以看出(如图5-a中箭头所示,误配点已经被剔除),本文的SURF+改进RANSAC配准结果更加精确,说明了对RANSAC的改进有效,比经典RANSAC具有更好的提纯效果。

为了定量说明改进RANSAC的有效性,本研究对RANSAC与改进RANSAC进行了性能比较,比较结果如表1所示。

表1　RANSAC与改进RANSAC的性能比较

从表1可以看出,相比于经典的SURF+RANSAC算法,本文算法在特征点检测数目和匹配的点数上均略有降低,在运行时间上有大幅降低。

以上结果说明了本文算法以牺牲较小的稳定性为代价,取得了配准质量的提高,并大幅提高了配准效率。

3.3图像拼接实验

为了证明对本文改进融合算法的有效性,本文给出了SURF+RANSAC直接拼接(以下简称算法A)、经典的SURF+RANSAC+加权平滑融合(以下简称算法B)以及本文算法(SURF+改进RANSAC+亮度均衡+加权平滑融合)最终的图像拼接实验结果,如图6所示。

图6　三种算法实验结果比较Fig.6　Image stitching experiment results ofthree different algorithms

图6-a是算法A的图像拼接结果,可以看出,算法A拼接结果存在非常明显的拼接线,如图6-a向右箭头和向下箭头所指。

图6-b是算法B的图像拼接结果,可以看出，算法B拼接结果消除了明显的拼接线,但在图像重叠区部分出现了过渡带,如图6-b左右箭头所指区域。

图6-c是本文算法的图像拼接结果,可以看出,本文算法不但消除了算法A的拼接线,而且没有产生算法B的过渡带,具有自然的视觉效果。

为了进一步说明本文算法的有效性,本研究在图像拼接实验的同时,记录了以上三种算法的运行时间,结果如表2所示。

表2三种算法的运行时间比较

Table2Runningtimesofthedifferentalgorithms

ms

从表2可以看出,算法A运行时间最少,本文算法次之,算法B运行时间最长。相对于算法B,本文算法运行时间较少,本文算法效率略微占优,大约提高效率10%。

综上所述,算法A效果差而效率高;算法B效果较好但效率最低;本文算法不但效果最好,而且具有较好的效率。本文算法拼接效果优于算法B的原因在于对图像进行加权平滑融合前,对输入图像进行了亮度均衡,因而提高了图像融合质量。相对于算法B,本文算法拼接效率提高的原因在于在特征点提纯时,对经典RANSAC进行了改进,能以较少的迭代次数找到正确的估计模型,因而较大幅度地提高了效率。相对于算法B,本文算法最终效率提高不大的原因在于,本文在改进图像融合算法时进行了亮度均衡预处理,增加了图像融合时间,需进一步加以研究改进。此外,本文算法在图像融合前采用了直方图均衡化方法对输入图像进行亮度预处理,应选择直方图较为平和的图像作为参考图像,否则容易造成最终结果图失真,这一缺点也需要研究克服。

4结论

笔者提出了一种改进的基于SURF特征匹配的图像拼接算法,通过改进RANSAC降低了图像配准迭代次数,提高了算法效率;通过改进加权平滑算法实现拼接线和过渡带的消除。实验结果表明,改进算法在效率有所提高情况下,能取得比经典SURF拼接算法更优的拼接效果。

参考文献：

[1]朱琳,王莹,刘淑云,等.基于改进快速鲁棒特征的图像快速拼接算法[J].计算机应用,2014,34(10):2944-2947.

[2]LOWEDG.Distinctiveimagefeaturesfromscale-invariantkeypoints[J].InternationalJournalofComputerVision,

2004,60(2):91-110.

[3]BAYH,TUYTELAARST,GOOLLV.SURF:speededuprobustfeatures[J].ComputerVisionandImageUnderstanding,2008,110(3):346-359.

[4]刘奇,何明一.基于SURF特征匹配的图像拼接算法[J].测控技术,2010,29(10):27-31.

[5]韩天庆,赵银娣,刘善磊,等.空间约束的无人机影像SURF特征点匹配[J].中国图象图形学报,2013,18(6):669-676.

[6]桂振文,陈靖,刘越,等.一种智能手机上的场景实时识别算法[J].自动化学报,2014,40(1):83-91.

[7]FISHLERMA,BOLLESRC.Randomsampleconsensus:aparadigmformodelfittingwithapplicationstoimageanalysisandautomatedcartography[J].CommunicationsoftheACM,1981,24(6):381-395.

[8]刘坤,葛俊锋,罗予频,等.概率引导的随机采样一致性算法[J].计算机辅助设计与图形学学报,2009(5):657-662.

[9]张红民,曾祯.一种改进的相邻概率随机抽样一致性算法[J].激光杂志,2013,34(5):29-30.

[10]张亚娟.基于SURF特征的图像与视频拼接技术的研究[D].西安:西安电子科技大学,2013.

[11]闫莉萍,刘宝生,周东华.一种新的图像融合及性能评价方法[J].系统工程与电子技术,2007,29(4):509-513.

(编辑：朱倩)

An Improved Image Stitching Algorithm Based on SURF Feature Matching

LI Haiyang1,ZHANG Ruizhe2

(1.SchoolofMath&ComputerScience,MianyangNormalUniversity,MianyangSichuan621000,China;2.ComputerScienceandTechnicAcademyDepartment,PingdingshanUniversity;PingdingshanHenan467002,China)

Abstract:Speed up Robust Features(SURF) algorithm is widely used in the field of image processing owing to its excellent invariance of scale, rotation, illumination and its faster calculation speed than SIFT. However, it is still hard to meet the demands in some high real-time applications and its calculation speed still needs to be further improved. In addition, when used in image matching, its image stitching results appear obvious stitching seam and transition zone because of the differences of the luminance in the original images. In order to overcome these disadvantages, this study proposes an improved image stitching algorithm based on SURF feature matching. In image matching, the random sample consensus (RANSAC) algorithm is improved to eliminate the false matching points and to reduce the iterations,resulting in improved efficiency of algorithm. In image fusion, the weighted average algorithm is improved to eliminate the stitching seam and the transition zone, resulting in improved quality of image stitching. Experimental results show that the improved algorithm can keep up the stability of SURF and effectively eliminate the stitching seam and the transition zone while its matching efficiency is further improved. Compared with classic image stitching algorithm based on SURF, the proposed algorithm has better stitching results and higher efficiency.

Key words:image stitching;speed up robust features;random sample consensus;weighted average algorithm;luminance equalization

中图分类号:TP391.41

文献标识码:A

DOI：10.16355/j.cnki.issn1007-9432tyut.2016.01.018

作者简介：李海洋(1972-)，男，四川双流人，副教授，主要从事图形图像处理、优化技术的研究，(E-mail)lhy1301@126.com

基金项目：四川省科技厅资助项目：基于色彩熵的半监督图像检索研究(2012JYZ013)；四川省教育厅资助项目(12ZB070)；绵阳师范学院资助项目(2013A12)

收稿日期：2015-05-19

文章编号:1007-9432(2016)01-0091-05