基于DPP改进RANSAC算法的图像拼接①

汪 旌,张 赟,陈 爽

1(杭州电子科技大学 计算机学院 图形图像研究所,杭州 310018)

2(浙江传媒学院 浙江广播电视技术研究所,杭州 310018)

3(沈阳工业大学 信息科学与工程学院,沈阳 110023)

图像拼接技术是现今热门的图像处理技术,图像拼接是将取自同一场景,有相互重叠信息的一组图像序列通过图像配准和图像融合的方法,拼接成为一幅无缝隙,宽视角,高清晰度图像的处理技术[1].图像拼接方法有以下 3 种: 1) 基于特征的图像拼接; 2) 基于交换域的图像拼接; 3) 基于灰度的图像拼接.其中基于特征的图像拼接是现今最常用的拼接方法.在基于特征的图像拼接中,由于受特征点检测方法精度,光照变化等因素影响,匹配特征存在错误信息,错误信息的存在会较大程度的影响模型参数估计的精度.针对模型参数估计的方法有: 线性法,迭代法和鲁棒法.线性模型参数估计方法[2]速度快,但易受误差匹配的影响.迭代模型参数估计方法精度高,但耗时久计算量大.而鲁棒模型参数估计方法[3,4]是通过错误信息排除策略,利用正确信息进行模型参数估计的方法.鲁棒参数估计算法中最广泛应用的是随机抽样一致性(Random Sample Consensus,RANSAC)算法.该方法算法鲁棒性强,结构简单,较好实现,已成为众多学者的研究对象.随机抽样一致性算法利用迭代方法从一组包含内点和外点的样本集中估算出参数模型,从而得到优质的匹配点集,然而它是一种不确定的算法,精度不高,得到一个合理结果存在一定概率,因此相关改进的RANSAC算法应运而生.MSAC方法[5]引入边界损失函数评估内外点的分布,获取了具有最大可能的一致集.PSOSAC方法[6]利用测试样本的匹配评价作为采样依据.Optimal RANSAC 方法[7]通过增加局部采样方式来提高模型估计精度与收敛速度.

本文提出一种基于行列式点过程的RANSAC算法,该算法利用行列式点过程(Determinantal Point Processes,DPP)采样法从测试点集中选取一个子集进行参数估计,选取的子集具有全局性和分散性,利用抽取到的分散性好的特征点求取参数模型.接着,运用所有特征点集对该模型进行检验.根据特征点集中数据对模型的支持度,观测内点数目来确定该模型估计的正确性.通过不断建立假设与检验的迭代,以期获取一个具有全局最优的模型.

1 图像特征提取与匹配

本文对于特征点提取采用鲁棒性较好的基于尺度空间理论的SIFT特征提取法[8].SIFT特征提取法首先建立图像高斯差分多尺度空间(Difference-of-Gaussian,DoG); 在DoG尺度空间求取局部极值点,剔除低对比度点和边缘响应点后对局部极值点进行精确定位,同时生成特征描述子,通过特征描述子建立两幅图像之间的关系.

目前,SIFT特征提取法已有相关改进,如文献[9]提出高斯二阶差分(D2oG)特征检测算子的SIFT算法.本文基于实际应用中算法复杂度考虑,采用基于尺度空间理论的SIFT算法.

1.1 构建图像的高斯尺度空间

一幅二维图像的高斯尺度空间可以定义为:

其中,

是尺度可变高斯函数,(x,y)是各像素点坐标,σ是用于表示图像平滑度的尺度空间参数,σ越大对应图像的概貌特征越明显,σ越小对应图像的细节特征越清晰.

1.2 SIFT特征提取法

(1) 空间极值检测

建立图像DoG金字塔后,在DoG尺度空间中的26个领域中检测极值点,如果一个点在DoG尺度空间本层以及上下两层的26个领域中是极值点(最大值或最小值),即认为该点是图像在该尺度下的一个特征点.如图1所示.

图1 Difference-of-Gaussian 金字塔示意图

(2) 确定DoG算子的方向不变性

