基于场景图划分的无人机影像定位算法

张 驰，李铸洪，刘 舟，沈未名*

（1.测绘遥感信息工程国家重点实验室（武汉大学），武汉 430079；2.华中科技大学软件学院，武汉 430074；3.武汉大学计算机学院，武汉 430072）

0 引言

从20 世纪60 年代至今，遥感（Remote Sensing，RS）技术作为一门新兴的科学技术迅速发展，如今已在地图测绘、环境监测、国土资源调查、城市三维重建等诸多领域发挥着举足轻重的作用。传统的遥感方式主要包括有人航空遥感和卫星遥感，尽管这些可以方便的获取大范围的地理信息数据，但在面对应急测绘、小范围的精细测绘等任务时，传统的遥感方式难以达到实际要求。近年来，在无人机（Unmanned Aerial Vehicle，UAV）、计算机、导航与定位技术不断发展的背景下，应运而生的无人机遥感（UAV Remote Sensing，UAVRS）技术有效地弥补了有人航空遥感和卫星遥感的缺陷，凭借其结构简单、灵活机动、实时性强以及成本低的优势，在应急测绘、小范围的精细测绘以及自然灾害救援中发挥了关键性的作用［1-3］。

无人机影像定位是无人机遥感技术中的一个十分关键的任务，主要利用无人机影像以及无人机平台获取到的一些辅助信息，计算出无人机相机和地面物体的相对位置关系，从而实现地面目标的精确定位。部分研究学者对传统航空摄影测量技术进行了改进，提出了一些适用于无人机的摄影测量方法。袁修孝等［4］提出基于全球定位系统（Global Positioning System，GPS）精密单点定位的低空遥感GPS 辅助空中三角测量方法，利用搭载在无人机中的动态GPS接收机获取的GPS摄站取代地面控制点进行摄影测量，并通过实验证明了这种方法的有效性以及优越性。郭复胜等［5］提出了一种无人机影像批处理三维重建方法，充分利用了无人机平台的辅助信息，包括低精度的位置信息、姿态信息以及粗略的地形高程信息，实现了大规模的无人机影像快速鲁棒的三维重建。Rhee等［6］针对无人机立体测绘中比较重要的3 个问题（外方位元素精度不高、拍摄不稳定和图像覆盖范围小），开发了一个摄影测量增量光束法平差程序，基本可以达到1∶1 000测图的精度要求。

随着计算机视觉技术的不断发展，运动恢复结构技术不断成熟，相较于摄影测量技术，运动恢复结构（Structure From Motion，SFM）技术不需要无人机平台提供任何辅助信息，也不需要额外的控制点信息，要求较低且通用性强，因此基于SFM 的无人机影像定位技术逐渐成为国内外学者的关注热点。尹双双等［7］针对移动全景影像，利用GPS 信息对影像匹配、场景初始化以及光束法平差等主要步骤进行了优化，提高了影像位姿和场景模型的精度。陈锐等［8］对SFM 技术中的图像特征提取、特征匹配以及光束法平差进行了优化，在较短时间内计算出较高精度的拼接影像，实时性较好。Lhuillier［9］提出了两种光束法平差IBA（Bundle Adjustment with Inequality constraint）和EBA（Bundle Adjustment with Equality constraint）用来融合GPS信息和SFM数据，为了保证较小的重投影误差，在光束法平差中引入了重投影误差的上界限。面对长序列无人机影像和低精度的GPS 信息，该方法仍然可以计算出较为准确的相机位姿。Irschara 等［10］利用GPS 和惯性测量单元（Inertial Measurement Unit，IMU）辅助信息加速SFM 的计算，实现了更加鲁棒和高效的三维重建。Qu 等［11］提出了一种基于图像队列的快速精确的三维重建方法，利用主成分分析、加权光束法平差等技术，在图像数量较多的情况下，较大提高了重建速度。

尽管这些方法结合无人机影像的特点对SFM 技术进行了有效的扩展，但在实际应用中，基于SFM 的无人机影像定位技术仍然存在一些问题：一方面，由于无人机影像规模的不断扩大，SFM技术流程中的图像匹配、光束法平差优化等步骤的计算量大大增加，导致无人机影像定位需要消耗大量的时间；另一方面，对于长序列无人机影像，由于SFM 固有的误差累计问题，每加入一张图像都会引入新的误差，导致最终的误差过大且难以全局优化。

