海量点云Out-of-CoreR树构建及拓扑近邻查询

摘要

性能良好的R树空间索引与局部型面特征参考数据对于曲面重建具有极其重要的意义。目前主流的R树因构建参数单目标串行优化导致子树选取与结点分裂结果并不理想，当点云非均匀分布、k值过小时，k近邻点集作为局部参考数据并不能有效体现局部型面特征，且由于点云数据规模趋于海量，甚至超出主存容限，目前的R树构建及k近邻查询机制将无法使用。本文基于多目标优化改进R树中的子树选取与结点分裂算法，利用主元分析扩展搜索包围球对k近邻点集优化以获取拓扑近邻点集，并基于Out-of-Core策略，结合数据库SQLite实现R树索引Out-of-Core分级存储机制与拓扑近邻Out-of-Core查询机制。主要研究内容如下：
　　(1)提出R树形位多目标聚类构建算法，将子树选取视为多目标优化，其中将周长增量、重叠度增量优化指标作为决策向量，根据上溢结点子结点在各轴向的形位分布选取分裂轴，对候选分裂解以重叠度为指标进行聚类过滤，并将周长之和最小解作为结点分裂结果，从而避免了指标因单目标串行优化而导致 R树性能下降的情况，使得结点分布与数据分布更具一致性，R树性能有所提高。
　　(2)提出R树索引的Out-of-Core构建策略，将数据库SQLite与R树构建相结合实现索引结点存储于主存与数据点存储于辅存的分级存储机制，从而有效解决了因点云数据规模过大甚至超出主存限制的情况。
　　(3)提出主元分析导向自适应扩展的拓扑近邻查询算法，利用过目标点的第二主元平面分割k近邻点集，根据小点集与近邻点集点数比例与预设阈值的大小确定是否扩展搜索包围球，使得每个目标点实现自适应拓扑近邻查询，从而有效提高查询效率，并设置搜索包围球半径的上限值，从而避免边界、棱边处点的无限查询与相邻曲面点的越界查询，使得获取的拓扑近邻点集能够有效体现局部型面特征。
　　(4)提出拓扑近邻的Out-of-Core查询策略，首先在主存中获取近邻叶结点，然后利用数据库 SQLite从辅存中将近邻叶结点包含的数据点读入主存，继而获取目标点的近邻点。对于空间近邻叶结点查询，以目标点与结点包围盒的最小距离、最小最大距离、最大距离为基准对索引结点制定各种剪枝策略以减少遍历结点个数，从而有效提高近邻叶结点的查询效率。对于近邻点集的查询，提出即用即查、用后即删的策略，使得空间查询时内存占用始终保持最小化。拓扑近邻的Out-of-Core查询策略不仅可适应于R树索引Out-of-Core分级存储机制，而且可有效减少空间近邻查询中内存的占用。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

内容提要

1.1 课题研究的背景及意义

1.2 索引构建及局部参考数据查询的研究现状

1.3 索引构建及局部参考数据查询的问题分析总结

1.4 本文主要研究内容

第二章 海量点云的R树形位多目标聚类Out-of-Core构建

内容提要

2.1 引言

2.2 多目标聚类选取子树

2.3 基于形位多目标聚类的结点分裂

2.4 海量散乱点云的Out-of-Core分级存储机制

2.5 R树构建实验及性能分析

2.6 本章小结

第三章 主元分析导向自适应扩展的拓扑近邻查询

内容提要

3.1 引言

3.2 k近邻点集

3.3 拓扑近邻查询的主元分析导向

3.4 自适应扩展的拓扑近邻查询

3.5 实验分析

3.6 本章小结

第四章 海量散乱点云的拓扑近邻Out-of-Core查询

内容提要

4.1 引言

4.2 Out-of-Core查询机制

4.3 k近邻Out-of-Core查询

4.4 拓扑近邻Out-of-Core查询

4.5 实验

4.6 本章小结

第五章 全文总结与展望

内容提要

5.1 总结

5.2 展望

参考文献

在读期间公开发表的论文

致谢