一种基于海量激光雷达栅格点云数据的建模方法

摘要

本发明公开了一种基于海量激光雷达栅格点云数据的建模方法，包括如下步骤：读取三维空间点云数据，同时利用这些三维空间点云数据自上而下构建四叉树空间索引；并自下而上在所述空间索引树的非叶子节点填充三维空间点云数据的索引标识信息；将上述构建的空间索引树依据深度优先遍历方式存储为二进制索引文件；将三维空间点云数据压缩存储为二进制数据文件；以面向对象方式设计数据库，并将所述空间数据对象存入数据库对象表；将上述数据库中数据调入外存暂存，并通过内存映射方式直接从外存上将指定标识信息的三维空间点云数据映射到内存，由图形处理器进行绘制。

权利要求

1.一种基于海量激光雷达栅格点云数据的建模方法，其特征在于，包括如下步骤：步骤一，读取三维空间点云数据，同时利用这些三维空间点云数据自上而下构建四叉树空间索引；并自下而上在所述空间索引树的非叶子节点填充三维空间点云数据的索引标识信息；

步骤二，将上述构建的空间索引树依据深度优先遍历方式存储为二进制索引文件；将三维空间点云数据压缩存储为二进制数据文件；

步骤三，以面向对象方式设计数据库，并将所述空间数据对象存入数据库对象表；

步骤四，将上述数据库中数据调入外存暂存，并通过内存映射方式直接从外存上将指定标识信息的三维空间点云数据映射到内存，由图形处理器进行绘制。

2.如权利要求1所述的建模方法，其特征在于，所述步骤一中，所述四叉树空间索引节点的数据结构包括节点的三维最小外包盒、二维行列数外包矩形、节点名称标识信息、节点的父指针、节点的孩子节点指针、节点存储点坐标的标识信息、三维坐标偏移参数，标识信息的偏移参数。

3.如权利要求1所述的建模方法，其特征在于，所述步骤二中，所述压缩的三维空间点云数据包括其几何属性和纹理属性信息。

4.如权利要求1所述的建模方法，其特征在于，所述步骤三中，以面向对象方式进行数据库概念模型设计、数据库逻辑模型设计、数据库物理设计；所述空间数据对象包括原始数据对象、三维最小外包盒对象、空间变换矩阵对象。

说明书

一种基于海量激光雷达栅格点云数据的建模方法

技术领域

[0001] 本发明涉及一种建模方法，尤其涉及一种基于海量激光雷达栅格点云数据的建模方法。

背景技术

[0002] 三维激光扫描仪是以激光发射器为中心多次发射激光并经地物表面反射接收激光测距，以阵列的方式进行高分辨率穹形扫描，其获取的点云数据在未经任何预处理的情况下称为栅格点云，因此该栅格点云数据具有数据量大(海量性)、按扫描线排列(栅格性)、同一射线方向上仅存在一个表面三维坐标点(唯一性)等特点。有的扫描仪装有照相机，还能获取三维点的纹理信息，但一般没有点的法向信息。各种地面激光雷达的测距范围均有一定的限制，获取数据的距离值一般在1000m以内。

[0003] 近年来，国内外在基于点云的空间数据索引和海量空间数据存储与管理研究方面已经取得长足的发展。目前，公知的适合点云的三维空间索引方法主要有规则格网、四叉树、八叉树、k-d树、R树及其变种和一些很具代表性的混合索引等。这些索引中很多是点对象和空间实体的最小外包矩形建立的，但其索引粒度基本上都索引到了单个点对象，不适用于海量点云的三维空间索引。目前的三维空间索引大多是从二维空间索引的基础上发展而来的，与二维空间索引相似，三维空间索引方法也是基于空间数据的层次化聚类原则，结构上类似于早期用于数据检索的B+树，现有的空间索引往往支持内存或外存的细节层次技术，在生成空间索引和细节层次数据时通常是复制点云数据备份，采用“以空间换时间”的方法来实时选取所需层次的数据进行处理与可视化。选取何种索引机制作为空间数据库的空间索引，要根据实际情况和应用需要来确定。目前，相关平台的软件系统采用多种索引机制并存、取长补短的策略，但还没有一种方法明显优于其他方法。另外，三维空间索引技术还存在很多问题，如高效索引树算法的改进、复杂空间查询方法的优化、查询操作中几何过滤方法的优化、索引评价标准等，这些都有待于进一步探索。

