基于逐层优化SGM 的倾斜影像三维重建

马东岭石壮吴鼎辉毛力波

(山东建筑大学 测绘地理信息学院，山东 济南250101)

0 引言

实景三维模型可以细致地还原城市面貌，在城市数字化、智能化发展方面具有不可替代的作用，伴随着我国城市智慧化建设的推进，已经成为了智慧城市空间数据体系的重要组成部分[1]。 借助于无人机平台，倾斜摄影测量技术可以快速采集影像数据，实现全自动的实景三维建模，降低了三维建模的经济成本和技术要求[2-4]。 从无人机倾斜影像到三维模型的技术流程大致分为多视影像匹配、多视影像定向、密集匹配、点云构网和纹理映射[5]。 其中，密集匹配是一种在具有重叠度的二维影像中逐像素地匹配，并尽量寻找最多同名像点的技术[6]，是二维影像生成三维点云的关键技术之一，其效率和精度直接影响三维重建的效率和三维模型的精度。

根据求解视差所采取匹配策略的不同，影像密集匹配方法可以分为全局匹配和局部匹配方法，然而这两种方法一般难以兼顾精度和速度。HIRSCHMULLER[7]提出的半全局匹配(Semi-Global Matching，SGM)算法是一种介于局部匹配和全局匹配之间的密集匹配算法，仅在像素点8 个方向做匹配代价计算，进行能量聚集，而且在每个方向上能量聚集时，均是通过动态规划的方式完成，因此能同时兼顾计算效率和匹配精度，成为目前密集匹配的首选算法。 然而，无人机倾斜摄影一般从正下方垂直角度、前后左右4 个倾斜角度搭载5 台传感器[8]，采集的影像数据具有基数多、视角变化大、倾斜遮挡较多等特点[9]。 在使用传统半全局密集匹配算法进行密集匹配时，由于其动态规划路径是一维的，像素在一维的路径上进行代价累积计算时，只与在选定方向上的像素有关联，因此在视角变化比较大、地物被遮挡、视角单一及重复纹理处容易产生错误的匹配。 另外，随着能量聚集范围的扩大，伴随着错误匹配的累积，密集匹配的计算效率也会不如刚开始时的效率高[10]。 因此，直接应用传统的半全局算法进行倾斜摄影三维重建存在一定的困难。

针对该问题，诸多学者提出了相关改进方法。陈智君等[11]提出区域生长的SGM 算法，通过视差控制点修正动态规划路径，减少了误匹配，但是较依赖区域生长匹配的范围和精度。 李珊等[12]提出将绝对差和Census 算法融合替代单一匹配代价来改进SGM 算法，但是融合的算法会增加计算的复杂度。 吴军等[13]提出融合尺度不变特征转换(Scaleinvariant feature transform，SIFT)和SGM 的匹配方法，使用SIFT 优化路径减少误匹配，但是机载倾斜影像所固有的多视图约束尚未得到充分利用。ROTHERMEL 等[14]提出tSGM 算法，采用由粗到精的金字塔逐层优化匹配策略，利用上层匹配结果动态地寻找每个像素的视差搜索范围，减少了密集匹配的时间，同时提高了匹配的准确度。 还有学者在地形高差较大的城区使用tSGM 算法获取高精度的数字表面模型(Digital Surface Model，DSM)，在计算效率和内存开销方面也具有较好的平衡[15-16]。

文章针对无人机倾斜影像在角度变化大、遮挡处容易产生误匹配以及计算效率大幅度降低的问题，在无人机倾斜影像多视密集匹配阶段采用多级分层匹配思想，使用低分辨率影像的匹配结果，动态限定高分辨率影像上待匹配像素的视差搜索范围，即对SGM 的动态规划路径进行像素约束，通过增加有效匹配点的密度和减少匹配过程中的内存开销与计算时间，进一步提高倾斜影像三维重建的精度和效率。

1 基于逐层优化SGM 的倾斜影像三维重建流程

在获取倾斜影像数据后，通常进行空中加密、密集匹配、表面模型构网和纹理映射等过程，最终得到实景三维重建模型。 为解决传统SGM 算法在密集匹配阶段存在的问题，文章在密集匹配阶段采用逐层优化SGM 策略，通过低分辨率影像对的匹配结果限制高分辨率影像匹配视差的搜索界限，在动态限定的搜索范围内寻找有效视差并自适应计算匹配代价。 其基本的流程如图1 所示。

