EDP Sciences logo
Submit your paper
Search
Menu
All issues Volume 37 / No 2 (April 2019) JNWPU, 37 2 (2019) 249-257 Full HTML
Open Access
Issue
JNWPU
Volume 37, Number 2, April 2019
Page(s) 249 - 257
DOI https://doi.org/10.1051/jnwpu/20193720249
Published online 05 August 2019

© 2019 Journal of Northwestern Polytechnical University. All rights reserved.

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License ( http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

图像匹配是计算机视觉和数字图像处理的基础技术，广泛应用于图像拼接[1]、目标定位[2]、SLAM(simultaneous localization and mapping)[3]等领域。基于特征点的图像匹配算法作为当前图像匹配技术的主流方向，得到了国内外研究学者的广泛关注，主要研究如何增加特征点之间的区分性。SIFT[4]、SURF(speeded up robust features)[5]、ORB(oriented FAST and rotated BRIEF)[6]、Harris角点[7]等经典特征得以提出，相应的关于特征描述子的改进工作，如重新设计SIFT特征描述子[8-11]，改进相似性度量方式[12-16]，使用CNN(convlutional neural networks)训练LIFT(learned invariant feature transform)描述子[17]等方法不断被提出。以上这些对图像特征的改进手段在一定程度上能够提高匹配的精度和速度，但由于传统的特征匹配方法在区分正确和错误匹配时过度依赖特征描述子，可能会导致许多正确匹配被不合理地拒绝，匹配召回率仍然不高。

对BF(brute force)[4, 18]、FLANN(fast library for approximate nearest neighbors)[19]等经典匹配方法展开研究，发现：BF匹配方法通过计算2幅图像的特征点描述子之间的欧式距离，寻找最近邻的特征点作为匹配对。由于特征点都是基于局部区域的特征，当2幅图像中存在重复纹理时，会很容易产生误匹配。虽然BF匹配方法的匹配数目较多，但是误匹配也较多，综合匹配性能较差，如何合理地区分正确与错误匹配成为了BF方法急需解决的问题。FLANN方法可以利用比率测试来验证候选匹配特征点对，以剔除虚假匹配，但是由于相似的外观，比率测试会拒绝许多重复结构的特征点，导致许多正确匹配的错误拒绝，影响了匹配的召回率。RANSAC(random sample consensus)[20-23]也可以缓解这一问题，但RANSAC本身要求大多数误匹配应被预先排除，并且当最近距离匹配集合中的误匹配数量较多时会失效。针对RANSAC方法在剔除SIFT误匹配点方面的不足，谭仁龙等[24]提出了一种基于主方向的SIFT误匹配点剔除方法，利用特征点间的主方向夹角近似相等作为约束条件，提高了特征匹配的可靠性和准确性。雷俊锋等[11]将特征点周围邻域的主方向梯度作为特征之一，采用主方向梯度和欧式距离相结合的计算方法进行特征点的匹配，提高了特征匹配效率。边家旺等[25]在特征匹配中引入了运动平滑约束和邻域匹配支持的思想，并在网格框架下加速ORB特征点匹配，使得特征匹配更加快速。此外，以互相关系数作为相似性度量准则的特征匹配算法也被研究[14-16]，通过比较2幅图像在各个位置的相关系数，得到相关值最大的点，即最佳匹配位置，提高了匹配准确率。

为了在剔除错误匹配的同时尽可能地保留更多的正确匹配，以克服特征匹配召回率较低的问题，提高特征匹配的综合匹配性能。本文对特征点主方向和尺度的统计特性展开研究，并借鉴BF匹配方法的高召回率低准确率的特点，采用网格手段，综合利用SIFT特征点的主方向、尺度和位置等约束优化特征匹配，提出了一种基于网格的统计优化特征匹配算法。首先在目标图中寻找原图中每个特征点的最近邻(BF)匹配特征点，得到初匹配结果，其次利用匹配主方向差剔除初匹配中的大部分错误匹配，然后基于匹配尺度比信息对匹配图像划分网格，统计匹配特征点的位置信息在网格间的分布情况，计算原图中每个网格细胞的归一化互相关系数以判断该网格细胞的匹配是否正确，最终得到优化后的特征匹配结果。

本文主要工作是：①研究了最近邻匹配中匹配主方向差和匹配尺度比的统计特性。②提出了匹配主方向差约束、匹配尺度比约束和匹配位置约束，并将其引入特征匹配，克服了特征匹配召回率较低的问题。③基于匹配特征点的位置信息，利用归一化互相关函数和网格法筛选出正确匹配。

1 算法说明

本文算法首先在目标图中寻找原图特征点的最近邻匹配，然后对匹配结果中匹配主方向差和匹配尺度比的统计特性展开研究，1.2节表明可以利用匹配主方向差约束剔除大量误匹配，1.3节表明可以利用匹配尺度比约束为2个匹配特征点划分小邻域，以确保小邻域对应的3D信息基本相同，为本文算法中网格的划分提供了依据，1.4节表明可以利用匹配位置约束进一步地剔除误匹配，从而尽可能地保留最近邻匹配结果中的正确匹配，提高匹配召回率和综合匹配性能。

1.1 定义与记号

由SIFT的定义[4]，假设某SIFT特征点的位置为(x, y), 尺度为σ, 如图 1a)所示。