[0004] 近几年国际国内研究较多的是直接通过密接采样的离散点云(也称为点模型)的方式隐性地表示空间地物，它能更好地表达形状复杂且不规则的物体，较其他几何模型在绘制质量和绘制速度上有着较大优势，但在点模型的数据预处理阶段往往需要很大的时间和空间消耗来计算模型表面的几何属性，如求解主曲率、主方向，计算法矢和法锥面等，数据转换时间都至少需要几分钟，而且超过一定容量的海量数据还不能被预处理，如2006年斯图加特大学为斯坦福大学计算机图形实验室的QSplat软件编制的.qs格式转换工具Laser Splat 1.0就只能处理小于400M的PTX文件，这些都限制了海量点云后处理工作的实施质量与效率。

[0005] 由于空间数据的特殊性，常规的DBMS不能很好地存储与管理空间数据，通常采用的方式都是在数据库管理系统上加入一层所谓暗盒、数据刀片等空间附件实现空间数据的存储和管理，相关的产品有ESRI的ArcSDE、MapInfo的SpatialWare、Oracle的Oracle Spatial、IBM的DB2 Spatial Extender、Informix的Spatial DataBlade。这种方式结构复杂、效率不高，而且功能上受到商业产品的限制不便于扩展，编程实现较为困难。随着空间应用领域的不断扩展和空间数据的海量增长，研究和运用空间数据存储与管理技术解决现有的点云数据存储系统在性能和扩展性方面亟待解决的问题，满足人们对高性能、海量数据存储和数据安全性的要求，实现对海量数据的高效透明访问和分析已经成为当前点云数据存储与管理技术研究的热门课题。一般来讲，软件系统中三维点云数据的存储方式有以下三种：

[0006] 一、数据的文件存储及管理方式。文件存储即将所有的数据(空间数据和属性数据)都存储在一个或多个文件中。采用文件方式来管理数据的优点是灵活，即每个厂商都可以任意定义自己的文件格式。这种方式有安全性不高、数据的更新、查询、检索等操作不便、数据共享和海量数据无法管理等弊端。

[0007] 二、采用文件和关系数据库来共同管理空间数据。这是目前大多数地理信息系统(GIS)软件系统采用的数据管理方案。解决方式是空间数据采用文件方式来管理，属性数据则采用数据库进行管理。对于非结构化的描述数据，不论是文本、图像还是声音等，一般都对应于一个文件，这样便可以简单地在关系数据库中只记录其文件存在的路径。

[0008] 三、采用数据库存储空间数据和属性数据。空间数据和属性数据都可以采用关系数据技术来存储数据，即空间数据也可存放在数据库中。这种存储的方式有两种：一是空间数据和属性数据合二为一，将空间数据和属性数据存储在一起，两者不分家；二是将空间数据存放在一个模式下，属性数据存放在另一个模式下，两者分开，仍然采用空间数据和属性数据分别存储的技术。GIS中空间数据的存储方法也可以借鉴到海量点云的数据库存储与管理中，

[0009] 可以说海量空间数据的组织与数据库存储管理是空间数据处理和数据可视化的基础，这就需要新的数据模型和有效的空间索引机制支持。

发明内容

[0010] 本发明针对现有技术的弊端，提供一种基于海量激光雷达栅格点云数据的建模方法。

[0011] 本发明所述的基于海量激光雷达栅格点云数据的建模方法，包括如下步骤：

[0012] 步骤一，读取三维空间点云数据，同时利用这些三维空间点云数据自上而下构建四叉树空间索引；并自下而上在所述空间索引树的非叶子节点填充三维空间点云数据的索引标识信息；

[0013] 步骤二，将上述构建的空间索引树依据深度优先遍历方式存储为二进制索引文件；将三维空间点云数据压缩存储为二进制数据文件；

[0014] 步骤三，以面向对象方式设计数据库，并将所述空间数据对象存入数据库对象表；

[0015] 步骤四，将上述数据库中数据调入外存暂存，并通过内存映射方式直接从外存上将指定标识信息的三维空间点云数据映射到内存，由图形处理器进行绘制。

