激光扫描点云数据预处理

三维激光扫描测量技术的出现提供了一种高效率、高分辨率、高精度的三维空间信息获取方式，它能从复杂实体或实景中重建目标的全景三维数据及模型，是一项集光学、机械、电子及计算机等技术于一体的新型测量技术。三维激光扫描测量技术突破了传统的单点测量方式，最快可以以每秒上百万点的测量速度获取目标表面较为完整的三维坐标，同时可以记录目标物的激光反射率和回光强度等特有信息，与相机标定后还可以获取色彩信息，其测量精度在一定距离内可达到毫米级甚至亚毫米级，能够快速把物体表面的三维信息较完整地转换成计算机可直接读取、处理并输出的点云数据。

主要有以下特点：

1) 数据的海量性。现有的相位式激光扫描仪最快测速可超百万个点每秒，扫描获取的点云数据量一般远远大于其他点云获取方式。

2) 数据的不均匀性。由于地面三维激光扫描仪从单点发射激光进行测量，导致距测站近的位置数据稠密，距测站远的位置数据稀疏，不像其他点云获取方式可以人为控制在测量目标不同位置处的测量间隔。

3) 坐标系的随意性。由于测量设站的随意性，各测站之间的测站坐标系关系未知，需要事后进行坐标系的统一。

4) 数据的散乱性。由于扫描目标的不规则性、激光扫描设备多次回波探测能力、多站数据拼接及数据另存和更改等因素，不能保证点云数据都按照类似扫描线等具有邻接拓扑关系的数据类型进行存储，导致后续数据处理的对象一般是散乱点。

5) 噪声的多样性。主动无接触式测量受环境干扰可能产生非测量目标物体表面的无用数据和离群噪声，物体表面的特征可能导致测量产生毛刺噪声，无合作目标的激光测距方式必然产生细小的随机噪声。

6) 数据的信息量丰富。激光扫描测量不仅可以获取目标物表面的三维坐标信息，与相机正确标定可以获取色彩信息，同时还可以获取物体的回光强度和反射率等特有信息。

___

点云数据量大、范围广等特点导致内业数据处理耗时长、过程复杂，并且需要专业人员采用专业软件进行处理；建立模型的精度一般为毫米级甚至更低，不能满足部分应用领域对测量精度的要求。

因此,提高海量数据存取与处理的速度、精度及自动化程度是激光扫描数据处理发展的必由之路。

激光点云数据的预处理是激光点云数据处理首先要完成的一步，主要包括

• 数据组织
• 多站拼接
• 简化压缩
• 去噪光顺

一、背景

1.数据组织

1.1 分析目标的局部特征

直接利用单个点的三维坐标不能得到测量目标的表面信息，一般都要根据点之间的邻接关系确定一定数量的局部点集用于分析目标的局部特征；计算每个点的法矢和曲率信息也是不可或缺的一步，是点云数据处理中一些后续算法的基础。针对散乱点云，需要对点云数据进行组织，建立点与点之间的邻近关系，进而恢复法矢和曲率等信息。

对海量激光点云数据进行处理的前提是能够对其进行合理存储与快速读取。单站三维激光扫描测量获取的点云数据如果按照文本文件存放，文件大小一般在百MB至GB量级。若想有效、快速地对如此大的数据进行操作，就必须对数据进行合理的存放与读取。目前对点云的存储主要可分为ASCII格式和二进制格式两种类型。以ASCII码表示，数据查看比较方便、读写操作容易且兼容性好，但占用存储空间一般比较大；二进制存储方式数据保密性好、节省空间且数据导入导出比较高效，但为了跨平台处理一般需要文件解码。

1.2 利用数据结构将点分块管理,以此实现邻近点的快速搜索

计算机的处理能力有限，要对海量数据进行高效的数据查询、数据显示处理，就需要设计数据在内存中的结构。为了对点集进行分析，就必须已知每个点的局部趋势，对于散乱点集中的某一点，离它近的点对其影响大，远的点对其影响小，这就需要临近搜索算法。

利用数据结构将点分块管理，对点集进行遍历处理时，就只需先寻找各点在数据结构中所在的数据块，之后在所在数据块中及邻近数据块中寻找邻近点，以此实现邻近点的快速搜索。只有建立点云数据邻近结构，其表面的法矢和曲率等信息才能得以正确、高效地计算。

