一种八叉树和三维R树集成的激光点云数据管理方

发布时间：2021-06-05

第４１卷　第４期测　绘　学　报

Ｖｏｌ．４１，Ｎｏ．４

　２

０１２年８月Ａｃｔａ　Ｇｅｏｄａｅｔｉｃａ　ｅｔ　Ｃａｒｔｏｇｒａｐ

ｈｉｃａ　Ｓｉｎｉｃａ　Ａｕｇ．，２

０１２ＧＯＮＧ　Ｊｕｎ，ＫＥ　Ｓｈｅｎｇｎａｎ，ＺＨＵ　Ｑｉｎｇ，ｅｔ　ａｌ．Ａｎ　Ｅｆｆｉｃｉｅｎｔ　Ｍａｎａｇ

ｅｍｅｎｔ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｐｏｉｎｔ　Ｃｌｏｕｄ　Ｄａｔａ　Ｂａｓｅｄ　ｏｎ　Ｏｃｔｒｅｅ　ａｎｄ　３ＤＲ－ｔｒｅｅ［Ｊ］．Ａｃｔａ　Ｇｅｏｄａｅｔｉｃａ　ｅｔ　Ｃａｒｔｏｇｒａｐ

ｈｉｃａ　Ｓｉｎｉｃａ，２０１２，４１（４）：５９７－６０４．（龚俊，柯胜男，朱庆，等．一种八叉树和三维Ｒ树集成的激光点云数据管理方法［Ｊ］．测绘学报，２０１２，４１（４）：５９７－

６０４．）一种八叉树和三维Ｒ树集成的激光点云数据管理方法

龚　俊１，柯胜男１，朱　庆２，钟若飞３

１．江西师范大学软件学院，江西南昌３３００２２；２．武汉大学测绘遥感信息工程国家重点实验室，湖北武汉４３００７９；３．首都师范大学资源环境与旅游学院，北京１０００４８

Ａｎ　Ｅｆｆｉｃｉｅｎｔ　Ｍａｎａｇ

ｅｍｅｎｔ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｐｏｉｎｔ　Ｃｌｏｕｄ　Ｄａｔａ　Ｂａｓｅｄ　ｏｎ　Ｏｃｔｒｅｅ　ａｎｄ３Ｄ　Ｒ－ｔｒｅｅＧＯＮＧ　Ｊｕｎ１，ＫＥ　Ｓｈｅｎｇｎａｎ１，ＺＨＵ　Ｑｉｎｇ２，

ＺＨＯＮＧ　Ｒｕｏｆｅｉ　３

１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｓｏｆｔｗａｒｅ，Ｊｉａｎｇｘｉ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈａｎｇ３３００２２，Ｃｈｉｎａ；２．Ｓｔａｔｅ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇｉｎ　Ｓｕｒｖｅｙｉｎｇ，Ｍａｐｐｉｎｇ　ａｎｄ　Ｒｅｍｏｔｅ　Ｓｅｎｓｉｎｇ，Ｗｕｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ　４３００７９，Ｃｈｉｎａ；３．Ｃａｐｉｔａｌ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｏｌｌｅｇｅ　ｏｆＲｅｓｏｕｒｃｅｓ，Ｅｎｖｉｒｏｎｍｅｎｔ　ａｎｄ　Ｔｏｕｒｉｓｍ，Ｂｅｉｊｉｎｇ１

０００４８，ＣｈｉｎａＡｂｓｔｒａｃｔ：Ｖｅｈｉｃｌｅ－ｂｏｒｎｅ　ｌａｓｅｒ　ｐｏｉｎｔ　ｃｌｏｕｄ　ｄａｔａ　ｈａｓ　ｂｅｃｏｍｅ　ｋｅｙ　３Ｄ　ｓｐａｔｉａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｏｕｒｃｅ　ｉｎ　ｆｉｅｌｄｓ　ｓｕｃｈ　ａｓ　ｄｉｇｉｔａｌ　ｃｉｔｙａｎｄ　ｃｒｉｓｉｓ　ｍａｎａｇｅｍｅｎｔ．Ａｉｍｉｎｇ　ａｔ　ｔｅｃｈｎｉｃａｌ　ｂｏｔｔｌｅｎｅｃｋ　ｏｆ　ｌａｒｇｅ－ｓｃａｌｅ　ｐｏｉｎｔ　ｃｌｏｕｄ　ｄａｔａ　ｍａｎａｇｅｍｅｎｔ，ａ　ｎｅｗ　ｓｐａｔｉａｌ　ｉｎｄｅｘｍｅｔｈｏｄ－３ＤＯＲ－ｔｒｅｅ　ｉｓ　ｐｒｅｓｅｎｔｅｄ，ｗｈｉｃｈ　ｉｎｔｅｇｒａｔｅｓ　ｏｃｔｒｅｅ　ａｎｄ３Ｄ　Ｒ－ｔｒｅｅ．Ｔｈｉｓ　ｍｅｔｈｏｄ　ｕｔｉｌｉｚｅｓ　ｏｃｔｒｅｅ　ｔｏ　ｆｏｒｂｉｄ　ｐｏｉｎｔ－ｂｙ

－ｐｏｉｎｔｉｎｓｅｒｔｉｏｎ　ａｎｄ　ｇｅｎｅｒａｔｅｓ　ｌｅａｆ　ｎｏｄｅｓ　ｏｆ　Ｒ－ｔｒｅｅ　ｅｆｆｉｃｉｅｎｔｌｙ．Ｒ－ｔｒｅｅ　ｓｔｒｕｃｔｕｒｅ　ｉｓ　ｅｘｔｅｎｄｅｄ　ｔｏ　ｐｒｅｓｅｎｔ　ｌｅｖｅｌｓ　ｏｆ　ｄｅｔａｉｌ（ＬＯＤ）ｇｅｎｅｒａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｐｏｉｎｔ　ｃｌｏｕｄ　ｍｏｄｅｌｓ．Ｆｉｎａｌｌｙ，ａ　ｄａｔａ　ｏｒｇａｎｉｚａｔｉｏｎ　ａｐｐｒｏａｃｈ　ｉｓ　ｐｕｔ　ｆｏｒｗａｒｄ　ｆｏｒ　ｌａｒｇｅ－ｓｃａｌｅ　ｐ

ｏｉｎｔｃｌｏｕｄ，ｗｈｉｃｈ　ｅａｓｉｌｙ　ｕｓｅｓ　ｆｉｌｅ　ｍａｐｐｉｎｇ　ｔｅｃｈｎｉｑｕｅ　ｔｏ　ａｃｃｅｌｅｒａｔｅ　ｄａｔａ　ａｃｃｅｓｓ．Ｅｘｐｅｒｉｍｅｎｔｓ　ｐｒｏｖｅ　ｔｈａｔ　ｔｈｉｓ　ａｐｐｒｏａｃｈ　ｈａｓ　ｆｉｎｅｓｐａｃｅ　ｕｔｉｌｉｚａｔｉｏｎ　ａｎｄ　ｓｐａｔｉａｌ　ｑｕｅｒｙ　ｅｆｆｉｃｉｅｎｃｅ　ｗｉｔｈ　ＬＯＤ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ　ｃａｐａｂｉｌｉｔｙ　ａｎｄ　ｄａｔａ　ｃａｃｈｅ　ｍｅｃｈａｎｉｓｍ，ｗｈｉｃｈ　ｌａｙｓ　ａｓｏｌｉｄ　ｆｏｕｎｄａｔｉｏｎ　ｆｏｒ　ｐｏｓｔ－ｐｒｏｃｅｓｓｉｎｇ　ａｎｄ　ｃｏｍｐｒｅｈｅｎｓｉｖｅ　ｐｒａｃｔｉｃｅｓ　ｏｆ　ｌａｒｇｅ－ｓｃａｌｅ　ｐｏｉｎｔ　ｃｌｏｕｄ　ｄａｔａ．Ｋｅｙ　

