三维海量点云数据的组织与索引方法

1、第10卷第2期2008年4月地球信息科学GEO-INFORMATION SCIENCEVol 10, No. 2Apr. t 2008三维海量点云数据的组织与索引方法路明月,何永健（南京信息工程大学遥感学院，南京210044）摘要：三维点云是三维G1SS的数据来凍.也是三维CIS对地学空间对象、現孩进行表达、描述以及建模的 重耍手段。点云数据的高效组织是对其进行各种分析处理的基础.为此本文在对三维坐标点按照一定的規则进 行排序的基础上，采用规则空间八叉树与平衡二叉树相结合的嵌套复合结构进行组织，大大加速了三维点数据 基于坐标的査诃检索，为海址点云数据的进一步分析操作奠定了基础。最后，文中对该复

2、合组织结构进行了内 外存相统一的设计与实现，并验证了该方法的正确性及有效性。关縄词：三维海址点云；三维GIS；空间数据组织；复合组织结构收稿日期：2008 - 01 -26；修回日期：2008 - 03 - 07基金项目：本项目获虔拟地理环境教育部:点实验案开放基金（2OX7VGE02）资助。作者简介：路明月（1978-）,男.江苏徐州人，博匕讲师；研究方向为：三维GIS,虚拟气象空间理论与技术。 E-mail: lumingjudd nuist ediL cn1引言三维CIS是传统二维GIS在Z空间上的扩展, 能够更真实地表达地学对象及现象的存在特征. 并完成在真三维空间的分析操作.是G1S

3、发展的 重要方向。近年来随着雷达.激光扫描等三 维遥测技术S】的日益成熟，三维点云数据成为 三维领域重耍的数据来源，也是三维GIS刘地学 空间对象、现象进行表达、描述以及建模的重要 手段。通过对三维点云数据的处理操作，能够提 取出其中隐含的厲性以及空间特征信息，也可 以衍生出构建三维空间模型的其他矢量数据（如 TIN数据等）。然而三维点云数据的海量性及其离 散性在很大程度上制约着这些操作分析的快速进 行。因此需要对其进行髙效的组织，并以此建立 强大的索引机制进一步支持相关的操作分析。2三维坐标的点云数据组织对于三维点云而言，三维坐标是其基本数据, 也是蕴含空间信息的直接载体，所以对点云进行 的

4、各种涉及空间关系特征的操作处理（如三维点云 的数据压缩、空间插值、表面重构等）往往都需 要三维点坐标的匹配査询，在海最数据下，这种 匹配査询的效率成为制约其快速进行的重要因素； 并且三维坐标点作为三维矢量数据的主要表现形 式，是构建空间几何对象的基本元索，也是进行 各种矢量空间判断及操作分析的直接对象，所以 基于坐标对三维点数据进行高效的组织，对于三 维GIS的矢量数据操作有着非常重要的意义。由 此，本文采用规则空间八叉树+平衡二叉树” 的复合嵌套结构对三维海盘点云数据进行组织, 形成双重索引体系加强三维坐标点的匹配搜索， 有效地解决了这一瓶颈问题。八叉树结构是四叉树在三维空间上的扩展。 规则

5、空间八叉树结构将点云数据所“占据”空间 的外包罗六面体按照八叉树的思想进行等格网规 则剖分（其深度取决于根据数据址而设定的“格网 粒度”）.并通过坐标对比，将点数据层层深入, 归属于八叉树的叶子节点中，八叉树的中间节点 仅作为数据归属（检索）的“通道S而不进行点数 据的存储。这样“预组织”后的点云数据被分据 到若干个规则六面体中（其二维平面结构如图1所 示）。这种方法采用规则格网剖分，易于实现，具 有较好的可操作性，在点云数据的空间分布比较 均匀，且数据量不是很大时也可以达到快速检索 的目的.但是当海量数据，且点云数据的空间分 布不均匀（如存在局部点云密集）时，这种单一组 织方式存在的弊端就会

6、凸现出来：会造成叶子格 网中点云数据址的不均衡，在数据密集的叶子格 2期路明月尊：三维海址点云数据的组织与索引方法193网中进行坐标点的二次査询仍然是耗时的瓶颈, 难以全面提高点云数据的检索效率。如果大匮增 加八叉树的深度，不仅会给数据结构的实现带来 困难，也会造成大量“无点空间”的浪费，降低图1点云数据的规则空间八叉树组织平面结构示意图Fig, 1 Sketch Mp for the spatial octree structure of the points cloud基于此，文中对存储于叶子节点中的点云数 据采用平衡二叉树进行二次组织。二叉树结构本 身具有较高的检索效率(检索算法上具有对

7、数复 杂度)，但是其要求存入的数据能够按照一定的规 则进行排序，并且按照此规则所进行的排序结果 必须遵循两个原则刃：(1) 唯一性，即坐标不同的三维点坐标的排 序结果一定不同；(2) 传递性:如果 pntl pnt2, pnt2 pnt3, 则pntl pnt3(pnti为三维坐标点)。为此，本文将三维点坐标进行“分维”处理, 在一维空间中进行排序操作：首先将坐标点投影 到轴上进行比较，如果相同，再投影到y轴上比 较，依次拓展到z轴进行判断。这种方法在具体操 作时类似于字符串的比较方法，将任意两个三维 A(pntl, pnt2)坐标的儿z分别作为其三个基 本字符依次进行比较判断。伪码如下：if

