基于视差梯度约束的RANSAC算法

孙坤

图像拼接技术中的图像配准阶段存在计算量过大的缺陷，这是由于计算变换模型矩阵时，传统的RANSAC算法计算了全部匹配特征点（包括伪匹配点对）对应的模型参数，本文在RANSAC算法前设计了基于视差梯度约束的预检验过程，筛选掉大量伪匹配特征点，大大提高了图像配准效率。

【关键词】图像匹配 RANSAC算法 视差梯度约束

1 引言

我们知道，图像拼接的过程一般分为三个步骤：图像预处理（特征提取）、图像配准以及图像融合。其中，图像配准是图像拼接过程中的核心内容。通过相似性度量准则找到匹配的特征点对，然后通过匹配的特征点对求解图像之间的变换矩阵，使图像的内容在拓扑和几何上对齐，最终完成圖像的拼接。

如今，在图像配准领域常用的的方法有：像素差平方和法、互相关法和RANSAC算法。本文主要对RANSAC法进行相应的研究和改进。在使用RANSAC法对粗匹配的特征角点进行提纯时，由于伪匹配特征点的存在，算法在变换模型计算和检验上花费了大量的时间。本文通过在计算变换模型前增加基于视差梯度约束的预检测过程，筛选掉伪匹配特征点，再进行模型计算和检验，大大提高了图像配准效率。

2 图像配准技术

欲将两幅图像进行无缝拼接，需要求出两幅图像之间的几何对应关系，包括平移、旋转、缩放等。两幅图像A和A1的一般变换模型可表示为：

求解变换模型，就是求解变换矩阵的参数λ0……λ7。在求解过程中需要一定数量的精确匹配点对，这与图像拼接的最终结果密切相关。图像的拼接效果取决于变换矩阵参数估计的精确度，而参数估计的关键在于获取精确匹配的特征点对。在特征点匹配过程中获得的“匹配特征点集合”往往存在一定数量的伪匹配特征点，即在第一幅图像中的某个特征点会对应于第二个图像中的多个特征点。为了获得更精确的匹配特征点对，人们通常用RANSAC算法对匹配特征点进行提纯。

3 RANSAC算法简介

RANSAC算法（随机抽样一致性算法）是一种非常有效的估计算法，如果精确的数据占大多数，伪匹配点对只是少量时，可以用最小二乘法来求解模型的参数和误差；如果伪匹配点对很多，如伪匹配点对的数目超过了50%，最小二乘法就不适用了，而RANSAC算法却可以求解。

3.1 RANSAC算法思想

在模型参数的求解过程中，伪匹配点对的存在是造成结果出现偏差的重要原因，为了提高结果的准确度，需要从原始数据中提取出一组不包含伪匹配点对的数据样本进行模型参数求解，而这需要遍历数据的不同组合，计算量太大。RANSAC算法认为在一定置信概率下，只需要搜索M组抽样（M足够大），就可以认为这组抽样中至少有一组抽样不包含伪匹配点对，利用找出的这组抽样数据来求解出模型的参数，然后将参数代入模型作为假设模型，对其它原始数据进行筛选，筛选掉偏差大的特征点，用保留的精确匹配特征点再次求解模型，得到精确的参数。

3.2 RANSAC算法的具体步骤

（1）计算抽样数量M

P=1-（1-（1-ε）m）M

P：置信概率；ε：数据错误率；m：求解模型参数需要的最小数据量

（2）从原始数据中随机抽取m个数据组成一个抽样，将抽样点数据代入方程，求解模型参数；

（3）将上一步求出的参数代入模型，用这个假设模型来筛选原始数据，去除偏差较大的数据，获得精确匹配点对；重复（2）、（3）步，将M组抽样数据都做相同的处理；

（4）根据每组抽样获得的精确匹配点对的数量和误差方差的大小，选择最优的抽样及抽样数据所对应的模型参数；

（5）用这个最优模型筛选掉原始数据中偏差大的点，用剩下的精确匹配点计算最终的模型参数。

3.3 RANSAC算法评价

当M很大时，RANSAC算法的计算量也会很大，其中包含了大量计算伪匹配点对所对应的参数，做了许多无用功。下面我们将从减少计算错误的参数方面对RANSAC算法进行改进。

4 基于视差梯度约束的RANSAC算法

若要使用RANSAC算法来提纯原数据中粗匹配的特征角点，由于可能会存在一定数量的伪匹配点，所以在实际的匹配过程中会在计算错误的模型参数和检验上浪费大量时间。针对这一不足，我们在计算变换模型前额外增加了一个预检验过程，先检验所选的抽样中是否有伪匹配点对的存在。若没有伪匹配点对，再开始进行模型计算和检验，否则，重新抽样。

根据视差梯度的定义，若当前图像中两个相邻角点m、n分别匹配于另一幅图像中的角点m1和n1，它们计算得出的视差梯度应该小于2。如果经计算，它们视差梯度大于2，则我们可以认为这两对角点并不十分匹配。视差梯度的公式为：

其中，（n1，m）和（n1，n）是对应角点的图像坐标向量，||p||表示向量p的模。

根据以上分析，改进的RANSAC算法步骤如下：

（1）计算抽样数量M

P=1-（1-（1-ε）m）M

P：置信概率；ε：数据错误率；m：求解模型参数需要的最小数据量

（2）从原始数据中随机抽取m个数据组成一个抽样；

（3）在第（2）步选择的随机抽样中，任意选择两对匹配点，计算它们的视差梯度，若其视差梯度大于2，则返回步骤（2）；否则，转入步骤（4）；

（4）将抽样点数据代入方程，求解模型参数；

（5）将上一步求出的参数代入模型，用这个假设模型来筛选原始数据，去除偏差较大的数据，获得精确匹配点对；重复（2）、（3）、（4）步，将M组抽样数据都做相同的处理；

（6）根据每组抽样获得的精确匹配点对的数量和误差方差的大小，选择最优的抽样及抽样数据所对应的模型参数；

（7）用这个最优模型筛选掉原始数据中偏差大的点，用剩下的精确匹配点计算最终的模型参数。

在具体实验过程中，我们发现，采用基于视差梯度约束的RANSAC算法能够有效地提高算法效率，极大地缩短了模型参数检验需要的时间。

5 结束语

本文通过在应用变换模型前增加基于视差梯度的预处理过程，减少了伪匹配特征点的数量，降低了变换模型计算与检验的时间，进而提高了RANSAC算法的效率，从而提高了图像配准的效率，进一步为后期的图像融合的准确性做铺垫。

参考文献

[1]杜志斌.基于角点检测与匹配的图像拼接设计与实现[D].东北大学（学位论文），2011.

[2]杨占龙.基于特征点的图像配准与拼接技术研究[D].西安电子科技大学，2008.

[3]靳峰.基于特征的图像配准关键技术研究[D].西安电子科技大学，2015.

[4]廖斌.基于特征点的图像配准技术研究[D].国防科学技术大学，2008.

作者单位

西北工业大学 陕西省西安市 710000