图1 基于逐层优化SGM 的倾斜影像三维重建流程图

1.1 倾斜影像获取及空中加密

无人机倾斜摄影测量的相机安置方式通常采用十字形，即由一个垂直安置的相机和4 个45°倾斜安置的相机构成。 在5 个角度一次曝光从而获得具有一定重叠度的5 张照片，如图2 所示。

图2 无人机倾斜影像获取方式图

在获取倾斜影像数据后，先要进行空三加密。空三加密是根据无人机倾斜影像的机载定位定向系统(Position and Orientation System，POS)数据解算倾斜影像的外方位元素的过程。 通过特征点提取、核线约束等特征点稳健匹配等关键算法，得到同名点匹配结果，同时构建连接点、连接线、POS 数据的区域网平差误差方程，从而解算全部倾斜影像的空中姿态和拍摄位置，进而求得影像同名点的地面测量坐标。

1.2 倾斜影像密集匹配

密集匹配是在多视影像定向的基础上求解地表上地物密集同名像点位置的过程。 在倾斜摄影中，通过对相邻影像进行密集匹配可以获得视差图，利用视差图可以计算像点的深度，进而获得地物的三维点云。 由于SGM 能得到与全局匹配算法相媲美的结果，并且在匹配时间上优于全局算法，以及匹配精度优于局部匹配算法，成为目前密集匹配的首选。

1.2.1 传统半全局密集匹配

传统的半全局密集匹配算法的思想是:(1) 建立全局能量函数；(2) 最小化该能量函数；(3) 在能量函数达到极小值时获取最优视差。 全局能量函数E(D)可以看做由所有像素的匹配代价和视差优化平滑项组成[7]，由式(1)表示为

式中等号右侧首项为所有像素点的匹配代价之和，C(p，Dp) 为左影像上像素点p视差为Dp时与右影像点的匹配代价。 其余两项是视差优化平滑项，其中T[] 表示一个判断函数，在像点p临近视差差值等于1 的像素点q增加惩罚数P1，在临近视差差值＞1 的像素点q给予惩罚数P2。

匹配代价由代价矩阵组成，代价矩阵维度为r ×c ×(dmax- dmin)，其中r为影像行数、c为影像列数、dmax和dmin分别为视差搜索的上、下界。 代价矩阵计算后，对代价矩阵上的每个点从8 个方向进行代价积聚，如图3 所示。

图3 视差空间匹配代价聚合过程图

像素点p在匹配移动方向为r时的积聚函数由式(2)表示为

式中等号右侧的第1 项为像素点p视差为d时的当前代价；第2 项为从{}中的候选值中选取在r方向上的前一个像素代价最小值；第3 项为防止数字过大设置的惩罚系数。 将所有方向上的代价积聚值进行求和后的代价积聚求和公式由式(3)表示为

完成代价矩阵的积聚后，在视差搜索范围内利用赢家通吃(Winner Take All，WTA)算法，每个像素选择最小聚合代价值所对应的视差值作为最优视差，也是最终视差。

1.2.2 逐层优化半全局匹配

逐层优化SGM 将整个场景进行分层降采样，低分辨率影像上的匹配结果不仅用于初始化和改善互信息匹配成本，而且还用于限制下一层影像上的视差搜索界限，并逐步优化到原始层。 通过动态限定匹配通道上的视差搜索范围的方式，确定高分辨率影像等级的互信息匹配成本，进而实现由粗到精的匹配。

在计算视差搜索范围时，在待计算像素X1周围窗口中搜索视差最大值dmax、最小值dmin，判断最大、最小值差值是否超过最大预设范围。 如果在最大预设范围内，上边界范围设置为dmax-X1＋2，下边界范围设置为X1-dmin＋2。 如果超出了预设范围，上边界范围设置为R[(dmax- X1)/(dmax- dmin)] ，下边界范围设置为R[(X1- dmin)/(dmax- dmin)] 。 在tSGM 算法中[14]，代价聚集需要从代价矩阵上每个点周围8 个方向进行代价聚集，顾及视差变化、重复纹理及计算效率，将搜索窗口的大小预设为7 pixel×7 pixel。 如果匹配成功，得到最小和最大的视差；如果未成功，搜素窗口变大到31 pixel×31 pixel，并继续搜寻有效视差和最大、最小视差。 此外，使用搜索窗口包含的视差的平均值对当前金字塔级别的视差进行更新，并将有效像素和无效像素的最大视差搜索范围分别限于16 pixel 和32 pixel。 使用上面得到的最大值和最小值定义下一个金字塔图像的视差搜寻范围，在32 个像素内确定有效值，因此把搜索范围设置为[2×(X1＋d - dmin)，2×(X1＋d ＋dmax)] 。 在计算视差范围时，匹配代价矩阵用l × w×(dmax-dmin)表示，其中l为图像行数、w为图像的列数。 视差搜寻范围的减少简化了匹配代价结构，使用传统的SGM 和逐层优化SGM 的代价结构对比示意图如图4 所示。

