利用图割算法进行城市密集点云表面模型重建

马东岭，王晓坤，李广云

(1. 信息工程大学地理空间信息学院，河南 郑州 450001； 2. 山东建筑大学测绘地理信息学院，山东 济南 250101)

智慧城市的建立需要城市真三维模型作为数据基础[1]。现行建立城市三维模型的方法主要有手工建模、三维激光扫描仪建模、利用多视影像建模。手工建模是指利用类似于3ds Max等建模软件[2]以及最初的测量数据进行建模[3]。通常，手工建模具有模型美观、单体化好等优势，但建模速度慢、周期性长[4]，且有轻重区分，将不重要的模型建成白模型。因此，该种建模方式并不能够兼顾效率和质量，只能用于城市重要建筑的精细建模。为了提高建模效率，利用三维扫描技术进行三维重建已应用于多个领域[5]，如古建筑三维重建、边坡监测等。由于利用三维激光扫描技术进行三维重建需要像全站仪一样设站，因此该种建模方式对于大场景、大区域的复杂城市进行三维重建的效率依旧不能满足要求。近几年由于无人机(UAV)技术[6]的迅猛发展，无人机倾斜摄影以其高效便捷、成本低廉的优势成为城市区域摄影测量的主要手段。在这种情况下，基于倾斜影像的城市三维重建成为研究热点。而如何利用倾斜影像获得的密集点云来构建密集点云表面模型是基于倾斜影像进行三维重建的核心问题之一。

针对密集点云表面模型重建，国内外已有大量学者进行了相关研究。其中，文献[7]提出了一种基于体素的重建方法——Marching Cubes算法，该算法是在每一个体素中抽取相应的等值面的算法；文献[8]提出了一种基于物体中轴线转换来拟合表达物体表面的Power Crust的重建算法；文献[9]在IMLS方法[10]基础上提出了基于拟合代数球面的移动最小二乘表面重建算法——APSS算法；文献[11]提出了一种基于隐式曲面方程的重建方法——Poisson算法，该算法是通过隐式曲面方程的重建来解决表面重建问题；文献[12]在研究二维构网生长算法及现有空间三维构网方法的基础上，提出了利用空间三角形的法向量实现三维构网；文献[13]提出了一种无需对离散点集所对应的自由曲面进行分片投影的生长算法；文献[14]利用球面投影实现激光扫描点云数据的三维构网方法。针对城市建模特点，有学者专门研究符合城市特点的建模方法。针对城市模型存在直角拐角多、拐点不容易捕捉的问题，文献[15]提出了符合城市模型的区域生长算法；针对城市区域的地形特征，文献[16]提出了顾及地形的城市三维可视化方法。虽然以上方法能够完成对城市区域的三维重建，但是仍存在城市区域建模效率偏低、建模效果不理想等问题，因此寻找一种更为理想的表面模型重建方法迫在眉睫。本文以城市区域为例，利用无人机获取倾斜影像，并对倾斜影像进行预处理得到目标区域的三维密集点云，在此基础上利用图割算法对点云进行表面模型重建。本文提出的方法在城市区域密集点云表面模型重建中具有建模效果好、建模效率高的优势。

1 图割理论

图割算法是一种基于图论的能量优化算法[17]，该方法将目标构成一幅网格图的形式，并建立相应的能量方程，运用求最大流最小割的方式获取网格图的最优化分割来获取最优化结果。利用图割方法解决问题需将待分割的目标群体作为图割算法网格图的顶点[18]，并将待分割的目标群体的相关关系作为图割算法网格图的边。由于图割问题存在目标和背景两种关系，因此除了待分割的目标群体外，还有代表目标的汇节点和代表背景的源节点。利用图中边集合的一个子集作为割集合，其代价就是边子集中所有元素的权值的和。割集合即指将该集合中所有边打断会导致图割网格图的分开。如果一个割集合的元素所有权值之和最小，那么这个集合就称为最小割，也即图割的结果。根据福特-富克森定理，网路的最大流max-flow等于最小割min-cut。因此max-flow/min-cut算法就可以用来获得s-t图的最小割。

2 密集点云表面模型重建方法

本文将密集点云表面模型重建问题转换为利用图割方法选取最优四面体问题。由于利用图割方法解决问题需要建立相应的图结构，因此本文将密集点云构成的四面体作为图的节点，四面体之间的相邻三角面作为图的边。除此之外，还需要给定相应的节点权值和边的权值，其中节点的权值为表面可见性Evis(S)，边的权值为光泽一致性Ephoto(S)和表面平滑度Earea(S)。建立能量函数方程

E(S)=Evis(S)+λphotoEphoto(S)+λareaEarea(S)

(1)

式中，λphoto和λarea为相应的正权重。通过求解图的最小割来保证上述方程达到的最小值，进而选出最佳的表面四面体和对应的表面三角形。

2.1 表面可见性Evis(S)

在构建小四面体时，每个顶点需要保留一些可见性信息。若该点是通过多次合并获取的，则该点至少保留两个原始点的可视性信息。这个信息决定了节点可视性，如果某个四面体的顶点属于最终表面，那么应该在它所来自的视图中是可见的。这种情况说明，当一个顶点到摄像机中心的射线与一个标记为内侧的四面体相交时，它们就会发生冲突。因此，用Evis(S)表示当一条光线从摄像机中心的射线穿过在表面的四面体时，穿入穿出时就会发生能量变化。但是，这样的能量项不适合图割算法，因为它需要图中两个以上节点之间的复杂交互。相反，射线从内部射到相机中心，经过若干个三角面片，穿出可视面片时，能量发生变化，相机中心发出的光线与小四面体上的三角面的交点到该三角面相对的顶点的距离的函数作为四面体权值。表面可见性为

