Scattered Point Cloud Simplification Algorithm Integrating <i>k</i>-means Clustering and Hausdorff Distance

LI Jian; CAO Yao; WANG Zongmin; WANG Guangyin

doi:10.13203/j.whugis20180204

Volume 45 Issue 2

Feb. 2020

Turn off MathJax

Article Contents

Abstract

References

Geomatics and Information Science of Wuhan University > 2020 > 45(2): 250-257. > DOI: 10.13203/j.whugis20180204

LI Jian, CAO Yao, WANG Zongmin, WANG Guangyin. Scattered Point Cloud Simplification Algorithm Integrating k-means Clustering and Hausdorff Distance[J]. Geomatics and Information Science of Wuhan University, 2020, 45(2): 250-257. DOI: 10.13203/j.whugis20180204

Citation:

PDF (21952 KB)

Scattered Point Cloud Simplification Algorithm Integrating k-means Clustering and Hausdorff Distance

LI Jian^1,,
CAO Yao^2, ,,
WANG Zongmin^{2, 3},
WANG Guangyin²

1.
School of the Geo-Science & Technology, Zhengzhou University, Zhengzhou 450001, China
2.
School of Water Conservancy and Environment, Zhengzhou University, Zhengzhou 450001, China
3.
Zhongyuan University of Technology, Zhengzhou 450007, China

Funds:

The National Natural Science Foundation of China 51678536

the Open Research Fund of State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing 15E01

Key Scientific Research Projects of Colleges and Universities of Henan Provincial Department of Education 14A420002

More Information

Author Bio:
LI Jian, PhD, associate professor, specializes in LiDAR point cloud data processing and 3D reconstruction. E-mail:lijian5277@163.com
Corresponding author:
CAO Yao, master. E-mail: 772440651@qq.com
Received Date: June 13, 2019
Published Date: February 04, 2020

Graphical Abstract

Abstract

Abstract

Aiming at the incomplete retention of features during the point cloud data procession by point cloud simplification algorithm, and data holes caused by small-curvature point cloud simplification algorithm, this paper proposes a new point cloud simplification algorithm integrated k-means clustering and Hausdorff distance. The topological adjacency is established in the new simplification algorithm based on the OcTree algorithm.Then the principal curvatures of all point cloud is calculated and the Hausdorff distance of the principal curvatures is calculated, and the Hausdorff distance threshold set by the requirements of the reduced target is used to extracted the point cloud feature. Finally, k-means clustering is performed on non-feature regions to extract feature points, and the extracted feature points are merged to obtain reduced results. Results show that the proposed algorithm can retain the feature information of the model more completely and avoid the void phenomena.
- point cloud simplification,
- Hausdorff distance,
- k-means clustering,
- curved surface fitting

FullText(HTML)

References (22)

References

