用于构建带3D线条的网格优化的高效多目标动态规划方法

《ISPRS JOURNAL OF PHOTOGRAMMETRY AND REMOTE SENSING》：Efficient multi-objective dynamic programming for building mesh optimization with 3D lines

　　

李晓彤|魏东|张永军|万毅|郭浩宇|王光帅

武汉大学遥感与信息工程学院，中国武汉430079

摘要

具有精确边缘的3D网格对于建筑物的可视化和结构理解至关重要。目前，3D网格的构建主要基于3D点。尽管3D线可以对边缘和平面提供有效的约束，但在现有研究中它们受到的关注有限。本文提出了一种新颖的动态规划（DP）方法，用于高效优化包含3D线的现有建筑网格，以确保局部拓扑一致性，并消除全局重新三角剖分的需要。为了实现精确的重新三角剖分，我们提出了一种自适应加权策略，在DP过程中优化多个目标。为了提高重新三角剖分的效率，我们引入了一个概率决策模型来减少DP中的冗余优化过程。对比实验表明：（1）使用DP进行三角剖分能够 achieve 最佳的几何精度，并且对我们的自适应加权策略具有抗噪能力；（2）我们的概率决策模型将DP的运行时间减少了约25%，同时对精度的影响很小。我们工作的源代码可在以下链接获取：https://github.com/XiaotongLi123/mesh-optimization-with-3D-building-lines。

引言

由于3D网格具有清晰的拓扑结构和经济的存储要求，它在摄影测量和计算机视觉中是3D对象的主要数字表示形式（Henderson等人，2020年）。具有精确边缘和平面的3D网格对于建筑物的可视化和结构理解至关重要，从而促进了数字城市发展和智能城市管理（Biljecki等人，2015年）。目前，3D网格的构建主要依赖于3D点（Kazhdan和Hoppe，2013年；Labatut等人，2007年）。然而，来自多视图图像（Hirschmuller，2007年）或LiDAR传感器（Wang等人，2018年）的点特征在表示建筑物时存在以下弱点：（1）由于这些区域的多视图立体ognosis性能较差或LiDAR点分辨率低，它们在表示建筑物边缘时通常不够精确；（2）在表示平面结构时过于密集，导致存储成本较高。这些弱点会被3D网格继承。

3D线是城市场景中常见的几何特征。它们可以作为锐利边缘和平面结构的约束，以克服基于点的3D网格的缺点。尽管有一些方法可以从多视图图像中高效重建高质量的三维线（Guo等人，2024年；Wei等人，2024年），但很少有研究关注利用3D线来提高网格质量。Guo等人（Guo等人，2024年）和Langlois等人（2019年）仅使用3D线构建了建筑网格，这忽略了3D点在表示细节和不规则结构中的关键作用。为了结合点和线性特征以获得更好的重建效果，Zhou等人（2019年）和Hofer等人（2014年）将3D线上的采样点与多视图立体模型的点云融合起来，以优化边缘质量。然而，这些改进仍然有限，因为他们的采样策略未能充分利用3D线的边缘约束。传统的基于点和线的构建方法首先将这两种特征结合起来对整个3D空间进行Delaunay三角剖分，然后利用图割算法进行表面提取（Sugiura等人，2015年）。然而，这种全局重新三角剖分策略难以用于现有3D网格的高效优化。此外，它还需要精确的相机位置来确保表面提取过程中的可靠可见性分析。

在本文中，我们将3D建筑线嵌入到局部网格中，以优化边缘和平面的表示。我们使用动态规划（DP）作为优化方法，它在使用点进行3D网格三角剖分方面已被证明是有效的。以前的工作在DP过程中优化了单一标准，如周长（Klincsek，1980年）、面积（Barequet和Sharir，1995年）或二面角（Barequet等人，1996年）。然而，由于不同的目标可以提供不同类型的约束，因此联合优化对于使用DP进行准确和通用的三角剖分是可取的。为了实现这一目标，一些研究依次优化不同的目标（Liepa，2003年；Wei等人，2010年）。然而，这些方法显然不是最优的，因为它们未能实现真正的联合优化。在本文中，（1）我们提出了一种多目标同时优化过程，以提高DP的三角剖分性能。核心思想是一种自适应加权策略，可以根据DP过程中的反馈迭代调整，从而实现多个标准的平衡优化。此外，DP中耗时的回溯过程限制了大规模场景中重新三角剖分的效率。因此，（2）我们引入了一个概率决策模型，以适应性地进行回溯过程。它利用共面一致性来估计概率并在DP过程中更新它们。在合成数据和建筑场景上进行的实验展示了我们方法的三个贡献：

