基于KD树的点云数据自适应屏幕精度高效显示方法

杨建思，刘 华，林 鹏

(武汉大学城市设计学院，湖北武汉 430072)

基于KD树的点云数据自适应屏幕精度高效显示方法

杨建思，刘 华，林 鹏

(武汉大学城市设计学院，湖北武汉 430072)

海量激光点云数据的快速显示是目前一个技术瓶颈。本文提出一种基于KD树的点云数据自适应屏幕精度的高效显示方法，采用类似LOD的技术将点云进行KD树的组织，并在KD树节点上引入屏幕精度的概念，在点云数据显示时，计算KD树节点在屏幕上的投影范围，进而决定其是否显示点云细节。试验证明，该算法在显示大规模点云数据时，由于通过KD树自适应屏幕精度调度点云数据使绘制点的数据量大大减少，从而大大加快了点云的显示速度。

点云组织；索引；KD树；可视化

一、引 言

机载激光雷达(light detection and ranging，Li-DAR)是激光扫描与探测系统的简称，它集激光、全球定位系统(GPS)和惯性导航系统(INS)3种技术于一体[1]，是一种通过位置、距离、角度等观测数据直接获取地球表面点三维坐标，从而实现地物信息提取和三维场景重建的对地观测技术[2]。

为了获取被观测物的详细信息，LiDAR数据的密度往往很大，使得LiDAR数据量很大，其数量通常达到GB级，在显示系统中将数据点显示出来的图像往往非常密集，因而形象称其为点云(pointcloud)。

目前有大量关于点云数据组织与数据结构的论文[3-10]，但大多数论文是关于点云数据结构与索引的空间利用率、平均检索速度、内外存调度算法及平衡性等问题的，在点云数据的可视化方面，一般是使用视口裁切去除视口外点[11-13]。已有的关于大数据量简化显示的办法一般是基于三角面片的LOD，而对离散的LiDAR数据点云来说，传统的LOD方法及遮挡面消除方法都不太适用。

本文提出一种基于KD树的点云数据自适应屏幕精度的高效显示方法。该方法类似于LOD方法[14-16]，将点云进行KD树的组织，在KD树节点上引入屏幕精度的概念；在点云数据显示时，计算KD树节点在屏幕上的投影范围，进而决定其是否显示点云细节。由于通过KD树自适应屏幕精度调度点云数据可使绘制点的数据量大大减少，从而大大加快了点云的显示速度。

二、KD树

在数据组织结构中，二叉树是非常简单、高效且成熟的结构，但它仅仅适用于单维数据。LiDAR数据是三维数据，不存在某种排序能同时兼顾3个方向的维度属性，从而不能保证原来邻近的数据在排序以后也有邻近的特征。

基于二叉树向多维空间中的扩展，Bentley提出多维空间中的二叉树索引，即KD树[17]。KD树将多维空间中的数据成功地在一个树内完成索引，但数据对插入顺序非常敏感，树的结构往往缺乏平衡性。自适应的KD树[18]提出在建立KD树时根据数据特征选取特定的划分平面，使每次划分都将空间分为数据相等的两个子空间，但这种优化只对静态数据有用，对于数据的动态更新，树的结构需要全部重新组织。

自适应的KD树像KD树一样，依次选取与坐标轴垂直的平面将数据空间一分为二，其坐标轴依次在3个坐标轴之间选取；自适应的KD树在向KD树插入数据之前，预先计算数据点在各个方向的排序，进而选取特定的点，使得平面划分的结果让每个节点的左右子节点包含的点数目最多相差1。

为了使该数据结构能更好地适应点云数据的显示，本文对自适应的KD树作出以下改动。

1)原始的KD树算法对划分平面的选取为依次选取3个方向的划分平面，这样保证了数据的公平性，但是也造成了数据区域形状各异，很不规则。因而笔者将划分平面定义为使划分的结果区域最接近正方形的划分方式，即对需要进行划分的区域分别计算区域在3个轴向的长度Length_X、Length_Y、Length_Z，求出其中的最大值，本次划分将数据区域沿该轴方向一分为二，这样能保持每个节点内的数据在空间位置上更加相近。

2)在传统KD树中，每个节点进行细分一直到每个节点只包含一个数据点。对于海量点云数据来说，不需要将数据一直划分到每个节点最多只有一个数据点才终止，KD树的每个叶子节点可以有许多数据点，具体的点数或范围可依应用而定。