ｗｏｒｄｓ：ｏｃｔｒｅｅ；３Ｄ　Ｒ－ｔｒｅｅ；ｌａｓｅｒ－ｓｃａｎｎｉｎｇ；ｐｏｉｎｔ　ｃｌｏｕｄ；ｄａｔａ　ｍａｎａｇｅｍｅｎｔ摘　要：车载激光扫描点云数据已经成为数字城市和危机管理等领域越来越重要的三维空间信息源，针对大规模点云数据高效管理的技术瓶颈，提出一种八叉树和三维Ｒ树集成的空间索引方法———３ＤＯＲ树，充分利用八叉树的良好收敛性创建Ｒ树叶节点，避免逐点插入费时过程，同时Ｒ树平衡结构保证良好的数据检索效率。并还扩展Ｒ树结构生成多细节层次（ＬＯＤ）点云模型，提出一种支持缓存的多细节层次点云数据组织方法。试验证明，该方法具有良好的空间利用率和空间查询效率，支持多细节层次描述能力和数据缓存机制，可应用于大规模点云数据的后处理与综合应用。关键词：八叉树；三维Ｒ树；激光扫描；点云；数据管理

中图分类号：Ｐ２０８　　　　文献标识码：Ａ　　　　文章编号：１００１－１５９５（２０１２）０４－０５９７－

０８基金项目：国家自然科学基金（４１００１２２２）；国家９７３计划（２０１０ＣＢ７３１８０１；２０１１ＣＢ３０２３０６）；国家８６３计划（ＳＳ２０１２ＡＡ１２１００１）；江西师范大学青年英才培育资助计划；江西省教育厅科技项目（ＧＪＪ１２１８８

）１　引　言

欧洲空间数据研究组织ＥｕｒｏＳＤＲ指出三维城市建模能力需要具备高覆盖度、

高逼真度和高更新率，意味着对三维城市建模技术提出更好、更快、更廉价和更智能的要求，而这恰恰是传统三维

建模手段的弱项［

１］

。三维激光扫描技术和多角度摄影测量密集匹配技术为三维建模旺盛需求和有限人力物力资源间的冲突提供解决方案。ＲＩＥＧＬ的ＶＭＸ－２５０、ＴｏｐＣｏｎ的ＩＰ－Ｓ２和Ｏｐｔｅｃｈ的Ｌｙ

ｎｘ已是实际运行的移动测图系统［

２

］。最新的移动测图系统装备多个激光扫描仪，

动态获取厘米级密度的海量三维激光点云，精度可达５ｃｍ［３］

。移动测图

系统的原始数据采集率为３６０ＧＢ／ｈ，假设以３０～

４０ｋｍ／ｈ行驶，每千米道路数据采集量为１０ＧＢ，一个小城区的数据采集量可能高达若干ＴＢ，前所未有的数据采集速度和高分辨率要求对三维激光点

云数据高效管理面临更为严峻的挑战［

４

］。随着高分辨率车载激光扫描系统的普及应用，大量散乱点云数据的快速处理成为国际研究的焦点。点云数据后处理如简化滤波、语义分割和特征提取等交互操作受限于数据管理和可视化的性能，极大地制约了快速获取点云数据的综合

应用能力［５－

６］。在计算机图形学领域，发展了多种

专门的数据组织方法加速绘制效率和质量，但多关注单个目标的点云数据，难以有效处理复杂场

Ａｕｇ

ｕｓｔ　２０１２　Ｖｏｌ．４１　Ｎｏ．４　ＡＧＣＳ　ｈｔｔｐ：∥ｘｂ．ｓｉｎｏｍａｐ

ｓ．ｃｏｍ景的地物目标数据。由于点云数据量大且分辨率高，一种有效的处理策略是顾及细节层次的自适

应可视化。Ｓｕｒｆｅｌｓ［７］和Ｑｓｐ

ｌａｔ［８］是多细节层次点表达模型的两个最具代表性的实现方法，它们的预处理过程均很费时，

不平衡的树状结构容易导致树深过高进而致使查询效率恶化。之后，计算机图形领域的绝大多数方法基本是上述两种方法的改进，

如采用并行处理方法和图形处理器提高绘制效率，

或者实现外存缓存机制等［９］

。在空间信息科学领域，文献［１０］提出基于顺序四叉树的数据组织方法管理机载激光点云，采用分段文件映射技术随机抽取不同细节的点云，并关联到相应层的节点中，很好地实现了自适应点云绘制，然而随机抽取方式不能保证对车载激光点云也具有良好简化结果，

过深树高引发频繁迭代计算也是影响管理效率的隐患。文献［１１］的方法与之类似，

它们仍然是一种二维数据管理方法，难以最好地支持视锥体裁剪等可视化算子。文献［１２］采用八叉树和平衡二叉树的嵌套结构管理海量点云，顾及了树状结构的平衡性问题，但是采用单一维度作为二叉树剖分依据没有顾及三维空间特性。文献［１３］采用空间数据分布方法将海量点云分配至多个服务器，

采用并行访问技术提高数据管理效率，是利用计算机集群管理点云的有益尝试。

三维Ｒ树可以根据目标数据自适应地调整索引结构，目标分布状态对其影响较小，是一种有

前途的三维空间索引方法［１４－

１５］。理论上，三维Ｒ

树的动态更新和自适应调整能力非常适合分布散乱、

密度不均的三维点云应用。然而，由于算法复杂、点云数量庞大等诸多原因，至今未见Ｒ树成功管理点云的文献发表。

本文利用八叉树的快速收敛能力，提出一种八叉树和Ｒ树集成的新三维索引方法—３ＤＯＲ

树，显著提升大规模点云的Ｒ树索引创建效率，并采用一种顾及多细节层次的三维Ｒ树索引扩展结构高效生成多细节层次点云模型，支持大规模车载激光点云的高效管理和自适应可视化。本文研究内容可以描述如图１

。

图１　本文研究框架

Ｆｉｇ．１　Ｔｈｅ　ｆｒａｍｅｗｏｒｋ　ｏｆ　ｔｈｉｓ　ｓｔｕｄｙ

２　集成八叉树和Ｒ树的三维空间索引

模型３ＤＯＲ树

　　Ｒ树索引能够很好地适应空间数据分布特点，

且能提供稳健高效的空间查询能力［

１６

］。Ｒ树索引生成方法分为动态方法和静态方法，动态生成方法更符合空间数据管理要求，

但是每个点均要经过节点选择和节点分裂等复杂操作才能插入到索引结构中，对于数以亿计的点云数据来说并不现实，需要寻求一种更高效的索引创建方法，本文采用一种动静结合的方式构建三维Ｒ树索引结构，兼具静态方法的高效率和动态方法的自适应性。

下面是结合三维Ｒ树和八叉树（ｏｃｔｒｅｅ）的索引创建算法（３ＤＯｃｔ－Ｒｔｒｅｅ，简称３ＤＯＲ树）描述，图２是３ＤＯＲ树创建流程图。给三维Ｒ树设定扇出

（ｆａｎｏｕｔ）参数，即每个节点允许包含最大元组数目和最小元组数目，

