EN中文

地球信息科学学报 >

2021 , Vol. 23 >Issue 8: 1497 - 1507

DOI: https://doi.org/10.12082/dqxxkx.2021.200742

遥感科学与应用技术

基于改进RANSAC算法的复杂建筑物屋顶点云分割

  • 刘亚坤 , 1 ,
  • 李永强 , 1, * ,
  • 刘会云 1 ,
  • 孙渡 2 ,
  • 赵上斌 1
展开
  • 1.河南理工大学测绘与国土信息工程学院,焦作 454003
  • 2.江苏省太仓市自然资源和规划局港区分局,太仓 215400
* 李永强（1976— ）,男,河南许昌人,博士,副教授,主要从事激光扫描三维建模理论与方法研究。 E-mail:

刘亚坤（1992— ）,男,河南周口人,硕士生,主要从事点云数据处理研究。E-mail:

收稿日期: 2020-12-07

  要求修回日期: 2021-03-24

  网络出版日期: 2021-10-25

基金资助

国家自然科学基金项目(41771491)

国家自然科学基金项目(41701597)

国家自然科学基金项目(U1810203)

中国博士后科学基金项目(2018M642746)

版权

版权所有,未经授权,不得转载、摘编本刊文章,不得使用本刊的版式设计。
收起

An Improved RANSAC Algorithm for Point Cloud Segmentation of Complex Building Roofs

  • LIU Yakun , 1 ,
  • LI Yongqiang , 1, * ,
  • LIU Huiyun 1 ,
  • SUN Du 2 ,
  • ZHAO Shangbin 1
Expand
  • 1. School of Surveying and Land Information Engineering, Henan Polytechnic University, Jiaozuo 454003,China
  • 2. Port area branch of Taicang natural resources and Planning Bureau, Jiangsu Province, Taicang 215400, China
* LI Yongqiang, E-mail:

Received date: 2020-12-07

  Request revised date: 2021-03-24

  Online published: 2021-10-25

Supported by

National Natural Science Foundation of China(41771491)

National Natural Science Foundation of China(41701597)

National Natural Science Foundation of China(U1810203)

China Postdoctoral Science Foundation Project(2018M642746)

Copyright

Copyright reserved © 2021
Fold

摘要

屋顶模型重建影响到建筑物完整模型重建质量,屋顶面点云分割质量对屋顶模型重建具有重要意义。针对传统RANSAC算法在屋顶点云面片分割时易产生错分割、过分割等问题,本文顾及点云位置信息,提出一种对点云重新分配的改进RANSAC点云分割算法。算法暂时剔除非平面内点,选取平面内点集中3个点作为初始样本,平面拟合判定邻域是否有效,从有效邻域中选取标准差值最小的3个点为初始模型。利用RANSAC算法对屋顶点云进行分割。利用K近邻算法统计误分类点与面片的距离降低误分类,优化过分割面片并进行连通性分析,利用距离及法向量一致性检验的方法重分配非平面内点。为验证本文算法有效性,选取芬兰Helsinki地区的3栋相互独立的复杂建筑物屋顶以及上海某小区的6栋建筑物群屋顶作为实验数据。在2组数据中,本文提出的改进RANSAC算法分割屋顶面片的平均准确率分别为92.17%、87.82%,78%的建筑物屋顶不存在过分割。在第2组数据中,所有分割面片上的点与其对应的最佳拟合平面的距离的标准差的平均值为0.030 m。实验结果表明,本文算法分割建筑物屋顶面片的准确率较高,较好的抑制了过分割现象,且抗噪能力强。

关键词： 机载LiDAR; 屋顶点云; RANSAC算法; 种子点选取; 屋顶点云分割; 误分类判定; 面片优化; 点云重分配

本文引用格式

刘亚坤 , 李永强 , 刘会云 , 孙渡 , 赵上斌 . 基于改进RANSAC算法的复杂建筑物屋顶点云分割[J]. 地球信息科学学报, 2021 , 23(8) : 1497 -1507 . DOI: 10.12082/dqxxkx.2021.200742

Abstract

Roof model reconstruction affects the quality of building complete model reconstruction, and the segmentation quality of roof point cloud is of great significance for roof model reconstruction. Aiming at the problems of wrong segmentation and over segmentation in the traditional RANSAC algorithm, this paper proposes an improved RANSAC algorithm to redistribute the point cloud, considering the location information of the point cloud. The algorithm eliminates the non planar points temporarily, and selects three points from the planar points set as the initial samples in the way of R radius neighborhood to fit them. The distance between the remaining points in the neighborhood and the fitting plane is calculated, and the neighborhood meeting the threshold requirements is classified as an effective neighborhood, three points with the minimum standard deviation are selected as the initial model, RANSAC algorithm is used to segment the roof point cloud. Aiming at the misclassification phenomenon in segmentation results, the distance between misclassification points and patches is calculated by k-nearest neighbor algorithm, and then the misclassification points are reclassified, at the same time, the angleθ and the distance d between patches are considered to merge the over segmented patches, the Euclidean distance based clustering segmentation algorithm is used to analyze the connectivity of the merged patches. By using the distance from a point to a plane and the consistency of the normal vectors between the point and the plane, the non planar points are redistributed. In order to verify the effectiveness of the algorithm, three independent roofs of complex buildings in Helsinki area of Finland and six roofs of buildings in a residential area of Shanghai are selected as experimental data. In the first group of experiments data, the average accuracy of the segmentation of roof patch is 92.17%, and the highest accuracy is 93.18%. In the second group of experiments data, the average accuracy of the segmentation of the roof patch is 87.82%, and the highest accuracy is 94.44%. The average standard deviation of the distance between the points on all the segmentation patches and the corresponding best fitting plane is 0.030 m. According to the above two groups of experiments data, 78% of the buildings have no over segmentation, and the average accuracy is 90%. The experimental results show that the algorithm has a high accuracy in extracting the roof plane slice, which can suppress the over segmentation and has a good anti noise ability.

