一种基于线性KD树的点云数据组织方法

常规KD树索引对大规模点云数据进行组织和管理时,指针的存储往往耗费大量的内存空间。本文结合线性索引的编码思想,提出了一种线性KD树索引的构建和查找方法,存储点云时可以充分利用内存空间,通过自然数编码表示结点间的关系,并给出了线性KD树的构建和邻域查找方法。最后通过与开源最临近搜索库ANN库进行对比试验,证明本文的线性KD树索引可以明显减少点云组织时的内存消耗,并与基于指针的ANN库具有相近的临近查找效率。

基于八叉树与KD树索引的点云配准方法

针对点云配准算法中KD树多维查询效率较低的问题,提出一种基于八叉树和KD树多层索引结构的点云配准方法。首先为模型点云数据建立八叉树全局索引,然后在八叉树叶子结点构建局部数据的KD树索引。对传统的ICP点云配准算法进行改进,通过叶子结点的全局索引值快速定位局部点云数据块,利用局部KD树索引加快最近点的搜索,计算最近点时利用欧氏距离阈值、点对距离差值和法向量阈值剔除部分噪声点。实验表明,改进算法提高了点云配准的效率和精度。

KD树索引策略下紧支撑径向基函数的点云建模

采用紧支撑径向基函数(Compactly Supported Radial Basis Function,CSRBF)对点云进行建模和可视化表达会因穷举搜索问题导致计算机内存溢出,最终引起建模和可视化失败。KD树索引具有快速搜索点的优点且避免了穷举搜索问题,将KD树索引和CSRBF插值模型相结合,提出KD树搜索策略下的CSRBF点云建模与表达方法。建立点云数据的KD树索引,采用CSRBF构建点云的隐式曲面函数模型,通过Marching Cubes算法对建好的模型进行有效的可视化表达。采用经典的兔子点云进行实验验证,结果表明KD树索引搜索策略下CSRBF的点云建模与表达方案可行。

基于重叠区域的高性能近似kD树算法

kD树是近邻搜索中应用最广泛的算法之一,针对其性能随着空间维度的增加而迅速降低的问题,提出一种可应用到高维空间的kD树搜索算法——okD树.在该okD树的创建过程中,左右子结点之间保留重叠区域,重叠区域不参与后续的划分而是直接传递到子结点;在搜索过程中,对于存在重叠区域的子结点不进行回溯,以提高okD树的搜索效率,不进行回溯的子结点中包含的重叠区域扩大了搜索范围,从而提高了搜索精度.实验结果表明okD树算法的性能优于当前主流的近似kD树算法.

基于KD树的露天矿采场示坡线自动生成方法

为了提高露天矿采场示坡线的绘制效率和精度,根据露天矿采场数据的特点,提出示坡线自动绘制解决方案:将采场的线状数据按给定步距分解为空间散点,并采用KD树对空间散点进行组织和索引,不需要先验地知道散点间的拓扑关系便可以快速确定任意散点的邻域点集,根据示坡线绘制的基本原则和方法,实现任意散点处的示坡线绘制。该方法用VC++.NET编程得以实现,实验结果表明:该方法结果正确、速度较快,保证了示坡线符号均匀、美观。此外,该思想还可应用于等高线地形。

KDT树:一种多维空间数据索引结构

通过扩展KD树索引结构,提出了一种新的多维空间数据索引结构——KDT树,给出了数据结构和算法描述,并通过与当前流行的空间数据索引结构——R树的对比,对其性能进行了测试与评估。实验表明,作为一种主存索引结构,KDT树在时间效率方面明显优于R树,并且此种优势随着索引记录数量的增多而越加明显。此外,KDT树亦能较好地解决常规KD树在索引占据一定空间范围的空间对象(如:线、面、体等)时存在的问题。

基于KD树的点云数据自适应屏幕精度高效显示方法

海量激光点云数据的快速显示是目前一个技术瓶颈。本文提出一种基于KD树的点云数据自适应屏幕精度的高效显示方法,采用类似LOD的技术将点云进行KD树的组织,并在KD树节点上引入屏幕精度的概念,在点云数据显示时,计算KD树节点在屏幕上的投影范围,进而决定其是否显示点云细节。试验证明,该算法在显示大规模点云数据时,由于通过KD树自适应屏幕精度调度点云数据使绘制点的数据量大大减少,从而大大加快了点云的显示速度。

