基于视点可重建性约束的最短航线规划方法

Shortest Route Planning Method Based on View Reconstructability Constraint

摘要

无人机航拍图像三维重建是目前获取高质量三维模型的重要手段。现有无人机航拍任务规划方法生成的航线简单、航拍视角固定导致图像对景物覆盖程度不够高，制约三维模型建模质量。为了得到高质量三维模型，提出一种基于视点可重建性约束的最短航线规划方法。该方法首先基于先验模型生成候选视点集合，其次以可重建度为约束采用下山单纯形法优化视点，最后将最短航线问题转化为旅行商问题进行求解。实验结果表明，该航线规划方法能够提高图像对景物的覆盖程度，显著改善目标场景的重建效果。以可重建性为约束条件设计无人机最短航线，可以提高影像三维重建质量。

Abstract

Three dimensional (3D) reconstruction of unmanned aerial vehicle (UAV) aerial images is an important means to obtain high quality 3D models. In the existing UAV aerial photography task planning methods, generate simple the routes are generated simply and the aerial photography angle is fixed, which lead to insufficient coverage of the image, thus restricting 3D modeling quality. To obtain high quality 3D model, a shortest route planning method based on view reconstructability constraint is proposed. The candidate viewpoint set is firstly generated based on the prior model by using the methed. Then the viewpoint is optimized by using the downhill simplex method constrained by reconstructability. Finally the shortest route istransformed into the traveling salesman problem to be solved. The experimental results show that this route planning method can improve the coverage degree of the image to the scene and significantly improve the reconstruction effect of the target scene. The quality of 3D image reconstruction can be improved by designing the shortest route of UAV with the constraint of reconstructability.

Graphical abstract

关键词

无人机 / 三维重建 / 可重建性 / 航线规划

Key words

UAV / 3D reconstruction / reconstructability / route planning

0 引言

随着无人机技术的快速发展，无人机应用于大规模三维场景重建^[1]，可以实现按照航线飞行采集数据，进行图像三维重建得到三维模型，推动了无人机摄影测量^[2-5]的发展。

目前常用的无人机航线规划方法是使用商业化规划软件进行航线规划，一般利用平面、斜面、包围盒等几何形状作为目标区域景物的先验场景，在拍摄过程中相机视角通常是固定的。在城市建筑等相对复杂的场景中，现有航线规划工具难以实现从不同角度对景物表面各个位置的覆盖拍摄，常常是在完成后续图像三维重建后才发现景物三维模型表面存在空洞或者采样不足等问题，不得不进行补充飞行，制约了整个流程的作业效率和成果质量。因此，在飞行前就规划好高质量的视点与路径具有重要作用。

文献[6]选择具有良好视差关系的视点并采集图像，实现了根据少数图像重建得到高质量三维重建模型，表明了视点选择的重要性。文献[7]根据共同特征之间的视线夹角选择视点。文献[8-10]通过初始飞行采集影像，重建场景表面，并沿着表面法线方向生成候选视点。然后，采取不同的方法选择最佳视点，这些视点可以增加观测覆盖的范围并得到不同的观测角度。文献[11]先获取一个概略的三角形网格模型，然后为每个三角形生成一个候选视点，并迭代选择可以观察到三角形数量最多、从不同角度观察的视点。该方法通过考虑视点与场景表面的角度来选择视点。文献[8]考虑视线夹角的大小来选择视点，但该方法没有考虑视点之间的重建度。

为了有效地选择视点，不仅要考虑增加视点观测覆盖的范围和获取视点不同的观测角度，还需要考虑如何最大化每个视点对重建结果的贡献。因此，设计了一种基于视点可重建性约束的最短航线规划方法，先获取先验场景，并以此为基础生成候选视点并优化，再生成平滑的航线采集数据。通过与倾斜摄影测量方法进行实验对比与分析，验证该方法的有效性。

1 基于视点可重建性约束的航线规划

