王玉茜，张雪涛，闫 飞，庄 严,

（1.大连理工大学控制科学与工程学院，大连 116024；2.大连理工大学人工智能学院，大连 116024）

1 引 言

近年来，随着人类在人工智能、地图构建、图像处理等领域取得突破性的科技进展，无人机和地面机器人也得到了迅速发展，二者各有利弊。一方面，无人机具有较广的观察视角，但其有效载荷低、续航时间有限；另一方面，地面机器人的视角受限制，但其有效载荷高、续航时间长[1]。如果利用无人机进行环境探索，从而引导地面机器人更快地完成作业任务，即空地协作，吸引了诸多学者研究[2-6]。文献[7]提出了一种基于鸟瞰图导航地面机器人的概念证明。文献[8]利用无人机空中建图，进而驱动地面机器人进行避障和路径规划。空地协作可以拓宽地面机器人的有限视场[9-10]，可以用于虚拟现实[11]、多机器人监控[12-13]、协同作战[14]。而如何利用无人机对地面环境建图是空地协作领域发展的一个关键问题。

本文目标是使用无人机生成可供地面机器人使用的室外大范围拓扑地图。为此，本文提出了一种基于道路分割、图像拼接和骨架提取的大范围拓扑地图构建方法，其中，图像拼接技术可实现室外大范围场景的获取，道路分割和骨架提取可实现拓扑地图的构建。

为实现拓扑化地图的构建，首先需要无人机对地面道路的准确观测，即对场景中的道路进行准确分割。在道路分割领域，基于航拍图像的道路检测技术的应用范围越来越广，道路识别也得到广泛研究。文献[15]基于视觉对车道线和道路边界进行检测，同时运用基于蒙特卡罗方法的置信度评价方法对待测图像进行处理。该算法能够有效地克服道路环境不佳的影响，并且计算耗时较小。然而，该算法仅适用于与环境背景特征相差较大的道路目标检测，很难适用于背景环境复杂的无人机航拍图像。文献[16]提出了基于启发式搜索连接的航拍图像直线检测方法，首先对图像进行高斯滤波和边缘检测，然后利用启发式搜索连接，提取出符合道路直线模型的直线，最终获得检测结果。该算法实现简单并具有良好的抗噪性能。文献[17]提出了基于霍夫变换的航拍图像道路检测，霍夫直线检测作为直线提取的经典算法，广泛应用于直线检测领域。文献[18]针对道路颜色与周围环境颜色存在明显区别的情况，提出了基于颜色识别的道路检测，但航拍图像受屋顶、树木阴影、车辆等影响较大，不适合应用此方法。随着深度学习的发展，出现了多种基于神经网络[19-20]的航拍图像道路提取方法，主要分为两类：一类追求图像分割的准确性，牺牲了时间；另一类则以快速为主，降低了准确性。为了兼顾时间与准确性，本文采用时间与准确性均衡的D-LinkNet 语义分割神经网络[21]。

其次，通过图像拼接实现大范围场景的获取，在图像拼接领域，Szeliski 提出了包含相机三维旋转运动的图像拼接技术，该方法首先求解透视矩阵，然后求解单应性矩阵的参数，调整焦距和旋转矩阵以消除累积误差，最后采用加权融合的方法将拼接图像合成到一起。Brown 等[22-23]使用基于不变局部特征的物体识别技术来选择匹配图像，实现了无序图像的全自动拼接，取得了较好的拼接效果。然而，当图像数目较多时，边缘图像会发生畸变。为了解决这个缺陷，Gao 等[24]将场景划分为背景平面和前景平面，用两个单应性矩阵分别对齐背景和前景，进而无缝拼接大部分现实场景。随后，文献[25]采用网格优化的方法来解决图像拼接问题，从形状矫正的角度出发，借鉴图像缩放的Shape-Preserving 类方法，非重叠区域逐渐过渡到全局相似变换，并对整个图像 增加相似变换约束，矫正拼接图像的畸变，减小了投影失真。Lowe[26-27]提出了尺度不变特征变换（Scale-Invariant Feature Transform, SIFT）算法，其具有尺度不变性，可在图像中检测出关键点，对于光线、噪声、微视角改变的容忍度也相当高，但SIFT 算法计算量大，匹配速度较慢。因此，Bay 等[28]提出了快速鲁棒特征（Speeded Up Robust Features, SURF）算法，它是SIFT 算法的加速版，其性能可与SIFT 相媲美，且比SIFT 快三倍。SURF 善于处理模糊和旋转的图像，但不擅长处理视点变化和照明变化。为解决SIFT 特征的高昂计算代价以及对噪声敏感的弱点，Rublee 等[29]提出了特征提取算法（Oriented FAST and Rotated BRIEF，ORB），该算法基于FAST 和BRIEF 特征提出了二值特征，大大减少了计算量，提高了匹配速度，实验表明，ORB 算法在时间上比SIFT 快100 倍，比SURF 快10 倍，并且匹配效果也较好。在道路分割后进行图像拼接，可减少拼接时提取特征点的数量，大大减少了匹配拼接的计算量。除此之外，为了进一步提高匹配速度，本文设计了基于GPU 加速的ORB 图像拼接算法，可以兼顾实时性与准确性。