采用八叉树剖分三维空间，节点收敛条件是每个叶节点中的点数目小于等于最大元组数目。八叉树分裂过程中，满足扇出参数条件的子节点将重新计算范围，

以叶节点身份插入到三维Ｒ树中。点数小于扇出参数最小值的子节点中的点输出至数组，

按顺序重组为满足扇出参数的叶节点逐一插入到Ｒ树，

过程中不对数组中的点重新空间排序，原因是这些点相对邻近，重新排序代价高且意义不大。对于无法保证满足扇出参数的情况，添加其中的点到全局点数组中，待八叉树剖分结束后，以单点身份逐一插入Ｒ树。

算法描述：点云的空间索引创建算法。算法输入：点元组集合，Ｒ树扇出参数为［ｉｍｉｎ，ｉｍａｘ］

。算法输出：三维Ｒ树索引结构。

步骤１：计算包含所有点集的最小包围盒（ｍｉｎＸ，ｍｉｎＹ，ｍｉｎＺ，ｍａｘＸ，ｍａｘＹ，ｍａｘＺ），并以（ｍｉｎＸ，ｍｉｎＹ，ｍｉｎＺ）为起算点，计算包含所有点集的最小立方体范围，作为八叉树根节点范围，全部点均是节点ｎｏｄｅ中的元组，并创建两个点数组Ａｒｒａｙ１和Ａｒｒａｙ

２。步骤２：如果元组数目大于ｉｍａｘ，则将空间均匀分为８个子节点Ｃｈｉｌｄｉ（

ｉ＝０，１，…，７），并将点分配至对应的子节点，进入步骤３；如果ｎｏｄｅ中

元组数目小于等于ｉｍａｘ，

则停止分裂。步骤３：清空Ａｒｒａｙ１，逐一遍历子节点Ｃｈｉｌｄｉ，如果Ｃｈｉｌｄｉ中的点数目小于ｉｍｉｎ，将其中的点加入Ａｒｒａｙ１中，令Ａｒｒａｙ

１中的点数目为ｉＰｔ－８９５

第４期龚　俊，等：一种八叉树和三维Ｒ树集成的激光点云数据管理方法Ｎｕｍ，

进入步骤４

。图２　３ＤＯＲ树创建流程图

　Ｆｉｇ

．２　Ｆｌｏｗ　ｃｈａｒｔ　ｏｆ　ｔｈｅ　３ＤＯＲ－Ｔｒｅｅ　ｃｏｎｓｔｒｕｃｔｉｏｎｐ

ｒｏｃｅｄｕｒｅ步骤４：如果ｉＰｔＮｕｍ小于ｉｍｉｎ，将数组中所有点逐一插入Ａｒｒａｙ２中；如果ｉＰｔＮｕｍ大于等于ｉｍｉｎ且小于等于ｉｍａｘ，

则将数组中所有点打包为叶节点插入Ｒ树中；如果ｉＰｔＮｕｍ大于ｉｍａｘ且小

于等于２ｉｍａｘ，将点均分为两个叶节点，插入Ｒ树中；如果ｉＰｔＮｕｍ大于２ｉｍａｘ，ｋ为ｉＰｔＮｕｍ／ｉｍａｘ取整，将数组前（ｋ－１）ｉｍａｘ个点，均分（ｋ－１）个叶节点插入Ｒ树，剩余点数ｉＲｅｓｔＮｕｍ为ｉＰｔＮｕｍ－

（ｋ－１）ｉｍａｘ，如果ｉＲｅｓｔＮｕｍ等于ｉｍａｘ，则将其作为一个叶节点插入到Ｒ树，如果大于ｉｍａｘ（必然小于２ｉｍａｘ）

，则将其均分为两个叶节点，插入Ｒ树中。步骤５：逐一遍历子节点Ｃｈｉｌｄｉ，如果Ｃｈｉｌｄｉ中的点数目大于ｉｍａｘ，则令ｎｏｄｅ为Ｃｈｉｌｄｉ，进入步骤２。

步骤６：逐一遍历子节点Ｃｈｉｌｄｉ，如果Ｃｈｉｌｄｉ

中的点数目大于等于ｉｍｉｎ且小于等于ｉｍａｘ，则将节点中的点组成叶节点插入Ｒ树。

步骤７：所有八叉树分支分裂结束后，将

Ａｒｒａｙ

２中的点以元组身份逐一插入Ｒ树。步骤８：退出。

本方法利用八叉树分配邻近点至相同或相邻节点中，通过以节点为插入单元的策略批量插入点，避免了逐点插入的费时操作，显著地提高索引

生成效率，同时仍然采用动态生成方法构建Ｒ

树，使得树形结构具有很好的空间适应性，保证平衡树状结构和良好空间利用率。图３是某点云数据的八叉树叶节点层（分裂参数为１００，即大于１００个点要分裂节点）和３ＤＯＲ树结构叶节点层（扇出参数为４０和１００

）

。图３　八叉树和３ＤＯＲ树的叶节点层Ｆｉｇ

．３　Ｌｅａｆ　ｎｏｄｅｓ　ｉｎ　Ｏｃｔｒｅｅ　ａｎｄ　３ＤＯＲ－ｔｒｅｅ３　顾及多细节层次的３ＤＯＲ树扩展结构

对于车载激光点云测图应用需要高效交互性能来说，启用多细节层次策略成为合理甚至必须的选择，即根据视距和软硬件性能实时选择合适细节层次表示点云场景。关于Ｒ树和多细节层次场景结合的已有研究均试图采用Ｒ树的天然层次结构实现目标查询和细节层次查询的双重功

能［

１７－

１９］。然而，应用Ｒ树节点包围盒作为低细节层次描述，忽略单个目标的ＬＯＤ（ｌｅｖｅｌ　ｏｆ　ｄｅｔａｉｌｓ）描述需求，也不能满足可视化精度要求。

传统Ｒ树索引方法仅在叶节点中管理目标模型，本文扩展结构使得中间节点也能管理目标模型。叶节点层管理全部和最精细的目标，从每个子节点按照某种规则挑选一个最有代表性的目标作为较粗层次目标模型集合存于父节点中，因此上层节点中的目标数目和子节点数目相等。举例说明，

从每个子节点中选择一个距离目标集合重心最近的目标作为上层节点的目标。

本文方法借助Ｒ树的层次结构，叶节点代表最高的细节层次，中间节点代表中等的细节层次，根节点代表最低的细节层次。每层被设置一个适用范围，包括最近距离和最远距离，相邻层的适用范围无缝拼接。同层中所有节点的适用范围相同，当视点和节点的距离落于该范围内，即访问节点中的点模型。在全景描绘时，只需访问根节点中的点模型，随着视点接近，视域逐渐减小，关注

９

９５

Ａｕｇ

ｕｓｔ　２０１２　Ｖｏｌ．４１　Ｎｏ．４　ＡＧＣＳ　ｈｔｔｐ：∥ｘｂ．ｓｉｎｏｍａｐ

ｓ．ｃｏｍ细节逐渐提高，从根节点访问其子节点，根节点中的点仅是其子节点中的重要目标，因此关注的目标集合有所增加，细节层次增强。ＬＯＤ选取距离原则的详细解释可以参考文献［２０］。图４是点云的多细节层次描述效果

。

图４　点云的多细节层次描述

Ｆｉｇ．４　ＬＯＤ　ｒｅｐ