[0016] 本发明所述的基于海量激光雷达栅格点云数据的建模方法的步骤一中，所述四叉树空间索引节点的数据结构包括节点的三维最小外包盒、二维行列数外包矩形、节点名称标识信息、节点的父指针、节点的孩子节点指针、节点存储点坐标的标识信息、三维坐标偏移参数，标识信息的偏移参数。

[0017] 本发明所述的基于海量激光雷达栅格点云数据的建模方法的步骤二中，所述压缩的三维空间点云数据包括其几何属性和纹理属性信息。

[0018] 本发明所述的基于海量激光雷达栅格点云数据的建模方法的步骤三中，以面向对象方式进行数据库概念模型设计、数据库逻辑模型设计、数据库物理设计；所述空间数据对象包括原始数据对象、三维最小外包盒对象、空间变换矩阵对象。

[0019] 本发明所述基于海量激光雷达栅格点云数据的建模方法中，在海量原始点云数据读取的同时快速建立三维空间索引结构树，方便地存取自组织的空间索引数据和二进制点云数据，采用内存映射技术避免了外存的不必要细节层次数据备份与采样点冗余，节约外存和内存的空间，可视化操作时数据查询效率高，数据结构简单有效，在保证基本绘制质量的前提下达到较高的绘制效率，同时利用大型商用数据库来存储数据保证了数据的安全性与并发性，提高了海量空间数据管理的效能。

附图说明

[0020] 图1为本发明所述基于海量激光雷达栅格点云数据的建模方法的流程示意图；

[0021] 图2为本发明所述基于海量激光雷达栅格点云数据的建模方法中QMBB树空间索引节点数据的结构示意图；

[0022] 图3为本发明所述基于海量激光雷达栅格点云数据的建模方法中细节层次选取的示意图。

具体实施方式

[0023] 下面结合附图对本发明做进一步的详细说明，以令本领域技术人员参照说明书文字能够据以实施。

[0024] 如图1所示，本发明所述的基于海量激光雷达栅格点云数据的建模方法，包括如下步骤：

[0025] 步骤101，读取三维空间点云数据，同时利用这些三维空间点云数据自上而下构建四叉树空间索引；并自下而上在所述空间索引树的非叶子节点填充三维空间点云数据的索引标识信息。

[0026] 本步骤中，根据原始三维空间点云数据的栅格性，依扫描点云的行数和列数以自上而下的方式构建四叉树空间索引。

[0027] 所述四叉树空间索引节点的数据结构包括节点的三维最小外包盒(MBB)、二维行列数外包矩形(MBR)、节点名称ID、节点的父指针、节点的孩子节点指针、节点存储点坐标的ID标识、三维坐标偏移参数，ID偏移参数等等。在每个点坐标读取的过程中依次定义点的ID(标识信息)值并根据ID值将其插入四叉树索引的叶子节点中，同时计算每个叶子节点的最小外包矩形体(MBB)。

[0028] 当点云中所有的点均插入到空间索引树并计算MBB完毕后，利用均匀采样的方法以自下而上的方式填充空间索引树的非叶子节点数据，直到根节点。非叶子节点也存储多分辨率的点云数据，但不存储真实的三维坐标数据，只是存储坐标数据的索引ID，作为真实点坐标及灰度纹理信息的指针。

[0029] 这样，一个以四叉树为基础的三维空间索引结构(定义为Quad-MBBTree，QMBB树)就在数据读取的过程中快速实时生成了，同时大规模的点云数据也就被分割成多分辨率的细节层次数据块，这是后续点云数据处理和可视化的基础。

[0030] 经大量数据实验，QMBB树空间索引结构节点存储的点云数量控制在20000个点左右为宜，存储的点数超过100000个，则单个节点内点云数据读取缓慢，实时可视化难以实现；数据小于5000个则空间索引树的深度过深，海量数据查询影响索引节点的命中效率。本发明采用16384个点，当叶子节点的有效点总数达到分裂要求，即总数超过16384个点时进行节点分裂与点云数据的重分配，重复这个工作直到所有点坐标数据读取完毕，此时QMBB空间索引则构建完毕。

[0031] 步骤102，将上述构建的空间索引树依据深度优先遍历方式存储为二进制索引文件；将三维空间点云数据压缩存储为二进制数据文件。