基于视点可重建性约束的最短航线规划方法属于先探索再利用方法，包括探索和利用两个阶段，如图1所示。探索阶段目的是获取场景的概略模型作为先验场景；利用阶段基于先验场景进行视点和航线规划，生成飞行轨迹进行数据采集。

1.1 候选视点生成

获得先验场景常用的方法是，通过最低点飞行采集数据，进行图像重建得到先验场景。视点生成部分一般先基于先验场景确定无人机飞行的安全空域，再生成候选视点并优化视点位置和姿态。首先，在先验场景使用类似图像去噪的基于滤波器的方法，并把中值滤波器换成膨胀算子，生成安全空域。如图2所示，在安全和潜在危险空域之间形成一个封闭的表面，然后在封闭表面周围均匀分布生成初始候选视点。

1.2 可重建度计算

影响运动恢复结构（Structure From Motion, SFM）以及多视立体（Multi-View Stereo, MVS）重建的因素会间接影响重建模型的质量^[12]。通过研究发现，有以下影响重建模型质量的因素。

1）距离。相机视点与场景表面之间的距离决定了重建模型的分辨率，三角测量误差随着距离和视角差值的减小而增加。

2）多视角。需要从多个视角观察目标场景（理论上至少两个视角，实际上需要更多视角以提高三维重建的完整性和准确性），从不同的角度获得具有足够重叠率的视点。

3）观测角和视线夹角。在MVS中更浅的观测角度（即视线与场景表面法线之间的角度）重建效果更好。相邻视点的视线夹角角度大有利于提高三角测量质量，但是会导致在复杂的三维结构中，对图像进行对应点或者特征匹配变得困难。

现有方法^[13-17]引入可重建度启发式方法，只需要概略模型就可以预测重建质量，可重建度启发式方法是基于一个采样点和一对可以观察到采样点的视点之间的几何关系，来定义可重建性并用于计算可重建度。

得到初始候选视点集之后，在场景表面均匀生成一组采样点s。如图3所示,对于一对视点\left(V_{\mathrm{1}},V_{\mathrm{2}}\right)可以看到的采样点s,s相对于\left(V_{\mathrm{1}},V_{\mathrm{2}}\right)的可重建度为

R\left(s,V_{\mathrm{1}},V_{\mathrm{2}}\right)=w_{\mathrm{1}}(\alpha )w_{\mathrm{2}}(d)w_{\mathrm{3}}(\alpha )\mathrm{c}\mathrm{o}\mathrm{s}\theta（1）

式中：权重w_{\mathrm{1}}和w_{\mathrm{3}}保证交会角既不会过大也不会过小；权重w_{\mathrm{2}}保证视点距离采样点不会过远；余弦系数\mathrm{c}\mathrm{o}\mathrm{s}\theta确保视点方向不会偏离法向量太多；R\left(s,V_{\mathrm{1}},V_{\mathrm{2}}\right)从交会角、视距、偏离法向量3个方面评估采样点的可重建度；\alpha是2个视点的视线夹角；d是从采样点到2个视点距离中较长的那段距离；n\mathrm{是采}\mathrm{样点}s处的表面法线；\theta是视线与n之间的2个角度中较大的1个。如式（2），根据视点的视线夹角对三角测量误差的影响，可以建模为

w_{\mathrm{1}}(\alpha )={\left(\mathrm{1}+\mathrm{e}\mathrm{x}\mathrm{p}\left(-k_{\mathrm{1}}\times \left(\alpha -{\alpha }_{\mathrm{1}}\right)\right)\right)}^{-\mathrm{1}}（2）

式中，\alpha随着d的增加而减小。如式（3），距离可以建模为

w_{\mathrm{2}}(d)=\mathrm{1}-\mathrm{m}\mathrm{i}\mathrm{n}\left(d/d_{\mathrm{m}\mathrm{a}\mathrm{x}},\mathrm{1}\right)（3）

式中，d_{\mathrm{m}\mathrm{a}\mathrm{x}}是一个阈值，参考文献[14]中的方法设置为\mathrm{2}\times d_{\mathrm{G}\mathrm{S}\mathrm{D}}。如式（4），基于视差对影像立体匹配的影响，可以建模为

