1.2.1 点云数据的存储组织研究现状

三维激光扫描仪从物体表面获取的点云数据随着采样时间间隔的减小，数据量不断增加，大量的点云数据不仅加大了系统负荷，而且大大降低了后续处理效率。系统软件采集的点云数据导入普通的建模软件，由于数据量庞大几乎无法运行。因此，采用何种数据结构组织点云数据，成为数据处理、模型建立的关键。

激光扫描生产了大量多维点云数据，这些数据需要有效的存储和组织，为了支持计算和表面模型重构，大量的数据结构必须能执行特殊的空间索引和操作，Thomas Brinkhoff提出用持久稳固的数据结构来代替主存数据结构对点云进行组织，用多维的空间访问方法来组织点云数据，提出了点访问方法和矩形访问方法。

点访问方法主要有格网文件和等级Hash树两种方法，格网文件（Nievergelt et al.，1984）是一个基于Hashing原理用格网目录替代Hash函数的一种多维点访问方法。格网文件存储非均匀或相关分布的点。用格网文件分割空间具有下面属性：①数据库块描述的区域是矩形的。②数据空间完全被块区域覆盖。③块区域不重叠。Hash树是一种多维点树，Hash树的典型例子是BANG文件，BANG文件是一个等级树，树的上部分是目录，而叶节点存储数据，目录节点的块区域是基于一个格网结构并被一个矩形所表示，与传统的格网文件相比，块区域不表示完整的矩形区域，在同一节点下小块区域内藏的小矩形被从矩形移除，块区域的形状是不规则的且包含几个不相连的区域。Hash树的另一个例子是buddy（Seeger & Kriegel，1990），buddy树也是一个等级树，具有目录节点包含矩形块区域，区域不需要覆盖整个数据空间的特点。

矩形访问方法，是由Thomas Brinkhoff提出的用R树或者它的变种树R*树以及RR*树组织多维点的一种空间访问方法。指出空间访问方法是动态的索引结构支持点的插入、修改与删除，它支持数据在外存永久性的存储。矩形点访问方法适合二维、三维或多维点。它们支持基本空间查询的有效处理。基本的空间查询有：点查询与区域查询，K近邻的计算，空间连接。

Eric Wahl提出快速搜索三维点云的变化区域方法，提出了八杈树和平衡二杈树，八杈树是把一个立体空间按等级分割为八块，高等级节点不包含三维点，只有叶子节点包含三维点，其他节点被用来遍历这棵树。因此，索引可被解释为寻找八杈树从上到下的一条路径。在平衡二杈树中，只有元子单元需要作为树节点被实现，单元的索引依然按照位置进行编码，这种位置独立于数据的输入次序与空间次序，等级高的单元不需要额外分配节点。平衡二杈树的内存消耗比八杈树要低，八杈树的缺点是内存消费高，但对于大数据集，平衡二杈树加工方法更复杂些。

国内，路明月提出采用规则八杈树与平衡二杈树相结合的嵌套复合结构进行组织，规则空间八杈树结构将点云数据所“占据”空间的外包罗六面体按照八杈树的思想进行等格网规则剖分，并通过坐标对比，将点数据层层深入，归属于八杈树的叶子节点中，八杈树的中间节点仅作为数据归属（检索）的“通道”，而不进行点数据的存储。对存储于叶子节点中的点云数据采用平衡二杈树进行二次组织，以解决点云数据量分布不均匀时在数据密集的叶子格网中进行坐标点的二次查询的耗时问题。在点数据检索时，首先根据三维坐标判断其所属八杈树的叶子格网，然后根据二杈树结构对该叶子格网中的点数据进行二次检索。在进行邻域搜索时，提取当前坐标点所在二杈树节点的若干前驱和后续节点，再配合空间八杈树结构做进一步的筛选即可获得其邻域点集。但是在数据写入时，需要进行多次比较，以确定存放的位置，所以初始化的速度较慢。黄先锋从数据组织的角度提出实时绘制大规模LIDAR点云数据的方法，通过构建顺序四杈树使点云数据均匀分布在四杈树的节点上，实现快速的数据筛选。

Liu Hua提出一种实现雷达数据数据库管理的方法，这种方法是采用八杈树分割数据空间，由于数据量大，要求排序，大数据集耗费大量时间，所以不能构建全局KD树，只能构建局部KD树，即在每个八杈树数据节点构建一个局部KD树。在数据组织中，精确控制KD树节点的大小，为了有效的显示点云数据，定义了显示精度，基本的思路是通过计算投影后节点数据的大小，判断一个节点是否被显示。讨论屏幕缓冲方法，使得KD树从前向后遍历，可以减少点的显示数量增加显示速度，需要指出的是这种方法适合远离视点或者非常密的点云数据。