基于线性四叉树的快速邻域查询算法 被引量：10

1

作者 赵慧 宋星 《计算机工程与设计》 CSCD 北大核心 2007年第18期4333-4335,共3页

邻域查询是位置服务系统的核心技术,它的实现取决于空间对象数据模型。根据空间对象分布构建的四叉树模型,以及线性四叉树中位置码的使用,提出了一种新的基于线性四叉树的快速邻域查询算法。该算法根据满四叉树结点编码思想对线性四叉树... 邻域查询是位置服务系统的核心技术,它的实现取决于空间对象数据模型。根据空间对象分布构建的四叉树模型,以及线性四叉树中位置码的使用,提出了一种新的基于线性四叉树的快速邻域查询算法。该算法根据满四叉树结点编码思想对线性四叉树的Morton码进行了改进,并增加了表示四叉树所有结点状态的序列,通过网格模型的邻域查询算法实现了线性四叉树的快速邻域查询。 展开更多

关键词 位置服务系统 线性四叉树 邻域查询 Morton编码 结点状态序列

下载PDF 职称材料

基于四叉树的邻域查询技术 被引量：8

2

作者 张芩 郭薇 《系统仿真学报》 CAS CSCD 2001年第S2期48-50,共3页

邻域查询技术是地理信息系统中基本的空间分析操作,本文对基于四叉树和八叉树的邻域查询技术进行了探讨,并详细介绍了基于显式四叉树和FD线性四叉树的邻域查询算法。

关键词 :地理信息系统 邻域查询 四叉树 八叉树

下载PDF 职称材料

融合kd tree邻域查询的深度学习点云分类网络 被引量：13

3

作者 马杰 王旭娇 +2 位作者 马鹏飞 杨立闯 王楠楠 《深圳大学学报（理工版）》 EI CAS CSCD 北大核心 2020年第1期79-83,共5页

为解决PointNet++精度较低、耗时较长,且对输入点的噪声敏感的缺陷,引入一种高效的k维树(k-dimensional tree,kd tree)邻域查询方法,通过构建kd tree查找查询点周围指定半径内的近邻点,构造局部区域集,完成在PointNet++分组层上的局部... 为解决PointNet++精度较低、耗时较长,且对输入点的噪声敏感的缺陷,引入一种高效的k维树(k-dimensional tree,kd tree)邻域查询方法,通过构建kd tree查找查询点周围指定半径内的近邻点,构造局部区域集,完成在PointNet++分组层上的局部特征提取.针对原网络训练过程中存在的过拟合问题,引入随机失活(dropout)正则化,减少网络收敛训练的时间.在Ubuntu14.04系统下搭建TensorFlow的图形处理器深度学习环境,并在ModelNet40数据集上进行训练和测试.实验结果表明,分别为当查询半径为0.1、0.2和0.3时,该查询方法的分类准确率分别为91.1%、92.1%和94.3%,皆优于PointNet++方法,且网络训练用时更短.改进后的结构在斯坦福三维语义分析数据集(Stanford 3D semantic parsing dataset)上进行语义分割实验平均交并比(mean intersection over union,MIoU)达57.2%,且其对于遮挡物体的鲁棒性更高. 展开更多

关键词 计算机神经网络 深度神经网络 深度学习 点云分类 邻域查询 k维树 ModelNet40

下载PDF 职称材料

散乱点集拓扑邻域均值逆向漂移查询算法 被引量：2

4

作者 孙殿柱 白银来 +1 位作者 李延瑞 李聪 《机械工程学报》 EI CAS CSCD 北大核心 2015年第1期182-187,共6页

