海洋测绘2023，Vol.43Issue(6)：12-15,4.DOI:10.3969/j.issn.1671-3044.2023.06.003
基于k-d树的多波束点云边缘与孔洞提取算法
An algorithm of contour extraction applied to multibeam bathymetric point cloud based on k-d tree
摘要
Abstract
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树/凹包算法Key words
multibeam bathymetric point cloud/boundary extraction/rapid neighborhood search/k-d tree/concave envelope分类
天文与地球科学引用本文复制引用
吴冬强,于宗泽,傅晓洲,利明泽..基于k-d树的多波束点云边缘与孔洞提取算法[J].海洋测绘,2023,43(6):12-15,4.基金项目
国家自然科学基金面上项目(42072324) （42072324）
中国地质调查局地调二级项目(DD20221718). （DD20221718）
