基于ORB的无人机图像快速拼接算法

王慎谦，张荣国，李晓波，王 晓，王 芳

(太原科技大学 计算机与技术学院，太原 030024)

近年来，无人机遥感技术已经广泛地应用于军事和民用领域，无人机(UAV)遥感是一种低空技术，已成为信息获取的重要手段。无人机具有采集速度快，操作方便，安全性好，投资少等优点，已广泛用于各种地面勘察应用中。但是，由于飞行高度低且摄像机的焦距有限，因此无人机图像的景物很小。因此，捕获相对完整的目标区域变得困难。同一目标的多个图像应通过技术手段组合以获得所需目标的完整场景。图像拼接的目的是将具有重叠部分的多个图像组合在一起以形成全景图像。

图像拼接主要包括特征提取，特征匹配，光束调整，自动全景校正，增益补偿和多波段融合。在图像拼接领域中最著名的特征提取算法是D.G.Lowe提出并完善的尺度不变特征变换的方法(Scale Invariant Feature Transform，SIFT)[1]，SIFT算法有着较好的尺度不变性，对于光照、噪声、旋转、缩放、遮挡都具有良好的抗干扰性，然而特征点的检测采用尺度空间极值，特征描述子则采用梯度直方图的方法来计算，这导致了该算法的计算量大，时效性低。加速鲁棒性特征(Speeded Up Robost Features，SURF)算法[2]是由H.Bay等人提出的对SIFT改进的一种算法，它基于Hessian矩阵对极值空间中特征点检测的加速和特征描述子降维的方法来降低计算时间，但是依然不能满足实时性的要求。除了传统的人工标注的图像匹配方法外，当前基于深度学习的图像处理方法也被广泛的应用于解决图像匹配的问题，深度学习的方法能够提取更加细微的特征信息，但深度学习网络需要复杂的结构和更多计算时间，而ORB(Oriented FAST and Rotated BRIEF)算法[3]基于改进的FAST和BRIEF算法，在特征检测的实时性方面有着显著的效果。

为了解决ORB算法特征匹配精度低和特征提取稳定性差的问题，本文提出一种基于改进的ORB无人机图像拼接算法，采用四叉树对特征点均匀分布和图像局部熵自适应阈值来改进ORB算法。改进的算法与原ORB相比，在保证特征提取速度的前提下，特征点匹配精度明显提升。

1 基本理论

ORB是 Rublee 等人在 2011 年提出的一种利用二进制字符串描述特征点的特征提取算法。ORB算法通过改进的FAST特征点和BRIEF特征描述子，使其具备了尺度不变性和旋转不变性，该算法最大的特点是速度快，具有旋转不变性，降低了对噪声的敏感性。

1.1 特征点提取

FAST特征点检测算法是从图片中选取一个像素p，设置该点的亮度值为Ip，以p点为中心，在半径3的圆上取16个像素点。设置一个阈值t，如果选取圆上有个连续n个点亮度大于Ip+t或者小于Ip-t，则像素点被定义为特征点。计算公式如式(1)所示：

(1)

为了提高特征点检测速度，快速排除大量非特征点，首先会检测像素p的1，5，9，13四个像素点的灰度值，如果其中3个点亮度大于Ip+t或者小于Ip-t，则被定义为特征点。特征点检测如图1所示：

图1 FAST特征点检测示意图

由于FAST不具备方向性和尺度不变性，因此需要构建金字塔实现尺度不变性，然后采用灰度质心法为FAST提供方向性，灰度质心法主要思想是计算特征点以r为半径范围内的质心，从特征点坐标到质心形成一个向量作为该特征点的方向，具体步骤如下：

(1)在一个图像块B中，定义图像块矩为：

(2)

其中I(x,y)为(x,y)处的灰度值。

(2)通过矩计算出质心为:

(3)

θ=arctan(m01,m10)

(4)

1.2 BREIF描述子

ORB算法中特征描述使用BREIF，它是一种二进制描述子，其描述向量是由0和1组成，先对图像进行高斯滤波，减少噪声的干扰，在以特征点为中心的S×S像素区域内，随机选择n点对进行灰度值比较，并进行如下二进制赋值:

(5)

其中p(x)，p(y)分别代表x和y处的像素灰度值，通过比较得到n个二进制码串组成一个n维二进制失量为:

(6)

为了使特征描述子具有方向性，将特征点质心方向信息添加到描述子中，对于位置(xi，yi)处包含n个二进制测试的特征集合构成一个2×n的矩阵Q为：

