基于几何特征枝干点云骨架提取最短路径算法
Shortest Path Extraction Algorithm of Tree Branch Point Cloud Skeleton Based on Geometric Characteristics
树木建模广泛应用于林业信息化等领域,点云各项优良特性使其也称为树木建模主要方法。基于几何特征的树木枝干点云骨架提取中以根节点距离相似归类的方法在枝条分叉处更加合理,而该方法的实际应用受制于传统使用的最短路径求解算法的 Dijkstra 算法因而较少。本研究主要针对树木枝干点云,将现有典型最短路径算法进行相应的改进以应用于基于几何特征的树木枝干点云骨架提取中。通过实际数据验证可知,利用邻接表能够大幅度降低内存需求,相较于以往采用的 Dijkstra 算法,SPFA 的执行速度是理想的,更加快速,能够对精细化点云树木建模提供帮助。
Nowadays,tree modeling is widely used in computer games,forestry informatization and other fields.The excellent characteristics of point cloud make it also known as the main method of tree modeling.In the field of extracting tree branch point cloud skeleton based on geometric characteristics,the method that uses the similarity of the shortest-path distance between each point and the root point to classify is more reasonable in trunk bifurcations,but this method has less practical application as it is subject to Dijkstra algorithm-a traditional algorithm of solving the shortest path.This research mainly aims at the tree branch point cloud,and improves the existing shortest path algorithm to be applied to extracting tree branch point cloud skeleton based on geometric characteristics.Through the verification of actual data,it can be seen that the use of adjacency table can greatly reduce the memory requirements.Compared with the previous adopted Dijkstra's algorithm,the execution speed of SPFA is ideal and faster,which can provide help for the fine point cloud tree modeling.
杨杰;温小荣;叶金盛;汪求来;
南京林业大学林学院 ,江苏 南京 210037;南京林业大学南方现代林业协同创新中心,江苏 南京 210037##南京林业大学林学院 ,江苏 南京 210037;广东省林业调查规划院,广东 广州 510520;广东省林业调查规划院,广东 广州 510520;
point cloud tree modeling skeleton extraction shortest path
1949-1962 / 14
评论