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

doi:10.12082/dqxxkx.2021.200742

地球信息科学学报 ›› 2021, Vol. 23 ›› Issue (8): 1497-1507.doi: 10.12082/dqxxkx.2021.200742

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

刘亚坤¹(), 李永强¹^,^*(), 刘会云¹, 孙渡², 赵上斌¹

1.河南理工大学测绘与国土信息工程学院,焦作 454003
2.江苏省太仓市自然资源和规划局港区分局,太仓 215400

收稿日期:2020-12-07 修回日期:2021-03-24 出版日期:2021-08-25 发布日期:2021-10-25
通讯作者: * 李永强（1976— ）,男,河南许昌人,博士,副教授,主要从事激光扫描三维建模理论与方法研究。 E-mail: liyongqiang@hpu.edu.cn
作者简介:刘亚坤（1992— ）,男,河南周口人,硕士生,主要从事点云数据处理研究。E-mail: 757899220@qq.com
基金资助:
国家自然科学基金项目(41771491);国家自然科学基金项目(41701597);国家自然科学基金项目(U1810203);中国博士后科学基金项目(2018M642746)

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

LIU Yakun¹(), LI Yongqiang¹^,^*(), LIU Huiyun¹, SUN Du², ZHAO Shangbin¹

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

Received:2020-12-07 Revised:2021-03-24 Online:2021-08-25 Published:2021-10-25
Contact: LI Yongqiang
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)

摘要/Abstract

摘要：

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

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

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

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

LIU Yakun, LI Yongqiang, LIU Huiyun, SUN Du, ZHAO Shangbin. An Improved RANSAC Algorithm for Point Cloud Segmentation of Complex Building Roofs[J]. Journal of Geo-information Science, 2021, 23(8): 1497-1507.DOI:10.12082/dqxxkx.2021.200742

图/表 14

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

表1

表2

表3

屋顶分割结果在第2组实验中的质量分析

屋顶	脚点数/个	非面片点云数量/个	屋顶实际面片数量/个	本文算法分割面片数量/个	本文算法分割准确率/%	$σ ̅$ /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

表3

参考文献 33

[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 18^th 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: 10.1080/01431161.2019.1597294
[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.1016/j.autcon.2019.102892
[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: 10.1364/JOSA.38.000060
[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 39^th 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: 10.3390/rs8010005
[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: 10.3390/rs9050433
[26]	Xu Dong, Li Fang Hui, Wei Hong Xing. 3D point cloud plane segmentation method based on RANSAC and support vector machine[C]. 2019 14^th 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: 10.1145/358669.358692
[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]. 12^th 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: 10.1080/01431161.2012.690083
[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: 10.1016/j.patrec.2010.10.009

屋顶	脚点数/个	非面片点云数/个	各算法分割准确率/%
屋顶	脚点数/个	非面片点云数/个	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

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

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

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 33

相关文章 7

Metrics

本文评价

推荐阅读 0

[1]	张海清, 李向新, 王成, 习晓环, 王濮, 陈正宇. 结合DSM的机载LiDAR单木树高提取研究[J]. 地球信息科学学报, 2021, 23(10): 1873-1881.
[2]	王广帅, 万一, 张永军. 交叉点结构特征约束的机载LiDAR点云与多视角航空影像配准[J]. 地球信息科学学报, 2020, 22(9): 1868-1877.
[3]	陶鹏杰, 宋孟肖, 段延松. 利用高精度DLG进行机载LiDAR点云精度评定研究[J]. 地球信息科学学报, 2019, 21(4): 608-614.
[4]	刘凯斯, 王彦兵, 宫辉力, 李小娟, 余洁. 机载LiDAR点云数据的二面角滤波算法[J]. 地球信息科学学报, 2018, 20(4): 414-421.
[5]	鲁林, 周小成, 余治忠, 韩尚, 汪小钦. 随机森林算法在机载LiDAR数据林分平均树高估算中的应用研究[J]. 地球信息科学学报, 2016, 18(8): 1133-1140.
[6]	邓富亮, 杨崇俊, 曹春香, 范协裕. 高分辨率影像分割的分形网络演化改进方法[J]. 地球信息科学学报, 2014, 16(1): 95-101.
[7]	姜文聪, 张继贤, 程春泉, 梁勇. SIFT与粗差剔除算法相结合的机载SAR影像匹配研究[J]. 地球信息科学学报, 2013, 15(3): 440-444.

屋顶	屋顶实际面片数量/个	RANSAC 算法/个	区域增长算法/个	基于局部约束RANSAC算法/个	本文算法/个
A	14	16	17	15	15
B	44	51	48	49	41
C	21	24	24	23	19