八叉树与三维R*树集成的激光点云数据存储结构

针对海量激光点云数据组织与管理困难等问题,结合八叉树在三维空间上的快速收敛能力以及三维R^*树对不规则分布的多维点数据性能稳定的优势,提出了一种八叉树与三维R^*树集成的空间混合索引结构—3DOR^*树。首先,通过对激光点云数据进行八叉树划分;然后,对八叉树叶子节点构建三维R^*树,进而实现3DOR^*树索引结构的构建;最后,对激光点云数据进行特征分析,构建基于3DOR^*树的激光点云数据存储结构,实现基于3DOR^*树的激光点云存储与管理。本文以江西理工大学图书馆激光点云数据为例,进行实验对比分析,证明了基于3DOR^*树的激光点云数据存储结构比三维R^*树、八叉树与三维R树混合树等其他树形结构,具有高效的空间存储与查询等优势,可应用于海量激光点云数据存储、管理与分析应用。     

MFSTR-tree：面向Argo海洋浮标的时空数据索引

针对Argo海洋浮标数据的准实时性、海量性、时空异变性等特点和多种查询应用需求,分析了当前时空索引方法的优势与不足,提出了一种多频率STR-tree索引与格网索引的混合索引结构MFSTR-tree。该方法在首先轨迹束层利用动态轨迹束作为叶节点生成STR-tree结构,将STR-tree索引结构灵活、数据冗余少的优势进一步扩大;接着通过轨迹束的多种频率在采样点层构建格网索引,实现在查询效率上的提升;同时给出了该结构插入算法和查询算法的具体描述。本文以中国Argo实时资料中心提供的2015年海洋浮标数据为例,将该方法与HR-tree和STR-tree方法进行了构建效率和查询效率的对比实验,结果表明该方法在保证了构建存储效率和时间效率的同时,有效改善了原有STR-tree应用于Argo数据中的查询效率问题。     

基于 HBase的海量地理空间数据的空间索引模型构建与优化

传统关系型数据库在海量地理空间数据的存储与管理上面临着高并发访问规模限制、数据库扩展能力不 足等困难.非关系数据库如 HBase等以其强大的扩展能力与计算能力为该问题提供了新的思·与方法.空间索 引模型和分布式存储模式设计是影响基于非关系数据库的海量地理空间数据的存储与查询效率的关键因素.对 当前主要基于 HBase的索引模型和空间数据存储设计进行了研究,设计了基于行政区划编码与矢量要素编码结 合的 RowKey(行键),使空间数据在 HBase存储中得到很好的聚类效果,并针对要素重叠与边界划分等问题提出 了一种基于四叉树ＧR树的改进的空间索引模型.该模型基于四叉树结构将空间数据划分为多个子网格,为?一个 子网格构建 R树索引,利用 Hilbert(希尔伯特)曲线对子网格进行编码,并设计了基于 MapReduce的并行化索引构 建算法和相应的空间查询算法.经实验测试,该存储设计和空间索引模型具有较好的查询效率.      

一种异构多核架构快速查询多边形图层间空间关系的方法

目前,空间关系查询中常用的Plane Sweep 算法是一种串行方法,而关于多核CPU的并行查询算法,在面对海量数据查询时,由于CPU核心数及线程数量的限制,其难以满足查询效率需求。针对该问题,本文提出了一种全新的异构多核架构多边形图层间空间关系查询的并行算法。首先,利用STR 树索引过滤不相交的多边形;然后,对过滤后多边形的线段构建四叉树索引,利用CPU+GPU架构并行计算线段的相交以判断多边形环间的拓扑关系;再根据环间的拓扑关系计算多边形间的维度扩展九交模型(DE-9IM)参数值,据此确定多边形间的空间关系;最后,通过实验验证了该算法的准确性和高效性。实验表明,本算法能有效缩短大数据量的空间查询时间。在实验中逐渐增加目标数据集和源数据集多边形的数量,当两数据集都为50 000 个多边形时,以包含关系为例,相比于ArcGIS,本文提出的算法可达到2 倍的加速比。     

方向关系在空间查询中的应用研究

