一种新的无人机航拍图像快速拼接算法

李玉峰，任静波

(沈阳航空航天大学电子信息工程学院，辽宁 沈阳，110136)

1 引言

在无人机航拍过程中，受所携带相机拍摄范围限制，无法在一张图像中记录所有的场景，此时就需要运用图像拼接技术[1]将数张无人机航拍图像拼成一张完成的图像。

目前，无人机航拍图像拼接技术主要有以下三个步骤：图像预处理，图像配准和图像融合[2]。其中图像配准是图像拼接过程中的主要步骤。

图像配准的方向大致可分为三个，基于变换域、基于灰度信息以及基于特征信息[3]。其中基于特征的图像配准方法是目前最常用的配准方法，该方法只需要提取图像中的点、线或边缘特征等少量信息[4]。常用的特征提取算法包括：Harris等[5]提出一种组合式拐角和边缘检测器，称为Harris算法，Harris算法直接提取图像中的角点和边缘信息，但是环境适应能力较差[6]；David等[7]提出了一种关键点比例不变的图像特征提取算法SIFT，SIFT算法作用在高斯变换后的尺度空间内，寻找图像在变换后保留下来的局部特征点，并提取其所在图像位置，这种算法在特征点数量有限的情况下具有较好的稳定性甚至可以达到实时性的要求，但在纹理细节不丰富的图像上则容易造成错误匹配[8]；Bay等[9]提出了提取速度快且同样具有鲁棒性和抗干扰性的SURF算法，大幅改进了特征提取的效率，但SURF与SIFT这两种算法的缺点是不能较好的保留图像的细节与边缘信息[10]；Rublee等[11]提出了ORB算法，该算法具备良好的旋转不变性和鲁棒性，同时特征提取速度快，但缺点是尺度不变性上有所不足[12]-[13]；Leutenegger等[14]提出了一种二进制鲁棒不变可伸缩的关键点检测算法BRISK， BRISK算法主要使用快速角点检测(FAST)进行特征点检测，该算法计算速度快但鲁棒性较差；Alahi等[15]提出了一种快速关键点检测算法FREAK(Fast Retina Keypoint)， 它采用了一种类似于人类视网膜感知图像的模式，FREAK算法最大的特点是快速，且具有方向不变性[16]；Pablo等[17]-[18]先后提出了KAZE， A-KAZE算法，A-KAZE为KAZE加速版，其中，KAZE和A-KAZE 在创建的非线性尺度空间中通过非线性扩散滤波来检测和描述其中的特征点。这两种算法在旋转、尺度和光照不变性方面均表现稳定，同时鲁棒性好，匹配成功率高[19]。

本文提出一种新的无人机航拍图像拼接算法，针对A-KAZE算法在特征向量描述阶段计算量复杂，用时长的缺点，首先对A-KAZE算法的特征向量描述部分做出改进，使用经主成分分析法精简降维的FREAK算子进行特征向量描述；同时针对特点量匹配阶段存在引入错误匹配的情况，本文对最近邻比率策略的基础上对其进行改进，设定次近邻特征点的搜索阈值，从而提高特征点初次匹配的配准效率，同时提高了配准速度，再利用随机样本一致性算法对特征点进行二次匹配。最后使用加权平均融合算法对图像进行融合。试验结果表明，本文所提方法在拼接图像的过程中用时更短，且拼接准确率和拼接精度均有提升，可应用于无人机航拍图像拼接中。

2 A-KAZE算法

A-KAZE算法是基于非线性尺度空间的特征检测和描述算法，同时在KAZE算法的基础上采用快速显示扩散数学框架(Fast Explicit Diffusion，FED)来快速求解偏微分方程[20]。

A-KAZE算法主要包括五个步骤[18]：

步骤1：非线性尺度空间构造。利用非线性滤波函数和快速显示扩散数学框架加入金字塔框架从而加速非线性尺度空间的构建，如式(1)所示

L(i+1，j+1)=(I+τjA(Li)L(i+1，j))，

j=0，1，…，n-1

(1)

其中，I为单位矩阵，τj为恒定步长(限制显示扩散的稳定条件)，A(Li)是对图像编码的传导矩阵，L为非线性尺度空间下的滤波图像。

