拟万有引力定律三维激光点云数据精简方法

邓博文　王召巴　金永

摘要：为对海量三维激光点云数据进行精简，提出一种拟万有引力定律的点云数据精简方法。该方法将万有引力定律中各点质量替换为点的切向与径向联合曲率表征参数，通过求解点云中各点之间的引力分布，实现点云数据平坦与特征区域的划分，完成点云数据中特征点的提取与保护。将非特征区域点大比例均匀采样，再与完整的特征点融合形成精简后点云数据，将其与原始点云进行对比，结果表明：该精简方法在有效保留特征区域的基础上可以大比例精简点云，同时精简前后点云点距离误差较小。在总精简比94%时，最大点间距离偏差值为0.1 mm，且高偏差值点均位于非特征区域。

关键词：信号处理；三维激光点云精简；万有引力定律；特征点保护

文献标志码：A 文章编号：1674-5124（2018）05-0108-05

0引言

三维激光点云数据是指物体经过三维激光扫描系统扫描后在空间坐标系下表征物体表面特征的海量点集。随着三维激光扫描系统检测精度和速度的大幅提高，点云数据的量级可达千万甚至更大。一般的点云数据处理方法是先对其进行网格化，而随着点云数据量的增加，网格化的时间以及内存开销急剧增大，同时，管理、操作以及处理网格拓扑信息的复杂程度也随之急剧增加；此外，当多网格模型在屏幕中网格数量大于屏幕分辨率时，用点作为模型数据的基本单元比多边形网格有更加明显的效率优势。Levoy等提出了基于点的点云数据处理概念，成为计算机图形学的研究热点。然而，海量的数据依旧会造成处理的困难，因此，研究点云数据的压缩、精简方法就具有重要的意义。

HUANG Y等通过对八叉树结构生成的细节层次树进行渐进式编码，在后续的研究中，FAN等对点云数据进行一系列自下而上的聚类，生成了一颗细节层次（Level of Details）树，对树进行由根到葉的遍历，在遍历过程中，对遍历节点进行编码，实现了对原始模型的编码压缩。文献中也使用了相似的基于八叉树结构的渐进编码技术对点云数据进行编码压缩。杨岳湘等通过行小波编码对三维数字高程模型（DEM）数据进行编码压缩，取得了良好的压缩效果。方芳等将散乱点云数据进行切片，然后对切片后的“片点云”通过弦高差法逐层进行特征点保留，实现了数据的压缩，而在后续的研究过程中，徐工等在对散乱点云切片后，对其进行小波变换，利用小波系数峰值，自适应地保留特征信息，实现散乱点云的自适应压缩。杨璐璟在其硕士学位论文中提出了一种“曲率一法矢量”算法，本质上是通过计算点云数据中各点的曲率和法矢量，在不同的曲率范围内采用不同的法矢量夹角阈值进行采样，从而达到精简点云数据的目的。陈俊宇等通过设定点云间最大误差值，而后对点云进行统一采样，实现了点云数据的有效精简，然而该方法由于采用统一采样可能会造成特征点的丢失。刘迎等使用KD树对点云进行划分，在此基础上使用主成分分析法求取各点的曲率，从而实现了点云特征的提取，而后对点云进行特征点的精简，该方法可以有效保护特征同时精简点云，然而该方法需要遍历海量点云数据，无法避免的占用大量的计算资源并且需要大量计算时间，降低了点云精简的效率。类似的研究还有很多㈣。上述方法分为两类：1）需要在三维空间中对点云进行划分，而后求取点云的局部拓扑关系，进而对其微分几何性质进行计算，对于本文将使用的海量点云数据而言，其微分几何性质的计算十分耗时：2）需要对点云数据进行全局遍历，用以生成八叉树、KD树或是LOD树，从而在子叶节点上对点云数据进行精简，无疑该类方法对于本文将使用的海量点云来说同样是代价巨大的。

为实现基于实际几何尺寸的回转体构件的虚拟装配，前期开发一种基于龙门结构的回转关节臂式激光扫描系统（RAMSGL）。该测量机可以快速、精确地测量回转体构件的表面信息，且获取的点云数据量十分巨大。因此，本文旨在分析点云获取方式的基础上，开发出一种高效、准确的点云精简算法。

1点云数据的获取及分析

1.1点云数据获取方式

如图1所示，本文的检测对象是一个半径l 10mm盲法兰，法兰盘上有高为3mm的台阶面，以及均匀分布的6个直径8.5 mm的通孔，每个通孔都有一个0.5 mm的倒角，此外，法兰盘外边缘也存在一个相同尺寸的倒角。