针对上面所描述的问题，本文对基于SFM 的无人机影像定位算法进行了优化，主要贡献如下：1）提出了基于场景图划分的无人机影像定位算法，利用分而治之的思想，通过场景图的构建与划分对无人机影像进行分组，利用光束法平差进行融合；2）利用无人机平台获取的GPS 信息缩小图像匹配的空间搜索范围并且为光束法平差添加新的约束。实验结果表明，对于大规模长序列的无人机影像，优化后的方法可以更快速地完成更精确的影像定位。

1 基于运动的结构恢复

运动恢复结构是计算机视觉领域多视图重建中的核心问题，主要任务是根据对物体或场景拍摄的多视图像，利用特征匹配、三角化以及光束法平差等技术，计算出相机位置和姿态信息以及同名点的世界坐标。SFM技术可分为增量式SFM和全局SFM。增量式SFM首先挑选一个初始相对进行重建从而得到一个初始三维模型，之后不断添加新的图像，并对新加入的同名点进行三角化同时利用光束法平差重新进行优化，直至所有图像处理完毕［12-15］。全局SFM 则同时估计所有相机的位姿信息并且光束法平差只执行一次［16-19］，因此，相较于增量式SFM，全局SFM 计算速度较快，但同时全局SFM 缺乏误差剔除的机制，因而其重建结果受匹配误差的影响很大。本文主要针对增量式SFM进行优化。

增量式SFM 的重建流程如图1 所示，主要包括同名点获取和增量重建两个阶段。

图1 增量式SFM重建流程Fig.1 Flowchart of SFM incremental reconstruction

第一阶段为同名点获取。首先通过特征提取技术计算出图像中特征点的位置以及对应的特征描述子。尺度不变特征变换（Scale-Invariant Feature Transform，SIFT）［20］及其派生物［21］因具有较好的稳定性和不变性被广泛使用。之后对图像进行特征匹配，即比较两幅图像中特征点的相似程度，通常使用两个特征描述子之间的欧氏距离进行描述，从而得到可能的重叠图像对以及它们相匹配的特征。由于匹配仅仅依赖于特征描述子之间的相似程度，很可能相匹配的一对点并不对应于场景中的同一点，所以需要对匹配点进行几何验证，即使用一个几何变换来描述两幅图像相匹配的特征点间的映射关系。通常随机抽样一致（RANdom SAmple Consensus，RANSAC）算法［22］被使用来滤除不满足几何变换的错误匹配点。这一阶段的输出为经过几何验证的重叠图像对以及经过外点滤除后的相匹配的特征点。这一输出也被表示为场景图，场景图的节点为图像，场景图的边连接了几何验证后的图像对。

第二阶段为增量重建，即根据第一阶段得到的场景图进一步恢复出相机的位姿以及三维模型。这一阶段首先选取一个图像对进行重建从而实现初始化，被选取的图像对应当具有较多的同名点以及较长的基线以便于得到一个分布较好的初始三维模型。之后不断从剩余图像中选择新的图像添加进来，利用直接线性变换（Direct Linear Transform，DLT）、EPnP［23］等求解PnP（Perspective-n-Point）问题的方法计算新加入图像的位姿信息，同时利用三角化计算出新的同名点对应的世界坐标。由于相机的位姿计算和三角化是分开进行的，同时随着新加入图像的不断增多，误差会不断累积，因此需要光束法平差进行进一步的优化。光束法平差主要通过对相机参数Pc以及投影得到的三维空间点Xk进行联合优化从而达到最小化重投影误差的目的。重投影误差表示为：

其中：π为投影函数，可将三维空间点Xk投影到图像平面上；xj为对应的特征点的坐标；ρj为损失函数。光束法平差问题通常使用LM（Levenberg-Marquardt）算法求解。直至所有的图像都添加完毕，最终可以获得所有图像对应的相机位姿以及完整的三维模型。

2 基于场景图划分的层次式SFM算法

2.1 算法流程

本文在增量式SFM 的基础上，结合无人机图像的特点以及无人机平台的辅助信息，提出了基于场景图划分的层次式SFM算法，算法流程如图2所示。

图2 基于场景图划分的层次式SFM算法流程Fig.2 Flowchart of hierarchical SFM algorithm based on scene graph division

对于输入的无人机图像以及图像对应的GPS 信息，首先进行同名点提取以获取场景图，与上文所述不同的是，在特征匹配阶段，由于GPS信息一定程度上反映了图像的空间关系，因此本文分别计算两两图像间的GPS 距离，GPS 距离较远的两幅图像被视为不重叠图像，之后不对其进行特征匹配。相较于暴力匹配，即对所有图像进行两两特征匹配，结合GPS的匹配策略极大降低了时间复杂度，提高了运行效率。