ｒｅｓｅｎｔａｔｉｏｎ　ｏｆ　ｐｏｉｎｔ　ｃｌｏｕｄｓ４　基于３ＤＯＲ树的点云数据高效组织方法

　　由于文件大小的限制，

大规模点云工程采用工程－点云－点层次模式组织点云数据。车载激光点云采集过程中，每隔几百万个点分段为单个点

云，单个点云的原始文本文件数据量为数百兆字节，某个应用中的点云集合即为点云工程，一个小型城镇的点云工程可能高达数十ＧＢ。本文采用自定义的文件结构组织大规模车载激光点云，目的是为了提高数据管理效率，其方法也可实现于商业数据库管理系统。

以自定义文件系统方式为例，点云工程是包含众多点云的目录，点云是单个二进制数据文件，图５是本文数据组织方法描述。每个点云包括头部分和实体部分，头部分包括点云的整体信息，如版本号、总数据量、Ｒ树扇出参数（子节点数目的最大最小值）、总点数、Ｒ树总层数、

空间范围、中心点坐标、压缩标志以及根节点地址等。点坐标是实际点坐标减去中心点坐标的差值，这样坐标可以采用较少有效位数表示，

有利于采用４字节单精度浮点类型表示点坐标，另外，如果空间范围在各坐标轴上的长度小于６５５．３５ｍ且精度要求在厘米级（车载激光扫描数据精度可达到厘米级），将坐标值乘以１００然后用２字节短整数类型表示点坐标，数据量减少７５％

。

图５　点云工程数据组织方法

Ｆｉｇ．５　Ｄａｔａ　ｏｒｇａｎｉｚａｔｉｏｎ　ｍｅｔｈｏｄ　ｏｆ　ｐｏｉｎｔ　ｃｌｏｕｄ　ｐｒｏｊ

ｅｃｔ　　点云的实体部分采用三维Ｒ树索引结构管

理点数据，Ｒ树索引结构包括根节点、中间节点和叶节点。本文的多细节层次生成方法中，上层节点从每个子节点中选取一个点作为低细节层次描

述，为避免重复存储和处理，选取点将从子节点移出至上层节点，这样中间节点和叶节点中的点数目要减１。为了实现缓存机制，即根据视域条件动态调度数据，父节点记录子节点的首地址，即子

００６

第４期龚　俊，等：一种八叉树和三维Ｒ树集成的激光点云数据管理方法节点相对文件起始位置的偏移量。Ｒ树存储结构可以分为按广度遍历存储顺序和按深度遍历存储顺序组织。广度遍历存储顺序指按节点层的次序存储节点数据，从根节点开始，将节点按层顺序依次记录到文件中，

负面影响是父节点和子节点无法集中存储；深度遍历存储顺序指从根节点开始，然后记录其各个子树，负面影响是中间层的兄弟节点无法集中存储。图６（ａ）和（ｂ）分别是广度遍历存储和深度遍历存储的原理

。

图６　广度和深度遍历存储原理描述

　Ｆｉｇ．６　Ｐｒｉｎｃｉｐａｌ　ｄｅｓｃｒｉｐｔｉｏｎ　ｏｆ　ｂｒｅａｄｔｈ　ａｎｄ　ｄｅｐ

ｔｈｔｒａｖｅｒｓａｌ　ｓｔｏｒａｇ

ｅ点云工程数据规模通常很大，超出主存容量和图形绘制硬件处理能力，一般打开工程时仅调度上面数层节点中的点数据以描述全景，当视点逼近局部场景时，

将通过父节点依次访问子节点直至叶节点，因此广度优先存储和深度优先存储方式均不能完全满足高效调度的要求。本文采用二者混合方案来最大限度提升数据调度效率。以叶节点层为第０层，例如全景显示第２层及以上节点中的点数据时，将第２层及以上层采用广度优先存储，

最下两层按照深度优先存储，至于具体以第几层为分界线，将根据总数据量决定，如果数据量小可以下调，如果数据量大可以上调。图７是本文方法的原理描述，其中第２层是分界线。本文方法采用文件映射技术访问点云文件，每个父节点记录所有子节点地址，

采用类似于访问内存方法根据节点地址访问节点外存数据。本文方法将极有可能连续访问的节点数据集中存储，

有利于提高外存访问效率

。

图７　混合存储方式原理描述

Ｆｉｇ．７　Ｐｒｉｎｃｉｐａｌ　ｄｅｓｃｒｉｐｔｉｏｎ　ｏｆ　ｍｉｘｅｄ　ｓｔｏｒａｇ

ｅ单点数据内容包括三维坐标、颜色以及强度等信息，

可以根据应用需要扩展单点结构。如果采取压缩方式存储，

三维坐标值采用２字节短整型表示，相对于双精度浮点型表示，数据量减少７５％，可以显著减少数据调度量，提升外存访问效率。另外，为最大限度提升三维可视化效率，点数据应当按照图形绘制硬件特点进行组织，

例如，采用Ｏｐ

ｅｎＧＬ绘制引擎时，可以将节点中的点数据组织成ＶＢＯ顶点缓冲形式，

直接送入绘制管线处理。５　试验结果与分析

本试验采用测试数据是车载激光扫描移动测图系统采集的真实数据，是中国某小型城镇的真

彩色三维点云数据。车辆行驶耗费２０ｍｉｎ扫描该镇全部道路，获取详细的街道、房屋立面、树木以及电线等点模型。原始数据包含９２个点云文件，每个点云文件包含２００多万个点，总数据量约为１４．６ＧＢ（包含坐标、颜色、时间等数据），总点数为２．２亿。测试环境配置如下：笔记本电脑，ＣＰＵ　Ｉｎｔｅｌ　Ｄｕｏ　Ｔ７５００，内存１ＧＢ。５．１　索引创建效率测试

索引创建效率关系到应用成败，如果索引创建需要十几个小时甚至更长，即使查询效率满足交互要求，也不能适应实际应用需要。由于格网索引的格网尺寸难以确定，

且大量空格网容易导致空间利用率极低，本文不予比较测试。本文分别对八叉树、三维动态Ｒ树和３ＤＯＲ树生成算法进行效率测试。其中，八叉树参数为１００，即节点中点数目小于等于１００时停止分裂，三维Ｒ树的扇出参数为４０和１００，而３ＤＯＲ树中，八叉树分裂参数为１００，Ｒ树扇出参数为４０和１００。

采用一份包含２　４２６　４５４个点的点云数据测试索引创建效率，表１中有八叉树、３ＤＯＲ树以及三维动态Ｒ树的创建效率对比。八叉树深度

１

０６

Ａｕｇｕｓｔ　２０１２　Ｖｏｌ．４１　Ｎｏ．４　ＡＧＣＳ　ｈｔｔｐ：∥ｘｂ．ｓｉｎｏｍａｐｓ．ｃｏｍ

不平衡，叶节点树深从１到１７不等。３ＤＯＲ树深

度平衡，树深为４。三维动态Ｒ树深度平衡，树深

为５。从测试数据可知，本文的３ＤＯＲ索引方法

创建效率满足准实时要求，树深平衡，并且树深比

另两种方法小。原因是，３ＤＯＲ树本质上仍是Ｒ

树索引结构，且叶节点基本是满负荷，从而节点数

目减少和深度减小。较小的树深直接减少迭代运

算层数，有利于显著改善算法效率。本文对总数

据量１４．６ＧＢ的点云工程创建索引，总耗费时间

约为４０ｍｉｎ。

５．２　空间利用率测试

相对于ＣＰＵ计算和主存访问效率，外存访

问效率低两个数量级以上且改善空间有限，数据