Key words： airborne LiDAR; roof point cloud; RANSAC algorithm; seed selection; roof point cloud segmentation; judging the point of misclassification; patch optimization; point cloud redistribution

1 引言

建筑物作为城市主体要素,其三维空间信息的准确获取是数字城市建设的基础。激光雷达技术为三维空间数据获取提供了最直接和最重要的手段,是建筑物三维重建的最有效数据来源[1]。屋顶面是建筑物基本结构单元,从屋顶LiDAR点云中分割出符合屋顶结构的多个点云面片是屋顶建模的基础,分割质量将直接影响最终建模精度。点云分割是点云处理过程中的关键,其原理是把点云分为若干个特定,且具有独特性质区域的过程[2]。目前,屋顶面分割算法主要有：区域增长算法[3,4,5,6]、随机抽样一致 性算法（Random Sample Consensus, RANSAC）[7,8,9]、 基于几何特征的分割算法[10,11,12,13]、基于聚类的分割算法[14,15,16]、合成算法[17,18,19]等。区域增长算法根据种子点与邻域点集内点的拓扑关系建立生长规则,生长规则对分割结果影响较大,且无法有效避免非目标点云的影响。随机抽样一致性算法通过随机样本生成初始模型,然后用剩余数据验证该模型,对于包含噪声点的数据集也有较好的稳定性,迭代次数影响最终分割质量。基于几何特征的分割算法重点在于识别目标实体的几何特征,根据不同面片所具有的细节基元分割面片,但几何特征易受噪声点影响,导致分割结果产生较大误差。聚类算法通过将样本集中的数据分为不同的组,组内具有相同属性,组与组间的属性不完全相同。组内与组外数据属性的判定是该算法的核心。合成算法结合2种或2种以上不同算法特点,取长补短,使分割结果最优化。
在以上几种算法中,RANSAC算法对噪声点和异常值有较高的鲁棒性,在基础矩阵估计、特征匹配、运动模型选择等计算机视觉领域得到了广泛应用[20]。在点云处理方面,该算法能够对包含大量噪声数据的数据集进行处理,找出与实际平面相吻合的最佳数学平面。Aluir等[21]利用RANSAC算法分割屋顶平面,基于相邻面片间的连续性优化分割结果,以提高分割结果的完整性。Xu等[22]根据正确与不正确的平面假设间的误差分布差异设计权重函数,对观测值误差较大点赋予较大损失函数值,以总权值代替内点比率。兰军[23]提出多面随机抽样一致性算法,改进了采样点策略与模型迭代规则,提升了面片分割精度和效率。张宏伟等[24]针对“伪屋顶面”分割问题,提出一种基于局部约束点云平面分割算法。该算法基于局部抽样策略生成初始模型,利用点云局部曲面法向约束及距离建立迭代准则,结合半径约束规则进行点云空间聚类,降低了错分割概率。Li等[25]提出了一种改进的基于正态分布变换单元的RANSAC方法,在每次迭代中选择平面正态分布变换单元作为最小样本,以确保在同一平面上采样的正确性,降低虚假平面分割概率。Xu等[26]提出一种支持向量机（SVM）预分类的RANSAC算法,该方法基于点云坐标 ( x , y , z ) 和颜色 ( R , G , B ) 信息,利用SVM预测点云类别,提高RANSAC算法分割精度。
虽然RANSAC算法已经是一种相对成熟的点云分割算法,但是对于一些复杂屋顶结构的面片分割仍存在不足之处。改进种子点选取方式可以使提取出的最佳数学平面与实际平面相吻合的概率大大提高。因此,本文在RANSAC算法相关研究基础上,针对传统RANSAC算法在处理机载LiDAR点云由于种子点选取不恰当导致过分割或欠分割这一问题,在构建k-d树结构的基础上,提出一种利用点云位置分布规律对点云重分配的改进RANSAC算法。该算法预先剔除对分割精度产生负面影响的噪声点、面片相交处点,从而提高种子点提取时该点位于模型内部的概率。基于以上规则完成点云分割后,再对预先剔除点进行重分配,提高分割结果的完整性。

2 研究方法