则该特征点所在的尺度图像为

式中, I(x, y)是图像区域, G(x, y, σ)是高斯核函数, 满足:

计算以(x, y)为中心, 以3×1.5σ为半径的邻域内每个像素L(x, y)对应梯度的幅值和幅角, 公式如下:

利用梯度直方图统计该邻域内所有像素的梯度分布特性, 如图 1b)所示, 横轴是梯度幅角, 纵轴是对应的梯度幅值的累加值, 然后通过对直方图中主峰值和距离它最近的2个柱值进行抛物线插值得到该特征点的主方向θ(0°≤θ≤360°)。如图 2所示, 设原图中的SIFT特征点的主方向为θ原，尺度为σ原; 目标图中匹配SIFT特征点的主方向为θ目, 尺度为σ目, 记:

定义1  匹配主方向差为2个主方向之间的夹角α, 若目标图中匹配特征点的主方向位于区域A, 则α>0;若目标图中匹配特征点的主方向位于区域B, 则α < 0。如图 2和(6)式、(7)式所示:

① 当0°≤θ原 < 180°时，

② 当180°≤θ原 < 360°时，

定义2  匹配尺度比为原图中的特征点的尺度与目标图中匹配特征点尺度的比值。即:

因此匹配主方向差的范围是-180°~180°, 可以利用直方图研究其在最近邻匹配中的统计特性。

thumbnail 图1

SIFT特征参数及梯度方向直方图
thumbnail 图2

匹配主方向差的定义示意图

1.2 匹配主方向差约束

假设1:对于原图中的某一个特征点, 若它匹配错误, 则它在目标图中对应的匹配特征点的主方向可能处于任意方向。

采用TUM[26]的freiburg3数据集, 进行大量实验验证匹配主方向差的分布。当匹配错误时, 虽然2个匹配特征点最相似且都具有旋转不变性, 但由于重复纹理的影响, 它们的主方向可能差别较大。

取数据集的第0帧与第10帧图像, 分别提取1 000个特征点, 用BF匹配方法进行匹配, 得到1 000个匹配对, 其中正确匹配数为686, 错误匹配数为314。正确匹配、错误匹配和所有BF匹配结果的匹配主方向差的标准差分别为3.68, 101.92和57.19, 它们的匹配主方向差的分布直方图分别如图 3所示。取数据集中第0帧图像分别与第0, …, 99帧图像进行匹配, 得到匹配主方向差的标准差分布, 如图 4所示。

