基于结构信息的图像拼接算法①

韩伟东,闵士桐

(东北大学 理学院,沈阳 110004)

图像拼接研究已有数十年,拼接算法也较为成熟.近年来,关于灰度信息的方法研究也逐渐减少,现在提出关于彩色图像的CSIFT[1](A SIFT Descriptor with Color Invariant Characteristics)算法,对于医学图像和遥感图像拼接研究占了很大比例.利用Harris算子提取特征[2]时,由于无法去除误配点对,Capel[3]在利用Harris算子提取特征点的同时,引入RANSAC (Random Sample Consensus)[4]算法,去除由Harris提取的误配点对,进一步提高精度.而Harris算法不能处理尺度变换图像.Lowe在文献[5]中提出SIFT (Scale Invariant Feature Transform)算法及改进.提取特征的算法还有点特征提取算子 (如Harris算子和改进算子、Susan算子及其改进算子[6])、线特征提取算子 (如LOG算子[7]、Canny算子及其改进算子[8])和区域特征提取算子[9]等.2001年,EFROS提出了基于图像渲染的纹理合成算法[10],进行了对纹理渲染以及合成.2012年,Xu基于相对总变差模型的图像结构提取方法.本文将利用这种算法与图像配准算法相结合,处理纹理多、背景复杂的图像拼接问题.

1 图像配准概念

相机将三维空间场景拍成二维是一种映射关系.拍摄时,世界坐标系 (Xw,Yw,Zw)、相机坐标系 (XC,YC,ZC)、图像坐标系 (X,Y)三者关系[11]如图1所示.

图1 相机成像坐标系

点由世界坐标系到相机坐标系,最后在投影到图像平面上.图像配准就是对这种图像变换的关系进行求解,使得两幅图像上对应像素点位置保持一致.对于参考图像I1和带配准图像I2,在点 (x,y)处的灰度值可以分别表示为I1(x,y)和I2(x,y),则两幅图像可以表示为:

图像配准目的是找到映射T,使得将两幅图变换为同一坐标系.

对图像处理的配准方法有如下3类:

1)基于图像灰度信息的配准方法

利用搜索算法找出时的相似度最有变换模型.基于图像灰度信息的配准方法一般可以分为3类:基于互相关法[12]、基于序贯相似度检测匹配法[13]、基于互信息法[14].

2)基于变换域内信息的配准方法

利用傅立叶变换为基础进行频域内的配准.算法具有一定抵抗噪声的鲁棒性.

3)基于图像特征信息的配准方法

提取点、线、边缘等特征信息,减少计算量、提高时间效率,对图像的灰色变化有一定鲁棒性.

2 图像结构信息的拼接算法 (SKM)

对于两幅或多幅图像进行拼接时,提取出的图像特征点的好坏对图像拼接具有巨大影响.

SIFT (Scale-Invariant Feature Transform)[1]算法是一种较好的局部特征提取算法.但是在存在较多的纹理结构噪声的图像中,利用SIFT算法提取特征点,会提取数量较大的特征点,影响匹配的效率和准确性.如图2流程图所示,本文引用RTV (Relative Total Variation)算法[15]提取图像结构信息,有效地去除图像纹理噪声.在此基础上再对结构图像进行SIFT特征的提取与匹配,然后利用RANSAC (RANdom SAmple Consensus)[4]算法对匹配进行筛选,并将左右两侧的图像进行亮度调整.由SKM算法得到变换矩阵H,作用于两幅原图像,完成图像的拼接.

图2 SKM算法流程图

2.1 基于总变差模型的图像主结构提取算法

图像纹理的去除选用既有的基于相对总变差模型的纹理结构提取方法 (RTV)[15],在图像拼接之前对给定的两幅照片进行主结构提取,然后进行拼接.该算法较其之前的双边过滤等算法处理图像的程度更强,效果也更加明显,可以充分保证对可能出现在纹理之上的特征点的过滤.

在此算法中,定义总变差量度:

其中,q属于以像素p为中心的矩形区域R(P).Dx(p)和Dy(p)是x和y方向上对于像素p的图像总变化,用来计算R(P)内部的绝对空间差异.gp,q是加权函数,表示为:

