Novel algorithm for fast extracting edges from massive point clouds

doi:10.3778/j.issn.1002-8331.2010.36.059

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (36): 213-215.DOI: 10.3778/j.issn.1002-8331.2010.36.059

• 图形、图像、模式识别 • Previous Articles Next Articles

Novel algorithm for fast extracting edges from massive point clouds

WANG Zong-yue^1，2，MA Hong-chao²，XU Hong-gen³，YANG Zhi-wei¹

1.Computer Engineering College，Jimei University，Xiamen，Fujian 361021，China
2.School of Remote Sensing and Information Engineering，Wuhan University，Wuhan 430072，China
3.China Aero Geophysical Survey and Remote Sensing Center for Land and Resources，Beijing 100083，China

Received:2010-06-28 Revised:2010-10-22 Online:2010-12-21 Published:2010-12-21
Contact: WANG Zong-yue

海量点云的边缘快速提取算法

王宗跃^1，2，马洪超²，徐宏根³，杨志伟¹

1.集美大学计算机工程学院，福建厦门 361021
2.武汉大学遥感信息工程学院，武汉 430072
3.中国国土资源航空物探遥感中心，北京 100083

通讯作者: 王宗跃

Abstract

Abstract: A novel algorithm is proposed for fast extracting edges from massive point clouds in this paper.First，organize point cloud data in grid form，and then exclude non-edge discrete points，at last extract edges in the condition of Alpha Shapes.The algorithm sacrifices a small amount time on grid data organization，while saving a lot of Alpha Shapes conditional time，thereby significantly improves the efficiency.This algorithm has been realized in the VC environment，and experimental results show that the algorithm can extract outer boundary，holes and other functions，and is high efficiency.

Key words: Light Detection And Ranging（LiDAR）, point clouds, edges

摘要： 提出一种海量点云边缘快速提取算法。该算法先对点云数据进行格网组织，然后排除非边缘的离散点，最后采用Alpha Shapes判断条件提取边缘。该算法牺牲少量格网数据组织时间，节约大量的Alpha Shapes条件判断时间，从而显著提高算法效率。在VC环境下实现了该算法，实验结果表明该算法不仅具有提取外边界、空洞等功能，而且效率高。

关键词: 机载激光雷达, 点云, 边缘

CLC Number:

P237.3

WANG Zong-yue^1，2，MA Hong-chao²，XU Hong-gen³，YANG Zhi-wei¹. Novel algorithm for fast extracting edges from massive point clouds[J]. Computer Engineering and Applications, 2010, 46(36): 213-215.

王宗跃^1，2，马洪超²，徐宏根³，杨志伟¹. 海量点云的边缘快速提取算法[J]. 计算机工程与应用, 2010, 46(36): 213-215.

[1]	LI Zhongdao, LIU Yuansheng, CHANG Feixiang, ZHANG Jun, LU Ming. Research on UWB and LiDAR Fusion Positioning Algorithm in Indoor Environment [J]. Computer Engineering and Applications, 2021, 57(6): 260-266.
[2]	XU Jingzhong, MA Lina. Automatic Boundary Extraction from Building Point Clouds Based on Virtual Grids [J]. Computer Engineering and Applications, 2021, 57(10): 181-186.
[3]	ZHAO Long, WEI Qun. Research and improvement of point clouds reducing algorithm based on a set of images in progress of 3D-reconstruction [J]. Computer Engineering and Applications, 2016, 52(8): 211-216.
[4]	SUN Pengpeng, MIN Haigen, XU Zhigang, ZHAO Xiangmo. Real-time ground point clouds extraction algorithm using extended vertices [J]. Computer Engineering and Applications, 2016, 52(24): 6-10.
[5]	LIN Chengda1, FANG Yihang1, CHANG Tingting1, JI Zheng2, ZHAI Ruifang3. Fine reconstruction of objects by integrating close range point clouds and digital images [J]. Computer Engineering and Applications, 2015, 51(21): 185-190.
[6]	YOU Anqing1, HAN Xiaoyan2, PAN Xudong1, HE Xi1. Optimizations of spatial distance check algorithm in power transmission system [J]. Computer Engineering and Applications, 2014, 50(17): 259-262.
[7]	DONG Baogen1, QIN Zhiyuan1, CHEN Jing2, XU Yanbing3. Threshold-free method for airborne LiDAR point clouds data filtering [J]. Computer Engineering and Applications, 2013, 49(15): 219-223.
[8]	ZHI Xiao-dong¹，LIN Zong-jian²，SU Guo-zhong³，ZHONG Liang¹. Research on organization of airborne LiDAR points cloud based on improved quadtree algorithm [J]. Computer Engineering and Applications, 2010, 46(9): 71-74.
[9]	LI Bao，CHENG Zhi-quan，DANG Gang，JIN Shi-yao . Survey on normal estimation for 3D point clouds [J]. Computer Engineering and Applications, 2010, 46(23): 1-7.
[10]	WANG Zong-yue^1，2，MA Hong-chao²，WU Jian-wei²，XU Hong-gen³，PENG Jian-gui². Novel method to evaluate contours’ quality [J]. Computer Engineering and Applications, 2010, 46(20): 30-32.
[11]	WANG Zong-yue^1，2，MA Hong-chao²，XU Hong-gen³，WU Jian-wei²，PENG Jian-gui². Method of parallel contours extraction based on cluster and multi-core CPU [J]. Computer Engineering and Applications, 2010, 46(17): 5-7.
[12]	LV Fang-mei^1,2,XI Jun-tong¹,MA Deng-zhe¹. Topological features detection and automatic segmentation of point clouds from human body surface [J]. Computer Engineering and Applications, 2008, 44(6): 196-198.

Novel algorithm for fast extracting edges from massive point clouds

海量点云的边缘快速提取算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 12

Recommended Articles

Metrics