论文部分内容阅读
[摘要]本文采用单坐标轴搜索方法快速确定点云的k紧邻信息，然后在保留所有边界点的基础上，结合测点的曲率特征以及k邻域内保留点的情况对点云进行非均匀化。结果表明，该方法能够在快速、有效地简化点云数据的同时保持原始特征信息。
[关键词]单坐标轴搜索法 三维激光扫描 散乱点云 边界提取 简化
[中图分类号] P217 [文献码] B [文章编号] 1000-405X（2015）-2-249-2
0引言
三维激光扫描技术是一门新兴的测绘技术，又称为“实景复制技术”，是测绘领域继GPS技术之后的又一次技术革命。该技术可以真正做到直接从实物中进行快速的逆向三维数据采集及模型重构，激光点云中的每个三维数据都是直接采集目标的实测数据，使得后期处理的数据完全真实可靠。由于技术上突破了传统的单点测量方法，其最大特点就是精度高、速度快、逼近原型，是目前国内外测绘领域研究关注的热点之一[1-3]。
但是，在快速获取被测物体的表面形状信息的同时，由于被测对象的复杂性，其测量数据密集而无序，并且随着激光扫描技术的不断提高，采样点精度达到亚毫米级，也因此产生了大量的冗余数据，既给数据存储带来不便，也对后续的曲面重构的效率与质量造成影响。特别是在被测曲面曲率较小的地方，点云过于密集可能导致重建模型的光顺度降低。因此，在保持被测物体的拓扑形状与几何特征，即能为模型重建提供必要信息的前提下，简化点云数据是十分必要的。
1单坐标轴搜索法原理介绍
根据删除一个测点会在曲面法方向上引起的误差大小作为点删除的依据。由于待重建曲面是未知的，删除一点后重建的曲面更是未知的，因此如何计算删除一点可能引起的法向误差是问题的关键：根据每个点Pi及其k近邻，用最小二乘拟合曲面在点Pi处的近似切平面T。由于Pi的k近邻真实地表达了待建曲面在Pi点附近的几何信息，即Pi点处的曲率越大，Pi的k近邻到切平面T的垂直距离就会越大[4]。因此，以测点近邻到其最小二乘切平面的垂直距离作为判断是否删除该点的依据是合理可行的，如图1示。
2散乱点云简化的预处理
2.1改进的散乱点云的 邻域建立
这里，对传统K邻域算法进一步修改，取得点云主体部分（即重要数据部分）的最小点间距dmin，以5-6倍dmin值作为中心点前后的距离参数dis，这样就能更好的根据不同规模不同精度的点云数据调节距离参数dis，提高算法的适应性。另外，在三个坐标轴单方向搜索完成后，只保留从三个坐标方向提取出的共同点参与最后的三维距离计算。
2.2微切平面法求曲率
由于是对散乱点的法矢估算，这里采用“微切平面法”。设点云中测点的集合P={p1，p2，…，pn}，任一点piCP的k邻域为N（pi），通过最小二乘法在pi点处对N（pi）进行拟合，构造出的近似切平面记作 T（pi），T（pi）的单位法矢即为pi点处的单位法矢■。
首先采用最小二乘进行平面拟合。即通过散乱点集P={p1，p2，…，pn}求出一张平面T（x，y，z），使任一点piCP到平面的距离的平方和最小：
■丨丨T（x，y，z）- pi 丨丨2 （1）
设所求平面的方程表达式为：
ax+by+cz+d=0 （2）
则平面法矢为：■=（a′，b′，c′）。由于平面方程中的参数a，b，c，d为线性表示，所以最小二乘平面的拟合属于线性最小二乘问题。系数a，b，c，d可以由数据点{pi（xi，yi，zi），i=0，1，…，n} 来确定。
由于最小二乘平面拟合的目标函数为：Ax=0，其中
由上小节知道，当上式中b=0时，可以用特征向量估计法（EVE），得到矩阵（ATA）绝对值最小的特征值λi及其对应的特征向量xi（i=1，…，4），即待求平面参数（a，b，c，d）T的最小二乘解。求解特征值和特征向量采用雅可比法[5]。
由于（a，b，c，d）T不是相对独立的参数，它们的值不是绝对的，因此必须要对矢量进行单位化处理：
pi点在局部曲面处的单位法矢为：■=（a′，b′，c′），这样便完成了对法矢的初步估算。
3边界提取、简化实验及结论
计算程序采用VB6.0在Core（TM） Duo CPU 2.0GHz、内存1G的计算机上实现，使用Auto CAD表现效果图，采用的点云数据为“Stanford Bunny”，由斯坦福大学计算机图形实验室使用Cyberware MS3030扫描仪得到的[6]。为了更好的验证基于保留边界点的精简方法是否能达到预期效果，这里将Bunny点云割出前半部分，以外轮廓作为模型的边界。
本文将dis 取为0.003m（大约是点云最小距离dmin 的5倍）， num取为50；k 为点近邻的个数，它的取值对实验结果影响较大，若取值过大则增加算法复杂度，影响效率，取值过小则无法完整描述点、曲面的几何特性。根据文献[7]提供的经验值，这里将k 的取值范围定为15-35， f为边界提取过程中的参数，为了突出效果先将f 取为0.3，图2分别为k 取15、25、35时的“兔子耳朵”边界图；边界参数f 的取值关系到边界点提取的准确性，这里将f的取值范围定为0.3-0.6。表1 给出了具体参数。
同时，这里也对“只有任意两个平面的两侧点数差与 的比值都大于一定的阈值 时，该点为边界点”进行验证：图3为只要求其中一个平面的两侧点数差与 的比值大于阈值，该点即为边界点的准则下提取的 “兔子耳朵”边界图， 图3为 取0.3， 分别取15、25、35。
由图2可以看出：k取15时无法很好的表达点云的局部信息，边界不完整，k取25、35时效果基本一致，边界保留情况较好，然而由于k取35增大了算法的复杂度，影响了实验效率，所以认为k取25较为合理。 并且，通过图2与图3的对比，可以看出文献提到的只要求其中一个平面的两侧点数差与k的比值大于阈值，该点即为边界点的规则，并不完善，许多非边界点也保留了下来，而本文采用方法则比较精准的提取出点云数据的边界。
Research of 3D laser Scanning Based On Single-axis Searching Method
Xin Cheng-zhang
Geology and Mineral Exploration and Development Bureau of Gansu Province，Gansu Lanzhou，730060
Abstract：This paper used a single axes searching method to gain the information of K-nearest neighbors of the points reserved，simplifies the other points according to the curvature and the proportion of reserved points in their K-nearest neighbors.The sesult shows that the method can quickly and effectively simplify the point cloud data at the same time to maintain the original features.
Keywords：Single-axis search method， three-dimensional laser scanning， scattered point cloud， boundary extraction， simplify
参考文献
[1]张弘.三维激光扫描点云简化算法研究[D].河海大学研究生院，2011.
[2]李新，王细洋.基于扫描线的三维激光扫描数据精简算法[J].机械设计，2010，27（4）：17.
[3]张艳丽，周儒荣，蔡炜斌，周来水.海量测量数据简化技术研究[J].计算机辅助设计与图形学学报，2001，13（11）：1019-1023.
[4]周儒荣，张艳丽，苏旭等.海量散乱点的曲面重建算法研究[J].软件学报，2001，12（2）：249-255.
[5]周长发.科学与工程数值算法[M].北京：清华大学出版社，2002.
[6]The Stanford 3D scanning repository.[EB/OL]. http：//graphics.stanford.edu/data/3Dscanrep/.2011-08-30/2010-07-01.
[7] 董秀军.三维激光扫描技术及其工程应用研究[D].成都：成都理工大学， 2007：11-12，18.
[关键词]单坐标轴搜索法 三维激光扫描 散乱点云 边界提取 简化
[中图分类号] P217 [文献码] B [文章编号] 1000-405X（2015）-2-249-2
0引言
三维激光扫描技术是一门新兴的测绘技术，又称为“实景复制技术”，是测绘领域继GPS技术之后的又一次技术革命。该技术可以真正做到直接从实物中进行快速的逆向三维数据采集及模型重构，激光点云中的每个三维数据都是直接采集目标的实测数据，使得后期处理的数据完全真实可靠。由于技术上突破了传统的单点测量方法，其最大特点就是精度高、速度快、逼近原型，是目前国内外测绘领域研究关注的热点之一[1-3]。
但是，在快速获取被测物体的表面形状信息的同时，由于被测对象的复杂性，其测量数据密集而无序，并且随着激光扫描技术的不断提高，采样点精度达到亚毫米级，也因此产生了大量的冗余数据，既给数据存储带来不便，也对后续的曲面重构的效率与质量造成影响。特别是在被测曲面曲率较小的地方，点云过于密集可能导致重建模型的光顺度降低。因此，在保持被测物体的拓扑形状与几何特征，即能为模型重建提供必要信息的前提下，简化点云数据是十分必要的。
1单坐标轴搜索法原理介绍
根据删除一个测点会在曲面法方向上引起的误差大小作为点删除的依据。由于待重建曲面是未知的，删除一点后重建的曲面更是未知的，因此如何计算删除一点可能引起的法向误差是问题的关键：根据每个点Pi及其k近邻，用最小二乘拟合曲面在点Pi处的近似切平面T。由于Pi的k近邻真实地表达了待建曲面在Pi点附近的几何信息，即Pi点处的曲率越大，Pi的k近邻到切平面T的垂直距离就会越大[4]。因此，以测点近邻到其最小二乘切平面的垂直距离作为判断是否删除该点的依据是合理可行的，如图1示。
2散乱点云简化的预处理
2.1改进的散乱点云的 邻域建立
这里，对传统K邻域算法进一步修改，取得点云主体部分（即重要数据部分）的最小点间距dmin，以5-6倍dmin值作为中心点前后的距离参数dis，这样就能更好的根据不同规模不同精度的点云数据调节距离参数dis，提高算法的适应性。另外，在三个坐标轴单方向搜索完成后，只保留从三个坐标方向提取出的共同点参与最后的三维距离计算。
2.2微切平面法求曲率
由于是对散乱点的法矢估算，这里采用“微切平面法”。设点云中测点的集合P={p1，p2，…，pn}，任一点piCP的k邻域为N（pi），通过最小二乘法在pi点处对N（pi）进行拟合，构造出的近似切平面记作 T（pi），T（pi）的单位法矢即为pi点处的单位法矢■。
首先采用最小二乘进行平面拟合。即通过散乱点集P={p1，p2，…，pn}求出一张平面T（x，y，z），使任一点piCP到平面的距离的平方和最小：
■丨丨T（x，y，z）- pi 丨丨2 （1）
设所求平面的方程表达式为：
ax+by+cz+d=0 （2）
则平面法矢为：■=（a′，b′，c′）。由于平面方程中的参数a，b，c，d为线性表示，所以最小二乘平面的拟合属于线性最小二乘问题。系数a，b，c，d可以由数据点{pi（xi，yi，zi），i=0，1，…，n} 来确定。
由于最小二乘平面拟合的目标函数为：Ax=0，其中
由上小节知道，当上式中b=0时，可以用特征向量估计法（EVE），得到矩阵（ATA）绝对值最小的特征值λi及其对应的特征向量xi（i=1，…，4），即待求平面参数（a，b，c，d）T的最小二乘解。求解特征值和特征向量采用雅可比法[5]。
由于（a，b，c，d）T不是相对独立的参数，它们的值不是绝对的，因此必须要对矢量进行单位化处理：
pi点在局部曲面处的单位法矢为：■=（a′，b′，c′），这样便完成了对法矢的初步估算。
3边界提取、简化实验及结论
计算程序采用VB6.0在Core（TM） Duo CPU 2.0GHz、内存1G的计算机上实现，使用Auto CAD表现效果图，采用的点云数据为“Stanford Bunny”，由斯坦福大学计算机图形实验室使用Cyberware MS3030扫描仪得到的[6]。为了更好的验证基于保留边界点的精简方法是否能达到预期效果，这里将Bunny点云割出前半部分，以外轮廓作为模型的边界。
本文将dis 取为0.003m（大约是点云最小距离dmin 的5倍）， num取为50；k 为点近邻的个数，它的取值对实验结果影响较大，若取值过大则增加算法复杂度，影响效率，取值过小则无法完整描述点、曲面的几何特性。根据文献[7]提供的经验值，这里将k 的取值范围定为15-35， f为边界提取过程中的参数，为了突出效果先将f 取为0.3，图2分别为k 取15、25、35时的“兔子耳朵”边界图；边界参数f 的取值关系到边界点提取的准确性，这里将f的取值范围定为0.3-0.6。表1 给出了具体参数。
同时，这里也对“只有任意两个平面的两侧点数差与 的比值都大于一定的阈值 时，该点为边界点”进行验证：图3为只要求其中一个平面的两侧点数差与 的比值大于阈值，该点即为边界点的准则下提取的 “兔子耳朵”边界图， 图3为 取0.3， 分别取15、25、35。
由图2可以看出：k取15时无法很好的表达点云的局部信息，边界不完整，k取25、35时效果基本一致，边界保留情况较好，然而由于k取35增大了算法的复杂度，影响了实验效率，所以认为k取25较为合理。 并且，通过图2与图3的对比，可以看出文献提到的只要求其中一个平面的两侧点数差与k的比值大于阈值，该点即为边界点的规则，并不完善，许多非边界点也保留了下来，而本文采用方法则比较精准的提取出点云数据的边界。
Research of 3D laser Scanning Based On Single-axis Searching Method
Xin Cheng-zhang
Geology and Mineral Exploration and Development Bureau of Gansu Province，Gansu Lanzhou，730060
Abstract：This paper used a single axes searching method to gain the information of K-nearest neighbors of the points reserved，simplifies the other points according to the curvature and the proportion of reserved points in their K-nearest neighbors.The sesult shows that the method can quickly and effectively simplify the point cloud data at the same time to maintain the original features.
Keywords：Single-axis search method， three-dimensional laser scanning， scattered point cloud， boundary extraction， simplify
参考文献
[1]张弘.三维激光扫描点云简化算法研究[D].河海大学研究生院，2011.
[2]李新，王细洋.基于扫描线的三维激光扫描数据精简算法[J].机械设计，2010，27（4）：17.
[3]张艳丽，周儒荣，蔡炜斌，周来水.海量测量数据简化技术研究[J].计算机辅助设计与图形学学报，2001，13（11）：1019-1023.
[4]周儒荣，张艳丽，苏旭等.海量散乱点的曲面重建算法研究[J].软件学报，2001，12（2）：249-255.
[5]周长发.科学与工程数值算法[M].北京：清华大学出版社，2002.
[6]The Stanford 3D scanning repository.[EB/OL]. http：//graphics.stanford.edu/data/3Dscanrep/.2011-08-30/2010-07-01.
[7] 董秀军.三维激光扫描技术及其工程应用研究[D].成都：成都理工大学， 2007：11-12，18.