1 引言

图像特征点检测及匹配是图像处理和计算机视觉中非常重要的一类技术,在目标识别、图像配准、目标跟踪、全景图像拼接等领域有着广泛的应用^[1-4]。例如,在目标识别中,匹配点数量的多少会直接关系到能否正确识别出目标。然而,特征点匹配的过程中,图像纹理的相似、噪声的影响及阈值的选择不当等可能导致误匹配现象发生^[5]。误匹配点的存在将会在一定程度上干扰识别结果,降低识别正确率^[6],且误匹配点会在不同场景中有不同程度的影响,必须用某种方法将其消除。需要指出的是,删除误匹配点时需尽量避免删除正确匹配点,保证剔除精度^[7]。研究表明,在图像配准中,正确匹配点的保留比例与配准精度呈正相关的关系^[8-9]。由此可见,如何设计合理的算法以使在剔除全部误匹配点的同时尽可能多地保留正确匹配点具有重要的意义。

传统的误匹配点检测和剔除技术^[10]主要有三类:基于函数模型拟合的方法、基于图的方法、基于统计模型的方法。基于函数模型拟合的方法是尝试找到一个函数模型,使尽可能多的正确匹配点满足该模型的方法。这种方法运算简便、执行速度快,但鲁棒性不理想,当误匹配点较多且误差较大时,会严重影响拟合出来的函数模型,且当匹配情况较复杂时,很难拟合出理想的函数模型,导致剔除精度不佳。基于图的方法(GTM算法)是Aguilar等^[11]在2009年提出的。GTM算法从候选匹配点中构建K最近邻图,通过邻接矩阵的相似度大小判定是否为误匹配点。该算法克服了鲁棒性差的问题,检测精度不依赖特定的函数模型,适用于匹配点较多的场景,但难以剔除图像纹理相似而产生的误匹配点,图像整体的定位能力不强。目前应用最广泛的算法是1987年由Fischler等^[12]提出的基于统计模型的random sample consensus(RANSAC)算法及其改进后的方法,它利用单应矩阵不断迭代估算最优模型参数,包含在估算模型内的匹配点被认定为“内点”,即正确匹配点,其余的“外点”被认定为误匹配点。RANSAC算法同样具有良好的鲁棒性,并克服了GTM算法无法剔除相似图结构中误匹配点的缺点,而且改进后的RANSAC算法减少了迭代次数^[13-14],大幅提升了运算速度。另外,当RANSAC算法的阈值设置过高时,小于该阈值数据的差异就会很大。M-estimator SAC(MSAC)算法通过拓展损失函数的边界,提升了模型的估算精度,但仍存在剔除部分正确匹配点的情况^[15]。

针对目前常用的剔除算法存在的问题,基于Pearson相关系数的概念^[16-17],本文提出了一种新的误匹配点剔除的思路,即利用长度和夹角特征进行双重约束,有效地避免了单一约束条件下无法剔除处于某些特殊位置的匹配点的情况。整体算法包括粗剔除和精剔除两个阶段:粗剔除阶段剔除误差较大的误匹配点,并选定置信度最高的匹配点对作为基准匹配点对;精剔除阶段逐一剔除误差较小的误匹配点,直至相关系数超过阈值。对所提算法和MSAC算法进行对比,实验结果表明,所提算法的剔除精度达到了90%以上,是MSAC算法的1.67倍,在一定程度上克服了MSAC算法剔除精度较低的缺点。

2 算法基本原理

2.1 SURF特征点检测及匹配

加速鲁棒特征(SURF)是图像处理中一种常用的特征点检测算法^[18],它的部分基本原理来源于Lowe提出的尺度不变特征转换(SIFT)特征点检测方法^[19],但SURF算法对SIFT算法中的某些步骤进行优化,使运算速度有了显著提高,且在不同场景中的鲁棒性更强。SURF算法的整体执行效率更高,可以实现计算机视觉系统中的实时处理^[20]。

