0 引言

近年来，随着民用无人机的快速发展和消费级数码相机的快速普及，高分辨率无人机序列图像成为基于图像的三维重建的重要数据来源。无人机序列图像的大范围、高分辨率的特性使得高细节纹理的城市级别三维重建成为现实。

中科院自动化所的郭复胜^[1]等人利用GPS、IMU、地面概略高程数据等辅助信息计算图像之间的概略重叠度，缩小影像匹配范围，从而提升无人机图像三维重建的效率。辅助信息的获取需要从网络上查找或者通过飞行文件解析。本文试图通过一种更加便捷的方式提高无人机序列图像的重建效率，并且更加自动化。

本文设计并实现的无人机序列图像快速三维重建系统FDroneMap主要从两方面提升系统的运行效率，一方面是对重建算法进行重新设计和优化，另一方面是对重建模块进行并行化设计^[2]。

1 系统简介

通常的基于图像的三维重建系统一般包含以下几个模块：图像特征提取、图像特征匹配、从运动恢复结构（Struture from Motion，SfM）。其中图像特征匹配模块耗时最长。在三维重建系统中为了充分利用图像信息，常用的特征匹配策略是暴力匹配（brute force matching），其时间复杂度为O(N²)。特征匹配所消耗的时间会占总处理时间的一半以上，如果待处理的图像尺寸增大，特征匹配所占的时间比例还会持续增加。其次是特征提取模块及SfM模块中的光束法平差^[3]（Bundle Adjust）部分，这两部分模块的处理时间也会随着图像尺寸的增加而剧增。因此为了提高处理速度，FDroneMap主要针对这三部分进行改进和优化。其中特征匹配模块采用了一种新的基于哈希表的匹配方法，并结合无人机序列图像本身的时空序列特性改进匹配策略，从而提高匹配效率。特征提取模块和光束法平差部分通过挖掘原有算法中的可并行性，进行并行化设计，充分利用CPU/GPU的并行计算能力，提升处理速度（别的例如图像加载等部分也进行了并行设计，这里不一一赘述）。本文系统的处理流程如图1所示。

2 重建算法优化

2.1 基于哈希表的图像特征匹配方法

FDroneMap采用基于哈希表的特征匹配方法^[4]，该特征匹配方法分为3个步骤：哈希搜索、哈希重映射、哈希排序，图2为匹配流程，其中L表示哈希表总个数。这3个步骤是一个由粗到精的匹配过程。通过这种由粗到精的匹配方法可以极大地提高特征点匹配的效率。

2.1.1 哈希查找

以图2中的图像I、J为例，哈希查找的目的是获取图像I中的特征点p在图像J中匹配搜索的粗略范围。为了实现这一目的，首先将点p以及图像J中所有的特征点描述符进行哈希映射，生成m位的二进制编码，然后通过特征点对应的编码对所有图像特征点进行聚类，编码相同的视为同一类。最后查找所有包含点p的类组成匹配搜索的概略范围。

查找过程中使用的编码位数m的大小会直接影响聚类的结果，一方面编码越长分类规则越复杂，特征点也越容易被区分开，落在每个分类中的特征点数也越少（待选匹配点也随之减少），这会大大缩小匹配范围，很大程度上减少下一步精确匹配的时间；另一方面编码位数过长会导致落在每个类别的特征点个数过少，待匹配的范围太小，从而降低匹配结果的精度。因此在实际查找过程中选择编码位数时需要权衡效率和精度，本文实验中采用的编码位数为10。

2.1.2 哈希重映射

获取了粗略的匹配范围后，可以通过直接计算点p与所有候选匹配点描述符之间的欧氏距离，比较欧氏距离的大小来确定最终匹配点。但由于粗略匹配的范围相对还是很大，直接计算所有候选点的欧氏距离会耗费相对长的时间。因此为了提升计算的效率，在计算出粗略的匹配范围后，首先对点p以及所有的候选匹配点重新进行更高维度的哈希映射，每个候选匹配点获得一个更多位数的二进制编码。利用该二进制码对所有特征点重新进行分类。然后计算点p与所有候选类别的编码之间的汉明距离（hamming distance），并按照距离大小排序（见2.1.3小节）。汉明距离越小，说明该类别里的候选匹配点与点p越相似。