w_{\mathrm{3}}(\alpha )=\mathrm{1}-{\left(\mathrm{1}+\mathrm{e}\mathrm{x}\mathrm{p}\left(-k_{\mathrm{3}}\times \left(\alpha -{\alpha }_{\mathrm{3}}\right)\right)\right)}^{-\mathrm{1}}（4）

式中：k_{\mathrm{1}}、{\alpha }_{\mathrm{1}}、k_{\mathrm{3}}和{\alpha }_{\mathrm{3}}是4个可控参数；参考文献[14]中的方法设置为k_{\mathrm{1}}=\mathrm{32}、{\alpha }_{\mathrm{1}}=\frac{\mathrm{\pi }}{\mathrm{16}}、k_{\mathrm{3}}=\mathrm{8}和{\alpha }_{\mathrm{3}}=\frac{\mathrm{\pi }}{\mathrm{4}}，可以更好地计算可重建度。在至少2个视点的原则下，采样点s在视点集V上的可重建度为

h(s,V)=\sum _{i,j=\mathrm{1},\dots ,|V|}v\left(s,V_i\right)v\left(s,V_j\right)R\left(s,V_i,V_j\right)（5）

式中，v\left(s,V\right)是二值函数，如果采样点s在视点V上可见，则等于1，否则为0。

对单个采样点来说，计算所有可以看见该采样点的视点对，关于该采样点的可重建度之和为该采样点的最终可重建度。因此，通过下山单纯形法不断优化视点位置和角度来提高采样点的可重建度，如式（6），寻找目标函数O的最小值为

\begin{array}{l}\underset{V}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}O}=\underset{V}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\lambda |U|+\\ \sum _{s\in S,U}{\left(\mathrm{m}\mathrm{a}\mathrm{x}\left(h_{\mathrm{m}\mathrm{a}\mathrm{x}}-h(s,V),\mathrm{0}\right)\right)}^{\mathrm{2}}\end{array}（6）

式中：U\subset S代表所有候选视点不能观察到的采样点集合；argmin \lambda \left|U\right|用\lambda因子探索视点观察不到的采样点，在此设定为1；\sum _{s\in S,U}{\left(\mathrm{m}\mathrm{a}\mathrm{x}\left(h_{\mathrm{m}\mathrm{a}\mathrm{x}}-h\left(s,V\right),\mathrm{0}\right)\right)}^{\mathrm{2}}是使采样点的可重建度最大，当h(s,V)达到一定阈值时，添加视点会造成视点冗余。

对于每个视点，分别对视点的方向和位置进行优化。当视点位置固定时，方向影响视点对采样点的观测。因此，在每个视点的观测球形直方图（Spherical Histogram）中收集采样点的质量提升信息，并将这些球形直方图与代表视点平截锥体（Viewing Frustum）的核心进行卷积，可以确定对样本点重建度贡献最大的视点方向。

1.3 基于下山单纯形的视点位置优化

使用下山单纯形法（Downhill Simplex Method）来优化视点位置。下山单纯形法是一种用于在多维空间中寻找目标函数最小值或最大值的数值方法。该方法使用了单纯形的概念，单纯形是n维空间中的（n+\mathrm{1}）个顶点的特殊多面体。单纯形包括线段（一维空间中的线段）、三角形（二维平面上的三角形）、四面体（三维空间中的四面体）等。

首先，在均匀分布的初始视点周围随机定向创建单纯形，在此采用三角形，并以单纯形中最低点的观察方向进行初始化。然后，迭代随机选择视点集，并行优化视点的位置和方向。对于单个单纯形优化时，因为其他视点的位置变化可能导致目标函数O发生变化，所以先重新评估单纯形中所有顶点的目标函数O的变化。在评估新候选位置的顶点目标函数O的变化时，确定候选位置的最优视点方向。

在下山单纯形法中，如果新位置更好，单纯形会扩张，如果新位置比之前已知的位置差，单纯形会收缩。由于在迭代过程中会优化其他视点，目标函数可能发生变化。因此，单纯形需要保持合适的大小，通过提高优化次数较少的视点的选择概率，促进单纯形保持合适的大小。