SURF算法可分为6步。1)特征点提取。与SIFT算法不同的是,SURF算法通过高斯滤波后构建的Hessian矩阵来生成图像的突变点,而SIFT算法采用了difference of Gaussian(DOG)金字塔提取特征点。此外,SURF算法使用盒式滤波器替代高斯滤波器,提高了运算速度。2)尺度空间构建。SURF与SIFT都有构建高斯金字塔的过程,在SIFT算法中,各组的图像大小之间有1/4的降采样关系;而在SURF算法中,组间图像的大小是相同的,各组使用的盒式滤波器的尺寸则是递增的。SURF算法取消了不同组图像的降采样过程,因此优化了计算速度。3)特征点定位。对经Hessian矩阵处理后的图像中的像素点与该点三维邻域中的26个点进行比较,筛选出初步特征点。4)特征点主方向确定。SURF算法通过计算特征点扇形邻域中的harr小波特征之和,将计算结果最大的方向确定为该特征点主方向。5)特征点描述子生成。这一步中,SURF与SIFT的唯一区别在于4×4区域块的方向由特征点主方向决定,SURF算法中特征描述子的数量是SIFT算法的1/2,提升了算法效率。6)特征点匹配。SURF算子在SIFT算子根据欧氏距离计算匹配度的基础上加入了Hessian矩阵迹的判断,从而判断两个兴趣点的对比度变化方向,这一方法可以消除一小部分的误匹配点。

2.2 Pearson相关系数

与RANSAC算法及其衍生算法采用的单应矩阵估算模型的原理不同,所提剔除算法建立在利用Pearson相关系数判定两组长度和夹角之间的线性联系程度之上^[16-17],这一算法克服了传统算法过分关注局部特征而忽略整体性的问题。Pearson相关系数是一种线性相关系数,其取值在-1到1之间,-1代表负线性相关,0代表完全不相关,1代表正线性相关。两组数据x和y之间的Pearson相关系数的表达式为

rPearson(x,y)=S(x,y)σ(x)×σ(y)。(1)

x、y两组数据间的协方差为

S(x,y)=1n-1∑k=1n(xk-x̅)(yk-y̅)。(2)

x的标准差为

σ(x)=1n-1∑k=1n(xk-x̅)2。(3)

y的标准差为

σ(y)=1n-1∑k=1n(yk-y̅)2。(4)

x的平均值为

x̅=1n∑k=1nxk。(5)

y的平均值为

y̅=1n∑k=1nyk,(6)

式中:n为一组数据中个体的数量。通过绘制x为横轴、y为纵轴的散点图,可以更加直观地看出Pearson相关系数的大小与两个数据对象x和y之间相关性的关系。图1中每个子图有300个点,横坐标为x的大小,纵坐标为y的大小,图中数字表示x和y之间的相关度。从散点图可以看出:当散点的分布由服从负相关逐渐变为完全无序时,Pearson相关系数从-1增加到0;当散点的分布由无序逐渐变为服从正相关时,Pearson相关系数从0增加到1。这说明,当两组数据中的大部分为正相关时,如果出现若干不服从正相关分布的点,会降低Pearson相关系数;同样地,如果剔除这些异常点,Pearson相关系数会有很大程度的提升。

图 1. Pearson相关系数的大小与散点分布规律之间的关系

Fig. 1. Relationship between size of Pearson correlation coefficient and law of scatter distribution

下载图片 查看所有图片

3 基于Pearson相关系数的图像误匹配点剔除原理及算法实现

3.1 长度和夹角的双重特征约束

针对特征点匹配时的误匹配现象,以SURF算法为例,提出了一种利用长度和夹角双重特征进行约束的误匹配点剔除算法,该算法的部分思想借鉴了Li等在1995年提出的基于距离比的方法^[21]。Li算法是一种基于统计模型的方法,该方法假设两幅图像中所有正确匹配点对之间的距离比应该近似等于1,距离与1相差较小的匹配点对认定为正确匹配点,若检测到距离比与1差距较大的匹配点对,则可认定为误匹配点。所提算法在Li算法的基础上改变了匹配点连接的方式,并加入了匹配点所形成的夹角的约束,进一步提升了剔除精度,并尽可能多地保留了正确匹配点对。

