Point cloud simplification method combining K-means++ clustering with UAV LiDAR point cloud normal vectors

doi:10.6046/gtzyyg.2020.02.14

Abstract
Figures/Tables
References
Related Articles
Metrics

Download: PDF(5942 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

It is important to reduce the amount of unmanned aerial vehicle (UAV) light detection and ranging (LiDAR) data effectively based on point cloud simplification method, and this is of great significance for later point cloud storage and fast processing. The authors used K-means++ method to cluster point cloud normal vectors so as to achieve point cloud simplification. Firstly, the echo point cloud was removed by using the echo number. After that, the zero-mean normalization method was used to normalize the point cloud attribute information, and the KD tree (K-dimension tree) was used to establish the point cloud index so as to construct the point cloud K neighborhood. Then, the principal component analysis method was used to estimate the point cloud normal vector, and the optimal number of clusters was determined by the elbow method. Finally, the point cloud simplification was achieved by K-means++ clustering method. The simplified result was generated into a Delaunay triangulation and converted into raster data, and the validity of the method was verified by the correlation coefficient. The results show that this method can remove 7 722 points of multiple echo point clouds for 69 544 point cloud data in the study area; as for K-means++ clustering with a cluster number of 8 for the point cloud normal vector, the corresponding simplification rates were 81.389%, 81.833% and 85.369%, respectively. The time to generate the Delaunay triangulation after streamlining was much lower than that before the simplifying, with the simplification process being 81.833%, and the highest correlation coefficient was 0.890. This method can provide a reference for point cloud reduction.

Keywords point cloud K neighborhood point cloud normal vector K-means++ clustering method Delaunay triangle

TP79

Corresponding Authors: Qingzhan ZHAO E-mail: zqz_inf@shzu.edu.cn

Issue Date: 18 June 2020

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

	Peiting LI
	Qingzhan ZHAO
	Wenzhong TIAN
	Yongjian MA

Cite this article:

Peiting LI,Qingzhan ZHAO,Wenzhong TIAN, et al. Point cloud simplification method combining K-means++ clustering with UAV LiDAR point cloud normal vectors[J]. Remote Sensing for Land & Resources, 2020, 32(2): 103-110.

URL:

https://www.gtzyyg.com/EN/10.6046/gtzyyg.2020.02.14 OR https://www.gtzyyg.com/EN/Y2020/V32/I2/103

Tab.1 Parameters of Riegl laser scanner VUX-1

Fig.1 Visualization of the original point cloud echo intensity in study area

Fig.2 Technical flow chart for this paper

Fig.3 3D visualization results of original point cloud echo times in study area

Tab.2 Index numbers corresponding to point cloud K neighborhoods

Tab.3 Point cloud characteristic information corresponding to index number 1

Fig.4 Visualization of point cloud normal vector

Fig.5 Clustering SSE for different number of results

Fig.6 3D visualization of K-means++ for clustering point cloud normal vector

Tab.4 Statistics of point cloud number and intensity error after clustering

Fig.7 Delaunay triangulation of clusters 1, clusters 2 and clusters 3

Tab.5 Statistical results and correlation coefficients of Delaunay triangulation before and after clustering

[1]	陈洁, 肖春蕾, 李京. 无检校场的机载LiDAR点云数据检校方法[J]. 国土资源遥感, 2015,27(4):27-33.doi: 10.6046/gtzyyg.2015.04.05.
[1]	Chen J, Xiao C L, Li J. Calibration of airborne LiDAR cloud point data with no calibration field[J]. Remote Sensing for Land and Resources, 2015,27(4):27-33.doi: 10.6046/gtzyyg.2015.04.05.
[2]	Fink C M, Drohan P J. High resolution hydric soil mapping using LiDAR digital terrain modeling[J]. Soil Science Society of America Journal, 2016,80(2):355-363.
[3]	李凤霞, 饶永辉, 刘陈, 等. 基于法向夹角的点云数据精简算法[J]. 系统仿真学报, 2012,24(9):1980-1987.
[3]	Li F X, Rao Y H, Liu C, et al. Point cloud simplification based on angle between normal[J]. Journal of System Simulation, 2012,24(9):1980-1987.
[4]	Zhao P C, Wang Y, Hu Q W. A feature preserving algorithm for point cloud simplification based on hierarchical clustering [C]//36th IEEE International Geoscience and Remote Sensing Symposium.Beijing:IGARSS, 2016: 5581-5584.
[5]	李仁忠, 杨曼, 刘阳阳, 等. 一种散乱点云的均匀精简算法[J]. 光学学报, 2017,37(7):97-105.
[5]	Li R Z, Yang M, Liu Y Y, et al. An uniform simplification algorithm for scattered point cloud[J]. Acta Optica Sinica, 2017,37(7):97-105.
[6]	陈龙. 散乱点云特征提取和聚类精简技术研究[D]. 西安:西南科技大学, 2017.
[6]	Chen L. Research on feature extraction and clustering simplification of scattered point cloud[D]. Xi’an:Southwest University of Science and Technology, 2017.
[7]	葛源坤. 基于曲率特征信息的散乱点云数据预处理技术研究[D]. 成都:西南交通大学, 2012.
[7]	Ge Y K. Research on data pre-processing technology of scattered point cloud based on curvatures feature[D]. Chengdu:Southwest Jiaotong University, 2012.
[8]	陈西江, 章光, 花向红. 于法向量夹角信息熵的点云简化算法[J]. 中国激光, 2015,42(8):336-344.
[8]	Chen X J, Zhang G, Hua X H. Point cloud simplification based on the information entropy of normal vector angle[J]. Chinese Journal of Lasers, 2015,42(8):336-344.
[9]	Han H Y, Han X, Sun F S, et al. Point cloud simplification with preserved edge based on normal vector[J]. Optik, 2015,126(19):2157-2162. doi: 10.1016/j.ijleo.2015.05.092 url: https://linkinghub.elsevier.com/retrieve/pii/S0030402615004052
[10]	苏本跃, 马金宇, 彭玉升, 等. 基于K-means聚类的RGBD点云去噪和精简算法[J]. 系统仿真学报, 2016,28(10):2329-2341.
[10]	Su B Y, Ma J Y, Peng Y S, et al. Algorithm for RGBD point cloud denoising and simplification based on K-means clustering[J]. Journal of System Simulation, 2016,28(10):2329-2341.
[11]	唐林. 三维点云数据精简与压缩的研究[D]. 南京:东南大学, 2017.
[11]	Tang L. Research on 3D point cloud data simplification and compression[D]. Nanjing:Southeast University, 2017.
[12]	Li X D, Li W, Jiang H Z, et al. Automatic evaluation of machining allowance of precision castings based on plane features from 3D point cloud[J]. Computers in Industry, 2013,64(9):1129-1137. doi: 10.1016/j.compind.2013.06.003 url: http://dx.doi.org/10.1016/j.compind.2013.06.003
[13]	李乐林, 江万寿, 郭程方. 基于区域多次回波点密度分析的城区LiDAR建筑物提取[J]. 国土资源遥感, 2015,27(2):29-35.doi: 10.6046/gtzyyg.2015.02.05. doi: 10.6046/gtzyyg.2015.02.05 url: http://www.gtzyyg.com/CN/abstract/abstract1854.shtml
[13]	Li L L, Jiang W S, Guo C F. Classification of LiDAR point clouds in urban areas based on the analysis of regional multi-return density[J]. Remote Sensing for Land and Resources, 2015,27(2):29-35.doi: 10.6046/gtzyyg.2015.02.05.
[14]	Cai Z P, Wang C, Wen C L, et al. Occluded boundary detection for small-footprint ground borne LiDAR point cloud guided by last echo[J]. IEEE Geoscience and Remote Sensing Letters, 2015,12(11):2272-2276. doi: 10.1109/LGRS.8859 url: https://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=8859
[15]	Visalakshi N K, Thangavel K. Impact of normalization in distributed K-means clustering[J]. International Journal of Soft Computing, 2009,4(4):168-172.
[16]	樊丽, 刘晋浩, 黄青青. 基于特征融合的林下环境点云分割[J]. 北京林业大学学报, 2016,38(5):133-138.
[16]	Fan L, Liu J H, Huang Q Q. Point cloud segmentation algorithm based on feature fusion used for understory environments[J]. Journal of Beijing Forestry University, 2016,38(5):133-138.
[17]	蔡志敏, 王晏民, 黄明. 基于KD树散乱点云数据的Guass平均曲率精简算法[J].测绘通报, 2013(s1):44-46.
[17]	Cai Z M, Wang Y M, Huang M. Guass mean curvature reduction algorithm based on KD tree scattered point cloud data[J].Bulletin of Surveying and Mapping, 2013(s1):44-46.
[18]	彭占伟. 基于K近邻的点云数据处理研究[D]. 昆明:昆明理工大学, 2014.
[18]	Peng Z W. Research on point cloud data processing based on K-nearest neighbor[D]. Kunming:Kunming University of Science and Technology, 2014.
[19]	陈永辉. 基于激光扫描的三维点云数据处理技术研究[D]. 北京:中国科学技术大学, 2017.
[19]	Chen Y H. Research on data processing techniques based on laser scanning 3D point clouds[D]. Beijing:University of Science and Technology of China, 2017.
[20]	邢正全, 邓喀中, 薛继群. 基于栅格划分和法向量估计的点云数据压缩[J].测绘通报, 2012(7):50-52.
[20]	Xing Z Q, Deng K Z, Xue J Q. Point cloud data compression based on grid division and normal vector estimation[J].Bulletin of Surveying and Mapping, 2012(7):50-52.
[21]	陈龙, 蔡勇, 张建生. 自适应K-means聚类的散乱点云精简[J]. 中国图象图形学报, 2017,22(8):1089-1097.
[21]	Chen L, Cai Y, Zhang J S. Adaptive K-means clustering simplification of scattered point cloud[J]. Journal of Image and Graphics, 2017,22(8):1089-1097.
[22]	赵越, 周萍. 改进的K-means算法在遥感图像分类中的应用[J]. 国土资源遥感, 2011,23(2):87-90.doi: 10.6046/gtzyyg.2011.02.16. doi: 10.6046/gtzyyg.2011.02.16 url: http://www.gtzyyg.com/CN/abstract/abstract627.shtml
[22]	Zhao Y, Zhou P. An improved K-means algorithm for remote sensing classification[J]. Remote Sensing for Land and Resources, 2011,23(2):87-90.doi: 10.6046/gtzyyg.2011.02.16.
[23]	Sebastian Raschka. Python machine learning[M] //Beijing: China Machine Press, 2015.
[24]	张素洁, 赵怀慈. 最优聚类个数和初始聚类中心点选取算法研究[J]. 计算机应用研究, 2017,34(6):1617-1620.
[24]	Zhang S J, Zhao H C. Application research of computers study on the optimal number of clusters and the selection algorithm of initial cluster centers[J]. Application Research of Computers, 2017,34(6):1617-1620.
[25]	Yang Z, Liu X, Hu Z W, et al. Seamless service handoff based on Delaunay triangulation for mobile cloud computing[J]. Wireless Personal Communications, 2017,93(3):795-809. doi: 10.1007/s11277-014-2229-6 url: http://link.springer.com/10.1007/s11277-014-2229-6

[1]	SONG Qi, FENG Chunhui, MA Ziqiang, WANG Nan, JI Wenjun, PENG Jie. Simulation of land use change in oasis of arid areas based on Landsat images from 1990 to 2019[J]. Remote Sensing for Natural Resources, 2022, 34(1): 198-209.
[2]	REN Chaofeng, PU Yuchi, ZHANG Fuqiang. A method for extracting match pairs of UAV images considering geospatial information[J]. Remote Sensing for Natural Resources, 2022, 34(1): 85-92.
[3]	ZANG Liri, YANG Shuwen, SHEN Shunfa, XUE Qing, QIN Xiaowei. A registration algorithm of images with special textures coupling a watershed with mathematical morphology[J]. Remote Sensing for Natural Resources, 2022, 34(1): 76-84.
[4]	PAN Jianping, XU Yongjie, LI Mingming, HU Yong, WANG Chunxiao. Research and development of automatic detection technologies for changes in vegetation regions based on correlation coefficients and feature analysis[J]. Remote Sensing for Natural Resources, 2022, 34(1): 67-75.
[5]	XUE Bai, WANG Yizhe, LIU Shuhan, YUE Mingyu, WANG Yiying, ZHAO Shihu. Change detection of high-resolution remote sensing images based on Siamese network[J]. Remote Sensing for Natural Resources, 2022, 34(1): 61-66.
[6]	JIANG Na, CHEN Chao, HAN Haifeng. An optimization method of DEM resolution for land type statistical model of coastal zones[J]. Remote Sensing for Natural Resources, 2022, 34(1): 34-42.
[7]	WU Fang, LI Yu, JIN Dingjian, LI Tianqi, GUO Hua, ZHANG Qijie. Application of 3D information extraction technology of ground obstacles in the flight trajectory planning of UAV airborne geophysical exploration[J]. Remote Sensing for Natural Resources, 2022, 34(1): 286-292.
[8]	WANG Qian, REN Guangli. Application of hyperspectral remote sensing data-based anomaly extraction in copper-gold prospecting in the Solake area in the Altyn metallogenic belt, Xinjiang[J]. Remote Sensing for Natural Resources, 2022, 34(1): 277-285.
[9]	LIU Wen, WANG Meng, SONG Ban, YU Tianbin, HUANG Xichao, JIANG Yu, SUN Yujiang. Surveys and chain structure study of potential hazards of ice avalanches based on optical remote sensing technology: A case study of southeast Tibet[J]. Remote Sensing for Natural Resources, 2022, 34(1): 265-276.
[10]	YAO Jinxi, ZHANG Zhi, ZHANG Kun. An analysis of the characteristics, causes, and trends of spatio-temporal changes in vegetation in the Nuomuhong alluvial fan based on Google Earth Engine[J]. Remote Sensing for Natural Resources, 2022, 34(1): 249-256.
[11]	WU Yijie, KONG Xuesong. Simulation and development mode suggestions of the spatial pattern of “ecology-agriculture-construction” land in Jiangsu Province[J]. Remote Sensing for Natural Resources, 2022, 34(1): 238-248.
[12]	ZHANG Qinrui, ZHAO Liangjun, LIN Guojun, WAN Honglin. Ecological environment assessment of three-river confluence in Yibin City using improved remote sensing ecological index[J]. Remote Sensing for Natural Resources, 2022, 34(1): 230-237.
[13]	HU Yingying, DAI Shengpei, LUO Hongxia, LI Hailiang, LI Maofen, ZHENG Qian, YU Xuan, LI Ning. Spatio-temporal change characteristics of rubber forest phenology in Hainan Island during 2001—2015[J]. Remote Sensing for Natural Resources, 2022, 34(1): 210-217.
[14]	SUN Yiming, ZHANG Baogang, WU Qizhong, LIU Aobo, GAO Chao, NIU Jing, HE Ping. Application of domestic low-cost micro-satellite images in urban bare land identification[J]. Remote Sensing for Natural Resources, 2022, 34(1): 189-197.
[15]	ZHENG Xiucheng, ZHOU Bin, LEI Hui, HUANG Qiyu, YE Haolin. Extraction and spatio-temporal change analysis of the tidal flat in Cixi section of Hangzhou Bay based on Google Earth Engine[J]. Remote Sensing for Natural Resources, 2022, 34(1): 18-26.

Viewed

Full text

Abstract

Cited

Shared

Discussed