2.1.3 哈希排序

在计算出点p与所有候选匹配类别编码之间的汉明距离后，为了进行高效的排序，建立一个哈希表，分别使用汉明距离和其关联的类别作为表的键和值。再对表进行检索，得到汉明距离最小的前k个候选类别。最后通过计算点p与这k个候选类别中包含的候选匹配点之间的欧式距离确定最终匹配点（一般选择两个匹配点）。在整个排序过程，哈希表只需要建立一次，时间复杂度仅为O(N+k)。

要获取图像I中特征点p在图像J中匹配点，通常的匹配过程是首先分别计算图像J中所有特征点与p点特征描述符之间的欧氏距离，然后选取欧式距离最小的作为点p在图像J中的匹配点。整个过程的时间复杂度是O(N²)。而基于哈希表的特征点匹配方法在整个匹配过程中，只在最后一步对有限的k个候选类中的候选点进行了欧氏距离的计算，这会大大提升特征点匹配的效率。

2.2 结合时空序列特性的图像匹配策略

不同于一般的来源于互联网的图像集，无人机序列图像之间存在了很强的时空序列性。在拍摄时间上有着前后关系的两张图像必定在空间上也有着相互重叠的关系。

如果能充分利用这种时空序列特性，可以大大减少图像匹配耗费的时间。在处理无人机序列图像时，可以通过飞行文件获取每张图像的曝光时间，并据此生成按时间排序的图像序列。因为无人机序列图像分辨率很高，只需要对图像序列中前后相邻的图像进行匹配就可以获取充分多的匹配点，这足以保证后续的相机运动估计及场景稀疏结构恢复的精度。这种匹配策略的时间复杂度仅为O(N)，极大地加快了图像匹配的速度。只对图像序列中的相邻图像之间进行匹配，也减少了误匹配的产生（例如无人机飞行场景中经常有形状纹理相似的房顶，如果使用暴力匹配很可能会产生误匹配），这也能一定程度提高重建结果的精度。

3 并行设计

对系统模块的并行设计包含从图像加载到模型导出的整个流程。其中对系统效率影响最大的是图像特征提取模块以及SfM模块中的光束法平差（Bundle Adjust，BA）部分。

3.1 基于GPU/CPU并行加速的特征提取

图像特征提取是基于图像的三维重建技术的基础内容，也是FDroneMap系统的核心模块。图像三维重建中最常用的图像特征提取算子为SIFT^[5]（Scale Invariant Feature Transform）算子。SIFT特征点检测的主要步骤如下：首先对原始图像进行DOG滤波处理，然后对滤波后的图像进行极大值和极小值检测，这些极值的像素坐标即为特征点的坐标，最后计算特征点的主方向并通过计算特征点周围128维的特征向量构造特征描述符。

在SIFT特征提取的过程中，有以下几个部分可以做并行化设计^[6]：（1）将颜色信息转换为强度信息，（2）对图像进行上采样和下采样，（3）建立DOG金字塔，（4）特征点检测，（5）计算特征点主方向并构造特征描述符。

通过这5个部分进行并行化可以有效提高特征提取的效率。在实验过程中发现，并不是所有的部分都是使用GPU加速效率更高，其中（1）、（2）部分使用CPU多核并行效率更高。

3.2 基于多核并行的BA

SfM模块主要包含三部分：相机运动估计、场景结构重建以及光束法平差优化。其中光束法平差部分是对前两个部分获得的参数进行平差估计，通过不断地迭代过程拟合出更优的估计结果。下式为光束法平差的估计模型：

式中，R_i、t_i分别表示第i个图像所对应相机的旋转和平移参数，K_i表示第i个图像的内参数矩阵，X_j表示第j个场景三维点在全局坐标系中的坐标，N_c表示进行重建的图像总数，N_3D表示重建的三维场景点总数，x_ji表示第j个三维场景点对应于第i个图像平面上的二维坐标，g表示通过场景点j进行三维空间相似变换和投影到第i个面上获得的二维坐标值。

