基于KD树的LiDAR点云索引方法及其在公路勘测中的应用

王世杰，艾明耀，马 捷，严 俊

（1.河南省交通规划勘察设计院有限责任公司，河南 郑州 450052；2.武汉大学 遥感信息工程学院，湖北 武汉 430079）

基于KD树的LiDAR点云索引方法及其在公路勘测中的应用

王世杰1，艾明耀2，马 捷1，严 俊2

（1.河南省交通规划勘察设计院有限责任公司，河南 郑州 450052；2.武汉大学 遥感信息工程学院，湖北 武汉 430079）

针对基于LiDAR点云公路勘测设计中高密度、海量、散乱点云的索引与管理难点，提出一种基于KD树的LiDAR点云索引方法，对机载LiDAR点云进行高效管理，在此基础上快速生成纵横断面，实现基于LiDAR点云的公路勘测应用。实验结果表明，该方法能够支持高密度大数据量点云的一体化索引管理，能够很好地支持基于LiDAR的公路勘测设计。

机载LiDAR；点云；KD树；索引；公路勘测

随着以3S技术为基础，以现代高分辨率卫星对地观测，全球重力场模型及空间信息分析技术为核心的对地观测技术的发展，全球定位系统、航测遥感、高分辨率卫星在公路规划、勘察与设计和信息化管理中得到广泛应用。由于实际公路勘测对高程和效率的高要求，GPS-RTK、高分辨率遥感技术和常规航测及低空航测精度难以满足公路测量的要求和建立公路数据库的任务[1]。国外，三维激光扫描系统已经用于公路的勘测设计以及维护。国内也引进了LiDAR设备与技术，用于公路勘测选线、线路设计，但多采用成熟的LiDAR数据处理软件得到DEM、DOM和DLG等产品，将这些数据产品导入设计软件进行公路的勘测和选线设计等[2-4]。因此，研究利用高密度LiDAR点云的公路勘测设计方法，对于提高公路勘测设计精准度和效率、公路工程和信息化运营管理有着极其重要的现实意义。

基于LiDAR点云的公路勘测设计需要解决将高密度、海量、散乱点云导入公路勘测设计平台（AutoCAD、纬地CAD、EiCAD等）进行三维可视化显示，方便勘测设计人员直接操作点云数据，快速提取所需要的纵、横断面及对周边三维地形的观察。本文提出了一种基于KD树的LiDAR点云索引方法，对机载LiDAR点云进行高效管理，在此基础上快速生成纵横断面，实现基于LiDAR点云的公路勘测应用。实验表明，本文提出的方法能够支持高密度大数据量点云的一体化索引管理，能够很好地支持基于LiDAR的公路勘测设计。

1 机载LiDAR原理及数据特点

机载LiDAR集成激光测距仪、动态差分GPS接收机（DGPS）、惯性导航系统（INS）、成像设备和同步控制装置等[5,6]，通过激光测距与DGPS、IMU获取的位置和姿态数据联合解算，能够直接快速地获取地物表面的三维空间坐标，生成数字高程模型，如图1所示。

图1 LiDAR原理示意图

机载LiDAR作为直接的主动测量方式，能够获取高密度、海量的三维点云。目前大部分的商业机载LiDAR系统都能达到每m2几个数据点的密度。例如，Fli-Map1系统可达9点/m2[6]，如果采用Fli-MAP1系统进行公路勘测测量，每km2可以达到900万个点，其以标准格式存储可以达到200 M。在实际工程中机载激光雷达的飞行区域可以达到几百甚至上千km2，如此海量的数据给数据的存储、处理带来了巨大挑战，也直接影响到LiDAR在公路勘测、数字城市、水利电力勘测等领域中的应用。

2 基于KD树的LiDAR点云索引方法

对于海量、离散的机载LiDAR点云数据而言，选择合适的空间索引方法以便有效地实现数据的存储、查询和组织管理是非常重要的。合适的索引方法对执行点云存贮、查询、操作，实现点云数据的快速搜索、建模和重复应用、计算以及入库存档有很大的帮助和便利。在目前的研究和应用中，对LiDAR点云数据进行空间索引建立的方法主要有规则格网、四叉树、八叉树等[7,8]。

KD树[9,10]是k（k≥2）维的二叉索引树，主要用于检索多属性的数据或多维点数据。它要么是一棵空树，要么是一棵具有下列性质的二叉树：

1）若它的左子树不空，则左子树上所有结点的第d维的值均小于它的根结点的第d维的值，其中d为根结点的分辨器值；

2）若它的右子树不空，则右子树上所有结点的第d维的值均大于或等于它的根结点的第d维的值；

3）它的左右子树也分别为KD树。

与二叉索引树不同的是，KD树的每个结点表示k维空间的一个点，而且树的每一层都根据这层的分辨器作出分枝决策。在本文中，KD树的第i层的分辨器定义为：i mod k（树的根结点所在的层为第0层，根结点孩子所在的层为第1层，依次递增）[10,11]，取分辨器所在数据维的中值作为分割点。根据这一原则，三维点集构建KD树时，首先第0层的分辨器为X，根据所有X值的中值来决定根结点，左右子树依据根结点X值进行分割，所有X值小于根结点X值的点都分配于左子树中，大于根结点X值的点分配于右子树中；根结点的孩子结点则以Y值进行类似的分割，得到第二层；根结点的孙结点则以Z值进行类似的分割，是为第三层；根结点的曾孙结点则以X值进行分割；一直进行类似的分割直至叶结点，从而完成三维点集的KD树。

图2 KD树构建示意图（K=2）[10]