下山单纯形法有助于保持算法的灵活性和有效性，在提高目标函数的同时，也考虑到了实际应用中飞行空域的限制。通过动态调整单纯形大小，该算法可以更好地适应复杂多变的环境，并在寻找全局最优解的过程中，避免陷入局部最优解。终止条件确保算法可以在实际问题中以合适的计算成本收敛到一个满意的解。

1.4 轨迹生成

得到最终优化的视点后，需要生成平滑航线采集数据。首先，找到从初始视点经过每个视点的最短航线，将最短航线问题转化为旅行商问题（Travelling Salesman Problem, TSP）进行求解，采用2-optimization（2-opt）^[18]算法来解决TSP。2-opt是一种随机性算法，也称两元素优化，基本思想就是随机取两个元素进行优化，一直到无法优化为止。

以TSP为例：假设有7座城市，一位旅行商要经过这7座城市并且最终返回出发的城市，求解最短的路线。

使用2-opt解决该问题的算法如下（设置参数最大迭代次数C_{\mathrm{m}\mathrm{a}\mathrm{x}}，初始化计数器C值为0）。

1）随机选择一条路线d（例A→B→C→D→E→F→G），假设这条路线是最短路线d_m；

2）在路线d中随机选择不相连的2个节点，将2个节点之间的路径翻转过来获得新路径，例如随机选中了B节点和E节点，则新路径为A→E→D→C→B→F→G，括号部分为被翻转的路径。

3）如果新路径比d_m路径短，则设新路径为最短路径d_m，将计数器C计为0，返回步骤2），否则将计数器C值加1，当C\ge Coun{t}_{\mathrm{m}\mathrm{a}\mathrm{x}}时，算法结束，此时d_m即为最短路径，否则返回步骤2）。

然后，采用B样条曲线插值方法^[19]，将最短航线转换成安全、平滑、动态可行、时间短的航线。B样条曲线是把最短航线的路径点当成B样条曲线的控制点，通过在相邻的控制点之间插入一个或多个中间点来生成曲线，再连接所有的中间点来形成平滑的航线。

2 实验设计

本节介绍实验中使用的先验场景情况，实验环境和质量评价指标。

2.1 实验先验场景

先验场景是无人机航线规划方法的关键，基于细节多的代理进行规划，一般会得到更高质量的飞行轨迹、更高精度的重建模型。如图4所示，采用3个合成场景的概略模型、较精细模型作为先验场景，高细节程度模型作为真值进行质量评价。其中：概略模型是通过寻找场景中每个建筑的边界框综合高度信息构建的盒状模型；较精细模型是通过倾斜摄影获取的影像重建得到的三维模型；高细节程度模型是通过激光扫描数据重建的真值。

2.2 质量评价指标

采用模型评价方法^[20]对重建质量进行评价。把重建模型和真值对齐，然后以400 000的点云总数量、0.002 m的体素大小对两个三维模型进行均匀重采样，并计算重建精度（Precision）、重建完整度（Recall）和F1值（F1-score）。

其中，Precision通过计算重建后的点云（R）到真值点云（G）的距离衡量重建精度。如式（7）所示，R中的一个点r到G中所有点的距离中，最小的距离就是r到整个G的距离。式（8）定义在阈值d下Precision的计算方式，对于R中的所有点r，计算这些点到G的距离，统计所有距离小于阈值d的点的个数，除以R中点的总个数后，乘以100得到Precision。

e_{r\to G}=\underset{g\in G}{\mathrm{m}\mathrm{i}\mathrm{n}}‖r-g‖（7）

（8）

Recall衡量重建完整度，即真值点云（G）到重建后的点云（R）的距离。和Precision类似，式（9）定义在G中的一个点g到R中所有点的距离中，最小的距离就是g到整个R的距离。式（10）定义在阈值d下Recall的计算方式，对于G中的所有点g，计算这些点到R的距离，统计所有距离小于阈值d的点的个数，除以G中点的总个数，乘以100得到Recall。