其中,σ控制窗口的空间尺度.在纹理突出的图像中,表明图像总变化的细节像素和的结构像素变差量度 D 都对视觉显着性有作用.

为了帮助区分突出的结构和纹理元素,需要计算图像固有的变化量,表示为:

L捕获整体空间变化.因为就方向而言,一个像素的∂S的符号可能是正的或负的,所以∂S的符号取决于图像中的颜色梯度是否一致.

由于一个局部图像中的边缘比复杂图案的纹理能提供更多相近方向的渐变,算法假定在一个图像中产生的L 包含的纹理通常小于图像中包括结构边缘的纹理,即噪声的变差要比图像的自然变化产生的基本变差大.为进一步增强纹理与结构之间的对比 (尤其对于视觉上显着的区域),将D 与L 组合形成一个更有效的纹理分解正则化器.从图像中去除纹理的效果由正则化器引导,该项称为相对总变差 (RTV).目标函数最终表示为:

其中,(Sp-Ip)2可使输入和结果不会产生较大偏差.从图像中去除纹理的效果由正则化器引导,该项称为相对总变差 (RTV).λ为权重.ε为一小量,从而使分母不为0.

通过求解该最小值来提取结构图像.以x方向为例:

设

其中,Gσ为标准差为σ的Gaussian核函数,*表示卷积.y方向讨论类似.原目标函数可以写成矩阵形式:

其中,vS和vI分别代表S和I的两个列向量,Cx和Cy是向前差分梯度算子的Toeplitz矩阵,Ux,Wx,Uy,Wy为对角矩阵,对角元素分别为Ux[i,i]=Uxi,Uy[i,i]=Uyi,Wx[i,i]=Wxi,Wy[i,i]=wyi.模型最终表示为:

在计算机程序中,RTV算法函数有两个主要参数λ和ε.λ参数控制处理强度,取值范围为 (0,0.05];ε参数控制最终结果的锐度,该值越小,结果图像的锐度越高,取值范围为 (0.001,0.03].

2.2 基于结构信息的配准算法

SIFT算法基于尺度空间理论[16],对于图像的缩放、旋转、仿射变换保持较好的稳定性.SIFT算子可以在纹理较少的图像中提取更多特征,具有良好的性质.但在较多纹理的图像中,该算子将提取较多的特征点.所以对于一般具有较多纹理噪声的图像,利用RTV算法对图片纹理处理,再利用SIFT特征点的提取进行匹配.通过由SKM算法得到的变换矩阵H作用于原始图像,从而完成对图像进行拼接.

SIFT算法实现[17]如下:

1)构建图像的尺度空间

文献[18,19]中Lindeberg等人证明Gaussian核是实现尺度变换的唯一线性变换核.图像的尺度空间L(x,y,σ)可以定义为图像I(x,y)与高斯核函数G(x,y,σ)的卷积,

其中,σ是尺度因子,σ越小,在视觉上图像就越清晰,σ越大,图像越模糊,表示卷积,(x,y)代表像素的位置.

为了在尺度空间中检测到稳定的特征值点,采用高斯差分尺度空间 (DoG空间,即Difference of Gaussian scale-space),DoG算子定义为两个相邻尺度的Gaussian核间的差分,公式表示为:

其中,k表示两个相邻尺度空间倍数的常数.

式(14)是由尺度归一化的LoG (Laplace of Gaussian)函数 σ2∇2G近似得到,LoG算子的极值能够产生稳定的图像特征.用DoG算子来代替尺度归一化的LoG算子进行极值检测,在实际计算过程中,将高斯金字塔 (如图3)中每组图像中的相邻的上下两幅图像的像素值相减,得到高斯差分图像.

图3 高斯金字塔模型

如图4,左边的图像是由初始图像开始形成的高斯金字塔图像,每一阶的第一个图像是由上一阶的最后的高斯图像进行降采样得到的.

2)空间极值点的检测

对尺度空间DoG函数进行曲线拟合 (子像素插值),利用DoG函数在尺度空间Taylor展开.

图4 高斯差分图像的形成

将修正因子代入,得到:

上式去除那些对比度较低的不稳定极值点.Lowe的试验显示,所有取值小于0.04的极致点均可舍去.