[0032] 本发明中，QMBB树空间索引结构建立好之后将其依据深度优先遍历的方式存储为二进制索引文件，再次读取该二进制索引文件后可快速恢复该点云的QMBB树空间索引结构，而不需要重新构建空间索引。同时，将点云数据按照索引树节点内相对坐标的原理进行压缩，将点的几何属性、纹理属性及其他属性分别压缩至合理范围，以便于数据的显示与传输，所述压缩后的数据被存储为二进制数据文件。

[0033] 其中，记录点的三维坐标和RGB纹理值各至少需要三个浮点型数据，共需2*3*4等于24字节，记录点的ID和灰度各需要1个浮点型数据4字节，因此存储一个点结构共需32字节256比特(bit)。不同的数据应用不同的压缩方法，对于将灰度值和RGB纹理值，将其各分量分别拉伸到0-255整数范围，分别用一个字节来存储，这样的拉伸手段不会影响点云的纹理绘制效果。

[0034] 对于三维浮点坐标值则采用空间位置量化的方法进行压缩。由于本发明采用的空间索引分块数据的Z坐标值一般来说比较大，这由地面激光雷达的射程决定的，市场上现有的地面激光扫描仪的最远有效距离一般不会超过1000m，大于1000m之后获取的点云数据往往误差也比较大，可以丢弃不用。如前所述，以每个扫描点最小点间距1mm计，则16384个点在空间内某一坐标方向上至多存在16.384m范围，一般在X、Y方向上采用14个比特位就能精确表达点的一个方向坐标；由于Z坐标值有可能比较大，但一般不会超过1000m，我们采用20个比特位来表达Z方向坐标，大于1000m的则截断，视为无效点。同理一个节点内的每个坐标点的个数一定，不超过16384，且同一块数据类的三维点都是相邻的，ID号不会相差太大，也可在采用减去点集中最小ID值后用2个字节来表达。

[0035] 图2所示为本发明中的QMBB树空间索引节点的数据结构示意图。在图2所示数据结构图中，指向子节点的指针1标示该节点的四个子节点的节点名称编码8；三维坐标偏移量2和三维点的ID标识偏移值4是为点云数据压缩设置的属性，依据单个节点内包含的点的个数有限和点坐标的范围有限来压缩原始点云数据，将节点内所有的坐标值减去三维坐标偏移量2的值再将其转化为双字节二进制数据存储，同理三维点的ID标识也采用同样的办法压缩成双字节二进制数据存储；三维点数据ID标识指针3存储该节点内所有点的ID值，间接存储点云数据；节点的最小外包矩形体5表示该节点包含的三维点的最小外包矩形体，它是由节点内所有的点坐标计算出来的；节点的行列位置最小外包矩形6表示该节点包含的点所在的行列号的最大最小值，它是QMBB空间索引构建过程中每个节点内生成的二维行列数极值；指向父节点的指针7标示该节点的父节点的节点名称编码8，每个节点均有双向指针指示其父、子节点；节点的名称编码8唯一标识该节点的名称，其编码方式为根节点标识为字符“1”，其四个子节点分别标识为“11”、“12”、“13”、“14”，节点“11”的四个子节点分别标识为“111”、“112”、“113”、“114”，每个节点名称编码的字符串长度代表它在QMBB空间索引树中的深度；子节点处理次数标识9是在QMBB空间索引树节点迭代操作中记录子节点的操作次数。

[0036] 表1所示为本发明中空间点云数据的压缩统计。

[0037] 本发明中的总体压缩率达到37.5％，压缩了近三分之二的数据量。

[0038] 表1

[0039]

[0040] 步骤103，以面向对象方式设计数据库，并将所述空间数据对象存入数据库对象表。

[0041] 本步骤中，待二进制空间索引文件和数据文件生成后，以面向对象的方式分别进行数据库概念模型设计、数据库逻辑模型设计、数据库物理设计等，原始数据对象、MBB对象、空间变换矩阵对象以及其他属性等空间数据对象设计完毕后，将自组织的各类对象数据分别存入数据库对象表，采用ODP.NET数据库操作库来存取数据。本发明中，在可视化和数据处理的过程中始终调用数据库里存储的数据，以保证数据的安全性与并发性。所述需要的数据会被调入外存暂存，为内存映射和数据可视化工作做好准备。