[1]	龚健雅, 崔婷婷, 单杰, 等.利用车载移动测量数据的建筑物立面建模方法[J].武汉大学学报·信息科学版, 2015, 40(9): 1 137- 1 143 http://ch.whu.edu.cn/CN/abstract/abstract3311.shtml Gong Jianya, Cui Tingting, Shan Jie, et al. A Survey on Facade Modeling Using LiDAR Point Clouds and Image Sequences Collected by Mobile Mapping Systems[J]. Geomatics and Information Science of Wuhan University, 2015, 40(9): 1 137-1 143 http://ch.whu.edu.cn/CN/abstract/abstract3311.shtml
[2]	闫利, 胡晓斌, 谢洪.车载LiDAR海量点云数据管理与可视化研究[J].武汉大学学报·信息科学版, 2017, 42(8): 1 131-1 136 http://ch.whu.edu.cn/CN/abstract/abstract5807.shtml Yan Li, Hu Xiaobin, Xie Hong. Data Management and Visualization of Mobile Laser Scanning Point Cloud[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1 131-1 136 http://ch.whu.edu.cn/CN/abstract/abstract5807.shtml
[3]	张顺岚, 莫建文, 邹路路.基于k近邻和法向精度的点云精简算法[J].武汉理工大学学报(交通科学与工程版), 2014, 38(3): 572-575 doi: 10.3963/j.issn.2095-3844.2014.03.022 Zhang Shunlan, Mo Jianwen, Zou Lulu. Point Cloud Simplification Algorithm Based on k Neighbor and Normal Accuracy[J]. Journal of Wuhan University of Technology (Transportation Science & Engineering), 2014, 38(3): 572-575 doi: 10.3963/j.issn.2095-3844.2014.03.022
[4]	李健, 王宗敏, 马玉荣, 等.多站激光点云数据全自动高精度拼接方法研究[J].武汉大学学报·信息科学版, 2014, 39(9): 1 114-1 120 http://ch.whu.edu.cn/CN/abstract/abstract3081.shtml Li Jian, Wang Zongmin, Ma Yurong, et al. Automatic and Accurate Mosaicking of Point Clouds from Multi-station Laser Scanning[J]. Geomatics and Information Science of Wuhan University, 2014, 39(9): 1 114-1 120 http://ch.whu.edu.cn/CN/abstract/abstract3081.shtml
[5]	Sun W, Bradley C, Zhang Y F, et al. Cloud Data Modelling Employing a Unified, Non-redundant Triangula Mesh[J]. Computer-Aided Design, 2001, 33(2): 183-193 doi: 10.1016/S0010-4485(00)00088-9
[6]	李仁忠, 杨曼, 刘阳阳, 等.一种散乱点云的均匀精简算法[J].光学学报, 2017, 37(7): 97-105 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=gxxb201707012 Li Renzhong, Yang Man, Liu Yangyang, et al. An Uniform Simplification Algorithm for Scattered Point Cloud[J]. Acta Optica Sinica, 2017, 37(7): 97-105 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=gxxb201707012
[7]	Han H, Han X, Sun F, et al. Point Cloud Simplification with Preserved Edge Based on Normal Vector[J]. Optik-International Journal for Light and Electron Optics, 2015, 126(19):2 157-2 162 doi: 10.1016/j.ijleo.2015.05.092
[8]	Tonini M, Abellan A. Rockfall Detection from Terrestrial LiDAR Point Clouds: A Clustering Approach Using R[J]. Journal of Spatial Information Science, 2014(8): 95-110
[9]	Weir D J, Milroy M J, Bradley C, et al. Reverse Engineering Physical Models Employing Wrap-Around B-spline Surfaces and Quadrics[J].Proceedings of the Institution of Mechanical Engineers Part B Journal of Engineering Manufacture, 1996, 210(22): 147-157 doi: 10.1243-PIME_PROC_1996_210_100_02/
[10]	Wang L, Chen J, Yuan B. Simplified Representation for 3D Point Cloud Data[C]. IEEE International Conference on Signal Processing, Beijing, China, 2010
[11]	Lee K H, Woo H, Suk T. Point Data Reduction Using 3D Grids[J]. International Journal of Advanced Manufacturing Technology, 2001, 18(3): 201-210 doi: 10.1007/s001700170075
[12]	Yuan S, Zhu S, Li D S, et al. Feature Preserving Multiresolution Subdivision and Simplification of Point Clouds: A Conformal Geometric Algebra Approach[J]. Mathematical Methods in the Applied Sciences, 2017, 41(10): 4 074-4 087
[13]	杨秋翔, 杨小青, 杜健.基于Hausdorff距离的点云分片精简算法[J].计算机工程与设计, 2016, 37(8):2 105-2 109 http://d.old.wanfangdata.com.cn/Periodical/jsjgcysj201608024 Yang Qiuxiang, Yang Xiaoqing, Du Jian. Point Cloud Simplification Algorithm Based on Hausdorff Distance and Segmentation[J]. Computer Engineering and Design, 2016, 37(8): 2 105-2 109 http://d.old.wanfangdata.com.cn/Periodical/jsjgcysj201608024
[14]	陈璋雯, 达飞鹏.基于模糊熵迭代的三维点云精简算法[J].光学学报, 2013, 33(8):161-167 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=gxxb201308025 Chen Zhangwen, Da Feipeng. 3D Point Cloud Simplification Algorithm Based on Fuzzy Entropy Iteration[J]. Acta Optica Sinica, 2013, 33(8): 161-167 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=gxxb201308025
[15]	Shi B Q, Liang J, Liu Q. Adaptive Simplification of Point Sloud Using k-means Clustering[J]. Computer-Aided Design, 2011, 43(8): 910-922 doi: 10.1016/j.cad.2011.04.001
[16]	吕钊, 康志忠.利用地面激光扫描数据进行建筑物变化检测[J].武汉大学学报·信息科学版, 2011, 36(11): 1 284-1 289 http://ch.whu.edu.cn/CN/abstract/abstract712.shtml Lv Zhao, Kang Zhizhong. Change Detection of Buildings Based on Terrestrial Laser Scanning Data[J]. Geomatics and Information Science of Wuhan University, 2011, 36(11): 1 284-1 289 http://ch.whu.edu.cn/CN/abstract/abstract712.shtml
[17]	Li T, Pan Q, Gao L, et al. A Novel Simplification Method of Point Cloud with Directed Hausdorff Distance[C]. IEEE 21st International Conference on Computer Supported Cooperative Work in Design (CSCWD), Wellington, New Zealand, 2017
[18]	周玉莲.基于法矢信息的点云特征提取技术的研究[D].哈尔滨: 哈尔滨工业大学, 2012 http://cdmd.cnki.com.cn/Article/CDMD-10213-1013039165.htm Zhou Yulian. Feature Extruction of Point Cloud Based on Normal Information[D]. Harbin: Harbin Institute of Technology, 2012 http://cdmd.cnki.com.cn/Article/CDMD-10213-1013039165.htm
[19]	朱煜, 康宝生, 李洪安, 等.一种改进的点云数据精简方法[J].计算机应用, 2012, 32(2):521-523 http://d.old.wanfangdata.com.cn/Periodical/jsjyy201202057 Zhu Yu, Kang Baosheng, Li Hong'an, et al. Improved Algorithm for Point Cloud Data Simplification[J]. Journal of Computer Applications, 2012, 32(2): 521-523 http://d.old.wanfangdata.com.cn/Periodical/jsjyy201202057
[20]	袁小翠, 吴禄慎, 陈华伟.特征保持点云数据精简[J].光学精密工程, 2015, 23(9):2 666-2 676 http://d.old.wanfangdata.com.cn/Periodical/gxjmgc201509030 Yuan Xiaocui, Wu Lushen, Chen Huawei. Feature Preserving Point Cloud Simplification[J]. Optics and Precision Engineering, 2015, 23(9): 2 666-2 676 http://d.old.wanfangdata.com.cn/Periodical/gxjmgc201509030
[21]	史宝全, 梁晋, 刘青, 等.基于约束搜索球的点云数据与CAD模型精确比对检测[J].计算机集成制造系统, 2010, 16(5): 929-934 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201005005 Shi Baoquan, Liang Jin, Liu Qing, et al. Precision Inspection of Point Cloud & CAD Model Based on Constraint Search Sphere[J]. Computer Integrated Manufacturing Systems, 2010, 16(5): 929-934 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201005005
[22]	傅思勇, 吴禄慎, 陈华伟.空间栅格动态划分的点云精简方法[J].光学学报, 2017, 37(11): 253-261 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=gxxb201711029 Fu Siyong, Wu Lushen, Chen Huawei. Point Cloud Simplification Method Based on Space Grid Dynamic Partitioning[J]. Acta Optica Sinica, 2017, 37(11):253-261 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=gxxb201711029