所提算法的基本原理如图2所示,假设对两张图进行SURF特征点匹配,实线框和虚线框分别为两张图的匹配点及对应情况。可以直观地看出,O(O')、A(A')、C(C')为正确匹配点对,B(B')为误匹配点对,应该予以剔除。此时在各图中以O(O')点为基点,将其与其他点连线,并记录连线长度,所得数据如柱状图所示。由柱状图中的长度数据可以看出,降低原图两组长度数据相关性的原因是线段OB(O'B')的长度不同,当剔除B(B')点后,两组长度数据的Pearson相关系数会有显著提升,此时可以认定为检测到了误匹配点对B(B')。

图 2. 利用长度特征检测误匹配点

Fig. 2. Using the length feature to detect mismatched points

下载图片 查看所有图片

但仅利用匹配点连线长度的数据分布特点无法剔除处于某些特殊位置的误匹配点,如图3所示,实线框和虚线框图中,O(O')、A(A')、B(B')、D(D')为正确匹配点对,C(C')为误匹配点对,当在只加入长度特征约束的情况下,两组数据相关性极高,无法检测到误匹配点对。此时加入夹角特征的约束,按匹配点顺序记录夹角数据,即∠BOA、∠COB、∠DOC。原图中夹角数据的Pearson相关系数在试剔除C(C')时会显著增加,此时认定C(C')为误匹配点对。由此可见,在长度和夹角同时约束的情况下,特殊位置的误匹配点对得以剔除,克服了仅使用长度特征约束的缺陷。

图 3. 同时利用长度和夹角特征检测误匹配点

Fig. 3. Using the length feature and the angle feature together to detect mismatched points

下载图片 查看所有图片

3.2 具体算法实现

算法总体包括粗剔除和精剔除两部分。粗剔除部分中,通过遍历每个匹配点,对每个匹配点与各自图中其余匹配点进行连线,分别计算以该点为基准匹配点时长度和夹角特征数据的Pearson相关系数,即该点在粗剔除阶段的置信度,并剔除置信度低于粗剔除阈值的匹配点。精剔除部分中,通过确定基准匹配点后不断迭代剔除的方式逐步逼近精剔除阈值,直至两图基准匹配点的长度和夹角特征置信度超过精剔除阈值,输出最终的匹配结果。

粗剔除具体步骤如下,流程如图4所示。

1) 输入两幅图像,进行SURF特征点匹配,并剔除一对多、多对一的情况,保证匹配点的一一对应,再根据对应关系对匹配点进行编号。

图 4. 粗剔除阶段流程

Fig. 4. Flowchart of rough eliminating stage

下载图片 查看所有图片

2) 以1号匹配点对为基点,在各自图中与剩余匹配点依次连线。求出图中各连线长度,按照匹配对应关系存入两组数组。

3) 对长度数据进行标准化。从第一对长度数据开始,求出比例系数η=d₁/d'₁,将第二幅图对应的数组中每一元素都乘以η。

4) 计算此时两组数据之间的Pearson相关系数P_d0。

5) 以下一对长度数据为标准,重复步骤3)、4),直至所有数据遍历完毕。

6) 保留P_d0的最大值P_d,此时的P_d为基点对应的长度特征置信度。

7) 按编号顺序,求出两图中各连线之间的夹角,逆时针为负,顺时针为正,按照匹配对应关系存入两组数组。

8) 计算两组夹角数据,得Pearson相关系数P_θ,此时的P_θ为基点对应的夹角特征置信度。

9) 重复步骤2)~8),直至全部匹配点遍历完毕。

10) 按从小到大的顺序分别绘制P_d和P_θ的散点图,对对应的匹配点序号进行重新编号,并拟合曲线,取拐点处的值为粗剔除阈值,剔除置信度小于该阈值的匹配点对。散点图示例由图5所示。

图 5. 置信度散点图及拐点的选择