8、 (xl x2)或者if (xl = =x2) and (yl y2 )或者if(xl = =x2) and (y2 = = y2 ) and (zl z2)则 pntl pnt2；该方法在一定程度上保持了三维坐标点之间 相互的空间位置关系，便于邻近域的衣询检索, 并且能够确保排序结果的唯一性及传递性，满足 二叉树的构建条件，使点云数据可以根据三维坐 标直接采用二叉树结构进行组织，进一步提高检 索效率。这样，在点数据检索时，可以首先根据三维 坐标判断其所属八叉树的叶子格网，然后根据二 叉树结构对该叶子格网中的点集数据进行二次检 索。在进行临域搜索时，提取当前坐标点所在二 叉树节点的若干前驱和后

9、续节点，再根据具体要 求配合空间八叉树结构作进一步的筛选即可获得 其临域点集。这种嵌套式复合结构通过空间规则八叉树将 海量点云数据分散到44多棵二叉树”中分别进行 “独立”组织(其二维平面结构如图2所示)，能够 全面提髙点云数据的检索效率，消除采用单一结 构的各种弊端；并且该方法对点坐标的査询检索 具有很高的效率，特别对于海量数据而言，比线 性结构要高很多：比如10亿个三维点数据，如果 采用线性查找平均比较次数为5亿次，而采用这 种复合组织结构(以5层八叉数结构为例)平均比 较次数不超过二十次。这样可以大大缩短三维点 的匹配査询时间，使该过程基本上可以认为与数 据虽无关，彻底提髙检索效率，为相

10、关的分析操 作解决了瓶颈问题。图2点云数据的复合肢套组织平面结构示意图FJ& 2 Sketch map for the compound structure of thepoints cloud3数据组织结构的设计实现与应用3.1数据组织结构设计与实现通过上述分析，三维点数据以坐标为关键字 直接存储在二叉树中，而二叉树作为二级组织结 构关联存储于空间八叉树的叶子节点中。这种结 构的内存实现比较容易(其数据结构如图3所示)， 八叉树与二叉树的嵌套关系可以用指针或者ID作 为关联手段进行实现。由于点云数据的海量性.文中在设计时将该 结构映射到外存的数据库文件组织中，使内外存 结构相一致，以便在数気

11、咆超大.以至于内存无 法一次性读入时，可以以外存替代内存进行无缝a图3点云数据复合嵌套组织的内存结构图 Fig. 3 Compound structure of 3D pointe cloud in the memoiy结合的统一数据检索。这种点云数据的嵌套复合 组织，在数据库中可以通过对八叉树表单以及点 数据表单的设定来实现。其中八叉树用于点云数 据的预处理，关键是能够快速获取点坐标所归属 的叶子节点。其字段设定如表1:1八叉树表单字段设计 Tab. 1 Fields design of the octree字段名称类型备注mlong关律字小坐标point非空大坐标point非空父空间ID耐

12、该节点子空间ID列老long本节点所包含的点数思的tring衽外存敷据库中可以是对存储文件（选用）应的视图名称（当本节点 为叶子节点时采用）在具体操作时，将点云数据的外包罗六面体 作为八叉树的根节点，即将其设定为首项记录（即 ID = 1）O检索时.以该首项记录为入口，通过其 子节点ID列表深入访问，并进行坐标所属关系判 断，直至获取叶子节点的ID（该记录的子节点列表 为空）。从而完成点云数据归属操作的“预处理”。 该八叉树表单主要记录了八叉树的结构及其基本 参数，在实际应用时，可以将其直接映射到内存 八叉树中，以更快速地完成相关的处理操作。点数据的表单字段设计，要配合八叉树的表 单结构，而且

13、能够实现二叉树结构根据点坐标快 速进行相关检索査询的功能，据此设计的字段如 表2所示：聂2点单的字段设计 Tab. 2 Fields design of the point字段名称类5!备注（外存中）IDlong坐标,double第一关傅字坐标ydouble第二关儀宇坐标*double第三关字所MAXW叶子节点IDint非空，外键其他信息待定在该表单字段设计中，利用数据库的检索特 性，通过将三维坐标的孔儿z分别设定为第一, 第二和第三关键字，完成基于点坐标的二叉树结 构向外存结构的映射，使其检索按照设定的方式 快速进行，达到内外存结构的无缝统一。字段ID 不再是索引的关键字段，仅仅作为点对象的

