检索结果-南通市图书馆

基于自动终止准则改进的Kd-tree粒子近邻搜索研究

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

工程科学与技术 2023年

作者：张挺王宗锴林震寰郑相涵福州大学土木工程学院福州大学计算机与大数据学院

对于大规模运动模拟问题而言，近邻点的搜索效率将对整体的运算效率产生显著影响。本文基于关联性分析建立Kd-tree的最大深度dmax与粒子总数N的自适应关系式，提出了Kd-tree自动终止准则，即ATC-Kd-tree，同时还考虑了叶子节点大小阈值n... 详细信息

对于大规模运动模拟问题而言，近邻点的搜索效率将对整体的运算效率产生显著影响。本文基于关联性分析建立Kd-tree的最大深度dmax与粒子总数N的自适应关系式，提出了Kd-tree自动终止准则，即ATC-Kd-tree，同时还考虑了叶子节点大小阈值n0对近邻搜索效率的影响。实验表明ATC-Kd-tree具有更高的近邻搜索效率，适用性更强，可求解不同N值的近邻搜索问题，解决了粒子总数N发生改变时需要再次率定最大深度dmax的问题。同时，本文还提出了网格搜索法组合坐标下降法的两步参数优化算法GSCD法。通过二维阿米巴虫形状的参数优化实验发现，GSCD法可更为快速地率定ATC-Kd-tree的可变参数，其优化效率相比于网格搜索法最高提升了205%，相较于改进网格搜索法最高提升了90%。

关键词： Kd-tree 粒子近邻搜索自适应网格搜索法坐标下降法

基于Kd-tree与DBSCAN的水电机组状态监测数据清洗方法

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

中国农村水利水电 2023年

作者：谭志锋姬联涛荆岫岩王璞田海平国家电网有限公司国网湖南电科院中国电力科学研究院有限公司

针对水电机组状态监测数据量逐步增大，数据质量差的问题，提出了一种基于改进K维树（K- Dimensional tree，Kd-tree）与基于密度的空间聚类算法（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）的水电机组... 详细信息

针对水电机组状态监测数据量逐步增大，数据质量差的问题，提出了一种基于改进K维树（K- Dimensional tree，Kd-tree）与基于密度的空间聚类算法（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）的水电机组状态监测数据清洗方法，首先对输入数据建立Kd-tree，再使用DBSCAN在最近邻样本上扫描完成聚类，聚类结束以后会分离出噪声点，将噪声点去除即可完成对水电机组状态监测数据清洗。选取某水电站状态监测系统上导摆度数据1088条，再以相同时间间隔插入随机数据100条，通过算例与常规DBScan、K-means、OCSVM算法对比聚类性能与时间性能，本文所提出的方法识别正确率最高，为97.78%，消耗时间最少，为0.007732s，数据清洗效果最优，并可以大幅减少计算时间。

关键词： Kd-tree DBSCAN 水电机组状态监测数据清洗

Improved Data Stream Clustering Method: Incorporating Kd-tree for Typicality and Eccentricity-Based Approach

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Computers, Materials & Continua 2024年第2期78卷 2557-2573页

作者： Dayu Xu Jiaming Lu Xuyao Zhang Hongtao Zhang College of Mathematics and Computer Science Zhejiang A&F UniversityHangzhou311300China College of Economics and Management Zhejiang A&F UniversityHangzhou311300China

Data stream clustering is integral to contemporary big data applications.However,addressing the ongoing influx of data streams efficiently and accurately remains a primary challenge in current research.This paper aims to elevate the efficiency and precision of data stream clustering,leveraging the TEDA(Typicality and Eccentricity Data Analysis)algorithm as a foundation,we introduce improvements by integrating a nearest neighbor search algorithm to enhance both the efficiency and accuracy of the algorithm.The original TEDA algorithm,grounded in the concept of“Typicality and Eccentricity Data Analytics”,represents an evolving and recursive method that requires no prior knowledge.While the algorithm autonomously creates and merges clusters as new data arrives,its efficiency is significantly hindered by the need to traverse all existing clusters upon the arrival of further data.This work presents the NS-TEDA(Neighbor Search Based Typicality and Eccentricity Data Analysis)algorithm by incorporating a Kd-tree(K-Dimensional tree)algorithm integrated with the Scapegoat tree.Upon arrival,this ensures that new data points interact solely with clusters in very close proximity.This significantly enhances algorithm efficiency while preventing a single data point from joining too many clusters and mitigating the merging of clusters with high overlap to some extent.We apply the NS-TEDA algorithm to several well-known datasets,comparing its performance with other data stream clustering algorithms and the original TEDA algorithm.The results demonstrate that the proposed algorithm achieves higher accuracy,and its runtime exhibits almost linear dependence on the volume of data,making it more suitable for large-scale data stream analysis research.

