基于局部聚类的特征匹配筛选算法①

王金宝,赵 奎,刘 闽,宗子潇,王其乐

1(中国科学院大学,北京 100049)

2(中国科学院 沈阳计算技术研究所,沈阳 110168)

3(沈阳市环境监测中心站,沈阳 110016)

4(东北大学 计算机科学与工程学院,沈阳 110004)

5(沈阳市第三十一中学,沈阳 110021)

特征点匹配即对2幅图像中具有相同或者相似特征的关键点进行匹配,是图像拼接、计算机视觉识别等技术的关键环节[1],在全景融合、监控、直播及三维仿真等领域有着重要应用.但特征点匹配算法基本都或多或少的存在误匹配,现阶段主要通过相关匹配筛选算法来进行处理,其中比较著名的有随机抽样一致性算法(RANSAC),该算法通过利用求解变换矩阵和改进最小二乘法来进行特征点对的匹配筛选.但该算法存在受迭代次数影响大,自适应性差,对匹配数量缺少约束,随匹配点对增长计算量暴增等缺陷.基于以上不足,本文从特征匹配点对局部聚类的角度出发,提出了局部聚类的特征匹配筛选算法(LCMF),提高筛选效率.

为验证LCMF的性能,首先对图像进行特征提取和匹配,SIFT算法作为最经典的特征提取算法有着广泛的应用[2–4],但其发布时间久远,后来基于其算法有着大量的改进算法.本文选取偏重质量的SIFT的升级版算法SURF和较新的偏重于效率的ORB算法进行特征提取,使用比较常用的最邻近算法进行特这个匹配.

1 特征提取与特征匹配

本文采用SURF和ORB分别进行特征提取,采用最邻近匹配算法进行特征匹配.

1.1 SURF与ORB

SURF[5–8],即 Speed Up Robust Feature,是一种加速版的SIFT,2006年被提出.与SIFT算法的主要区别在于:

(1)提出了盒子滤波矩阵的概念,构建尺度空间.

(2)Hessian 矩阵求极值点.

积分图像定义为原图像左上角到点X构成的矩形区域中像素的灰度和,对于图1的M区域计算积分图像,只需做如公式(1)运算即可:

图1 积分图像

盒式滤波器是积分图像的一种快速计算,可以将时间复杂度从O(mn)降到O(1),对于图2,具体过程如下:

图2 盒式滤波器

(1)n×m为盒式滤波器尺寸,先建立 1×M的缓冲区;

(2)计算M次n×1区域的积分图像存入缓冲区;

(3)计算缓冲区开始1×M区域的和,随滤波器的移动,后续只需要前后的一加一减操作;

(4)当滤波器换行时,先通过上下的一加一减操作更新缓冲区,重复上述过程.

SURF算法利用Hessian矩阵来判断极值,Hessian矩阵定义:

Hessian矩阵判别式:

根据H判别式的正负可以判断极值点,SURF算法并不是直接计算H的,而是通过一些优化来计算的.

SURF算法和SIFT算法很相似,但速度明显高于SIFT算法,约为3倍左右[5].

ORB[9],即 Oriented FAST and Rotated BRIEF,是基于FAST和BRIEF算法的一种特征提取算法,于2011年被首次提出,在专利方面不同于SIFT与SURF,可自由使用.ORB算法更关注实时性,速度快于SIFT与SURF,但特征提取质量略差于SIFT与SURF.

ORB算法在FAST和BRIEF的基础上主要做了以下改进和处理:

(1)为FAST算法增加了特征方向.

(2)使用带方向的BRIEF算法对描述子进行处理[10].

(3)带方向的BRIEF特征方差和相关性分析.

(4)具有旋转不变性的去相关BRIEF算法.

1.2 最邻近匹配