量大小直接关系到后续外存数据调度效率，进而

影响用户体验。点云工程数据量往往大于主存容

量，动态调度和数据缓存机制成为必须采用的策

略。本文通过中心点平移方法将双精度浮点型数

据转化为单精度浮点型，进一步将单精度浮点型

转化为短整型，并清除冗余点（距离小于１ｃｍ视

为冗余点），数据量压缩显著，表１中有文本格

式、Ｐｏｉｎｔｏｏｌｓ商业格式和本文结构的数据量对

比。不难看出，原始文本数据转化为本文数据格

式，压缩率超过全球业界领先者Ｐｏｉｎｔｏｏｌｓ。

表１　空间索引重要指标对比

Ｔａｂ．１　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｋｅｙ　ｃｒｉｔｅｒｉａ　ｆｏｒ　ｓｐａｔｉａｌ　ｉｎｄｅｘ

空间索引创建效率对比／ｓ空间利用率对比／ＧＢ

八叉树三维

Ｒ树

本文

方法

原始

数据

Ｐｏｉｎｔｏｏｌｓ

本文

结构

测试

数据

５　５７４　２５　１６　１．８２　１．４３

５．３　数据调度与可视化效率测试

如果用户打开和全景显示工程的等待时间过长，将严重影响用户体验。采用Ｐｏｉｎｔｏｏｌｓ商业平台将试验数据转化为其特有ＰＯＤ格式并组织成为工程后，试验环境打开工程耗时超过４ｍｉｎ。由于是商业平台，无法测算其效率瓶颈。值得指出的是，当工程打开后，该商业平台可以保证后续交互操作的流畅性。

本文方法中，点云工程包含２亿多个点，扇出参数为４０和１００，第２层及以上点云模型不会超过１０万个点（２×１０８／（４０×４０）），因此打开工程只需调度第２层及以上的点云模型。第２层以上按照广度优先遍历方法进行存储，后续访问时按照广度优先遍历顺序即可将所需节点外存数据依次读取，不会出现跳跃访问，最大限度地提高数据访问效率，试验结果表明耗时仅需４ｓ，图８是点云工程的全景图。另外，本文设计试验测试深度优先存储方法的访问效率，节点数据重新按照深度优先遍历方式存储，打开整个工程耗时３ｍｉｎ，相比于本文方法，效率下降明显

。

图８　点云工程全景

Ｆｉｇ．８　Ｆｕｌｌ　ｓｃｅｎｅ　ｏｆ　ｐｏｉｎｔ　ｃｌｏｕｄ　ｐｒｏｊｅｃｔ

本试验环境允许的数据缓存容量不超过２００兆，单帧绘制点数不超过５００万个，如果超过容许值将自动清理缓冲区。当视点落于场景中近距离浏览地物目标时，自适应可视化机制下最高细节层次作用范围的最远距离一般保持在１５ｍ左右，即使显著改变视点位置，所需调度数据量也不会超过１０ＭＢ，调度时间不超过２ｓ。试验采用多线程机制调度数据，并不影响主线程绘制任务，实现点云场景多细节层次描述效果。

５．４　空间查询效率测试

车载激光扫描平台的一项重要任务是三维测图，捕捉三维点成为应用成败的关键。如果不借助空间索引功能，从场景中数以亿计的点集中搜索目标点将会效率极低。本文借助三维Ｒ树索引能力，捕捉目标点没有明显停顿，符合交互测图要求。试验过程测试多个环节，如捕捉点、场景移动和连线等功能，均能实现流畅交互操作。图９是本试验平台的测图结果，其中包括天线和建筑物墙面等测图成果

。

图９　试验平台三维测图效果

Ｆｉｇ．９　３Ｄｍａｐｐｉｎｇ　ｉｎ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｐｌａｔｆｏｒｍ

２０６

第４期龚　俊，等：一种八叉树和三维Ｒ树集成的激光点云数据管理方法

６　结　论

大规模点云管理和可视化是阻碍点云应用的难题，本文采用一种集成八叉树和三维Ｒ树的新方法，借助八叉树细粒度地划分点云的三维空间，通过将八叉树叶节点组织为Ｒ树叶节点的策略，避免了海量点云的逐点插入操作，显著提升索引创建效率，由于依然采用动态插入方法创建三维Ｒ树，保证了深度平衡的树状结构，实现良好的空间查询效率。基于Ｒ树的天然层次结构，本文还提出了一种点云场景多细节层次模型生成方法和点云数据层次组织结构。本文研究不仅为大规模点云自适应可视化提供管理支持，同时也为激光点云深度利用提供理论和方法支持。

当前单点包含４～６个属性值，随着传感器技术的发展，未来极可能翻倍甚至更多，通过自动分类和目标提取还可以产生更加丰富的语义信息，也给点云管理带来新挑战。语义可以视为点云的另一种细节层次，后续研究将面向数据融合和语义管理的点云管理方法，实现同全景影像、矢量图形以及语义信息的集成应用。

参考文献：

［１］　ＮＥＢＩＫＥＲ　Ｓ，ＢＬＥＩＳＣＨ　Ｓ，ＧＬＣＨ　Ｅ．ＥｕｒｏＳＤＲ　ＯｎｌｉｎｅＳｕｒｖｅｙ　ｏｎ　Ｖｉｒｔｕａｌ　Ｇｌｏｂｅｓ［Ｒ］．Ｔｈｅ　１１４ｔｈ　ＥｕｒｏＳＤＲ　Ｓｔｅｅｒｉｎｇ

Ｃｏｍｍｉｔｔｅｅ　Ｍｅｅｔｉｎｇ，Ｐａｒｉｓ：［ｓ．ｎ．］，２００９．

［２］　ＢＡＲＢＥＲ　Ｄ，ＭＩＬＬＳ　Ｊ，ＳＭＩＴＨ－ＶＯＹＳＥＹ　Ｓ．ＧｅｏｍｅｔｒｉｃＶａｌｉｄａｔｉｏｎ　ｏｆ　ａ　Ｇｒｏｕｎｄ　Ｂａｓｅｄ　Ｍｏｂｉｌｅ　Ｌａｓｅｒ　Ｓｃａｎｎｉｎｇ

Ｓｙｓｔｅｍ［Ｊ］．ＩＳＰＲＳ　Ｊｏｕｒｎａｌ　ｏｆ　Ｐｈｏｔｏｇｒａｍｍｅｔｒｙ　ａｎｄ　Ｒｅｍｏｔｅ

Ｓｅｎｓｉｎｇ，２００８，６３（１）：１２８－１４１．

［３］　ＨＡＡＬＡ　Ｎ，ＰＥＴＥＲ　Ｍ，ＫＲＥＭＥＲ　Ｊ，ｅｔ　ａｌ．ＭｏｂｉｌｅＬｉＤＡＲ　Ｍａｐｐｉｎｇ　ｆｏｒ　３ＤＰｏｉｎｔ　Ｃｌｏｕｄ　Ｃｏｌｌｅｃｔｉｏｎ　ｉｎ　Ｕｒｂａｎ

Ａｒｅａｓ—Ａ　Ｐｅｒｆｏｒｍａｎｃｅ　Ｔｅｓｔ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＸＸＩ

ＩＳＰＲＳ　Ｃｏｎｇｒｅｓｓ．［Ｓ．ｌ．］：ＩＳＰＲＳ，２００８．

