基于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算法,本算法能够更为精确地识别出散乱点云中的边界点,实用性强。

基于形状特征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个特征矩阵中至少两个特征值相同来识别该区域是否被篡改;引入随机抽样一致性策略,降低图像块的误匹配率,提高检测精度。实验结果表明,与当前图像伪造检测技术相比,该检测算法的检测精度更高,能有效识别出旋转、缩放、模糊以及噪声等伪造形式。

基于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表示时序图的优越性.

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

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

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

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

用K-D树实现对双模态多媒体数据库的有效查询

论文提出了一种用k-d树来查询双模态视觉听觉语音识别数据库的方法。这种方法揉合了查询地理信息系统的多维数据库和空间数据库的方法,结合双模态视觉听觉语音数据库自身的特点提出了在数据库中插入、查询和删除记录的算法。最后还对把查询多维数据的方法应用在双模态语音识别数据库领域进行了展望。

基于四叉树的SIFT与K-D树融合的图像匹配研究

为了解决SIFT算法在立体视觉中耗时长、误匹配度高以及提取的特征点扎堆的问题,提出一种基于四叉树的SIFT与K-D树融合的快速特征匹配算法。该方法采用一种结合了自适应阈值的快速特征点提取算法提取关键点,由于所提取的关键点具有扎堆现象,故提出一种四叉树结构并将其应用到图像匹配中。利用改进的K-D树与随机一致性算法进行关键点的粗匹配与提纯。实验证明,该改进算法的平均匹配速率相比SIFT算法提高了3.35倍,匹配正确率由86.18%提高到97.53%,同时该改进算法比SIFT算法在视角、模糊、光照以及尺度变化方面更具有优越性,所以该算法能够满足高匹配率、实时性好且特征点均匀化的要求。

频谱感知中的K-D树KNN-SVM算法研究

传统的特征值检测法需要计算信号检测统计量和检测阈值,在不同的应用场景下,需要运用不同的特征提取算法来提取信号特征,却难以找到合适的特征提取算法。基于此文中提出一种改进的基于特征向量的K-D树KNN-SVM联合分类器算法。该算法相比传统的特征值检测法,无需计算检测统计量和检测阈值,且在KNN部分将训练样本排列成K-D树结构,可以大大减少KNN部分的冗余计算,使得支持向量机在分类超平面模糊时,加快K近邻算法的搜索速度。仿真实验结果表明,在选定最佳参数的K-D树KNN-SVM联合分类器中,相比KNN或SVM频谱感知算法,其检测性能明显提高,且检测效率也比KNN-SVM高。

水声目标识别中的K-D树KNN-SVM分类器研究

常规的KNN-SVM联合分类器中K-近邻算法没有充分挖掘训练样本的信息,使用遍历的方法来计算待识别样本与训练样本之间的距离,特别是在训练样本巨大时,存在大量的冗余计算。针对该问题,将训练样本训练成K-D树的结构,设计了K-D树KNN-SVM分类器,该分类器可以大大减少这些多余的计算,从而提高了搜索效率,有效缩短了搜索时间。进行了仿真和实验研究,分别设计了KNN、SVM、KNN-SVM分类器对两类水下目标进行了分类识别,并对相关参数的选取进行了优化。实验结果表明:在选定了最佳参数后的KNN-SVM联合分类器较其它两类分类器在识别率和识别效率方面都是最佳的;采用了K-D树结构的KNN-SVM联合分类器中KNN部分识别效率要比常规的高约7.5倍。