一种改进RANSAC算法的单应性矩阵估计方法

来源:用户上传      作者:

　　摘 要：在图像拼接技术中，单应性矩阵是实现两幅图像正确拼接的关键因素。针对传统RANSAC算法误匹配点概率较高，需要设置固定的投影误差阈值t导致迭代次数多、运行时间长、估计的单应性矩阵精度低等问题，提出一种改进的RANSAC算法以降低误匹配率。利用特征点周围灰度梯度相似性，剔除初始匹配中部分误匹配点，以减少矩阵估计的迭代次数;通过快速舍弃错误的单应性矩阵以减少内点检测时间，提高算法运行效率;通过BGD算法最小化损失函数以拟合精确的单应性矩阵。对比实验结果表明，改进的RANSAC算法能够有效剔除误匹配点，减少内点检测时间，提高单应性矩阵H的精度。
　　关键词：图像匹配;RANSAC算法;单应矩阵;BGD算法;误匹配点
　　DOI：10. 11907/rjdk. 191439 开放科学（资源服务）标识码（OSID）：
　　中图分类号：TP317.4 文献标识码：A 文章编号：1672-7800（2020）002-0149-04
　　英标：A Homography Matrix Estimation Method Based on Improved RANSAC Algorithm
　　英作：LI Jia-Hui1，ZHANG Feng-shou1，CUI Hao-Yang 2
　　英单：（1.College of Mechanical and Electrical Engineering， Henan University of Science and Technology， Luoyang 471003， China;2.College of Mechanical and Electrical Engineering and Automation， Shanghai University， Shanghai 201900，China）
　　Abstract： In image stitching technology， the homography matrix is the key factor to achieve the correct stitching of two images. The traditional RANSAC algorithm has a high probability of mismatching points and needs to set a fixed projection error threshold t and it will lead to many iterations， long running time， and low accuracy of the estimated homography matrix. An improved RANSAC algorithm is proposed to reduce the mismatch rate. The similarity of gray gradient around feature points is used to eliminate some mismatched points in initial matching， so as to reduce the iteration times of matrix estimation. By quickly discarding the wrong homography matrix， the detection time of the inner point is reduced， and the operating efficiency of the algorithm is improved. The loss function is minimized by the BGD algorithm to fit the exact homography matrix. According to the results of the comparative experiment， the improved RANSAC algorithm can effectively eliminate the mismatch points， reduce the inside point detection time， and improve the accuracy of the homography matrix H.
　　Key Words： image matching; RANSAC algorithm; homography matrix; BGD algorithm; mismatch point
　　0 引言
　　图像拼接技术是指将一组具有相互重叠部分的图像进行空间匹配对准，经重采样融合成一幅包含各图像序列信息的宽视角场景、可理解性更好的新图像[1-2]。图像配准是指根据两幅图像重叠区的一致性求解图像之间的投影变换，即平面单应性矩阵，广泛应用于三维重建、目标跟踪和机器人视觉等领域[3-4]。目前图像配准方法研究最多、应用最為广泛的是基于特征点的图像配准方法。在特征点匹配过程中，不可避免地会产生误匹配[3-6]，目前有很多消除误匹配的方法，如霍夫聚类法、最小中位法以及随机抽样一致性算法（Random Sample Consensus，RANSAC）等等。其中，RANSAC由Fischler & Bolles在1981年提出，广泛应用于图像拼接领域。文献[7]中，在提取图像的 SIFT 特征点后，根据阈值法对特征点进行初始匹配，然后采用改进的RANSAC 算法对初始匹配对筛选，再计算图像间单应性矩阵，最后使用加权平均的融合方法实现图像的无缝拼接，可靠性较高但效率较低;文献[8]提出了一种改进的全景图自动拼接算法，利用 RANSAC 算法去除误匹配，但是估计的单应性矩阵精度低，拼接效果一般;文献[9]中，在改进的RANSAC算法中改用8对特征点匹配点对，确保对应8个特征点皆为内点，从而大大降低迭代次数，提高运算效率;文献[10]重复采用两次 RANSAC 算法引导匹配，降低了单应性矩阵估计效率;文献[11]首先进行初步筛选，然后利用相似三角形求出基准单应性矩阵，设定阈值，剔除不满足阈值的匹配点对，最后得到精确匹配点。一般当匹配对超过一半外点时，RANSAC算法就能估计出正确的单应性矩阵。但是在内点概率[ω]非常小的情况下，迭代次数将非常高，导致运算效率降低。 　　目前基于RANSAC算法的单应性矩阵估计均存在精度低、算法运行时间长等问题。因此，本文提出一种改进RANSAC算法的单应性矩阵估计方法，能够有效剔除误匹配点，减少运行时间，显著提高单应性矩阵精度。
　　1 RANSAC算法基本原理
　　RANSAC算法基本假设是样本中包含正确数据也包含异常数据，即数据集中含有噪声。这些异常数据可能由于错误的测量、错误的假设、错误的计算等产生。同时RANSAC也假设给定一组正确数据，存在可以计算出符合这些数据模型参数的方法[12-13]。它是一种有效的参数估计算法，通过不断迭代，从包含内点和外点的观测数据集中随机选取一定数量的样本对单应性矩阵进行估计，最终找出内点个数最多、误差最小的单应性矩阵。RANSAC算法的最小迭代次数如下：
　　其中，[ε]是内点在观测数据集中的比例，n是得到模型参数所需要的最少样本数，p代表置信度，一般取0.95[～]0.99。计算两幅图像的单应性矩阵所需的最少样本数n=4，置信度取p=0.97。因为内点数在数据集中的比例通常未知，所以通常选择最坏条件下的内点比例，之后通过不断更新此内点比例进行迭代。
　　SIFT算法是一种数字图像特征描述常见的算法，这种描述具有尺度不变性，可在图像中检测出关键点，提取位置、尺度、旋转不变量。通过传统SIFT算法提取两幅图像的特征点后，采用欧式距离作为特征点进行相似性度量[14]。虽然采用两个特征点之间的欧氏距离进行特征匹配的方法简单快捷，但难免会存在一些在尺度空间上特征比较相似的误匹配点。因此，需要采用RANSAC算法去估计两幅图像之间的单应性矩阵，然后再利用单应性矩阵剔除误匹配点[15]。
　　RANSAC算法步骤如下：①从初始匹配对集合S中随机选取4对匹配特征点作为内点集合Si，估计初始的单应性矩阵Hi;②用Hi计算S中剩余的匹配点对。如果某个特征点的投影误差小于阈值t，则将其添加到Si中;③记下Si集合中匹配点对的数量;④重复以上步骤，直到迭代次数大于k;⑤比较哪次计算中内点数量最多，内点数量最多的那次估计模型就是所要求解的单应性矩阵。
　　2 改进RANSAC算法的单应性矩阵估计方法
　　传统的RANSAC算法主要存在两个局限性[16]：①效率。传统方法效率与子集大小、内点比例以及数据集大小有关。当数据集中存在较多的误匹配点时，需要增加迭代次数，同时大量错误的单应性矩阵内点检测会降低运算效率;②精度。传统方法在计算单应性矩阵参数时，为了考虑效率，通常选取最小子集去估计模型参数，所以得到的模型参数并非最佳参数。
　　本文从3个方面对RANSAC算法加以改进：
　　（1）利用特征点周围灰度值的相似性进一步剔除误匹配点。在两幅待拼接图像中，两对正确的特征点匹配对周围灰度值的变化应该具有很高的相似性，根据这一特性将初始匹配点按照灰度梯度变化的相似性从大到小依次排序，并将前80%的特征点匹配对作为求参点集，进一步剔除误匹配点，从而减少单应性矩阵估计的迭代次数。本文采用8邻域的拉普拉斯算子计算特征点周围灰度值的梯度变化，具体公式如下：
　　其中step为步长，在本文中step=1。
　　（2）快速舍弃错误的单应性矩阵以减少内点检测时间。在每次随机选取4个匹配点去估计初始单应性矩阵后，即使单应性矩阵不合理，也需要测试剩余的所有匹配点对，这大大增加了计算量。所以，本文利用初始单应性矩阵在剩余匹配点对中随机选取4对匹配点，如果这4对匹配点均适合该单应性矩阵，则加入到内点集中继续进行匹配操作，如果其中有任意一个匹配点对不符合该单应性矩阵，则马上舍弃该单应性矩阵，重新选取新的匹配点对去估计新的单应性矩阵。本方法可以快速舍弃不合理的单应性矩阵，从而大大减少单应性矩阵测试所有剩余匹配点对的时间。
　　（3） 在应用机器学习算法时通常都会使用梯度下降法去训练模型参数，因此本文将采用批量梯度下降法（Batch Gradient Descent，BGD）进一步精确拟合单应性矩阵参数，投影变换矩阵如下：
　　由式（3），把一个图像中的[x，y，1]作为训练单应性矩阵H的输入数据，把另一个图像中的[x，y，1]作为[x，y，1]对应的标签数据，因此特征点匹配对作为训练单应性矩阵H的训练数据集。将之前由RANSAC算法获得的单应性矩阵H的值作为训练时的初始值，因此能够在极短的时间内使得损失函数收敛，获得精确的单应性矩阵。
　　BGD算法的具体思路是，在更新每一参数时都使用所有样本进行更新。假设单应性矩阵H中的每个参数为[θj]，则线性回归的假设函数为：
　　其对应的损失函数为：
　　其中，n=9，m是由RANSAC算法得到的最多内点个数。
　　对损失函数求偏导可得：
　　最小化损失函数需按照每个参数[θ]的梯度负方向更新每个[θ]值：
　　其中[α]为学习率，它控制[θ]每次向[Jθ]变小的方向迭代时的变化幅度。[α]属于超参数，多次实验结果表明，[α]取0.01时能够使损失函数快速收敛并不发生局部振荡现象。
　　通过上述公式可知该算法能得到一个全局最优解，损失函数接近最小值时单应性矩阵精度也最高。
　　3 实验与分析
　　通过金相显微镜采集一组一元硬币中“YI”字符局部的显微图像，如图1所示。表1为显微镜采集环境，采用传统RANSAC算法和改进RANSAC算法作对比实验，验证改进RANSAC算法的正确性。
　　首先使用SIFT-PCA算法提取图1（b，c）中的特征点，图 1（b）的特征點个数为3 685个，图1（c）的特征点个数为2 087个;然后采用近似最近邻搜索算法按照R=0.6进行初始匹配。初始匹配的特征点个数为220个，如图2 所示，从图2可以看出初始匹配后的图像中存在大量误匹配点。 　　<F：＼软件导刊＼上传＼软件导刊2020-02＼Image＼李嘉惠-2.tif>
　　图2 初始匹配后的特征点匹配对
　　在初始匹配基础上，分别采用传统RANSAC算法和改进后RANSAC算法估计单应性矩阵，并利用单应性矩阵剔除图像中存在的误匹配点对，式（8）、式（9）分别是传统RANSAC算法的匹配结果和改进RANSAC算法的匹配结果。从式（8）可以看出，传统的RANSAC算法仍出现了少量误匹配，需要进一步剔除，而采用改进后的RANSAC算法能够进一步剔除误匹配和一些特征点匹配度较弱的匹配点。利用改进RANSAC算法估计出的单应性矩阵进行透视投影变换，将右图与左图拼接，拼接结果图3 所示。
　　传统RANSAC算法的特征点匹配结果及传统RANSAC算法的单应性矩阵如下：
　　改进RANSAC算法的特征点匹配结果及改进RANSAC算法的单应性矩阵如下：
　　为验证改进RANSAC算法在估计单应性矩阵精度和运行时间上的优越性，本文采用均方根误差（RMSE）作为几何误差，将特征点匹配准确率作为评价指标。
　　其中，S是剔除误匹配后的匹配点个数，H是单应性矩阵，[pi]是待匹配图1中的某一点坐标，[qi]是待匹配图2中的某一点坐标，[Hqi]为[qi]通过单应性矩阵H转换到图1中的对应坐标点，dis代表欧式距离。
　　理论上在单应性矩阵H非常精确的情况下，坐标点[qi]与[Hqi]应该重合，即几何误差RMSE=0。但RMSE一般是一个不为零的数，并且RMSE越小，估计的单应性矩阵H的精度越高。由于RANSAC算法是随机选择内点进行参数模型估计的，因此本文统计5组实验结果。
　　在计算特征点匹配准确率时需要确定一个误差阈值，也就是说[dis（pi，Hqi）]的值小于某个误差阈值时，可以判定这对特征点匹配正确。根据Krystian Mikolajczyk在《An affine invariant interest point detector》一文中对误差阈值的设定可知，特征点检测器实际上检测的是特征区域，例如Harris-Affine检测的是一个椭圆区域，SIFT检测的是一个圆形区域，因此，当两个特征点区域的重叠误差小于1.5个像素时，则可判定这是一对正确匹配的特征点。根据实验结果选取重叠误差阈值为2，实验结果如表2所示。
　　从表2可以看出，改进的RANSAC算法相比于传统的RANSAC算法能够大大提高单应性矩阵精度，降低了内点检测时间，提高了执行效率，从而验证了改进RANSAC算法的正确性和有效性。为验证本文提出的改进RANSAC算法的鲁棒性，将其应用到多视野拼接过程中。图4为“YI”字符的图像序列，共采集相邻的10个视野，拼接结果如图5所示。从图5可以看出，拼接图像无错位现象，且没有发生明显的扭曲变形，从而进一步验证了本文算法的鲁棒性和精确性。
　　4 结语
　　本文针对RANSAC算法存在迭代次数多、运行时间长、估计的单应性矩阵精度低等问题，提出一种基于改进RANSAC算法的单应性矩阵估计方法。利用特征点周围梯度变换的相似性剔除初始匹配中的部分误匹配点，通过快速舍弃错误的单应性矩阵，以减少内点检测时间;通过BGD算法最小化损失函数进一步拟合精确的单应性矩阵。实验结果表明，改进的RANSAC算法能大大提高单应性矩阵精度，减少运行时间，提高算法执行效率。但本文对于需要设置与问题相关的阈值t没有进行深入研究，未来的工作是进一步考虑阈值t对算法运行效率和单应性矩阵精度的影响。
　　参考文献：
　　[1] 陆园园， 张明. 基于SIFT算法的红外图像拼接方法改进[J]. 计算机系统应用，2015，24（8）：165-170.
　　[2] DUAN Y，CHEN W，WANG M，et al. A relative radiometric correction method for airborne image using outdoor calibration and image statistics[J]. IEEE Transactions on Geoscience and Remote Sensing， 2014， 52（8）：5164-5174.
　　[3] 王俊杰，劉家茂，胡运，等. 图像拼接技术[J]. 计算机科学， 2003，30（6）：141-144.
　　[4] 伍梦琦，李中伟，钟凯，等. 基于几何特征和图像特征的点云自适应拼接方法[J]. 光学学报，2015，35（2）：237-244.
　　[5] 蒋波，翟旭平. 基于PCA-SIFT特征匹配的图像拼接算法[J].  计算机应用，2016， 36（s2）：143-145.
　　[6] MA Y，REN Z. Image mosaic method based on improved sift feature detection algorithm[C].  Proceedings of the 9th International Symposium on Linear Drives for Industry Applications，2014：771-779.
　　[7] 雒伟群，高屹. 基于改进RANSAC算法的图像拼接方法[J]. 科技创新与应用，2015（5）：21-22.
　　[8] 赵辉， 陈辉，于泓. 一种改进的全景图自动拼接算法[J]. 中国图象图形学报，2018，12（2）：336-342.
　　[9] 熊飞雪. 基于改进的RANSAC算法的图像拼接研究[D]. 阜新：辽宁工程技术大学，2016.
　　[10] 周剑军，欧阳宁，张彤. 基于 RANSAC 的图像拼接方法[J]. 计算机工程与设计，2009，30（24）：5692-5694.
　　[11] 刘婷婷.  基于单应性矩阵剔除SIFT错误匹配点的方法[J]. 哈尔滨商业大学学报：自然科学版，2016，32（1）：95-98.
　　[12] 王淑霞，周波. 一种基于RANSAC算法的单应矩阵估计方法[J]. 科学中国人，2015 （8Z）：157-161.
　　[13] 单欣，王耀明，董建萍. 基于RANSAC算法的基本矩阵估计的匹配方法[J]. 上海电机学院学报，2006，9（4）：66-69.
　　[14] 瞿中，李秀丽. 基于改进IGG模型的全景图像拼接缝消除算法[J]. 计算机科学，2017，44（12）：274-278.
　　[15] MOU W，WANG H，SEET G. Robust homography estimation based on nonlinear least squares optimation[J]. Mathematical Problems in E-ngineering，2014（6）：372-377.
　　[16] 刘晓霞，李峰，熊兵. 基于韦伯局部特征的图像拼接检测[J]. 计算机工程与应用，2013，9（12）：140-143.
　　（责任编辑：杜能钢）
转载注明来源:https://www.xzbu.com/8/view-15224494.htm