采用局域像素匹配的随机抽样一致改进算法

戴卫华，刘盛春，赵 慎 ，彭 华，张 昊，黄志刚，李小林

(1. 信息工程大学 信息系统工程学院， 河南 郑州 450001；2. 哈尔滨工程大学 水声工程学院， 黑龙江 哈尔滨 150006；3. 陆军工程大学 石家庄校区， 河北 石家庄 050003；4. 盲信号处理国防科技重点实验室， 四川 成都 610041；5. 拉盖尔电子科技有限公司， 湖南 长沙 410073)

图像拼接技术可以有效解决宽视场图像获取问题，是“全景视频”热点应用的技术基础，在视频会议、监控和遥感测绘等领域有广泛的应用[1]。现实中可以采用广角相机拍摄得到宽视场图像，但是这样得到的宽视场图像在边缘容易发生严重畸变，校正畸变的过程十分烦琐，且广角相机光学器件价格昂贵。除此之外，广角相机视场一般不超过180°，只采用单个广角相机很难获取更宽视场图像，尤其是360°全景图像。图像拼接技术恰能解决该问题：采用多个相机，同时获取视场图像，相邻相机的视场图像一般存在30%至50%的重叠区域，所有相机视场能够覆盖360°范围。通过处理，将相邻两个视场图像拼接成更宽的视场图像。经过多次拼接，所有视场图像最终形成一个360°的全景图像。

图像拼接算法众多，大致分为设备标定法和重叠区域检测法[2]。设备标定法需要精密成像器材，耗费大量人工操作，使用很不方便。重叠区域检测法容易自动化操作，实现灵活，因此成为主流方法[3]，其典型代表是尺度不变特征变换(Scale Invariant Feature Transform，SIFT)算法[4]和加速稳健特征(Speeded-Up Robust Features，SURF)算法[5]。SIFT算法利用图像特征点360°方向的梯度信息，同时利用高斯核实现尺度空间变换，具有显著的图像变换不变性，在旋转、仿射、尺度变换等场合下性能稳定，唯一不足的是计算量大。SURF算法则被称为加速SIFT算法，即除了采用盒子滤波代替高斯滤波，其他过程基本一样，性能与 SIFT算法十分接近，但计算大幅度简化，在视频拼接等实时性要求高的场合具有优势。不过，随着图形处理单元(Graphics Processing Unit, GPU)高性能计算芯片技术的发展，SIFT算法在图像、视频拼接领域应用时机逐渐成熟。

无论采用SIFT算法，还是SURF算法，在完成特征提取和特征匹配之后，至少需要4对特征匹配点才能计算参考图像和待拼接图像之间的坐标转换参数，即单应矩阵。在大多数场合，会得到多于4对的特征匹配点，用于计算单应矩阵的匹配点组合很多。由于图像多样性、模糊和噪声等干扰，有些匹配点存在误差，甚至错误，不适合用于计算单应矩阵。因此需要从原始匹配点中选出最佳的4对，以尽可能准确地计算单应矩阵。SIFT算法和SURF算法采用随机抽样一致(RANdom SAmpling Consensus，RANSAC)算法[6]来优选4对特征匹配点，它具有很强的容错能力，本质上是一种离散数据集拟合方法：随机抽取4对匹配点作为一个组合，计算单应矩阵，再计算其余匹配点由单应矩阵映射为内点(即匹配误差在阈值范围内的匹配点)的数目。重复抽样，通过比较各组合得到的内点数目来确定4对最佳匹配点组合以及单应矩阵。然而， RANSAC算法难以适应内点占比低的情形。比如得到12对匹配点，其中，4对内点，8对外点(即匹配误差超出阈值范围的匹配点)，则RANSAC算法优选出错误组合的概率很高。为此，不少学者提出RANSAC改进方法，主要策略是对匹配点提纯，即在执行RANSAC算法之前剔除部分外点。李彬[2]、刘海洋[7]和周玉洁[8]等对匹配点相似程度量化排序，弃用相似程度低的匹配点，或利用图像重叠信息弃用非重叠区域匹配点；汪旌[9]等用行列式点过程抽样实现抽样点的均匀化和分散化, 剔除一些错误匹配点；刘宇[10]等对匹配点分布进行排序并剔除稀疏匹配点。这些改进方法降低了外点的干扰，提高了后续RANSAC算法的效率，本质上则优化了RANSAC算法的数据集输入。