最后，关于地图构建，目前的地图表示方法分为三类：栅格地图、几何地图和拓扑地图[30]。其中，拓扑地图将环境表示为一张拓扑意义的图，图中的节点对应环境中的拐点或交叉点，弧表示不同节点之间的通道，适合于表示大规模环境。为完成拓扑地图的构建，需要对道路分割后的大范围场景进行骨架提取。一类方法是通过对所有道路线段求交来建立道路拓扑，但是在确定道路是否相交时难以选择阈值。与此不同，用骨架表示目标图像的连接拓扑和边界信息，在机器人领域有着广泛的应用。图像骨架提取，即提取目标在图像上的中心像素轮廓，以目标中心为准，对目标进行细化，细化后的目标为单像素宽度。中轴线是一个典型的骨架模型，其具有简单、完整等优点。在此基础上，研究人员提出了一系列基于细化的骨架提取算法，其大致可分为迭代和非迭代两大类。在迭代算法中，又分为并行迭代和顺序迭代两种。Saeed 等[31]提出的K3M 算法则是顺序迭代中应用广泛的方法之一，该类算法的思想是，假定从二值图像中物体的边界处同时开始燃烧，物体就会被逐步细化，但在燃烧过程中要保证满足一定条件的点被保留或者被“烧掉”，以确定燃烧结束后，剩下最后一个像素宽度的图像为图像的骨架。该方法存在像素冗余问题，得到的骨架出现分叉、不平滑现象。并行迭代以Zhang并行快速细化算法最为经典，该算法多应用于文字骨架的提取，在连接性和轮廓噪声抗扰度方面效果较好。本文使用骨架提取的方法进行拓扑化，将Zhang 并行快速细化算法应用于拓扑地图的构建。

为了实现室外大范围拓扑地图构建，本文提出了基于道路识别、图像拼接、骨架提取集成的拓扑地图构建框架。具体而言，先由图像拼接实现大范围场景获取，然后通过道路识别和骨架提取实现拓扑地图构建。由于所提策略先分割后拼接，实现了方法的实时性。此外，设计了基于GPU加速的ORB 图像拼接算法，提高了拼接效率。

2 大范围拓扑地图构建方案

2.1 整体方案设计

本文的整体设计方案可分为三部分：道路分割、图像拼接、拓扑构建，采用边分割边拼接、先分割后拼接的方案，前者可减少同时参与拼接的图像数目，增加拼接准确性，后者可减少拼接时特征点检测与匹配的计算量，增加拼接速度，流程图如图1 所示。

图1 整体方案流程图Fig.1 Flow chart of the general scheme

2.2 基于深度学习的航拍图像道路分割

道路系统是一个非常复杂的系统，其主要特点是连接特性和宽度特征，传统的道路检测的方法包括基于启发式搜索连接的直线检测方法[15]、基于霍夫变换的直线检测[16]、基于颜色分割的道路检测[17]等。但是航拍图像中的道路极易受到非道路因素的干扰，如阴影、车辆、与道路连通的开放区域（如小型停车场、篮球场）等，这些干扰不可避免，且将直接影响道路的连接特性和宽度特征。为了提高道路分割的准确性，选用D-LinkNet 语义分割神经网络对道路进行分割。D-LinkNet 网络包含编码器、中心部分、解码器三部分，组成结构如图2 所示。