每个特征点的方向参数由特征点领域像素点的梯度方向分布特性决定.

像素点的梯度:

公式(3)、(4)分别给出了处像素点的梯度幅值和方向角.

实际计算中,在以特征点为中心的邻域窗口内采样,用直方图统计邻域像素的梯度方向.梯度直方图的范围是0～360度,每10度代表一个方向,总共36个方向,直方图的峰值处即为特征点的主方向.

(3) 生成SIFT特征向量

将特征点描述为一组特征向量,特征向量是对特征点及其邻域内的像素点特征的精确描述.一个特征点由4×4=16个种子点构成,特征点的特征向量由所有子块梯度直方图构成,图2左图的方型线框大小为16×16.每个小格代表一个像素点,像素点的梯度即小格内的带箭头直线表示,梯度的幅值大小即直线的长度,梯度方向即箭头方向.16×16的方型线框共产生4个种子点.图2给出特征向量生成的过程:

图2 特征向量生成过程

(4) 特征点的匹配

获取到特征点描述子后,进行特征点的匹配.特征点的匹配就是特征向量的匹配,本文采用的方法是比较特征向量的欧氏距离,当此距离小于某个阈值时则认为这两个点已匹配上.文献[10]证明: 当图像的噪声接近高斯噪声时，L2欧式距离能够更好的区分特征点对的真匹配与伪匹配。其次，L2欧式距离在特征点匹配的具体实现中具有极佳的便利性，在具体应用中利用一些数学工具箱则可非常快速的计算出特征向量间的L2欧式距离.

特征点匹配完成后,利用RANSAC算法筛选出匹配度低或误匹配的点,最后选择合适的特征点计算出最佳投影变换矩阵,实现图像配准.但是当特征点对数量庞大、错误率高、估算模型复杂时,计算量会加大,传统的RANSAC算法效率会大幅度下降.本文提出一种基于行列式点过程的改进RANSAC算法,能适应匹配点数目庞大,错误率高的情况.

2 RANSAC 算法

传统的RANSAC算法的主要过程为: 首先在特征点集中随机的选取几个点作为基准点,利用基准点计算出一个模型,用点集中剩余点来估算此模型,同时记录内外点.如果误差距离在设定范围内,那么此点即称为该模型的内点; 否则为外点.当统计的内点数达到预设的阈值时,认为该模型合理,否则继续随机选择特征点生成新的模型重复上述过程,最后将内点数量最多的模型作为最优模型[11]具体的算法流程如下:

(1) 首先在样本点集S中随机选取一定数量为N的点计算出数学模型A,用剩余的S–N个点测试模型A,将满足模型A的点存入内点集M中.

(2) 判断内点集M的数量,若大于或等于设定阈值C,则表述模型A合理,否则重新从(1)开始.

(3) 在设定的迭代次数D范围内,不断重复(1)(2).最终统计到内点数最多的点集M',获取参数模型A',此模型即为最终的所选模型.

3 基于行列式点过程的改进RANSAC算法

传统的随机一致性RANSAC算法虽然可以很大程度上利用相对正确的配对点来生成变换矩阵,但是依然存在不足:

(1) 传统的RANSAC算法采用随机取点的方式进行初始模型计算,但是随机取点会导致取样点集中于某一区域,这个区域可能正确匹配率很低或存在过多误匹配点,如此求取的投影变换矩阵精确性会有所下降,根据RANSAC算法的流程,在所有点都验证结束后才可能区分出误匹配点,这样会大大降低算法的效率.

(2) 在随机选择特征点时,如果选取到的点位置很接近,则会被当成同一个点,这样计算出来的投影变换矩阵精度也会降低.

基于以上传统的RANSAC算法的缺陷与不足,本文提出了一种基于DPP的改进RANSAC算法.

3.1 基于DPP的改进RANSAC算法

在RANSAC算法执行过程中,对测试样本的采样是其算法框架下的重要环节之一,而DPP具有良好的全局性和负相关性,在抽样过程中会呈现出覆盖面广且“分布均匀”的完美性质[12],这对于传统的RANSAC随机采样过程中采样不均的缺陷有非常正面的作用.

