基于八叉树的点云数据的组织与可视化

张会霞

（太原师范学院 城市与旅游学院，山西 太原 030012）

基于八叉树的点云数据的组织与可视化

张会霞

（太原师范学院 城市与旅游学院，山西 太原 030012）

三维激光扫描获取了大量的点云数据，数据的组织直接影响点云数据的操作速度.采用数据库管理点云数据，对点云数据采用八叉树数据模型进行组织，建立空间索引，对点云数据进行分块提取，实现点云数据的检索以及可视化.

八叉树；点云数据；组织；可视化

三维激光扫描技术（3D Laser Scanning Technology）是一种先进的全自动高精度立体扫描技术.它是一项新兴的获取空间数据的技术，同传统的测量手段相比，三维激光扫描测量技术可以连续、自动、快速地采集大量的目标物表面数据，即点云数据，并且拥有许多独特的优势［1］.由于点云数据量大，把所有的点一次性的调入内存，系统运行缓慢，故需要进行合理的数据组织，建立索引.

三维激光扫描获取的数据为三维目标物点云数据，由于目标物多为不规则形状，对于体状目标物数据的管理，八叉树数据模型具有独到的优势，故采用八叉树数据模型进行组织.

1 八叉树模型的基本理论

三维激光扫描获取大量的点云数据，对点云数据采用八叉树模型进行组织，通过对点云数据层层分割，最后叶节点存储的数据量大大减少，可以加快检索速度.

八叉树是一种非常直观的数据结构，具有树的深度小，遍历速度快的特点［2］.八叉树分为规则八叉树和线性八叉树.规则八叉树是指直接通过八叉树结构来描述空间信息，即显性地描述节点及通过指针来表达父子关系.八叉树由中间节点组成，叶子节点保存在中间节点的子节点中.八叉树节点的数据结构要存储8个子节点的指针、父节点的指针，对于非叶子节点，还要存储下一个子节点的指针，以及该节点的属性数据，内存消耗大.

线性八叉树是为了克服规则八叉树编码的不足而形成的一种高效的编码方法.这种方法只存储叶节点，包括叶节点的位置、大小、属性值.叶节点的编码称为地址码，常用的地址码是Morton码，它隐含了叶节点的位置和大小信息.比如空间目标的大小为2n×2n×2n，分辨率为1，那么任意叶节点的Morton码是一个n位数的编码［3］，可以写成：

八叉树的结构示意图如图1所示：

点云数据由于数据量大，且都分布在目标物的外表面，在八叉树中每个节点对应一个数据块.本文对点云数据分割3次，分为4级，目的是为了分块检索数据.

2 点云数据八叉树模型的生成

八叉树模型是一种中间结构，它不能直接由原始采样数据生成，只能由其他模型转换得到［4］.本节由三维阵列生成八叉树模型，由于三维阵列表示的数据量大，一般情况下只作为过渡表示，把点云数据先转换成三维阵列表示，再转换成八叉树模型.

图1 八叉树结构示意图

对于2n×2n×2n的三维阵列表示的目标，若某一单元的三维坐标为（I，J，K）（I，J，K＝0，1，2，...，2n－1），将三维坐标转换成二进制表示有如下形式［3］：

把点云数据采用八叉树模型进行分割，分割三次就产生23×23×23个三维阵列格网.确定每个点所属的三维阵列格网，也就是把点云数据归属于不同的格网中，即八叉树叶节点中.八叉树的地址码采用八进制的Morton码进行编码，通过计算每个格网的Morton码，按Morton码的大小进行排序.可根据Morton码进行分块检索.

2.1 Morton码的生成

Morton码的生成算法有两种：一种是比特运算法，另一种是求余数法.比特运算法是按位操作，十进制的行号在计算机内部采用二进制的形式表示，把X、Y、Z方向的行列号用二进制的形式II、JJ、KK表示，通过取出KK、JJ、II的二进制中的各位交叉结合，就可得到每个单元的Morton码.按位运算主要利用C语言按位操作的“或”运算，由于本文是采用C＃语言进行开发，故采用第二种求Morton码的方法求余数法进行计算.求余数法是把十进制的行列号通过求余数转换为二进制的行列号，再通过公式求出Morton码.

