滁州学院地理信息与旅游学院，安徽 滁州

收稿日期：2021年5月11日；录用日期：2021年7月12日；发布日期：2021年7月21日

摘要

近年来人们对三维模型的需求与日俱增，三维激光点云技术的兴起为此提供了一个新的方向。然而，目前基于3D点云的建模工作大都通过人工交互的方式进行，因此如何利用3D点云数据实现三维模型的自动构建是目前研究的热点。本文提出一种基于3D点云的规则化模型自动构建方法：首先使用优化后的RANSAC算法对数据进行平面分割，然后提取出每个平面的轮廓线并进行分段；最后用线段中的关键点进行三角化，完成对三维模型的构建。实验结果表明，该方法可以完成独立平面和规则物体的三维模型自动构建，并可以灵活地与其他方法相结合以帮助构建物体中的规则部分，对规则物体的有较好的还原效果且所需三角面少。

关键词

点云，滤波，平面分割，三角化，建模

A Method of Building a Regularized Model Automatically Based on a 3D Point Cloud

Ge Gao, Peng Li^*, Zhen Zhang, Pengcheng Xu

School of Geographic Information and Tourism, Chuzhou University, Chuzhou Anhui

Received: May 11^th, 2021; accepted: Jul. 12^th, 2021; published: Jul. 21^st, 2021

ABSTRACT

In recent years, people’s demand for 3D models is increasing day by day, and the rise of 3D laser point cloud technology provides a new direction for this. However, most of the current modeling based on 3D point cloud is carried out through human interaction, so how to use 3D point cloud data to realize the automatic construction of 3D model is the focus of current research. This paper proposes a method of automatic construction of a regularized model based on 3D point cloud: first, the data is split flat using the improved RANSAC algorithm, then the outline of each plane is extracted and segmented, and finally the three-dimensional model is constructed by triangulation by the key points in the segment. Experimental results show that the method can complete the automatic construction of three-dimensional models of independent planes and regular objects, and can be flexibly combined with other methods to help build the rule part of the object, which has a good reduction effect on the regular object and requires fewer triangular faces.

Keywords:Point Cloud, Filter, Plane Segmentation, Triangulation, Modeling

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

经过近几十年的飞速发展，三维激光扫描技术在不断提高精度的同时也大幅度降低了成本，现已广泛地应用于地形测绘 [1]、自主导航 [2]、文物保护 [3]、逆向工程 [4] 等领域。在这些研究中，许多都依赖于激光点云的模型构建，凭借着获取速度快、精度高、自身携带空间信息、无需接触目标等优势，基于激光点云的自动模型构建将极大地提高三维建模的效率，减轻劳动者的负担。

许多学者都对使用基于点云的模型构建做出了研究：张珍铭 [5] 使用Delaunay三角化的方法对点云进行模型构建，并在此基础上提出了一种区域增长算法，通过构造影响域提高了筛选最优三角片的效率。刘涛 [6] 使用了泊松重建算法对点云进行了构建，并利用双三次样条插值方程解决了泊松重建中的空洞问题。此类方法多用于曲面重建，但如果模型中存在平面部分，这部分将会出现顶点过多的现象，导致重建效果差。Nan [7] 等人使用改进的RANSAC算法提取出原始数据中的平面并规则化，最后将问题转化为二进制标记问题从而挑选出合适的候选平面，拟合出最终的模型。这种方法可以很好地还原出物体的大致形状，并可以修复原始数据中缺失的部分。类似的使用平面相交关系进行规则模型构建的方法一般需要模型必须为包围盒结构，且对数据本身有一定的要求。闫阳阳等人 [8] 使用了交互式的建模方法，首先对点云数据进行下采样并剔除噪声点，再将处理后的点云数据导入到AutoCAD工具中绘制线框图，最后导入到3dsMax软件中进行三维模型构建，虽然最终的效果较好，但这种交互式的方法并没有实现点云建模自动化，在效率和人力节省方面提升有限。目前效果较好的基于点云的模型自动构建方法往往都只适用于规则模型或曲面模型中的一种。基于点云的自动化模型构建仍需要不断研究以得到更广泛的应用。

