基于改进的FAST-SURF快速图像拼接算法

陈 伟，刘 宇，王亚伟，孙 静，嵇 婷，赵青林

（1.西安应用光学研究所，陕西 西安 710065；2.西安文理学院 机械与材料工程学院，陕西 西安 710065）

引言

图像拼接是将同一场景中具有重叠视场的两幅或者多幅图像组合，以产生一幅无缝全景图或高分辨率图像的过程，经过拼接所获得的图像有较大的视场[1]。它广泛应用于地质勘测、军事侦察、医学微创手术、航空航天以及视频会议等领域。图像拼接基本流程包括图像预处理、图像配准、图像融合等[2]，其中图像配准是一个重要环节，常用的图像配准算法是基于特征的配准方法，该方法具有计算速度快、鲁棒性好和对图像变形不敏感等优点。常见的特征配准算法中，较为成熟的有SIFT(scale invariant feature transform)[3]算法和SURF(speeded-up robust features)[4]算法。SIFT算法具有尺度不变性和旋转不变性，图像在尺度变化和旋转变化的情况下匹配效果受影响很小，由于采用差分高斯金字塔进行特征点提取，并且每个特征点都需要构建128 维描述子，所以在计算和匹配过程中运行时间相应增加，降低了运行速度[5-6]。Herbert Bay 等人在分析总结多种特征检测方法的基础上提出了SURF 算法，加入了积分图像简化计算，减少了检测特征点的计算量，而且对图像的平移、旋转、缩放等变化具有很好的不变性[7]。尽管SURF 算法具有杰出的性能，但仍然存在计算量大、匹配时间长的问题。FAST(features from accelerated segment test)[8]算法是由Edward等人提出的一种快速角点检测算法，最大的特点就在于其计算效率高，正是由于其具有高速性能，所以更适合应用于快速拼接。本文主要思想是通过FAST 算法在图像重叠区域提取特征点，使用降维SURF 描述子进行特征点描述并改进特征点匹配算法，然后通过随机抽样一致性(random sample consensus，RANSAC)改进算法获取单应性矩阵，再通过图像变换融合实现快速拼接。

1 特征点的提取与描述

1.1 FAST 特征点提取

FAST 特征点提取是速度较快的角点检测算法之一，其过程主要包含非特征点检测、特征点检测、非极大值抑制[9]。FAST 特征点的获取算法实现过程如下：

1）在待检测灰度图像中任选一点P，如图1所示。以P点为圆心，以3 个像素为半径画圆，取如图所示的16 个像素点；

图1 FAST 特征点示意图Fig.1 Schematic diagram of FAST feature points

2）计算P1、P9与P点的灰度差，若其绝对值大于阈值 τ1，则计算P1、P5、P9、P13与中心P的灰度差，若其绝对值中有3 个及以上大于阈值 τ1，则计算P1∼P16这16 个点与中心P的灰度差，若其绝对值中有9 个及以上大于阈值 τ1，则为候选特征点，不满足条件则丢弃；

3）非极大值抑制，找出以特征点P为中心的一个邻域内的所有特征点，分别计算各个特征点与圆周上16 个像素点灰度差的绝对值的总和，若P点的这个值最大，则保留这个特征点。

算法流程图如图2所示。从原理上分析，FAST算法原理简单，计算量小，所以速度快。

图2 FAST 特征点提取流程图Fig.2 Flow chart of FAST feature points extraction

1.2 SURF 描述子

本文使用FAST 算法提取特征点，通过灰度统计信息计算主方向和特征向量，进而获得SURF 描述子。实现过程如下：

1）确定特征点主方向。

以特征点为圆心，6S（S为特征点所在的尺度，本文的方法中，S取值为2）为半径画圆，计算区域内所有像元x和y方向上的Haar 小波响应dx和dy。Haar 小波计算时，每个像元计算尺寸为4S，并对其进行高斯函数加权，然后通过一个 60°的扇形滑动窗口对区域内所有小波响应进行求和，值最大的方向即为特征点的主方向。

2）构建SURF 描述子。

沿特征点主方向构造一个20S×20S的矩形区域[10]，并划分为像元个数一致的16 个子区域。对每个子区域内的所有像元计算尺寸为 2S的Haar 小波响应，分别定义为dx和dy，并对其进行高斯函数加权，累加dx和dy，累加dx和dy的绝对值，形成一个4 维特征向量v，把所有16 个子区域的4 维特征向量v组合起来，就形成了一个64 维特征向量，即SURF 描述子。本文中为了提高匹配速率，对SURF 描述子进行了降维，去掉矩形区域4 个角上的子区域，形成48 维特征向量。