Fig. 5. Scatter diagram of confidence and selection of inflection point

下载图片 查看所有图片

在粗剔除阶段中,剔除阈值的选取是十分关键的步骤。当选取阈值过大时,会剔除部分应该保留的正确匹配点,提高了误剔除率。当选取阈值过小时,会增加精剔除阶段的迭代次数,进而增加运算时间。此外,精剔除阶段不能完全保证粗剔除阶段保留的误匹配点对被剔除,尤其是一些位于拐点附近的误匹配点被保留的可能性较大,降低了剔除精度。散点图阈值的选择,实际上不止有一种方式。首先对散点图的分布规律进行一定的分析,如图5所示,正确匹配点应分布在纵坐标值较高的区域,即虚线框中;而误匹配点大多数应分布在纵坐标值较低的区域,且由于其随机性,分布范围较大。因此拐点应选在拟合曲线斜率变化最剧烈的位置。本实验中采取的是一种自动选取拐点的方式,如图6所示,右侧为置信度散点图,左侧虚线框内为拐点附近散点的放大图。首先连接散点图纵坐标值最小的点A和最大的点B,选取所有散点中与线段AB垂线距离(线段TC的长度)最大的点D₁以及纵坐标值仅次于D₁的点D₂的中点T作为拐点,即将这两点的纵坐标平均值作为粗剔除阈值。此外,还可以采取对散点分布进行拟合后求二阶导数的零点的方法,或者在等采样间隔的条件下通过判别式来确定拐点位置^[22]。针对散点分布为非常规的情况,也可采取人工选定拐点阈值的方法。

图 6. 选定粗剔除阈值的方法

Fig. 6. Method for selecting a threshold value of rough eliminating stage

下载图片 查看所有图片

精剔除流程如图7所示,其中试剔除的概念为在本轮循环中尝试剔除某组数据,但在下一轮循环中会保留之前试剔除的数据,并非永久剔除,精剔除具体步骤如下。

图 7. 精剔除阶段流程图

Fig. 7. Flowchart of refined eliminating stage

下载图片 查看所有图片

1) 输入此时剔除后的剩余匹配点的信息。设定长度特征精剔除阈值T_d。

2) 以长度特征置信度P_d中的最大值P_dmax对应的匹配点对作为基准匹配点对,按编号顺序试剔除剩余匹配点中的一对。

3) 计算此时两图中基准匹配点对所对应的长度特征置信度P'_d及置信度的增长幅度δ_d=P'_d-P_dmax。

4) 重复步骤1)、2),直至全部剩余匹配点对试剔除完毕。

5) 剔除δ_d的最大值对应的试剔除匹配点对,若此匹配点对为夹角特征置信度P_θ最大值P_θmax对应的匹配点对,则剔除δ_d的次大值对应的匹配点对。

6) 若此时的长度特征置信度P'_d低于阈值T_d,则重复步骤1)~4);若高于阈值,则退出循环。

7) 输入此时剩余匹配点的信息。设定夹角特征精剔除阈值T_θ。以粗剔除后夹角特征置信度P_θ最大值P_θmax对应的匹配点对作为基准匹配点对,计算此时的夹角特征置信度P_θ2。

8) 按编号顺序试剔除剩余匹配点对中的一对,计算此时两图中基准匹配点对所对应的角度特征置信度P'_θ和置信度的增长幅度δ_θ=P'_θ-P_θ2。

9) 重复步骤7),直至全部剩余匹配点对试剔除完毕。

10) 剔除δ_θ的最大值对应的试剔除匹配点对。若此时的夹角特征置信度P'_θ低于阈值T_θ,则重复步骤6)~8);若高于阈值,则退出循环,并输出最终的匹配结果。

关于精剔除阶段的阈值选定方法,确定精剔除阈值T'的表达式为

T'=Pmax+(1-Pmax)×η,(7)

式中:T'为长度特征精剔除阈值T_d和夹角特征精剔除阈值T_θ的统称;P_max为粗剔除结束时长度或特征置信度P的最大值;η为精剔除系数,取值为(0,1),η值越大,精剔除阶段保留的匹配点对越少。

