kd-tree

摘要： 针对传统RANSAC算法提取车载LiDAR地面点云精度低、结果不稳定等问题,提出了一种改进的RANSAC算法。使用KD-Tree构建点云拓扑关系并将点云空间划分成不同区域,设置邻域半径得到每个点的邻近索引并计算点云法向量,根据法向量对地面点云进行粗提取。遍历粗提取的地面点云求平均高程,将其作为阈值滤除较高的地物点得到地面点集。从地面点集中随机选取一个点作为种子点,利用FPS算法选取剩余两个种子点并拟合平面模型,将点集数据代入平面模型,判断每个点云数据到平面模型的距离是否满足预设的阈值并统计地面点数量,重复该步骤直至拟合出一个最优平面模型,最后利用最优平面模型精确提取地面点。实验结果表明,改进后算法提取地面点的一类误差、二类误差、总误差分别为2.16%、4.79%、2.99%,均比原算法低,同时改进后的算法稳定性更强。

摘要： 时序图是顶点之间的连通性随时间变化的图,大规模时序图的紧凑表示和高效操作是分析和处理时序图数据的基础.提出了一种基于决策图的时序图数据紧凑表示方法——k^(d)-MDD.k^(d)-MDD是对k^(d)-tree的改进,该方法对时序图的邻接矩阵进行k^(d)划分,通过引入多值决策图来合并相同子矩阵,即k^(d)-tree图数据表示中存在的同构子树,存储结构更加紧凑.在k^(d)-MDD紧凑表示基础上,提供了基于k^(d)-MDD的时序图的基本操作(如顶点正向反向邻居的检索、边是否处于活动状态的检查、边的添加和删除等).在真实的时序图数据集上(Flickr-growth,YouTube-growth,Wikipedia等)的实验结果表明,k^(d)-MDD表示中的节点数仅为k^(d)-tree表示中节点数的1.58%~4.65%,与c k^(d)-tree和bc k^(d)-tree相比,其节点数为c k^(d)-tree中节点数的11.13%~20.39%,为bc k^(d)-tree(bucket c k^(d)-tree)中节点数的23.17%~41.95%.实验结果验证了k^(d)-MDD表示时序图的优越性.

摘要： 为了从移动终端位置数据中精准识别居民职住地,提出了一种基于时空约束密度聚类的职住地识别方法。首先,利用基于K-means的DBSCAN(density-based spatial clustering of applications with noise)时空驻点聚类过程将居民多天的原始轨迹点分成不同的时空驻点簇;然后,利用基于速度阈值的停留点簇和移动点簇识别过程将居民的每一个时空驻点簇区分为停留点簇或移动点簇;接着,利用基于K近距离的DBSCAN重要停留点聚类过程将居民的停留点分成不同的重要停留点簇;最后,利用基于KD-tree优化的KNN(K-nearest neighbor)职住地识别过程将居民的每个重要停留点识别为工作地、居住地、职住同一区域或兴趣地点区域。实验结果表明,该方法的每个过程都是合理有效的,并且最终的职住地识别效果要优于时间阈值法、累加时间法和信息熵法。

摘要： 点云配准的质量直接影响着三维重建的质量。针对传统K-4PCS耗时长且易出现错误匹配等问题,文中提出一种基于边界质心的点云粗配准方法。通过对点云进行边界提取,既保留点云外表特征,又减少了点云数据的大小,提高了粗配准速度。为了加快边界点的提取速度,使用K-D tree算法完成对k近邻点的搜索。通过配准边界点的质心,减少点云初始距离并增加重叠度,保证了粗配准的精度。实验结果证明,文中方法在粗配准速度和精度方面都优于传统K-4PCS算法,其速度约为传统K-4PCS算法的2倍,平移和旋转精度也比传统K-4PCS高了40%以上。文中所提方法对提高点云粗配准的速度和精度具有一定的参考价值。

摘要： ICP配准算法对待配准点云初始位置要求较高,且配准过程耗时长,因此提出了一种基于特征点改进的ICP点云配准算法。利用点云的局部法向量提取特征点,根据特征点的特征直方图得到初始配准点云;通过K-D tree搜索点集中的对应点对,运用四元数法得到配准参数,根据刚性距离约束条件精确配准点云。实验表明,该算法避免了ICP配准算法因初始位置姿态而陷入局部最优,同时提高了配准效率和精度。

摘要： 逆向工程采用激光扫描设备获取点云数据时会引入无关离体噪声点,针对密度聚类法去噪时引起的内存占用较大、收敛时间较慢的问题,提出了一种高效的点云去噪聚类方法。首先,采用KD-tree建立点云数据的空间索引结构,选择点云的某一维度,找出最小索引核心点云。然后,沿着该维度方向在核心点云邻域外选择最近的未标记的点云扩展密度类。最后,分离出密度相连最大的点云类以完成点云去噪。实验结果表明,与统计滤波、半径滤波、密度聚类滤波算法相比,该方法在完整保留目标点云的同时能高效地去除离体点云噪声,提高了点云去噪的质量。