D-LinkNet 使用ResNet34 作为网络的编码器，编码模块由最大池化层和若干残差块组成，四个编码模块依次分别具有3、4、6、3 个残差块。单个残差块如图3 所示，在普通卷积的基础上增加恒等映射，可以有效解决随着卷积神经网络深度的增加而出现的训练误差增大的问题。激活函数选用非线性函数ReLU，残差块输出可表示为

图2 D-LinkNet 结构图Fig.2 Structure chart of D-LinkNet

图3 单个残差块Fig.3 Single residual block

当输入、输出维度发生变化时，需要在恒等映射过程中对x做线性变换Ws，相当于加入了1×1 卷积层，如下：

在深度网络中为了增加感受野且降低计算量，通常会进行降采样，这样虽然可以增加感受野，但会使得空间分辨率降低，而空洞卷积的出现，巧妙地解决了这一问题。空洞卷积是一种功能强大的内核，可用于调整特征图的感受野而不降低特征图的分辨率，使得整个网络识别能力更强、接收域更大、融合多尺度信息，广泛应用于图像分割、识别任务中。中心层部分由空洞卷积层组成，空洞卷积如图4 所示。

图4 膨胀系数r = 2 的空洞卷积Fig.4 Dilated convolution with r = 2

假设空洞卷积的卷积核大小为k，膨胀系数为r，则其等效卷积核k′为

当前层感受野Ri计算公式如下：

其中，Ri-1表示上一层感受野，Si-1表示之前所有层步长之积。

D-LinkNet 中心部分的空洞卷积层结合级联模式和并行模式，可以灵活调整特征图的感受野，且每个路径的感受野不同，可以有效地融合多尺度特征。其结构如图5 所示，当堆叠的空洞卷积层膨胀系数r分别为1、2、4、8 时，每层的感受野一次为3、7、15、31。

图5 中心部分结构图Fig.5 Diagram of central part

道路分割是一个二分类问题，训练模型时，损失函数采用Dice 损失和二值交叉熵损失结合的方式。Dice 损失大多用于样本极度不均衡的情况，一般情况下使用Dice 损失会对反向传播有不利的影响，使得训练不稳定，因此，选用二值交叉熵损失函数与Dice 损失相结合的方式进行损失计算。

其中，yi表示样本i真实标签类别，pi表示样本i预测输出类别。

D-LinkNet 是一种高效的语义分段神经网络，它具有跳接、残差块、空洞卷积和编码器-解码器体系结构的优势，在计算和存储方面非常有效。

2.3 基于ORB 算法的图像拼接

无人机航拍受飞行高度、摄像头视角范围、焦距等因素的影响，单张图像涵盖的室外场景范围较小，为获得室外大范围图像，需要拍摄多幅图像，通过图像拼接技术，把各幅图像间重叠的部分进行提取、匹配、拼接，从而得到大范围室外场景。图像拼接算法结构如图6 所示，主要包含图像特征点提取与匹配、图像配准、图像融合三部分，其中，特征点提取与匹配、图像配准两步实现了基于GPU 的CUDA 并行加速处理。

图6 图像拼接算法结构图Fig.6 Diagram of image stitching algorithm

ORB 是一种快速特征点提取和描述的算法，分为两部分，分别是特征点提取和特征点描述。特征点提取是由FAST 算法发展来的，特征点描述是根据BRIEF 特征描述算法改进的。ORB 特征是将FAST 特征点的检测方法与BRIEF 特征描述子结合起来，并在它们原来的基础上做了改进与优化。

图像的特征点可以理解为图像中比较显著的点，如物体轮廓点、亮度变化分界点等。ORB 首先采用FAST 算法来检测特征点，FAST 算法是公认的最快的特征点提取方法。选取图像中某一像素为特征点，检测该候选特征点周围一圈的像素值，如果候选点周围领域内有足够多的像素点与该候选点的灰度值差别够大，则认为该候选点为一个特征点。在使用FAST 提取出特征点之后，给其定义一个特征点方向，以此来实现特征点的旋转不变性，称为oFAST 算法，ORB 算法提出使用矩法来确定FAST 特征点的方向。即通过矩来计算某特征点周围的图像区块p内的质心，该特征点坐标到质心形成一个向量作为该特征点的方向。对图像求质心时，每个像素点的值即该处的密度，利用图像零阶矩和一阶矩可求得图像质心，矩定义如下：