由图 3a)和图 4可知, 正确匹配的匹配主方向差近似服从正态分布, 标准差较小, 分布较为集中。由图 3b)可知, 错误匹配的匹配主方向差近似服从均匀分布, 标准差较大, 分布较为发散。结合图 3c)可知, 所有BF匹配的匹配主方向差的分布直方图只有单峰, 而且正确匹配恰好完全落在其中, 这与假设1相对应。因此, 可以通过匹配主方向差优化BF匹配结果, 即:统计BF匹配的匹配主方向差的分布直方图, 选取对应于最高峰和次高峰的匹配对作为初始匹配结果, 这样就可以剔除大量错误匹配。

thumbnail 图3

匹配主方向差的分布直方图
thumbnail 图4

正确匹配的匹配主方向差的标准差分布情况

1.3 匹配尺度比约束

由图 5可知, 正确匹配的匹配尺度比均值与目标图像的缩放倍数近似成反比, 近似满足Mtrue=1/λ, Mtrue为正确匹配的匹配尺度比的均值, λ为目标图像缩放倍数; 相比BF匹配的匹配尺度比的均值, 经过匹配主方向差优化后的匹配尺度比的均值更加接近真实值。因此, 对于正确匹配对应的2个特征点, 可以利用匹配主方向差优化后的匹配尺度比的均值对它们划分小邻域, 以确保这2个小邻域对应的3D信息基本相同。即, 对于原图中某个特征点, 设它的邻域半径为r, 若它匹配正确, 则它在目标图中对应的匹配特征点的邻域半径近似等于r/M, M为匹配主方向差优化后的匹配尺度比的均值。

thumbnail 图5

匹配尺度比的均值的分布情况

1.4 匹配位置约束

假设2:对于某匹配, 若它匹配正确, 则它的邻域内存在足够多的匹配支持该匹配; 若它匹配错误, 则它的邻域内存在较少或没有匹配支持该匹配。

邻域定义为匹配特征点周围的小邻域, 如图 6中区域a、区域b所示。假设2成立是由于运动平滑, 正确匹配对的邻域对应着相同的3D信息, 从而在邻域内存在足够多的相似特征, 即存在足够多的匹配支持; 相反地, 错误匹配的邻域对应着不同的3D信息, 从而在邻域内存在较少或不存在相似特征[25]。

thumbnail 图6

匹配位置约束示意图

2 基于网格的统计优化特征匹配算法

基于以上的分析, 本文使用基于互相关函数的网格法加速对匹配位置约束的求解。2.1节介绍了基于匹配尺度比的网格划分, 2.2节介绍了基于匹配特征点的位置信息, 在网格框架下引入归一化互相关函数筛选正确匹配的方法。算法概述如下：

输入:原图像Ia和目标图像Ib

输出:Inliers

初始化:

1:分别提取SIFT特征点并计算描述子;

2:对Ia中的每个特征点, 在Ib中寻找最近邻匹配, 得到初匹配S0;

3:利用S0的匹配主方向差约束得到初始匹配集合S1;

4:将Ia划分为G1个非重叠网格;

5:利用S1的匹配尺度比约束, 将Ib划分为G2个非重叠网格;

6:for L=1 to G1 do

7:  R=1;

8:  for i=1 to G2 do

9:    if χLi>χLR, then

10:    R=i;

11:    end if

12:  end for

13:计算S(L, R)NCC

14:if S(L, R)NCC≥Tth, then

15:Inliers=Inliers∪χLR

16:end if

17:end for

迭代:

(1) 将原图中的网格分别沿x方向、y方向以及x和y方向平移半个网格细胞, 重复步骤6~17;

(2) 对于不同的G2, 重复步骤5~17。

2.1 网格划分

设匹配主方向差的分布直方图的横坐标范围是-180°~180°, 其中每10°一个柱, 总共36个柱。首先统计BF匹配的匹配主方向差的分布直方图, 选取对应于最高峰和次高峰的匹配作为初始匹配集合S1。

结合1.3节, 为了利用匹配尺度比约束估计图像的缩放倍数, 以区间表示图像可能的缩放倍数, 并将该区间均匀地分为8个小区间, 相邻小区间相差倍。然后计算S1中的匹配尺度比的均值M, 判断落于其中小区间的位置并将该小区间的2个端点值分别记为λ1和λ2。