2 改进FAST-SURF 算法

传统的SURF 算法和改进FAST-SURF 算法流程图如图3所示。其中相同部分包括输入两幅待拼接图像，分别提取两幅图中的特征点，为每个特征点构建SURF 描述子，确定特征点主方向，在两幅图中寻找满足要求的匹配点对，采用RANSAC方法求取两幅图之间的单应性矩阵，对待拼接图像进行变换和融合，实现图像拼接。改进算法包括：在重叠区域用FAST 算法提取特征点并对描述子降维，采用自适应最近邻与次近邻比值法和几何约束法进行特征点匹配，改进RANSAC 算法等。

图3 算法流程图Fig.3 Flow chart of algorithm

2.1 图像间的重合区计算

图像拼接中，特征点主要分布在图像的重叠区域，在实际应用中，相机安装位置是固定的，可以提前计算出图像序列之间的重叠区域，特征点检测与匹配时，仅在图像重叠区域之间进行，可以大幅度缩短计算时间。以2 个相机为例，图4 是其几何关系示意图。具体计算步骤如下：单个相机的水平拍摄角度为 α（即相机的水平视场角），相机安装在一个半径为r的圆面上，r通常很小，可以减小2 个相机之间的盲区和视差，相邻相机之间的距离为L，图像拼接重叠区域一般要求10%～50%，可通过（2）式计算图像水平重叠区占比 τ2。

图4 相邻相机几何关系示意图Fig.4 Schematic diagram of geometrical relationship between adjacent cameras

2.2 自适应最近邻与次近邻比值法

本文采用KNN（K-nearest neighbour）算法[11]，又叫K 最近邻算法对特征点进行匹配，衡量特征点匹配程度采用欧式距离，KD 树进行搜索。KNN 算法可以有效衡量邻居的权重，距离较近的邻居比距离远的邻居所占权重高[12]。

参考图像I1和待配准图像I2的特征点描述子分别是q=(q1,q2,···,qn)，p=(p1,p2,···,pn)，按（3）式计算q中每个描述子和p中所有描述子的欧式距离，并进行从小到大排序，按照（4）式计算比值，dj1和dj2分别为最近和次近点间的欧式距离[13]，该值反应最近点与次近点的关系，当这个值具有更大差异优势时才能构成匹配点，通过设置阈值 τ3可以剔除一部分错误匹配点。

阈值 τ3的取值为[0.5，0.9]，按照经验值 τ3通常取0.6。在实际应用中不同的测试图像的最佳阈值是不同的，主要与获取的粗匹配点数有关，τ3越大获得的匹配点越多，误匹配点也越多，后续计算单应性矩阵所需时间越长，效率越低；反之 τ3太小获得的匹配点不足，后续无法计算出单应性矩阵，且精度不高。因此必须合理选择阈值 τ3，通过大量测试数据，按下列方式自适应选取阈值效果最佳。具体步骤如下：

1）KNN 算法获取所有参考图像I1和待配准图像I2匹配点的最近和次近点间的距离dj1和dj2，计算其比值并从小到大排序；

2）首先设置阈值 τ3=0.85，计算满足τ3＜0.85的匹配点个数M；

3）若M＜100，则执行步骤4）；若100 ≤M≤1 000，τ3循环减0.005，直到计算的匹配点个数小于等于(4×M)/9+56，则执行步骤4）；若M＞1 000，τ3循环减0.005，直到计算的匹配点个数小于等于0.5×M并且最大不超过750，则执行步骤4）；

4）完成特征点粗匹配。

2.3 几何约束法

经过自适应最近邻与次近邻比值法获取粗匹配点，其中依然存在错误匹配点，为了提高匹配精度，采用几何约束法进一步提纯。两张待匹配图像，正确的匹配点之间的连线基本平行，其夹角在一定范围内，如果存在错误匹配点，其夹角则不在此范围内。利用这个特点可剔除一些不满足要求的匹配点。2 个粗匹配点的连线夹角α按（5）式计算，其中为匹配点，W为图像宽度。所有粗匹配的特征点之间的连线角度平均值记为αmean。

正确的角度应该在平均值αmean附近，一般角度范围为[αmean-5°,αmean+5°]，在该角度范围外的匹配点是错误匹配点，应该删除。

2.4 改进RANSAC 算法

将上述方法获取的匹配点对，通过RANSAC 算法[14]按照（6）式计算单应性矩阵H：

