基于k-d树的ICP算法的管道缺陷最深点自动识别研究

金属管道外表面存在凹坑、腐蚀缺陷等情况,为了准确判断管道的剩余服役寿命,提出一种基于k-d树ICP算法的油气管道缺陷最深点自动识别方法。扫描获取带有缺陷的管道点云数据,提取缺陷处至少1/3管道环向区域点云数据,建立标准圆柱件模型获取点云数据。利用ICP算法对两组点云数据进行配准,基于k-d树算法关联所有无序点云,从而加速搜索点云邻域,快速精确地识别出缺陷最深点。将该算法在天然气长输管段进行验证,以第三方专业检测机构的检测缺陷最深点数据为基准,通过计算对比发现,自动识别方法的误差率仅为0.54%,较之传统人工测量方法,测量误差率降低了3.22%,有效提高了管道外表面缺陷深度测量的准确度。

基于Kinect的3D全景图像扫描重建技术

为解决传统的迭代最近点(ICP)算法耗时长的问题,基于K-D树改进ICP算法,通过Kinect对室内场景进行三维重建。利用加速鲁棒性特征(SURF)算法提取特征点,分别使用传统的ICP和基于K-D树改进ICP算法完成多帧点云数据的配准,对比单一场景和多场景下的模型重建效果。结果表明,在面积为30 m^(2)的房间三维模型重建中,传统ICP算法处理时间分别为1.31 min(单一场景)和8.06 min(多场景),而改进ICP算法处理时间为0.67 min(单一场景)和5.23 min(多场景)。改进后的ICP算法三维重建速度较快,没有明显的物品位置错乱等情况,能满足日常需要。

基于k-d树的多波束点云边缘与孔洞提取算法

多波束测深数据广泛服务于水下地形测量。一些基于测深数据的应用需要提取测深数据的边缘轮廓和探测数据中的空洞。针对已有边缘识别算法执行效率低、边界点提取不完整等问题,通过分析点云模型的局部几何属性,提出一种新的基于k-d树的由粗到精的边缘提取算法。首先抽稀测深数据,基于k-d树建立散乱点云的拓扑关系;然后计算散乱点云法向量,采用距离及角度阈值法进一步提取孔洞与边缘轮廓点并去除错误识别的点;最后基于凹包算法,精确获取边缘轮廓点。在西太平洋海域的实验表明:相较于Alpha-shape和Boundary estimation算法,本算法能够更为精确地识别出散乱点云中的边界点,实用性强。

基于Hausdorff距离改进的ICP算法

为满足三维点云配准的高精度要求,提出一种基于Hausdorff距离改进的ICP算法。利用三维点云拟合曲面的主曲率和点邻域内Hausdorff距离相结合的方法,对点云进行简化,剔除正态分布图中Hausdorff值小的点云,使简化后的关键点充分保留点云的几何特征;采用K-D树加速查找,通过最小二乘迭代进行点云ICP配准。对经典ICP算法和改进ICP算法做对比实验,实验结果表明,改进的ICP算法将配准误差由原来的0.3mm控制在了0.1mm左右,大幅提高了点云配准的精确度。

基于形状特征k-d树的多维时间序列相似搜索

多维时间序列是信息系统中一类重要的数据对象,相似搜索是其应用的一个核心.两个序列(子序列)相似度加以比较的常用方法是:将序列(子序列)转换成空间中的曲线,然后计算曲线间的欧几里德距离.这种方法的主要缺陷是它仅考虑了序列(子序列)间的整体距离关系,而不能体现它们自身的局部变化.针对此问题,提出了一种新的可应用于多维时间序列的快速相似搜索方法.该方法将序列(子序列)的局部变化特性与检索结构(k-d树)结合起来,使得在搜索k-d树的同时实现了序列(子序列)的局部变化匹配,从而极大地提高了查询效率和正确率.实验结果表明了算法的有效性.

基于k-d树的k-means聚类方法

在直接k-means算法的基础上提出了一种新的基于k-d树的聚类方法。通过把所有的对象组织在一棵k-d树中,可以高效地发现给定原型的所有最近邻对象。利用的主要思想是:在根结点,所有的聚类中心(或称为候选原型)都是所有对象的最近邻候选集合,对于根结点的子结点,通过简单几何约束来剪枝该候选集,这种方法可以被递归使用。使用基于k-d树的方法可以使直接k-means算法的总体性能提高一到两个数量级。