DoG算子具有较强的边缘响应现象,一个较差的DoG算子的极值在横跨边缘的地方有较大的主曲率,而在垂直边缘的方向有较小的主曲率.主曲率可由Hessian矩阵得到:

H的特征值α和β代表x和y方向的梯度:

D的主曲率和H的特征值成正比,其中α和β分别为矩阵H中的较大与小特征值.令α=γβ,则

当γ越大时,即在某一个方向的梯度值越大,而在另一个方向的梯度值越小,(γ+1)2/γ值越大,为了剔除这样的边缘响应点,需要设置一个阈值R(在Lowe的文章中,R取10),可通过如下公式来检测判断是否需要剔除极值点,

3)特征点方向分配与描述向量的生成

为使算子具有旋转不变性,利用特征点的邻域像素梯度给分配一个方向参数.对在DoG金字塔中求得的特征点,求其所在的金字塔图像中3σ邻域内像素点的梯度和方向分布,梯度的大小及方向为:

用一个梯度方向的直方图进行统计,范围0～360度,其中每10度一个柱.每个采样点按照其梯度方向θ(x,y)加权统计到直方图,权值为幅度m(x,y)和贡献因子的乘积.贡献因子是采样点到关键点距离的量度,距离越大,贡献因子越小.直方图的峰值代表了该关键点处邻域梯度的主方向.

接着将坐标轴的方向旋转为特征点的主方向,并以特征点为中心选取16×16的邻域窗口,将窗口平均地划分为16个4×4的区域,在区域内求取8个分区的梯度直方图,利用 Gaussian函数进行加权处理,如图5所示,得到一个16×8维的向量,最后将向量进行归一化处理,减少光照的影响,生成特征点的描述向量.

图5 图像描述算子的生成

图5中左图为特征描述子生成时其四分之一的像素的梯度方向,圆圈表示高斯加权的范围,右图为加权到8个方向后生成的描述子.

4)特征点匹配与筛选

以特征向量的欧氏距离作为特征点判定相似性的度量,取图像中某个特征点,找出与另一图像中距离最近的两个特征点,如果最近距离与次近距离的比值小于某个阈时就接受这对匹配点,阈值一般取0.4～0.6之间.阈值越小,求出的匹配点对越少,匹配的稳定性越高.最后利RANSAC算法筛选匹配点[20-22],去掉匹配错误的点,提高匹配精度.利用这个模型测试所有数据,并计算满足这个模型数据点的个数与投影误差 (即代价函数),选出最优模型即代价函数最小.

具体步骤如下:

(1)从匹配点集中随机选出4组匹配点对.

(2)计算变换矩阵H:

其中,s是尺度参数.

(3)通过变换矩阵H,对匹配点进行变换,并设置误差度量函数,如果匹配点对变换后不超过误差,则认为是一致集中的元素,遍历完所有点对后,返回一致集中的元素个数.根据一致集中的元素个数判断是否为最优,若是则更新最优一致集.

(4)更新当前的错误概率,若大于允许的最小概率则重复 (1)到 (3)迭代,知道小于最小概率时结束.

SIFT算法在特征匹配过程中,要对128维的特征描述向量进行计算,匹配时计算量较大.特别是在纹理较多的图像中,提取的特征点个数较多,计算量就更大了.而生活中的场景一般有较多纹理结构,所以利用基于结构信息拼接算法(Structural Keypoint Matching,SKM),采用基于RTV的图像主结构提取算法来像的结构,并在提取的结构图像中进行SIFT特征点的提取与匹配特征点的提取与匹配,这样可以避免图像中细致纹理噪声在图像特征提取过程的影响.

SIFT算法在求特征点时,若提取了较多的特征点,就会占据较多内存空间来储这些特征点描述向量,尤其是在高分辨率的图像中,并且随着提取特征点数量的增加会极大地增加特征点匹配时的计算量.而SKM算法提取图像的主结构后,去掉了纹理噪声,会使特征点数减少,从而减少计算量.下面以图6、图7两幅纱窗示意图为例,介绍基于信息结构的图像拼接算法.

分别对图6和图7进行主结构提取,去除纹理.

如图8所示,可以发现大部分细节纹理噪声都被消去,并保留了图像的主要结构特征,同时对其进行SIFT特征点的提取.