(7)

定义特征点方向θ与对应旋转矩阵Rθ构造的特征点对矩阵为：

Qθ=RθQ

(8)

具有方向的特征描述子为：

gn(p,θ)=fn(p)|(xi,yi)∈Qθ

(9)

采用贪婪搜索对256个像素对进行不相关的测试，构成最终的具有方向的特征描述子BRIEF.

2 ORB改进算法

2.1 基于四叉树的特征点均匀分布

四叉树的数据结构是其每个节点下至多可以有四个子节点，在二维空间内分为四个区域，并且在该区域中信息存入四叉树节点中。本文引入四叉树概念来均匀分布特征点，FAST是采用4个像素点灰度差来快速判断特征点，这经常会导致提取的特征点过于集中在纹理比较明显的区域，而纹理较弱的区域很难提取到特征点，使得匹配精准度下降，为此提出使用四叉树来均匀分布的方式提取FAST特征点。

首先，为FAST算法增加尺度不变性，通过高斯卷积核对图像进行下采样，构建八层金字塔,并且按照每层的尺度因子给每层分配所需的特征点的数量，每层所需的特征点数量计算如下：

(10)

其中N为所需特征点数量，s为尺度缩放因子，i是层数，Ni为每层所需的特征点。

其次，基于四叉树对特征点进行均匀提取，其步骤为：(1)在特征点提取时，我们对金字塔中每一层图像用大小为30×30像素的网格进行划分，再对每个网格提取FAST特征点；(2)采用四叉树筛选特征点，通过计算图像的宽度和高度的比例得到初始节点数为n；(3)如果节点内的特征点数大于1，则每个节点继续分裂成四个节点，直到节点内的特征点数大于所期望的特征点数则停止分裂；(4)然后提取每个节点内质量最好的特征点。四叉树均匀分布如图2所示：

图2 四叉树均匀分布

2.2 基于局部熵的自适应阈值

在传统的ORB算法中，特征点提取是通过人工经验设置的固定阈值，无法适应图像的明暗变化，提取的特征点效果也受到影响， Mur-Artal等人[4]提出的MR算法，对特征点分布有明显的提升，但阈值依然是人工设定的固定值，其在特征点提取的时候，对于没有检测出特征点的区域降低阈值提取，这大大增加提取的时间；丁等人[5]提出自适应阈值的FAST提取算法，采用动态的全局KSW熵和局部的灰度差提取特征点，改进后算法稳定性提高，但是算法时间却增加了一倍；保等人[6]提出通过滑动窗口的方式分割图像，计算每个窗口区域图像的信息熵，保留高信息熵的区域提取特征点，改进后的算法匹配精度提高0.3%，但效果不显著；因此本文给出了一种基于图像局部熵的自适应阈值方法。

信息熵是描述事务不确定性的度量，理论上讲，熵是信息无序程度的一种度量，在度量图像信息的不确定性的时候，熵值越大，无序度越高。在图像处理中，图像熵可以反映图像的信息丰富程度，它是一种特征的统计形式，反映了图像中平均信息量的多少，熵值越大，信息量越大。由于图像存在不同明暗变化区域，可以通过图像熵动态的确定阈值。

KSW熵算法是一种既简单而有效的阈值选择方法。它是利用灰度直方图近似估计目标熵和背景熵的两个信息之和最大值，以此得到最佳阈值。但是由于KSW熵获取最佳阈值时，目标熵和背景熵需要大量的运算时间，为了减少计算量，缩短寻找最佳阈值的时间，所以本文结合对图像划分网格的方法，在每一个图像块中求最佳阈值，具体过程如下：

(1)对图像块的直方图进行归一化，概率分布可表示为：

(11)

其中ni是灰度值为i的像素数量，N是图像块中像素总数。

(2)在图像块中计算像素概率分布最佳的熵值，计算如下：

(12)

其中H代表像素的熵值，pi是某个像素在该图像块中出现的概率，计算最佳熵值如下：

V=Max(H(K))

(13)

(3)其次，计算出图像块的灰度均值为：

(14)

其中MN代表图像块大小，I(i,j)代表在该图像中i,j处的灰度值。

(4)通过计算最佳阈值与灰度均值差的绝对值，动态获取局部图像的最佳阈值，通过校正参数σ调整阈值，则最终动态阈值为：

(15)

其中T为阈值，σ为校正参数，根据实验参数一般取0.8到1.

