KD-Tree的并行化创建方法分析

针对KD-Tree的串行创建效率不高的问题,文中对KD-Tree创建的并行化方法进行了研究。首先通过分析串行创建的方法;结合GPU的并行特性,改进了原有方法;并对三种不同的并行化方法进行了对比,其中基于GPU构建的并行化方法既保证了稳定性和性能,又具有比较满意的时间复杂度。

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

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

基于KD-Tree的组合目标电磁散射快速算法

用线索KD树空间加速算法对复杂目标的几何结构进行重新组织,然后根据弹跳射线法(SBR)基本原理进行目标和射线的求交计算,进而计算出复杂目标的多次散射场。该算法充分利用了树结构的快速遍历特性,避免了大量的、无效的求交计算,显著提高了传统射线追踪法的效率,加速比最高可达90倍。数值结果验证了本方法在组合目标雷达散射计算中的有效性。

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

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

一种基于GPU虚拟栈的光线跟踪KD-Tree遍历算法

光线跟踪是实现高真实感绘制的渲染技术,利用GPU的大规模并行计算能力实现光线跟踪计算加速是目前研究的热点。KD-Tree是GPU上光线跟踪的主要加速结构,而基于栈的CPU遍历算法无法直接应用到GPU上。本文提出一种基于二进制位运算的虚拟栈结构,通过较少的存储空间代价实现了GPU上栈的功能。通过设计宽松的入栈条件减少了相交测试次数,降低了数据存储量。结合已有的无栈遍历算法,设计实现了基于虚拟栈的KD-Tree遍历算法,相对于传统CPU算法达到两个数量级的加速比,相对使用简单栈结构的GPU算法也有较大幅度的速度提升。

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

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

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

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

基于小波变换的35kV变电站供10kV电炉变压器负荷保护检测方法

过高或过低的负荷可能导致供10kV电炉变压器的不稳定,甚至引发系统崩溃或设备故障。因此,提出一种基于小波变换的35 kV变电站供10 kV电炉变压器负荷保护检测方法。通过经验小波和小波变换对含有噪声的电炉变压器负荷数据进行去噪处理,将其分解为多频率的模态函数,以峭度值为依据划分去噪后的模态函数尺度域,重构电炉变压器负荷数据。通过KD-Tree算法将电炉变压器负荷数据划分为多个数量均匀分区,计算可达距离设定电炉变压器负荷判定阈值。建立局部簇关联关系集合,合并处理电炉变压器负荷计算节点聚类结果,划分全局异常样本点集合,完成电炉变压器负荷数据异常检测。实验结果表明,所提方法的去噪效果较好,对电炉变压器负荷异常查全率和查准率均保持在95%以上,且检测时间保持在600 ms以内,可以高效且准确地实现电炉变压器负荷保护检测。

基于高阶重力场模型的山区高程拟合研究

选用沿海山区GNSS水准点的实测高程异常,分别对近几年国际上公布的EGM2008、EIGEN-6C2、EIGEN-6C3stat、GECO、XGM2019e、SGG-UGM-2这6个高阶重力场模型计算的高程异常进行精度检验,分析不同模型、不同截断阶次模型高程异常精度与阶次的关系,采用基于Kd-Tree算法的二次曲面拟合方法进行山区水准面移去—拟合—恢复。结果表明,利用基于Kd-Tree算法高阶重力场模型进行山区水准拟合精度提高明显,具有较好的适应性。

一种针对大规模场景的点云匹配算法

针对大规模点云匹配时传统算法速度慢和匹配结果不一致的问题,提出一种新的点云匹配方法。该方法首先利用KD树找到点云中深度最小的点并以该点作为种子点,然后通过在深度信息和曲率两个方面做以改进的区域生长分割算法提取出点云上表面区域,并在该区域提取点云边界。最后使用改进的点对特征完成点云匹配算法验证。实验结果表明,相比传统算法,该方法在匹配速度以及匹配结果的一致性方面得到了显著的提升,在处理大规模点云匹配上具有实际应用价值。

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

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

基于Kd树改进的高效K-means聚类算法

针对经典的K-means算法在多维数据聚类效率上还有待提高的问题,本文提出一种称为CKmeans的改进聚类算法。该算法在k-means算法的基础上,通过引入Kd树空间数据结构,初始聚类中心从多维数据某一维的区间等间隔集中选取,以及在数据对象分配过程中采用剪枝策略来提高算法的运行效率。实验结果表明,CK-means聚类算法较经典的k-means聚类算法运行效率更高。

基于差分隐私保护的KDCK-medoids动态聚类算法

K-medoids算法对初始中心点敏感,不能有效地对动态数据进行聚类,且需要对相关的隐私数据进行保护。针对这些问题,提出了基于差分隐私保护的KDCK-medoids动态聚类算法。该算法在采用差分隐私保护技术的基础上将KD-树优化选取出的k个聚类中心和增量数据相结合建立新的KD-树,然后采用近邻搜索策略将增量数据分配到与其相应的聚类簇中,从而完成最终的动态聚类。通过实验分别对小数据集和多维的大数据集的聚类准确率及运行时间进行了分析,同时也对采用差分隐私保护技术的KDCK-medoids算法在不同数据集上的有效性进行了评估。实验结果表明,基于差分隐私保护的KDCK-medoids动态聚类算法能够在实现隐私保护的同时快速高效地处理增量数据的动态聚类问题。

基于KD树改进的DBSCAN聚类算法