图2是一个二维KD树的实例，结点的二维坐标为A（7, 2），B（5, 4），C（9, 6），D（2, 3），E（4, 7），F（8, 1）。根结点A点分辨器的值为0（X轴），其的左子树的所有数据点B、D、E的X维的值都比A的X的值7小，右子树的所有数据点C、F的X的值都大于7。结点B的分辨器的值为l（Y轴），则其左子树的数据点D的Y维的值比B的Y维值4小，右子树的数据点E的Y维值大于4。

为了测试索引的性能，分别取100万、200万、300万点云数据对KD树索引效率进行实验，本文实验中采用的计算机硬件环境为CPU Intel E5300 2.60 GHz、内存2 GB，系统环境为Windows XP SP3 32位操作系统。

从图3可以看出，最邻近查询所耗费时间与所查询的点个数成正相关的关系，所查询的点越多，所耗费的时间越多。同时，建立索引的点云数目越大，最邻近查询所耗费的时间也越多。

图3 最邻近查询的时间消耗

3 基于KD树索引的高密度LiDAR点云公路断面设计

3.1 纵断面设计

假定公路主线已经给定，基于LiDAR点云数据获取该公路纵断面的算法为：

1）从公路主线起点开始，每隔1 m获取公路主线上的点Vi（X，Y）。

2）基于LiDAR点云数据，利用KD树索引，查找以Vi（X，Y）点为圆心，以5 m为半径的圆内的点，取其距离加权高程值作为Vi点的高程H，得到纵断面数据的第i个点Vi（X，Y，Z）。

3）重复前两步，直至达到公路主线的终点。

4）将点V1，V2，…，Vi，…，Vn（假设最终在公路主线上取到n个点）依次连接，即可得到该公路的纵断面数据。

图4为按照以上步骤所获取的公路纵断面。其中，左侧窗口影像中的红色线条即为目标公路主线，右侧窗口中是该公路的纵断面，横坐标为沿公路主线与公路起点之间的距离，纵坐标为在公路上取到的点的高程值。

图4 纵断面

3.2 横断面设计

在KD树索引下，基于LiDAR点云数据获取公路主线横断面算法步骤如下：

1）沿公路主线，从公路起点开始，每隔L m（本文设为5 m）取公路上的点，最终得到点W1，W2，…，Wi，…，Wn。

2）过点Wi作垂直于该点所在公路直线段的垂线段V，设定垂线段长度为S m（本文设为20 m），且点Wi为垂线段的中点。从线段V一端开始，每隔S m（本文设为1 m）取点，得到点P1，P2，…，Pn。基于LiDAR点云数据以及KD树索引，获取以Pi点为圆心，R为半径的圆内所有的点，求其高程的距离加权平均值作为Pi的高程。重复这一计算过程，最终获取该垂线段V上所有点P1,P2,…,Pn的高程值H1，H2，…，Hn，以及横断面数据的坐标（v1，H1），（v2，H2），…， （vn，Hn），其中v1是P2到垂线段起点的距离，Hi为该点的高程值。将点P1，P2，…，Pn依次连接，即可得到点Wi处公路的横断面。

3）重复前一步，直到生成所有点W1，W2，…，Wi，…，Wn的横断面数据，并将各个点的横断面数据依次由下而上进行排列，可得到该公路的横断面数据。

图5为按照以上步骤所获取的公路横断面。其中，左侧窗口影像中的红色线条标示的即为目标公路主线，右侧窗口中是该公路的横断面，横坐标代表与公路正交的垂线段，纵坐标代表在公路上取到的用来生成横断面的正交点离开公路起点的距离。

图5 横断面

4 结 语

本文给出了基于KD树索引的高密度LiDAR点云公路勘测方法，利用LiDAR点云建立KD树索引，快速查询并计算得到公路设计中需要的纵横断面。利用LiDAR点云直接构建公路勘测设计中的纵横断面，省去了生成DOM和DEM的步骤，避免了因数据处理产生的精度损失，提高了公路勘测设计的效率。

[1] 富志鹏.基于LiDAR的高速公路测设技术应用研究[D].西安:长安大学, 2011

[2] 兰增荣,胡友健,隆华平,等. LiDAR技术在公路勘测中的应用[J].工程地球物理学报,2009,6(1): 99-104

[3] 李海亮,陈楚江,余绍淮,等.基于密集激光雷达数据的公路设计地表信息生成方法[J].中外公路,2011,31(4):330-332

[4] 王玲玲.机载激光雷达技术在山区高速公路勘测设计中的应用[J].公路交通科技:应用技术版,2010(7):115-117

[5] 李清泉,李必军,陈静.激光雷达测量技术及其应用研究[J].武汉测绘科技大学学报,2000,25(5):387-392

[6] 张小红.机载激光雷达测量技术理论与方法[M].武汉:武汉大学出版社,2007

[7] 路明月,何永健.三维海量点云数据的组织与索引方法[J].地球信息科学,2008,10(2):190-194

[8] Bertino E,Ooi B C.The Indispensability of Dispensable Indexes[J].IEEE Transactions on Knowledge and Data Engineering,1999,1(11):17-26

[9] Friedman J H, Louis B J, Ari F R.An Algorithm for Finding Best Matches in Logarithmic Expected Time[J].ACM Transactions on Mathematical Software,1977,3(3):209-226

[10] Wikipedia.Quadtree[EB/OL].http://en.wikipedia.org/wiki/ K-d_tree,2012-05-01

[11] Bentley J L.Multidimensional Binary Search Trees used for Associative Searching[J].Communications of the ACM,1975,18(9):509-517

P237.3

B

1672-4623（2015）01-0140-03

10.3969/j.issn.1672-4623.2015.01.046

王世杰，正高职高级工程师，主要研究方向为公路勘测与设计。

2014-01-15。