2.3 PROSAC特征点匹配

渐进样本一致性PROSAC是一种基于RANSAC改进的样本检验匹配方法。PROSAC算法的结构类似于RANSAC，基于这两种算法的随机采样，如图3所示样本收敛基本一致。RANSAC算法通过随机从数据集中抽取样本点，反复地选取样本数据去估计模型，直到迭代出较为好的模型，但没有考虑到样本之间的差异性，导致算法效率低，运算时间长，而PROSAC算法利用线性排序结构节省了大量的计算时间,与RANSAC相比快了几百倍。PROSAC算法样本并不是从所有数据中提取的，而是先对相似性较高的样本点进行排序，然后再从具有最高质量的数据子集中提取样本点，最后通过样本数据去估计模型。这样防止了由于随机抽取的离群值导致验证次数的增加，通过设置非随机性的最小值来减少重复次数，改善了处理时间，以便在完成足够的验证过程时可以减少重复的验证次数。

图3 RANSAC和PROSAC随机采样

2.4 改进ORB算法描述

基于ORB无人机图像快速拼接算法如表1所示：

表1 改进的ORB算法步骤及流程

3 实验结果及分析

本实验是在MacOS10.13.6操作系统上进行的，计算机CPU为i5-5257U，8G内存，本文算法基于C++编译完成，实验平台为Qt5和OpenCV3.4.2.实验数据采用senseFly提供公开的无人机航拍图像中的Industrial Estate数据EP0057、EP0058，如图4(a)所示，数据EP0028、EP0029，如图4(b)所示和中国永州无人机航拍图像数据DSC03373、DSC03374，如图4(c)所示，图像分辨率为1 024×682，格式为JPEG.为了验证本文提出改进的ORB算法，从实现数据中选择了重叠部分50%，80%和具有旋转的图像，分别与SIFT算法，SURF算法，AKAZE算法，ORB算法，和ORB-SLAM算法，SuperPoint算法进行比较；在无人机图像拼接过程中，实时性和稳定性是最重要的因素，所以本文从特征点提取速度，特征点匹配的正确率和匹配的精准度进行对比。

图4 实验数据

3.1 特征点提取时间

为了衡量特征点提取的速度，本文对参考图像和待拼接图像提取1 000个特征点，对比SIFT算法，SURF算法，AKAZE算法，ORB算法，和ORB-SLAM算法在特征点提取时间，时间越少，则提取特征点速度越快。如图5所示。

图5 特征点提取的时间

3.2 匹配正确率

为了衡量特征点提取的准确性，本文采用匹配正确率CMR(Correct matching rate)进行评估，检测两张图片所有特征点对，如果特征点对的描述子向量之间的距离低于所选择阈值，阈值一般设置为0.8，则该点对匹配，然后再用PROSAC对匹配的点对集进行精匹配。计算公式如下：

(16)

其中，CMR表示的是正确匹配点数与所有匹配点对数之比，即nc表示匹配正确点数，N为所有匹配点数，CMR值越大，表示匹配性能越好。表2，表3，表4分别为三个实验数据的特征点匹配的正确率。

表2 实验数据(a)特征点匹配的正确率

表3 实验数据(b)特征点匹配的正确率

表4 实验数据(c)特征点匹配的正确率

3.3 配准精准度

为了衡量两幅图像的配准精准度，本文采用均方根误差RMSE(Root mean square error)进行评估，计算公式如下：

(17)

表5 配准精准度比较

图6 图像拼接结果

4 结语

本文针对无人机图像拼接的实时性和稳定性，提出了一种基于四叉树的局部熵自适应阈值的ORB改进算法，本文首先对图像划分网格，在网格内使用局部熵计算局最佳阈值，再采用四叉树的方法均匀提取特征点，然后使用KNN算法对特征点进行粗匹配，再采用PROSAC算法对匹配的特征点进行精匹配，并且计算单应性矩阵对图像进行拼接，最后对拼接的接缝处使用加强平均算法进行融合，实验结果表明本文算法在保持ORB算法的特征点提取快优点的前提下，提高了ORB算法的匹配正确率，在配准精准度也拥有较好的表现，本文算法在与SIFT算法，SURF算法和AKAZE算法比较中，特征点提取速度具有绝对优势，与ORB算法和ORB-SLAM算法比较中，本文算法匹配的正确率有较好的提高，与SuperPoint深度学习的特征点提取的算法比较中，本文算法在特征点提取的时间和匹配的准确度都有较大的优势。