对KD树节点是否再分的标准有两种基本的判别方法(如图1所示)：基于点的数目，即如果某个节点内数据点的个数小于等于N，则节点不需要再分；基于空间范围，即如果节点数据的“尺寸”小于给定尺度R，则节点不需要再分。

图1

基于点数的划分标准在最近点的查找时优势明显，基于空间范围的划分标准在优化显示时操作比较简单。考虑到基于空间范围的划分标准在数据空间分析时会有很大优势，笔者采用的划分策略为：确定一个相对较大的空间尺度，以这个大小为空间划分的主要标准；预先确定每个节点最多能容纳的点的个数nmax，经过空间标准划分以后，如果某个区域内点个数大于nmax，继续细分至点的个数小于nmax。

本文提出的自适应屏幕精度的点云数据显示算法不论是否采用内外存调度策略，都能有效加快显示速度。另一方面，自适应的KD树在建立KD树时，通过预先的计算使树保持良好的静态平衡性，从而使树的深度减小，减少了平均查找时间，加快了处理速度。为了体现屏幕精度对显示效率的提高，本文不采用内外存调度算法，而选用比较高效的自适应的KD树，以期更好地表现显示屏幕精度算法的优越性。

三、自适应屏幕精度显示算法

1.自适应屏幕精度的概念

LOD最早是由Clark于1976年提出的[11]，其思想是当模型在屏幕中占据较小区域时，可以使用较粗略的模型来代替原始模型进行绘制，以便对复杂场景进行快速绘制。其核心是不绘制那些对视点来说“微不足道”的模型或模型细节，这些模型或是因为距离很远，只需将复杂的物体用简单的体素来渲染，或是因为太微小而根本不进行渲染。

对点云数据而言，对象是一个个数据点，不存在大小之分；每个点不论视点位置如何，投影到屏幕以后都是一个像素大小，没有优先之别，因而很难利用LOD算法。针对这个问题，笔者以自适应的KD树为结构提出了树模型中节点自适应屏幕显示精度的算法。

首先，针对点数据是一个个没有大小没有体积的个体，抛弃在点的显示中一直把一个个点当作独立个体来看待的想法，将数据集合看作整体，即在数据组织时利用KD树组织场景中的数据，在考虑场景中的LOD模型时把KD树中的节点作为一个整体看待，考虑其投影到屏幕以后，如果节点内所有点都在同一个像素区域内，则可以将整个节点当作单点看待；如果投影到屏幕以后节点最大距离不超过半个像素，可以直接对该节点进行显示。

因而，该思路将每个节点可以看成是一个模型，这个模型有3个细节层次：全细节模型、单点模型及零点模型。全细节模型即整个节点相对观测点来说很大，需要将所有数据点显示；单点模型是数据区域投影接近一个像素大小，可以将节点简化为一个数据点；零点显示即投影范围很小以至于不需要进行处理。同时，注意到在树状结构中有父子节点的结构，因此对于全细节模型，实际上不需要显示所有数据点，只需要分别对其子节点进行模型检验即可。这种树形结构的递归正是该模型只需区分3个细节层次的原因。

图2显示了一颗简单的KD树，其中的数字用于标明节点半径大小，假设该树离观察者距离较远，通过计算发现所有半径大于等于8的节点在屏幕上占据一个像素的范围，则对于该树的显示，只会显示其中的4个节点，对其他半径小于8的节点，即使显示，也只会被遮盖，其显示是没有意义的。

2.自适应屏幕精度的显示算法

如上节所述，自适应屏幕精度的显示需要对每个节点的“大小”作一个定量的描述，以计算节点相对于观察者来说占据了屏幕上多少像素的位置。对“大小”的计算，有基于节点的包围盒和包围球两种屏幕精度算法。

图2 采用节点半径划分KD树的层次

(1)包围盒投影法

节点的“大小”通过计算节点包围盒到屏幕的投影范围得到，即计算包围盒的8个顶点投影到屏幕以后的屏幕坐标，根据这8个点的屏幕坐标确定节点是否需要细分。如果这8个二维坐标中某两点的水平或竖直坐标差大于1.5个像素，则节点被定义为全细节；如果坐标差大于0.5个像素，即定义节点为单点模型；否则为零点模型。

图3是推导任意点在特定视点下投影坐标的示意图。图中点O是观察点，过点O沿视线方向是Z轴，向上的方向为Y轴，将Z轴与Y轴的外积作为X轴。点P是模型中的任意一点，设P在YZ、XZ的平面投影分别为E、A，A在Z轴和X轴上的投影为D、B，则AB(或DO)、PA、PE(或AD)分别为P到XY、XZ、YZ平面的距离。A′、P′、E′和D′分别是A、P、E、D投影到屏幕上的点，B′为A′在X轴的投影，C′为E′在Y轴的投影。