14、标识; 所属八叉树叶子节点的ID以外谨的形式存丁表单 中，配合八叉树结构的预处理，同时也可以通过 该字段上溯到其所属的八叉数空间，进行邻域对 象的査询检索等。这种设计将所有的点云数据存放在一个表单 中，在已知点坐标所属八叉树叶子节点ID的情况 下，仍然需要对其作至少两次检索：首先根据外 键(所属ID)进行14预搜索然后在结果中进行 基于坐标的二次搜索。在实际操作中可以从点数 据表单中根据所属空间ID(外键)提取出不同的 “视图S进行单独存放在获取所属叶子节点ID 后.直接到其对应的视图中进行快速检索，进一 步减少耗时环节，提奇检索效率。3.2应用实例文中在基于VC+.NET 2005及Open

15、GL自主 开发的三维可视化分析平台中，结合SQL Server 数据库系统实现了对某地区三维雷达点云数据(共 有1 178 799个坐标点)的复合结构组织及其可视 化表达(如图4所示)，并对其进行相关检索操作 分析，获得显着效果，有效地验证了这种复合结 构的正确性以及有效性。图4基于复合结构的海最点云数据的三维效果图 Rg. 4 3D rendering rf the points cloud dala with the compound structure4结论本文在对三维空间坐标进行顶点排序的基 础上，采用空间规则八叉树与二叉树相结合的嵌 套复合结构对空间点云数据进行了高效的组织. 根本上

16、解决了海駅点云数据基于顶点坐标的快速查 询检索的瓶颈问题，同时也为三维GIS领域基于顶 点的三维矢量数据分析操作莫定了基础。然而在数 据读入时，需要进行多次比较.以确认存放的位置. 所以初始化的速度会相对较慢。在超大数据量时, 可以将初始化后的各种数据存放于结构一致的数据 库中.以后的检索査询可以直接在数据库中进行, 从而避免复合结构的频繁初始化。参考文献(1 Raper J9 Kelk B Threelimensional GIS. In： Geographical Information Sjstemd： Principles and Applications Long-man, Lond

17、cn, 19911 (1)： 299 *317.2 Zhao H J9 Shibasaki R. Reconstruction of textured urban 3D model by ground.based User range and CCD images. IEICE Trans lnf &Syt. , E83D, 2001, (7)； 1429 *1440.3李清泉，李必军.陈静.激光宙达测fit技术及其应用 研究.武汉测绘科技大学学报.2000 , 25(5)； 387 391.4 李必军，方志祥,任娟.从激光打描数据中进行建筑 物特征提取研究.武汉大学学报倍息科学版. 2003

18、 , 28(1)： 65-705 陈静，李清泉，李必军.激光扫描测就系统的应用研 究.测绘工程，2001, 10(1)： 49-526 周備荣.张丽艳，苏旭等海於散乱点的曲面*建 算法研究.软件学报，2001, 12(2)： 249- 255.7 息文华，郭新城.3维GIS中的八夏树空间索引硏究. 测绘通报.2003,(1): 25-278 严蔚敏.吴伟民.数据结构.北京：清华大学出版 社t 1999候捷，孟岩译.C卄标准程序库.武汉：华中科技大 学出版社，2002.2期路明月尊：三维海址点云数据的组织与索引方法#2期路明月尊：三维海址点云数据的组织与索引方法#Organization and

19、 Indexing Method for 3D Points Cloud DataLU Mingyue, HE Yongjian(School of Remote Sensing 9 Nanjing University cf Informaiion Science & Technology % Nanjing 210044, China)Abstract： Being the primary data source, 3D points cloud is also an important means to describe and express the geographic object

20、s and phenomena in 3D GIS as well as to perform model building. And the effective organization of the points is the basis for its operation and analysis. Therefore, in this paper, 3D points are arranged and sorted according to a specified rule, and then organized by a compound structure of spatial o

21、ctree and balanced bina ry tree, which greatly speeds up the query process based on the 3D coordinate, and lays a solid foundation for the further analysis of 3D points data This paper also unifies the compound structure in both memory and database. And a case study has proved its validityKey words： 3D points cloud data； 3D GIS; spatial data organization: compound structureroHnsisLU WAHiFANGDATA三维海量点云数据的组织与索引方法作者：路明月，何永健，LU Mingyue, HE Yongjian作者单位：南京信息工程天学遥感学院南京,2100刊名：