关键词： Data stream clustering TEDA Kd-tree scapegoat tree

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

场景导向的Kd-tree点云滤波算法

激光杂志 2021年第11期42卷 74-78页

作者：赵浚壹马峻陈寿宏郭玲徐翠锋桂林电子科技大学电子工程与自动化学院广西桂林541004 广西自动检测技术与仪器重点实验室广西桂林541004

采集点云是三维重建过程中的关键步骤,在采集点云的过程中,不可避免地产生一些噪声及离群点。针对噪声及离群点的传统滤波算法主要依赖于概率学模型假设,然而由于环境的复杂性导致噪声及离群点的分布并不完全服从于假设的模型,从而传统... 详细信息

采集点云是三维重建过程中的关键步骤,在采集点云的过程中,不可避免地产生一些噪声及离群点。针对噪声及离群点的传统滤波算法主要依赖于概率学模型假设,然而由于环境的复杂性导致噪声及离群点的分布并不完全服从于假设的模型,从而传统的滤波算法不能达到良好的滤波效果。另外,传统滤波算法通常需要对样本逐个遍历,因此耗时较高。针对这些问题,针对特定场景的结构特点,提出了一种场景导向的kdtree(k-dimensional tree)点云滤波算法。首先对点云下采样后计算其重心,再设定搜索半径阈值,最后依据所计算得到的重心及搜索半径结合Kd-tree分割出场景结构并保留,从而达到滤波目的。实验结果表明,提出的算法不仅具有良好的滤波效果,而且在算法的处理速度方面,相较于传统的半径滤波算法、统计滤波算法分别提高了4.8倍、14.2倍。

关键词：点云滤波降噪离群点 Kd-tree 三维重建

启发式探查最佳分割平面的快速Kd-tree构建方法

在线全文

学校读者我要写书评

暂无评论

计算机学报 2009年第2期32卷 185-192页

作者：范文山王斌清华大学计算机科学与技术系北京100084 清华大学软件学院北京100084 信息系统安全教育部重点实验室北京100084 清华信息科学与技术国家实验室北京100084

在基于光线跟踪方法的真实感绘制中,Kd-tree是一种重要的加速结构.文章对Kd-tree的构建方法进行了研究,提出了一种基于分区(binning)算法的快速构建方法.首先,通过分析Kd-tree的成本函数,启发式地定位了当前节点的分割平面所在的子区间... 详细信息

在基于光线跟踪方法的真实感绘制中,Kd-tree是一种重要的加速结构.文章对Kd-tree的构建方法进行了研究,提出了一种基于分区(binning)算法的快速构建方法.首先,通过分析Kd-tree的成本函数,启发式地定位了当前节点的分割平面所在的子区间;其次,对探查到的子区间进行进一步的细化采样(sub-sampling),使得到的分割平面更好地逼近最优分割位置;同时,文章分析了现有方法在处理分割终止时存在的问题,提出了更加合理的分割终止条件.与以往方法相比,新方法用更小的计算成本生成了质量更好的Kd-tree,构建过程更加鲁棒.实验数据验证了文中方法的有效性.

关键词：光线跟踪 Kd-tree SAH 分区算法细化采样

虚拟场景的一种快速优化Kd-tree构造方法

在线全文

学校读者我要写书评

暂无评论

电子学报 2011年第8期39卷 1811-1817页

作者：过洁徐晓旸潘金贵南京大学计算机软件新技术国家重点实验室江苏南京210093

Kd-tree因其具有场景自适应划分、低存储消耗和快速遍历等优势成为使用最为广泛的加速结构.本文提出一种快速优化的Kd-tree构造方法,该方法通过分析场景的SAH函数,将模拟退火技术使用到最优分割平面搜索过程中加快搜索过程,从而加速kd-t... 详细信息