图2为RAMSGL获取近似有序点云数据的方式简图，扫描部件选用基恩士公司生产的LV7080型二维线激光传感器。紫色粗体线条为二维激光光线，紫色粗体虚线为转过一定角度后的激光光线，需要指出的是，激光光线始终与直径共线。二维激光传感器逆时针旋转一周，每隔0.03。采集一次数据，每条激光光线上包含800点数据，点与点之间间隔0.05mm。由于数据量巨大，为使结果更加清晰，选择图1中黑色扇形区域标出的工件部分（点元数据量为2 885 229（2 837xl 017）点进行后续研究，也不会影响算法的一般性。图1中黑色扇形区域所标出的工件的点云数据量为2 885 229（2 837xl 017）点，后文将不再强调该黑色扇形区域。

1.2点云数据分析

图3（a）为点云数据原始三维图像，由于待测法兰的特征差异方向集中在Z轴方向，为了方便观察，本文将该区域以一个矩形（即以点云矩阵的行列）方式在X-O-Y平面上进行投影，并以Z方向数值作为灰度值进行显示，如图3（b）所示。

从图中可以看出，点云数据相当密集，平坦区域（即图3（b）中灰度基本一致区域）有相当大的点云密度，点云中存在大量的冗余数据。

1.2.1点云数据径向分析

分析点云数据的获取方式可知：在每条激光光线方向（径向）上，点云数据代表着被测法兰沿半径方向的—个截面轮廓，如图4所示为一条分割圆孔的点云数据。该轮廓含有台阶面、通孔倒角、通孔以及法兰外边缘倒角等特征，这些特征在Z轴方向上表现出明显的曲率变化。因此，本文采用Z轴方向的曲线曲率作为表征参数。

曲线曲率就是针对曲线上某个点的切线方向角对弧长的转动率，通过微分来定义，令弧长MM的切线转角为△α，弧长为△s，M处的曲率为K=dα/ds。

根据式（1）也可求出该轮廓截面关于Z轴的径向曲率分布，如图5所示。图中有3个明显的峰值，对比图4可知，第1个峰值出现在台阶面位置，后两个峰值分别位于直径分割圆孔的两侧，同时可以看到，圆孔两侧以及点云末尾存在3个小的凸起峰，这是由圆孔周边以及法兰外沿倒角造成的，而这些峰值所处位置正是点云数据压缩时应该保持的位置。其余平坦区域的曲率变化平缓。

1.2.2点云数据切向分析

在被测法兰的切线方向上，每条点云数据代表着不同半径轮廓圆的表面特征值，如图6所示为一条穿过圆孔的轮廓圆的点云数据，可以看出，通孔及其倒角处，曲线的曲率发生了明显的变化。

同理，通过式（1）求出轮廓圆关于Z轴的切向曲率分布，如图7所示。图中的峰值依旧出现在圆孔的两侧，两侧的倒角也同样造成了小的突起峰值。但是，由于在切向，代表台阶面或法兰外沿的点云曲线并不具有明显的起伏，因此台阶面及法兰外沿并没有在切向曲率分布中被表征出来。由于每一点的切向方向与径向方向彼此近似正交，因此，为了将各种特征都表征出来，借鉴平均曲率的概念，得到联合曲率为

切向与径向曲率的“联合曲率”准确地将台阶面、圆孔表征了出来。但是，却无法明显将台界面倒角、圆孔倒角以及台界面切相面识别出来，而这些点同样是工件重构的重要特征点，如果无法准确识别，无疑会对后续的精简的精度产生影响。因此，本文提出了一种拟万有引力的压缩方法。2拟万有引力压缩方法

万有引力定律的具体表述为：任意两个质点有通过连心线方向的力相互吸引。

本算法将质点质量替换为该点联合曲率，并求取每点3阶邻域内引力的“合力”，如图8所示为点“受力”简图。

图中P_i为P点3阶邻域内的点，两点间的欧氏距离为

点云数据中各点的受力为

从图中可以清晰地看到，台阶面、圆孔以及各倒角特征被保留下來，为后续压缩工作提供了保障。通过cloudcompare软件对比精简前后数据，以点之间距离误差为颜色索引进行显示，从蓝色至浅黄，距离误差逐渐由0增大至0.1 inln，结果如图10所示。总精简比为94%时，最大点间距离偏差为0.1 mm，且偏差值点均集中在非特征区域。

3结束语

针对由线激光传感器扫描系统RAMSGL获取的海量近似有序点云数据的精简问题，本文提出了拟万有引力定律的点云数据精简方法。该方法无需求解海量点云数据的拓扑结构，节省了大量的运算时间和计算机资源。通过将万有引力公式中各点的质量替换为该点切向、径向“联合曲率”参数，求取了点云数据的“引力”分布图，该图可以有效地将点云数据划分为特征点和非特征冗余点两部分，实现了对点云数据特征点的提取和保护。最终将完整的特征点和经过大比例采样的非特征冗余点融合，实现了点云精简。

（编辑：徐柳）