针对DBSCAN聚类算法随着数据量增大,耗时越发非常严重的问题,提出一种基于KD树改进的DBSCAN算法(以下简称KD-DBSCAN).通过KD树对数据集进行划分,构造邻域对象集,提前区分出噪声点和核心点,避免聚类过程中对噪声的邻域集计算以及加快了核心点对象的邻域集查询速度.文中以浮动车GPS数据为实验数据,对比传统DBSCAN算法和KD-DBSCAN算法的聚类效果和时间性能,实验结果表明KD-DBSCAN算法的聚类效果和传统的DBSCAN基本一致,但时间性能有很大的提升.

融合多源数据的高速公路路段车流碳排放精细测算方法

在“双碳”政策的时代背景下,交通行业碳减排任务艰巨,但目前面临车辆碳排放测算精度不高的问题。为实现车辆碳排放的精细测算,文中提出了一种融合多源数据的高速公路路段车流碳排放精细测算方法。首先,运用KD-树算法将运营车辆的GPS坐标与高速公路道路点坐标搜索匹配,实现对运营车辆的实时监测。然后,建立车辆碳排放测算模型,进而设计相关的计算流程。最后,以虎门大桥主桥段为例进行路段断面碳排放测算,通过VISSIM仿真及相关对比实验,验证了文中所提出的算法的科学性和可靠性。结果表明:按车辆类型分类,微型小型客车的碳排放最高,占比达74.36%;按燃料类型分类,汽油车的碳排放最高,占比达80.50%;新能源汽车运行车次数占12.60%,但碳排放仅占4.27%,因此大力发展新能源货车是推进高速公路碳减排的重点。研究还发现,将交通饱和度控制在0.32~0.38时,当量标准车的平均碳排放较少;当交通饱和度大于0.62时,当量标准车平均碳排放显著增加。文中研究结果可以为交通管理部门制定相关策略提供理论依据。

An Improved Iterative Closest Points Algorithm

Visual method including binocular stereo vision method and monocular vision method of the relative position and pose measurement for space target has become relatively mature, and many researchers focus on the method based on three-dimension measurement recently. ICP alignment, which is the key of three-dimension pattern measurement method, has the problem of low efficiency in large data sets. Considering this problem, an improved ICP algorithm is proposed in this paper. The improved ICP algorithm is the combination of the original ICP algorithm and KD-TREE. The experimental comparison between the improved ICP algorithm and the traditional ICP algorithm in efficiency has been given in this paper, which shows that the improved ICP algorithm can get much better performance.

基于改进KD树的k近邻算法在欺诈检测中的应用

面对互联网交易中店家靠刷销量欺骗消费者的问题,提出使用k最近邻(k-Nearest Neighbor,k NN)算法进行欺诈检测。针对传统k NN算法在搜索k近邻时耗时过多的问题,提出基于KD树结构的k NN算法。为解决经典KD树算法由于每次回溯都要回溯到根节点而导致查询效率低的问题,提出使用最佳桶优先(Best-Bin-First,BBF)算法进行k个近邻的查询。算法首先对待测数据集进行PCA降维,再构建KD树结构,最后使用BBF算法进行k近邻的查询。实验证明,提出的算法可及时有效地检测出欺骗行为。

锥台工件点云拟合算法研究

针对不完整锥面工件模型拟合问题背景,为了解决大量点云数据的标准几何模型拟合问题,提出一种基于遗传算法的锥面点云数据拟合算法:通过随机选取拟合模型采样点,用点云数据点-标准模型采样点的距离计算替代点云数据点-标准曲面模型的距离运算,提高计算效率同时保留点云细节特征;通过对点云数据建立Kd-tree索引提升标准模型采样点距离检测效率;通过遗传算法迭代搜索拟合模型参数,并通过变数据量、变拟合精度等方法改进遗传算法的搜索效率。经实验验证:采用该算法可有效提升部分锥面工件拟合的匹配精度,误差范围±0.5 mm,且对于大量点云数据的处理效果良好。

改进DBSCAN算法下的轨迹点到充电站位置的探测方法

在当前新能源汽车快速发展的背景下,针对相关充电设施位置信息更新缓慢等问题,如何通过第三方数据得到工作状态正常的充电站点分布具有重要意义。本文分析了新能源汽车充电停留轨迹数据的典型特征,并基于这些特征构建了时空关联静动(Stop/Move)模型。利用新能源汽车轨迹数据作为数据源,采用具有噪声的基于密度的聚类(DBSCAN)算法来检测满足充电停留点的点簇,并进一步探测充电站的位置。同时,针对DBSCAN算法具有高时间复杂度的问题,通过构建K维空间树(KD树)数据结构提高了算法执行效率;针对不同参数会影响DBSCAN算法聚类结果的问题,运用邻域参数自适应优化方法提升了轨迹点的聚类效果。利用深圳市的新能源车轨迹数据进行实验分析,结果表明,相比原始DBSCAN算法和k均值聚类(K-MEANS)算法,改进DBSCAN算法提高了算法执行效率,对真实充电站点探测成功率较高。

基于改进快速密度峰值算法的电力负荷曲线聚类分析

为解决传统聚类算法对大数据背景下高维海量、类簇形状差异巨大的电力负荷曲线进行聚类分析时存在的聚类结果不稳定、聚类效果较差、聚类速度慢和内存消耗过大等问题,提出一种改进的快速密度峰值聚类算法。首先应用主成分分析法对归一化后的负荷曲线集进行降维处理,以减少样本向量间欧式距离的计算量和加快后续操作。然后利用kd树算法对降维后的数据进行快速K近邻搜索生成KNN矩阵。最后以KNN矩阵代替原算法的距离矩阵作为输入数据。在基于KNN改进的样本局部密度和距离计算准则的基础上,运用快速密度峰值算法对负荷曲线进行聚类分析。通过实验和算例分析验证了所提改进算法的实用性和有效性。