激光散乱点云K最近邻搜索算法  

K-nearest neighbor searching algorithm for laser scattered point cloud

作　　者：赵京东[1] 杨凤华[1] 

机构地区：[1]曲阜师范大学数学科学学院,山东曲阜273165

出　　处：《计算机应用》2016年第10期2863-2869,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61104136);曲阜师范大学实验室开放基金资助项目(sk201418)~~

摘　　要：针对激光散乱点云的数据量大,且具有面型的特点,为降低存储器使用量,提高散乱点云的处理效率,提出了一种散乱点云K最近邻(KNN)搜索算法。首先,利用多级分块、动态链表的存储方式,只存储非空的子空间编号。对相邻子空间进行3进制编码,利用编码的对偶关系,建立相邻子空间之间的指针连接,构造出包含KNN搜索所需的各类信息的广义表,然后再搜索KNN。KNN搜索过程中,在计算被测点到候选点距离时,直接删除筛选立方体内切球之外的点,可将参入按距离排序的候选点数减少为现有算法的一半。依赖K值和不依赖K值的分块原则,均可计算不同的K邻域。实验结果表明,该算法不仅具有低的存储器使用量,而且具有较高的效率。Aiming at the problem of large amount of data and characteristics of surface in laser scattered point cloud, a K-Nearest Neighbors （KNN） searching algorithm for laser scattered point cloud was put forward to reduce memory usage and improve processing efficiency. Firstly, only the non-empty subspace numbers were stored by multistage classification and dynamic linked list storage. Adjacent subspace was coded in ternary, and the pointer connection between adjacent subspaces was established by dual relationship of code, a generalized table that contained all kinds of required information for KNN searching was constructed, then KNN were searched. In the process of KNN searching, the candidate points outside inscribed sphere of filtration cube were directly deleted when calculating the distance from measured point to candidate points, thus reducing the candidate points that participate in the sort by distance to half. Both dividing principles, whether it relies on K value or not, can be used to calculate different K neighborhoods. Experimental results prove that the proposed algorithm not only has low memory usage, but also has high efficiency.

关 键 词：散乱点云 子空间 K最近邻 广义表 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]