本文提出一种新策略：改进特征匹配点优选准则。即给定特征匹配点的数据集输入，独立于特征匹配点，从参考图像重叠区域任选出局域像素点集合。随机抽样，从输入数据集中选出4对匹配点，构成一个组合，计算单应矩阵，再由单应矩阵计算映射的待拼接图像局域像素集合，然后计算两个局域像素集合之间的像素误差。重复抽样，当像素误差最小时实现局域像素粗匹配，将单应矩阵初步确定为最佳图像转换参数。在此基础上，进一步提出局域像素精匹配方法，对粗匹配所得映射局域像素，在其邻域内各方向进行微调，计算像素误差，当像素误差最小时实现局域像素精匹配，记录此时的微调量，与单应矩阵共同用于图像拼接。

1 RANSAC算法

RANSAC算法最初由Fischler[7]等提出。其本质是一种数据集拟合方法，即确定一个最佳参数模型，以描述数据集。在SIFT算法或SURF算法中，假设数据集为N对匹配点，每对匹配点记为sn=(xn,yn;x′n,y′n)，其中(xn,yn)、(x′n,y′n)为匹配特征点分别在参考图像和待拼接图像中的坐标。数据集记作SN={sn}。执行RANSAC算法的基本步骤如下所示。

Step1：从数据集SN中随机抽样，选取4对匹配点si1、si2、si3与si4，构成一个组合，计算单应矩阵Hi。以参考图像投影变换至待拼接图像的模型参数为例[3]，公式为：

h=(ATA)-1ATb

(1)

式中：

(2)

(3)

(4)

单应矩阵Hi与向量h元素的关系为：

(5)

(6)

Step3：重复Step 1、Step 2，重复随机抽样的总次数为M，得到M个内点统计数，找出最大值，将其对应的单应矩阵取出，作为最佳图像转换参数H。M通过如式(7)计算确定。

M=log1-p4(1-P)

(7)

由此可见，RANSAC算法的核心是在每次随机抽样时判断内点并比较前后两次随机抽样所得内点数目的大小。该方法在数据集内点占比较高的条件下十分有效和稳健，但在外点占比高尤其是外点集中分布时表现不佳。其根本原因为RANSAC算法自身的局限性：判断内点仅依赖数据集空间分布属性，虽然可以保证至少一次抽样的4对匹配点全是内点，但是无法保证该次抽样时计算所得内点总数最大。图1为RANSAC算法用直线拟合局限性示意图。由于外点数目更多，且集中分布在虚线附近，由RANSAC算法原理不难推出虚线拟合下计算所得内点更多，从而错失正确拟合的直线。

图1 RANSAC算法直线拟合局限性示意图Fig.1 Limitation schematic of RANSAC algorithm linear fitting

为克服RANSAC算法局限性，常见策略是尽量剔除外点，正如前文所述；采用新策略：引入特征匹配点以外的监督数据，即图像的局域像素，通过判断局域像素是否匹配，优选出4对特征匹配点，计算单应矩阵。

2 改进算法

改进算法分两部分：局域像素粗匹配和局域像素精匹配。算法所要求的输入数据集与RANSAC算法一致，可以是特征匹配点原始数据集，也可以是经过其他改进方法剔除了部分外点的特征匹配点新数据集。数据集仍记为sN={sn}，匹配点数目为N对。

2.1 局域像素粗匹配

粗匹配基本步骤如下所示。

