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

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