基于几何特征枝干点云骨架提取最短路径算法

Shortest Path Extraction Algorithm of Tree Branch Point Cloud Skeleton Based on Geometric Characteristics

树木建模广泛应用于林业信息化等领域,点云各项优良特性使其也称为树木建模主要方法。基于几何特征的树木枝干点云骨架提取中以根节点距离相似归类的方法在枝条分叉处更加合理,而该方法的实际应用受制于传统使用的最短路径求解算法的Dijkstra算法因而较少。主要针对树木枝干点云,将现有若干最短路径算法进行相应的改进以应用于基于几何特征的树木枝干点云骨架提取中。通过实际数据验证可知,利用邻接表能够大幅度降低内存需求,相较于以往采用的Dijkstra算法,SPFA的执行速度是理想的,更加快速,能够对精细化点云树木建模提供帮助。

Tree modeling is widely used in 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 algorithma traditional algorithm of solving the shortest path.This research mainly aimed at the tree branch point cloud,and improved some existing shortest path algorithms respectively to be applied to extracting tree branch point cloud skeleton based on geometric characteristics.The verification of actual data indicated that the use of adjacency table could greatly reduce the memory requirements.Compared with the previous adopted Dijkstra's algorithm,the execution speed of SPFA was satisfactory and faster,which could provide help for the fine point cloud tree modeling.