在平差过程中，由于每张图像所对应的相机参数独立且对应的场景三维点的重投影误差计算互不干涉，所以可以对平差算法进行并行化设计。在实际计算过程中，为了加快运算效率，将这个非线性优化问题转换成简单矩阵向量的计算，并且将计算任务分配到多个线程加速运算（本文实验采用8线程计算）。

4 实验

在当前的基于图像的三维重建系统中，VisualSfM系统在计算效率和重建结果的精度方面都具有一定的优越性。因此本文将VisualSfM系统作为参照对象，在系统运行效率和重建结果精度两方面与FDroneMap进行比较。

4.1 实验结果

为了比较系统的运行效率，FDroneMap和VisualSfM系统分别在6组不同大小尺度的图像集上进行了测试。这6组图像集均来源于无人机航拍。实验结果见表1，其中，T_l为图片加载时间，T_f为特征提取时间，T_m为特征匹配时间，T_b为光束法平差消耗时间，Σ为总消耗时间。

为了比较重建结果的精度，FDroneMap和VisualSfM系统分别在3组公开数据集^[7]上进行了测试。这3组数据集均带有真实的地面数据（ground truth），可解析出每张图像曝光时相机的真实位置。为了将比较结果进行量化，实验比较了FDroneMap和VisualSfM系统的相机位置估计误差（与ground truth比较），结果如图3～图5所示。

4.2 结果分析

从表1中可以看出，FDoneMap在处理时间上明显低于VisualSfM系统，而且随着图像数量和大小的增加两者处理时间之间的差值进一步扩大。5组数据处理时间分别相差了5、7.5、7、16、11、35倍。

从图3～图5可以看出，FDroneMap相机位置估计误差与VisualSfM系统相比没有太大差异，图3、图5几乎保持一致，图4总估计误差FDroneMap略低于VisualSfM系统。

综上，对比实验结果表明：FDroneMap显著提高了无人机序列图像的三维重建的效率，并且没有损失重建结果的精度。

5 结论

通过对算法的优化和对重建模块的并行化设计，FDroneMap在计算效率和处理精度方面都有较好的表现。在大量实验过程中发现一个问题，当FDroneMap处理的图像序列中存在模糊或者扭曲图像时，重建的结果会不完整。当前的处理策略是将原序列拆成多个图像序列分别进行场景结构重建。因此下一步的工作是主要是研究如何对多序列生成的多场景模型进行最优化的融合。

参考文献

[1] 郭复胜，高伟.基于辅助信息的无人机图像批处理三维重建方法[J].自动化学报，2013，39(6)：834-845.

[2] WU C.VisualSFM：A visual structure from motion system[EB/OL].(2012-02-15)[2016-10-22].http：//www.ccw.me/vsfm.html.

[3] TRIGGS B，MCLAUCHLAN P F，HARTLEY R I，et al.Bundle adjustment—a modern synthesis[C].International workshop on vision algorithms.Springer Berlin Heidelberg，1999：298-372.

[4] CHENG J，LENG C，WU J，et al.Fast and accurate image matching with cascade hashing for 3d reconstruction[C].IEEE Conference on Computer Vision and Pattern Recognition(CVPR2014).2014；1-8.

[5] LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60(2)：91-110.

[6] WU C.SiftGPU: A GPU implementation of scale invariant feature transform(SIFT)[EB/OL].(2009-08-27)[2012-10-18].http：//cs.unc.edu/~ccwu/siftgpu.html.

[7] STRECHA C，HANSEN W V，GOOL L V，et al.On bench-marking camera calibration and multi-view stereo for high resolution imagery[C].Computer Vision and Pattern Recog-nition，2008.IEEE Conference on，2008：1-8.

作者信息:

谢理想，万 刚，曹雪峰，王庆贺

（信息工程大学 地理空间信息学院，河南 郑州450001）