我们将原图像划分成G1的非重叠网格, 将目标图像分别划分成G2(1)=λ1×G1和G2(2)=λ2×G1的非重叠网格, 每个小网格称为一个网格细胞。基于匹配尺度比约束对图像进行网格划分后, 正确匹配对应的2个网格细胞的3D信息基本相同, 从而可以利用匹配特征点的位置信息进一步地剔除误匹配。另外, 实际处理时, 许多特征点可能位于网格边缘, 因此将原图中的网格分别沿x方向、y方向以及x和y方向平移半个网格细胞, 重复基于网格的匹配优化方法以筛选出正确匹配。

2.2 基于互相关网格的匹配优化

设2幅图像间的正确匹配集合和错误匹配集合分别为T和F。划分网格后, 基于S1统计网格细胞间的匹配数目{χ|χij≥0, i=1, …, G1, j=1, …, G2}。利用匹配位置约束的特点, 设原图中某网格细胞L在目标图中对应的网格细胞为R(如图 7所示), 为考察网格细胞{L, R}的8个邻域的匹配支持情况, 定义{L, R}之间的互相关函数为

式中：Ai表示Li和Ri之间的匹配对数目；Bi表示Li与R′之间的匹配对数目；R′表示在目标图中与Li匹配数目最多的网格细胞。

因此, S(L, R)NCC越接近1, 网格细胞{L, R}之间的匹配可信度越高。即:

thumbnail 图7

网格细胞{L, R}的8个邻域示意图

3 实验及结果

本实验基于64位PC平台的Ubuntu 14.04系统。实验选取TUM[26]和DTU[27]数据集中的图像进行测试, TUM是视频图像序列, DTU包含旋转、尺度、视角、亮度等不同图像。实验图像如图 8所示, 第一、二行分别为原图像和目标图像, 图像分辨率为640×480。

针对图 8所示4组实验图像, 实验时提取SIFT特征点数目N=2 000, 设置经验阈值Tth=0.9和网格大小G1=20×20, 将本文算法分别与FLANN算法(阈值为0.6)、ROBUST[28]算法(阈值为0.6)进行比较, 匹配性能结果如图 9和表 1所示, 匹配耗时结果如表 2所示。此外, 将TUM的freiburg3数据集中的第0帧图像分别与第1, 2, …, 30帧图像进行匹配, 分别计算准确率P、召回率R和F值:F=, 如图 10所示。4组实验a, b, c和d中的准确率、召回率和F值与网格大小的关系如图 11所示。

由图 9和表 1可知, 本文算法不仅在匹配准确率上保持了与其他算法相当的鲁棒性, 而且大大提高了匹配召回率。图 10中本文算法的F值优于经典的FLANN和ROBUST算法, 结合表 1可知本文算法的匹配召回率平均提高了10%以上, 因此本文算法的综合匹配性能更好。由图 11可知, 匹配准确率随网格数量增大而增大, 匹配召回率随网格数量增大而减小, 综合来看网格大小为20×20时既能获得较鲁棒的准确率和召回率, 也能保证较高的计算效率。另外, 由表 2可知, 本文算法计算量较大, 耗时主要集中在SIFT特征提取部分(约334 ms), 匹配部分耗时相对较少(约42 ms), 可见本文的统计优化思想可以快速地对基于SIFT特征点的最近邻匹配结果进行优化。

thumbnail 图8

实验图像
thumbnail 图9

实验结果对比图
表1

本文算法与FLANN和ROBUST匹配算法的性能比较

表2

本文算法与FLANN和ROBUST匹配算法的耗时比较ms

thumbnail 图10

3种算法的准确率、召回率和F值对比图
thumbnail 图11

4组实验中准确率、召回率和F值与网格大小的关系

4 结论