DPP最早在量子力学和随机矩阵中提出,DPP是一种概率模型,它通过核矩阵的行列式来给出每一个子集的概率[13]基于它的特性,DPP为采样,计算边缘概率等其它推理任务提供了有效的解决办法.在本文中主要利用其采样特性对RANSAC算法进行改进.

一个离散集上的点过程P是在Y的所有子集上的概率分布,此过程的基础上,当且仅当过程P由一个半正定矩阵K所确定,且矩阵k由Y中的元素索引时,将这个点过程称为行列式点过程.即当Y为一个依据点过程P所获得的子集时,对任意的有:

其中为保证公式的有效性,指定且当时,

从上式可以得到,矩阵K的对角元素表示单个元素被选择到子集中的概率,非对角元素决定了元素对间共同出现的负相关性,矩阵K中包含了所有的元素间的信息.据此将K称为核矩阵,并将这个全局负相关称为多样性.所以得到以下结论:Kij的值越大代表i和j同时发生的概率越小.标准DPP采样法的算法描述如算法1.

End while

算法中,第j次抽取元素i的概率为:

由此,抽取序列的概率为:

由于所有的实对称矩阵均可表示为葛朗姆矩阵,即实对称矩阵K可写成K=BTB.其中Bi表示集合Y中的元素.由算法1可见可以从K中得到一个子集Y作为标准DPP的抽样结果.

由式(7)和(8)可知,标准的DPP采样是完全根据概率进行操作,因此最终的取样点不固定.如果采样得到的点超过实际应用所需点数,那么会造成计算资源的浪费,因为采样点已经足够分散在采样空间中,更多的采样点对于提升计算精度的帮助微乎其微.若采样得到的点数少于实际应用所需点数,则达不到计算仿射或者透视变换的参数个数.因此采用可控的采样方法对于图像拼接来说意义重大.对于RANSAC算法,希望可以人为的选择每次采样点的数目,保证计算精度的同时,不造成计算资源的浪费.所以本文采用k-DPP采样[14].k-DPP是一种仅对基数k进行建模的条件DPP.在实际应用中基数k为采样集合中采样点的个数,k-DPP采样法避免了标准DPP采样法中采样点不固定造成的计算精度不准确以及资源浪费的弊端,实现均匀分散采样的前提下控制采样点的个数.通过简单调节标准DPP采样方法即可实现k-DPP采样.k-DPP采样算法如算法2.

算法 2.k-DPP 采样法[14]Input : 输入K的特征值和特征向量对{()}Output: YFordo If thenif k=0 then break end if end if end for继续算法1中采样算法的第二个循环

算法2中e为关于特征向量的基本对称多项式(elementary symmetric polynomials),e的计算公式如下:

相比较于标准DPP采样法,显然k-DPP采样法有着更强的可控性,因此更加符合图像应用上的要求.

3.2 基于DPP的改进RANSAC算法流程

(1) 利用SIFT特征提取算法分别提取有重合场景的两幅图像P1,P2的特征点集,记为

(2) 利用相似性度量函数构造DPP采样所需核矩阵K.相似性度量函数计算公式如式(10),d是S(Am,An)的预设方差,本文设定d=5.

由S的定义可知,对任意的Am和An,必有 0 ≤S(Am,An)≤ 1,因此矩阵K满足边缘概率分布,K是核矩阵.

(3) 对模拟概率分布后的得到矩阵K进行特征分解,特征值和特征向量按照从大到小的索引顺序排列按照算法2的描述循环判断,更新集合J中的满足条件的特征向量.本文的实现过程中k=8.

(4) 重复算法1中的while循环,按照概率中抽取8个特征点.

(5) 图像P2重复上述操作,即可从匹配后的特征点对中选取8对分散性好的点对.