空间方向关系作为空间查询的重要选取条件,在地理信息系统等许多领域得到了广泛的应用。本文利用锥形模型和四叉树索引提出一种基于方向关系的空间查询算法,并在其基础上结合空间距离关系,实现了基于方向和距离关系的复合空间查询。实验表明,提出的算法能够对不同几何类型的空间数据进行准确、高效的查询,较好地满足了实际应用的需求。     

基于格网化邻域查询的海上船舶救援搜索方法

海洋渔业是高风险行业,各类海洋灾害频繁发生,海上航行、作业环境复杂,因此,海上快速救援对保护渔民的生命财产安全具有重要意义。本文基于空间剖分的格网化编码,提出一种根据有效救援距离和失事船舶位置进行邻域搜索以查找失事船只相邻和最邻近可供救援的船只的方法,其中有效救援距离通过救援船舶的类型和航速来设定,根据有效救援距离设置不同的编码搜索长度。本文将模拟实验区域设定为我国东海海域,随机生成1×10⁴个船位点,在时间检索效率和内存占用两方面,实验结果表明,与传统的船舶间距离的计算方法相比,基于格网化邻域搜索的查询方法编码后船位数据较编码转换前船位数据占用内存空间减少56.47%,同时,编码后检索运算的用户时间是编码前用户时间的17.67%,因此,基于格网化邻域搜索的查询方法占用内存小,且运算效率较高,能够有效提升对遇险船舶邻域救援船只的查询效率。     

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

三维点云是三维GIS重要的数据来源,也是三维GIS对地学空间对象、现象进行表达、描述以及建模的重要手段。点云数据的高效组织是对其进行各种分析处理的基础,为此本文在对三维坐标点按照一定的规则进行排序的基础上,采用规则空间八叉树与平衡二叉树相结合的嵌套复合结构进行组织,大大加速了三维点数据基于坐标的查询检索,为海量点云数据的进一步分析操作奠定了基础。最后,文中对该复合组织结构进行了内外存相统一的设计与实现,并验证了该方法的正确性及有效性。     

面向地形数据的点云简化算法

针对地形点云数据量大、表面特征复杂多样等特点,提出面向地形数据的点云简化算法。基于K-D Tree搜索各点K邻域,构建点集空间拓扑关系|应用移动最小二乘法计算各点曲率,通过曲率的划分,在平缓区域按距离进行简化,保证整个算法的效率|在突变区域根据曲率简化,确保曲率变化大的关键特征信息不丢失,从而实现点云数据的简化。利用基于熵理论的定量评价方法,通过实例验证该方法的可行性和普适性。     

空间数据库中的三种查询优化方法

查询优化是数据库系统设计和实现所采用的一项重要技术,也是影响数据库系统性能的一个重要因素.文章对最新的几种空间数据库的查询优化方法如基于线性四叉树的快速邻域查询算法,大规模高维向量空间的快速范围查询法和基于柱子群算法的数据库查询优化,进行了对比概述,总结了其优缺点.     

基于微分形态学断面的机载LiDAR数据滤波新方法

提出一种基于微分形态学断面的机载LiDAR点云数据滤波新方法。该方法由点云数据构建规则格网,去除粗差点;对构建的每一个格网进行多尺度分解,获取初始地面点及地物点;分别利用曲面逼近及微分形态学断面构建DTM（digital terrain model）,通过阈值函数判别二者之间的残差,确定最终地面点。使用国际摄影测量与遥感学会提供的测试数据进行实验,并与8种经典滤波算法比较分析,表明该方法能够有效去除地物点和保留地面点,并降低总误差。     

融合点、体素和对象特征的多基元点云分类

单一基元分类方法难以全面描述复杂的点云场景,采用多基元进行分类成为一种趋势,提出了一种融合点、体素和对象特征的点云分类方法。主要包括4个方面:(1)分别确定各层面分类基元,点基元方面采用最优邻域方法,体素基元方面基于八叉树方法进行体素划分,对象基元方面使用改进的多要素分割方法进行点云分割;(2)提取各基元分类特征,首先提取点基元分类特征并进行局部线性约束编码(Locality-constrained Linear Coding, LLC),然后以此为基础提取体素基元和对象基元的潜在狄利克雷分布特征(Latent Dirichlet Allocation, LDA)和最大池化特征(Max Pooling, MP);(3)降低分类特征维度,利用随机森林变量重要性算法对分类特征进行筛选与降维;(4)进行点云分类,使用随机森林算法实现点云分类。采用3种不同类型的点云数据进行试验,结果表明融合3种基元特征的分类精度相比于点基元分类分别提升了1.43%、7.02%和2.48%,分类特征降维可以有效降低特征冗余度,分类器分类时间减少约70%;通过与其他算法的对比,新算法分类精度更优,且适用于多种场景...     

