《测绘学报》
城市场景结构感知的网格模型简化算法
张春森1, 张会1, 郭丙轩2, 彭哲3
1. 西安科技大学测绘科学与技术学院, 陕西 西安 710054;
2.武汉大学测绘遥感信息工程国家重点实验室, 湖北 武汉 430079;
3.武汉讯图科技有限公司, 湖北 武汉 430079
收稿日期：2019-02-26；修回日期：2019-08-10
基金项目：国家自然科学基金重大研究计划（91638203）；陕西省自然科学基金（2018JM5103）
第一作者简介：张春森(1963—), 男, 博士, 教授, 研究方向为数字摄影测量计算机视觉与遥感应用。E-mail:zhchunsen@aliyun.com
摘要：针对二次误差测度（QEM）网格简化算法全局几何特征信息损失严重的缺点，提出一种具有结构感知功能面向城市三维模型重建的网格简化算法。该算法顾及城市影像中平面结构特征，以代理平面为全局特征约束条件，使模型在简化过程中全局结构特征更多地被保持，以利于多层次细节模型（LOD技术）、网格优化提速等模型后续操作。以倾斜摄影获取影像生成的初始三角网格模型为试验数据，采用所给算法对其进行网格简化并与QEM算法进行对比。结果表明：所给算法简化精度及简化效率均优于QEM算法。
关键词：网格简化 场景结构感知 三维重建 平面检测
Structure-aware simplified algorithm of mesh model for urban scene
ZHANG Chunsen1, ZHANG Hui1, GUO Binxuan2, PENG Zhe3
1. College of Geomatics, Xi'an University of Science and Technology, Xi'an 710054, China;
2. State Key Laboratory of Information Engineering in Surveying, Mapping & Remote Sensing, Wuhan University, Wuhan 430079, China;
3.Wuhan Xuntu Technology Co. Ltd., Wuhan 430079, China
Foundation support: The Major Research Plan of the National Nature Science Foundation of China (No. 91638203); The Natural Science Foundation of Shaanxi Province(No. 2018JM5103)
First author: ZHANG Chunsen (1963—), male, PhD, professor, majors in digital photogrammetry computer vision and remote sensing application. E-mail:zhchunsen@aliyun.com.
Abstract: Aiming at the shortcomings of global geometric feature loss caused by quadratic error measure (QEM) mesh simplification algorithm, a structure-aware mesh simplification algorithm for urban environment 3D model reconstruction is proposed. The algorithm takes into account the planar structure features in urban images, and uses the proxy plane as the global feature constraint in the simplification process, so that the global structural features of the model are more preserved during the simplification process, which is conducive to the refinement and progressive transmission of the model (LOD technology), grid optimization speedup and other model follow-up operations. In this paper, the initial manifold triangle mesh model generated by oblique photography is taken as the experimental data. The proposed algorithm is used to simplify the mesh and compare with the QEM algorithm, which experimental results show that the proposed algorithm has excellent simplification accuracy and simplified efficiency than the QEM algorithm.
Key words: mesh simplification scene structure aware 3D reconstruction plane detection
三维重建是数字城市建设的重要内容之一。近年来测绘领域发展的倾斜摄影技术克服了传统航空摄影只能从垂直角度拍摄的局限，以多角度、大范围、高精度、高分辨率的方式快速获取城市区域影像，在大规模并行计算的协助下可快速建立基于倾斜影像的三维模型，有效地降低了城市三维模型的建模成本，因此，倾斜摄影测量技术成为城市三维建模的首选技术[1-3]。然而，随着建模场景增大以及对模型细节精度要求提高，三维模型的数据量也显著增大，给计算机实时计算、传输、处理和显示三维模型带来了困难。网格简化一方面在保持目标结构信息的同时，可减少三维模型存储量，便于数据读取和利用；另一方面，也为生成多层次细节模型(LOD)打下基础[4]，达到根据视点与模型之间的远近距离动态调节简化比，降低场景复杂度，实现实时动态显示模型的效果，为后续网格优化[5-6]、纹理映射等操作奠定基础。
近年来，国内外学者在网格简化[7]方面作了许多卓有成效的工作。根据简化过程中删简掉的网格元素，可将网格简化[8-9]大致分为：基于顶点移去的网格简化、基于面合并和面折叠的网格简化、基于边折叠的网格简化[10]。其中应用最广泛、效果最佳的是边折叠简化策略。文献[11]提出了通过优化全局函数的边折叠网格简化方法。由于该算法在误差测度计算方面过于复杂，文献[12]对其进行改进，提出了局部二次误差测度的边折叠算法(quadric error metrics，QEM)。QEM算法以网格顶点到局部平面距离的平方作为误差测度。该方法计算过程简单、简化效率高、实用性能强，是最经典、应用最广泛的网格简化算法。
在经典的QEM算法基础上，国内学者也提出了多种有效的改进算法。文献[13]为提高QEM算法的简化效率，将三角网模型划分为一系列强独立区域，采用二次误差测度计算边折叠代价，将独立区域内的所有强独立边中的最小折叠代价作为强独立区域排序值，取各个强独立区域中折叠代价最小的边并行地进行折叠操作。文献[14]给出在QEM算法的基础上，在权值的计算中加入顶点法向量夹角与边长因子，以便更准确地反映出模型的细节特征，并利用边折叠的优势，引入基于八叉树的模型划分策略，在实现子模型简化的前提下，有效避免了子模型重组过程中的额外简化步骤。文献[15]针对简化过程中生成渐进网格时存在局部区域精度与效率平衡优化的问题，提出一种基于局部区域环间法矢夹角变换的半边折叠渐进网格简化算法；文献[16]在简化过程中引入折叠点的拉普拉斯坐标和原三角形法向量信息来更新折叠点位置；文献[17]针对简化仅依赖局部特征而造成对尖锐特征保持差的问题，首先计算曲面局部极点特征值，再叠加不同尺度下局部特征值的高斯差分获得特征的视觉显示度，将视觉显示度作为权值赋给每个二次误差矩阵，从而达到对显著度较高区域特征保持的目的。以上改进的QEM算法在简化过程中只改进了局部特征保持效果，没有顾及模型的整体结构特征，随着简化比的增大，模型的整体结构特征缺失更加明显[18]。
为了适应城市大场景三维模型重建，顾及城市影像中平面反映了大多数人工建筑物中诸如房顶、街道等的面状结构特征[19]，本文提出一种基于结构感知的城市场景网格模型简化算法，即在QEM算法通过二次误差测度维持局部特征的同时，通过平面检测算法提取代理平面，并以此作为简化过程中的全局特征约束条件对网格进行简化。试验结果表明：在相同的简化比下，本文算法能更好地保持模型的结构特征，尤其在较高简化比下，本文算法明显优于QEM算法，达到了较好的简化效果。
1 结构保持的场景网格简化方法
本文方法是在QEM算法基础上，通过二次误差测度[20]在维持局部特征的同时，根据平面检测算法提取代理平面，并以此作为网格简化过程中的全局特征约束条件参与网格简化。算法主要包括：在原始三维模型上通过区域增长检测代理平面、代理平面参与简化计算带权值的二次误差Q(e)，根据代理平面之间的关系给出结构保持原则，边收缩代价计算以及根据代价值确定边折叠顺序简化网格模型等步骤。总体技术流程如图 1所示。
| 图 1 本文技术流程 Fig. 1 Technique flow chart |
图选项 |
1.1 经典QEM算法
QEM算法[21]是在简化过程中以边作为删除对象，故归为边折叠简化类。该算法以每条边两端点到相关局部平面距离的平方作为二次误差测度确定边简化顺序，由简化比确定折叠边数量。如图 2所示，边折叠是将网格中一条满足条件的边V1、V2折叠，同时计算出一个新顶点V，并更新模型的几何拓扑关系，形成新的网格模型。
| 图 2 边折叠操作 Fig. 2 Edge collapse |
图选项 |
QEM算法的关键在于求解二次误差，因此定义任意平面的二次矩阵Q如式(1)所示
设图 2中点V1=[x1, y1, z1, 1]T的相关局部平面集合为plane(V1)，集合中所有平面的二次矩阵累加和为Q1，同理对于点V2=[x2, y2, z2, 1]T设其相关局部平面集合为plane(V2)，集合中所有平面的二次矩阵累加和为Q2。经过边折叠操作收缩到顶点V=[x, y, z, 1]T，更新拓扑关系之后，则简化后，网格二次误差为新顶点V到平面集合plane(V1)和plane(V2)中所有局部平面的距离累加和，将其称为该边折叠后代价C
对于边折叠简化算法，需要在边折叠之后找到新生成顶点的位置，即图 2中的V=[x, y, z, 1]T。由式(2)可知，新顶点的位置直接影响着边收缩代价，也决定了整个模型中边折叠的顺序，以及简化后的模型。
1.2 结构感知城市场景网格模型简化算法
在城市场景中，人工建筑多以平面作为最基本也是最重要的几何结构，因此可以用平面代表大多数人工建筑物如屋顶、街道等重建目标的全局结构特征参与简化。相较于QEM算法，本文算法在求解二次误差，确定边折叠顺序时作如下改进：首先检测出代理平面作为原始模型的全局特征，然后对所有边根据局部特征和全局特征关联一个权值，即带权值的二次误差Q(e)，在此基础上综合考虑结构保持原则，最终计算出网格模型每条边收缩后新顶点位置以及该边收缩的代价值，根据代价值确定边折叠顺序简化网格模型。
1.2.1 代理平面检测
代理平面检测首先根据三角面到其局部切平面的距离作为平坦度衡量标准，将原始模型中所有三角网格按照平坦度进行排序。依次选取平坦度指数，将指数最高且尚未被遍历到的三角面作为种子面进行区域增长。每扩散到一个三角面则计算其与本次区域增长的种子面之间的法向量夹角和两者之间的距离，判断是否同时小于给定阈值作为区域继续增长的判断条件，若均小于给定阈值则继续进行区域增长，否则停止。此外，为避免每个三角形都能成为一个单独的区域，每完成一次区域增长还需保证该区域的面积总和大于给定阈值才能作为一个完成的增长区域。
每次区域增长遍历到的三角面认为属于一个近似平面，取区域内所有网格顶点拟合为代理平面Φ，表示为ax+by+cz+d=0或Φ=[a, b, c, d]，其中n=[a, b, c]为该平面的单位法向量。值得注意的是原始模型中的三角面未必只对应一个代理平面，可能对应多个代理平面，也可能没有对应的代理平面。
为了使区域增长结果和代理平面更加直观，对原始模型和检测出的代理平面按照以下原则可视化[22-23]：
原则1：相邻代理平面赋予不同的颜色。
原则2：对于属于多个代理平面的三角面，将三角面的颜色设置为与自身法向量和代理平面的法向量最接近的代理平面的颜色。
原则3：对于不属于任何代理平面的三角面，将其颜色设置为灰色。
1.2.2 加权二次误差Q(e)
在经典的QEM算法中二次误差计算只考虑到边折叠后新生成顶点到相关局部切平面之间的距离并作为边折叠代价。本文算法引进代表城市模型全局特征的代理平面，在计算二次误差时兼顾全局轮廓和内部结构特征，计算新生成顶点到其相关的局部切平面、代理平面、两者的正则面的距离，提出一种新的加权二次误差Q(e)计算公式
Q(e)由维持模型的内部结构特征Qinner和维持整个模型的轮廓结构特征Qbdry两部分组成。其中参数μ∈(0, 1)。Qinner可表达为新生成顶点到局部切平面和多个代理平面的加权二次误差，Qbdry可表达为局部切平面和代理平面正则曲面的加权二次误差
式(4)为待折叠边e的二次误差计算公式，即本文式(3)中维持模型的内部结构特征Qinner和维持整个模型的轮廓结构特征Qbdry的计算过程。
其中Qinner可表达为新生成顶点到局部切平面和多个代理平面的加权二次误差, 维持模型的内部结构特征。T(e)代表待折叠边e所属原始模型三角面的集合，t代表集合T(e)中的任意一个三角面，|t|代表三角面t的面积。如图 3(a)所示，折叠边e属于三角面t1和t2，即T(e)={t1, t2}；λ∈(0, 1)是一个经验值常量；Qpt表示局部切平面pt(如图 3(c)所示)的Q矩阵；proxies表示三角面t所属代理平面集合，如图 3(b)所示黄色区域为三角面t1属代理平面集合，QΦ表示代理平面Φ的Q矩阵。
|
| 图 3 Q(e)求解过程相关元素解释 Fig. 3Q(e) interpretation of the relevant elements of the calculation process |
图选项 |
式(4)中Qbdry可表达为局部切平面和代理平面正则曲面的加权二次误差, 维持整个模型的轮廓结构特征。其中，e′表示原始三角网模型的边界边，如图 3(d)所示三角网模型中，标注的紫色边只属于一个三角面则认为该类边为三角网模型的边界边，集合E∂κ表示原始三角网模型的边界边集合；|te′|代表边界边e′所属的原始模型中唯一三角面的面积；Qe′, te′代表包含边界边e′的三角面te′的正则面(如图 3(e)所示)的Q矩阵；E∂κ\Φ表示原始三角网模型代理平面中包含的边界边集合；Qe′, Φ代表包含边界边e′且垂直于其所在代理平面的Q矩阵。
Qinner项的作用是维持模型的内部结构特征。前一项维持原始模型在简化过程中到其局部切平面的距离变化不大，因为局部切平面代表了模型内部局部特征，因此这一项意义为控制简化前后模型内部局部变化不大；后一项维持简化前后模型到代理平面之间的距离变化不大，因为代理平面代表了模型内部全局特征，因此这一项的意义为保持简化后模型内部的全局特征。
Qbdry的前一项维持原始模型的大致轮廓，防止过度简化，如若是一张近似平面化成一个点，这种操作不能出现在网格简化过程中；后一项是维持代理平面的形状，因为代理平面代表模型整体大致轮廓，也有边界并不是一个无限制的平面，因此简化后要保持代理平面的整体结构变化不大。
1.2.3 结构保持规则
QEM算法每次折叠一条边，就会删去两个顶点、两个三角面及一条边，并生成一个新顶点。一系列操作之后不但影响了模型自身点、线、面的拓扑关系，也可能影响该模型代理平面的拓扑关系[24-25]。而代理平面的拓扑关系代表了全局结构特征应禁止发生改变。因此本文算法添加了以下两种结构保持原则，将折叠后会破坏这两种原则的边的权值强制设置为一个极大值，不能被折叠。
(1) 代理平面图保持原则。如图 4(a)所示，代理平面无向图中P0和P1之间没有连通关系，若将v0和v1所组成的边收缩之后，形成如图 4(b)所示的新的代理平面无向图，两代理平面相互连通，破坏了原模型代理平面拓扑关系，因此该边禁止折叠。
|
| 图 4 代理平面图保持原则 Fig. 4 Graph preservation rules |
图选项 |
(2) 代理平面保持原则。由于代理平面是由多个原始模型中的三角面限制的有限平面，边折叠过程会造成三角面个数的减小，引起代理平面改变。如图 5所示，代理平面P1为正方形，若将v0和v1所组成的边收缩之后，P1形状改变为三角形，破坏了代理平面的形状特征，因此规定代理平面无向图中任意一个代理平面包含的顶点的个数小于阈值μ则不能进行边收缩。
|
| 图 5 代理平面保持原则 Fig. 5 Proxy preservation rules |
图选项 |
1.2.4 边收缩代价
边折叠操作代价如式(2)所示，因此新顶点位置的选取直接决定了边折叠代价的大小。对比多种新顶点位置确定方法，本文采用文献[26-27]中的方法，将Q(e)=(Q1+Q2)分解
若A为非奇异矩阵，则新顶点位置V=A-1f; 若A为奇异矩阵，该矩阵不存在逆矩阵的情况下新顶点位置为收缩边的中点
计算原始网格模型中所有边的初始代价值，按照升序进行排列，优先折叠代价值最小的边，确定新的顶点，再重新计算边折叠代价值，再次进行排序重复操作。由于实现过程中包含了大量的旧边删除和新顶点插入的操作，且每次都折叠代价值最小的边，因此在实现过程中为了提高效率将边折叠代价按照堆排序算法[28]后，以顶堆的数据结构存储，确定简化边序列。
2 试验结果与分析
为了验证本文算法的可行性及有效性，在Microsoft Visual C++及CGAL库环境下将算法编程实现。利用无人机拍摄的135幅山东威海某区域倾斜影像，通过图割构网算法生成网格模型(图 6)，并以此作为网格简化原始数据。采用本文算法对其进行简化，其中计算加权二次误差Q(e)时，参数λ取值0.5，代理平面保持原则中阈值μ=4，并与QEM算法得到的简化结果进行对比。图 7(a)为采用本文算法对试验区三维网格模型检测出的代理平面，图 7(b)-(d)为检测出代理平面局部放大图。从显示结果可以看出：本文算法对试验区建筑物的立面、屋顶及平坦的街道等面状特征都能很好地检测出来。
|
| 图 6 试验区网格模型 Fig. 6 Test area mesh model |
图选项 |
|
| 图 7 代理平面检测 Fig. 7 Proxy plane detection |
图选项 |
图 8为试验区网格模型不同程度的简化结果，其中图 8(a)为原始网格模型，图 8(b)、(d)、(f)为利用本文算法简化比分别为10%、50%、99%的简化结果，对应的图 8(c)、(e)、(g)为使用QEM算法简化比分别为10%、50%、99%的简化结果。
|
| 图 8 简化结果对比 Fig. 8 The comparison of the proposed model |
图选项 |
从视觉效果看，在简化程度比较小的情况下本文结构感知算法和QEM算法都能够达到很好的简化效果，其中本文算法局部和全局特征更加明显；当简化程度增大以至模型要求达到极简的情况时，本文结构感知算法相较于传统的QEM算法效果显著，即对模型大程度的简化依旧能保持模型的整体结构特征。
采用文献[29-30]中Metro4.7工具测量原始模型与简化模型间的豪斯多夫距离作为客观评价两种算法的简化效果标准，对比结果如表 1所示。图 9是根据表 1给出的可视化折线图。
表 1 不同方法简化模型误差对比Tab. 1 Error comparison of simplified models by different methods
| 简化比/(%) | QEM算法 | 本文算法 |
| 10 | 0.001 72 | 0.001 66 |
| 20 | 0.005 74 | 0.004 93 |
| 30 | 0.007 31 | 0.005 83 |
| 40 | 0.032 00 | 0.007 97 |
| 50 | 0.034 08 | 0.010 63 |
| 60 | 0.035 12 | 0.013 41 |
| 70 | 0.043 69 | 0.028 45 |
| 80 | 0.065 22 | 0.040 39 |
| 90 | 0.113 70 | 0.064 14 |
| 99 | 0.485 02 | 0.276 01 |
表选项
|
| 图 9 不同方法简化模型误差对比曲线 Fig. 9 Error comparison curves of simplified models by different methods |
图选项 |
由图 9可以看出：当简化程度较小时，两种算法的简化误差基本上相差不大，随着简化比的加大简化误差明显增大，尤其当简化比大于80%以后，本文算法表现出明显的优势。表 2为两种不同方法简化时间对比，可以得出：在相同简化比下，本文算法较QEM算法更加高效。综合表 1与表 2结果可以看出：本文所给算法的简化精度与速度均优于QEM方法，是一种有效的三角网格简化算法。
表 2 不同方法简化时间对比
Tab. 2 Different methods simplify time comparison
简化比/(%) | QEM算法 | 本文算法 |
10 | 0.001 | 0.001 |
20 | 2.513 | 2.009 |
30 | 5.903 | 4.216 |
40 | 8.158 | 7.402 |
50 | 11.571 | 10.092 |
60 | 14.366 | 13.117 |
70 | 18.506 | 16.507 |
80 | 22.095 | 18.373 |
90 | 25.875 | 21.691 |
99 | 30.684 | 24.735 |
表选项
3 结论
由于城市环境下的三维模型构建，带有平面的网格简化模型更有助于对场景的理解以及后续应用的部署[31-32]，本文在QEM算法基础上提出一种感知全局特征的网格模型简化算法，利用原始三角网格检测出来的平面代理全局特征，将其几何和结构特征添加到QEM算法边收缩简化过程中。试验结果表明，本文提出的结构感知算法相较于传统的QEM算法更能够在简化过程中保持模型的局部和全局特征，简化前后误差更小，是一种有效的三角网格简化算法。
【引文格式】张春森, 张会, 郭丙轩, 等. 城市场景结构感知的网格模型简化算法. 测绘学报，2020，49(3)：334-342. DOI: 10.11947/j.AGCS.2020.20190068
联系客服
