导读:本文是一篇关于数据算法论文范文，可作为相关选题参考,和写作参考文献。

(河海大学 江苏南京 210098)

摘 要:近年来,三维激光扫描技术在医学、工业、土木工程领域有着广泛的应用前景,三维激光扫描点云数据预处理技术也成为研究的热点.本文主要从云去噪与平滑、点云配准和点云精简三个重要环节讨论了点云数据的预处理技术过程.

关键词:点云 点云去噪 配准 点云精简

中图分类号:TP391.7文献标识码:A文章编号:1674-098X(2011)11(b)-0027-02

在通过计算机将现实世界数字化的过程中,传统简单的的二维图像显然已经不能满足社会的需求,而三维激光扫描技术相对于传统的二维技术更具有独特的优势.随着三维激光扫描技术的发展,基于点云数据的三维数据模型已经日趋成熟,并广泛的运用于军事、机械、电子、影视等各个专业领域,并产生了深远的影响.

三维激光扫描技术是通过仪器测量现实世界中真实存在的物体,获取物体表面的基本点云数据,然后通过数据处理在计算机中生成相应的三维数据模型,即点云模型.点云模型具有存储简单、处理灵活、三维细节能力强等特点,点云模型也成为近年来的研究热点.

三维激光扫描技术所采集的点云数据往往具有数据量庞大的特点,同时由于采集过程中不可避免的存在各种误差使得点云数据中产生噪声点,因此往往需要对点云数据进行预处理以期最大程度的还原物体的真实性.本文着重介绍点云去噪与平滑、点云配准和点云精简三个重要环节.

数据结构与算法:数据结构与算法01 浙江大学 全60讲 零基础自学

1.点云去噪与平滑滤波

由于测量过程中的由于各种测量误差和随机误差,例如测量仪器的震荡、被测物表面粗糙不平、镜面反射、遮挡物遮挡等各种因素,均会使所测点云数据中不可避免的存在着不合理的噪声点.所以在对点云数据进行处理之前,首先要进行去噪与平滑工作.

对于点云去噪的研究,国内外已经展开了大量的研究,并提出了许多行而有效的方法[1],而这些处理方法主要与获取点云的排列形式密切相关.点云排列形式一般分为有序或部分有序排列和无序排列.对于有序或部分有序排列的点云数据中当中的噪声点的处理,通常按照扫描线采用平滑滤波的方法进行处理.而对于无序点云,由于点云自身点与点的拓扑关系尚未建立,所以目前对于无序点云数据的去噪处理还没有一个简单、便捷的方法.

1..1 有序或部分有序点云去噪算法

对于有序或者部分有序的点云数据,由于其点与点的拓扑结构较为完整,所以针对这类点云数据去噪处理技术较为成熟,可以采用的去噪算法很多,例如最小二乘滤波和卡尔曼滤波、邻域平均法、孤立点排异法,对于部分点云数据也可以采用局部算子对其进行局部滤波处理已达到更满意的效果.目前应用最为广泛的是平滑滤波算法,平滑滤波算法通常分为高斯滤波、中值滤波和平均滤波三种算法,其中高斯滤波能够较好的保持原始数据的原貌,中值滤波则主要用于消除数据毛刺,而点云数据平均滤波效果较为平均.在实际的使用过程中,则可以根据原始数据特征和后续数据处理级建模需求灵活使用合适的滤波算法.

1..2 无序点云去噪算法

而无序点云数据由于点与点的拓扑关系尚未建立,所以上述滤波算法无能为力,但是我们只要在散乱的点与点之间建立合适的拓扑结构模型,即可进行去噪处理.国内外对寻找点与点之间拓扑关系进行了大量的研究,常见的处理方法主要有以下三种:

(1)八叉树法:主要基于八叉树的方法来分割点云,然后根据包围盒与数据点空间分布的对应关系,便建立点的拓扑关系,

(2)空间单元格法:在三个方向上按照一定的间隔分别创建一系列平行平面,把包围盒划分为许多单元格,取各单元格中最靠近单元格中心的数据点作为中心点,代替整个测量数据,即可建立点的拓扑关系,

(3)法:的方法通常用来查找距离最近的两点,是一种便于空间中点搜索的数据结构.

2.点云配准

在利用三维激光扫描仪对北侧物体进行点云数据采集时,由于仪器视角以及环境的限制,往往需要多次测量才能完成.因此每次测量仅能得到被测物基于某一特定坐标系的部分点云数据,为了得到基于同一坐标系的完整数据,以便于后续三维模型的建立,就需要考虑将不同视角的坐标系转换到同一坐标系中,对局部点云数据进行整合与配准,即点云配准问题.