其中，(u,v)是特征邻域内的点，I(u,v)为图像灰度表达式。该矩的质心为

假设特征点坐标为O，则向量即为该特征点的方向：

得到特征点后需要以某种方式描述这些特征点的属性。这些属性的输出称为该特征点的描述子。ORB 采用BRIEF 算法来计算一个特征点的描述子。该算法的核心思想是在某特征点周围的图像区块p内，选取n对点对，把这n对点对的比较结果组合起来作为描述子。因此，BRIEF 描述子的输出结果是一个二进制串的特征描述符。一个二值测试τ定义如下：

其中，像素x与像素y组成一对点对，p(x)、p(y)分别表示图像区块p内像素x和像素y的灰度值。

BRIEF 描述子选取点对的时候，是以当前特征点为原点，以水平方向为X轴，以垂直方向为Y轴建立坐标系。当图片发生旋转时，坐标系不变，同样的取点方法取出来的点却不一样，计算得到的描述子也不一样，所以BRIEF 描述子不具备旋转不变性。ORB 算法对BRIEF 描述子的这一缺点进行了改进，改进后的方法改变了坐标系的建立方式，以特征点为圆心，以特征点和选取区域质心的连线为X轴建立平面坐标系，即利用oFAST 中求出的特征点的主方向θ，对特征点邻域进行旋转，改进后的算法称为Steer BREIF 算法。假设在某一特征点的邻域内选取n对点集，用S表示，则

其中，Rθ表示旋转矩阵，Sθ表示旋转后的点对位置。

BRIEF 描述子的一个优秀特性为点对均值稳定，方差大，区分性强，那么不同特征点的描述子就表现出的差异性越大，对匹配来说不容易误配。但是当 BRIEF 沿着特征点的方向调整为Steered BRIEF 时，均值就漂移到一个更加分散式的模式，且方差变小，区分性降低，此时选取点对时就不能随机选取，需要经过比较选取出区分度大、关联程度低的点对。ORB 算法的最后一步为特征点的匹配，当两个描述子的相似度达到一定阈值时，可认为这两个描述子代表的是同一个特征点。

图像配准是一种确定待拼接图像间的重叠区域以及重叠位置的技术，通过匹配点对构建图像序列之间的变换矩阵，将两张图像转换为同一坐标下，RANSAC 算法对于图像变换矩阵的求解与精炼有较好的效果。RANSAC 算法首先随机地选择两个点，通过这两个点确定一条直线，并称在这条直线的一定范围内的点为这条直线的支撑。这样的随机选择重复数次后，具有最大支撑集的直线被确认为是样本点集的拟合。

在特征点提取与匹配和图像配准过程中，提取大量特征点，并完成大量描述子计算与匹配的数学计算，是图像拼接程序耗时长、效率低的主要原因。由于显卡具有优秀的并行计算能力，为有效提高拼接效率，本文充分利用显卡进行并行加速计算，大大提高了算法的运行速度。

根据配准时得到的变换矩阵，可以对相应图像进行变换以确定图像间的重叠区域，并将待融合图像映射到一幅新的空白图像中形成拼接图。若两幅待拼接图像之间亮度、饱和度存在差异，则会导致拼接后的图像缝合线两端出现明显的明暗变化，此时，可采用加权平滑算法处理，即图像重叠区域中像素点的灰度值由两幅图像中对应点的灰度值加权平均得到。

其中，Pixel_L和Pixel_R分别为两幅待拼接图像中对应点的灰度值，k为加权系数。

2.4 基于骨架提取的拓扑地图构建

拓扑地图由边和节点构成，用来表示道路的连通关系，使用骨架提取算法实现拓扑化，构建出道路的拓扑地图。骨架可理解为物体的中轴，骨架提取流程图如图7 所示。

图7 骨架提取流程图Fig.7 Flow chart of skeleton extraction

骨架提取主要包括以下步骤：首先，图像细化。细化就是经过层层剥离，从原图像中去掉一些点，但仍要保持原来的形状，直到得到图像的骨架。其次，过滤。过滤使得任意两骨架点不能紧靠在一起，两点之间至少间隔一个空白元素。最后，检测端点和交叉点。端点和交叉点即拓扑地图中的节点，骨架即边。