基于无人机传感器数据与词袋模型的点云自动化分类

激光点云分类是Li DAR数据应用的关键步骤和重要研究课题。针对Li DAR点云数据识别率低的问题,以体素化的点云为研究对象,提出了一种基于词袋模型的城区机载Li DAR点云数据分类方法。考虑到点云数据缺乏纹理信息,文中综合分析了点云数据和影像数据的特点,以点为单位提取描述点云的几何特征和影像特征分类特征;以体素为单位分割点云数据,并以体素为基础构建描述场景信息的词袋模型;最后基于随机分类器完成场景的分类。文中以ISPRS提供的Vaihingen数据作为实验数据。实验结果表明,本文提出的模型能有效地改善点云的分类质量,分类正确率能达到93%以上。     

一种地形自适应的机载LiDAR点云正则化TPS滤波方法

随着机载激光雷达成像技术（LiDAR）的不断发展,激光点云数据处理的相关研究也在不断深入。点云滤波是机载激光雷达点云数据处理的重要环节之一。针对多数经典滤波方法在复杂地形和地物条件下的滤波效果不够理想的现状,提出一种新的基于相对变异系数的地形自适应正则化薄板样条插值点云滤波方法。采用二维区域增长获取初始插值参考点后,基于线特征约束对参考点进行优化,去除部分低可靠性参考点以得到较准确、分布离散均匀的初始插值参考点集合,在此基础上通过正则化薄板样条插值方式来拟合地形点与地物点之间的滤波分类面,完成对机载激光点云的高精度自适应滤波。对比实验结果表明,本文的地形自适应滤波方法在2组实验数据的总体错误率分别达到4.14%和4.17%,在错误率和多地形综合表现等方面具有优势,且滤波运算效率在目前主流的滤波算法中处于较高水平。另外,实验结果验证了地形自适应滤波方法在斜坡、山脊等起伏较多的复杂地形与包含植被和建筑物的混合地形等处的点云滤波结果具有较好的准确性。     

基于可视范围的图像检索方法

图像是视觉所及环境的自然再现,具有表达直观、内容丰富的特性,其已成为GIS空间数据采集与应用中一种重要的可视数据源。随着硬件终端的高速发展,集成的传感器愈加丰富,多源传感器信息融合已成为移动GIS数据釆集的发展趋势。针对移动终端获取方位角偏差问题,本文重点阐述了基于移动终端的重力传感器与磁力传感器获取镜头拍摄朝向的算法,并基于EXIF图像格式实现了图像元数据、定位信息、方位信息一体化采集生成可定位图像。针对现有可定位图像以点代面建模方式的不足,本文以镜头视野范围AOV（Angle of View）模型为基础,提出了以图像元数据、位置信息以及方位信息构建图像可视域的方法,并采用多级网格方式对图像可视域面状特征建立空间索引,实现基于可视域的图像检索。在此基础上,针对福建省野外遥感核查采集的8022幅可定位图像,采用点建模及可视域建模2种方式建立检索图像集。从检索速度、检索结果2个方面进行对比分析,表明基于可视域图像检索方法不仅能检索出拍摄位置在检索区域内的图像,还可检索出拍摄位置在检索区域外但实际拍摄场景在检索范围内的图像。同时,通过多级空间网格索引可提升6.22-8.64倍检索速度。     

利用MapReduce的异常轨迹检测并行算法

