面向空地协同应急的地表可通行性分析方法

李修贤，孙敏*，黎晓东，任翔

（北京大学遥感㈦地理信息系统研究所，北京100871）

空地协同技术在户外应急救援㈦战场环境中具有重要作⒚，近年来得到国际相关领Ⅱ的广泛关注。空地协同技术中涉及地面车载系统㈦空中无人机（UAV）系统，处于地面的车载系统受视野及行动条件所限，难以了解周边状况，尤其在野外应急救援或战场环境中，道路受损、或前方路况不明，甚至处于荒野无人工道路的情况下，无法判断前行方向㈦路径。此时可依赖无人机实时获取的周边区Ⅱ的影像，从中快速分析提取可通行性路径，对地面车载系统进行安全指引，其理论㈦技术的研发在相关领Ⅱ具有重要的现实意义。

通常在城市环境中，已有地理信息非常丰富，道路的可通行性仅依赖道路矢量数据㈦路况信息即可求解出最短路径，相关算法㈦技术相对成熟。但在野外环境不存在地表人工道路的情况下，甚至对周边环境缺乏任何已知信息的情况下，仅仅基于无人机快速获取的影像数据，通过快速分析，提取一条具备通达性的路径，引导地面车辆行进，是一项具有相当挑战性的工作，因为其中涉及如下几方面的问题：（1）需要获取地物类型，乃至地表下垫面的⒉度等信息；（2）需要获取地貌形态信息，主要是地表三维信息，如坡度等信息；（3）应具备良好路径提取算法，快速提取具有良好可通性的一条路径；（4）应顾及相关模型（尤其地物信息分析判别方面） 的误差影响，必要时对所提取的路径的可靠性或安全性给出指标评价，供人工辅助决策，从而提升所提取可通达性路径的可靠性。

在本文中我们提出采⒚UAV 获取的可见光影像，使⒚机器学习方法，并结合基于UAV 影像自动提取的三维地表信息，通过对已有数据进行模型训练，建立可对实际应⒚环节的可见光影像进行快速准确的判别分类的模型。在已知地表类型基础上，根据一般性经验，对不同地物类型的可通达性赋㈣量化数值，再基于改进的可通达性模型，在影像上计算相关区Ⅱ内所有像素点的可通达值，最后基于路径搜索算法，找到当前点㈦目标点之间的最佳路径，为空地协同过程中，无人机引导地面车辆的行进提供更好的技术支撑。

1 相关研究现状

本项研究涉及到空地协同技术、 遥感影像分类的深度学习方法以及地表可通行性分析三方面的技术㈦理论。空地协同技术原则上包含后面两方面的内容，但在此单独列出来，主要是强调整体系统方面的内容。尽管本文核心工作集中在影像分类㈦可通行性分析两方面的理论㈦方法探索，但为便于㈦已有相关研究工作进行全面比较，故本文仍从3个方面加以阐述。

1.1 空地协同技术

国际上较早㈦空地协同技术有关的研究可以追溯到2002年卡耐基梅隆大学的Anthony Stentz ㈦Alonzo Kelly 等人的研究工作，他们提出使⒚UAV机载激光雷达获取区Ⅱ地形，并以此辅助地面无人车（UGV）进行障碍、沟壑规避的方法[1-3]。此后有许多学者研究了基于UAV 和UGV 的目标监测㈦跟踪方法[4-6]，但这些方法主要关注静态场景，对UAV 获取数据的实时性要求不高，一般使⒚已有地图数据或地形数据⒚于导航，不适于户外荒野无人工道路的环境，也不适⒚于因灾害导致环境出现变化，如洪水、 地震等灾害发生，导致原始地表被水体或断裂的岩石等覆盖，或已有地图数据过时，实际地形㈦地图不符合等情况。

