RANSAC算法求解单应矩阵的具体研究

2017-02-06 22:53王博杨
价值工程 2017年2期
关键词:迭代

王博杨

摘要: 本文主要研究RANSAC算法在单应矩阵求解中的应用。具体方法是在单应矩阵的求解过程中,利用RANSAC算法原理,通过不断地取点、阈值判断等迭代过程,逐步更新内点集,优化单应矩阵的计算结果,得到更精确解。

Abstract: In this paper, we mainly study the application of RANSAC algorithm in solving single homogeneous matrix. By using the RANSAC algorithm, the interior point set is updated step by step through the iterative process of taking points and thresholds, and the result is optimized to obtain more accurate solutions.

关键词: RANSAC算法;迭代;单应矩阵

Key words: RANSAC algorithm;iteration;homography matrix

中图分类号:TP317.4 文献标识码:A 文章编号:1006-4311(2017)02-0216-02

0 引言

图像拼接技术能够将多目视频图像拼接成同一平面下的合成图像,通过该方法的应用可以将无畸变全景监控变为现实,在军事、交通、科研等领域具有深远意义。图像拼接技术的关键一步就是多目视频图像间的单应矩阵的求解。虽然通过4对不共线坐标就可以求出单应矩阵,但是因为噪声的存在,在实际取点过程中,一定会存在误差,导致单应矩阵计算不够准确,会给后续的图像拼接造成严重影响。

RANSAC算法(Random Sample Consensus)是一种获得非确定样本数据的方法,于1981年由Fischler和Bolles最先提出。对于RANSAC算法有一个基本的假设:样本中包含正确数据(inliers,符合模型的数据)和异常数据(Outliers,不符合模型的数据),通过不断地更新内点集,找出最优的样本模型。

1 基于RANSAC算法的单应矩阵求解流程

为求得单应矩阵的精确值,我们可以通过以下步骤进行:

第一步,先从数据集S中随机选择4对样本。

第二步,根据上述单应矩阵的求解方法,我们可以求得单应矩阵H的初始解,并记为模型M。

第三步,通过模型M计算i点的投影误差,并通过阈值比较,若d?t,则将i点加入内点集I。

第四步,若通过模型M确定的内点集所包含点的数量大于最优内点集,则更新最优内点集,同时迭代次数,否则从最优内点集中选择4对样本重复第二步。

第五步,若迭代次数大于k则结束,最后求得的单应矩阵H是最优解,否则重复第二步。

算法的具体流程如图1。

2 计算参数的确定

2.1 迭代次数k

根据公式k=确定迭代次数,其中w=内点数/数据总数,p为置信度,我们取值为0.99。

2.2 阈值t

阈值的计算可以通过公式t2=F(α)σ2求得,显而易见当d?t2时点(x,y)为内点,当d>t2时点(x,y)为外点。A是特征点为内点的先验概率,为了提高精度,我们取值为0.9。因为是2个自由度,所以n取值为2,通过查表,我们可得F(0.9)=4.605,σ可以通过样本特征点的提取,采用样本标准差公式σ=求出,则阈值t就可以通过计算获得。

3 算法的优化

RANSAC算法因为需要进行的大量的迭代计算和数据处理,因此在某些复杂场景拼接过程中,效率会比较低下。现在学术界一些优化算法,如2004年由中国科学院的赵向阳、杜利民等人提出的一种全自动稳健的图像融合拼接算法,该方法通过RANSAC算法迭代计算出最大内点集合后,利用LM(Levenberg-Marquardt)算法对单应矩阵进行优化估计,但是在实际运算过程中并没有提高多少精度,反而计算效率进一步降低;2012年宁德师范学院计算机系的张世良对算法进行优化,在采集数据样本的时候通过用K-means聚类算法把N对角点进行分组,每次4对数据求单应矩阵1对数据进行检验,不符合要求的数据组直接剔除,运用这种方式减少迭代次数,实际上剔除数据组的计算量并没有实质性的减少,所以整体算法的效率没有提高。但是上述两种方法为我们提高的优化思路有两点:

一是若是图像采集质量较低伪匹配点较多的情况下,在选取子集S时可以根据样本特性等采用特定的选取方案,使用有约束的随机选取来代替原来的完全随机选取。

摄像机在同一平面水平排开,摄像机在水平和垂直方向没有旋转,那么匹配点间一定有x=xi+λdi+Δxi及y=y+Δyi的约束关系,其中λ为比例系数。通过约束关系很容易把伪匹配点排除掉,极大地减少出错概率和迭代次数。

二是若是图像采集质量较高伪匹配点较少的情况下在合理的基础上简化运算步骤,上述运算过程中,我们采集每对点坐标都进行了阈值检测,完全可以采用多点同时检测的方法:

图像质量越高,m取值越大,同时检测的点就越多,算法效率越高。通过实验,使用上述RANSAC算法,可以快速排除噪声干扰,准确地求出单应矩阵。

4 结束语

如图1所示,左侧图像显示的是没有使用RANSAC算法的图像特征点匹配,可以看出出现个别错误匹配,这将可能导致后续图像拼接出现严重错误。右侧图像是采用了RANSAC算法优化的特征点匹配,完全排除了错误干扰,符合运用需求。

参考文献:

[1]陈艺虾.改进的ransac算法在图像配准中的应用[J].计算机科学与探索,2010.

[2]黄梅.基于改进ransac算法的图像拼接技术[J].海南大学学报,2011.

[3]WeiJei Huang, An Improved RANSAC Algorithm of Color Image Stitching, 2013.

[4]Xiaowei Li, Computing Homography with RANSAC Algorithm:A Novel Method of Registration, 2004.

[5]曲天伟.改进的ransac算法在图像配准中的应用[J].计算机应用,2010.

[6]AditiMajumder, Rick Stevens. Perceptual Photometric Seamlessness inProjection-Based Tiled Displays, ACM Transactions on Graphics, Vol. 24, No.1 January 2005.

[7]贾莹.基于Harris角点检测算法的图像拼接技术研究[D].吉林大学,2010.

[8]曾琦.Image registration method based on improved Harris corner detector, 2010.

[9]Mark Hereld, Ivan R. Judson, and Rick Stevens. A Measurement Engine for Aligning Multi-Projector Display Systems, Argonne National Laboratory preprint ANL/MCSP958-0502, 2002.

[10]A Way Based On Within-class Scatter Matrix to Improve RANSAC Algorithm, 2012.

[11]Liang Sun.An Improved Harris Corner Detection Algorithm For Low Contrast Image, 2014.

[12]黄梅.面向全景拼接的ransac算法改进[D].海南大学,2011.

[13]陈利军.图像角点检测和匹配算法的研究[J].通信与信息系统,2005.

猜你喜欢
迭代
聚焦递推关系求数列通项
中间件“迭代”
一种用于室内定位的线性规划算法
DNS解析的探究
涨价与医保政策需同步“迭代”