图6 纱窗左侧图

图7 纱窗右侧图

图8 提取与匹配

最后根据特征点匹配的结果,求出图像变换模型矩阵的参数.通过仿射变换,以及得出的模型参数对图像进行变换和拼接,得到最终图像,如图9所示.

图9 变换拼接图

3 实验分析与讨论

3.1 图像去纹理效果分析

对图像去除纹理可以使图像的颜色变化趋于连续,在物体和图案的顶点处的特征点更容易识别,若进行直接拼接,有些情况下会造成平行的特征点匹配,或者在某一小范围区域出现大量特征点对.这些特征点对后面的拼接过程起到的作用相当,因此即使去除一部分也不会对拼接造成困难.在进行纹理去除后,上述现象有了明显的改善,特征点较原来可减少一半以上.

由2.1的理论分析知,λ为比较特征差异的程度,λ增大时,由该部分构成的方程 (7)在求解时将更偏重于此项,故λ可以简化看作为去纹理强度.

在实际应用过程中,发现只需取较小的处理强度值λ即可将纱窗网格去除.另外,当采用不同的λ值时,该方法对图像的特征点筛选作用也略有不同.

为了达到最好效果,即在保证图像固有元素的完整性和可区分性的基础之上,尽量少地保留特征点,分别对λ值进行了在0.1和0.01的数量级上的改动(这里进行的是逐步缩小区间的做法,需要大量试验,只展示一组图像,如图10-图12所示),最终发现只需λ值在(0,0.03]范围时,能够得到较好效果,当超过0.05时,效果便不再显著,且图像清晰度会大幅下降.

图10 RTV 算法测试图 (λ=0.005,σ=2)

图11 RTV 算法测试图 (λ=0.01,σ=2)

图12 RTV 算法测试图 (λ=0.05,σ=2)

对于另一个参数锐度,在允许范围内更改其值,没有发现拼接过程有很大变化.分析其原因,应为锐度值与图像的细致程度为正相关,不能符合减少特征点的目标.

3.2 对虚影的处理结果分析

相对于RTV算法对纹理的去除及对后续拼接的影响,其对拼接产生的虚影的去除效果并不明显.事实上,由于固有拼接方法在最后的拼接处理时,将两幅图像的对应像素做线性组合,这种连续变化的模糊像素与网格等有明显特征的、与附近需保留的像素在RGB颜色数值上形成突跃的纹理有一定区别,不一定能被RTV算法的提取纹理结构的系统所识别,因此处理效果较不明显,但实验发现加强处理强度后同一色块中的像素会相互影响进而融为一体,故仅仅在相近颜色的像素被RTV处理之后,虚影有一定减弱的程度.

3.3 匹配率对比和SKM的算法评价

实验的结果中主要有下列参考值以评判几种算法的性能:

(1)特征点数

特征点是拼接图像的基础.特征点的数量与计算量、准确度等后续要素都密切相关,保证特征点数在合理范围内,是算法的首要目标.

(2)图像匹配率

图像配准后对配准的图像进行图像拼接,根据特征点的匹配率来评价拼接图像的效果.匹配率越高,说明算法的对特征点的利用程度越强,算法的运行更加高效而浪费的数据资源越少.

下面由两组实验测试SKM算法与经典特征点算法的各个参数之间的对比和实验效果.

第一组测试中,如图13、图14所示,以纹理较多的墙面和地砖为实验,测试SKM算法和经典算法下特征点数及匹配率.如表1所示.

图13 经典算法下的特征点匹配图像

图14 SKM算法下的特征点匹配图像

表1 两种算法对第一组测试图像配准的性能比较

由表1可以看出,SKM算法所确定的特征点仅为经典算法的60%-70%,在运算次数与其平方成正比的匹配过程中,该特质有效减少了特征点匹配时的计算量,由于去噪作用,对拼接产生干扰的特征点被筛去,进而匹配率也有所提升.通过对比可知,SKM算法的特征点配对数要比经典算法少很多,而特征点的匹配效果还是很好的.

通过类似的一些图像配准实验,很容易发现,在纹理较多的图像中,SKM算法的效率比经典算法的效率要高,且保证了配准的确性性.甚至在背景十分复杂的图像中,SKM算法的优势更加明显.