针对规则对象的还原以及模型的自动化构建，本文提出一种全自动的模型构建方法：首先通过改进后的RANSAC算法将预处理后的点云数据分割为平面集合，随后提取它们的边缘点分割为线段合集并用端点进行描述，接着在对这些端点进行筛选后描述其对应的平面多边形，最后对多边形进行三角化完成模型构建。由于本方法在构建时会分解出物体中的所有平面并逐一进行模型构建，因此可以灵活地和其他方法相结合，帮助构建物体中的规则部分。整个模型构建的过程可以实现自动化且对平面对象有较好的还原度。图1展示了此方法的模型构建流程。

图1. 技术流程

2. 构建过程

2.1. 基于优化RANSAC算法的点云平面提取

为了能够对单一平面进行构建，需要提取出模型中的所有平面，然后逐一对这些平面进行构建。在进行平面提取时，本文使用了RANSAC算法，并针对性地对其进行了优化。RANSAC算法最早由Fischler和Bolles提出 [9]，Ruwen Schnabel等人又在其基础上提出了提取点云数据规则部分的方法 [10]。此方法假设数据由符合偏差阈值的局内点和超过阈值的局外点组成；使用时首先需要设定好几何模型S(1)、偏差阈值 以及迭代次数。随后随机抽取不在同一直线上的若干点以确定平面模型 中的参数，并通过式(2)计算各点到 的距离 ，统计不同的模型中Dp < ϵ的点个数，最终在迭代结束后将符合点数最多的平面作为最优内点取出。在余下的外点中重复上述过程，直到完成所有平面的提取。

$ax+by+cz+d=0$ (1)

$D_p=\frac{\left|a{x}_i+b{y}_i+c{z}_i+d\right|}{\sqrt{a^2+b^2+c^2}}$ (2)

由于RANSAC算法会提取出所有符合模型的点，有时会错误地提取到不属于当前目标面的点，这一问题不仅会影响当前平面的正确性，还可能会影响后续平面的提取。不属当前目标平面的“问题点”在分布上较本体而言更为稀疏，根据这一特点，本文在得到最优内点时会对每个点在其半径为R的范围内包含点的个数n进行判断，如果n小于预设阈值N，便可以判断该点为“问题点”，将其归还到“外点”之中。图2对比了直接采用RANSAC算法和经过优化后的效果，可以看到，过度分割的问题得到了解决。

图2. 问题平面处理

2.2. 边缘线提取

得到分割平面后，通过判断采样点与邻近点所构成的法向量夹角大小对平面的边缘点进行提取 [11]，先对点云数据进行法向量估计，再利用估计出的法线值进行角度计算，通过设定角度范围对边缘点进行提取。在进行法向量估计时，首先通过建立kd树进行k邻域搜索 [12] 确定一个点集，用这些点组成的拟合平面的切面法线作为待测点的法向量。再使用主成分分析法 [13] 对拟合平面进行计算，通过式(3)计算出当前点的k邻域点集 $P_i$ 的重心 $\bar{P}$。随后通过式(4)和式(5)求出协方差阵C和特征向量 ${\bar{V}}_j$，其中，λ_j为协方差阵的第j个特征值。

$\bar{P}=\frac{1}{K}{\displaystyle \underset{i=1}{\overset{K}{\sum }}{P}_i}$ (3)

$C=\frac{1}{K}{\displaystyle \underset{i=1}{\overset{K}{\sum }}\left(P_i-\bar{P}\right){\left(P_i-\bar{P}\right)}^T}$ (4)

$\text{C}\cdot {\bar{V}}_J={\lambda }_j\cdot {\bar{V}}_J$ (5)