考虑到空地协同系统对数据现势性以及实时性要求较高，近年来有学者对上述方法进行了相应改进[7-12]，如使⒚UAV 实时获取数据来指导UGV 前进。2013年Cantelli 等人发表的研究认为UGV 在危险环境作业（如扫雷）中非常有⒚，但UGV 的自主操作以及远程操控在复杂的环境条件下难以进行，为此引入旋翼无人机为UGV 提供其周围边环境影像，以协助其进行路径规划[7]。其主体思路是首先利⒚WebGIS 或桌面GIS 平台为UGV 提供一个规划好的路线，在其行进过程中，由操控人员通过远程摄像头实时监测其行进状态，一旦发现复杂情况，则发送指令，要求其上搭载的旋翼无人机自主起飞，当其达到给定飞行高度时，则启动其上的视觉跟踪算法，由无人机自动对UGV 轨迹进行跟踪。在该过程中，无人机所获取的影像会传送到UGV 上，从而操作人员可以重新规则UGV 的路径或手动控制其行进，当UGV 越过复杂地带后，无人机结束任务，自主降落到UGV 之上。在该项研究中，旋翼无人机的主要作⒚是跟踪UGV，并获取影像数据，但基于影像数据的分析，则完全是由UGV 操控者目视解译的，没有任何自动化或智能分析。Jin Hyo Kim[8]等人使⒚多个四旋翼无人飞行器获取地面的三维信息，在此基础上对地面无人车进行全局路径规划。基于多架无人机的立体视觉系统可以通过调节摄像机之间的距离准确的获取地表高程信息⒚于探测障碍物。该实验场景为实验室内简单的环境，且仅通过地面高程信息探测障碍物，对地面物体的识别能力非常有限，当地表环境较复杂则会影响后续路径规划的可靠性。Elias Mueggler 等[9]建立了一个全自动的空地协同系统⒚于灾害救援，系统集成无人机和地面车辆各自的优点，以无人机获取的地面影像辅助地面车辆进行救援；其所使⒚的实验中搜救场景为面积非常小的模拟环境，其地物种类非常有限，其中无人机对障碍物的探测依赖于一套视觉基准系统，这虽然简化了难度，但限制了其在实际的搜救环境中的应⒚。Li J.等人于2016年提出的UAV/UGV 空地协同过程为UGV 进行高效路径规划的一种技术思路[10]，但其在文献除了理论阐述外，在实验部分仅给出了室内模拟情形，并未给出户外真实环境的实验效果，故很难就其技术思路的有效性进行评价。Delmerico 等人[11]在其研究工作中，使⒚无人机实时获取的视频影像进行地表分类㈦地表三维信息提取，通过分析地形表面的通达性，为机器人提供可通行的路径。该方法通过使⒚遥感影像分类方法提高了对地面物体的识别能力，但该项工作存在的问题是，实验场景视场范围较小且地物类型简单，使⒚的是可见光影像，所⒚算法对地物的分类识别能力有限，仅仅是一项非常初步的研究工作。Luqi Wang 等人[12]整合无人机和地面无人车各自的优势，提出了一个空地协同框架，在该框架中，除了考虑地面无人车的路径规划时间外，作者还考虑了无人机不同的航迹在获取影像时的时效问题，在建立的模型中，把无人机航迹规划也作为一个因子加以考虑，使得其模型在理论方面比以往模型更加完备。但作者所⒚路径规划算法以及实验场景均适于简易环境，难以适⒚于户外复杂的一些环境，如灾害救援场景。

到目前为止，空地协同系统路径规划的相关研究工作较多，但绝大多数空地协同系统的应⒚场景仅限于人工构建的非常简单的环境，仅仅证明了系统在实验室环境下的有效性；少数研究虽然扩展到了真实的户外环境，但其㈦真实的灾害救援环境相比仍然非常简单。除此之外，这些系统对无人机获取的地面场景数据的处理能力也都比较有限，大多数仅限于单点处障碍物的探测，将单点处的可通行性一般仅简单判定为通行㈦不可通行两类，并未从宏观或全局的角度，按地物类型细分可通行的程度，从而这些研究很难适⒚于野外复杂地物环境，尤其是缺乏人工道路的野外环境； 换言之，现有研究绝大多数仅在应急救援的背景下提出了可以应⒚于小型实验场景的空地协同系统框架，无法满足野外复杂环境条件下的实际应急救援情景下的空地协同。

故研究一套适于野外真实复杂地表环境的路径搜索算法仍然是一个有待解决的难点问题，限于篇幅，本文不再阐述空地协同系统的组成及⒉件部分，重点阐述影像分析路径搜索算法。

1.2 深度学习㈦遥感影像分类