点云数据常用的数据结构包括均匀格网结构、k-d树结构及八叉树结构等。

• 均匀格网结构简单，但此结构依据数据范围进行划分，比较浪费空间，没有依据点云数据的分布进行划分导致其不具有自适应性；
• k-d树结构依点建立结构，但点数多时划分层次也相应增多，并且数据添加与删除都会导致结构的变化；
• 八叉树仅保存包含数据的节点，比较节省计算机内存空间，而且八叉树结构与点云数据相对独立(k-d树将节点建在点上)，数据的添加与删除比较方便易行。

2.多站拼接

机载、车载和手持式激光扫描测量系统由于进行了空间标定，一般不存在多站拼接问题。

但作为一种主动式非接触测量设备，地面三维激光仪为了获得物体的全景数据，需要多次设站进行扫描测量。另外，在对一些特殊目标进行测量时可能会遇到一些需多位置设站进行扫描的情形，如在对某弧形目标进行扫描时，如果激光的入射角(激光入射方向与物体表面夹角)过大，获取的点云数据随机误差就会占据很大一部分，以至得到错误的测量结果，需要多次设站对入射角过大的区域进行重测，保证每一个部位都有小入射角测量的结果。这样得到的多站数据就需要进行拼接处理。

针对多站激光点云拼接技术的研究一直是地面三维激光扫描测量数据预处理的研究热点，其高精度与自动化是研究的重点。

现有的点云数据拼接方法按照拼接精度主要分为粗拼接法和精拼接法两类。

• 粗拼接的目的是确定一个初始的坐标变换模型，将不同坐标系下的点云大致统一到一个全局坐标系下，适合精度要求不是很高的场合，或用于为精拼接提供一个良好的初始值。
• 精拼接法以Besl等提出的迭代最近点算法(iterative closest point，ICP)为代表，ICP算法最初应用于图像配准中，现在已被广泛应用于点云数据拼接中，具有很高的精度，但也存在一些较难解决的问题，这些问题也是目前学者对ICP算法的研究重点。

3. 简化压缩

3.1 保持模型特征的前提下缩小信息存储量

由于激光扫描设备测量速度非常快且扫描范围广，得到的原始激光点云数据量很大，对大量的数据进行存储和处理是一个很难突破的瓶颈。并不是所有的数据点对模型重建都有用，如果直接对海量点云进行处理，从数据点生成模型需要很长的处理时间，整个建模过程很难控制。因此，有必要在保证精度且保持模型特征的前提下减少扫描数据量，从而达到缩小信息存储量、提升处理速度并能保证几何造型和加工精度的目的，这就需要对点云数据进行简化压缩处理。

3.2 简化压缩方法

目前点云数据的简化压缩方法可主要分为可保持特征的简化法和不能保持特征的简化法两类。

不能保持特征的简化法主要有简单采样法、网格采样法和角度法等。

• 简单采样法是一种较为常用的方法，主要是通过均匀采样、随机采样或按距离采样等方式实现数据简化；
• 网格采样法是通过保存均匀网格或八叉树网格等的重心点(距离网格中心最近的点)实现数据简化，采样结果分布均匀，结果的点数等于网格的个数；
• 角度法的基本原理是选取点云数据中相邻三点，根据中间点与相邻两点连线间的夹角与阈值比较进行数据筛选，此类方法具有简单易行、效率高等优点，但其共有缺点是对特征不敏感，不能保证有效保持特征。

保持特征的简化法主要有曲率采样法等。曲率采样法的原则是小曲率区域保留少量的点，而大曲率区域则保留足够多的点，以精确完整地表示曲面特征，是一种根据物体的几何特征，对测量数据点云进行精简的方法。此类方法能较准确地保持曲面特征并有效减少数据点，但缺点主要是处理效率较低。

4.去噪光顺

激光扫描测量得到的激光点云数据不完全是有效数据，还包含了遮挡点、错误点等噪声点和测量随机误差点等。如激光入射角过大得到的错误结果人工很难剔除干净，需要通过一定的算法将之有效地剔除；

4.1 特征保持和噪声去除是一对相互矛盾的过程