e_{g\to R}=\underset{r\in R}{\mathrm{m}\mathrm{i}\mathrm{n}}‖g-r‖（9）

（10）

为了综合重建精度和重建完整度评价重建质量，式（11）计算表示为

F\mathrm{1}=\frac{\mathrm{2}P(d)R(d)}{P(d)+R(d)}（11）

在本文中Precision、Recall和F1保留两位小数，d距离阈值为0.1 m。

2.3 实验环境

实验仿真环境使用NVIDIA RTX 3080显卡，显存128 GB，PyCharm2021。无人机仿真在基于UE4软件的AirSim模拟器中实现。AirSim 是一款基于游戏引擎的开源跨平台仿真器，它是基于虚幻引擎开发的仿真平台，作为虚幻引擎的插件而存在，可以用于无人机、无人车等机器人的物理和视觉仿真。

3 实验结果与分析

按照以上先验场景和质量评价指标，进行不同方法对比实验结果与分析和不同细节层次先验场景对比实验结果与分析。

3.1 不同方法对比实验结果与分析

在学校、城镇和房区3个仿真场景中采用倾斜摄影方法与基于可重建性约束的最短航线规划方法进行重建结果对比与分析。采集的图像使用RealityCapture重建软件进行三维重建。得到重建结果进对比如图5所示。

在实验里基于可重建性约束的方法使用较精细模型作为先验场景，通过模型整体外观和局部细节对比，倾斜摄影方法的重建质量明显比基于可重建性约束的方法的重建质量低，整体外观和模型局部细节差。

如表1所示，在3个不同规模的场景里，基于可重建性约束的方法的重建精度、完整度和F1值都高于倾斜摄影测量方法。3个场景中，房区场景重建质量最高。

3.2 不同细节层次先验场景对比实验结果与分析

以学校、城镇和房区3个仿真场景的概略模型、较精细模型作为先验场景，采用相同的基于可重建性约束的方法进行规划，进行重建结果对比与分析。

如图6所示，在相同的场景里，基于不同概略程度的先验场景使用可重建性约束的最短航线规划方法进行航拍任务规划。通过模型整体外观和局部细节对比，在实验里使用较精细模型作为先验场景，比使用概略模型作为先验场景的重建模型质量更高，整体外观和模型局部细节更强，重建效果更好。

如表2所示，通过真值和重建模型的精度和完整度对比，说明在使用相同的基于可重建性约束的方法前提下，先验场景细节程度越高，得到的影像信息量越大，重建精度、重复完整度和F1值越高，生成的重建模型质量越高。

4 结束语

无人机航指获取的影像质量对重建的三维模型有重要影响。提出一种基于视点可重建性约束的最短航线规划方法，通过先验场景确定无人机飞行的安全空域，在安全空域上进行均匀采样得到候选视点；引入视点可重建度并结合下山单纯形法得到最终优化的视点；然后采用2-opt算法求解旅行商问题得到最短航线；结合B样条曲线插值方法得到平滑航线，采集对景物覆盖程度更高的影像。在3个不同场景下与倾斜摄影测量方法进行对比实验，并考察相同方法下使用不同细节层次先验场景的影响。实验结果表明，相比于倾斜摄影测量，本文方法得到的三维重建模型精度、完整度和F1值更高，获取的影像数据覆盖程度更高。在使用相同方法的情况下，先验场景越精细，生成的视点信息量越大，得到的三维重建模型精度、完整度和F1值更高。表明本文方法可以得到信息量大的视点，有效提高采集的影像质量，从而提高三维模型的重建质量。

综上所述，使用可重建度约束优化视点对于无人机航拍任务规划质量的提高有明显的作用。该方法需要先获得先验场景生成航线，再飞行采集数据，前期成本高。后续重点研究在采集数据的同时更新景物先验模型和动态规划调整航线，以降低任务成本。

参考文献