异常轨迹检测是移动对象数据挖掘的一个重要研究领域。TRAOD(TRAjectory Outlier Dectection Algorithm)算法是一种经典的异常轨迹检测算法,但它对于海量轨迹数据的异常检测效率低。为提高海量轨迹数据集的异常检测效率,本文提出了一种利用MapReduce 的异常轨迹检测并行算法(Parallel algorithm for TRAjectory Outlier Detection, PTRAOD),并在此基础上提出了网格索引的异常轨迹检测并行算法(Grid-based Parallel algorithmfor TRAjectory Outlier Dectection, GPTRAOD)。GPTRAOD算法在PTRAOD算法的基础上,利用网格索引实现区域查询,进一步提高算法效率。将PTRAOD算法和GPTRAOD算法在Hadoop 平台上加以实现,结果表明:本文提出的2 个并行检测算法,能实现异常轨迹的检测;GPTRAOD算法的效率优于PTRAOD算法;GPTRAOD算法具有较高的可扩展性和较好的加速比。     

基于虚拟特征点的三维激光点云粗配准算法

在地面三维激光点云特征提取的过程中,由于三维点云数据采集仪器、采集方法及后期处理等因素影响,依靠传统的基于曲率、法线等几何特征及统计学算法提取出的点云特征数量较多且存在较大误差,若使用其直接作为特征点数据进行点云粗配准,很难提高点云粗配准的精度及速度。因此,本文在对点云数据实际空间分布结构分析的基础上,结合特征点提取算法、法向一致化算法、PCA（Principal Component Analysis）方法及特征点聚类等方法,提出了一种三维激光点云数据虚拟特征点拟合算法。该算法生成的虚拟特征点是由点云实际的特征点拟合得到,或是由位于被测物特征线上的特征点拟合生成的特征线计算得到,该虚拟特征点并不是扫描对象上实际存在的激光反射脚点。通过实验验证,虚拟特征点拟合算法可以较准确地拟合出由于设备及操作方法等原因而未被采集到的建筑物边角点数据,得到的虚拟特征点数据较实际特征点数据具有更少的数据量及更高的精度,使用拟合得到的虚拟特征点可以减少粗配准算法的计算量,提高粗配准算法的计算效率并能获得更精确及可靠的初始配准变换参数。     

基于加权约束的单体建筑物点云表面重建算法

建筑物点云表面重建在高精度城市测绘、虚拟现实等领域有十分广泛的应用前景。由于建筑物的几何形态多变,重建算法普遍存在计算速率慢、拟合精度低和模型结构不完整的问题。为此,本文以单体建筑物为研究对象,提出基于加权约束的单体建筑物点云表面重建算法,在表面初始化过程中充分考虑数据对结构拟合的贡献。在此基础上,构建基于正则集的单体建筑物表面重建算法,实现建筑物拟合过程中的加权拟合误差、近邻结构平滑的同步优化。针对多类建筑物三维点云的实验结果表明,相比传统的建筑物重建策略,本文的加权约束方法可根据不同类型的点云数据设计自适应权重,并选择模型拟合中最优的权重函数,在高噪声、低精度点云数据下能得到更高精度的单体建筑物表面模型。     

基于等高线空间关系的鞍部点提取方法

鞍部点是反映地表形态起伏变化的重要地形特征点之一,准确地提取鞍部点有利于地形的空间关系和结构特征分析。现有的鞍部点提取方法通常是直接基于规则格网DEM数据,无法顾及鞍部点与周围地形的空间拓扑关系和复杂地形对其的影响,不仅产生大量的伪鞍部点,而且忽略一些关键地区的鞍部点。本文根据鞍部点的地形形态特征,设计了一种基于等高线数据的鞍部点提取算法。该算法利用等高线闭合的特征,将等高线按照一定规则转成等高面数据,再利用等高面之间的相邻拓扑关系实现递归查找并自动提取鞍部点。实验结果显示:①鞍部点的数量和位置与等高距的大小显著相关,在一定尺度范围内,等高距越小,提取出鞍部点越多,位置精度也逐渐提高;②与基于规则格网DEM数据提取方法相比,该方法能更有效的过滤大量伪鞍部点,提高了鞍部点的提取精度,同时也降低了鞍部点提取算法的复杂度;与基于等高线的增量缓冲方法(Incremental Buffering Algorithm)相比,本文的方法能有效提高鞍部点提取的完整性,更适用于本文DEM的尺度即5 m DEM数据。