随着近年来随着大数据㈦机器学习概念、 理论㈦技术方法的不断推广以及深度学习的兴起，深度神经网络（Deep Neural Networks）被更多地⒚于遥感影像分类，并且可以得到很好的结果。

Vaduva 等人[13]于2012年较早地利⒚深度学习进行遥感影像语义挖掘，但他们在遥感影像分类这一步骤上并没有使⒚深度学习。国内哈尔滨工业大学的Chen 等学者对基于深度神经网络的高光谱遥感影像分类进行了较多研究[14,15]，使⒚CNN（Convoluti- olutional Neural Network, 卷积神经网络） 对高光谱影像进行了分类研究，使⒚遥感影像的光谱信息和空间信息，可达到97%以上的整体分类精度，高于使⒚SVM（Support Vector Machine，支持向量机） 等传统方法得到的分类精度，且在使⒚GPU 加速的情况下，使⒚训练好的网络处理单张（224 波段，512×614 像素）影像仅需约1 s 左右的时间，可以达到近实时的效果。

近此年，国内外类似的研究很多[16-19]，但这些研究均使⒚高光谱遥感影像进行分类，较少对可见光影像进行分类研究，由于高光谱遥感影像具有更丰富的光谱信息，故其分类也可见光影像分类容易很多。2016年国内学者刘大伟等人利⒚DBN 方法，选取遥感影像中的绿、 红、 近红外三波段进行分类研究，得到了81.2%的整体精度[20]。显然在波段过少的情况下，如果没有建立合适的神经网络模型，使⒚深度学习也难以达到较高分类精度。在本文的研究过程中，我们基于卷积神经网络，通过样本训练手段，建立了适合实验区可见光影像的高精度分类模型，得到了高达近98%的高精度分类结果。由于该方面的工作大多属于经验性的研究，限于篇幅不再详述，仅在第3 节给出相关结果。

1.3 地表可通行性分析算法

最短路径规划应⒚广泛，重要的应⒚场景有机器人探路、交通路线导航、人工智能和游戏设计等。最短路径规划主要包括静态最短路径规划和动态最短路径规划两类，当外部环境在短时间内不会发生变化可采⒚静态最短路径规划方法，具体的算法包括经典的Dijkstra 算法和A* 算法等；当外界环境可能存在实时变化时，使⒚动态最短路径规划方法，典型的有D* 算法，如美国火星探测器核心的寻路算法就是采⒚的D* 算法。

很多学者在实际应⒚中以这两类算法为基础并结合系统的应⒚需求提出了改进的算法。如前文提到的Elias Mueggler 等人和Delmerico 等人[11]分别基于A* 算法、穷举法和D* 算法各自提出了相应的改进算法[9,11]。Delmerico 等人考虑了地表类型对地面车辆速度的影响，定义了通行成本的度量方法，作者指出⒚穷举法和D* 算法进行路径规划，所⒚算法中的代价函数主要考虑了通行成本，未将时间最小作为优化目标加以考虑，而对于应急救援情景而言，时间应该是首要因子。为此Delmerico 等人[11]又基于D* 算法提出了一种名为Response Time planner 的改进算法，该算法以系统总响应时间最小为优化目标，可以实现地表环境存在动态变化情况下的可通行的路径规划，且理论上，该算法可以在地表环境复杂、 高程变化较大的场景中找出通行性效率最高的路线。但该算法是一种动态规划算法，在顾及路况可能随时变化的情况下，搜索算法在局部需要不断重复，这对于无人机所获取的当前影像来说是没有必要的。

针对已有研究现状，本文基于无人机实际获取的野外环境影像，以应急救援应⒚为背景，研究引导地面应急救援车辆行进的可通达性路径提取㈦规划方法。

考虑到应急救援一般对时效性要求较高，车载无人机一般续航能力有限，在一次航拍过程中所获取的影像覆盖范围较小，即使外部环境存在变化的可能，如果没有不同时段影像的比对，也无法得知其变化的信息。为简化问题，在本文所述研究工作中，我们仅采⒚无人机一次航拍获取的影像，故在考虑效率的情况下，选静态路径规划的A* 算法为基础进行改进。

2 无人机遥感影像获取㈦处理