图4 传统SGM 和逐层优化SGM 的代价结构对比图

当处理最高的金字塔等级时，由于没有比这更高的图层，因此没有初始视差估计值可用。 在这种情况下，把沿水平核线匹配图像中的所有像素作为潜在的对像，通过视差搜索范围的自适应计算匹配代价。 在针对不能匹配的金字塔等级的图像时，交换基本图像和匹配图像的位置，对估计的差异值进行一致化性检查。 另外，通过分布式算法过滤斑点，在视差图的边缘处预设最大值。 如果检测到边缘，使用低通平滑；如果未检测到边缘，则需要强制增强平滑。 在影像重叠区域内执行匹配时，像素从左右图像边界逐列传递到图像中心，直到检测到第一个成功匹配的像素。

1.3 生成三维模型

在获取测区地物的密集点云后，三维模型重建最后进行的是表面模型构网和纹理映射。 构网是将密集匹配生成带有法向量的点云进行空间划分、过滤，将离散的点构建成为不规则三角网，完成从点到面、从离散的点云到三角网模型的转变，此时模型没有色彩，称为白膜。 通过纹理映射建立彩色纹理图像与三角网结构的对应关系，为模型贴上纹理，完成三维模型重建。

2 结果与分析

为验证逐层优化SGM 在密集匹配和倾斜影像三维重建中的有效性，选取倾斜影像像对和倾斜影像数据集进行实验与分析。 第一组实验使用大疆精灵4P 无人机，镜头倾斜角度为45°，在距地面70 m 处采集山东建筑大学校门倾斜影像像对，分别使用传统SGM 和逐层优化SGM 进行密集匹配。 第二组数据使用山东建筑大学逸夫楼和济南市某山村的倾斜影像数据集，在两种匹配方法的结果上分别进行三维重建，对比分析重建出的建筑物、草地、林地区域。

使用大疆精灵4P 无人机采集山东建筑大学逸夫楼倾斜影像数据，如图5 所示，影像数量为247 张。 无人机的云台角度为45°，分别从前后左右等方向进行拍照，航带高度为70 m，单幅影像的像幅大小为5 472 pixel×3 648 pixel。 第二组数据采集方式不变，无人机为大疆精灵4RTK，区域内共布设6 个控制点，组内影像数量为470 张，航带高度为120 m，单幅影像的像幅大小为4 864 pixel×3 648 pixel。 第二组数据的三维重建流程为:(1) 获取无人机倾斜影像后，空三加密；(2) 在密集匹配阶段，使用软件SURE 提供的逐层优化SGM 策略，完成影像金字塔的构建、动态限定搜索范围、有效视差寻找及匹配代价的自适应计算，进而完成无人机倾斜影像的密集匹配，基于密集匹配成果，继续使用该软件对无人机倾斜影像的三维点云进行构网和纹理映射；(3) 得到实景三维模型。

实验使用的硬件平台为台式机，系统为视窗Windows 10 64 位操作系统，中央处理器为英特尔Intel i7-7700k、主频为3.6 GHz、内存为16 G、显卡为英特尔Nvidia Quadro P600。 对两组实验数据结果均进行定性分析，分别针对第一组数据的点云质量和第二组数据的模型精度进行定量分析。

2.1 倾斜影像密集匹配实验与分析

