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

来源：计算机应用杂志2016年第10期北京时间：

作者：赵京东, 杨凤华

单位：曲阜师范大学 数学科学学院, 山东 曲阜 273165

摘要：针对激光散乱点云的数据量大，且具有面型的特点，为降低存储器使用量，提高散乱点云的处理效率，提出了一种散乱点云K最近邻（KNN）搜索算法。首先，利用多级分块、动态链表的存储方式，只存储非空的子空间编号。对相邻子空间进行3进制编码，利用编码的对偶关系，建立相邻子空间之间的指针连接，构造出包含KNN搜索所需的各类信息的广义表，然后再搜索KNN。KNN搜索过程中，在计算被测点到候选点距离时，直接删除筛选立方体内切球之外的点，可将参入按距离排序的候选点数减少为现有算法的一半。依赖K值和不依赖K值的分块原则，均可计算不同的K邻域。实验结果表明，该算法不仅具有低的存储器使用量，而且具有较高的效率。

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

基金资助：国家自然科学基金资助项目（61104136）；曲阜师范大学实验室开放基金资助项目（sk201418）。