[0042] 步骤104，将上述数据库中数据调入外存暂存，并通过内存映射方式直接从外存上将指定标识信息的三维空间点云数据映射到内存，由图形处理器进行绘制。

[0043] 本发明中，在进行视域裁剪和LOD(细节层次)判断时均是将数据库中的存储数据暂存到外存中，以内存映射的方式提取可视化时所需的数据进行显示。

[0044] 具体而言，针对可视化时海量外存数据的绘制问题，本发明是采用基于视点远近的细节层次(LOD)技术结合内存映射技术来进行点坐标数据的选择方案，避免了大量LOD数据的备份复制，提高了时间和空间利用率。

[0045] 具体的实现过程为：首先利用QMBB树空间索引结构中节点的MBB与OpenGL三维场景视锥体进行视域裁剪，判断MBB与视锥体是否相交，排除不在视锥体内的节点。接下来进行细节层次数据的选择，对于每个存在视锥体内的MBB的八个顶点，逐个计算屏幕视点到各个顶点的距离，记录距离的最大值MaxDist和最小值MinDist以及对应的二个顶点，将排除最大最小两个顶点后的六个顶点分别投影到视锥体的近平面上，计算投影的六边形在近平面上的投影面积ScreenArea，定义比例因子RateofArea2Dist来保守估算细节层次级别数据：

[0046] RateofArea2Dist＝ScreenArea/MinDist

[0047] 利用比例因子RateofArea2Dist取值范围的不同来确定需要显示到计算机屏幕上的数据，比例因子越小，则应采用较为粗略的层次数据；比例因子越大，则应采用较为精细的层次数据。层次数据选定后，提取相对应的QMBB树空间索引结构中节点存储的三维坐标点的ID值，接下来采用快速排序法将节点内获取点的ID值进行由小到大的排序，排序完成后利用内存映射技术直接从外存上将指定ID的坐标点数据映射到内存，这种方式快速高效，而且没有造成内存和外存的存储冗余，以指针的方式需要哪个点就提取哪个点信息，特别是经过ID排序后，内存映射时避免了在各块分页缓冲区内频繁切换的时间消耗，提高了时间利用率。最后将提取出的坐标点数据置于GPU(图形处理器)中进行绘制，保证内存中需要绘制点的数量和内存消耗量在合理的水平，最终达到有较高的显示帧率和较好的用户体验的目的。

[0048] 如图3所示，为细节层次选取的示意图中。

[0049] 首先，遍历QMBB空间索引树，从根节点开始逐个计算视点到当前节点的八个顶点的距离，并计算距离的最大最小值，分别将其对应的顶点记录下来，取其余的六个顶点计算其在视锥体近平面内的投影点，该投影点应呈平面六边形，再计算该平面六边形的近平面面积。

[0050] 图3中，三维场景内一个节点的八个顶点分别为q1-q8，经计算，q2点和q8点分别为距视点最近点和最远点，将其余六个顶点q1、q3、q4、q5、q6、q7分别投影到计算机屏幕，将计算机屏幕归算为视锥体近平面，六个投影点q1’、q3’、q4’、q5’、q6’、q7’构成一个平面六边形，计算此多边形的面积ScreenArea，加上前面计算出来的最小距离MinDist，通过前述的公式即可计算LOD判定因子RateofArea2Dist。

[0051] 本发明所述基于海量激光雷达栅格点云数据的建模方法中，在海量原始点云数据读取的同时快速建立三维空间索引结构树，方便地存取自组织的空间索引数据和二进制点云数据，采用内存映射技术避免了外存的不必要细节层次数据备份与采样点冗余，节约外存和内存的空间，可视化操作时数据查询效率高，数据结构简单有效，在保证基本绘制质量的前提下达到较高的绘制效率，同时利用大型商用数据库来存储数据保证了数据的安全性与并发性，提高了海量空间数据管理的效能。

[0052] 尽管本发明的实施方案已公开如上，但其并不仅仅限于说明书和实施方式中所列运用，它完全可以被适用于各种适合本发明的领域，对于熟悉本领域的人员而言，可容易地实现另外的修改，因此在不背离权利要求及等同范围所限定的一般概念下，本发明并不限于特定的细节和这里示出与描述的图例。