［４］　ＮＥＢＩＫＥＲ　Ｓ，ＢＬＥＩＳＣＨ　Ｓ，ＣＨＲＩＳＴＥＮ　Ｍ．Ｒｉｃｈ　ＰｏｉｎｔＣｌｏｕｄｓ　ｉｎ　Ｖｉｒｔｕａｌ　Ｇｌｏｂｅｓ———Ａ　Ｎｅｗ　Ｐａｒａｄｉｇｍ　ｉｎ　Ｃｉｔｙ

Ｍｏｄｅｌｉｎｇ？［Ｊ］Ｃｏｍｐｕｔｅｒ，Ｅｎｖｉｒｏｎｍｅｎｔ　＆Ｕｒｂａｎ　Ｓｙｓｔｅｍ，

２０１０，３４（６）：５０８－５１７．

［５］　ＹＡＮＧ　Ｂｉｓｈｅｎｇ，ＷＥＩ　Ｚｈｅｎｇ，ＬＩ　Ｑｉｎｇｑｕａｎ，ｅｔ　ａｌ．Ａ　Ｃｌａ－ｓｓｉｆｉｃａｔｉｏｎ－ｏｒｉｅｎｔｅｄ　Ｍｅｔｈｏｄ　ｏｆ　Ｆｅａｔｕｒｅ　Ｉｍａｇｅ　Ｇｅｎｅｒａｔｉｏｎ　ｆｏｒ

Ｖｅｈｉｃｌｅ－ｂｏｒｎｅ　Ｌａｓｅｒ　Ｓｃａｎｎｉｎｇ　Ｐｏｉｎｔ　Ｃｌｏｕｄｓ［Ｊ］．Ａｃｔａ

Ｇｅｏｄａｅｔｉｃａ　ｅｔ　Ｃａｒｔｏｇｒａｐｈｉｃａ　Ｓｉｎｉｃａ，３９（５）：５４０－５４５．（杨必

胜，魏征，李清泉，等．面向车载激光扫描点云快速分类的

点云特征图像生成方法［Ｊ］．测绘学报，２０１０，３９（５）：５４０－５４５．）

［６］　ＨＵＡＮＧ　Ｘｉａｎｆｅｎｇ，ＬＩ　Ｈｕｉ，ＷＡＮＧ　Ｘｉａｏ，ｅｔ　ａｌ．ＦｉｌｔｅｒＡｌｇｏｒｉｔｈｍｓ　ｏｆ　Ａｉｒｂｏｒｎｅ　ＬｉＤＡＲ　Ｄａｔａ：Ｒｅｖｉｅｗ　ａｎｄ

Ｐｒｏｓｐｅｃｔｓ［Ｊ］．Ａｃｔａ　Ｇｅｏｄａｅｔｉｃａ　ｅｔ　Ｃａｒｔｏｇｒａｐｈｉｃａ　Ｓｉｎｉｃａ，

２００９，３８（５）：４６６－４６９．（黄先锋，李卉，王潇，等．机载Ｌｉ－

ＤＡＲ数据滤波方法评述［Ｊ］．测绘学报，２００９，３８（５）：４６６－４６９．）

［７］　ＰＦＩＳＴＥＲ　Ｈ，ＺＷＩＣＫＥＲ　Ｍ，ＶＡＮ　ＢＡＡＲ　Ｊ，ｅｔ　ａｌ．Ｓｕｒｆｅｌｓ：Ｓｕｒｆａｃｅ　Ｅｌｅｍｅｎｔｓ　ａｓ　Ｒｅｎｄｅｒｉｎｇ　Ｐｒｉｍｉｔｉｖｅｓ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆＡＣＭ　ＳＩＧＧＲＡＰＨ　２０００．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２０００：３３５－３４２．

［８］　ＲＵＳＩＮＫＩＥＷＩＣＺ　Ｓ，ＬＥＶＯＹ　Ｍ．ＱＳｐｌａｔ：Ａ　ＭｕｌｔｉｒｅｓｏｌｕｔｉｏｎＰｏｉｎｔ　Ｒｅｎｄｅｒｉｎｇ　Ｓｙｓｔｅｍ　ｆｏｒ　Ｌａｒｇｅ　Ｍｅｓｈｅｓ［Ｃ］∥

Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＡＣＭ　ＳＩＧＧＲＡＰＨ　２０００．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ

Ｐｒｅｓｓ，２０００：３４３－３５２．

［９］　ＷＡＮＤ　Ｍ，ＢＥＲＮＥＲ　Ａ，ＢＯＫＥＬＯＨ　Ｍ，ｅｔ　ａｌ．Ｐｒｏｃｅｓｓｉｎｇａｎｄ　Ｉｎｔｅｒａｃｔｉｖｅ　Ｅｄｉｔｉｎｇ　ｏｆ　Ｈｕｇｅ　Ｐｏｉｎｔ　Ｃｌｏｕｄｓ　ｆｒｏｍ　３ＤＳｃａｎｎｅｒｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ　＆Ｇｒａｐｈｉｃｓ，２００８，３２（２）：２０４－２２０．

［１０］　ＨＵＡＮＧ　Ｘｉａｎｇｆｅｎｇ．Ｒｅｓｅａｒｃｈ　ｏｎ　３ＤＢｕｉｌｄｉｎｇ　Ｍｏｄｅｌ　Ｅｘｔｒａｃｔｉｏｎｆｒｏｍ　Ａｉｒｂｏｒｎｅ　ＬＩＤＡＲ　Ｄａｔａ［Ｄ］．Ｗｕｈａｎ：Ｗｕｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ，２００６．（黄先锋．利用机载ＬｉＤＡＲ数据重建３Ｄ建筑物模

型的关键技术研究［Ｄ］．武汉：武汉大学，２００６．）

［１１］　ＺＨＩ　Ｘｉａｏｄｏｎｇ，ＬＩＮ　Ｚｏｎｇｊｉａｎ，ＳＵ　Ｇｕｏｚｈｏｎｇ，ｅｔ　ａｌ．Ｒｅｓｅａｒｃｈｏｎ　Ｏｒｇａｎｉｚａｔｉｏｎ　ｏｆ　Ａｉｒｂｏｒｎｅ　ＬｉＤＡＲ　Ｐｏｉｎｔｓ　Ｃｌｏｕｄ　Ｂａｓｅｄ　ｏｎ

Ｉｍｐｒｏｖｅｄ　Ｑｕａｄｔｒｅｅ　Ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ

ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１０，４６（９）：７１－７４．（支晓栋，林宗坚，

苏国中，等．基于改进四叉树的ＬｉＤＡＲ点云数据组织研

究［Ｊ］．计算机工程与应用，２０１０，４６（９）：７１－７４．）

［１２］　ＬＵ　Ｍｉｎｇｙｕｅ，ＨＥ　Ｙｏｎｇｊｉａｎ．Ｏｒｇａｎｉｚａｔｉｏｎ　ａｎｄ　ＩｎｄｅｘｉｎｇＭｅｔｈｏｄ　ｆｏｒ　３ＤＰｏｉｎｔｓ　Ｃｌｏｕｄ　Ｄａｔａ［Ｊ］．Ｇｅｏ－ｉｎｆｏｒｍａｔｉｏｎ

Ｓｃｉｅｎｃｅ，２００８，１０（２）：１９０－１９４．（路明月，何永健．三维海

量点云数据的组织与索引方法［Ｊ］．地球信息科学，

２００８，１０（２）：１９０－１９４．）