在激光点云中，由于孤点和离群点等大噪声点存在“离群”特性，一般比较容易去除，可将其作为“去噪”的研究对象；毛刺点等小噪声点通常与突变特征具有某种几何上的相似性，需要在光顺与特征保持之间作有效的权衡，可将其作为“光顺”的研究对象。在实际处理过程中明确判定特征和噪声是非常困难的，特征保持和噪声去除是一对相互矛盾的过程。从数据处理角度讲，对于某一小块数据，大噪声一般仅占很一小部分，小噪声分布在较小的范围内，如果噪声过多过大说明测量结果数据不正确，从而无法有效处理。

由于大噪声一般是错误或无用的数据，因此针对大噪声的处理一般采用去除的方式。目前对离群点和孤点的去除主要采用人机交互的方式，也有学者采用基于平均距离传递的方式进行自动去除。

由于小噪声与物体表面数据比较接近，一般是正确数据包含了细小的误差，如果直接去除可能会导致表面数据产生空洞，因此对小噪声的处理一般采用调整的方式，但也有些学者采用将其删除的方式。目前已有的点云光顺方法很多是从图像降噪处理方法的基础上发展而来的，根据算法的最初应用对象可将其归纳为针对点云三角网化数据(有序或部分有序点云数据[9]，结构化后的点云数据)和直接针对散乱点数据两种类型。

针对点云三角网化数据的光顺方式主要有拉普拉斯法、平均曲率流和双边滤波法等。这些方式主要利用三角网各顶点的一层邻域顶点、一层邻域三角形或二层邻域三角形等空间邻域信息或法矢和曲率等表面属性信息对顶点进行调整，在建立散乱点的邻近关系、计算法矢及曲率信息的基础上，针对三角网数据的光顺方法，事实上也可以应用到激光散乱点云光顺中。

针对散乱点数据的光顺方法主要有基于Mean Shift法、基于小波变换法和基于局部曲面逼近等。这些方式主要通过恢复点之间的邻近关系，寻找各个点周围的邻近点进行局部表面分析，利用聚类或拟合面对比等方式将点沿一定方向向聚类中心或局部拟合面调整。针对此类数据的光顺方式离不开点间邻近关系的确定，导致效率低问题不可避免。

二、研究

1.数据结构-八叉树与KD树结合

1.1 八叉树的改进

八叉树最小分割粒度（叶节点）的确定随着点云数据的增多，成为制约其效率的主要原因。

最小分割粒度太小，则查找效率随着深度增加而降低。

最小分割粒度太大，则叶节点分配到的点数量随着点云分布不均匀程度及数据量增加，叶节点中查找效率降低。

因此，需要对叶节点进行二次组织，基于KD树在领域检索方面的优势。

在全局索引八叉树的叶节点加入KD树索引管理小区域点云数据。

最后利用LOD建立层次细节模型对不同层次点云可视化快速实现。

1.2 八叉树实现

八叉树是描述三维空间的模型，每个节点代表一个体积大小固定的正方体，每个正方体可以分成8个相等的子正方体，父正方体是8个子正方体体积之和。

在数据叶子节点上层构建八叉树组织结构：

• 1、设置最深递归深度
• 2、建立第一个立方体，范围是所有点云数据的最大范围。
• 3、把点云数据依次存入没有子节点而且在其范围中的立方体。
• 4、如果没有达到最深递归深度，对立方体8等分，再用8个立方体分别存入各自范围内的父立方体所存的点元素。
• 5、如果子立方体所存储点云元素数量与父立方体相同且不为0，应停止细分。
• 6、递归3-5，直至最深深度。

1.3 KD树实现

每个节点为K维点的二叉树。所有非叶子空间作为超平面将一个空间分割成两个小空间。

选择超平面的方法：K维中垂直于超平面的一维用来划分每个节点的归属。

KD树将整个空间划分成几个特定部分的空间划分树，与它相关的查找操作在特定空间内部进行。

1.4 点云

原始点云数据中没有明确的对应几何拓扑信息，称之为散乱数据点。

点云拓扑关系根据领域关系进行估算，进而估算几何信息（邻接关系，曲率大小，微切平面，数据点单位法向量）

2.八叉树与三维R*树集成的激光点云数据存储结构

2