我们提出了一种新的优化框架，用于增强建筑物的锐利边缘和平面结构，该框架利用现有网格而无需全局重新三角剖分。

(2)

我们引入了一种自适应加权策略，在DP过程中全面优化多个目标，这在以前的研究中尚未得到很好的解决。

我们引入了一个概率决策模型，以适应性地进行回溯过程，从而使DP过程更加高效，同时不影响三角剖分的精度。

图1展示了我们方法的流程。它需要3D线和现有网格作为输入。对于每条3D线，我们找到受约束的局部网格，称为线支持网格（LSM）。然后使用所提出的DP来使用3D线重新三角剖分局部网格。在本文的其余部分，我们首先讨论了不同几何原语的网格构建方法（第2节）。接着，我们介绍了寻找LSM的方法（第3节）以及我们使用高效多目标DP进行重新三角剖分的方法（第4节）。第5节我们利用合成数据和真实世界数据进行实验以展示性能。最后，第6节总结了本文。

章节摘录

基于点的网格构建

传统的摄影测量和计算机视觉技术使用点作为构建3D网格的原语。这些基于点的方法可以根据它们使用的先验进行分类（Huang等人，2024年）。基于三角剖分的方法中最经典和常用的是Delaunay三角剖分（Edelsbrunner和Shah，1994年），它使用规则的三角形面构建网格。这个经典且受欢迎的框架首先从输入点直接生成Delaunay四面体，然后

LSM搜索

本节讨论了给定3D线时搜索LSM的方法。如图1(a)所示，该过程首先将3D线投影到网格上以初始化LSM进行优化。然后我们使用共面一致性约束的贪婪增长策略来确定3D线的最大优化范围。当使用多条3D线时，LSM可能会相互重叠。因此，我们提出了一种迭代收缩策略来最小化误报并完善结果。

使用DP进行重新三角剖分

如图1(b)所示，给定一条3D线后，我们获得LSM的轮廓。然后我们用3D线将LSM分成两部分，可以通过联合最小化周长和二面角之和来使用DP框架解决重新三角剖分问题。

实验

如图9所示，我们使用了四个合成数据集、两个来自（Wei等人，2022年）的大规模城市场景数据集以及五个来自都柏林（Laefer等人，2017年）和朱等人（2023年）的具有高度复杂几何形状的建筑物来评估所提出的算法。这四个合成数据集包括一个半径为50米的正二十面体、一个边长为100米的立方体以及两个来自Luo等人（2022年）的简单建筑物模型。合成数据集#1的输入网格和

结论

在本文中，我们提出了一种基于DP的方法，用于高效优化包含建筑线条的现有网格，以更好地表示建筑物边缘和平面。它保持了局部拓扑一致性，并消除了全局重新三角剖分的需要。在优化过程中，我们引入了一种自适应加权策略和HT模型以实现精确和高效的重新三角剖分。在合成和真实世界数据集上的实验验证了我们方法的有效性

CRediT作者贡献声明

李晓彤：撰写——原始草稿、可视化、软件、方法论。魏东：撰写——原始草稿、方法论、资金获取。张永军：撰写——评审与编辑、监督、资金获取。万毅：撰写——评审与编辑、软件。郭浩宇：撰写——评审与编辑、软件。王光帅：数据管理。

利益冲突声明

作者声明他们没有已知的可能会影响本文所述工作的财务利益或个人关系。

致谢

本工作得到了国家自然科学基金（项目编号42301499）和天津科技研究与发展规划（项目编号TKL2025B05）的支持。此外，我们还要感谢武汉大学的黄子谦和湖南城市大学的朱先章