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

赵春晖, 樊斌, 胡劲文, 张志远, 潘泉

(西北工业大学 自动化学院, 陕西 西安 710072)

图像匹配是计算机视觉和数字图像处理的基础技术，广泛应用于图像拼接[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)所示。

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

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

L(x,y)=G(x,y,σ)*I(x,y)

(1)

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

(2)

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

(3)

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

θ1=θ原

(4)

θ2=(θ原+180°)/360°

(5)

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

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

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

(6)

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

(7)

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

(8)

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

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所示。

图3 匹配主方向差的分布直方图

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

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

1.3 匹配尺度比约束

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

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

1.4 匹配位置约束

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

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

图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:forL=1toG1do

7:R=1;

8: fori=1 toG2do

9: ifχLi>χLR, then

10:R=i;

11: end if

12: end for

13:计算S(L,R)NCC

14:ifS(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。

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

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

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

(9)

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

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

(10)

3 实验及结果

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

图8 实验图像

图9 实验结果对比图

实验序号ROBUST算法匹配数目准确率/%召回率/%FLANN算法匹配数目准确率/%召回率/%本文算法匹配数目准确率/%召回率/%a63410074.168598.779.073198.183.8 b39899.761.645593.866.153296.079.1 c81009.521994.721.43390.935.7 d66199.866.972399.472.888798.688.6

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

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

实验序号SIFT特征提取ROBUSTFLANN本文算法a336.055404.824376.169384.507b323.137380.942346.533360.824c317.437380.929350.093350.213d358.387418.290385.041407.836

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

4 结 论

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