使用逐层优化SGM 对山东建筑大学校门的倾斜影像像对进行密集匹配实验，结果如图6 所示。由于使用了逐层优化策略，寻找到了更多的有效视差，因此在生成的密集匹配深度图中包含了更多的地物和地貌信息，细节部分如图6(c)和(d)中的1 处所示。 在视差图转换物方点云的过程中，更多的有效视差信息可以交会出更多的有效点云，进而可以提高物方点云的有效密度。 而由于错误的匹配视差会生成错误物方点云，如果没有及时处理，则会影响后续三维重建的精细化程度，因此仅有较高的有效点云密度是不够的，还要提高有效匹配点云的准确度。 逐层优化SGM 在有效的搜索范围内进行匹配代价的计算，可使匹配结果在错误匹配的地方得到改善，如图6(c)和(d)中的2 处所示。 除此之外，此方法在缩小初始视差搜索范围的同时，在代价矩阵和路径积聚时的计算时间也会相应减少(见表1)，相较于传统SGM 时间的12.8 s，改进后的逐层优化SGM 的最终匹配时间是8.64 s，匹配效率提高了30%。

图6 无人机倾斜影像像对SGM 结果图

表1 计算时间对比表

2.2 逸夫楼匹配点云和三维模型精度分析

2.2.1 匹配点云实验及分析

采用传统的和逐层优化SGM 对逸夫楼数据进行密集匹配，两种方法生成的点云效果如图7 所示，匹配点云数量和匹配时间见表2。 由于在金字塔影像间动态限定搜寻范围寻找有效误差，因此减少了由倾斜影像视角变化较大而产生的错误点。 由表2可以看出，在相同的空三结果下，由于逐层优化SGM 比传统SGM 匹配出的点云数量有所减少，因此在总体匹配时间上降低了22%，而且由图7 可以看出，重点建筑上并没有出现点云缺失，点云的总体质量并未下降。

图7 无人机倾斜影像像组数据匹配点云效果对比图

表2 点云匹配数量和时间对比表

为验证逐层优化SGM 的密集点云精度，采用均方根误差(Root Mean Square Error，RMSE)作为评价指标。 在点云精度的对比实验中，使用最可依赖值替代真值，通过计算匹配出点的位置与最可依赖值的位置间的偏差，对比匹配出的点云的离散程度。RMSE 值越小点云离散程度越小，精度越高。 选取相同区域相对平整的正射地面和竖立墙面进行精度对比实验，无人机倾斜影像匹配点云部分对比如图8 所示。 基于逐层优化SGM，高频信息并不会传递到较低一级的金字塔影像上，对于重复纹理、弱纹理及纹理突变区域具有更好的稳定性。 因此，由图8(b)可以看到，相较于传统SGM，基于逐层优化的SGM 在地面区域以及纹理比较单一的墙面区域均产生了相对较多的平整点云。

图8 无人机倾斜影像匹配地面点云部分对比图

选取投影坐标系下地面点z值和墙面点y值的平均值作为最可依赖值，地面和墙面点的两种算法的RMSE 结果见表3，点云数量和RMSE 的变化趋势如图9 所示。 可以看出，在地面上基于逐层优化的SGM不仅比传统SGM 的数量多，而且RMSE 值更小，精度更好。 而在墙面上，虽然取得了一样的RMSE 值，但是基于逐层优化SGM 的点云数量要高于传统SGM。在点云稳健的前提下匹配出了更多的可靠点，而更多的可靠点将会在点云融合构网过程中增强网的密度，提高网格面模型(Mesh)的精细化程度。 因此，逐层优化SGM 在匹配精度上优于传统SGM。

表3 相同区域内的地面和墙面的RMSE 表

图9 不同匹配算法的点云精度对比图

2.2.2 无人机倾斜影像三维模型实验及分析

基于传统SGM 和逐层优化SGM 生成的点云构建的三维模型整体及细节如图10 所示。 虽然整体差异不大，然而在细节处，由于逐层优化SGM 动态地限定了搜索范围，自适应地计算了匹配代价，对于重复纹理匹配效果较好。 因此，较传统SGM，其生成的建筑三维模型在建筑表面能够更加清晰的显示棱角和边线，如图10(c)和(d)所示。 由于匹配出了更多的可靠点参与点云构网，所以构网后的Mesh在一些细节处表现更好，如墙角线的结构更加竖直，如图10(d)中的1 处所示。 构网紧密的话，纹理映射的效果也会得到增强，如图10(d)中的2 处所示，在墙角线处，基于逐层优化SGM 重建出的Mesh 比基于传统SGM 重建出的更加笔直，重建效果更好。对拥有较多建筑物的城区进行区域三维重建时，使用逐层优化SGM 匹配倾斜影像，不仅能在更短的时间内匹配出更多的可靠点，加快三维重建的速度，而且更多的可靠点能够构建出更密的网格，进而提高建筑物平面及立面的精细化程度。 此外，在后续应用三维模型进行三维测图时，还能够提高人工目视采集房屋要素的准确程度。