式中（x，y，1）与（x′，y′，1）为待匹配的特征点。单应性矩阵H中a11、a12、a21、a22功能是旋转、平移、缩放变换[15]，a13、a23功能是水平和竖直方向的平移，a31、a32为梯形失真。在经典的RANSAC 算法中，计算最佳模型参数是遍历所有可能的组合，并以误差最小的一组作为最佳参数，往往导致计算量大、运行时间长。本文对该方法进行了改进，包括减少计算单应性矩阵样本集个数和舍弃不合理参数模型。首先在数据集中选取6 对匹配点，估计出初始模型，若6 对匹配点的检验误差都小于阈值，则用剩余的匹配点计算检验误差；否则重新选取6 对匹配点，直到检验误差都小于阈值。其中第一次出现6 对匹配点满足要求时，计算检验误差，从小到大排序，按顺序取80%的样本作为新的数据集进行下一个循环的迭代。该改进方法缩短了最优结果的计算时间，提高了算法的执行效率。

改进RANSAC 算法流程图如图5所示。

图5 改进RANSAC 算法流程图Fig.5 Flow chart of improved RANSAC algorithm

改进RANSAC 算法对异常匹配点具有良好的抗干扰能力，且具有很好的容错能力。

3 图像融合

为了使图像拼接更加平滑，融合前对待拼接图像进行了直方图均衡化，减弱了曝光差异。将待拼接的两幅图像中的一幅图像进行投影变换，重叠部分像素值为0 的部分用另一幅图像对应位置的像素值进行填充，可有效减弱拼接痕迹。本文图像融合算法采用了渐入渐出加权融合算法。根据待融合像素点距重叠区域左边界的距离，不断改变左右两幅图之间像素点融合时的加权因子，以实现拼接后的图像重叠区域内像素值光滑变化。设I1(x,y)，I2(x,y)分别是待融合的两幅图像，则融合图像F(x,y)的像素值通过（7）式求解：

式中：γ是可调因子，0 ＜γ ＜1。令γ=d1/d，d=d1+d2，d1，d2表示重叠区域左、右边界的距离。

4 试验结果分析

为了验证本文优化算法在特征点的提取、匹配效率以及拼接时间上的效果，进行了以下对比实验。实验环境为CPU Intel Corei5 8 400，主频2.81 GHz，内存8 GB，操作系统Windows 10，开发环境为MATLAB R2013a。本文选取分辨率为992×744 pixels，存在旋转、光照差异的图像进行实验，实验中重叠区域为50%，特征点提取和匹配都在重叠区域进行。为了对比和验证本文优化算法和传统SURF 算法的性能，选取了均方根误差(RMSE)[16]、图像拼接总时间等5 个指标进行比较。均方根误差的计算公式如下：

式中：pi和qi分别表示匹配点对；H为两幅图像之间的单应性矩阵；f(qi,H)表示qi经矩阵H变换后的实际坐标；k为最终匹配点对的个数，该项指标反应了两幅图之间的匹配精度。测试程序运行100 次，求取各项指标平均值，指标对比结果如表1所示。

表1 本文优化算法和传统SURF 算法之间指标对照表Table 1 Index comparison between optimized algorithm and traditional SURF algorithm

从表1 中可以看出，本文优化算法和传统SURF 算法相比，本文优化算法提取的特征点个数要多，拼接效果如图6所示。图6（a）和6（b）为待拼接图像。从图6（c）和6（d）可以看出：传统SURF 算法存在明显的错误匹配，并且特征点的分布范围有限。本文优化算法特征点分布范围广，经过粗精匹配可有效剔除错误匹配点，有利于求取单应性矩阵，从投影变换后的RMSE 相比可知，本文优化算法明显优于传统SURF 算法。从图6（e）和6（f）可以看出，本文的图像融合算法可以明显消除拼接痕迹。从指标量化角度出发，本文优化算法和传统SURF算法相比较：特征点提取时间减少了30%，特征点匹配时间减少了45%，均方根误差减小了35%，图像拼接总时间减少了12%。从各项指标对比来看，本文的方法是可行的，在匹配准确率和效率上均有明显提升。

图6 传统SURF 算法和改进FAST-SURF 算法对比图Fig.6 Comparison images of traditional SURF algorithm and improved FAST-SURF algorithm

5 结论

本文提出了一种改进的FAST-SURF 算法，和传统的SURF 算法相比，在特征点提取区域、特征点提取方法、特征点描述子构建、特征点匹配和单应性矩阵获取上进行了改进，通过实验验证该算法在多数场景下具有拼接效果好、速度快的特点。该算法解决了传统算法计算时间长，匹配精度低的问题，具有一定的工程应用价值。该方法对于图像中存在尺度变化，以及图像视差导致拼接缝合处存在“鬼影”和重影问题，不能较好地适应，需要在以后的工作中进一步优化。