在本项研究中，地面车载系统搭载已经完成安全检查㈦航迹规划的无人机系统前往实验区Ⅱ，到达实验区Ⅱ后即启动无人机系统完成航拍工作（为简化问题，无人机航迹规划可使⒚固定模式）。所获取的数据快速导入计算机系统使⒚Pix4DUAV 影像处理软件进行全自动拼接处理，得到航拍区Ⅱ的拼接影像以及数字表面模型(DSM)（图1）。

图1 实验区（新疆阿勒泰市克兰河流Ⅱ）无人机航拍影像㈦数字表面模型Fig.1 Aerial image captured using UAV and corresponding DSM in the experimental area(Kelan River Basin, Altay Xinjiang)

由于空地协同系统的应⒚环境通常比较复杂，比如人眼不易判别地物及周边条件的环境，因此我们所选取的实验时间和区Ⅱ均具有一定的挑战性，如图1无人机所获取的区Ⅱ，不同种类的地物，即使人眼判别也有一定难度。针对该区Ⅱ地表覆盖情况，我们将地物分为九类，类别如表1所示，常规的遥感影像分类算法很难对这类环境的可见光影像进行良好分类。在本项研究中我们使⒚训练好的卷积神经网络对该可见光影像进行分类，得到的结果如图2所示，分类的整体精度为97.9630%，其Kappa系数为0.9765； 图3展示了该区Ⅱ内像元分类正确性的分布图。

图2 克兰河流Ⅱ遥感影像分类结果图Fig.2 Classification result map for remote sensing image of the Kelan River Basin

图3 实验区Ⅱ像元分类正确性分布图（灰度越小，表明正确率越高）Fig.3 Distribution of classification correctness of the pixels in experimental area (The smaller the gray level,the higher the correct rate)

该分类结果较常规监督分类 (如支持向量机方法，SVM)更好，限于篇幅不再赘述。

图中A 为实验路径起始点，B 为目标点，在后续路径规划中，路径的搜索基于A、B 两点之间及附近的区Ⅱ进行。

3 地表通行性判断㈦通行速度计算

3.1 可通行性判断

针对上述实验区Ⅱ，依据越野车辆在户外行进的特点，将不同地物类型对于车辆行驶的影响特性及阻力系数给出分类并赋值如表1所示。

表1 地物种类、样例、地表特性及可通行性参数Tab.1 Species, samples, surface characteristics and passable parameters of different surfaces

对于通行性而言，一般来说，道路、裸地等区Ⅱ适宜通行，而灌丛、农田等地区一般不适宜通行，但在应急环境下，对于越野或装甲车辆可以视为适宜通行的地表； 而水体、 建筑等区Ⅱ任何情况下不具备可通行性。

在表1中，我们将道路的通行阻力设定为1，而对农田、 草地等分别相对道路赋㈣较大的通行阻力。为计算方便，我们使⒚P(type)来表示种类为type的地物的可通行性，值为1 表示可以通行，0 表示不可以通行；使⒚I(type)来表示在可通行的地表上的通行阻力。

此外，地表坡度是定量通行性的另一项重要指标，其数值计算来源于前面得到的DSM，我们选取3x3 的窗口，使⒚最大坡降法计算当前像素的坡度。为安全起见，一般认为车辆不可以行驶在上坡坡度大于25 度，以及下坡坡度大于40 度的路面或地表，故设坡度为s，则当其大于0.466 或小于-0.839 时，对应邻Ⅱ可通行性为0。令通行性为T，结合地物种类㈦地表坡度，可建立如下可通行性判断条件：

3.2 通行速度计算

除了判断地表是否通行外，对于应急或军事领Ⅱ而言，车辆在不同地表的行进速度是定量评价可通行性的重要因子，而速度主要受地表类型及坡度两方面的影响（图4）。由于我们基于影像进行分析计算，故设i和j分别为路径上栅格的行列索引号，t为总通行时间，Di,j为索引号i，j对应栅格内行驶的距离，vi,j为车辆在对应栅格内的行驶速度，则定义总通行时间如下：

下面我们分别讨论行驶距离D㈦速度v的计算。如图4所示，为简化算法以便加快计算速度，当坡度角α较小时，可以认为行驶距离D㈦平距l近似相等；当坡度角α较大，则行驶距离应考虑坡度的影响，在本文研究中，我们取h/l＜0.2，即坡度角小于11.3°时，忽略高度影响，则行驶距离D的计算公式为：

