两种空间分块策略K近邻搜索算法的比较研究

摘要：

空间分块策略是K近邻搜索算法研究中的有效方法,然而现有算法进行空间划分时给出的子立方体大小主要取决于K值的大小,K值变化时需重新进行空间划分,影响了时间效率和稳定性.利用空间分块策略的优点,提出一种以建立离散数据空间索引为空间划分目标的K近邻搜索新算法.该算法预先对空间包围盒进行微分块,形成的子立方体结构仅与离散数据和预设参数相关,同一点云数据只需进行一次空间分配.搜索过程中,以计算点为球心建立空间动态球,判定符合条件的子立方体,进行K近邻搜索.测试结果表明,新算法较现有算法点云分配和遍历时间效率、随机点搜索时间稳定性及对不同K值的适应性等方面更具有优势.

关键词：空间分块、K近邻、动态球、算法比较

所属期刊栏目：16

分类号：TP391.4(计算技术、计算机技术)

资助基金：云南省应用基础研究面上项目2009CD102

在线出版日期：2012-01-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1676-1680