经过特征提取处理后获得了关键点的描述子,对同一个人描述子进行匹配,一般可以得到多个匹配结果.计算互相匹配的关键点间的欧式几何距离,选择其中最小的d1与次小的d2,设置阈值β,若其关系满足公式d1/d2＜β,则认为是正确的匹配,保留结果,此算法即为最近邻匹配算法.

2 RANSAC 与 LCMF

在对特征点匹配时,受相机参数、光影等外在影响以及特征提取、特征匹配算法等内在影响,一般会导致较多的误匹配,需要对匹配的点对进行筛选.现应用较广泛的筛选算法有RANSAC等,但其存在诸多不足.本文基于局部聚类的思想,提出了局部聚类匹配筛选算法(LCMF).

2.1 RANSAC

最小二乘法拟合易受缺陷数据影响,产生偏离实际的拟合结果,RANSAC算法针对此问题进行了算法改善,具体步骤为[11,12]:

再次，集中管制力度弱，缺乏有效的内部控制。一般来说，国有企业内部的层次相对较多，其投资的权利也是层层下放，并且缺乏统一的金内部控制标准，财务管制薄弱，导致难以实施科学有效的内部监控手段。

(1)随机选取4对匹配点,计算变换矩阵H;

(2)利用H计算预期点位,计算误差;

(3)统计σ误差范围内的内点数M;

(4)迭代上述过程;

(5)选取内点数最多的作为算法结果.

RANSAC算法与最小二乘法相比,具有更高的鲁棒性,更易于找到理想拟合.但其缺陷也很明显:

(1)迭代次数不易控制,预设定可能得不到理想结果;

(3)只能筛选正确匹配,无法对匹配数量进行约束;

(4)随着点对的增加,计算量呈爆炸式增长.

2.2 LCMF

针对RANSAC算法存在的问题,本文提出了一种完全不同的,复杂度远低于RANSAC的筛选算法.

图像融合基于局部相似性原理,因此正确的图像特征匹配对具有局部聚类的特性,但传统的二维点聚类算法时间复杂度高、随着匹配点对的增多计算量指数式增长,无法适用于图像融合匹配点对的筛选.针对图像融合的特殊性,将聚类模型简化为图3.

图3 聚类模型简化图

对于常规的矩形图像,将图像划分为9部分,对于可以进行图像融合的2幅图像存在以下约束:

(1)至多存在6块图像区域具有完全相同的图像特征.

(2)至少存在1块区域存在局部或完全相似.

另外,理论上2幅图像具有4对以上不共线的特征点匹配就可以进行图像融合,因此特征点聚类可以丢失信息,为不完全的聚类,如图3,若特征点匹配点对集中在块4和5的填色区域,聚类时可以只保留块5中红色区域舍弃块4中相连填色区域.

基于以上思想,LCMF具体算法步骤如下:

算法 1.LCMF 算法1)将进行过特征匹配的两幅图像M1,M2各自划分为9各区域,统计各区域内匹配特征点的数目C1,C2,…,C9;2)对C1,C2,…,C9 进行排序,得到递减序列Cx,首元素为Cx1;3)若Cx1＜25,调用 RANSAC 算法;4)建立集合 Ω=Cx1;5)若Cx(i)/Cx(i+1)＜5,{Ω=ΩUCx(i+1),i++};6)若Cx1＜50,跳到 9);7)将Ω空间元素区域继续划分为9个子区域,迭代一次上述过程,最终得到至多81个元素的Ω={Cy(i)};8)对 Ω 集合元素求和,若∑Ω＞150,计算β=∑Ω/150,设置随机因子α,使删除比例γ=(β–1)/β,进行分块随机删除匹配特征点;9)重新扫描M1、M2,若M1 中匹配特征点已被删除,则删除M2 中对应点,若M1中匹配特征点已被删除,也同样删除M2中对应点;10)更新集合 Z,Z 集合元素数Cz应满足Cz＜150;11)结束算法,进行后续处理.

与RANSAC算法相比,该算法的优势在于:

(1)单步计算速度更快.