本文提出一种基于网格的统计优化特征匹配算法, 给出了特征点匹配主方向差和尺度比约束, 并在基于归一化相关函数的网格框架下加速对匹配位置约束的求解, 综合利用SIFT特征的主方向、尺度和位置等信息优化特征匹配。与经典的FLANN和ROBUST匹配算法相比, 本文方法显著提高了匹配召回率, 获得了更好的综合匹配性能。但是, 因为本文方法基于图像中SIFT特征点之间的最近邻匹配, 而SIFT特征点的提取耗时较大, 所以本文方法耗时较大。如何加快SIFT特征点间的匹配或将本文方法的统计优化思想用于基于ORB等特征点的图像匹配将是接下来的研究目标。

References

  1. Song F, Lu B. An Automatic Video Image Mosaic Algorithm Based on Sift Feature Matching[C]//Proceedings of the 2012 International Conference on Communication, Electronics and Automation Engineering, 2012: 879–886 [Google Scholar]
  2. Zeng Qinghua, Pan Pengju, Liu Jianye, et al. Fast and Accurate Target Positioning with Large Viewpoint Based on Inertial Navigation System Information Acta Aeronautica et Astronautica Sinica, 2017, 38(8): 193–205 (in Chinese) [Article] [Google Scholar]
  3. Mur-Artal R, Tardós J D. ORB-Slam2:an Open-Source Slam System for Monocular, Stereo, and RGB-D Cameras[J]. IEEE Trans on Robotics, 2017, 33(5): 1255–1262 [Article] [CrossRef] [Google Scholar]
  4. Lowe D G. Distinctive Image Features from Scale-Invariant Keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91–110 [Article] [Google Scholar]
  5. Bay H, Tuytelaars T, Van Gool L. Surf: Speeded up Robust Features[C]//European Conference on Computer Vision, 2006: 404–417 [Google Scholar]
  6. Rublee E, Rabaud V, Konolige K, et al. ORB: An Efficient Alternative to SIFT or SURF[C]//IEEE International Conference on Computer Vision, 2011: 2564–2571 [Google Scholar]
  7. Harris C, Stephens M J. A Combined Corner and Edge Detector[C]//Proceedings of the Facrthe Alvey Vision Conference, Manchester, UK 1988: 147–152 [Google Scholar]
  8. Jin R, Kim J. Tracking Feature Extraction Techniques with Improved SIFT for Video Identification[J]. Multimedia Tools and Applications, 2017, 76(4): 5927–5936 [Article] [CrossRef] [Google Scholar]
  9. Wu T, Miao Z. An Improved Feature Image Matching Algorithm Based on Locality-Sensitive Hashing[C]//2016 IEEE 13th International Conference on Signal Processing, 2016: 723–728 [Google Scholar]
  10. Xia C, Wei P. An Improved SIFT Descriptor Based on In-Out Region Division[C]//2017 IEEE 2nd International Conference on Signal and Image Processing, 2017: 101–105 [Google Scholar]
  11. Lei Junfeng, Zhu Yueling, Xiao Jinsheng, et al. Improved of SIFT Matching Algorithm Based on Main Gradient of Direction Computer Engineeringand Applications, 2015, 51(13): 149–152 (in Chinese) [Article] [Google Scholar]
  12. Yin L, Hou J, Li W. An Improved Feature Matching Method Base on Gradient Constraint[C]//2014 International Conference on Mechatronics and Control, 2014: 684–688 [Google Scholar]
  13. Zhang Y. An Improved Image Feature Matching Method Based on SIFT Descriptor[J]. Boletín Técnico, 2017, 55(3): 300–306 [Article] [Google Scholar]
  14. Nakhmani A, Tannenbaum A. A New Distance Measure Based on Generalized Image Normalized Cross-Correlation for Robust Video Tracking and Image Recognition[J]. Pattern Recognition Letters, 2013, 34(3): 315–321 [Article] [CrossRef] [Google Scholar]
  15. Dinh V Q, Pham C C, Jeon J W. Robust Adaptive Normalized Cross-Correlation for Stereo Matching Cost Computation[J]. IEEE Trans on Circuits and Systems for Video Technology, 2017, 27(7): 1421–1434 [Article] [CrossRef] [Google Scholar]
  16. Rao Y R, Prathapani N, Nagabhooshanam E. Application of Normalized Cross Correlation to Image Registration[J]. International Journal of Research in Engineering and Technology, 2014, 3(5): 12–16 [Article] [Google Scholar]
  17. Yi K M, Trulls E, Lepetit V, et al. Lift: Learned Invariant Feature Transform[C]//European Conference on Computer Vision, 2016: 467–483 [Google Scholar]
  18. Arya S, Mount D M. Approximate Nearest Neighbor Queries in Fixed Dimensions[C]//Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithm, 1993: 271–280 [Google Scholar]
  19. Muja M, Lowe D G. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration[C]//Proceedings of the 4th Internetiarnal Conterence on Computer Vision theory and Appications, 2009: 331–340 [Google Scholar]
  20. Fischler M A, Bolles R C. Random Sample Consensus:a Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J]. Communications of the ACM, 1981, 24(6): 381–395 [Article] [Google Scholar]
  21. Kaur G, Agrawal P. Optimisation of Image Fusion Using Feature Matching Based on SIFT and RANSAC[J]. Indian Journal of Science and Technology, 2016, 9(47): 1–7 [Article] [Google Scholar]
  22. Li Huihui, Zheng Ping, Yang Ning, et al. Relative Angle Distance for Image Registration Based on SIFT Feature Journal of Northwestern Polytechnical University, 2017, 35(2): 280–285 (in Chinese) [Article] [Article] [Google Scholar]
  23. Chou C C, Wang C C. 2-Point RANSAC for Scene Image Matching under Large Viewpoint Changes[C]//2015 IEEE International Conference on Robotics and Automation, 2015: 3646–3651 [Google Scholar]
  24. Tan Renlong, Wan Youchuan. SIFT Mismatched Feature Point Elimination Method Based on Main Direction Geospatial Information, 2014, 12(1): 101–103 (in Chinese) [Article] [Google Scholar]
  25. Bian J W, Lin W Y, Matsushita Y, et al. Gms: Grid-Based Motion Statistics for Fast, Ultra-Robust Feature Correspondence[C]//2017 IEEE Conference on Computer Vision and Pattern Recognition, 2017: 2828–2837 [Google Scholar]
  26. Sturm J, Engelhard N, Endres F, et al. A Benchmark for the Evaluation of RGB-D SLAM Systems[C]//2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2012: 573–580 [Google Scholar]
  27. Aans H, Dahl A L, Pedersen K S. Interesting Interest Points[J]. International Journal of Computer Vision, 2012, 97(1): 18–35 [Article] [CrossRef] [Google Scholar]
  28. Laganère R. OpenCV Computer Vision Application Programming Cookbook Second Edition. Birmingham, UK, Packt Publishing Ltd, 2014 [Google Scholar]

All Tables

表1

本文算法与FLANN和ROBUST匹配算法的性能比较

In the text
表2

本文算法与FLANN和ROBUST匹配算法的耗时比较ms

In the text

All Figures

thumbnail 图1

SIFT特征参数及梯度方向直方图
In the text
thumbnail 图2

匹配主方向差的定义示意图
In the text
thumbnail 图3

匹配主方向差的分布直方图
In the text
thumbnail 图4

正确匹配的匹配主方向差的标准差分布情况
In the text
thumbnail 图5

匹配尺度比的均值的分布情况
In the text
thumbnail 图6

匹配位置约束示意图
In the text
thumbnail 图7

网格细胞{L, R}的8个邻域示意图
In the text
thumbnail 图8

实验图像
In the text
thumbnail 图9

实验结果对比图
In the text
thumbnail 图10

3种算法的准确率、召回率和F值对比图
In the text
thumbnail 图11

4组实验中准确率、召回率和F值与网格大小的关系
In the text

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.