[1]	HUANG Pan, TANG Jinsong, ZHONG Heping, XU Kui. A New InSAS Registration Method Based on Rational Function Surface Fitting[J]. Geomatics and Information Science of Wuhan University, 2019, 44(4): 601-607. DOI: 10.13203/j.whugis20170167
[2]	LI Pengcheng, XU Qing, XING Shuai, LIU Zhiqing, ZHANG Junjun. Weighted Curve Fitting Filtering Method Based on Full-Waveform LiDAR Data[J]. Geomatics and Information Science of Wuhan University, 2018, 43(3): 420-427. DOI: 10.13203/j.whugis20150377
[3]	LI Guojun, LI Zongchun, SUN Yuanchao, LI Wei, HUANG Zhiyong. Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 123-129. DOI: 10.13203/j.whugis20140513
[4]	YANG Jun, LIN Yanlong, ZHANG Ruifeng, WANG Xiaopeng. A Fast Algorithm for Finding k-nearest Neighbors of Large-Scale Scattered Point Cloud[J]. Geomatics and Information Science of Wuhan University, 2016, 41(5): 656-664. DOI: 10.13203/j.whugis20140191
[5]	CHEN Xijiang, HUA Xianghong, YANG Ronghua, ZHANG Qinghua. Planar Target Location Based on the Zoning K-means Clustering[J]. Geomatics and Information Science of Wuhan University, 2013, 38(2): 167-170.
[6]	SU Hongjun, SHENG Yehua. Supervised K-means Clustering Analysis for Hyperspectral Imagery[J]. Geomatics and Information Science of Wuhan University, 2012, 37(6): 640-643.
[7]	SHU Chanfang, LI Fei, HAO Weifeng. Geoid/Quasigeoid Fitting Based on Equivalent Point Masses[J]. Geomatics and Information Science of Wuhan University, 2011, 36(2): 231-234.
[8]	GU Chuan, PAN Guorong, SHI Guigang, CHEN Xingquan. Parameter Identification of Surface Fitting Based on Genetic Algorithm[J]. Geomatics and Information Science of Wuhan University, 2009, 34(8): 983-986.
[9]	HAN Yuanli, HU Peng, HUANG Xuelian, ZHANG Lihua. k-Data Field Approximation Method Based on k-Voronoi Diagram Division[J]. Geomatics and Information Science of Wuhan University, 2007, 32(4): 353-357.
[10]	ZHANG Mengjun, SHU Hong, LIU Yan, WANG Tao. An Adaptive Thresholding Approach Based on Spatial Curved Surface Fitting[J]. Geomatics and Information Science of Wuhan University, 2006, 31(5): 395-398.