(2)

式中，v为光线与重建三角面的交点；D(v)为交点到该三角面相对顶点距离的函数。

2.2 光泽一致性Ephoto(S)

光泽一致性项Ephoto(S)是指给定表面S与所看到的不同输入图像的匹配程度[19]。因此，表面光泽一致性项为

(3)

式中，ρ(T)是指每个三角形的可视信息量的多少，由3个顶点共有的可视信息给定；A(T)为根据三角形面积给定的权值。

2.3 表面平滑度Earea(S)

通过减少单个三角形表面面积来改善表面平滑性。因此，表面平滑度能量为

(4)

在表面S上的三角形T，A(T)为根据三角形面积给定的权值，并通过A(T)给图中每一条边赋值。

3 试验与结果分析

试验数据采用城市地区的无人机倾斜影像数据。计算机硬件环境为Intel Core i3 CPU 2.4 GHz、软件环境为SGM和GodWork。首先，通过GodWork软件对无人机倾斜影像数据进行空三解算；然后，利用SGM算法对空三解算后的影像进行多视密集匹配，生成试验需要的三维密集点云；最后，利用本文提出的图割算法来构建密集点云表面模型。流程如图1所示。

3.1 空三解算及生成点云

将无人机倾斜影像加载到GodWork软件中，通过软件计算影像的空三结果，并将纠正后的影像及影像的空三结果导入SGM软件中。通过SGM灰度匹配的方法将空三测量产生的稀疏点云生成为三维密集点云。

3.2 给密集点云添加结构

本文方法是在三维点云中添加一些结构，同时高效地聚合顶点中的相近顶点，这是通过逐步构建三维点集的Delaunay三角剖分来完成的。三角测量的每个顶点不仅存储其位置，而且还保存其起源的关键点列表。每次从原始三维点云中选择一个候选点，就可以找到它在三角测量中最近的邻居点，计算两个三维点之间的投影误差。这可能会出现两种不同的情况：如果重投影误差在某个阈值以上，则将该候选点视为不同的点并插入到Delaunay三角剖分中；相反，如果误差小于阈值，则在Delaunay三角剖分中不插入该候选点，而是更新最近的顶点。过程如图2所示。

3.3 对密集点云进行表面模型重建

利用本文提出的方法对密集点云构成的小四面体的三角面进行选取，通过求解图割问题最小割的方式，获取哪些面属于密集点云表面模型，并将这些面重建为密集点云表面模型。

通过上述方法重建的模型表面如图3所示。

由试验结果可以看出，该算法获取的三维密集点云表面模型保持了建筑物的棱角，并且将建筑物的屋顶装饰提取了出来，极大地还原了真实建筑的几何结构信息。对于有树木遮挡的地方，通过本文方法重建的模型能够较好地表达出建筑和树木。为进一步验证本文方法的有效性，将本文方法与MVE表面重建方法进行了对比，如图4所示。

经过对比可以看出，MVE重建方法在环境复杂的区域重建效果不好，没有有效的区分出墙面和其他的噪音点。而本文方法可以在环境复杂的情况下，完整地表达城市区域建筑物的三维表面，清晰地重现建筑物的细节特征。对于点云分布散乱的情况，该算法识别模型表面能力强，可以有效地标识出墙面和散乱点云。本文方法通过更加合理的选取规则，尽可能避开了大三角形的选取，构建的密集点云表面模型更加符合现实状况。试验结果统计数据对比见表1。

表1 研究区域试验结果对比

通过对比试验结果统计数据，本文方法生成的三维点云表面模型比MVE重建方法生成的三维点云表面模型的节点和面更多，说明本文方法选取的三角面更小，细节表达更详细。相比于MVE重建方法的用时，本文方法用时更短，体现了本文算法建模效率高的特点。

通过试验发现，本文提出的城市密集点云表面模型重建方法的模型重建效果更理想，能够正确重建出建筑物、路面、树木等地形地物。通过该算法重建出的模型建筑细节丰富，建筑物、植被分界清晰，证明该方法建模效率高、可行性高、重建效果好。同时，由于该算法相比于其他方法的运行时间短，因此解决了城市密集点云表面模型重建中存在的建模效率低的难题，大大提高了无人机倾斜影像在城市三维模型重建中的实用性和使用价值。

4 结 语

本文根据城市密集点云的数据特性，提出了一种基于图割理论的城市密集点云表面模型重建方法。通过对无人机倾斜影像进行数据预处理获取目标的密集点云，然后对预处理生成的密集点云插入连接边生成四面体，并将四面体及相邻三角面构成图割问题，通过求解这个图割问题获取密集点云的最优表面模型。利用该方法对一个比较复杂的场景点云数据进行试验，完整地重建了该地区的密集点云表面模型。试验结果表明，该方法重建效果好、重建速度快，重建出的建筑物几何特征结构清晰。对比于其他方法，该方法在点云杂乱的地区也可以完成点云模型表面重建。由于倾斜影像存在较大的透视变形、分辨率差异以及密集点云存在噪声和遮挡等问题，如何进一步在密集点云表面模型重建中去除这些错误将是下一步研究的重点。