Kd-tree因其具有场景自适应划分、低存储消耗和快速遍历等优势成为使用最为广泛的加速结构.本文提出一种快速优化的Kd-tree构造方法,该方法通过分析场景的SAH函数,将模拟退火技术使用到最优分割平面搜索过程中加快搜索过程,从而加速Kd-tree的构造过程.实验表明,通过本文的方法可以在保证构造的Kd-tree的质量情况下有效加快构造速度.同时,本文实现了该方法的一个多核并行扩展,利用多核CPU的并行处理能力,进一步加快了Kd-tree的构造过程.

关键词：虚拟场景 Kd-tree 加速结构模拟退火并行计算

用于射线跟踪的Kd-tree并行构建算法研究

在线全文

学校读者我要写书评

暂无评论

用于射线跟踪的KD-Tree并行构建算法研究

作者：王康西安电子科技大学

学位级别：硕士

随着人们对实时射线追踪的要求越来越高,研究者们持续提出更高效的加速算法,设备厂商也在对硬件迭代升级。射线追踪算法本身具有天然的并行性,十分适合使用GPU进行并行加速。最初,射线追踪主要用于图像渲染,如今射线追踪被应用于电磁散... 详细信息

随着人们对实时射线追踪的要求越来越高,研究者们持续提出更高效的加速算法,设备厂商也在对硬件迭代升级。射线追踪算法本身具有天然的并行性,十分适合使用GPU进行并行加速。最初,射线追踪主要用于图像渲染,如今射线追踪被应用于电磁散射的仿真、声场仿真等各个领域。而Kd-tree是一种广泛用于射线追踪的加速结构,相对于其他结构,其对射线追踪有着较好的加速效果,但是其构建时间却较长,这一定程度上限制了 Kd-tree的应用。现有对Kd-tree的研究,大多只针对SAH算法部分进行加速,并不是全程用GPU加速。本文基于对前人构建Kd-tree算法的研究,提出了使用GPU进行全程加速计算的并行建树方案,使得Kd-tree的构建速度进一步提高。本文的主要创新点如下:一、提出了一种在GPU端进行面元指派的方法。针对现行建树方案将面元指派工作放到CPU端完成的情况,本文引入了并行求前缀和的思想,提出了一种在GPU端进行面元指派的并行方法,有效的减少了内存指派的时间,同时减少了 CPU与GPU之间传输的数据量。使用benchmark模型进行测试时,相对于在CPU端指派面元,在GPU端指派面元到子节点的总时间减少了50%以上。二、针对建树过程中重叠三角面元导致的内存增长问题,本文提出了一种预申请内存大小估计的方法。根据初始三角面元的数量预估最终三角面元数组长度,可保证在程序开始就申请到足够的内存空间。为合理利用申请的内存空间,提出了一种按子节点三角面元数量比例动态分配内存的方法,实现了对预申请内存的无冲突访问。引入了一种计算SAH值的优化算法,并结合归约算法,加速了最小SAH值的计算过程。在本文实验环境中,相比于串行算法,该方法计算最小SAH值的加速比达到了5.8 倍。三、在以上工作的基础上,针对递归建树造成CPU与GPU间频繁数据传输的问题,提出了一种基于广度优先构建Kd-tree的方法,该方法使用两个队列分别存储偶数层与奇数层的待剖分节点,并逐层进行建树,每层只往CPU端传输下一层每个待剖分节点内面元的数量。所有建树任务都在GPU上完成,CPU仅需要计算开启的线程数,显著减少了 CPU与GPU的数据交互频次,降低了由此带来的时间开销。实验结果表明:在不降低Kd-tree质量的情况下,本文所提出的GPU并行算法,在常见场景中有较快的建树速度。使用本文方法构建Kd-tree,相比传统串行算法,加速比可以达到4.1～7.9倍;相比基于空间树的构建方法,有1.2～1.3倍的加速比。

关键词：射线追踪 Kd-tree SAH GPU 并行加速

全流水线化光线追踪Kd-tree遍历单元硬件架构

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

微电子学与计算机 2014年第11期31卷 167-172,176页

作者：王皛邓仰东清华大学微电子学研究所北京100084

