基于中剖面kd-树的光线跟踪加速算法

kd-树算法是光线跟踪加速技术中效果最突出、应用最广泛的算法之一。在深入讨论该算法的基础上,提出了中剖面kd-树算法。该算法通过在预处理阶段加入一个场景层次信息索引表,将剖分平面固定为中剖面,并利用栈存储下一结点所需信息,节约了一半的存储空间;此外,将剖分轴按照最大轴向进行剖分,从而减少了光线同时穿过两个子结点的可能性,减少了访问时间,提高了算法效率。

基于KD-树和K-means动态聚类方法研究

针对传统K-means聚类算法对初始中心点比较敏感、易陷入局部最优,首先提出基于KD-树的初始聚类中心点选取方法。该方法通过建立KD-树将数据集分割成矩形单元,计算每个矩形的矩形单元中心、矩形单元密度,并将计算所得矩形单元密度降序排列,通过选取前k个矩形单元中心作为初始聚类中心,可有效克服传统算法对初始中心点的敏感。此外,针对传统K-means聚类算法不能有效处理动态数据聚类的问题,进一步提出了KDTK-means聚类算法。该算法对基于KD-树优化选取的k个聚类中心和增量数据建立新的KD-树,利用近邻搜索策略将增量数据分配到相应的聚类簇中并完成聚类。实验结果表明,与传统的K-means聚类算法相比,提出的基于KD-树优化初始聚类中心点选取的算法能够有效选取具有代表性的初始中心,提出的KDTKmeans聚类算法能够快速高效地处理增量数据聚类问题。

基于kd-树的快速邻域分类方法

有关邻域粗糙集中信息粒化的研究大多以提升邻域分类准确率为目的,往往忽略了高效的邻域搜索策略对提升邻域分类方法时间效率的重要现实意义.为解决该问题,文中借助kd-树型邻域搜索策略,提出了一种基于kd-树的快速邻域分类方法 kdtree-NC,该方法在特征选择与邻域分类两阶段的信息粒化过程中,均采用kd-树搜索策略代替传统邻域分类方法 NC中的线性遍历搜索,很大程度上降低了NC处理大规模数据的时间消耗.在18组UCI数据集上的实验结果表明,与NC方法相比,kdtree-NC方法在特征选择和邻域分类上的时间效率都有显著提升.

结合Kd-树和熵编码的密文图像可逆数据隐藏

目的 密文图像可逆数据隐藏技术既可以保证载体内容不被泄露,又可以传递秘密信息,在军事、医疗等方面发挥着重要的作用。然而,以往的大多数方法存在图像冗余未被充分利用、数据嵌入容量不足等问题。为解决这些问题,提出了一种结合Kd-树和熵编码的高容量密文图像可逆数据隐藏算法。方法 该方法在图像加密之前需要对图像应用中值边缘检测(median-edge detector,MED)算法计算预测误差,并把得到的预测误差绝对值图像划分为两个区域:S0区域和S1区域。根据Kd-树标签算法和熵编码生成辅助信息,在对图像使用加密密钥Ke加密之后嵌入辅助信息,生成加密图像;在秘密数据嵌入阶段,根据附加信息和数据隐藏密钥嵌入秘密数据,生成载密图像;在解密阶段可以根据附加信息、图像加密密钥和数据隐藏密钥提取秘密数据并无损恢复图像。结果 实验测试了BOWS-2(break our watermarking system 2nd)数据集,平均嵌入容量为3.910 bit/像素。与现有的几种方法进行比较,该算法可以获得更高的秘密数据嵌入容量。结论 该方法在图像加密前腾出空间,与相关算法相比,实现了更高的嵌入容量,并且可以实现原始图像的无损恢复。

利用KD-树剔除机载雷达点云粗差的方法研究

针对机载LiDAR点云数据后处理中的现有粗差剔除方法存在需要大量人工干预或普适性差的缺点,该文在使用高程直方图剔除显著的高位、低位粗差的基础上,利用KD-树组织机载LiDAR点云数据,通过判断当前点与其k个最邻近点的平均距离远近来自适应地识别粗差点。实验结果表明:该算法具有参数较稳健、粗差剔除效果较好、效率较高的优势。

基于kd-树的差分隐私二维空间数据划分发布方法

为解决现有基于网格结构的差分隐私二维空间数据划分发布方法可能引起局部划分过细导致查询精度低的问题,提出了基于kd-树的差分隐私二维空间数据划分发布方法—kd-PPDP算法(differentially privacy partitioning publication algorithm based on kd-tree)。算法采用了kd-树算法思想,通过启发式地识别网格化后数据分布情况并合并相邻近似网格单元来防止局部划分过细问题,从而减少所添加的噪声,提高查询精度。通过实验对比分析了kd-PPDP算法与现有基于网格结构的划分发布方法的查询误差以及时间效率,结果表明了该算法的有效性和可行性。

KD-TSS:精确隐私空间分割方法

