基于八叉树空间分割的k近邻搜索算法  

Algorithm for finding k-nearest neighbors based on octree segmentation in space

作　　者：黄淼[1] 张海朝[2] 李超[3] 

机构地区：[1]平顶山学院软件学院,河南平顶山467000 [2]河南科技大学电子信息工程学院,河南洛阳471003 [3]西华师范大学计算机学院,四川南充637002

出　　处：《计算机应用》2008年第8期2046-2048,2051,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60475021);河南省杰出青年基金资助项目(0412000400);洛阳市科技攻关计划项目(0701041A)

摘　　要：以三维扫描得到的散乱点云为基础,提出了一种基于空间八叉树的快速k近邻搜索算法,通过对点集建立包围盒,利用八叉树记录分割过程,从而使近邻点的搜索只局限于采样点所在的包围盒及其周围的包围盒,并通过剪枝策略使搜索范围进一步缩小。大量真实数据的实验结果表明:该算法可以很好地提高近邻点的搜索速度。An octree based on the rapid k nearest search was presented for scattered points from 3D scanner. Through the establishment of bounding box on point sets, octree was used to record segmentation process, so that the search of point neighbors was limited to the bounding box of sample points and its neighbor, and through pruning strategies to further narrow the scope of the search. The experiments on a great deal of real data show that the search speed can be well improved.

关 键 词：K近邻 八叉树 包围盒 曲面重建 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]