三维数据重建中距离图的优化计算

摘要

In this paper, the optimal k-d tree algorithm for k-NN (k-Nearest Neighbor) searching in 3D space is developed and applied to compute the distance map in hierarchical reconstruction for visualizing the 3D data. It is shown by the simulation experiment that the algorithm optimizes the distance map computation and achieves higher efficiency. It is felt, the algorithm could be quite useful in many other applications.%拟合模型与三维数据间距离图计算是三维数据重建中的主要计算之一，决定了重建算法的实时性。本文设计了基于优化k-d树的三维空间k个最近点（k-NN：k-Nearest Neighbour）搜索算法，提高了搜索效率，使距离图计算时间大大减少，满足了三维数据层次式重建的计算实时性要求。作为三维空间最近点搜索的最佳算法之一，基于优化k-d树的最近点搜索算法可在更广泛的领域应用。