基于优化K-D树的大面积高密度PCB快速AOI

传统的AO I孔搜索算法是基于顺序的查询方法,其局限在于,随着孔数N的增加,其查询时间以O(N2)急剧恶化,严重影响了大面积高密度PCB的检测效率。提出一种基于优化K-D树的AO I系统查询算法,该方法在建立树和进行完整查询时的效率均为O(NlogN)。实验表明,这种方法查询效率明显高于顺序查询法,对含有大量孔的PCB仍然有较短的查询时间,因而可以较大幅度地提高AO I的检测效率,在需要点位置查询的仪器领域也有广泛的应用前景。

基于有界k-d树的最近点搜索算法

提出了一种基于有界k-d树的最近点搜索算法.算法的原理是:由根节点中的包围盒确定树中数据的空间范围,并在搜索过程中不断划分包围盒来缩小搜索范围,同时递归地计算查询点到包围盒的距离.结合优先级队列,基于有界k-d树的最近点搜索算法拓展到搜索按距离远近排列的多个最近点.实测和仿真分析表明,本搜索算法的计算效率高于传统的搜索算法.

一种基于K-D树优化的ICP三维点云配准方法

为提高三维点云数据配准精度和速度,提出一种基于K-D树优化的ICP三维点云配准方法,首先采用中心重合法实现点云数据的粗配准,然后利用K-D tree快速搜索最近点对改进传统ICP方法,完成三维点云数据精配准,该方法克服传统ICP算法中由于利用欧式距离来判断最近点所引起的工作量大、耗费时间多的缺陷,提高点云的配准速度。在此基础上利用斯坦福不同密度Bunny点云数据进行实验验证,结果表明在采用中心重合法实现三维点云粗配准的基础上,利用K-D tree优化ICP算法,能够提高点云配准的精度、速度和稳定性。

基于k-d树的机载LIDAR点云滤波处理

点云数据滤波处理是获取高精度数字地面模型的关键,而滤波的基本原理是基于某一邻域内高程的突变。在海量、离散的点云数据中,搜索某一邻域的速度将直接影响滤波处理的效率。应用k-d树组织点云数据,不需要先验地知道点云数据间的拓扑关系便可以快速确定其中某一点的邻域点集,从而大大地提高滤波速度。

利用k-d树索引改进数据流skyline查询算法

skyline查询技术近来引起了研究者们的广泛关注,面向数据流的skyline查询是其中的热点.对面向数据流的skyline查询问题进行了研究.对现有方法进行了改进,提出一种基于k-d树的skyline增量更新算法.该方法采用事件链机制来处理数据点的状态变化,避免重复计算过期数据点排它支配域上的skyline;增量数据点的处理过程中采用k-d树作为索引结构,以增强索引结构对数据流变化的自适应性;针对k-d树索引提出多个剪枝规则来减小搜索域,提高搜索效率.理论分析及实验表明,该方法能够更快地响应用户的查询请求,更适用于大规模、疏密分布变化的高速数据流应用场景.

一种采用改进K-d树的无人机影像特征匹配搜索方法

在高分辨率无人机影像匹配过程中,多采用SIFT或SURF算法进行尺度和旋转不变的特征提取与描述,但经过SIFT或SURF算法提取出的特征都是高维向量,在匹配点数量较大时,匹配搜索速度比较慢。针对这一问题,比较了穷尽搜索与K-d树搜索算法的特点;然后按照"降维"的思路,提出了一种采用改进K-d树的匹配搜索方法。经过理论分析和实验验证,该方法可以有效提高匹配搜索速度,并且匹配数据集规模越大、维度越高,搜索速度提升越明显。

多尺度LBP耦合K-D树的图像伪造盲检测算法

针对当前图像伪造检测算法难以有效识别相似区域,且其检测精度依赖于参数和阈值的选择,使其自适应能力较差等不足,提出局部二值模式耦合K-D树的复制-粘贴图像伪造检测算法。基于传统的LBP,设计具有均匀不变性、旋转不变性以及旋转均匀不变性的3种LBP,将其组合形成多尺度LBP(MLBP),利用MLBP提取图像特征,得到3组特征矩阵;引入K-D树,寻找其最优邻域,获取对应的3个相似特征矩阵,通过判断3个特征矩阵中至少两个特征值相同来识别该区域是否被篡改;引入随机抽样一致性策略,降低图像块的误匹配率,提高检测精度。实验结果表明,与当前图像伪造检测技术相比,该检测算法的检测精度更高,能有效识别出旋转、缩放、模糊以及噪声等伪造形式。