RANSAC算法是Fischler和Bolles提出的一种用于检测数学特征的模型拟合算法[27]。在点云处理方面,该算法采用迭代方式从1组包含异常点的被观测数据中估算出数学模型参数,具备随机性与假设性思想。随机采样最小的 n 个样本,得到初始参数模型,在包含异常点的样本集中迭代验证初始模型;在该验证过程中,计算待验证样本点与初始模型的误差,小于一定阈值归为内点,否则标记为外点;统计当前模型中正确数据在整体样本中的比率 w 。通常情况下,要保证 k 次迭代之后至少有1次 n 个采样子集都来自模型内部,且置信度要大于 P 0 (式（1））, P 0 为迭代过程中从样本集内随机选取的点都为局内点的概率阈值。
1 - ( 1 - w n ) k > P 0
同时,为防止迭代次数过少造成最终模型不理想,亦可设定1个最小迭代次数 k （式（2））。为了使参数更加准确,在 k 值的基础上再加上其标准偏差 S ( K ) （式（3））,得到最终的迭代次数 E ( k ) （式（4））。在足够次迭代后,取 w 最大的模型为最佳模型,即与实际平面吻合度最高的最佳数学平面。
k = log ( 1 - P 0 ) log ( 1 - w n )
S k = 1 - w n w n
E k = k + S ( k )
该算法随机采集3个种子点,生成初始模型,然后计算剩余点与初始模型的距离,满足一定规则后归为内点。但由于点云数据噪声点及面片相交处点的存在,导致初始模型不总是符合选取要求,从而影响面片分割质量及效率。

2.1 RANSAC算法改进

改进后的算法首先基于点云法向量与位置信息剔除非平面内点,旨在提高初始模型迭代为最优模型的概率;其次,在分割后的面片优化时,考虑到复杂屋顶结构,为避免数学相交但空间不相交的点云误分类现象,本文算法基于误分类点与最近面片的距离和法向量进行判定,重新判别误分类点的归属,以优化分割结果。对于过分割现象,采用面片法向量夹角θ以及面片间距离 d 对过分割面片进行合并,并基于欧式距离的聚类分割算法对合并后的面片进行连通性分析;最后,对非平面内点云重分配,以提高分割结果的完整性。改进后的屋顶点云分割算法流程如图1所示。
图1 改进的RANSAC算法屋顶点云分割流程

Fig. 1 Flow chart of improved RANSAC algorithm of roof point cloud segmentation

2.2 分割预处理

建筑物屋顶形状各异,主要有平顶[28]、人字形[29]、四坡形[30]、复杂屋顶[3]等。人字形、四坡形以及复杂屋顶中各个平面相交,分割时难度较大。本文将预处理后的屋顶点云按照其相对屋顶面片的位置分为3类：① 平面内点为点坐标位于面片内的点; ②面片相交处点为点坐标位于面片相交线处及与相交线距离最近的点;③ 噪声点为点坐标与屋顶面片相离的点。前文提到,RANSAC算法具有随机性与假设性的思想。随机性即种子点选取的随机性,如果在初始模型中随机选择的种子点恰好位于面片相交处点或噪声点（图2中非蓝色点）,那么假设的初始模型经过迭代所产生的最终模型易与最优模型产生较大偏差。此外,种子点选取不佳,也将会导致过分割及伪平面。本文在预处理阶段将对面片相交处点云及噪声点云进行筛选并剔除,使其无法参与最初的种子点选取及面片分割迭代过程。而后再对预先剔除的点云进行重分配,以确保屋顶面片分割结果完整性。
图2 复杂屋顶中不同位置点云分布示意

Fig. 2 Schematic diagram of point cloud distribution at different locations in a complex roof

独立点云所包含特征信息较少,最多包含该点的位置 ( x , y , z ) 、颜色（ R , G , B ）以及反射强度（ I ）信息,缺少几何特征信息。因此对每个点进行邻域分析,计算其法向量 γ ,将法向量和位置不符合要求的点（面片相交处点及噪声点）剔除。为提高计算效率,本文采用k-d树结构组织点云并进行邻近点快速查询。对于给定点 p i ,其邻近点集S={ p 1 , p 2 , …, p n },设 p ̅ （ x ̅ , y ̅ , z ̅ ）为点 p i 邻域点集的三维质心,计算公式如（5）,则点 p i 对应的协方差矩阵 C 可以表示为式（6）。根据特征方程公式（7）计算协方差矩阵 C 的特征值 λ i 。
p ̅ ( [ x , y , z ] ) = x ¯ = 1 n ∑ i = 1 n x i y ¯ = 1 n ∑ i = 1 n y i z ¯ = 1 n ∑ i = 1 n z i
C = 1 n ∑ i = 1 n ( p i - p ̅ ) ( p i - p ̅ ) T
λE - C = 0
通常情况下,平面内点云有2个不为零的特征值,其中最小特征值对应的特征向量即为该点的局部法向量 γ 。另外,考虑到真实场景中点云离散分布在拟合平面周围,因此定义粗糙度 λ ̅ （式（8））。
λ ̅ = λ 1 ( λ 1 + λ 2 + λ 3 )
其中, λ 1 为最小的特征值。由此可得,非平面内点筛选步骤为：
（1）采用k-d树结构方式组织点云,在点云数据集 P 内随机选取点 p i ,按照规则划定邻域点集,并计算该点的三维质心;
（2）结合质心、式(6)、式（7）计算该点的3个特征值,并得出该点法向量;
（3）利用式（8）计算粗糙度,若其粗糙度较低,但对应的法向量与竖直方向的夹角余弦小于给定阈值,则将该点归为立面点并从点集中剔除;若粗糙度较高,则将其归为一般噪声点。
（4）重复步骤（1）—步骤（3）,遍历所有点云,直到非平面内点全部筛选出局。
为提高原始点云数据中局内点的比例,以及下一步骤中种子点被正确选取的概率,这些筛选出的点云将不参与常规RANSAC阶段的求解,但在分割后处理阶段会按照一定的准则重分配到各面片中,使分割结果更加可靠。

2.3 种子点选取

传统RANSAC算法对于种子点的选取具有随机性,该方法效率低,且容易产生错分割现象。本文采用文献[31]提出的局部采样Local RANSAC方法进行种子点的选取,如图3所示。该方法认为属于同一个平面的点应该在空间上邻近,因此先随机选取第1个点,从其r半径邻域内选取另外2个点。具体方法如下：从原始数据集P中随机不重复地选择1个点,利用k-d树结构组织点云并统计r半径邻域内的点,若邻域内点个数小于点数阈值 N p ,则重新从数据集P中随机选点,直到有满足阈值条件的邻域;用最小二乘法对该邻域内点进行平面拟合,计算邻域内各点到该平面的欧式距离 d = d 1 , d 2 , d 3 , … , d n ,得出各点到平面的平均距离 d ̅ 及面片标准差 σ （式（9））;若标准差小于给定阈值 σ p ,则表示邻域范围内点云属于同一个面片概率较大,该点的邻域称为有效邻域,从有效邻域中选择 σ 最小的3个点作为初始种子点。
图3 种子点选取方式及屋顶面片分割

Fig. 3 Seed point selection and roof patch segmentation

d ̅ = ( d 1 + d 2 + d 3 + ⋯ + d n ) n σ = 1 n ∑ i = 1 n ( d i - d ̅ ) 2
由于屋顶平面边缘以及小团簇周围的点云数目较小,设置邻域内点数阈值 N p 及可以有效避免噪声及屋脊线处点云影响,降低伪平面出现概率,减少运算次数。面片标准差阈值能最大限度确保种子面选取正确性,提高后续模型解算效率及准确率。

2.4 面片优化

利用RANSAC算法分割点云,对每个点云面片进行编号。但需要考虑另一个问题,即所产生的点云面片与实际情况有可能存在偏差,因此需要对点云面片进行优化[32]。本文结合文献[33]中的方法,即法向量一致性检验和连通性检验,同时考虑分割面片间的距离 d ,采用一种K近邻分类-面片合并-连通性分析的策略。
2.4.1 误分类点归属判定
RANSAC算法每次只能确定1个平面,对于复杂屋顶结构点云分割,各面片分割具有顺序性,存在先分割出的平面中包含应属于其他面片点云的情况。图4所示为面片局部区域空间上不直接相交但是数学上相交的两平面点云误分类现象。针对此类问题,本文通过K近邻算法对面片B上的误分类点重新归类。首先计算该面片上所有点到其余面片的距离以及法向量夹角,若某个点2个参数同时满足给定阈值,则将该点标记为误分类点。利用k-d树结构获取每个误分类点邻域内最近的k个点,统计k个点所属的平面编号,出现次数最多的平面即为误分类点最终所属的面片。
图4 相邻面片的点云误分类现象

Fig. 4 Point cloud misclassification of adjacent patches

2.4.2 面片合并
当RANSAC算法的参数阈值设置不合理时,会出现过度分割现象,即将同一平面分割成多个更小的面片,因此需要进行面片合并以消除过分割的影响。同时考虑了面片法向量的夹角θ以及面片间的距离 d ,定义2个阈值参数：法向量夹角阈值 θ p 以及平面距离阈值 d p 。对于2个模型参数不同的平面P1、P2, n 1 ⇀ 、 n 2 ⇀ 分别为过两平面几何中心的法向量,则两面片的夹角可表示为式（10）：
θ = arcco s - 1 ( n 1 ⇀ · n 2 ⇀ )
对于两平面间的距离,若两面片法向量方向完全一致,则可用 r 12 ⇀ 在法向量上的投影大小表示（ r 12 ⇀ 为 n 1 ⇀ 、 n 2 ⇀ 的空间距离）。但是计算得到的面片夹角存在一定的误差,且夹角误差会随着点到平面距离的增大而增大,导致用不同法向量计算的面片距离波动较大。因此将面片间距离定义为式（11）：
d = max ( r 12 ⇀ · n 1 ⇀ , | r 12 ⇀ · n 2 ⇀ | )
只有当 θ < θ p 与 d < d p 同时成立时,才将2个面片合并。
2.4.3 连通性分析
通过面片合并,符合同一数学模型的面片合并成更大的面片。但是,数学意义上共面的面片在空间上并不一定是相邻的,因此还需要进行连通性检测。本文的连通性检验是基于欧式距离的聚类分割算法,具体方法如下：
（1）利用k-d树结构组织点云,从已分割面片P上随机选择1个点,通过r球半径搜索得到其邻域点集。
（2）将邻域点集放到类容器Q里并标记为已处理。从容器Q里随机不重复地选择1个点,继续搜索其邻域点集,放到容器Q里并标记为已处理。依此类推,直到容器Q里没有新的点加入,本次搜索结束。
（3）迭代进行上述过程,直到分割面片P中所有点都处理完。至此,屋顶面片被分割成空间上密度连通的区域。

2.5 非平面内点云重分配

分割预处理阶段筛选出的非平面内点没有参与RANSAC面片分割,因此需要将他们重新分配,以保证分割的完整性。对于这类点云的重分配详细步骤如下：
（1）令所有非平面内点云集合为U,集合中所有点都标记为未分配。
（2）从点集U中随机选取1个未被标记点 p i ,计算它到每个分割面片的距离d,找到距离最小值 d min 对应的面片 P ,编号记为 P i 。若 d min 的值大于预先设定的阈值 D P ,则直接剔除该点,否则将该点放到对应面片编号的临时容器内,并标记为已分配。
（3）遍历集合U,直到点集中的所有点都已被放到对应的临时容器中。对临时容器中的点进行法向量一致性检验,满足条件的点分配到对应的分割面片中,法向量不一致的点放入点集 U ˆ 中。
（4）对于点集 U ˆ ,将步骤（2）中距离最小值对应的面片编号删除,对剩余的分割面片重复执行上述步骤,直到所有点都重分配完毕。
对于完成最终分割的屋顶面片,基于先验知识判定面积小于0.5 m2的面片不是屋顶平面,并从分割结果中剔除。对于面片面积的计算,本文采用格网统计法：将分割面片绕Z轴和Y轴旋转后投影到XOY平面的二维格网,当格网内的点云数目大于一定阈值时将该格网标记为有效格网,最后计算所有有效格网的面积作为分割面片的面积。

3 实验分析

为验证本文算法的有效性,选用2组建筑物屋顶点云数据进行实验分析。第1组实验数据选取芬兰Helsinki地区的3栋相互独立复杂建筑物屋顶,该组数据采集时间为2016年3月,采用RIEGL激光雷达系统,点频300 Khz,如图5所示。图中颜色分布以点的高程为依据进行渲染,屋顶A呈U形分布、屋顶B呈复杂分布、屋顶C呈L形分布,各屋顶中相邻两面片大部分呈人字形结构,也存在平顶。该组数据首先利用传统RANSAC算法、区域增长算法以及基于局部约束RANSAC算法[24]分割3栋建筑物屋顶面;然后利用本文提出的改进RANSAC算法分割屋顶面;最后统计本文算法与其他3种算法分割出的点云面片数量,对比分析其分割质量。第2组实验数据选用上海某小区的6栋建筑物群屋顶,该组数据采集时间为2018年8月,采用AS-900HL多平台激光雷达测量系统,点频500 Khz,如图6（a）所示。图中建筑物编号从上到下,从左到右依次为1、2、3、4、5、6,图6（b）为提取出的屋顶点云,图中颜色按高程进行渲染。对于该组数据,利用本文改进RANSAC算法对其进行点云面片分割,并根据相关评价指标对其进行质量评估。
图5 第1组建筑物屋顶遥感影像及其对应点云数据

Fig. 5 The first group of building roof remote sensing images and corresponding point cloud data

图6 改进的RANSAC算法在第2组实验中的分割结果

Fig. 6 Segmentation results of improved RANSAC algorithm in the second group of experiments

3.1 算法性能分析

本文所述方法实验参数设置如下：局内点抽取概率阈值 P 0 为0.98,最大迭代次数为1000,种子平面标准差阈值 σ p 为0.1 m,r半径内点个数阈值 N p 设置为15,距离阈值 d p 设置为0.5 m ,法向量夹角阈值 θ p 设置为5°,连通半径设置为4倍点间隔。第1组数据实验结果如图7—图10,第2组实验数据结果如 图6（c）。图11为1号建筑物屋顶分割结果放大图。以上分割结果图中不同颜色表示不同的屋顶平面。
图7 RANSAC算法在第1组实验中的分割结果

Fig. 7 Segmentation results of RANSAC algorithm in the first group of experiments

图8 区域增长算法在第1组实验中的分割结果

Fig. 8 Segmentation results of region growing algorithm in the first group of experiments

图9 基于局部约束RANSAC算法在第1组实验中的分割结果

Fig. 9 Segmentation results of RANSAC algorithm based on local constraints in the first group of experiments

图10 本文算法在第1组实验中的分割结果

Fig. 10 Segmentation results of this paper algorithm in the first group of experiments

图11 第2组实验中1号建筑物屋顶点云分割结果

Fig. 11 Segmentation results of roof point cloud of No. 1 building in the second group of experimental

由图7可得,传统RANSAC算法对存在大面积面片的屋顶平面提取效果较好,但在较小面积屋顶平面较为集中的区域容易出现错分割现象,如屋顶A中①、屋顶B中③、屋顶C中⑤号区域;在分割较为复杂的建筑物屋顶面时,相邻屋顶平面内的点云容易产生误分类现象,如屋顶A中②、屋顶B中④,屋顶C中⑥号区域。由图8可得,区域增长算法对于面积较大区域面片提取结果较好,但对于面片相交处面片分割效果不理想,如屋顶A中②、屋顶B中③④号区域。且该算法对于结构复杂的屋顶容易出现过分割现象,如屋顶A中①,屋顶C中⑤号区域。由图9可得,基于局部约束RANSAC算法对于简单屋顶分割效果较好,但对于复杂屋顶分割效果较差,如屋顶B中③④号区域。且该算法对于面片相接处点云归属的判断准确率较低,如屋顶A中①,屋顶B中②,屋顶C中⑤号区域。
对比传统RANSAC算法、区域分割算法和基于局部约束RANSAC算法,本文算法降低了复杂屋顶结构较小面片错分割现象概率,较好地抑制了面片内点误分类现象的发生,保证了屋顶面的完整。由于本文算法基于先验知识将面积小于0.5 m2的面片判定为非屋顶面平面,因此第1组实验数据分割结果图中出现较多的小空洞,结合遥感影像图可以看出这些较小的面片大都是建筑物的天窗等附属结构,对最终的分割结果影响不大。
第2组实验数据,根据分割结果图6（c）和图11可得：本文提出的改进的RANSAC算法能正确地分割出绝大多数屋顶面片。点云密度较高的情况下分割的结果较好,当点云的密度较低或者点云质量不高时,本文算法的分割的准确率受到一定的影响,具体表现为对屋顶细小结构的面片的识别程度不高。但本文算法能正确识别出绝大多数的屋顶面片。

3.2 分割质量分析

根据相关指标,定量分析本文改进算法分割质量。对于第1组实验数据,将文中所提到的3种方法与本文方法进行对比分析;第2组实验数据,评价本文方法分割质量。其中,准确率被定义为正确提取的屋顶平面占所有屋顶平面的比例, Mean 为平均值。 σ ̅ 为分割面片上的点与其对应的最佳拟合平面的距离的标准差的平均值。
表1为不同算法在第1组实验中分割结果数量对比,表2为不同算法在第1组实验中的质量分析。由表1可知：RANSAC算法、区域增长算法提取3栋建筑物屋顶平面均出现提取出的面片数大于屋顶平面的实际面片数,主要因为这2种算法出现错分割和过分割的区域较多;基于局部约束RANSAC算法对于简单屋顶分割效果较好,而对于复杂屋顶,且多存在面片相接处屋顶分割效果不理想。本文算法能准确分割出绝大多数屋顶平面,部分面片未能提取出是因为该部分平面对应的脚点数较少,在改进算法中基于先验知识剔除。由表2可知：本文算法对于屋顶A、B、C分割的平均准确率为92.17%。对于屋顶A和C分割,本文算法相比其他3种算法准确率优势较小,主要是因为屋顶A和屋顶C结构简单且多存在面积较大面片。而对于复杂屋顶B,本文算法优势较为明显。
表1 不同算法在第1组实验中的分割结果数量对比

Tab. 1 Comparison of segmentation results number of different algorithms in the first group of experiments

屋顶 屋顶实际
面片数量/个 		RANSAC
算法/个 		区域增长
算法/个 		基于局部约束RANSAC算法/个 本文算法/个
A 14 16 17 15 15
B 44 51 48 49 41
C 21 24 24 23 19
表2 不同算法在第1组实验中的分割结果质量分析

Tab. 2 Quality analysis of segmentation results of different algorithms in the first group of experiments

屋顶 脚点数/个 非面片
点云数/个 		各算法分割准确率/%
RANSAC算法 区域增长算法 基于局部约束RANSAC算法 本文算法
A 27 688 1749 85.71 78.57 92.86 92.86
B 89 770 5865 84.09 90.90 88.64 93.18
C 37 180 2011 85.71 85.71 90.48 90.48
平均值 85.17 85.06 90.66 92.17
表3为第2组实验数据分割结果。通过对表3中数值的分析可知：本文提出的改进的RANSAC算法分割屋顶面片的平均准确率为87.82%,其中,第2栋建筑物的分割准确率最高,达到94.44%,第4栋建筑物的分割准确率最低,为81.48%。所有分割面片上的点与其对应的最佳拟合平面的距离的标准差的平均值为0.030 m。另外,6栋建筑物屋顶中,除5号建筑物外,其他5栋建筑物屋顶分割面片数量均小于实际屋顶面片数量,这是由于在改进算法中降低了过分割现象。第5栋建筑物面片分割数大于实际的面片数,主要由于该建筑物屋顶点云中存在细小结构的杂乱点云,但真实场景下的屋顶面片都被正确分割。通过对比两组实验数据,本文算法总体上具有良好的适用性,且抗噪能力较好。
表3 屋顶分割结果在第2组实验中的质量分析

Tab. 3 Quality analysis of roof segmentation results in the second group of experiments

屋顶 脚点数/个 非面片
点云数量/个 		屋顶实际
面片数量/个 		本文算法分割
面片数量/个 		本文算法
分割准确率/% 		σ ̅ /m
1 66 726 349 36 31 86.11 0.028
2 73 953 210 36 34 94.44 0.026
3 64 480 164 36 32 88.89 0.020
4 51 526 1275 27 22 81.48 0.039
5 72 862 576 27 31 87.10 0.034
6 67 602 721 27 24 88.89 0.035
平均值 87.82 0.030
由表2及表3可得：第1组实验中,本文算法对于3类屋顶面片分割平均准确率为92.17%,第2组实验中,本文算法对于6栋建筑物群屋顶点云面片分割平均准确率为87.82%,低于第1组实验数据分割结果。主要原因在于,第1组实验数据为相互独立屋顶,且相对第2组实验数据屋顶结构简单。第2组实验数据为小区建筑群屋顶,其结构相对复杂,多存在面积较小的屋顶平面,且屋顶面片间相对位置关系难以判定。

4 结论

本文以建筑物屋顶点云分割为研究对象,针对屋顶点云面片分割时容易产生错分割问题,提出一种结合点云位置规律信息对点云重分配的改进的RANSAC算法。为验证算法有效性,选取了2组点云数据对算法性能进行了实验分析。主要结论：
（1）在预处理阶段,以点云法向量为判定标准,筛选出非平面内点并暂时剔除,使其无法参与点云面片分割,进而利用剩余点与初始模型距离规则迭代分割屋顶点云面片。该阶段将原始点云数据中局内点数的比率从89.7%提高至97.6%。
（2）从剔除非平面点后的点云集合中,随机不重复的选取1个点 p i ,统计其r半径邻域内点的个数。若满足要求,则从其邻域内选取剩余种子点进行平面拟合,评价邻域内点与拟合平面距离。从有效邻域内选取3个点作为初始模型能够有效降低噪声点影响,最大限度确保初始模型选取的正确性。
（3）K近邻分类-面片合并-连通性分析的面片优化策略,能够对面片内点云的误分类现象进行重新判定,对过分割现象进行优化,提高了分割结果的准确性。对分割预处理阶段筛选出的非平面内点进行重分配,能够保证分割结果的完整性。
（4）对于2组实验数据,本文提出的改进的RANSAC算法分割屋顶面片的平均准确率分别为92.17%、87.82%,在第2组实验数据中,所有分割面片上的点与其对应的最佳拟合平面的距离的标准差的平均值为0.030 m。本文算法在提取建筑物屋顶平面的质量较高,且抗噪能力强。
机载LiDAR系统能够快速、方便的获取建筑物屋顶点云数据。本文针对建筑物屋顶点云面片分割问题,提出了一种改进的RANSAC算法,该算法对于屋顶面片分割具有较高的准确率,能够为后期屋顶模型重建提供基础。但本文算法对于拱形屋顶面的提取本文算法并不匹配,且对存在较多小面积的屋顶分割容易产生空洞,自适应性有待进一步提高。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
杨必胜, 梁福逊, 黄荣刚. 三维激光扫描点云数据处理研究进展、挑战与趋势[J]. 测绘学报, 2017, 46(10):1509-1516.

[Yang B S, Liang F X, Huang R G. Research progress challenge and trend of 3D laser scanning point cloud data processing[J]. Journal of Surveying and Mapping, 2017, 46(10):1509-1516. ]

[2]
景庄伟, 管海燕, 臧玉府, 等. 基于深度学习的点云语义分割研究综述[J]. 计算机科学与探索, 2021, 15(1):1-26.

[Jing Z W, Guan H Y, Zang Y F, et al. Survey of point cloud semantic segmentation based on deep learning[J]. Computer Science and Exploration, 2021, 15(1):1-26. ]

[3]
朱军桃, 王雷, 赵传, 等. 基于区域生长算法的复杂建筑物屋顶点云分割[J]. 国土资源遥感, 2019, 31(4):20-25.

[Zhu J T, Wang L, Zhao C, et al. Segmentation of point clouds on the roof of complex buildings based on regional growth algorithm[J]. Remote Sensing of Land Resources, 2019, 31(4):20-25. ]

[4]
王雯, 任小玲, 陈逍遥. 一种改进的区域增长彩色3D点云分割算法[J]. 国外电子测量技术, 2018, 37(11):10-14.

[Wang W, Ren X L, Chen X Y. An improved region - growing color 3D point cloud segmentation algorithm is presented[J]. Foreign Electronic Measurement Technology, 2018, 37(11):10-14. ]

[5]
Ma X. A Fast Point Cloud Segmentation Algorithm Based on Region Growth[C]. 2019 18th International Conference on Optical Communications and Networks (ICOCN), Huangshan, China , 2019:1-2.

[6]
Anh-Vu, Linh T H, Debra F, et al. Octree-based region growing for point cloud segmentation[J]. ISPRS Journal of Photogrammetry & Remote Sensing, 2015, 104:88-100.

[7]
Poz A P D, Ywata M S Y. Adaptive random sample consensus approach for segmentation of building roof in airborne laser scanning point cloud[J]. International Journal of Remote Sensing, 2019, 41(4):1-15.

DOI

[8]
李云帆, 谭德宝, 刘瑞, 等. 顾及建筑物屋顶结构的改进RANSAC点云分割算法[J]. 国土资源遥感, 2017, 29(4):20-25.

[Li Y F, Tan D B, Liu R, et al. An improved RANSAC point cloud segmentation algorithm considering the roof structure of buildings[J]. Remote Sensing of Land Resources, 2017, 29(4):20-25. ]

[9]
Hamid-Lakzaeian F. Structural-based point cloud segmentation of highly ornate building faades for computational modelling[J]. Automation in Construction, 2019, 108:102892.

DOI

[10]
张强. 基于几何特征的规则激光点云分割方法研究[D]. 长沙:湖南科技大学, 2015.

[Zhang Q. Research on regular laser point cloud segmentation based on geometric features[D]. Changsha: University of Science and Technology, Hunan, 2015. ]

[11]
Li X R, Liu G S, Sun S. Efficient point cloud segmentation approach using energy optimization with geometric features for 3D scene understanding[J]. Optical Society of American, 2021, 38:60-70.

DOI

[12]
党吉圣, 杨军. 多特征融合的三维模型识别与分割[J]. 西安电子科技大学学报, 2020, 47(4):149-157.

[Dang J S, Yang J. 3D model recognition and segmentation based on multi feature fusion[J]. Journal of XiDian University, 2020, 47(4):149-157. ]

[13]
侯琳琳. 基于几何特征的三维点云分割算法研究[D]. 北京:北京交通大学, 2019.

[Hou L L. Research on 3D point cloud segmentation algorithm based on geometric features[D]. Beijing: Beijing Jiao Tong University, 2019. ]

[14]
Saglam A, Makineci H B, Baykan Ö K, et al. Clustering-based plane refitting of non-planar patches for voxel-based 3D point cloud segmentation using K-means clustering[J]. International Information and Engineering Technology Association, 2020, 37(6):1019-1027

[15]
唐泽宇. 基于泊松分布K-means聚类的点云精简算法[D]. 太原:太原理工大学, 2019.

[Tang Z Y. Point cloud simplification algorithm based on poisson distribution K-means clustering[D]. Taiyuan: Taiyuan University of Technology, 2019. ]

[16]
吴燕雄, 李峰, 刘芳, 等. 平滑度欧式聚类算法分割点云数据[J]. 测控技术, 2016, 35(3):36-38.

[Wu Y X, Li F, Liu F, et al. Smoothness European clustering algorithm segmentation point cloud data[J]. Measurement and Control Technology, 2016, 35(3):36-38. ]

[17]
高广, 马洪超, 张良. 利用合成算法从LiDAR数据提取屋顶面[J]. 武汉大学学报·信息科学版, 2014, 39(10):1225-1230.

[Gao G, Ma H C, Zhang L. Extraction of roof surface from LiDAR data by synthetic algorithm[J]. Journal of Wuhan University (Information Science Edition), 2014, 39(10):1225-1230. ]

[18]
Yuan H, Sun W, Xiang T. Line laser point cloud segmentation based on the combination of RANSAC and region growing[C]. 2020 39th Chinese Control Conference (CCC), Shenyang, China , 2020:6324-6328.

[19]
石爱军, 白瑞林, 田青华, 等. 遗传算法结合自适应阈值约束的ICP算法[J]. 光学技术, 2018, 44(1):63-68.

[Shi A J, Bai R L, Tian Q H, et al. ICP algorithm based on genetic algorithm combined with adaptive threshold constraint[J]. Optical Technology, 2016, 44(1):63-68 ]

[20]
陈付幸, 王润生. 基于预检验的快速随机抽样一致性算法[J]. 软件学报, 2005(8):1431-1437.

[Chen F X, Wang R S. Rapid random sampling consistency algorithm based on pre-test[J]. Journal of Software, 2005(8):1431-1437. ]

[21]
Dal Poz A P, Sayuri Yano M. RANSAC-based segmentation for building roof face detection in LiDAR point cloud[C]. IGARSS 2018-2018 IEEE International Geoscience and Remote Sensing Symposium, Valencia, Spain, 2018:1276-1279.

[22]
Xu B, Jiang W S, Shan J, et al. Investigation on the weighted RANSAC approaches for building roof plane segmentation from LiDAR point clouds[J]. Remote Sensing, 2016, 8(1):5.

DOI

[23]
兰军. LiDAR点云中实时平面检测算法研究与实现[D]. 北京:北方工业大学, 2019.

[Lan J. Research and implementation of real-time plane detection algorithm in LiDAR point cloud[D]. Beijing: North China University of Technology, 2019. ]

[24]
张宏伟, 姜超, 张保明, 等. 基于局部约束的建筑物屋顶点云平面分割方法[J]. 测绘科学技术学报, 2017, 34(3):274-278.

[Zhang H W, Jiang C, Zhang B M, et al. Segmentation method of roof point cloud plane based on local constraint[J]. Journal of Surveying and Mapping, 2017, 34(3):274-278. ]

[25]
Li L, Yang F, Zhu H, et al. An improved RANSAC for 3D point cloud plane segmentation based on normal distribution transformation cells[J]. Remote Sensing, 2017, 9(5):433.

DOI

[26]
Xu Dong, Li Fang Hui, Wei Hong Xing. 3D point cloud plane segmentation method based on RANSAC and support vector machine[C]. 2019 14th IEEE Conference on Industrial Electronics and Applications (ICIEA), Xi'an, China , 2019:943-948.

[27]
Fischler M A, Bolles R C. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6):381-395.