(2)计算规模降低,本算法将图像划分为9*9块,使用迭代式计算,简化计算过程.

(3)对匹配结果数量进行约束,选取阈值 150,兼顾效果与效率,具有自适应性.

但当匹配结果过少时,该算法不起作用,因此通过在步骤3)中判断匹配点过少时,调用RANSAC算法来解决此问题.实际使用时,该过程被触发几率较低,即使进行RANSAC计算,计算量也很小,因此该算法在所有情况下都具有较好的自适应性.

3 实验结果及分析

3.1 实验环境

实验环境如下:操作系统版本Win10,处理器i3 4150,内存 8 GB,OpenCV 库版本 3.3.1.

3.2 匹配筛选

图4中4幅图像为图像融合处理实验中使用的图像.

图5是利用SURF算法提取的特征点,图6是利用ORB算法提取的特征点,由图可知,同一图像,SURF算法一般可以获得更多的特征点.另外,理论上只是匹配点具有局部聚类特征,但从图中发现ORB算法获取的特征点也具有局部聚类特征,这可能与FAST算法本身有关.

多个摄像机的光心与图像对应点连线的延伸线理论上应该交于一点,受畸变、误差等因素影响实际上往往无法交于一点,针对此问题,光束法平差(BA)利用LM算法对相机参数进行矫正使观测点坐标和预测点坐标间误差最小[13].图像拼接无BA矫正时处理结果有时会比较糟糕,如图7是基于SURF算法的无BA拼接,图8是基于ORB算法的无BA拼接.虽然BA算法处理后能获得较好的图像融合效果,但其时间开销很大,表1显示了有4幅图像无BA的图像融合时间.虽然BA开销较大,但为了获得效果可观的拼接图像,本文后续实验都是在有BA的基础上进行的.

图4 图像融合原图

图5 SURF 特征提取图

图6 ORB 特征提取图

图7 Surf无 BA 效果图

表1 特征提取性能比较 (单位:s)

图9,图11,图13是基于ORB特征提取的相关图像,图10,图12,图14是基于 SURF 特征提取的相关图像,图9,图10是不经过筛选的特征匹配点对,从图中可以看出,其存在大量的误匹配,图11,图12是经过RANSANC算法筛选过的特征匹配点对,图中只存在一个误匹配,匹配效果较好,图13,图14是经过本文算法匹配的特征匹配点对,与RANSAC相比,唯一的离群误匹配也被删除了,同时也删除了一部分正确的匹配点对,除了特征匹配点对数量的规模不如RANSAC,筛选效果相近.

图8 ORB 无 BA 效果图

图9 ORB 未筛选特征匹配

图10 SURF 未筛选特征匹配

表2显示的是利用RANSAC算法和本文算法进行4幅图像拼接的时间,数据表明,RANSAC算法对SURF和ORB都具有较高的稳定性,ORB算法具有较快的融合速度;本文算法对于SURF算法不太适用,SURF算法图像融合时间不稳定,波动较大,效果与RANSAC相比也不明显,表中记录了3组融合时间,而对于ORB算法却有较好的效果,速度优于RANSAC.

图15是基于ORB特征提取的最终的全景融合图像效果图.

图11 ORB RANSAC 筛选特征匹配 1

图12 ORB RANSAC 筛选特征匹配 2

图14 ORB LCMF 筛选特征匹配 2

4 结论

针对匹配筛选算法RANSAC存在的不足,本文从特征匹配结果具有局部聚类的角度出发,提出了局部聚类的匹配筛选算法LCMF.在对其验证过程中,选择偏重质量的SURF算法和偏重于效率的ORB算法进行特征提取,使用常用的最近邻算法进行特征匹配.实验结果表明,在使用ORB算法进行特征提取时,LCMF获得优于RANSAC算法的实验结果,本文算法具有研究的价值,后续研究将向普适性的改进方向推进.

图15 全景融合效果图

表2 RANSAC 与 LCMF 性能比较 (单位:s)