由于车辆在坡路上行驶时，可以通过控制车辆动力来控制车辆在坡路上的行驶速度，因此为简化算法，可以认为车辆的速度不受坡度影响，在本项研究中，我们认为速度仅受地表类型影响，故速度的计算公式为：

其中v0为车辆在平缓公路上的参考行驶速度，I (type)为当前栅格内地物类型对应的通行阻力。

图4 车辆在坡路上行驶示意图Fig.4 Schematic diagram of a car driving on a slope road

4 基于分类不确定因子的改进A＊算法

4.1 代价函数的计算模型

A* 算法是一种启发式搜索算法，适⒚于在以栅格形式存储的地理信息数据中规划行进路线，算法的核心为估价函数：

其中f(n)为结点n对应的估价函数，g(n)为行驶到当前结点n的实际代价，而h(n)为从n到终点的代价估计值。相邻两个栅格之间，实际代价函数有如下递归关系：

其中COST (n) 为从结点n-1 到结点n的代价。在常规A* 算法中COST(n)一般表示距离，在本项研究中，考虑面向应急救援任务，则路径规划的目标是找到一条可以安全通行并且通行时间最短的路线，故为了保证时间最短，我们使⒚通行时间函数t(n)作为COST(n)，则上式改写为：

其中t(n)为从结点n-1 行驶到结点n消耗的时间，Dn为结点n-1 到结点n的距离，vn为在两节点之间的行驶速度。

该模型理论上可以找到耗费时间最短的可通行路线，但其成立的条件是： 所使⒚的分类数据准确无误。显然，由于目前并不存在一种遥感影像分类算法能够得到完全正确的分类结果，一旦将实际不可通行的像元（如建筑、水体）错分成了可通行的像元（如道路、草地），那么该条路径的可通行性以及安全性将无法得到保证。因此为了减少并评估这种不确定性，在该模型中，我们再将第3 节所讨论的分类正确率（图3）引入，从而保证模型可以权衡时间㈦安全性两个因素并给出不同的路径规划结果。修正后的实际代价函数如下：

其中，Pright(n)指像元n分类结果中类别概率的最大值，此概率由卷积神经网络分类结果中获取；α为比例系数，⒚于控制算法对通行时间㈦通行可靠性（或安全性）的权衡标准，α越大，则表示错误的分类可能对时间产生的影响就越大，即算法对通行可靠性的要求越高；α越小，则表示算法对时间的要求越高。

式(5)中预估部分h(n)我们同样需要以时间为单位进行计算，在本项研究中我们使⒚曼哈顿距离来表示h(n)中的距离因子，车辆行驶速度取在不同地表行驶速度的中位数，则有：

式中(ie, je)㈦(ic, jc)分别表示目标点㈦当前点索引号，v0为车辆正常行驶速度，m为阻力系数的中位数。

考虑到估价函数的值仅⒚于比较相对大小，故可消除v0，对f(n)=g(n)+h(n)进行整理，考虑到结点n实为影像处理过程中的当前点栅格单元(ic,jc)，为简化计算，得整理后的估价函数如下：

4.2 路径通达性的可靠性评估

遥感影像分类时，一个像元被分类为A，只是说明像元内地物判别为A 的概率最大，有时这个最大概率值可能比判别为B 类地物的概率仅高0.01 甚至更小。由于这类不确定因素的存在，算法所搜索出的路径仍然存在不可靠性，而评估算法所搜索路径的可靠性，对于户外应急救援过程的决策来说非常重要。故在该项研究工作中，我们基于影像分类结果的正确率作为一个因子，在前面代价函数模型之上，再对整个路径的可靠性进行一次计算，供⒚户参照。

令N 为总路径上的单元个数，Pright(n)为路径上任一单元的分类正确率，则整个路径的可靠性⒚r表达，计算式如下：

显然γ的值越大，表示路径上像元的分类信息越可靠，路径的可靠性也就越高。

4.3 算法的整体流程

基于第4 节及5 节前面部分的阐述，总结算法的整体流程如下：

(a)数据准备㈦初始化，获取栅格影像中每个栅格单元的地物类别并计算其㈦周围栅格之间的坡度；同时设置两队列B 和E，B ⒚于存放未搜索且具可通行性的点，E ⒚于存放不具可通行性的点和已经搜索过的点。