得到每个点的法向量后，选取一点X与其k邻近点 $K_i\left(i=0,1,\cdots ,k-1\right)$ 组成参考点集R，将点集R向其切平面进行投影得到 和 ${K^{\prime }}_i\left(i=0,1,\cdots ,k-1\right)$。定义向量 $\stackrel{\to }{X^{\prime }{K^{\prime }}_1}\left(i=0,1,\cdots ,k-1\right)$，求该向量与其法向量的夹角 ${\alpha }_i\left(i=0,1,\cdots ,k-1\right)$。设定角度阈值 并根据式(6)对边缘点进行判断并提取。提取效果如图3所示。

$\{\begin{array}{l}{\alpha }_i>{\alpha }_{th},边缘点\\ {\alpha }_i<{\alpha }_{th},非边缘点\end{array}$ (6)

图3. 地面边缘点提取效果

2.3. 顶点提取与排序

顶点提取的目的是提取顶点对平面进行描述，但是仅有顶点信息难以对复杂平面进行描述，同时还会失去对去曲线的表达能力，因此本文首先使用与平面分割相似的优化RANSAC算法将边缘点分割为线段合集，再用每条线段的端点间的关系找到各个线段间的位置信息，最终提取出带有顺序关系的顶点。经过分割后，边缘线中的直线部分将在转折处被打断，而曲线部分将被切割为若干份，每一份点都近似于一段直线，分割效果如图4左所示。

拆分出的线段之间是没有相邻顺序关系的，因此还需要对这些由点构成的线段进行排序。但在此之前，需要先对公共边问题进行处理。在平面提取中，如果存在两个平面有一个公共边时，先提取出的平面会带走属于公共边上的点，后提取出的平面将不包含这个公共边。如图4右所示，由于绿色点所在面被优先取出，导致红色面在公共边部分不能取到点。这将导致后提取出的平在公共边位置的边是有偏差的。由于替代边提取出的端点与公共边提取出的端点间的距离会远小于其他端点，因此可以按照平面的分割的顺序，依次计算所属相邻两次分割平面的所有端点之间的距离，当存在两个点之间的距离近似于相邻点的平均距离，便可以判定这两个点由一个是因为由于公共边问题而产生的，将这两个端点中属于后分割出平面的端点替换成属于先分割出平面端点的坐标值。

完成端点校正后便可以进行端点的筛选和排序。限定一个平面范围，从任意一条线段的其中一个端点P₁开始，P₁所在线段的另一端端点为P₂，在其余点中寻找与P₂最近的点P₃，再从P₃开始，不断重复上述步骤，直到P_n = P₁，这时依次连接P₁到P_n所对应的点便可以描述该平面。与平面切割中的公共边问题类似，相邻线段也存在着公共点问题，所以在上述的排序过程中，当发现存在两点间的距离接近于线段中点的平均距离时，需要对比这两点所属线段的长度，删除所属线段较短的点。完成上述步骤后，剩余的有顺序关系的点集便可以完成当前平面的描述。

图4. 边缘点分割和公共边问题

2.4. 三角化

计算机在进行模型绘制时是以三角面为单位的，常见的三维模型格式也大都是基于三角网格描述，因此需要对排序后的端点所描述的平面进行三角化，方便模型的输出。简单的凸多边形只需要任意选取一个顶点依次连接其他的点便能完成三角化，但对于凹多边形这样做有可能会破坏其结构。可以将凹多边形分割为若干个三角形和一个凸多边形 [14] 以完成三角化。以图5为例，具体步骤为如下。

找出多边形中的凸顶点(1, 2, 3, 6, 7, 8)和凹顶点(4, 5)，选取一个凸点和它的两个邻点，判断这三点构成的三角形中是否存在其他点，如果存在则选取下一个凸点进行判断，直到找到某一个顶点和其邻点构成三角形中不包含有其他点。如图5上左，凸顶点2与其相邻的两个顶点内不包含其他点，将这三点构成的三角形取出，删除顶点2。寻找新图形中的凸顶点(1, 2, 5, 6, 7)和凹顶点(3, 4)，找到与临边构成三角形内不含有其他点的凸顶点，取出它与邻点构成的三角形并将其删除，重复上述找符合凸点和提取的步骤，直到新图形中没有凹顶点的存在，图5上右、下、演示了这一过程。在最后剩余的凸多边形中，任意选取其中一个顶点依次连接该多边形的其余点，完成三角化。

这种方法也可以用于内有空洞的多边形，当每个凸点和其相邻点所构成的三角形内都包含有其他多边形时，便可以断定后者实际上是前者多边形中的空洞，这时可以将空洞内中的其中一点与外边缘上的一点链接，将含有空洞的多边形转化为没有空洞的凹多边形。以四边形中包含四边形空洞为例，如图6所示，可以将空洞内和边缘中的一点进行连接，将这条连接线视为两条重叠在一起的边，图中的序号依次标记了这些点的顺序。

图5. 三角面切割过程

图6. 空洞多边形顶点编号

3. 实验结果与分析

为了验证方法的有效性，实例选用板凳、床、桌子及两座建筑物五组点云数据分别使用Delaunay三角化方法和本文方法进行建模构建测试，五组数据均是以平面作为主体。在进行Delaunay三角化之前已经对原始点云进行了预处理。原始点云的点数与尺寸信息以及两种方法构建出的模型信息如表1所示。

表1. 模型参数及精度

五组点云数据的构建效果如图7所示，图中由上到下分别为原始点云，本文方法构建模型和Delaunay三角化方法构建模型。

图7. 模型构建效果

可以看出，在单独使用时，本方法可以很好地对规则物体进行还原，且对于如图7中桌子这类由单独平面组成的物体也能很好地还原，所需三角面少，能够保证一定的精度。此外，由于本文方法可以对独立平面进行模型构建，这使得本方法可以方便和其他不能很好构建平面的方法形成互补，在使用结合方法时，可以先使用RANSAC算法将模型中的平面进行分离并使用本文方法对这些单一平面进行模型构建，随后使用其他方法对剩余的点云数据进行构建，最后将两部分模型合并，得到最终的模型。

以图8中的点云数据为例，他们都是由规则部分和曲面部分构成，现有的全自动建模方法为了保证构建效果一般采用三角网方法对其进行构建，在构建过程中，模型的规则部分也会由大量三角网组成，这不仅使最终得到的模型数据量过大，还增加了模型构建所需的时间，若原始点云质量不佳，规则部分的重建效果也难以得到保证。图8中为使用了本方法结合Delaunay三角化所构建出的模型。图8右的模型仅使用了Delaunay三角化对其进行构建。可以看到，在使用结合方法进行模型构建时，本文方法很好地对模型的规则部分进行了还原，而Delaunay三角化完成了其他部分的构建，两种方法分别发挥了各自的优势，使得最终得到的模型在数据大小和构建效果相较于仅使用单一方法更数据量更小，效果更好。

4. 结论

本文提出了一种新的点云自动化建模的方法，主要步骤包括了点云下采样，离散点剔除，平面分割，

图8. 模型构建效果对比

边缘线提取与分割，端点处理和多边形三角化。其中平面分割使用了经过优化的RANSAC算法，并根据该算法可能会出现的问题进行了相应处理，尽可能地还原了物体的原始面貌。实验结果显示，此方法可以较好地对规则物体和独立平面进行重建，且所需三角面数较少。此外，由于本文方法可以进行单个平面的构建，因此可以灵活地将本文方法与现有的其他构建方法进行结合以得到互补，从而使模型构建的效果更好、适用范围更广。

基金项目

全国大学生创新创业训练项目(201910377021)

文章引用

高 阁,李 鹏,章 震,许鹏程. 一种基于3D点云的规则化模型自动构建方法
A Method of Building a Regularized Model Automatically Based on a 3D Point Cloud[J]. 测绘科学技术, 2021, 09(03): 98-106. https://doi.org/10.12677/GST.2021.93012

参考文献