每个点的Morton码算法如下：

1）求点云数据X，Y，Z方向的最大最小点值：

2）求出点云数据的外包络六面体的长L、宽W、高H：

3）求出三维阵列中每个单元格的大小△X，△Y，△Z：

4）求出每一个点在三维阵列中的十进制行列号l，m，k：

5）将每一单元格十进制的行列号转换为二进制表示：

十进制的行列号l，m，k通过求余运算，转换成二进制的行列号Ib，Jb，Kb.

6）根据二进制的行列号，计算每一点的Morton码的值.

2.2 点云数据的存储结构

八叉树的构建在内存中进行，由于系统内存的限制，把内存结构映射到外存数据库中，并把一些信息写入外存数据库中.在数据量大时，可直接在外存数据库中进行检索，避免把所有的数据一次性的装入系统，使得系统运行缓慢.点的数据结构用C语言表示如下：

struct Point

数据库中点表字段设计，如表1.

所对应的八叉树表字段设计，如表2.

表2 八叉树表字段结构

表2中Point1为叶节点的最小坐标点，Point2为叶节点的最大坐标点.code为叶节点的Morton码.

3 点云数据八叉树模型的实现

采用八叉树模型组织点云数据，可以达到树的深度小，检索速度快的效果.以下代码是点云数据的八叉树模型生成算法代码，求出每个点所归属的叶节点，并把它保存在数据库中，用数据库管理点云数据，可视化时，根据需要提取出数据，加快系统运行效率.本文采用SQL Server2008管理点云数据，采用C＃语言开发Map Objects组件，在Map Objects组件下进行可视化.

八叉树分为四层，分割3次算法如下：

1）从数据库中读出点云数据；

2）求出点云数据的外包络六面体；

3）求出每个点所在的十进制行列号；

4）把每个十进制的行列号转换成二进制行列号；

5）求出点的八叉树Morton码；

6）写入数据库.

关键代码如下：

4 点云数据的检索及可视化

根据组织好的点云数据进行检索，可根据Morton码提取出点云数据，也可根据区域范围，通过八叉树索引表，确定包括那些Morton码，然后进行查询.图2是采用三维激光扫描仪获取的点云数据，本文对建筑物点云数据以文本的格式导入到SQL Server 2008数据库软件中采用八叉树数据模型进行重新组织，图3是根据Morton码提取出的点云数据，不考虑反射率，记录数71 960条，用时1 s，并在MO组件下进行可视化.实验证明，采用八叉树模型组织后的点云数据检索速度较快，适于点云数据的分块提取.

图2 原始的建筑点云数据

图3 根据Morton码提取出的点云数据

5 结论

本文采用八叉树组织点云数据，可实现点云数据的分块快速检索，采用MO组件进行可视化，可实现点云数据的可视化.通过编程验证，该算法效率较高.

［1］李必军，方志祥，任 娟.从激光扫描数据中进行建筑物特征提取研究［J］.武汉大学（信息科学版），2003，28（1）：65-70

［2］惠文华，郭新成.三维 GIS中的八叉树空间索引研究［J］.测绘通报，2003，1：25-27

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

［4］李清泉，杨必胜，史文中，等.三维空间数据的实时获取、建模与可视化［M］.武汉：武汉大学出版社，2003

The Organization and Visualization of Point Cloud Data Based on the Octree

Zhang Huixia
（College of Urban and Tourism，Taiyuan Normal University，Taiyuan 030012，China）

The three dimensional laser scanning gains the massive point cloud data，and the data organization immediate influence point cloud data operating speed.By using the database administrated point cloud data，using Octree data model to carry on the organization of the cloud data，establishing the spatial index，the point cloud data are carried on the block extraction，and realize the cloud data retrieval as well as the visualization.

octree；point cloud data；data organization；visualization

张丽萍】

1672-2027（2011）03-0128-05

TP39

A

2011-04-14

张会霞（1972-），女，山西运城人，博士，太原师范学院城市与旅游学院讲师，主要从事地图制图、GIS、三维激光扫描方面的研究.