Cited By

Cited by

Periodical cited type(16)

1.	陈冠华，李博，朱铮涛. 基于改进PointNet的空调散热器V形槽3D点云分割算法. 科学技术与工程. 2024(05): 1963-1971 .
2.	刘源，左小清，李勇发，杨栩，周定义，黄琨. 使用冯·米塞斯分布提取特征的点云精简方法. 激光与光电子学进展. 2023(02): 341-351 .
3.	尹金林，王春香，刘流，王齐超，潘杙成. 面向三维残缺点云图像的数据精简方法. 科学技术与工程. 2023(04): 1607-1614 .
4.	李祎承，杨东晓，高翔，马育林，许述财. 面向智能汽车的地下停车场定位与路径规划. 光学精密工程. 2023(05): 757-766 .
5.	张永建，张翔宇，丁晓，陈雨，白晓亮. 面向MR远程协同任务的实物虚拟化方法研究. 航空制造技术. 2023(12): 117-127 .
6.	马庆禄，黄筱潇，孔国英. 基于通道注意力和图卷积的激光三维目标检测. 计算机工程与设计. 2023(09): 2740-2746 .
7.	章紫辉，官云兰. 基于邻域点位置特征的点云数据精简. 激光与光电子学进展. 2023(16): 393-402 .
8.	李伟华，刘良林，李久明，吕超. 联合点曲率值与竖直平面约束的点云简化算法. 井冈山大学学报(自然科学版). 2023(06): 84-92 .
9.	林俊杰，刘昊洋. 基于GPU加速的多源点云融合算法研究. 大众科技. 2023(12): 11-14 .
10.	彭海驹，严科文，林松，赖浩源，张泽鑫. 融合kmeans聚类与Hausdorff距离的点云精简算法改进. 地理空间信息. 2022(08): 59-63 .
11.	李茂月，赵伟翔，马康盛，王飞. 结构光检测点云精简与重构参数自动调节方法. 仪器仪表学报. 2022(08): 122-130 .
12.	张丹生. 基于传感器网络的学生体能训练监测系统研究. 自动化与仪器仪表. 2022(10): 143-149 .
13.	张博，祝海江. 大型储罐的三维点云精简方法研究. 北京化工大学学报(自然科学版). 2022(05): 84-90 .
14.	高春艳，郭亮，吕晓玲，孙凌宇. 多平台数据融合系统的航迹关联技术. 科学技术与工程. 2021(08): 3169-3173 .
15.	李寅龙，张天舒. 基于时间滑窗的混合Hausdorff距离航迹关联算法. 舰船电子工程. 2021(10): 52-56+60 .
16.	陈兴蜀，常天祐，王海舟，赵志龙，张杰. 基于微博数据的“新冠肺炎疫情”舆情演化时空分析. 四川大学学报(自然科学版). 2020(02): 409-416 .

Other cited types(22)

Get Citation

PDF

XML

Article views (2074) PDF downloads (179) Cited by(38)

Scattered Point Cloud Simplification Algorithm Integrating k-means Clustering and Hausdorff Distance

Abstract

References

Related Articles

Cited by

Periodical cited type(16)

Other cited types(22)

Catalog

Related

Scattered Point Cloud Simplification Algorithm Integrating k-means Clustering and Hausdorff Distance

Abstract

References

Related Articles

Cited by

Periodical cited type(16)

Other cited types(22)

Catalog

Related

Export File

Citation

Format

Content