基于k-d树的多波束点云边缘与孔洞提取算法  

An algorithm of contour extraction applied to multibeam bathymetric point cloud based on k-d tree

作　　者：吴冬强 于宗泽[1,2] 傅晓洲 利明泽 WU Dongqiang;YU Zongze;FU Xiaozhou;LI Mingze(Key Laboratory of Marine Mineral Resoures,Ministry of Natural Resources,Guangzhou Marine Geological Survey,China Geological Survey,Guangzhou 510075,China;National Engineering Research Center for Gas Hydrate Exploration and Development,Guangzhou 266590,China)

机构地区：[1]自然资源部海底矿产资源重点实验室,中国地质调查局广州海洋地质调查局,广东广州510075 [2]天然气水合物勘查开发国家工程研究中心,广东广州266590

出　　处：《海洋测绘》2023年第6期12-15,共4页Hydrographic Surveying and Charting

基　　金：国家自然科学基金面上项目(42072324);中国地质调查局地调二级项目(DD20221718)。

摘　　要：多波束测深数据广泛服务于水下地形测量。一些基于测深数据的应用需要提取测深数据的边缘轮廓和探测数据中的空洞。针对已有边缘识别算法执行效率低、边界点提取不完整等问题,通过分析点云模型的局部几何属性,提出一种新的基于k-d树的由粗到精的边缘提取算法。首先抽稀测深数据,基于k-d树建立散乱点云的拓扑关系;然后计算散乱点云法向量,采用距离及角度阈值法进一步提取孔洞与边缘轮廓点并去除错误识别的点;最后基于凹包算法,精确获取边缘轮廓点。在西太平洋海域的实验表明:相较于Alpha-shape和Boundary estimation算法,本算法能够更为精确地识别出散乱点云中的边界点,实用性强。Multibeam echo sounders are widely applied to marine survey.Some work applications need to extract the edge profiles and the holes from bathymetric data.Aiming at the problems of low execution efficiency of the existing hole recognition algorithm and incomplete extraction of hole boundary points,a new edge extraction algorithm from coarse to fine based on k-d tree is proposed by analyzing the local geometric properties of the point cloud model.Firstly,the number of point clouds to be calculated is reasonably reduced.The topological relationship of scattered point clouds is established by k-d tree.Then,the normal vector is calculated for the remaining points,and the distance and angle thresholds are used to further extract the hole and edge contour points to remove the incorrectly identified points;Finally,based on the concave envelope algorithm,the edge outline points are accurately obtained in the original data set.The experiments in the Western Pacific show that,compared with Alpha-shape and Boundary estimation algorithm,the new algorithm can quickly identify the boundary points in the scattered point cloud and have strong practicability.

关 键 词：多波束测深点云 边缘提取 快速邻域搜索 K-D树 凹包算法 

分 类 号：P229.3[天文地球—大地测量学与测量工程]