图10 逸夫楼三维重建模型对比图

2.3 山村匹配点云和三维模型精度分析

2.3.1 匹配点云实验及分析

采用传统的和逐层优化的SGM 对第二组数据进行密集匹配，生成的点云效果对比图如图11 所示。 由于在金字塔影像间动态限定搜寻范围寻找有效误差，当处理最高的金字塔等级时，没有初始视差估计值可用，因此在边界处的点云处理不及传统半全局匹配点云。 点云匹配数量和时间对比见表4，可以看到，逐层优化SGM 的匹配时间降低了33%。虽然匹配时间受到一些边界点云影像的影响，但从整体上匹配效率得到了提高，而且在三维重建项目需要的核心区域，点云的质量并没有降低。 对于较大区域的三维重建项目，由于密集匹配时间得到缩短，整个三维重建的时间相应也会得到缩短，因此相同的集群配置可以在相同的时间进行更多的三维重建项目，进而降低了单个三维重建项目的成本。

图11 无人机倾斜影像像组数据匹配的山村特点效果对比图

表4 点云匹配数量和时间对比表

2.3.2 三维模型实验及分析

两种匹配策略生成的点云构建的三维模型整体及细节如图12 所示。 虽然直观的观看图12(a)和(b)，二者差异并不大，但是通过将模型放大查看建筑物的内部和平面细节可以看出， 由于传统SGM存在误匹配，构建的三维模型会出现纹理映射错误，如图12(c)所示。 而基于逐层优化的SGM，由于匹配出了更多的可靠点参与点云构网，因而构建的Mesh 在一些细节处表现更好，如图12(d)所示。 此外，在遮挡物较少的道路、裸露岩地和草地等区域，由于逐层优化SGM 是通过动态限定搜索范围寻找有效视差，能够减少错误匹配点，因此构网后的Mesh 拥有更高的精细化程度，从而使得根据三维模型纠正正射影像得到的真正射影像精度变得更高。然而，相较于建筑物与地面区域，对林木区域进行三维重建时，由于逐层优化匹配策略匹配出的有效点云较少，因此构建的Mesh 的精细化程度相应有所降低。

图12 山村三维重建模型对比图

为进一步定量地评价密集匹配策略重建出的三维模型的精度，依据CH/T 9015—2012《三维地理信息模型数据产品规范》[17]，在航测区域内均匀布设10 个特征点作为检查点，将全球定位系统—实时动态(Global Positioning System-Real Time Kinematic，GPS-RTK)测量出的坐标作为真实值，以三维模型上采集的坐标作为计算值。 高程检查点精度分析结果见表5。 三维模型的平面中误差为0.077 m，高程中误差为0.137 m。 在三维模型重建密集匹配效率提高了33%的前提下，基于逐层优化SGM 策略依旧满足1∶500(外业调绘)平面精度0.3 m 和高程精度0.5 m 的要求。

表5 三维模型检查点精度统计表 单位:m

3 结论

文章在无人机倾斜摄影三维重建密集匹配阶段采用逐层优化SGM，使用低分辨率影像的匹配结果动态限定了高分辨率影像上待匹配像素的视差搜索范围，并像素约束了传统SGM 的动态规划路径，自适应的计算匹配代价，并根据密集匹配成果视差图进行三维重建。 主要结论如下:

(1) 相较于传统的SGM，采用逐层优化SGM 进行像对匹配时，在减少无人机倾斜影像中地物遮挡、视差变化较大处的错误匹配的同时，密集匹配效率提高了30%。

(2) 基于逐层优化的SGM 在地面区域以及纹理比较单一的区域能够产生相对较多的平整点云，在三维重建过程中能够构建出更密集的Mesh 模型，提高三维模型重建的精细化程度。

(3) 基于逐层优化SGM 进行三维重建项目时，密集匹配效率能够提高22%～33%，继而能够提高三维重建的效率，降低三维重建的成本；同时，在建筑物和相对平坦的道路、草地等区域拥有更好的三维重建效果，而在林木及测区边缘区域的三维重建效果相对有所降低。