步骤2：寻找局部极值点。对每一个滤波后的图像求其Hessian矩阵的局部极大值点，通过极大值求解特征值，Hessian矩阵的计算公式如式(2)所示：

(2)

步骤3：计算特征点主方向。以特征点所在位置为中心，半径为6σi区域内求取相邻点的方向导数Lx，Ly，然后进行高斯加权。建立一个π/3的扇形区域，该扇形以0.15弧度为步长为单位进行旋转，对整个圆内区域进行遍历，从而获得最长向量。该最长向量的角度即为特征点的主方向。

步骤4：特征向量描述。采用二进制描述子M-LDB对特征点进行描述。在每个特征点周围选择一个固定区域，将区域的分成3×3的网格，对网格中的每一个点进行二进制操作ω，形成一个二进制描述符。如式(3)所示

ω(Func(i)，Func(j))=

(3)

其中，Func()为网格中每个点所在区域的平均强度信息和水平、垂直方向上的梯度信息。

步骤5：特征向量匹配。对两个特征向量计算其欧氏距离，欧式距离即n维空间中两个点之间的实际距离，在二维空间中，其公式如式(4)所示

(4)

其中，(x1-x2)和(y1-y2)为两特征向量的坐标。

3 特征描述及匹配优化算法

A-KAZE算法在旋转和尺度变换方面具有不变性等优点，但算法的实时性较差，难以满足数量巨大的无人机拍摄图像的拼接要求。因此，本文使用A-KAZE算法构建非线性尺度空间并寻找局部极值点，采用二进制描述子FREAK进行采样，并使用主成分分析法对采样后的描述符进行精简降维，并使用降维后的描述符进行特征点描述，在特征向量匹配阶段使用汉明距离进一步减少计算时间和运算所需内存，从而提高特征向量匹配速度。

3.1 基于精简降维的特征向量描述

特征描述子FREAK如图1所示，图内每一个圆内区域包含有一个采样点，即圆心位置。采样开始时首先对每个圆内区域进行高斯模糊处理，圆的半径为标准差，从而降低区域内噪声对后续采样的影响。

特征描述子FREAK算法的采样结构为6、6、6、6、6、6、6、1，这里的6表示每一个半径相同的采样范围内中有6个采样点，并且这6个采样点位置所处在一个同心圆中，最后的1即代表最终的特征点。

图1 FREAK算法采样方式

FREAK描述子采用二进制的方法对特征点实现描述，用F表示，如式(5)所示

F=∑0≤α≤N2αT(Pα)

(5)

其中，Pα为一个采样点对，N表示为特征向量的维度，T(Pα)是一个函数其定义如式(6)所示

(6)

FREAK算子每次采样可以得到43个点，共可以得到N=(43(43-1))/2=903个采样点对，有些采样点的值不影响最终采样点的确定，反而会增加采样特征冗余。

因此本文提出一种基于降维的特征向量描述方法，在FREAK算子采样得到采样点对后，运用主成分分析(Principal Components Analusis， PCA)旨在找出采样点对数据中的主成分，并利用这些采样出的主成分来概括原始数据信息，从而达到降维但保留主要信息的目的。

故对于通过FREAK每次采样得到采样点对，组成数据矩阵{v1，v2，…，vn}，其中所有的向量均为列向量，每行数据代表一个特征点。按照主成分分析法的步骤，对数据矩阵中的所有数据进行中心化，可表示为式(7)：

{x1，x2，…，xn}={v1-μ，v2-μ，…，v3-μ}

(7)

(8)

(9)

引入拉格朗日乘子，并对ω求导并令其等于0，便可得出∑ω=λω，此时

D(x)=ωTWω=λωTω=λ

(10)

这样就得到了x投影后的方差就是协方差矩阵的特征值，而要选择的最大方差投影即为协方差矩阵的最大特征值，最佳投影方向就是最大特征值对应的特征向量。

至此，主成分分析法降维特征向量的步骤如下：

1) 对样本数据进行中心化处理，将每次FREAK算子采样得到的二进制特征按照每行为一个特征点组成特征矩阵，假设提取所有特征点的前128位组成128×128的矩阵v，则

(11)

并计算每一行的均值

