基于栅格排序的散乱数据近邻快速搜索算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于栅格排序的散乱数据近邻快速搜索算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要： 文章提出了一种基于栅格排序的散乱数据近邻快速搜索算法。首先将散乱数据集进行空间栅格划分，然后求得当前被测点到周围栅格的距离并进行排序。按照栅格到被测点的距离，从小到大依次进行搜索，直到符合条件为止。实验结果表明，本算法可以大大缩小搜索范围，提高搜索速度。

Abstract: An algorithm for searching K-Nearest Neighbors of scattered points based sorted grids is presented. At first, the scattered points are divided into a set of uniform grids, and then sorted the distances between the current point and the grids around it. Searching the grids accord to the distances from small to large until meeting the requirements. Experiments show that the algorithm makes the searching range to be much smaller and the searching speed to be much faster.

关键词： 近邻；空间划分；散乱点

Key words: K-nearest neighbors；space division；scattered points

中图分类号：TH12文献标识码：A 文章编号：1006-4311（2011）16-0010-03

基金项目：本文受国家863高技术计划项目（2007AA04Z184）资助。

作者简介：李彬（1983-），男，河北安平人，硕士研究生，研究方向为数字化设计制造。

0 引言

随着科技的发展，逆向工程技术已经成为制造业信息传递的重要而简洁途径之一，它为快速设计和制造提供了很好的技术支持。所谓逆向工程，是指用一定的测量手段对实物或模型进行测量，根据测量数据通过三维几何建模方法重构实物CAD模型的过程。其中，数据处理是逆向工程的一个重要的技术环节，它决定了后续CAD模型重建过程能否方便、准确地进行。数据处理主要包括数据精简、数据分块、数据平滑、特征提取等。这些环节目前主要的方法都需要对数据点的几何信息（主要是法矢量和曲率）进行局部估计，这就需要确定每个数据点的k近邻，然后在k近邻中进行数据拟合，估算各种几何信息。

假设某一点集共n个点，通常求点P的k近邻点的方法是分别求出此点与其它n-1个点的欧氏距离，然后对它们从小到大排序，其中距离最小的k个点为点P的近邻点。这种方法很便利也很直观，但现实中的数据点集往往非常庞大，假若每一次都遍历n-1个点，那必然非常费时。为了提高搜索速度，国内外许多学者对这一问题进行了研究。综合而言这些方法可分为两类：（1）利用点集Voronoi图来进行k近邻搜索[1-2]；（2）利用空间分块策略进行k近邻搜索[3-4]。但是点集Voronoi图的计算量仍然非常大，而文献[3]不能保证所划分的包围盒尺寸达到或接近最佳搜索速度。文献[4]综合考虑了数据集的范围、点的总数及最近点数目k来划分栅格大小，并且在搜索终止准则上进行改进。此算法虽然优化了空间分块准则，改进了搜索范围，但还需要搜索较多栅格。

本文提出了一种基于栅格排序的快速搜索算法，将三维散乱点集进行空间栅格划分，求得被测点P到周围栅格的距离，按照栅格到P的距离从小到大进行搜索，能有效减少搜索栅格的数量，提高算法效率。

1 基于栅格排序的快速搜索算法

1.2 算法思想 本算法首先利用空间分块法把数据空间划分为许多大小相同的立方体，然后把每个点都归在相应的立方体中。计算被测点P到所在立方体六个面及周围立方体的距离，并进行排序。检查与以P为球心，栅格到P距离为半径的空间球产生干涉的立方体，并计算立方体内包含点是否为k近邻点，如果找到k个近邻点，那么搜索结束；否则，半径以求得的到立方体的距离为半径增大，直到满足条件为止。

具体算法如下：

文献[4]经过大量实验得出了β接近最佳搜索速度的边长调节系数，本文取β=1.1。

随着n的增大，n级栅格数会急速增多，通常的空间分块法是n级栅格搜索不满足条件，即搜索n+1级全部栅格，造成了数据急剧扩大。本算法首先只需求得被测点P到n级周围栅格的最小距离，并按距离排序依次搜索栅格，一旦满足要求找到k个近邻点即停止搜索，避免了搜索许多无用栅格。

要求被测点P到周围栅格的距离（如图2），我们可以对栅格进行分类以简化计算。从相对被测点P所在栅格的位置可以把周围栅格分为3类（如图3）：①相对于点P所在栅格沿一条坐标轴平移得到；②相对于点P所在栅格沿两条坐标轴平移得到；③相对于点P所在栅格沿三条坐标轴平移得到。

图5为二维搜索示意图，当取list[0]时，只搜索0号栅格；若不符合，则取list[1]，这时增加搜索2号栅格；取list[2]时增加搜索5号栅格，取list[3]时增加搜索3号栅格，依次进行。每次搜索都只增加一个最符合条件栅格，从而避免了大量无用栅格的搜索。

2 实验结果

为了验证本算法的有效性，作者进行了下面三组试验。实验数据为实物或模型的三维点云数据，图6为头像点云数据，图7为茶壶点云数据，图8为人体模型点运数据。

通过实验对比可以看到，本文经过改进的算法比文献[4]算法明显提高了搜索速度，缩短了搜索时间。文献[4]算法根据最小包围盒体积、点的数量和邻近点数目来k确定小立方体栅格的边长确实提高了传统空间分块算法的效率，但由于每次需要增加一圈栅格来重新计算，当搜索级数增大后会导致过多的不符合条件栅格进入选择范围，从而使计算量变得非常大，致使搜索时间不断增大。

3 结论

本文提出了一种基于空间分块的改进算法，通过记录栅格到被测点的距离对栅格进行排序。每次搜索只增加一个最符合要求的栅格，然后对其所包含数据点进行计算，避免了大量无用栅格点的计算。实验数据表明此算法能够大大提高在海量数据中的搜索效率。

参考文献：

[1]Goodsell G.On finding p-th nearest neighbors of scattered points in two dimensions for small p[J].Computer Aided Geometric Design，2000，17（4）：387~392.

[2]Dickerson M T，Drysdale R LS，Sack J R.Simple algorithms for enumerating interpoint distances and finding k nearest neighbors[J].International Journal of Computational Geometry and Applications，1992，2（3）：221-239.

[3]周儒荣，张丽艳，苏旭等.海量散乱点的曲面重建算法研究[J].软件学报，2001，12（2）：249-255.

[4]熊邦书，何明一，俞华.三维散乱数据的个最近邻域快速搜索算法[J].计算机辅助设计与图形学学报，2004，16（7）：909-917.

[5]马长胜，姜晓峰，强鹤群.一种改进的散乱数据点的近邻快速搜索算法[J].苏州大学学报（工科版），2007，27（2）：47-50.