选用经典的Zhang 并行快速细化算法，将输入图像二值化后选取其中某一像素点P1及其周围相邻8 个像素点，按图8 所示顺序标号。

图8 像素排列示意图Fig.8 A schematic view of the pixel arrangement

对图像中的每个点进行遍历，对每个像素为1 的点进行检测，若符合以下条件1、2，且符合条件3、4 之一，则非骨架点，删除该点。

条件1：2≤N(P1) ≤ 6，其中N(P1)为P1的8个邻域中黑色像素的数目。

条件2：A(P1) = 1，其中A(P1)指的是邻域像素按顺序排列时像素值由0 变1 的次数。

条件3：P2×P4×P6= 0且P4×P6×P8= 0或者P2×P4×P8= 0且P2×P6×P8= 0。

条件4：P2×P4×P8= 0且P2×P6×P8= 0。

过滤部分实现每两个白点之间不能紧靠在一起，即两个点之间至少隔一个空白像素，若满足P2+P3+P8+P9≥ 1，则删除P1。检测端点与交叉点部分首先需要确定卷积邻域范围，然后统计卷积范围内像素为1 的点的个数，若个数高于给定阈值，则说明P1为交叉点，反之则为端点。图9为图像中部分像素排列情况。

图9 部分像素排列情况Fig.9 Arrangement of partial pixel

3 实验结果及分析

为证明本文方案的有效性，在马萨诸塞州道路数据集上进行验证。首先，使用图像标注工具labelme 对数据集中道路部分进行标记，制作出用于训练及验证的数据集，并完成对D-LinkNet 网络的训练。所作数据集共5300 幅图像，其中80%用于训练，20%用于测试，该部分基于NVIDIA GTX1080 显卡配置下完成。其次，创建一个用于发送图像的ROS 节点，而后进行道路分割，每完成一幅图像的分割，便由ROS 节点发出该分割后的图像，直至处理完全部图像。图10 给出了两种不同场景下32 幅图像的道路分割结果，单幅图像程序运行时间约0.17 s，分割准确率达92.89%，具有较高的准确率与场景适应性。

图10 道路分割结果Fig.10 Result of the road segmentation

在图像拼接部分，首先创建一个新的ROS 节点，用于接收道路分割后发送的图像，当图像数量达到两幅即进行拼接，直到节点接收不到新的图像消息。

图像拼接采用基于GPU 的CUDA 并行加速方法，CUDA 处理图像的时候，首先需要把Mat图像上载到CUDA 数据单元GpuMat 对象中，然后对特征点提取及图像配准进行并行处理，处理完成之后，再从GpuMat 下载数据到原始Mat 对象中，完成后续图像融合操作。

本文比较了SURF 拼接算法、ORB 拼接算法以及GPU 加速后的ORB 算法的拼接耗时，各图像拼接算法运行时间对比如表1 所示。

表1 三种拼接算法时间对比Table 1 Time comparison of three stitching algorithms

其中，SURF 拼接算法选取特征点的条件与ORB 算法不同，其提取的特征点个数远大于ORB算法，因此SURF 算法在三种算法的比较中效率最低、耗时最长，ORB 算法效率居中，经GPU并行加速后的ORB 算法效率更高、耗时更短。

四种不同场景下的图像拼接与道路拓扑化结果如图11~12 所示，由此可见，本文方法在多种不同场景中具有较好的适应性与准确性。

图11 图像拼接结果Fig.11 Result of the image stitching

4 结 论

本文针对空地协作领域无人机室外道路观测问题，提出了由道路分割、图像拼接、骨架提取组成的基于视觉的无人机大范围室外道路拓扑地图的构建方法。首先，成功地将基于D-LinkNet的航拍图像道路分割和Zhang 并行快速细化算法 用于室外大范围拓扑地图构建问题；其次，提出先分割后拼接的方案，大大减少了图像拼接计算量，设计了基于GPU 加速的ORB 拼接算法，提高了拼接效率；最后，在INRIA aerial image 数据集上成功验证了该方法的准确性和实时性。

图12 道路拓扑化结果Fig.12 Result of the road topology