基于KD-树与差分隐私保护的空间数据分割得到了研究者的广泛关注,空间数据的大小与拉普拉斯噪音的多少直接制约着空间分割的精度。针对现有基于KD-树分割方法难以有效兼顾大规模空间数据与噪音量不足的问题,提出了一种满足差分隐私的KD-树分割方法 SKD-Tree(sampling-based KD-Tree)。该方法利用满足差分隐私的伯努利随机抽样技术,抽取空间样本作为分割对象,然而却没有摆脱利用树高度控制拉普拉斯噪音。启发式设定合适的树高度非常困难,树高度过大,导致结点的噪音值过大;树高度过小,导致空间分割粒度太粗劣。为了弥补SKD-Tree方法的不足,提出了一种基于稀疏向量技术(sparse vector technology,SVT)的空间分割方法 KD-TSS(KD-Tree with sampling and SVT)。该方法通过SVT判断树中结点是否继续分割,不再依赖KD-树高度来控制结点中的噪音值。SKD-Tree、KD-TSS与KD-Stand、KD-Hybrid在真实的大规模空间数据集上实验结果表明,其分割精度以及响应范围查询效果优于同类算法。

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

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

混合存储区块链中的时空关键字查询

混合区块链通过链上-链下的存储模式来支持供应链中多方协同的数据可信共享.针对现有时空关键字查询方法预先读取全部链下数据并采用B+树作为索引所导致的效率低下问题,提出一种混合存储区块链中的时空关键字查询方法.首先,设计按属性划分的区块链存储模型,并在区块内和区块间设计B~2M-BKM两级索引结构,支持关系型查询的同时高效检索区块数据;其次,设计链上-链下时空关键字查询方法,提升查询效率.最后,在公开数据集上进行实验,验证所提出方法的有效性.

保留边界的点云简化方法

针对点云简化算法中边界点丢失的问题,提出了一种保留边界的三维散乱点云的非均匀简化算法。首先利用kd-tree建立散乱数据点云的空间拓扑关系,计算出每个数据点的k邻域;然后针对目前依据点云分布均匀性算法提取边界效率低的问题,提出一种改进的点云边界点判定算法;最后保留所有边界点,对非边界点,根据曲面变分值和k邻域点已保留比例,进行点云的非均匀简化。实验结果表明,该算法精度高,空间复杂度低,而且简化后点云边界保留完整。

基于一维Otsu的多阈值医学图像分割算法

针对传统医学图像分割算法时间复杂度高、分割精度低等问题,提出一种基于一维Otsu的自动多阈值分割算法.考虑到医学图像信息的复杂性,引入基于梯度、灰度、距离的综合信息直方图替代传统的灰度直方图,并分别赋予这3个信息相应的权值.采用kd-树作为框架快速自动确定阈值个数,进而实现Otsu对医学图像的自动多阈值分割.与最大熵、基于粒子群优化的Otsu算法等进行对比实验的结果表明,该算法的分割性能优于其他算法.

基于轮廓线度量的形态学骨架剪枝方法

提出了一种基于轮廓线度量的骨架剪枝方法,该方法使用距离骨架点最近的轮廓点在轮廓线上的最小距离作为骨架点显著性的度量,该度量具有较好的显著性表现能力、多余的毛刺状分枝区分能力和公平性。在算法中将轮廓线上的所有点建立为kd-树,通过kd-树搜索距离骨架点最近的轮廓点。将此方法运用到形态学细化产生的骨架上,通过在最近骨架点搜索和距离计算上引入一定程度的平滑,得到效果良好的图像骨架。实验结果表明该方法有较强的稳定性和抗噪能力。

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

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

光线跟踪模拟卫星成像的并行加速研究

为了提高光线跟踪的速度，在深入研究和比较各种光线跟踪加速算法的基础上，采用了空间剖分技术和GPu并行加速相结合的方法。对地面数据信息采用kd-树的组织结构，并改进kd-树的构建方式，大大减少了时间复杂度。对光线跟踪部分，采用GPu并行加速，多条光线并行处理。该方法在保证图像质量的同时绘制速度大大提高，为快速生成真实感图像提供了有效手段。

一种改进SIFT算法

针对图像特征提取算法-SIFT,特征描述器维数较高,特征匹配耗费时间较长,匹配过程中存在相同图像不能匹配和不同图像能够匹配等问题,提出了一种改进SIFT算法与KD-tree搜索匹配算法相结合的新方法。采用KD-Tree算法替代传统链表式搜索方法降低特征点匹配时间;把特征点间距离和特征描述子内积同时作为匹配标准,加入相应匹配阈值减少匹配错误率,并通过理论和实验证明采用欧几里德距离作为相似性度量具有更高的匹配成功率。实验结果表明,在图像特征匹配中,该算法能够有效减少特征匹配错误率,大幅度降低匹配时间,具有较好的实时性和鲁棒性。

Research on the Algorithm of Image Matching based on Improved SIFT

The paper analyze and improve the SIFT optimized algorithm, and proposes an image matching method for SIFT algorithm based on quasi Euclidean distance and KD-tree. Experiments show that this algorithm has matching more points, high matching accuracy, no repealed points and higher advantage of matching efficiency based on keeping the basic characteristics of SIFT algorithm unchanged, and provides precise matching point to generate precise image stitching and other related fields of the follow-up product. At the same time, this method was applied to the layout optimization and achieved good results.

Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space

We present a study to show the possibility of using two well-known space partitioning and indexing techniques, kd trees and quad trees, in declustering applications to increase input/output （I/O） paraUelization and reduce spatial data processing times. This parallelization enables time-consuming computational geometry algorithms to be applied efficiently to big spatial data rendering and querying. The key challenge is how to balance the spatial processing load across a large number of worker nodes, given significant performance heterogeneity in nodes and processing skews in the workload.