为获取散乱点集的拓扑邻域数据,提出一种基于均值逆向漂移的自适应迭代搜索查询算法,基于R*树动态空间索引,采用动态扩展空心球k邻域查询算法快速获取目标样点的拓扑邻域参考数据,根据邻域查询与点集密度分布的关系,采用核密度估计描述... 为获取散乱点集的拓扑邻域数据,提出一种基于均值逆向漂移的自适应迭代搜索查询算法,基于R*树动态空间索引,采用动态扩展空心球k邻域查询算法快速获取目标样点的拓扑邻域参考数据,根据邻域查询与点集密度分布的关系,采用核密度估计描述点集的分布规律,利用均值漂移算法计算得到能够反映散乱点集局部分布特征的均值漂移矢量和均值点,将邻域搜索区域沿逆向均值漂移矢量移动进行邻域查询并实时更新样点的拓扑邻域参考数据,进而完成拓扑邻域查询的均值逆向漂移迭代计算,最终实现样点拓扑邻域数据的自适应搜索查询。试验表明,该算法可快速获取复杂型面均匀或非均匀采样点集的邻域数据,查询结果包含Voronoi邻域及其他有效邻域参考数据,能更好地反映散乱点集局部型面特征。 展开更多

关键词 散乱点集 拓扑邻域查询 R＊树 核密度估计 均值逆向漂移

下载PDF 职称材料

二进制编码八叉树的海量点云邻域快速搜索算法 被引量：6

5

作者 姜晓通 戴宁 +2 位作者 程筱胜 张长东 郭保苏 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2018年第5期824-832,共9页

海量点云的邻域搜索是点云数据处理的关键技术,是对点云进行进一步处理的基础.针对海量点云数据邻域搜索效率较低的问题,提出了一种基于二进制编码八叉树的快速搜索算法.首先构建八叉树,利用一种二进制编码方式对八叉树的各个节点进行编... 海量点云的邻域搜索是点云数据处理的关键技术,是对点云进行进一步处理的基础.针对海量点云数据邻域搜索效率较低的问题,提出了一种基于二进制编码八叉树的快速搜索算法.首先构建八叉树,利用一种二进制编码方式对八叉树的各个节点进行编码,即对空间3个维度分别进行编码;其次对邻域点进行查找过程,根据搜索半径直接确定需要搜索的高度;最后在确定的节点高度下,根据编码的特点直接计算所需要查询的邻域节点.实验结果表明,该算法准确性高、速度快,能够实现海量点云数据的快速邻域搜索. 展开更多

关键词 海量点云 二进制编码 八叉树 邻域查询

下载PDF 职称材料

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

6

作者 朱楚宏 汤开文 《国土资源导刊》 2009年第1期64-67,共4页

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

关键词 查询优化 邻域查询 优化金字塔技术 粒子群算法

下载PDF 职称材料

基于网格查询的局部离群点检测算法 被引量：2

7

作者 牛少章 欧毓毅 +1 位作者 凌捷 顾国生 《计算机工程与应用》 CSCD 北大核心 2019年第17期89-94,共6页

针对基于密度的局部离群因子算法(LOF),需要计算距离矩阵来进行k近邻查寻,算法时间复杂度高,不适合大规模数据集检测的问题,提出基于网格查询的局部离群点检测算法。算法利用距离目标网格中的数据点最近的k个其他数据点,一定在该目标网... 针对基于密度的局部离群因子算法(LOF),需要计算距离矩阵来进行k近邻查寻,算法时间复杂度高,不适合大规模数据集检测的问题,提出基于网格查询的局部离群点检测算法。算法利用距离目标网格中的数据点最近的k个其他数据点,一定在该目标网格或在该目标网格的最近邻接网格中这一特性,来改进LOF算法的邻域查询操作,以此减少LOF算法在邻域查询时的计算量。实验结果证明,提出的LOGD算法在与原LOF算法具有基本相同的检测准确率的情况下,能够有效地降低离群点检测的时间。 展开更多

关键词 局部离群因子 K近邻 距离矩阵 网格 记忆性 邻域查询

下载PDF 职称材料

Greedy DBSCAN:一种针对多密度聚类的DBSCAN改进算法 被引量：45

8