在增量重建阶段，随着图像的不断增多，光束法平差的时间复杂度急剧增大，此外考虑到不重叠的两张图像彼此依赖关系较小，故而本文采用分而治之的思想对此问题进行了优化。本文首先结合匹配关系和GPS信息重新构建了场景图并进行了划分（2.2 节将详细介绍场景图的构建与划分），为了方便之后的融合，划分出的相邻两组间应当存在多张重叠图像。之后使用多核CPU 并行进行各组的增量重建，一方面并行化充分利用了计算资源；另一方面，光束法平差的时间复杂度随图像规模的减小而减小，故而大大加速了重建过程。最后基于重叠区域对各组的重建结果进行融合，因为各组间存在着不同的误差，所以需要对整体进行光束法平差进一步优化重建结果。

2.2 场景图的构建与划分

场景图是一种图结构，场景图的节点表示图像，边表示图像之间的关系。在传统的SFM 之中，场景图的边连接了两幅具有重叠区域的图像。本文对场景图进行了扩展，即根据两幅图像之间的视觉关系和空间关系为场景图的边赋予了权重，表示如下：

其中：eij表示图像i和j相连的边；Wvis表示两幅图像的视觉一致性，与两幅图像的同名点数量成正比；Wgeo表示两幅图像的空间一致性，与两幅图像的GPS距离成反比，即同名点数量越多，GPS坐标越相近，这两幅图像相连的边的权重就越大；α用来控制Wvis和Wgeo的权重。

构建完场景图之后，本文采用归一化割（Normalized Cut，Ncut）［24］算法进行场景图的划分。定义场景图为G=(V，E)，其中V为顶点，E为边。假设需要将场景图分割成互不相交的两个子集A和B，那么归一化割可表示为：

其中cut（A，B）为集合A和B相连的边的权重之和：

assoc（A，V）和assoc（B，V）分别为集合A和B中的点到图中所有其他点的权重之和：

因此，归一化割既追求不同子集间权重最小，同时还追求同一子集内权重最大。归一化割的结果如图3所示。

图3 归一化割Fig.3 Normalized cut

考虑到增量重建所需的图像规模，归一化割的具体步骤为：设定子集的最大节点数为M，不断迭代地对场景图进行归一化割，直至所有子集的节点数均不超过M。

经过上述场景图的创建和划分，重叠度更高以及空间距离更近的图像将更有可能被划分为同一子集，这不仅为后续的增量重建提供了足够的冗余度，同时保证了重建尽可能少地受到错误信息的干扰。

2.3 GPS辅助光束法平差

根据运动恢复结构一节中所述，计算机视觉中的光束法平差通过最小化重投影误差实现对相机位姿、相机内参以及三维场景点坐标的优化，但是对于无人机拍摄的大规模长序列影像，仅仅依靠重投影误差，不仅会导致较大的误差偏移，而且可能出现多种重建结果同时满足视觉约束的情况。图4为仅仅依靠视觉约束对两组长序列影像进行重建出现的歧义性结果。

图4 歧义性结果Fig.4 Ambiguous result

本文结合GPS 信息对光束法平差进行了优化，考虑到SFM 计算得到的三维模型所处的坐标系B 与世界地理坐标系W并不一致，为了方便之后的光束法平差和场景融合，这里需要将场景模型转换到世界地理坐标系下以实现地理配准。因为模型坐标系与世界地理坐标系之间仅仅存在旋转、平移和缩放的关系，所以本文采用最小二乘法计算相似变换矩阵来实现这一转换。

完成地理配准之后，本文结合GPS 对光束法平差中的代价函数进行了扩展：

其中：Evis为重投影误差，与运动恢复结构一节中所述一致。Egps为计算出的相机中心点cj与实际GPS坐标之间的误差，表示为：

Ediff为计算出的相机中心点的相对距离和实际GPS 坐标的相对距离的误差，表示为：

在GPS 精度不高的情况下，相对距离误差受噪声的影响较小，可以对实际误差起到一定的补偿作用。另外，w1、w2和w3为这3项误差的权重。总的来说，Egps和Ediff的引入为光束法平差添加了相机位置的约束，有效避免了模型收敛到局部极小值的情况，使得对大规模长序列无人机影像的重建和定位更加鲁棒和精确。

3 实验与结果分析

3.1 实验准备