［１３］　ＭＡ　Ｈ，ＷＡＮＧ　Ｚ．Ｄｉｓｔｒｉｂｕｔｅｄ　Ｄａｔａ　Ｏｒｇａｎｉｚａｔｉｏｎ　ａｎｄ　ＰａｒａｌｌｅｌＤａｔａ　Ｒｅｔｒｉｅｖａｌ　Ｍｅｔｈｏｄｓ　ｆｏｒ　Ｈｕｇｅ　Ｓｃａｎｎｅｒ　Ｐｏｉｎｔ　Ｃｌｏｕｄｓ

［Ｊ］．Ｃｏｍｐｕｔｅｒ　＆Ｇｅｏｓｃｉｅｎｃｅ，２０１１，３７（１）：１９３－２０１．［１４］　ＺＨＵ　Ｑ，ＧＯＮＧ　Ｊ，ＺＨＡＮＧ　Ｙ　Ｔ．Ａｎ　Ｅｆｆｉｃｉｅｎｔ　３ＤＲ－ｔｒｅｅＳｐａｔｉａｌ　Ｉｎｄｅｘ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｖｉｒｔｕａｌ　Ｇｅｏｇｒａｐｈｉｃ　Ｅｎｖｉｒｏｎ－

ｍｅｎｔｓ［Ｊ］．ＩＳＰＲＳ　Ｊｏｕｒｎａｌ　ｏｆ　Ｐｈｏｔｏｇｒａｍｍｅｔｒｙ　ａｎｄ　Ｒｅｍｏｔｅ

Ｓｅｎｓｉｎｇ，２００７，６２（３）：２１７－２２４．

［１５］　ＧＯＮＧ　Ｊｕｎ，ＺＨＵ　Ｑｉｎｇ，ＺＨＡＮＧ　Ｙｅｔｉｎｇ，ｅｔ　ａｌ．Ａｎ　Ｅｆｆｉｃｉｅｎｔ３ＤＲ－ｔｒｅｅ　Ｅｘｔｅｎｓｉｏｎ　Ｍｅｔｈｏｄ　Ｃｏｎｃｅｒｎｅｄ　ｗｉｔｈ　Ｌｅｖｅｌｓ　ｏｆ

Ｄｅｔａｉｌ［Ｊ］．Ａｃｔａ　Ｇｅｏｄａｅｔｉｃａ　ｅｔ　Ｃａｒｔｏｇｒａｐｈｉｃａ　Ｓｉｎｉｃａ，２０１１，

４０（２）：２４９－２５５．（龚俊，朱庆，张叶廷，等．顾及多细节层

次的三维Ｒ树索引扩展方法［Ｊ］．测绘学报，２０１１，４０（２）：

２４９－２５５．）

［１６］　ＭＡＮＯＬＯＰＯＵＬＯＳ　Ｙ，ＮＡＮＯＰＯＵＬＯＳ　Ａ，ＰＡＰＡＤＯ－ＰＯＵＬＯＳ　Ａ　Ｎ，ｅｔ　ａｌ．Ｒ－Ｔｒｅｅｓ：Ｔｈｅｏｒｙ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ

［Ｍ］．Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ　Ｐｒｅｓｓ，２００５．

［１７］　ＫＯＦＬＥＲ　Ｍ．Ｒ－ｔｒｅｅｓ　ｆｏｒ　Ｖｉｓｕａｌｉｚｉｎｇ　ａｎｄ　Ｏｒｇａｎｉｚｉｎｇ　Ｌａｒｇｅ３ＤＧＩＳ　Ｄａｔａｂａｓｅｓ［Ｄ］．Ｇｒａｚ：Ｇｒａｚ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，１９９８．

［１８］　ＺＬＡＴＡＮＯＶＡ　Ｓ．３ＤＧＩＳ　ｆｏｒ　Ｕｒｂａｎ　Ｄｅｖｅｌｏｐｍｅｎｔ［Ｄ］．Ｅｎｓｃｈｅｄｅ：ＩＴＣ，２０００．

［１９］　ＬＩ　Ｊｕｎ，ＪＩＮＧ　Ｎｉｎｇ，ＳＵＮ　Ｍａｏｙｉｎ．Ａ　Ｍｅｃｈａｎｉｓｍ　ｏｆ

３

０

６

Ａｕｇｕｓｔ　２０１２　Ｖｏｌ．４１　Ｎｏ．４　ＡＧＣＳ　ｈｔｔｐ：∥ｘｂ．ｓｉｎｏｍａｐｓ．ｃｏｍＩｍｐｌｅｍｅｎｔｉｎｇ　Ｖｉｓｕａｌｉｚａｔｉｏｎ　ｗｉｔｈ　Ｌｅｖｅｌ　ｏｆ　Ｄｅｔａｉｌ　ａｔ　Ｍｕｌｔｉ－

Ｓｃａｌｅ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，２００２，１３（１０）：２０３７－２０４３．

（李军，景宁，孙茂印．多比例尺下细节层次可视化的实

现机制［Ｊ］．软件学报，２００２，１３（１０）：２０３７－２０４３．）

［２０］　ＧＯＮＧ　Ｊｕｎ，ＺＨＵ　Ｑｉｎｇ，ＺＨＡＮＧ　Ｈａｎｗｕ，ｅｔ　ａｌ．ＡｎＡｄａｐｔｉｖｅ　Ｃｏｎｔｒｏｌ　Ｍｅｔｈｏｄ　ｏｆ　ＬｏＤｓ　ｆｏｒ　３ＤＳｃｅｎｅ　Ｂａｓｅｄ　ｏｎ

Ｒ－ｔｒｅｅ　Ｉｎｄｅｘ［Ｊ］．Ａｃｔａ　Ｇｅｏｄａｅｔｉｃａ　ｅｔ　Ｃａｒｔｏｇｒａｐｈｉｃａ　Ｓｉｎｉｃａ，

２０１１，４０（４）：５３１－５３４．（龚俊，朱庆，章汉武，等．基于Ｒ

树索引的三维场景细节层次自适应控制方法［Ｊ］．测绘学

报，２０１１，４０（４）：５３１－５３４．）

（责任编辑：雷秀丽）

收稿日期：２０１１－０４－１１

修回日期：２０１２－０２－２９

第一作者简介：龚俊（１９７８—），博士，副教授，从事多维地理信息系统和三维激光点云数据处理的理论与应用研究。

Ｆｉｒｓｔ　ａｕｔｈｏｒ：ＧＯＮＧ　Ｊｕｎ（１９７８—），ＰｈＤ，ａｓｓｏｃｉａｔｅ　ｐｒｏ－ｆｅｓｓｏｒ，ｍａｊｏｒｓ　ｉｎ　ｍｕｌｔｉ－ｄｉｍｅｎｓｉｏｎ　ＧＩＳ　ａｎｄ　ＬｉＤＡＲ．

Ｅ－ｍａｉｌ：ｇｏｎｇｊｕｎｂｏｘ＠ｇ

櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂櫂

ｍａｉｌ．ｃｏｍ

（上接第５９６页）

［１０］　ＭＥＥＲ　Ｆ　ＶＡＮ　ＤＥＲ．Ｔｈｅ　Ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　Ｓｐｅｃｔｒａｌ　Ｓｉｍｉ－ｌａｒｉｔｙ　Ｍｅａｓｕｒｅｓ　ｆｏｒ　ｔｈｅ　Ａｎａｌｙｓｉｓ　ｏｆ　Ｈｙｐｅｒｓｐｅｃｔｒａｌ　Ｉｍａｇｅｒｙ

［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ａｐｐｌｉｅｄ　Ｅａｒｔｈ　Ｏｂｓｅｒｖａｔｉｏｎ