(12)

将矩阵v的每一行减去均值，得到新矩阵x

(13)

2) 求样本的协方差矩阵：

(14)

通过计算对协方差矩阵进行特征值分解，得到协方差矩阵的特征值λi和特征向量ωi。

3)将特征值从大到小进行排序，选取前d个特征值对应的特征向量ω1，ω2，…，ωi，通过映射

(15)

将样本映射到d维，其中i为第i个特征点，d为降维后的主成分信息。通过该方法，得到最能表征主成分的信息，即降维后保留主要信息的特征向量。

在完成特征向量降维后，特征点的主方向确定通过式(16)确定，计算公式如下

(16)

式中，O为特征点局部邻域的梯度值，M为采样点对的总个数，G表示采样点对的集合，PO为采样点对的所在位置。

3.2 阈值限定的最近邻距离比率匹配策略

A-KAZE算法使用汉明距离作为特征点的相似性度量。但直接计算最近邻匹配特征点会引入很多错误匹配。本文在汉明距离基础上使用改进的最近邻比率策略可以使得匹配结果更精确。

为了方便搜索特征点，在特征点匹配阶段将图像划分为n×n的网格，然后以网格为单位进行特征点搜索，从而改进最近邻比率策略特征匹配算法步骤如下：

1)将参考图像与待匹配图像划分成n×n的网格；

2)检测参考图像A得到特征点标记为FAi，再计算待匹配图像B中与图像A最近邻的特征点标记为FBj，其中i是图像A的特征点的位置，j是图像B中与图像A的i点最近邻点的位置；

3)以FBj所在区域为中心，建立一个5×5的邻域，在邻域中搜索近邻特征点并标记为FBk，k是图像B中与图像A的i点次近邻点的位置，通过式(17)的计算，即最近邻汉明距离D(FAi，FBj)与次近邻汉明距离D(FAi，FBk)的比率满足小于固定值TD，TD一般取值范围为[0，0.8]，则图像A的特征点FAi在图像B的匹配特征点即为FBj。

(17)

4)按照步骤三中方法寻找所有正确的匹配点对，得到正确的匹配特征点对；

4 无人机航拍图像拼接

由于无人机航拍图像相邻图像的相似程度较高，经过初次匹配的图像仍然存在错误的匹配点，因此本文在二次匹配中使用随机样本一致性算法剔除错误匹配点。随后使用随机样本一致性算法求解单应性变换模型，利用算法剔除错误匹配点后的4个正确特征点带入式(18)中，计算可得到3×3的单应性变换矩阵。单应性变换矩阵有8个参数，分别为(h0，h1，h2，h3，h4，h5，h6，h7)。

(18)

将图像经过单应性变换后叠加，为了使拼接后的图像整体颜色亮度保持一致，再使用加权平均算法对匹配后的图像进行融合，计算公式为

(19)

其中，R1为图像A所在区域，R2为图像B所在区域，v1与v2为权值，且满足v1+v2=1，当生成拼接图从左至右过渡时，v1的取值由0到1逐渐增大。

如图2所示为本文提出的一种新的无人机航拍图像快速拼接算法主要流程。

图2 一种新的无人机航拍图像快速拼接算法流程

5 实验结果与分析

本文测试图片为2018年无人机对辽宁盘锦红海滩湿地所拍摄的1100中挑选出来的具有地形代表性的3组张图片，如图3所示。同时，实验为了验证本文算法的性能，都将本文算法与传统的SIFT[7]算法，SURF[9]算法、ORB[11]算法、KAZE[17]以及A-KAZE[18]算法进行比较。

图3 无人机拍摄图像组合

5.1 特征点提取速度对比

特征点提取速度对比采用每个特征点提取的平均时间作为评价指标，用时越短，速度越快。图4给出了五种常用算法以及本文算法对六张高分辨率图像进行特征点提取平均用时对比。可以看出。本文算法在提取时间上比ORB算法更快，相对KAZE算法和SIFT算法在时间上有较大缩短，虽然同样需要构建非线性尺度空间，但使用降维后的特征向量描述可以很大程度的减少冗余特征点的描述，且采用二进制描述子可以大大减少计算量从而提取速度有了较大提升。