4 实验结果及分析

为验证所提算法对误匹配点的剔除效果,在MATLAB 2019b软件平台上设计了对比实验,对比组采用的算法分别是经典的RANSAC算法、RANSAC算法改进后的模型估算精度更高的MSAC算法^[15]、对RANSAC算法进行运算速度优化后的PROSAC算法。算法的实现借鉴并使用了一部分MATLAB工具箱自带的estimateGeometric Transform函数,将‘transformType’设置为‘projective’。考虑到实时性的要求,对比组全部剔除工作只进行一次。实验所用中央处理器为Intel core i5 9th Gen,图形处理器为GeForce GTX 1650,运行内存为16GB。

实验中使用了三组图片进行对比实验,左边连线代表保留下来的匹配点对,右边连线代表被剔除的匹配点对,“○”符号、“+”符号均代表匹配点。由图8~10中匹配结果可以较为直观地看出,所提算法与对比算法都能保留正确的匹配点对,且定位效果比较好,但是对比组会剔除更多正确的匹配点对。

图 8. 对比实验1的结果。(a)所提算法;(b)MSAC算法;(c)PROSAC算法;(d)RANSAC算法

Fig. 8. Results of contrast experiment 1. (a) Proposed algorithm; (b) MSAC algorithm; (c) PROSAC algorithm; (d) RANSAC algorithm

下载图片 查看所有图片

图 9. 对比实验2的结果。(a)所提算法;(b)MSAC算法;(c)PROSAC算法;(d)RANSAC算法

Fig. 9. Results of contrast experiment 2. (a) Proposed algorithm; (b) MSAC algorithm; (c) PROSAC algorithm; (d) RANSAC algorithm

下载图片 查看所有图片

图 10. 对比实验3的结果。(a)所提算法;(b)MSAC算法;(c)PROSAC算法;(d)RANSAC算法

Fig. 10. Results of contrast experiment 3. (a) Proposed algorithm; (b) MSAC algorithm; (c) PROSAC algorithm; (d) RANSAC algorithm

下载图片 查看所有图片

从表1可以看出,当对比组算法不进行循环时,MSAC、RANSAC和PROSAC算法的平均剔除精度只有57%,而所提算法的剔除精度维持在92%左右,是对比组算法的1.61倍。但从表2可以看出,所提算法的运算时间长于其他三种算法,这主要是由于精剔除过程中存在大量迭代计算,复杂场景中的匹配点数量较大,运算时间会变长。这说明所提算法的特点是误匹配点的误剔除率更低,剔除效果更好,但运算速度较慢。由于对比组算法的随机性,每次运行结果都会不同,因此可以通过迭代多次的方法使剔除精度得到进一步提升,但运算时间也会随迭代次数的增加而成倍增长。所提算法剔除精度较高的原因在于整体算法是建立在一种“先整体再局部”的思想上,即以初始匹配情况作为起始点,然后对局部的误差进行估计和剔除。而随机抽样一致算法随机抽样的原理实际上是基于“以局部估计整体”的思想,因此容易陷入局部最优解而忽略了整体特征^[23],即使增加迭代次数也不能完全避免此种情况。

5 结论

针对传统误匹配点剔除算法会剔除一定数量的正确匹配点的问题,提出了一种基于Pearson相关系数,同时约束长度和夹角特征的剔除误匹配特征点对的方法。将整体流程分为两大阶段。在粗剔除阶段,利用每对匹配点的长度和夹角置信度剔除误差较大的匹配点对。在精剔除阶段,通过迭代逼近的方式剔除匹配点对,最终的置信度超过阈值。对所提算法与MSAC、PROSAC、RANSAC算法进行多组对比实验,结果表明,所提算法能够在保留的匹配点对为正确匹配点对的前提下减小剔除匹配点对中正确匹配点对的比例,减少了传统算法中剔除过度的问题,剔除结果优于对比组算法,适用于会产生较多匹配点对的图像配准或目标识别等场景中。