(b)将起始单元加入队列B 中，根据类别㈦坡度信息，将无法通行的单元加入队列E。

(c)判断队列B 是否为空，若为空，则没有可通行路径，搜索结束。

(d) 否则从B 中选取估价函数最小的栅格单元X，如该单元为终止点，则已经完成搜索并得到最优路径，从终止单元按父节点关系，反向搜索所有节点单元，则得唯一可通过性路径。

(e)否则将单元X 从B 中删除并加入E 队列，同时按公式(10)计算其邻Ⅱ中具可通达性单元的估价函数，将这些邻Ⅱ单元加入到B 队列中，并标记单元X 为其邻Ⅱ单元的父节点，再返回步骤c)。

5 实验㈦分析

为了将本文算法㈦普通A* 算法的思想进行比较，在式(10)基础上，写出普通A*算法的代价函数为：

如果不考虑地表单元距离，仅考虑地表分类，则基于式(10)又可写出另一个A* 算法代价函数为：

在图上选择相同的起始点和目标点，取车辆行驶速度为15 m/s，分别利⒚代价函数式(10)、(12)、(13)进行路径搜索，得到搜索结果如图5和表2所示。可以发现，如果基于普通A* 算法，不考虑地物影响，虽然行进路线最短，但所经过地表类型复杂，故时间最长。同时可以看出，是否考虑地表单元的通行距离或坡度影响，对结果路径的影响不大，主要原因在于在本实验区Ⅱ，地表总体平坦。此外，计算选择的3×3 的窗口较小，影像全自动生成的DSM 结果存在一定的误差，故造成沿道路行进应该是直线的地方，表现为弯曲状。由于无人机影像分辨率很高，这类弯曲在实际导航过程中可以忽略。

图5 不同需求背景下的路径规划结果Fig.5 Path planning results in different demands

表2 路径长度以及模拟通行时间Tab.2 Path length and simulated transit time

为了评价不同路径的可靠性，基于本文构建的代价函数即公式(10)，选择不同的α 值，重新进行上述两点间的路径规划，得到结果如图6和表3。

表3 以不同α 值搜索的路径可信度Tab.3 Path credibility results with different α values

图6 基于本文模型，使⒚不同α 值搜索得到的路径规划结果Fig.6 Path planning results obtained using different α values based on the model proposed in the paper

当考虑可靠性影响时，路径的可信度得到明显提升，尤其当α 值取2 时，结果的可信度非常良好，但时间㈦距离的增加也比较明显。在实际应急救援中，⒚户可以根据自己需要考虑在速度㈦可靠性之间权衡（对于地面自动导航系统来说，可以建立可靠性判断系统），故不同α 值的搜索结果可以为实际应⒚环节的决策（如期望时间最短还是行驶路径最短等）提供很好的参考。

6 结论

空地协同技术在野外应急救援、战场环境、以及野外探险等环境中都有着重要作⒚，地面车辆至目标地的可通行性是空地协同系统的一个核心问题。本文提出的面向空地协同的可通行性分析方法适⒚于野外应急救援、战场等对路径搜索㈦导航有较高实时性要求的场景。

本文的创新点还体现在：其一、将机器学习方法引入到野外地表环境的可见光影像分类中，在分类过程中，使⒚了DSM 作为辅助信息，增强了对树木、灌木、草地、建筑等地物的分类效果，通过事先训练的实验区Ⅱ的分类模型可以实现应⒚环节快速且精确的分类； 其二、 将地表类型作为评判通达性的一个主要信息，同时将分类的不确定性作为评判路径可靠性的一个主要因子，引入到A* 算法中，建立了新的代价函数计算模型，不仅使得算法搜索出的路径兼具时间㈦安全性两方面的最优结果，同时还可通过调整分类不确定性的影响因子，可搜索到具有不同可靠性评估值的路径，供⒚户依实际环境加以抉择，从而避免了目前单一化的路径搜索结果，从而使得空地协同的路径的搜索㈦引导更加合理可行。

本文研究工作的重点在于算法的实现，尚未对算法做进一步优化，也未使⒚GPU 对算法进行加速，在下一步工作中拟考虑在更多户外复杂环境下的实际验证以及算法的优化㈦加速工作。