基于KD树最优投影划分的k匿名算法

针对现有数据发布隐私保护保护算法中的“局部最优”划分问题,提出了一种基于KD树最优投影划分的k匿名算法.首先,在全局范围内对每一个属性维度进行遍历,根据投影距离方差值衡量每个维度的离散度,并确定最优维度;然后,在最优属性维度上,计算其划分系数值,并确定最优划分点.进一步引入一种改进的KD树结构,与传统的KD树结点是一个数据点不同,新设计的KD树中的每个结点均是一个集合.用经过划分点并垂直于最优维度的超平面将一个结点分成两部分,分别作为其左、右孩子结点.最后通过理论分析证明了本文算法的正确性,用实验比较和验证了算法的性能,实验结果显示所提算法平均概化范围减小10%~22%,能够实现更优的划分和更好的数据集可用性.

基于KD树的射线跟踪法计算飞行器RCS

利用几何光学射线跟踪法对飞行器整体目标雷达散射截面(Radar cross section,RCS)进行估算,假设入射波为高频平面波,传播中符合几何光学定律,将入射波划分为平行入射线进行跟踪并进行口径积分。为减少射线与大型目标表面的求交计算次数,应用了KD树方法的基本原理,将飞行器目标表面划分多层子包围盒,设计了射线与子包围盒及面元遍历求交算法。应用文中方法计算了一种新型无人飞行器的RCS,计算结果与传统的RCS高频估算方法(PO方法)得到的结果以及实测结果进行比对。结果表明,文中方法较传统PO方法更接近实测结果,在飞行器RCS预估方面具有一定的应用价值。

基于KD树和混沌蜉蝣优化的并行谱聚类算法

针对大数据环境下并行谱聚类算法存在的节点负载不均衡、冗余计算、矩阵相乘时间开销大以及初始簇中心敏感等问题,提出了基于KD(k-dimension)树和混沌蜉蝣优化算法的并行谱聚类算法(PSC-MO)。首先,提出基于采样的KD-tree数据分区策略(DPS)划分数据,保证了节点间负载均衡;其次,在构建稀疏相似矩阵过程中,提出优化的分区分配策略(OPA)和基于三角不等式的KD树剪枝策略以进行跨分区的t近邻搜索,避免了过多的冗余计算;然后,提出正规化定理,通过元素对应相乘的方式代替矩阵相乘以优化Laplacian矩阵正规化过程,有效地减少了时间开销;最后,提出混沌蜉蝣优化算法(CMO),得到最佳位置作为初始簇中心后进行k-means并行聚类,解决了算法对初始簇中心敏感的问题。实验表明,PSC-MO算法不但具有良好的聚类效果,而且在大规模数据集上表现出了良好的数据和系统可扩展性。

一个新的线索KD树并行算法

KD树是三维场景渲染中常用的空间加速算法。由于SIMD计算平台不支持递归操作,导致KD树在GPU上的应用受到限制,因此提出了一个新的基于SIMD架构的并行KD树算法。通过创建时对KD树线索化,不仅省去堆栈使用,且因无需回溯到根节点而减少大量无效遍历操作,实现了基于GPU的高效并行加速。实验结果表明,线索KD树算法每秒计算的光线数与传统算法相比,提高3~8倍不等,最终显著提高光线跟踪渲染速度。

基于kd树的多维索引在数据库中的运用

该文突破在数据库查询中建立传统索引进行数据的查询,而是针对微型数据库引擎的设计中要实现的嵌套查询和多表连接查询引进了kd树,kd树在B+树的基础上进行了改进,从而来加快查询速度。该文介绍了kd树的结构、kd树的操作以及其实现的查询。

基于KD树和CDT的露天矿三维建模