点云配准一般分为初始配准和精确配准两步.初始配准是为了缩小点云数据间平移、旋转错位,使精确配准不至于趋于错误的方向,常见的初始配准主要有中心重合法、标签法、特征点(线、面)提取法等等,最后一种方法往往用于点云数据具有明显的特征.为了尽可能的使不同点云之间配准误差达到最小,还需要在初始配准的基础上进行精确配准.利用初始数据进行精确配准,最著名是和提出的最邻近点迭代算法,即算法.

2..1 ICP算法

算法[2]是目前应用最广泛的点云配准算法.算法的基本思路是:在相邻点云中搜索确定最邻近点对,利用找到的最近点对通过和所提出的严密解算过程计算被测物的变换参数,点对的搜索及变换参数的解算均采用迭代计算,直到目标函数值控制在可承受范围内,停止迭代过程.

设为两个点集,且,ICP的处理过程如下:

(1)设定两个点集的初始变换参数为已知.

(2)搜索最邻近点对:通过变换参数对点集中的每一个点进行变换,即,再从中寻找与其最邻近点,这样便得到点对.其中表示迭代次数,,.

(3)利用找到的最近点对进行配准变换,以所有最近点对距离平方和最小为标准来解算被测物的变换参数.

(4)当相邻两次计算值之差小于指定阈值时,算法结束,否则一直重复2～4步.

2..2 改进算法

上述的算法虽然能够基本满足精确配准在精度上的要求,但是还存在着运算效率不高、运算时间过大的缺陷,这在处理大量点云数据时将耗费大量时间.为了提高运行效率,降低计算时间,研究人员展开大量研究,主要在点的选择、对应点确定标准、算法的稳健性等方面展开,得到多种改进算法.

文献[3]提出一种由曲率的RGB值来选取拼舍的重叠子集,通过改进的ICP算法来实现重叠子集的拼舍,实现了再目标点云中局部最优的整体拼合.文献[4]首先通过标签法寻找对应的点对,计算变换矩阵完成点云的初始匹配,然后运用KD-Tree的空间搜索策略,通过计算点云之间的重叠部分来缩小ICP算法的迭代区域,最后给出对应点对的约束条件,通过删除错误的对应点对以提高有效性.文献[5]通过引入被测物的特征点,运用最小二乘算法求出初始变换矩阵完成粗略配准.然后采用K—D树来加速搜索最近点,用均方距离作为误差度量准则实现了改进后的最近点新的迭代算法,进一步得到了很好的精确配准效果.文献[6]利用MATLAB中封装的三角剖分函数,加速搜索迭代过程中的最近点,简化ICP配准算法的实现,并设计一种模拟实验的方法验证算法的有效性,有效的达到较好的配准精度.

3.点云精简

通过三维激光扫描仪获取的点云数据往往十分密集,而去噪平滑处理仅能去除很少一部分数据点,数据量仍旧很大.这些冗余的数据使得计算效率,存储效率都低.所以在保持数据精度的前提下,精简数据扫描点云数据量就显得尤为必要.

一般点云数据的排列方式可以分为以下四种:1)扫描线式点云数据,2)阵列式点云数据,3)三角网格式点云数据,4)安全散乱式点云数据.针对第1类和第2类点云数据,可根据其点云特征按扫描线逐行精简的原则处理,如最小距离法、均匀采样法.而对于后两种点云数据,一般着重于如何减少三角形网格的数目问题上[7].

3..1 最小距离法

该方法是基于一个最小距离阈值的精简方法,基本原理是:设定一个最小距离,然后沿着扫描线的方向逐个比较相邻两点间的距离,若则剔除后一点.依次判定所有扫描线.当扫描线中的数据点十分密集,且整体曲率变化缓慢时,该方法效果较为明显.

3..2 均匀采样法

该法根据点云数据的存储顺序,设定采样率,每隔个点就采集一个点,其余点均忽略不计.该法运用于有序点集时即为等间距采样法,运用于无须点集时,称之为随机采样法.该法精简速度很快,可节约大量时间,但算法稳定性受测点存储方式影响较大.

3..3 包围盒法

包围盒法是通过体包围盒来约束点云,然后按照一定的方法将体包围盒分割成若干个校包围盒,选取每隔小包围盒最靠近中心处的数据点代表这个包围盒包含的所有点集.经过该方法处理后的点云数目即为小包围盒的数目.包围盒的优点是简单、高效,并易于实现,但是在点云密集处很容易丢失细节.

3..4 均匀与非均匀网格法法

首先在垂直与扫描方向的平面内建立若干个均匀或非均匀的小方格,那么每一个数据点都被分配给某一个方格内.然后计算出这一点到方格的距离d,将所有分配到同一方格的数据点按距离大小依次排列,取中间值的数据点来代表所有分配于这个方格中的数据点,其余点则被剔除.

这种方法克服了均值和样条曲线的限制,有效的减少了点云数目,同时可以通过对网格大小等特征的控制一定程度的保持物体的基本外形特征.但是对于较为集

来源【首席数据官】，更多内容/合作请关注「辉声辉语」公众号，送10G营销资料！