Step1：在参考图像的重叠区域(避免单一纹理或重复纹理区域)，任选出N个局域像素，构成集合TN={tn}，作为监督数据集，其中tn=(an,bn)。

Step2：与RANSAC算法Step 1相同。

(8)

Step4：重复Step 2、Step 3，重复随机抽样的总次数仍为M，由式(7)确定。得到M个像素误差，找出最小值，将其对应的单应矩阵取出，作为最佳图像转换参数H。

由于局域像素集合TN与匹配对数据集SN点数相同，经单应矩阵映射局域像素、计算像素误差所需计算量与RANSAC方法基本相同。

局域像素匹配本质上也是像素相关算法，但与传统像素相关图像配准方法不同。本算法在SIFT或SURF算法完成特征匹配之后使用，不受图像旋转、尺度变换和仿射变换等影响，像素点未缺失遗漏，避免了传统相关算法的不足。图2以矩形局域像素为例，对粗匹配进行示意。

(a) 旋转变换(a) Rotation transformation

(b) 尺度变换(b) Scaling transformation

(c) 仿射变换(c) Affine transformation图2 局域像素粗匹配Fig.2 Local pixel rough matching

图2(a)、(b)和(c)分别表示图像旋转变换、尺度变换和仿射变换时的局域像素匹配。左图为参考图像，右图为待拼接图像。各图像中的阴影表示重叠区域，阴影中小矩形块内的圆点表示局域像素。从图2看到，无论图像发生旋转、尺度变换还是仿射变换，在参考图像中给定9个局域像素点，在待拼接图像中都会映射出9个局域像素点。只要Step 2随机抽样的4对特征匹配点均为内点，那么局域像素达成匹配，单应矩阵大概率确定为最佳转换参数，而不受其他外点影响，比RANSAC算法更加稳健。

2.2 局域像素精匹配

在粗匹配基础上，进一步，通过精匹配提高本算法图像配准精度。精匹配基本步骤如下所示。

Step1: 在待拼接图像中，以粗匹配得到的映射局域像素为参考中心，在0°～360°范围以45°间隔取8个方向，如图3所示。

图3 局域像素精匹配Fig.3 Local pixel fine matching

Step4: 新得20个像素误差，取最小值，与粗匹配得到的最小像素误差比较。若小于后者，记录其移位方向及移位量，用于图像配准微调，提高配准精度。为避免只匹配到局域极小值，可以适度扩大精匹配范围，例如增加8个移位方向，尽可能搜索得到最佳移位量。

与RANSAC算法相比，本文算法将使图像配准更加稳健和精确。算法计算量略有增加，来自局域像素精匹配，不过只有简单的加减、乘法，而且可根据指标要求灵活调减。

3 算法仿真验证

基于LENOVO小新系列笔记本(inter(R) i5-7300HQ CPU@2.5GHz)硬件和MATLAB R2014b软件，对算法进行验证仿真。

3.1 特征匹配点内点占比高的情景

验证本文改进方法在SIFT算法或SURF算法所得特征匹配点内点占比高的情景下的有效性，并与RANSAC经典算法进行比较。在良好光照条件下通过摄像头采集了图4所示的两幅数字图像(来自武汉理工大学某实验室)，左图为参考图像，右图为待拼接图像，均为png格式，像素大小为216×384，重叠区域约占33%。

图4(a)左、右图中重叠区域用符号“+”标记SIFT算法搜索的有效特征匹配点(描述符欧式距离最小值与次最小值之比不大于0.5)，共15对，内点13对，内点占比达86.7%。在参考图像重叠区域任选9个局域像素点，用符号“·”表示，呈矩形，如图4(b)左图所示。右图用蓝色和黄色符号标记的点分别为通过本文改进算法和RANSAC经典算法在待拼接图像中映射的局域像素。图4(c)是图4(b)在局域像素附近局部放大的效果图。而从放大效果图可以看出，改进算法与RANSAC算法搜索的映射局域像素点接近，但前者更加精确。

