基于KD树的点云索引技术研究

王儒　胡萍　蒋俊豪

【摘 要】随着计算机技术的进步以及社会需求的不断增加，激光雷达技术作为一种三维空间信息的实时获取手段，正以日新月异的速度向前发展。激光雷达技术有效地拓宽了数据源范围，改变了数据获取模式，能够快速获取高分辨率数字表面模型。然而，点云数据的海量性一直是制约点云数据处理方法的重要因素，迫切需要寻找一种高效空间索引方法来管理海量点云数据。因此，研究点云数据的管理和处理方法，形成点云的数据处理理论显得十分重要。本文利用kd-tree来管理点云数据的索引，实验证明kd-tree能高效的管理海量点云数据。

【关键词】点云；kd-tree；索引；激光雷达

0 引言

地球空间信息的快速获取和智能化处理是当前测绘领域的研究热点，也是“数字地球”、“数字城市”急待解决的问题。21世纪测绘技术必将实现高精度化、高速化、高效率化和标准化，空间数据处理必将实现智能化[1]。激光雷达技术是近几十年摄影测量与遥感领域最具有革命性的成就之一，是继全球定位系统（GPS）发明以来在遥感测绘领域的又一座里程碑，同时，激光雷达也可自成体系，组成地面三维激光扫描仪[2]。激光雷达系统扫描获得数以万计的激光点，被形象地称之为点云[3]。对于点云数据来讲，高效的索引结构还是其他数据处理的基础，例如点云滤波、点云精简都依存于某种索引结构。

本文针对激光雷达系统所获取的点云数据在管理与检索，提出了基于kd-tree的点云管理方案。并利用三维激光点云数据进行实验，结果表明基于kd-tree的点云管理能高效的管理海量点云数据。

1 KD 树基本原理

采用KD 树结构分割散乱点云，能明显加快搜索速度，为k 领域的建立打下坚实基础。KD 树是K-dimension tree 的缩写，是对数据点在k 维空间（如二维（ x，y），三维（ x，y，z），k维（x，y，z，…））中划分的一种数据结构，主要应用于多维空间关键数据的搜索：主要有范围搜索和最近邻搜索。

2 基于KD树建立点云邻域

点云数据为散乱数据点，即对于每个数据点只包含点的三维坐标值，而没有明确给出其对应的几何拓扑信息，因此一般需要根据空间点的邻域关系估算点对应的拓扑关系[5]，从而估算点对应的几何信息（如数据点单位法向量、微切平面、曲率大小和邻接关系）。

通常，计算某点的k个最近邻域的方法是求出候选点与其余n-1个点的欧氏距离，并按从小到大的顺序排列，前面的k个点即为候选点的k最近邻域。这种方法很直观，然而对于海量的点云数据而言，采用这种方法相当耗时，效率十分低下。本文通过对点云数据建立kd-tree索引，进而利用kd-tree进行点云邻域搜索[6]，算法如下：

假设kd-tree的结点为i，每一个结点都对应一个区域（根结点对应整个点区域），那么结点i所对应的区域为Reg（i）；R表示所要查找的区域范围。范围查询的函数Search（i，R）的算法描述如下：

①首先i=root，即表示从根结点开始搜索；

②如果i是叶子结点，那么返回该叶子结点中处于R中的点；

③如果R包含Reg（i），那么返回v的所有子树结点；

④否则，如果Reg（lefi（i））和R相交，那么search（left （i），R）；如果Reg（right（i））和R相交，那么seareh（righr（i），尺）。

KD 树是把整个空间划分为特定的几个部分，然后在特定空间的部分内可以进行相关搜索操作。搜索的核心在于找到实例点的邻居，关于搜索主要有两种搜索模式[7]：范围搜索和最近邻搜索。

2.1 范围搜索

范围搜索就是利用与实例点的空间距离作为判定标准，来寻找满足条件的点作为邻近点，因为特征空间中两个实例点的距离和反应出两个实例点之间的相似性程度。K近邻模型的特征空间一般是n维实数向量空间，使用的距离一般使用欧式距离。三维激光扫描仪扫描得到的墙角点云比较复杂，利用kd-tree索引管理技术可以方便的搜索出任意点的邻近点，从而快速建立起点云的拓扑关系，在搜索中我们可以采取基于点数以及基于距离（即范围）来快速搜索邻近点。如图2（a）所示。

2.2 最近邻搜索

最邻近搜索就是给定查询点及正整数K，从数据集中找到距离查询点最近的K个数据点。与范围搜索不同，K值只要大于1就一定可以找出对应的邻近点，而范围搜索如果设置的距离阈值可能会使得点云中比较稀的点没有满足条件的邻近点。如图2（b）所示。

3 实例分析

现采用kd-tree建立散乱点云的索引技术，并快速建立散乱点云的拓扑关系。利用三维激光扫描仪可扫描得到的球标靶点云，通过对该点云建立kd-tree索引，可以快速获得该点云的拓扑关系。如图3所示为利用最邻近8点搜索得到的点云拓扑网结构，原始点云的点数为35743，利用kd-trees索引来建立其拓扑关系所用的时间是3.8s。利用此方法获得点云的拓扑关系相比利用贪婪三角化获得拓扑关系更加高效。

最邻近8点搜索

4 总结

激光雷达技术在快速、精确获取空间目标的几何数据方面已取得了突破性进展，与此同时也给海量雷达数据的处理效率带来了挑战。本文针对激光雷达系统所获取的点云数据在管理与检索，提出了基于kd-tree的点云管理方案。利用三维激光点云数据进行实验并利用编程实现，结果表明通过对散乱点云建立kd-tree索引可以快速建立建立点云拓扑关系，从而方便了对点云的后处理。

【参考文献】

[1]张毅.地面三维激光扫描点云数据处理方法研究[D].武汉：武汉大学，2008.

[2]减克.地面激光雷达应用处理关键技术研究[D].北京：首都师范大学，2007.

[3]刘经南，张小红.激光扫描测高技术的发展与现状[J].武汉大学学报·信息科学版，2003，28（2）：132-137.

[4]路明月，何永健.三维海量点云数据的组织与索引方法[J].地球信息科学， 2008，10（2）：190-194

[5]PIEGL L A. TILLER W. Algorithm for Finding All K Nearest Neighbors[J]. Computer-Aided Design，2002，34（2）：167-172.

[6]刘立强.散乱点云数据处理相关算法的研究[D].西北大学，2010.

[7]刘艳丰.基于 kd-tree 的点云数据空间管理理论与方法[D].长沙：中南大学， 2009.

[责任编辑：曹明明]