ａｎｄ　Ｇｅｏｉｎｆｏｒｍａｔｉｏｎ，２００６，８（１）：３－１７．

［１１］　ＣＡＩ　Ｘｕｅｌｉａｎｇ，ＣＵＩ　Ｙｕａｎｌａｉ．Ｃｒｏｐ　Ｐｌａｎｔｉｎｇ　ＳｔｒｕｃｔｕｒｅＥｘｔｒａｃｔｉｏｎ　ｉｎ　Ｉｒｒｉｇａｔｅｄ　Ａｒｅａｓ　ｆｒｏｍ　Ｍｕｌｔｉ－ｓｅｎｓｏｒ　ａｎｄ

Ｍｕｌｔｉ－ｔｅｍｐｏｒａｌ　Ｒｅｍｏｔｅ　Ｓｅｎｓｉｎｇ　Ｄａｔａ［Ｊ］．Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｆ

ｔｈｅ　Ｃｈｉｎｅｓｅ　Ｓｏｃｉｅｔｙ　ｏｆ　Ａｇｒｉｃｕｌｔｕｒａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００９，

２５（８）：１２４－１３０．（蔡学良，崔远来．基于异源多时相遥感

数据提取灌区作物种植结构［Ｊ］．农业工程学报，２００９，

２５（８）：１２４－１３０．）

［１２］　ＤＥＮＮＩＳＯＮ　Ｐ　Ｅ，ＨＡＬＬＩＧＡＮ　Ｋ　Ｑ，ＲＯＢＥＲＴＳ　Ｄ　Ａ．ＡＣｏｍｐａｒｉｓｏｎ　ｏｆ　Ｅｒｒｏｒ　Ｍｅｔｒｉｃｓ　ａｎｄ　Ｃｏｎｓｔｒａｉｎｔｓ　ｆｏｒ　Ｍｕｌｔｉｐｌｅ

Ｅｎｄｍｅｍｂｅｒ　Ｓｐｅｃｔｒａｌ　Ｍｉｘｔｕｒｅ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｓｐｅｃｔｒａｌ　Ａｎｇｌｅ

Ｍａｐｐｅｒ［Ｊ］．Ｒｅｍｏｔｅ　Ｓｅｎｓｉｎｇ　ｏｆ　Ｅｎｖｉｒｏｎｍｅｎｔ，２００４，９３（３）：３５９－３６７．

［１３］　ＴＨＥＮＫＡＢＡＩＬ　Ｐ　Ｓ，ＧＡＮＧＡＤＨＡＲＡＲＡＯ　Ｐ，ＢＩＧＧＳＴ，ｅｔ　ａｌ．Ｓｐｅｃｔｒａｌ　Ｍａｔｃｈｉｎｇ　Ｔｅｃｈｎｉｑｕｅｓ　ｔｏ　Ｄｅｔｅｒｍｉｎｅ

Ｈｉｓｔｏｒｉｃａｌ　Ｌａｎｄ　Ｕｓｅ／Ｌａｎｄ　Ｃｏｖｅｒ（ＬＵＬＣ）ａｎｄ　Ｉｒｒｉｇａｔｅｄ

Ａｒｅａｓ　Ｕｓｉｎｇ　Ｔｉｍｅ－ｓｅｒｉｅｓ　ＡＶＨＲＲ　Ｐａｔｈｆｉｎｄｅｒ　Ｄａｔａｓｅｔｓ　ｉｎ

ｔｈｅ　Ｋｒｉｓｈｎａ　Ｒｉｖｅｒ　Ｂａｓｉｎ，Ｉｎｄｉａ［Ｊ］．Ｐｈｏｔｏｇｒａｍｍｅｔｒｉｃ

Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｒｅｍｏｔｅ　Ｓｅｎｓｉｎｇ，２００７，７３（９）：１０２９－１０４０．［１４］　ＭＥＥＲ　Ｆ　ＶＡＮ　ＤＥＲ．Ｓｐｅｃｔｒａｌ　Ｍａｔｃｈｉｎｇ　Ｕｓｉｎｇ　ＰｉｘｅｌＣｒｏｓｓ－ｃｏｒｒｅｌｏｇｒａｍｓ　ｆｏｒ　ｔｈｅ　Ａｎａｌｙｓｉｓ　ｏｆ　ＬＡＮＤＳＡＴ　ＴＭ

Ｄａｔａ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ａｐｐｌｉｅｄ　Ｅａｒｔｈ　Ｏｂｓｅｒ－

ｖａｔｉｏｎ　ａｎｄ　Ｇｅｏｉｎｆｏｒｍａｔｉｏｎ，２００１，３（２）：１９７－２０２．

［１５］　ＳＣＨＯＬＫＯＰＦ　Ｂ，ＭＩＫＡ　Ｓ，ＢＵＲＧＥＳ　Ｃ　Ｊ　Ｃ，ｅｔ　ａｌ．ＩｎｐｕｔＳｐａｃｅ　Ｖｅｒｓｕｓ　Ｆｅａｔｕｒｅ　Ｓｐａｃｅ　ｉｎ　Ｋｅｒｎｅｌ－ｂａｓｅｄ　Ｍｅｔｈｏｄｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋｓ．１９９９，１０（５）：１０００－１０１７．

［１６］　ＧＥＮＴＯＮ　Ｍ　Ｇ．Ｃｌａｓｓｅｓ　ｏｆ　Ｋｅｒｎｅｌｓ　ｆｏｒ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ：Ａ　Ｓｔａｔｉｓｔｉｃｓ　Ｐｅｒｓｐｅｃｔｉｖｅ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ

Ｒｅｓｅａｒｃｈ，２００２，２（２）：２９９－３１２．

［１７］　ＸＩＡ　Ｌｉｅｇａｎｇ．Ｓｔｕｄｙ　ｏｎ　Ａｕｔｏｍａｔｉｃ　Ｃｌａｓｓｉｆｉｃａｔｉｏｎ　Ｍｅｔｈｏｄｆｏｒ　Ｒｅｍｏｔｅｌｙ　Ｓｅｎｓｅｄ　Ｉｍａｇｅｒｙ　ｂｙ　Ｉｎｃｏｒｐｏｒａｔｉｎｇ　Ｓｐａｔｉａｌ－

Ｓｐｅｃｔｒａｌ　Ｆｅａｔｕｒｅｓ［Ｄ］．Ｈａｎｇｚｈｏｕ：Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ

Ｔｅｃｈｎｏｌｏｇｙ，２０１１：３６－３９．（夏列钢．耦合“图—谱”特征

的遥感影像自动分类方法研究［Ｄ］．杭州：浙江工业大学，

２０１１：３６－３９．）

［１８］　ＺＨＡＮＧ　Ｌｉ，ＺＨＯＵ　Ｗｅｉｄａ，ＪＩＡＯ　Ｌｉｃｈｅｎｇ．Ｋｅｒｎｅｌ　Ｃｌｕｓ－ｔｅｒｉｎｇ　Ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｃｈｉｎｅｓｅ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ，

２００２，２５（６）：５８７－５９０．（张莉，周伟达，焦李成．核聚类算

法［Ｊ］．计算机学报，２００２，２５（６）：５８７－５９０．）

［１９］　ＷＵ　Ｋ，ＹＡＮＧ　Ｍ．Ａｌｔｅｒｎａｔｉｖｅ　ｃ－ｍｅａｎｓ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｌｇｏ－ｒｉｔｈｍｓ［Ｊ］．Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，２００２，３５（１０）：

２２６７－２２７８．