为了充分验证本文所提算法的鲁棒性和有效性，本文选取了四个无人机影像数据集进行实验，分别为果子沟数据集、赛里木湖数据集、武大数据集以及NPU_Monticules 数据集，如图5 所示。其中，果子沟和赛里木湖数据集为长序列无人机影像，而武大和NPU_Monticules 数据集为无人机阵列式拍摄获取的影像。4 个数据集均包含GPS 信息，其中赛里木湖数据集的GPS精度为0.2 m，其他3个数据集的GPS精度为2 m。4个数据集均不包含任何地面控制点。

图5 无人机影像数据集Fig.5 UAV image datasets

此外，本文所有的实验所采用的PC 平台配置为Intel Core i7-6700HQ CPU 2.6 GHz，内存为16 GB，显卡为GeForce GTX 1060，系统为Ubuntu 16.04。

3.2 定量评价

为了验证本文提出的基于场景图划分的无人机影像定位算法的有效性，本文在上述4 个数据集上进行了对比实验，对比算法分别为COLMAP［13］、OpenMVG［25］以及OpenSFM［26］，其中，COLMAP 和OpenMVG 未利用GPS 辅助信息，OpenSFM 利用绝对GPS误差来优化光束法平差。定量评价指标为重投影误差，即三维点云的投影点和其对应的特征点之间的距离，具体定义可参照第1章。表1展示了4种算法在4个数据集上的重投影误差结果。

表1 四种算法的重投影误差结果 单位：像素Tab.1 Reprojection error results of four algorithms unit：px

从定量评价结果可以看出，相较于其他三种算法，本文提出的算法可以获得更小的重投影误差。对于果子沟和赛里木湖这两个长序列无人机影像数据集，融合了GPS 辅助信息的算法优势十分明显。尤其对于果子沟数据集，因其GPS 定位精度不高，本文提出的GPS 相对误差辅助平差有效消除了GPS噪声的影响，相较OpenSFM优化提升显著。

3.3 场景划分结果分析

为了验证本文提出的基于场景划分的层次式重建的优化效果，本文对四组无人机影像数据集分别进行了增量式重建和层次式重建。为了控制实验变量，除了场景图的划分与融合，层次式重建的其他实现过程与增量式重建保持一致。表2展示了增量式SFM和层次式SFM的运行时间。

表2 增量式SFM和层次式SFM运行时间 单位：sTab.2 Running times of incremental SFM and hierarchical SFM unit：s

可以看出，相较于增量式重建，基于场景图划分的层次式重建所需的时间要少得多，这主要因为：一方面并行化充分利用了计算资源；另一方面，光束法平差的时间复杂度随图像规模的减小而大幅降低。

3.4 GPS辅助平差结果分析

为了进一步验证GPS 辅助平差的优化效果，本文对有无GPS辅助下的重建结果进行了对比，如图6所示。

图6 有无GPS辅助的重建结果Fig.6 Reconstruction results with or without GPS assistance

对于果子沟数据集和赛里木湖数据集这种长序列无人机影像，由于航向重叠率不高且仅仅依赖视觉信息进行重建，导致随着图像的不断加入，误差不断累积以致出现了严重的误差漂移的情况，即图中所示重建结果出现了严重的弯曲。而GPS 的引入帮助对相机位置做进一步的约束，避免了出现歧义性的结果。

为了进一步分析定位误差的大小，本文将果子沟数据集的定位结果在x，y，z三个坐标轴上的投影绘制成折线图的形式，如图7所示。

从图7 可以看出，无GPS 辅助下两条线相隔较大，有GPS辅助下两条线近乎重合，因而在GPS的帮助下，相机的运动轨迹得到了很好的约束，误差漂移问题得到了很好的解决。

图7 有无GPS辅助的果子沟数据集定位结果对比Fig.7 Comparison of positioning results with or without GPS-assisted Guozigou dataset

4 结语

本文针对无人机影像定位问题，提出了一种基于场景图划分的层次式SFM 方法，结合视觉一致性和空间一致性进行场景图的创建同时利用归一化割实现对场景图的划分。此外，本文对光束法平差的代价函数进行了扩展，加入了GPS绝对位置误差和相对位置误差。实验结果表明，基于场景图划分的层次式SFM 方法大幅提高了无人机影像的定位速度，同时，相对和绝对GPS 误差辅助平差对相机位姿起到了很好的约束作用，解决了误差漂移的问题，避免了出现歧义性的结果，也因此本算法相较同类算法有较为显著的优化提升。

然而，本文提出的算法是基于增量式SFM 重建实现的，增量式SFM 重建中固有的误差累计问题仍然不可避免，考虑到全局SFM 重建有效避免了误差累计问题但带来了较大的不稳定性，因此如何有效地结合增量式SFM 重建和全局SFM重建，提高影像定位的准确性和稳定性是未来的研究趋势。