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

Abstract: 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.

Key words: scattered point cloud, subspace, K-Nearest Neighbors (KNN), generalized list