为了实现露天矿坑快速而准确的三维建模,以露天矿坑坡顶线、坡底线、道路边界线以及线上的点作为约束边线和离散点来进行约束Delaunay三角剖分(CDT)建立露天矿坑模型。对于各个离散点,利用KD树进行组织和索引,从而快速地确定各个离散点间的拓扑关系,对CDT后的三角网格进行局部修正,从而使露天矿坑模型更加准确美观。该方法成功在蓝光平台上实现,实验结果表明:利用该方法可以快速、准确地实现露天矿坑的三维建模。总之,这种建模方式更加方便、快捷,有利于离散点的动态增删和离散点与约束边间关系的处理。

一种基于KD树子样的自动聚类方法

基于进化算法的自动聚类方法具有搜索目标函数全局最优和自动发现聚类数的优点,同时也存在时间代价过高的缺陷。本文提出一种基于KD树子样的自动聚类方法,该方法使用KD树对样本空间进行分割,并在各子空间中随机取样形成KD树子样,然后在子样中自动聚类,最后运用K-Means在整个样本集中优化子样中的聚类结果。本文方法能够有效避免随机子样分布有偏的缺陷,即使比例很小的子样也能获得较好的聚类效果。仿真结果表明,本文方法能够保证聚类效果没有明显下降的情况下,显著缩短进化算法自动聚类的时间。

VDOD:一种基于KD树的分布式离群点检测算法

针对大数据的数据量大、维数高的特征,论文提出了一种新型的分布式离群点检测算法-VDOD。在数据预处理阶段,提出了基于方差的数据划分方法,划分过程中建立KD树,通过KD树将数据均匀地分配到各个计算节点;在离群点检测阶段,通过R树进行批量过滤。最后,基于真实数据集和人工数据集验证了VDOD算法的有效性。实验结果表明,相对于现有算法,文中算法可以显著提高计算效率并大幅降低网络开销。

基于KD树和KNN的高校学生异常状态预警算法研究

高校学生管理应开展经常性、预防性工作,将问题发生控制在源头。利用KD树存储结构优化KNN算法,解决KNN在k邻近结点搜索上的效率问题,将算法运用于学生状态分类,提前预警异常状态,对学生管理工作水平和质量的提升具有重要的意义。

基于新SURF＿DAISY算法和反向验证随机kd树的图像配准

在SURF图像配准的基础上,用新型DAISY特征描述符替换了原SURF特征描述算子,用推荐的反向验证随机kd树实现特征匹配,进而提出了一种基于新SURF_DAISY算法和反向验证随机kd树的图像配准方法。结果表明,图像配准方法在运算时间和匹配正确率上相比于SURF图像配准方法均有所提高。

基于KD树子样的聚类初始化算法

在处理大数据集聚类初始化问题时,随机子样法是一种重要的数据约简操作。对随机取样的过程、特征及缺陷进行了分析,提出一种基于KD树子样的聚类初始化方法。该方法利用KD树将样本空间以递归方式细分成多个子空间,并分别在各子空间中随机取样形成KD树子样,有效避免了随机子样分布有偏的不足,使得子样中好的聚类初始点也能很好的表达整个数据集的聚类结构。仿真结果表明,该方法选择的聚类初始点更加接近期望的聚类中心,能获得更高的聚类精度。

基于KD树和NBS距离的颜色量化算法

针对经典K均值聚类算法需要事先给定量化数目和量化时间长的问题,提出一种基于KD树和NBS距离的颜色量化算法。首先用中位切割算法对原始图像进行初始量化,然后依据NBS距离与人类视觉对颜色差别的定量关系确定出初始聚类中心,最后利用KD树作为数据结构来运行K均值聚类算法从而实现彩色图像的快速量化。测试实验在不需要事先给定量化数目的前提下,获得了较好的量化结果和较快的量化速度,表明所提算法是可行有效的。

基于KD树的规则格网DEM插值技术

插值是规则格网DEM生产的重要环节。通常插值算法首先需要获取待插值点的若干邻域采样点，然后由邻域采样点通过某种内插算法获取待插值点的高程值。邻域采样点的快速获取和高精度的内插算法是点云插值的关键。本文针对当前密集匹配并滤波后生成的点云数据，围绕邻域点的快速获取，在分析传统栅格法索引的基础上，引入KD树实现了邻域点的快速获取，并通过反距离加权插值算法完成了DEM插值。试验结果表明，在保证邻域点检索正确率的前提下，基于KD树的索引效率更优。