作者 冯振华 钱雪忠 赵娜娜 《计算机应用研究》 CSCD 北大核心 2016年第9期2693-2696,2700,共5页

针对基于密度的DBSCAN算法对于输入参数敏感、无法聚类多密度数据集等问题,提出了一种贪心的DBSCAN改进算法(greedy DBSCAN)。算法仅需输入一个参数Min Pts,采用贪心策略自适应地寻找Eps半径参数进行簇发现,利用相对稠密度识别和判定噪... 针对基于密度的DBSCAN算法对于输入参数敏感、无法聚类多密度数据集等问题,提出了一种贪心的DBSCAN改进算法(greedy DBSCAN)。算法仅需输入一个参数Min Pts,采用贪心策略自适应地寻找Eps半径参数进行簇发现,利用相对稠密度识别和判定噪声数据,在随机寻找核对象过程中使用邻域查询方式提升算法效率,最终通过簇的合并产生最终的聚类结果。实验结果表明,改进后的算法能有效地分离噪声数据,识别多密度簇,聚类准确度较高。 展开更多

关键词 多密度 贪心策略 相对稠密度 邻域查询 噪声数据 DBSCAN聚类

下载PDF 职称材料

基于核密度估计的散乱点云边界特征提取 被引量：14

9

作者 孙殿柱 刘华东 +1 位作者 史阳 李延瑞 《农业机械学报》 EI CAS CSCD 北大核心 2013年第12期275-279,268,共6页

为获得逆向工程中复杂散乱点云的边界特征,提出了一种基于k邻域点集核密度估计的边界特征识别与提取算法,通过R*树索引结构和动态扩展空心球算法实现样点k邻域点集的快速查询,将查询区域半径作为带宽对点集进行核密度估计,由核密度估计... 为获得逆向工程中复杂散乱点云的边界特征,提出了一种基于k邻域点集核密度估计的边界特征识别与提取算法,通过R*树索引结构和动态扩展空心球算法实现样点k邻域点集的快速查询,将查询区域半径作为带宽对点集进行核密度估计,由核密度估计获得反映点集分布的模式点,依据模式点到样点的距离与带宽的比值判别边界点特征。实验结果表明,该算法能够快速、准确提取逆向工程中均匀及非均匀分布的散乱点云的边界特征。 展开更多

关键词 散乱点云 边界特征 R^＊树 k邻域查询 核密度估计

下载PDF 职称材料

一种简单有效的基于密度的聚类分析算法 被引量：8

10

作者 陈燕俐 洪龙 +1 位作者 金达文 朱梧槚 《南京邮电学院学报（自然科学版）》 2005年第4期24-29,共6页

对数据挖掘中基于密度聚类的相关概念和算法进行了讨论,对OPTICS(O rdering Pointers to Iden-tify the C lustering Structure)算法聚类分析的正确性给以了证明。以DBSCAN,OPTICS为基础,提出了一种基于密度的简单有效的聚类算法。新算... 对数据挖掘中基于密度聚类的相关概念和算法进行了讨论,对OPTICS(O rdering Pointers to Iden-tify the C lustering Structure)算法聚类分析的正确性给以了证明。以DBSCAN,OPTICS为基础,提出了一种基于密度的简单有效的聚类算法。新算法主要在ε-邻域查询和种子队列的更新两个方面作了改进,给出了一种简单、效率较高的邻域查询方法-哈希表法,即对整个数据集合或部分数据作网格化处理。测试结果表明新算法能够有效地对大规模数据进行聚类,效率较高。 展开更多

关键词 数据挖掘 聚类 距离 密度 邻域查询

下载PDF 职称材料

一种新的基于线性四叉树的图像分割算法 被引量：1

11

作者 过洁 潘金贵 《系统仿真学报》 CAS CSCD 北大核心 2009年第S1期54-56,60,共4页