摘要： 电铲是露天矿场开采系统中的核心设备。由于传统电铲缺乏环境感知能力、人工挖掘满斗率低及能耗大等问题,导致无法实现高效挖掘。针对上述问题,提出了一种基于七段式S型速度曲线在三维空间下的挖掘轨迹优化方法与一种基于Kd-tree与K最邻近搜索的物料点云数据查找方法计算挖掘体积,将单位挖掘体积下的最小能耗作为目标函数建立轨迹优化模型,使用遗传算法对挖掘轨迹及参数进行优化,从而获得最优挖掘参数。

摘要： 为了提高几何光学与物理光学(GO-PO)方法在计算舰船目标散射、海面与舰船目标耦合散射时面元对入射波和反射波可见性判断的效率,提出了Kd-tree和GO-PO方法相结合的模型.Kd-tree方法在入射波或反射波射线与面元相交测试前,首先执行射线与面元所在包围盒的相交测试,若包围盒的距离参数不符合要求,则无须进入该包围盒,减少射线与大部分面元不必要的相交测试.数值结果表明,改进的GO-PO混合方法在保证计算精度的同时能够提高效率约3倍.因此,该混合方法是相对有效且能够运用于大范围海面与大型舰船目标复合电磁散射特性的研究.

摘要： 本发明公开了一种基于KDTree的图像数据库数据处理方法，包括如下步骤：步骤一、基于KDTree对地图标注信息进行遍历和整合，得到标注集S={s1,s2,…,sn}；步骤二、对标注集S进行基于词语相似度的敏感信息检测，将地图标注内容进行敏感度分级；步骤三、根据地图标注内容的敏感度等级进行对应的脱敏处理。本发明利用了地图标注的位置信息，实现了对地理空间数据中标注内容的遍历、整合和敏感信息脱敏的自动处理，克服了现有人工处理下工作繁琐，效率低下且容易出错以及出现漏洞的现象。

摘要： 本发明的用于钣金件建模的基于KDtree的空间面域生成方法及系统，采用KDtree数据结构，实现对曲线段的近邻搜寻，并以此构建面积最小面域，来生成由多个单元网格构成的钣金件整体的空间面域，通过近邻搜寻方法，大大减少了搜寻配对的运算时长，解决了传统的冗余迭代搜寻方法运算耗时长的问题，还能将生成的面域进行参数化输出，实现连续化和自动化，提供后续建模模块的参数化输入，有效节约人力资源，操作简单，使用可靠，耗时少从而减少工人工作强度，打破了生产时间的约束，有效提高生产速度。

摘要： 本发明公开了一种利用地面激光扫描技术进行测量对象表面重建时基于KDTree的点云数据双边滤波去噪的方法，在双边滤波算法中，通过KDTree来建立散乱点云数据点的领域，有了数据点的领域点集，利用逆迭代法求领域点得法向量ni，再计算滤波函数参数及滤波高斯参数得到双边滤波权因子λ，最终得到滤波后的新数据点p＇i=pi+λni。本发明的双边滤波方法用于滤除点云数据的噪声，方法简单有效，并且运算速度快，能够在保持特征的同时去除噪声，适用于处理小范围的噪声。

摘要： 本发明公开了一种基于KDTree的图像数据库数据处理方法，包括如下步骤：步骤一、基于KDTree对地图标注信息进行遍历和整合，得到标注集S={s1,s2,…,sn}；步骤二、对标注集S进行基于词语相似度的敏感信息检测，将地图标注内容进行敏感度分级；步骤三、根据地图标注内容的敏感度等级进行对应的脱敏处理。本发明利用了地图标注的位置信息，实现了对地理空间数据中标注内容的遍历、整合和敏感信息脱敏的自动处理，克服了现有人工处理下工作繁琐，效率低下且容易出错以及出现漏洞的现象。

摘要： 本发明的用于钣金件建模的基于KDtree的空间面域生成方法及系统，采用KDtree数据结构，实现对曲线段的近邻搜寻，并以此构建面积最小面域，来生成由多个单元网格构成的钣金件整体的空间面域，通过近邻搜寻方法，大大减少了搜寻配对的运算时长，解决了传统的冗余迭代搜寻方法运算耗时长的问题，还能将生成的面域进行参数化输出，实现连续化和自动化，提供后续建模模块的参数化输入，有效节约人力资源，操作简单，使用可靠，耗时少从而减少工人工作强度，打破了生产时间的约束，有效提高生产速度。

摘要： 本发明公开了一种利用地面激光扫描技术进行测量对象表面重建时基于KDTree的点云数据双边滤波去噪的方法，在双边滤波算法中，通过KDTree来建立散乱点云数据点的领域，有了数据点的领域点集，利用逆迭代法求领域点得法向量ni，再计算滤波函数参数及滤波高斯参数得到双边滤波权因子λ，最终得到滤波后的新数据点p＇i=pi+λni。本发明的双边滤波方法用于滤除点云数据的噪声，方法简单有效，并且运算速度快，能够在保持特征的同时去除噪声，适用于处理小范围的噪声。