4 实验结果对比与分析

实验采用了纱窗、涂鸦墙、篮球场网图、马路等背景复杂且噪声较多的图像作为研究对象.在导入图像之后,立即对图像做去纹理的处理.由于处理后的输出为两个图像矩阵,需将其再转化为图像格式.经此步后转而进行图像拼接处理.

在图像处理过后,利用SKM算法算出变换矩阵H,由此得到最终输出结果,完成拼接并显示图片.

4.1 图像数据来源

饰演的所有测试图像均由由VivoX21A手机拍摄,由于当图像的尺寸较大 (如1373×7373)时,程序处理时间过长,可能由于速度浮动和而无法比较且未知因素出现几率增加,所以在进行实验前在尽可能保证图像质量的情况下对图像进行了缩放处理,缩小后图像大小为500×500.

4.2 实验环境

硬件环境:运行实验的计算机CPU型号为Intel (R)Core (TM)i5-6300HQ CPU @ 2.30 GHz,内存为8.00 GB(2133 MHz).

软件环境:操作系统为 Microsoft Windows 10专业版 (64位),程序运行平台为MatlabR2016a,部分代码来源于Lowe的siftDemoV4[5].

4.3 实验结果对比和分析

1)在第一组实验中,我们采用了马路街道图 (如图15,图16所示),场景元素较多且分布复杂,还有些元素两张图仅出现一次,给拼接造成了难度.

图15 左侧街道图

在表2中,反映了图17中(上侧图是经典算法的特征点匹配图,下侧是SKM算法的特征点匹配图)经典算法与SKM算法特征点数量以及匹配率.可以看出SKM算法的特征点配对数要比经典算法少很多,而且特征点的匹配率还高.

如图18,图19所示,经典算法拼接时,由于特征点匹配过多,拼接又不能顾及所有特征,故出现较大偏差,如图中信号灯处和斑马线处.去噪后,此两处的拼接均大幅提高,斑马线处基本无断层.可见SKM拼接对图像特征的取舍与对重点拼接位置的聚焦作用.

图16 右侧街道图

表2 街道

图17 经典算法和SKM算法特征点匹配图

图18 经典算法下测试结果图1

2)在第二组测试中,测试了两幅不同角度的涂鸦墙,如图20所示.

图19 SKM算法下测试结果图1

图20 不同角度的涂鸦图

在涂鸦的图片中存在大量的纹理,故作为典型案例测试.表3中将SKM算法与经典算法相比较,在这组实验中,SKM算法减少大量特征点数.将两幅图像进行配准,提高了准确度.

表3 墙

结果表明,直接拼接中的效果图能够大致吻合,但在拼接处有极窄的纵向图像带并没有显示出来.而在去噪拼接中有效的避免了这一现象,并且右下方黑色形状的边界拼接的更加光滑,其上方的纹理也显示的较为完整,如图21,图22所示.

图21 经典算法下测试结果图

3)第三组实验,以篮球场为背景图像进行拼接,如图23所示.两种算法实验结果如图24所示.

图22 SKM算法下测试结果图

图23 篮球场图

图24 篮球场拼接结果图

在最后一组实验中,篮球场围栏的纹理在整个图像范围内都很相似,对提取特征略有影响,从数据上看可以证实这一点.去噪后特征点数明显降低,且拼接边界也有可见的优化效果.如表4所示,虽然SKM从特征点匹配率上表现稍差,但减少对特征点的计算量的效果突出,算法仍具有一定的可取性.

表4 篮球场

5 总结

通过多次图像配准实验,可以发现,SKM算法的效率比经典算法效率要高,且保证了配准的准确性.SIFT特征点提取是一种较成熟的算法,但对于多纹理的图像拼接时,耗时较长.本文提出的SKM算法将基于相关总变差模型的图像主结构提取算法与基于SIFT特征点提取算法相融合.实验表明,SKM算法在纹理较多的图像中进行配准时,继承了经典算法的稳定性,适用于纹理较多的图像,并且在纹理较多的图像配准过程中相比于经典算法而言有着更高效率.而日常拍摄的景物图像中纹理结构不少,尤其是对于纹理结构特别多的图像,SKM算法具有较好的性质.