﻿ 基于局部聚类的特征匹配筛选算法
 计算机系统应用  2018, Vol. 27 Issue (12): 192-197 PDF

1. 中国科学院大学, 北京 100049;
2. 中国科学院 沈阳计算技术研究所, 沈阳 110168;
3. 沈阳市环境监测中心站, 沈阳 110016;
4. 东北大学 计算机科学与工程学院, 沈阳 110004;
5. 沈阳市第三十一中学, 沈阳 110021

Filtering Algorithm of Feature Matching Based on Local Clustering
WANG Jin-Bao1,2, ZHAO Kui2, LIU Min3, ZONG Zi-Xiao4, WANG Qi-Le5
1. University of Chinese Academy of Sciences, Beijing 100049, China;
2. Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China;
3. Shenyang Environmental Monitoring Center Station, Shenyang 110016, China;
4. School of Computer Science and Engineering, Northeastern University, Shenyang 110004, China;
5. Shenyang Thirty-First Middle School, Shenyang 110021, China
Abstract: Feature matching is one of the key steps in image mosaic. The matching algorithm based on the best of two nearest matches often has a large number of mismatches. The good filtering algorithm can reduce the mismatch rate and improve the processing efficiency. Therefore, it is of great significance to study this kind of algorithm. The RANSAC algorithm is a widely used filtering algorithm, but it has many defects such as uncertain number of iterations and none of self-adaption in BA process. In this study, we propose a new filtering algorithm of Feature Matching based on Local Clustering (LCMF). The feature points are extracted by SURF and ORB, the BestOf2NearestMatcher algorithm is used to match, and then the LCMF algorithm is used to filter. The experiment shows that the algorithm can get better filtering result when ORB is used to extract feature.
Key words: feature matching     matching and filtering     local clustering

1 特征提取与特征匹配

1.1 SURF与ORB

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

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

(2) Hessian矩阵求极值点.

 \begin{aligned}\sum {{{M}} = \sum\limits_{x = 0}^{x = x4} {\sum\limits_{y = 0}^{y = y4} {\left( {x,y} \right)} } } - \sum\limits_{x = 0}^{x = x3} {\sum\limits_{y = 0}^{y = y3} {\left( {x,y} \right)} } \\- \sum\limits_{x = 0}^{x = x2} {\sum\limits_{y = 0}^{y = y2} {\left( {x,y} \right)} } + \sum\limits_{x = 0}^{x = x1} {\sum\limits_{y = 0}^{y = y1} {\left( {x,y} \right)} } \end{aligned} (1)
 图 1 积分图像

 图 2 盒式滤波器

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

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

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

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

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

 $H\left( {f\left( {x,y} \right)} \right) = \left[ {\begin{array}{*{20}{c}}{\frac{{{\partial ^2}f}}{{\partial {x^2}}}}&{\frac{{{\partial ^2}f}}{{\partial x\partial y}}}\\{\frac{{{\partial ^2}f}}{{\partial x\partial {y^{}}}}}&{\frac{{{\partial ^2}f}}{{\partial {y^2}}}}\end{array}} \right]$ (2)

Hessian矩阵判别式:

 $\det \left( H \right) = \frac{{{\partial ^2}f}}{{\partial {x^2}}}\frac{{{\partial ^2}f}}{{\partial {y^2}}} - {\left( {\frac{{{\partial ^2}f}}{{\partial x\partial y}}} \right)^2}$ (3)

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 最邻近匹配

2 RANSAC与LCMF

2.1 RANSAC

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

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

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

(4) 迭代上述过程;

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

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

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

(2) 迭代次数越多, 结果越理想, 但计算量也越大;

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

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

2.2 LCMF

 图 3 聚类模型简化图

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

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

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) 结束算法, 进行后续处理.

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

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

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

3 实验结果及分析 3.1 实验环境

3.2 匹配筛选

 图 4 图像融合原图

 图 5 SURF特征提取图

 图 6 ORB特征提取图

 图 7 Surf无BA效果图

 图 8 ORB无BA效果图

 图 9 ORB未筛选特征匹配

 图 10 SURF未筛选特征匹配

 图 11 ORB RANSAC筛选特征匹配1

 图 12 ORB RANSAC筛选特征匹配2

 图 13 ORB LCMF筛选特征匹配1

 图 14 ORB LCMF筛选特征匹配2

4 结论

 图 15 全景融合效果图

 [1] 冯宇平. 图像快速配准与自动拼接技术研究[博士学位论文]. 北京: 中国科学院研究生院(长春光学精密机械与物理研究所), 2010. [2] 文伟东, 张明. 基于SIFT算法的全景图像拼接技术研究. 计算机系统应用, 2017, 26(7): 227-231. [3] 于丽莉, 戴青. 一种改进的SIFT特征匹配算法. 计算机工程, 2011, 37(2): 210-212. DOI:10.3778/j.issn.1002-8331.2011.02.063 [4] 曾峦, 王元钦, 谭久彬. 改进的SIFT特征提取和匹配算法. 光学精密工程, 2011, 19(6): 1391-1397. [5] Bay H, Tuytelaars T, Van Gool L. Surf: Speeded up robust features. In: Leonardis A, Bischof H, Pinz A, eds. Computer Vision-ECCV 2006. Berlin: Springer, 2006. 404–417. [6] 赵璐璐, 耿国华, 李康, 等. 基于SURF和快速近似最近邻搜索的图像匹配算法. 计算机应用研究, 2013, 30(3): 921-923. DOI:10.3969/j.issn.1001-3695.2013.03.072 [7] Panchal P M, Panchal S R, Shah S K. A comparison of SIFT and SURF. International Journal of Innovative Research in Computer and Communication Engineering, 2013, 1(2): 143-152. [8] 齐冰洁, 刘金国, 张博研, 等. 高分辨率遥感图像SIFT和SURF算法匹配性能研究. 中国光学, 2017, 10(3): 331-339. [9] Rublee E, Rabaud V, Konolige K, et al. ORB: An efficient alternative to SIFT or SURF. Proceedings of the 2011 International Conference on Computer Vision. Washington, DC, USA. 2011. 2564–2571. [10] 周莉莉, 姜枫. 基于FAST和BRIEF的图像匹配算法. 计算机工程与设计, 2015, 36(5): 1269-1273. [11] 周剑军, 欧阳宁, 张彤, 等. 基于RANSAC的图像拼接方法. 计算机工程与设计, 2009, 30(24): 5692-5694. [12] 许可可, 朱文球, 郭富禄. 基于结构相似的RANSAC改进算法. 计算机工程与应用, 2016, 52(12): 168-171, 245. DOI:10.3778/j.issn.1002-8331.1407-0332 [13] Dubrofsky E. Homography estimation. Diplomová práce. Vancouver: Univerzita Britské Kolumbie, 2009.