[1] 姜三，许志海，张峰，面向无人机倾斜影像的高效SfM重建方案［J］.武汉大学学报（信息科学版），2019，44（8）：1153-1161.

[2] 田周泰，柴梦娟，刘广怡，基于改进人工鱼群算法的无人机三维航迹规划［J］.信息工程大学学报，2024，25（1）：80-84.

[3] XIE K， YANG H， HUANG S Q，et al. Creating and chaining camera moves for quadrotor videography［J］. ACM Transactions on Graphics，2018， 37（4）：88.

[4] GALVANE Q， LINO C， CHRISTIE M，et al. Directing cinematographic drones［J］. ACM Transactions on Graphics，2018，37（3）：34.

[5] GEBHARDT C， STEVŠIĆ S， HILLIGES O. Optimizing for aesthetically pleasing quadrotor camera motion［J］. ACM Transactions on Graphics，2018， 37（4）：90.

[6] MENDEZ O， HADFIELD S， PUGEAULT N，et al. Next-best stereo：extending next-best view optimisation for collaborative sensors［C］∥Procedings of the British Machine Vision Conference 2016. York，UK：BMVA Press，2016：1-65.

[7] GOESELE M， SNAVELY N， CURLESS B，et al. Multi-view stereo for community photo collections［C］∥2007 IEEE 11th International Conference on Computer Vision.Rio de Janeiro， Brazil： IEEE，2007. DOI：10.1109/ICCV. 2007.4408933 .

[8] ROBERTS M， SHAH S， DEY D，et al. Submodular trajectory optimization for aerial 3D scanning［C］∥2017 IEEE International Conference on Computer Vision. Venice，Italy： IEEE，2017：5334-5343.

[9] SCHMID K， HIRSCHMÜLLER H， DÖMEL A，et al. View planning for multi-view stereo 3D reconstruction using an autonomous multicopter［J］. Journal of Intelligent & Robotic Systems，2012，65（1）：309-323.

[10] HEPP B， NIEßNER M， HILLIGES O. Plan3D： viewpoint and trajectory optimization for aerial multi-view stereo reconstruction［J］. ACM Transactions on Graphics，2019，38（1）：4.

[11] HOPPE C， WENDEL A， ZOLLMANN S，et al. Photogrammetric camera network design for micro aerial vehicles［DB/OL］. （2012-05-06）［2024-05-20］.

[12] MABOUDI M， HOMAEI M R， SONG S，et al. A review on viewpoints and path planning for UAV-based 3-D reconstruction［J］. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing，2023，16：5026-5048.

[13] 李清泉，邵成立，万剑华，优视摄影测量与泛在实景三维数据采集：以实景三维青岛为例［J］.武汉大学学报（信息科学版），2022，47（10）：1587-1597.

[14] SMITH N G， MOEHRLE N， GOESELE M，et al. Aerial path planning for urban scene reconstruction［J］. ACM Transactions on Graphics，2018，37（6）：183.

[15] ZHOU X H， XIE K， HUANG K，et al. Offsite aerial path planning for efficient urban scene reconstruction［J］. ACM Transactions on Graphics，2020，39（6）：192.

[16] 李清泉，黄惠，姜三，优视摄影测量方法及精度分析［J］.测绘学报，2022，51（6）：996-1007.

[17] ZHANG H， YAO Y， XIE K，et al. Continuous aerial path planning for 3D urban scene reconstruction［J］. ACM Transactions on Graphics，2021，40（6）：225.

[18] CROES G A.A method for solving traveling-salesman problems［J］. Operations Research，1958，6（6）：791-812.

[19] ZHOU B Y， GAO F， WANG L Q，et al. Robust and efficient quadrotor trajectory generation for fast autonomous flight［J］. IEEE Robotics and Automation Letters，2019，4（4）：3529-3536.

[20] KNAPITSCH A， PARK J， ZHOU Q Y，et al. Tanks and temples： benchmarking large-scale scene reconstruction［J］. ACM Transactions on Graphics， 2017，36（4）：78.

基金资助

国家自然科学基金(42101458)

国家自然科学基金(41801388)