DOI

[28]
Brenner C, Haala N, Norbert. Rapid acquisition of virtual reality city models from multiple data sources[J]. International Archives of Photogrammetry and Remote Sensing, 1998, 32(5):323-330.

[29]
Milde J, Brenner C. Graph-based modeling of building roofs[C]. 12th AGILE Conference on GIScience, Hannover, Germany . 2009.

[30]
Kada M McKinley L. 3D building reconstruction from LiDAR based on a cell decomposition approach[J]. International Archives of Photogrammetry and Remote Sensing, 2009, 37(3):47-52.

[31]
Chen D, Zhang L Q, Li J, et al. Urban building roof segmentation from airborne LiDAR point cloud[J]. International Journal of Remote Sensing, 2012, 33(20):6497-6515.

DOI

[32]
徐博. 基于航空LiDAR数据的建筑物屋顶面三维重建关键技术研究[D]. 武汉:武汉大学, 2017.

[Xu B. Research on key technologies of 3D reconstruction of building roof surface based on aviation LiDAR data[D]. Wuhan: Wuhan University, 2017. ]

[33]
Gallo O, Manduchi R, Rafii A. CC-RANSAC: Fitting planes in the presence of multiple surfaces in range data[J]. Pattern Recognition Letters, 2011, 32(3):403-410.

DOI

Options
文章导航

/

〈 〉