在提出引入restart遍历算法的基础上,构造流水线处理机制,使得硬件架构可以实现整个遍历和相交测试流程模块间(粗粒度)和模块内部(细粒度)完全流水线化.同时,也改进了光线-图元相交测试的浮点算法,能够减少浮点运算单元个数.实验结果在F... 详细信息

在提出引入restart遍历算法的基础上,构造流水线处理机制,使得硬件架构可以实现整个遍历和相交测试流程模块间(粗粒度)和模块内部(细粒度)完全流水线化.同时,也改进了光线-图元相交测试的浮点算法,能够减少浮点运算单元个数.实验结果在FPGA验证中实现了每秒约处理8千万条光线的能力(100MHz工作时钟).

关键词：光线追踪相交测试 Kd-tree 完全流水线化 restart算法

基于Kd-tree的并行光线跟踪算法在CPU/GPU异构平台中的研究

在线全文

学校读者我要写书评

暂无评论

基于KD-tree的并行光线跟踪算法在CPU/GPU异构平台中的研究

作者：张培承上海大学

学位级别：硕士

光线跟踪算法是全局光照明模型经典的算法之一,为计算机图形学领域提供了一种通过渲染获得真实感图形的解决方案。Kd-tree加速结构是光线跟踪算法中常用的空间剖分策略,基于Kd-tree的光线跟踪算法在CPU和GPU上都已经分别得到很多改进,... 详细信息

光线跟踪算法是全局光照明模型经典的算法之一,为计算机图形学领域提供了一种通过渲染获得真实感图形的解决方案。Kd-tree加速结构是光线跟踪算法中常用的空间剖分策略,基于Kd-tree的光线跟踪算法在CPU和GPU上都已经分别得到很多改进,取得了很大发展。但现有的基于Kd-tree的光线跟踪算法仍然存在着Kd-tree构建并行度不高,场景遍历效率较低的问题;而且在CPU/GPU异构平台中,现有光线跟踪算法无法同时高效的利用CPU与GPU的计算能力。本文以CPU/GPU异构平台中的并行光线跟踪算法为研究对象,提出了加速结构Kd-tree多层分阶段的构建思想和在Kd-tree的遍历前增加路径压缩预处理操作的概念,并结合CPU/GPU异构平台特点对光线跟踪算法流程进行改进。最后辅以实验,对本文提出的CPU/GPU异构平台中光线跟踪算法的改进进行验证。本文的主要研究工作如下:（1）鉴于现有的基于GPU的光线跟踪算法存在着加速结构Kd-tree构建并行度较差,耗费时间较长的问题,提出一种多层次的Kd-tree构建算法,将均匀栅格划分、基于分区的近似SAH划分和基于精确SAH划分的空间划分策略结合起来,对不同阶段的Kd-tree节点采用合适的划分策略,从而加快了高质量kdtree的构建速度。（2）目前基于Kd-tree的光线跟踪算法中,加速结构Kd-tree的遍历过程中可能遇到大量不包含物体的空白节点,对这些节点的遍历将导致不必要的计算。针对这一问题,本文在构建Kd-tree的过程中引入Morton Code,并根据路径压缩思想将空白节点剔除,从而减少无用的遍历求交计算,提高Kd-tree的遍历速度。（3）单纯对CPU或GPU优化的光线跟踪算法渲染过程中任务并行度较低,CPU资源利用不充分。本文基于CUDA并行编程架构,并结合光线跟踪算法的改进,提出CPU/GPU异构平台中并行光线跟踪算法的完整渲染流程及过程中的任务数据分配策略,加快了三维模型的图像渲染速度。为了验证关于光线跟踪算法的改进及其在CPU/GPU异构平台中的实现,本文设计了两组实验。由实验结果可以得到以下结论:首先,在相同条件下,改进的Kd-tree构建与遍历算法能较大提高光线跟踪算法的效率。其次,在相同条件下,本文方法在CPU/GPU异构平台中的渲染速度要明显高于只针对CPU或GPU的优化算法。综上所述,本文提出的针对CPU/GPU异构平台中基于Kd-tree的并行光线跟踪算法的改进取得了预期的结果,较大地提高了光线跟踪算法的渲染速度。

关键词：光线跟踪算法 CPU/GPU异构平台 Kd-tree Morton Code