图4 各算法提取特征点的用时(ms)

5.2 特征匹配速度对比

特征点匹配速度采用匹配时间作为对比，时间越短，匹配速度越快。从图5中可以看出，SIFT算法和SURF算法耗时较长，ORB算法、KAZE算法和A-KAZE算法次之，主要原因在于SIFT算法与SURF算法采用欧式距离进行特征点相似度匹配，会耗费大量的时间；本文相较于KAZE算法和A-KAZE算法在匹配时间上有所提高，主要原因在于改进的最近邻比率策略可以节省图像遍历搜索相似特征点的时间，从而使得匹配时间有所减少。

图5 各算法匹配时间(ms)

5.3 匹配正确率对比

图6为各算法匹配正确率的对比数据，匹配正确率通过式(20)计算得出

(20)

其中，Nc为正确的特征点匹配数目，N为特征点细匹配后的数目。从图8可以看出，本文算法与KAZE、A-KAZE算法的匹配正确率相对较高，这是因为KAZE算法、A-KAZE算法与本文算法均采用了构建非线性尺度空间来提取特征点，使得特征点提取准确性增强。综合图7和图8可以看出本文算法在保证了匹配时间较短的情况下实现了较高的匹配正确率。

图6 各算法匹配正确率(%)

5.4 配准精度对比

拼接结果的成功与否与配准精度有着较大的关系，本文采用参考图像与待匹配图像之间点的距离均方根误差RMSE(Root Mean Square Error)作为配准精度的评价指标。其定义为

(21)

表1 各算法配准精度

表1给出了各个算法的配准精度对比，由于本文选取的图像为有雾天气下拍摄的无人机高分辨率图像，从而会导致图像的光照条件发生变化，给配准带来影响。从表中可以看出本文算法在对比实验中配准精度最高，这是因为本文选用的FREAK算子具有光照、旋转和尺度不变性，在有雾的情况下仍然可以精确配准图片，适用于复杂环境下的无人机航拍图像拼接。

通过上述实验结果可知，ORB算法虽然有着较快的特征点提取速度，但是牺牲了匹配精度以及匹配正确率；SIFT算法与SURF算法虽然匹配正确率和配准精度较高，但是其特征点提取速度和特征点匹配速度较慢，在实际使用时如需要处理大批量的图像拼接任务会导致算法效率低；KAZE算法与A-KAZE算法在以上四个方面均有不错的平衡，本文通过对特征描述及匹配算法的优化，在保证配准精度的前提下提升了特征点提取速度，同时有着较快的特征匹配速度。综合以上四个方面，本文算法在图像拼接方面有较高的效率及优势。

5.5 图像拼接结果

如图7所示为本文算法与A-KAZE算法的图像拼接效果对比图，带有标记的图为A-KAZE算法的拼接图，从拼接对比图一中可以看出，红框内可以明显看出有拼接缝的存在，且拼接缝的两边的道路出现了错位的现象；从拼接对比图二中可以看出明显的几何畸变，从2可以看出绿框内的道路和小路存在弯曲和错位，其纹理细节也存在模糊的现象，3中存在大面积的拼接缝；从拼接对比图三的2中可以看出，拼接缝两侧存在明显的颜色差异，颜色亮度不一致。拼接对比图的下方为本文算法的拼接效果图，从图中可以看出拼接图实现了无拼接缝且过渡平滑，整体颜色和亮度保持一致，说明拼接效果良好。

图7 拼接对比图

6 结论

为了提高无人机航拍图像拼接的效率以及实时性，本文提出了一种新的无人机航拍图像快速拼接算法。该算法根据A-KAZE算法的基本原理，采用主成分分析处理以及运用阈值限定策略提升了特征点提取速度和匹配速度，对无人机航拍图像进行快速拼接。试验结果表明，本文算法相较于改进前的算法在特征点提取时间上最多缩短了50%，特征点匹配用时最多缩短了24%，匹配正确率最高可达99.51%，图像配准精度最多提高了30%，且图像拼接结果颜色和亮度一致，无明显的拼接缝，且具有较强的实时性。在未来的工作中可以考虑采用更高效的特征向量提取算法和匹配算法，从而进一步提高整体运行效率和减少拼接时间。