式中，AB、PA、PE分别为P到XY、XZ、YZ平面的距离；OD′为视点到屏幕的距离，在OpenGL中可根据gluPerspective函数参数求得。

(2)包围球估算法

以上方法计算量比较大。实际上构建KD树时在预处理阶段把节点半径作为参数存储，则显示时可以通过节点半径在屏幕上的大小作近似估计。

如图4所示，通过KD树中的节点半径信息，可以认为节点内所有点都在图中黑圆中。如果能用圆的直径d代表节点尺度，则可以简化计算。事实上对于需要判别大小的节点而言，其距离一般离视点较远，用d来代替黑圆的误差不大。通过计算可知，当fovy为60°时，最大误差仅7.7%；当fovy为90°时，最大误差也只有17%，这种误差对节点大小的估计是允许的。

图4 根据节点半径估算屏幕精度

设图中d(两倍节点半径)投影到屏幕以后的长度为d′，容易看出

式中，AO为点到标准面的距离；BO即包围盒投影法中的OD′，即

对屏幕精度的判别：若d′＜1或d′＜1.5，该节点被定义为“很小”，不需要显示其子节点。

3.基于KD树遮挡数据的裁切方法

按照以上方式可以减少很多点的显示，加快显示速度。引入KD树以后，还可以采用点(节点)的遮挡来加速绘制过程。

考虑到KD树划分时是在3个维度上划分的，投影到二维平面时，在与二维平面垂直的深度上会有很多节点重叠投影到同一个像素上，树越深，这种重叠引起的重绘越多。为了进一步提高显示效率，可以考虑在遍历树结构时按照由前到后的顺序遍历，并对每个像素进行遮挡判断，即如果屏幕上的像素已经被正确绘制，则屏蔽掉该像素块后面所有节点的显示。对于屏幕像素而言，一种简单的处理方式是引入一个BOOL型的屏幕缓冲区来存储屏幕上的点是否已经被绘制。

引入屏幕缓冲区以后，对每个节点的层次判断可以再增加一个标准：如果该节点下所有点被某些已显示的屏幕像素区域遮挡，则直接返回。在数据量很大而且屏幕像素比较多时，已绘制的屏幕像素比较密，这时遮挡会直接剔除很多远处数据点的计算。

四、试 验

本试验使用的是 Intel Pentium Dual E2140 CPU、1 GB内存、NVIDIA GeForce 8600 GT显卡的机器，采取的数据源为一个城市的部分模型，该文件有300多万个数据点。笔者先采用原始的KD树对数据进行组织，并进行常规的遍历显示，显示的平均时间为76 ms；再采用包围球估算法计算屏幕精度，分别采用1.2个像素和2个像素的精确度进行显示，结果发现显示效果从视觉上几乎都没有区别，而显示效率大大提高。点云显示效果如图5所示。

图5 屏幕精度算法中的点云显示结果

将3个显示方案在不同距离视点的显示时间绘制在图6中。从图中可以看出，原始的绘图方式显示时间不变，总是76 ms；两种KD树自适应屏幕精度的绘图方式显示时间随着视点与模型距离的增大而减小，而且采用2个像素的屏幕精度的绘制时间要比1.2像素的显示时间少很多。由此可以证明，该算法能有效减少点云显示中点的绘制个数，而且在屏幕精确度要求降低的情况下，其显示速度的加速非常明显。

图6 3个方案的显示时间对比

注意到图6中两种屏幕精度显示曲线的变化趋势相当一致，因此制作了图7所示的表，图中显示的是1.2个像素的精度与2个像素的精度在点的个数与显示时间上的一致性。即尽管这两个模型在同样的场景下显示时间差别很大，但它们都遵循着显示时间与显示点的个数成正比的规律，即对于任何显示任务，显示时间与显示点的个数成正比。该结论也说明了笔者在数据处理过程中采取策略的正确性，即没有对过多不需要显示的点进行额外计算。

图7 1.2个像素的精度与2个像素的精度在个数与时间上的对比

通过对上面的两组数据进行分析，可以得出两个结论：一是本文提出的基于KD树的点云数据自适应屏幕精度显示方法大大加快了显示速度；二是由于这种算法的显示时间与显示点的数目成正比，在最坏的情况下对1440像素×900像素分辨率的满屏幕场景显示，也仅需要显示130万个数据点，按照笔者的推算显示时间最多只需要50 ms，也就是说对于任何大小的点云场景，通过该方式进行精度控制，都可以实现每秒20帧的绘制效率。