融合BRIEF与ICP点云配准的零部件姿态估计方法

物体姿态估计在增强现实、自动驾驶和机器人操作等领域具有重要意义。在机器人抓取与辅助装配过程中实时并准确地估计目标姿态极其重要,为提高装配过程中零部件的抓取与监控的实时性与精度,研究了基于多视图特征库估计目标姿态的方法,设计融合BRIEF(Binary Robust Independent Elementary Features)特征匹配与ICP(Iterative Closest Point)点云配准的零部件姿态估计方法对零部件姿态角进行估计测量。以法兰、扳手、电钻等零件工具进行实验,实验结果表明融合BRIEF特征匹配与ICP点云配准的姿态估计方法运行耗时约200ms,而姿态估计的最大误差角度为4.5°,能有效保证零部件姿态估计方法的实时性与精度,可应用于机器人抓取作业、辅助装配监控等。

基于K-D树加速的大型点云配准算法

为了实现大型点云的精确配准,首先对大型点云数据进行降采样及去质心预处理,并采用迭代最近点(Iterative Closest Point,ICP)算法计算点云间的旋转矩阵R与平移矩阵T,最终在Visual Studio中基于OpenGL库实现界面交互和结果显示。结果表明,该配准算法既支持人为选择关键点进行配准,也支持随机生成关键点进行配准,且准确率高。大型点云数据实验表明,针对大型点云点数目多,普通配准算法计算时间长的问题,采用K-D树进行配准算法加速,可保证精度,同时大大缩短了大型点云配准计算时间。

基于kd-MDD的时序图紧凑表示

时序图是顶点之间的连通性随时间变化的图,大规模时序图的紧凑表示和高效操作是分析和处理时序图数据的基础.提出了一种基于决策图的时序图数据紧凑表示方法——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表示时序图的优越性.

基于三维激光扫描的矿山法隧道超欠挖及平整度智能化检测

为了提高矿山法隧道施工过程中的超欠挖及平整度检测水平,将三维激光扫描与其他信息化手段结合,取得了一定的研究成果。但是,超欠挖检测主要采用断面法实现,未充分发挥三维技术优势;平整度检测主要通过最大凹凸点到拟合平面的距离进行计算,不符合现行规范的靠尺法要求。针对上述问题,利用切割、去噪、补全、降采样等算法,进行激光扫描点云预处理;通过聚类及BPA算法,将点云转化为空间三角网;借助三角网格投影及棱柱体体积积分,统计三维超欠挖情况;综合运用k-d树和八叉树算法,模拟靠尺法平整度计算流程,完成三维平整度计算。在实际工程项目中进行应用验证,最终实现矿山法隧道施工阶段的智能化超欠挖和平整度检测。

基于红黑树与K-D树的LiDAR数据组织管理

LiDAR点云是由海量的激光离散脚点组成的三维点集,在平面以及垂直方向上均分布有数量不均的离散点。LiDAR点云离散点相互之间缺乏空间拓扑关系,所以建立适当的数据组织结构对LiDAR点云进行组织是对LiDAR点云进行处理的基础。根据LiDAR点云的数据结构特点,利用红黑树与K-D树建立一种"非空"规则立方体格网和K-D树相结合的双层次数据结构,用于LiDAR点云的组织管理,从而降低结构冗余和提高索引效率。

基于K-D树的多维数据分布方法

系统地介绍了基于并行化k-d树的多维数据分布方法。给出了几种构造k-d树的策 略和相应算法，并从理论上分析和比较了各种策略的通信花费及其应用范围。

基于Hadoop的大数据查询系统简述

近年来,随着计算机技术的迅猛发展,其领域迎来了大数据时代。随着大数据的出现,传统的关系型数据库已经不能满足高储存量的要求,此时成本低廉、有着良好并行性和伸缩性的云数据库应运而生,它采用键值对数据模型和分布式的计算环境。但是海量数据在Key-value数据库中的查询效率低下、实时性差等问题又普遍存在。为了解决查询效率低下这一问题,将多维数据模型和索引技术应用于Key-value数据库,将事实数据以多维的形式进行存储并在多维模型上建立索引以加快查询速度。论文将系统地描述多维数据模型的建立和索引技术的实现,最后简单地和主流Key-value数据库进行优缺点对比。