图像分割是进行图像分析的一个关键步骤,其分割效果直接决定图像分析的好坏。提出了一种新的基于线性四叉树的图像分割算法,这是一种基于区域增长的图像分割技术,具有比较理想的分割效果,同时利用一种具有常数时间复杂度邻域查询的线性... 图像分割是进行图像分析的一个关键步骤,其分割效果直接决定图像分析的好坏。提出了一种新的基于线性四叉树的图像分割算法,这是一种基于区域增长的图像分割技术,具有比较理想的分割效果,同时利用一种具有常数时间复杂度邻域查询的线性四叉树加快其区域增长过程。 展开更多

关键词 图像分割 线性四叉树 邻域查询 区域增长

原文传递

基于八叉树自适应体归并的光线跟踪加速结构 被引量：8

12

作者 袁昱纬 全吉成 +2 位作者 吴晨 刘宇 王宏伟 《光学学报》 EI CAS CSCD 北大核心 2017年第1期243-252,共10页

针对光线跟踪算法计算量大和运行效率低的问题,提出了一种采用八叉树自适应体归并(OAVM)的光线跟踪加速结构。该结构将八叉树模型的空节点自适应地聚集为包围体,尽可能地减小了光线与空白节点的求交次数。基于OAVM的一种多级八叉树结构... 针对光线跟踪算法计算量大和运行效率低的问题,提出了一种采用八叉树自适应体归并(OAVM)的光线跟踪加速结构。该结构将八叉树模型的空节点自适应地聚集为包围体,尽可能地减小了光线与空白节点的求交次数。基于OAVM的一种多级八叉树结构的特点,提出了采用Morton码对各层级的所有节点分别进行编码的算法,该结构所采用的存储方式和邻域查询算法有效减小了指针数量,避免了递归搜索。同时,该算法可以有效处理大规模动态场景的局部更新问题。基于Liang-Barsky算法,光线相交测试的计算速度得到提升。实验结果表明,和传统结构算法相比,所提出算法的指针总数平均减少了54.45%,光线相交测试时间平均缩短了52.37%,大幅加快了相交测试速度,提升了场景的渲染效率。 展开更多

关键词 光计算 光学数据处理 光线跟踪 八叉树 自适应体归并 相交测试 邻域查询

原文传递

一种新的散乱点云数据多级空间索引 被引量：7

13

作者 赵江洪 王继伟 +1 位作者 王晏民 郭明 《地球信息科学学报》 CSCD 北大核心 2015年第12期1450-1455,共6页

散乱点云数据具有数据量大(海量性)、数据表达精细(高空间分辨率)、空间三维点之间无拓扑关系(散乱性)等特征,在对其进行应用前必须进行数据预处理(如去噪、配准、分割等)。而在这些数据处理过程中需频繁的进行邻域查找,如果没有高效的... 散乱点云数据具有数据量大(海量性)、数据表达精细(高空间分辨率)、空间三维点之间无拓扑关系(散乱性)等特征,在对其进行应用前必须进行数据预处理(如去噪、配准、分割等)。而在这些数据处理过程中需频繁的进行邻域查找,如果没有高效的查询索引机制,很难实现数据自动处理。因此,如何进行数据的组织和索引,以提高后续邻域检索和查询等操作的速度,是目前点云数据处理中的一个研究热点。针对现有点云数据采用的空间索引方式的优缺点,本文提出了一种多级格网和KD树混合的空间索引,该索引提出变分辨率格网索引与KD树的混合索引模式,简称Multi Grid-KD树索引。该方法在保持网格索引算法实现简单查询效率高等优点的同时,解决了单一分辨率数据冗余的问题。以故宫太和殿的点云数据为例,对本文提出的Multi Grid-KD树索引算法和KD树、八叉树等经典算法做对比。结果表明,本文索引方法在最邻近点查询以及四邻域查询的效率上均优于KD树,以及八叉树索引。 展开更多

关键词 点云 空间索引 邻域查询 KD树 八叉树

原文传递