五、结束语

本文所提出的算法通过对KD树的改造，引入LOD算法，提出自适应屏幕精度的显示与裁切，大大减少了点云数据绘制中点的绘制数目，从而有效加快了点云显示速度。该算法重在将树结构和传统的LOD技术结合，提出的设计思路对所有层次模型都能有非常明显的加速效果。

目前该算法亟待改进的方面有：在建立KD树的时候，节点特征的选取应该根据模型本身特征选取特征点，以使其更适应应用的需求；对于建立 KD树索引的标准，由于实际任务的不同，应用所关心的属性也不同，需要针对点的颜色、方向等难量化的属性建立便于量化的索引机制，以使得本算法可以实现多属性的查询功能。

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

[2] 梁欣廉，张继贤，李海涛，等.激光雷达数据特点[J].遥感信息，2005(3)：71-75.

[3] HENRICH A，SIX H W，WIDMAYER P.The LSD Tree： Spatial Access to Multidimensional Point and Non-point Objects[C]∥Proceeding of the 15th International Conference on Very Large Databases，1989：45-53.

[4] CLARK J H.Hierarchical Geometric Models for Visible Surface Algorithms[J].Communication of the ACM，1976(19)：547-554.

[5] BENTLEY J L.Multidimensional Binary Search Trees in Database Applications[J].IEEE Transactions on Software Engineering，2006(4)：333-340.

[6] GONG J，KE S N，ZHU Q，et al.An Efficient Point Cloud Management Method Based on a 3D R-Tree[J]. Photogrammetric Engineering＆Remote Sensing，2012， 78(4)：373-381.

[7] KOTHURI R，GODFRIND A.Pro Oracle Spatial for Oracle Database 11g[M].[S.l.]：Springer，2008.

[8] SCHN B，BERTOLOTTOA M.Storage，Manipulation，and Visualization of LiDAR Data[C]∥Proceedings of 3D-ARCH.Trento：[s.n.]，2009：25-28.

[9] RAVADA S，HORHAMMER M，BARIS M K.Point Cloud：Storage，Loading，and Visualization[C]∥National Science Foundation TeraGrid Workshop on Cyber-GIS.Washington DC：[s.n.]，2010：2-3.

[10] VOSSELMAN G.Automated Planimetric Quality Control in High Accuracy Airborne Laser Scanning Surveys[J]. ISPRS Journal of Photogrammetry and Remote Sensing，2012(74)：90-100.

[11] GEOSYSTEMS L.Leica Cyclone，3D Point Cloud Processing Software[EB/OL].2011-07-26.http：∥hds.leica-geosystems.com/en/6515.htm.

[12] 黄先锋，陶闯.机载激光雷达点云数据的实时渲染[J].武汉大学学报：信息科学版，2005，30(11)：975-978.

[13] 支晓栋，林宗坚.基于改进四叉树的LiDAR点云数据组织研究[J].计算机工程与应用，2010，46(9)：71-74.

[20] 龚俊，柯胜男，朱庆，等.一种八叉树和三维R树集成的激光点云数据管理方法[J].测绘学报，2012，41 (4)：597-604.

[14] 王晏民，郭明.大规模点云数据的二维与三维混合索引方法[J].测绘学报，2012，41(4)：605-612.

[15] 徐文学，杨必胜，魏征，等.多标记点过程的LiDAR点云数据建筑物和树冠提取[J].测绘学报，2013，42 (1)：51-58.

[16] 郑顺义，周朗明.旋转平台点云数据的配准方法[J].测绘学报，2013，42(1)：73-79.

[17] ROBINSON J T.The K-D-B-tree：A Search Structure for Large Multidimensional Dynamic Indexes[C]∥ Proceeding of ACM SIGMOD International Conference on Management of Data，1981：10-18.

A High Efficient Display Method Based on KD Tree Index for Point-cloud Data

YANG Jiansi，LIU Hua，LIN Peng

TP391.9

B

0494-0911(2014)07-0018-05

2014-01-13

国家863计划(170325)；国家自然科学基金(61331016)

杨建思(1963—)，女，江西樟树人，博士，副教授，研究方向为计算机图形学、虚拟现实与数字城市。

杨建思，刘华，林鹏.基于KD树的点云数据自适应屏幕精度高效显示方法[J].测绘通报，2014(7)：18-22.

10.13474/j.cnki.11-2246.2014.0216