计算出临时投影矩阵Hi,计算剩余样本点通过Hi变换后的欧氏距离L2记为di,若di≤thresh0,则将此样本点加入点集Si中,di加入Di中.在完成一定抽样次数后,选择点集Si中点数最多的点集为内点集Si,并记录此时的投影矩阵对应的距离集合而此时获取的投影矩阵即通过改进的RANSAC算法得到的最佳参数估计模型.值得注意的是,对于不同的问题可以选取不同数目的点对,在图像拼接的算法中选取8对特征点对是对投影变换的最小自由度和计算鲁棒性进行了折中.

4 实验结果

4.1 图像拼接

为了检验本文提出的基于DPP的RANSAC算法在剔除误匹配点方面的有效性,本文进行了图像拼接实验.分别用传统的RANSAC算法和改进后的RANSAC算法对两组场景信息不同的图像进行了处理.测试环境配置如下: Microsoft Windows 10,CPU 为 2.40 GHz,内存为 8 GB,硬盘为 500 GB SATA,编译工具为matlab R2014a.

如图3和图4所示,本文选取了两组测试图像,均采用SIFT特征提取算法提取了特征点,通过计算图像特征点之间的欧式距离L2距离进行初始匹配,然后分别利用传统的RANSAC算法和改进后的RANSAC算法进行消除误匹配点对的对比试验.并分别统计两种算法的正确匹配率,迭代次数以及完成拼接所用时间.

图3 第一组实验对比图

第一组测试图像大小同为788×788,对同一场景的拍摄角度不同.

第二组测试图像大小为1278×852和736×852.两幅图像大小不同,清晰度也不同.

上述实验对比可观测出传统的RANSAC算法虽然也能剔除掉一部分误匹配点,但是依旧存在误差匹配,而改进后的RANSAC算法基本无误差匹配.表1给出迭代次数,正确匹配率,以及时间效果上的两种RANSAC算法效率对比(实验将原RANSAC算法的迭代次数控制在300次以内).

图4 第二组实验对比图

由表1可知,虽然改进后的RANSAC最终得到的匹配点数目少于传统的RANSAC算法,但是剔除了更多的误匹配点,因此正确率明显提高.同时改进后的算法迭代次数和拼接耗时大大减少.这是因为传统的RANSAC算法在随机取点的过程中不能保证取样点的分散性,当随机取样点集中于正确匹配率低的区域时会大大增加了算法的迭代次数和拼接时间,而改进的RANSAC算法保持了取样的分散特性,降低了迭代次数和拼接时间.

表1 实验结果对照表

4.2 兴趣区域图像配准(ROI Image Registration)

ROI图像配准在现代制造业中应用广泛,如产品的局部近似立面检测.如图5(a)是拍摄到的一个计算机的前面板,图5(b)是拍摄到的一部随机摆放的计算机.实验通过匹配兴趣区域,将图5(b)中的计算机前面板矫正到图5(a)所示的正面角度,由于计算机的前面板不是完全的明面,而是有许多小凹凸,比如支架或者接口的凹凸,因此在拍摄视角改变后兴趣区域的图像配准不完全符合投影变换.在此情况下进行匹配点筛选,若采取到的匹配点位置集中,则进行透视模型估计时得到的模型参数估计精度不高,当采用分散性好的匹配点进行透视模型参数估计能得到更为鲁棒的结果.

图5 兴趣区域图像配准实例图

实验通过SIFT特征提取法提取图5(a)和图5(b)匹配特征点对,分别利用传统的RANSAC算法和改进的RANSAC算法剔除误差匹配点后求取最优变换矩阵.利用剔除误差匹配点后计算得到的变换矩阵将图5(b)中的计算机面板角度转换成图5(a)中ROI图像所示的正面角度.图5(c)是使用传统RANSAC算法对图5(b)进行兴趣区域配准得到的结果,图5(d)则是使用基于DPP的改进RANSAC算法对图5(b)进行兴趣区域变换的结果.可以观察到的是,利用传统RANSAC算法进行兴趣区域配准得到的结果发生了畸变,而利用基于DPP改进的RANSAC算法则得到了非常鲁棒的结果.

5 结束语

本文将DPP采样法与RANSAC算法相结合,提出了一种更加高效,精确度更高的改进RANSAC算法.其特点如下:

k-DPP采样法在传统DPP采样法加以改进,在均匀分散化采样的前提下保证采样点数目可控,这一特性对传统RANSAC算法中随机取点导致取点区域集中的问题有很好的正面作用[15].

改进的RANSAC算法在图像拼接中也保持了极佳的效率.当原始点集数据很大,匹配错误率高的时,改进的RANSAC算法能快速精准的找到最佳变换矩阵,高效的完成图像拼接.

RANSAC算法不仅可以应用于图像拼接领域,同时也可应用到人脸识别[16]、图匹配[17]、立体图像配准[18]、医学图像拼接[19]等领域.今后作者考虑进一步将改进的RANSAC算法应用到更多领域,如虚拟现实,全景合成处理等.

参考文献

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

2Armangué X,Salvi J.Overall view regarding fundamental matrix estimation.Image and Vision Computing,2003,21(2): 205–220.[doi: 10.1016/S0262-8856(02)00154-3]

3魏若岩,阮晓钢.基于Skinner操作条件反射的抽样一致性算法.控制与决策,2015,30(2): 235–240.

4唐永鹤,胡旭峰,卢焕章.应用序贯相似检测的基本矩阵快速鲁棒估计.光学 精密工程,2011,19(11): 2759–2766.

5Torr PHS,Zisserman A.MLESAC: A new robust estimator with application to estimating image geometry.Computer Vision and Image Understanding,2000,78(1): 138 –156.[doi: 10.1006/cviu.1999.0832]

6Chum O,Matas J.Matching with PROSAC-progressive sample consensus.Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Diego,CA,USA.2005.220–226.

7Hast A,Nysjö J,Marchetti A.Optimal ransac —towards a repeatable algorithm for finding the optimal set.Journal of WSCG,2015,21(1): 21–30.

8Lowe DG.Distinctive image features from scale-invariant keypoints.International Journal of Computer Vision,2004,60(2): 91–110.[doi: 10.1023/B:VISI.0000029664.99615.94]

9徐敏,莫东鸣,张祯.高斯二阶差分特征算子在图像拼接中的应用.计算机系统应用,2016,25(4): 167–173.

10Brown M,Szeliski R,Winder S.Multi-image matching using multi-scale oriented patches.Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Diego,CA,USA.2005.510–517.

11Fischler MA,Bolles RC.Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography.Communications of the ACM,1981,24(6): 381–395.[doi: 10.1145/358669.358692]

12Kulesza A,Taskar B.Determinantal point processes for machine learning.Foundations and Trends in Machine Learning,2012,5(2-3): 123–286.[doi: 10.1561/2200000044]

13Johansson K.Determinantal processes with number variance saturation.Communications in Mathematical Physics,2004,252(1-3): 111–148.[doi: 10.1007/s00220-004-1186-4]

14Kulesza A,Taskar B.k-DPPs: Fixed-size determinantal point processes.Proceedings of the 28th International Conference on Machine Learning.Bellevue,WA,USA.2011.1193–1200.

15Decreusefond L,Flint I,Privault N,et al.Determinantal point processes.Peccati G,Reitzner M.Stochastic Analysis for Poisson Point Processes.Cham: Springer,2016.311–342.

16Shao H,Chen S,Zhao JY,et al.Face recognition based on subset selection via metric learning on manifold.Frontiers of Information Technology & Electronic Engineering,2015,16(12): 1046–1058.

17Yu TS,Wang RS.Graph matching with low-rank regularization.Proceedings of 2016 IEEE Winter Conference on Applications of Computer Vision (WACV).Lake Placid,NY,USA.2016.1–9.

18Tong RF,Zhang Y,Cheng KL.StereoPasting: Interactive composition in stereoscopic images.IEEE Transactions on Visualization and Computer Graphics,2013,19(8):1375–1385.[doi: 10.1109/TVCG.2012.319]

19Adwan S,Alsaleh I,Majed R.A new approach for image stitching technique using Dynamic Time Warping (DTW)algorithm towards scoliosis X-ray diagnosis.Measurement,2016,(84): 32–46.