图5(a)、图5(b)分别是采用RANSAC与改进算法获得的拼接图像，拼接缝两侧均保留原始像素，未做像素融合，以便于显示拼接位置。可以发现，前者在拼接缝位置存在一点垂直方向的错位，而后者在拼接缝位置对接良好。

改进算法执行局域像素粗匹配阶段用时[1 365×(132+198.4+58.6)]μs,共0.531 0 s。其中：1 365为从15对特征匹配点中任选4对的组合数，即循环控制数；132 μs为单次循环需要计算的映射局域像素坐标耗时；198.4 μs为单次循环插值计算映射局域像素灰度值耗时，58.6 μs为单次循环计算像素误差耗时。在图像局域像素精匹配阶段耗时0.011 7 s，像素匹配总耗时0.542 7 s。与之相比，RANSAC经典算法耗时(1 365×242.3 )μs，共0.330 7 s。故改进算法与RANSAC经典算法计算耗时大致相同。

(a) 特征点匹配(a) Feature point matching

(b) 局域像素匹配(b) Local pixel matching

(c) 局域像素匹配放大(c) Amplified local pixel matching图4 特征点匹配和局域像素匹配效果Fig.4 Feature point matching and local pixel matching effect

(a) RANSAC算法效果(a) RANSAC algorithm effect

(b) RANSAC改进算法效果(b) Improved RANSAC algorithm effect图5 图像拼接效果Fig.5 Image splicing effect

3.2 特征匹配点内点占比低的情景

进一步验证改进算法在SIFT算法或SURF算法特征匹配点内点占比较低的情景下的有效性，并与RANSAC经典算法进行比较。在轻度雾霾天气和逆光条件下用相同摄像头采集图6所示两幅图像(来自郑州某高校实验室)。左图为参考图像，右图为待拼接图像。两幅图质量不高，颜色对比度低，细节不够清晰，仅能分辨建筑、树林和路灯的基本轮廓。两幅图重叠区域约占36%，但仍在33%左右区域搜索特征匹配点。

图6(a)展示了SIFT算法搜索的有效特征匹配点(描述符欧式距离最小值与次最小值之比不大于0.5)，共19对，内点10对，内点占比52.6%。图6(b)、图6(c)依次是局域像素匹配效果的全图和局部放大图。在左侧参考图像中选了16个局域像素，分别通过本文改进算法和RANSAC算法得到映射局域像素；在右图中仍然分别用蓝色和黄色符号标记。由图6(c)可见，两种算法的待拼接图像相对参考图像发生了小角度的旋转。

图7(a)、(b)分别是根据RANSAC算法和改进算法结果进一步拼接的图像，图中参考图像在拼接图中均做了旋转映射。但是，在图7(a)中拼接缝左侧下方存在无法映射的像素区域(用右侧像素填充)，参考图像与待拼接图像在垂直方向未配准，且缩放有明显误差。原因主要是RANSAN算法优选的4对特征匹配点只保证了计算所得“内点”数目最大，而无法有效降低该4对内点自有误差的干扰。相比之下，图7(b)拼接更加精确，验证了改进算法在优选最佳特征匹配点组合和准确计算单应矩阵时的稳健性能。

(a) 特征点匹配(a) Feature point matching

(b) 局域像素匹配(b) Local pixel matching

(c) 局域像素匹配放大(c) Amplified local pixel matching图6 特征点匹配和局域像素匹配效果Fig.6 Feature point matching and local pixel matching effects

(a) RANSAC算法效果(a) RANSAC algorithm effect

(b) RANSAC改进算法效果(b) Improved RANSAC algorithm effect图7 拼接效果图Fig.7 Image splicing effect

4 结论

提出一种基于局域像素匹配的RANSAN改进算法。仿真结果表明：改进算法未明显增加计算耗时，在特征匹配点内点占比较高与较低的条件下，均具有优于RANSAC经典算法的稳健性能，求解的单应矩阵使得图像拼接更加精确。