迭代最近点匹配算法的树结构k近邻搜索比较研究

Comparative study on tree structure-based KNN methods of ICP matching algorithm

为提高ICP匹配算法中k近邻搜索的存储和计算效率,本文分析总结了几种树结构k近邻搜索算法,利用模拟和实测数据实验对比研究了它们对ICP匹配结果的影响。实验结果表明,几种算法的拉入范围相同,匹配精度差异较小,主要差异在于搜索效率不同。其中,主轴搜索树k近邻算法的存储结构较优,近似搜索策略的计算效率较高,使得基于主轴树近似搜索的匹配效率最高。

In order to improve the storage and computation efficiency of ICP matching algorithm, k Nearest Neighbor searching algorithms（KNN） based on several tree structures were summarized in the paper. Then the influences of the KNN methods on matching accuracy were compared and analyzed with simulated and measured data. Experimental results demonstrated that the pull-in-range aspects of the methods are the same and the matching accuracies have little difference, while the main difference exists in the search efficiency. Among these methods, the Principal Axis Tree KNN searching method has superior storage structure, and the Approximate Search Strategy has higher computational efficiency, which makes the optimal matching efficiency of Approximate Principal Axis Tree.