三维激光点云数据精简算法*

黄晓铭，杨 剑，陈 辉

(上海电力学院自动化工程学院，上海 200090)

随着科学技术的发展，三维激光扫描设备的精度逐渐得到提升，通过扫描几乎能够采集到原始模型表面完整的数据.[1-2]但是，由于采集到的点云数据量大且密度高，如果直接对其进行处理，必将降低后续三维重建的效率，影响重构目标表面的光滑性，致使重建效果欠佳.与此同时，庞大的数据量在存储、显示方面也会对计算机提出很高的要求，导致数据处理效率不高.因此，在保留点云数据细节特征和不影响模型重建精度的前提下，需要对海量数据进行点云精简[3-4]，以达到去除冗余点和提高重建效率的目的.

1 激光点云数据精简算法的研究现状

目前，国内外学者对点云数据进行了大量的研究，提出了许多可行的点云精简算法.对于空间散乱点云，由于散乱点云数据之间没有明显的拓扑关系，如果对海量点云直接进行处理，就会严重影响算法的运行效率；因此应先对采集到的点云数据建立合适的几何拓扑关系以缩短精简时间.建立点云拓扑关系的方法主要有八叉树法、空间均匀栅格划分法和k-d树法等[5-6]，流行的散乱点云数据精简算法有三角网格法、随机采样法、聚类法、迭代法、均匀网格法、非均匀网格法和曲率采样法等[7-9].

1996年，D J Weir等[10]提出了包围盒法，将所有的点云数据包含在最小空间长方体中，根据设定的小包围盒将长方体划分为大小相同的包围盒，保留小包围盒的中心点，删除其余点.该算法原理简单，易于实现，适用于均匀分布点云数据的精简，但中心点有可能并非原始点云数据，易造成细节特征的丢失.1997年，R R Martin等[11]提出了均匀网格法，将点云空间进行了均匀网格划分，只保留各网格的中值点.该方法与包围盒法类似，容易丢失特征点，不能保持原始模型的特征信息.2001年，K H Lee等[12]采用非均匀网格精简点云数据，在均匀网格划分的基础上，根据点云的法矢偏差值对均匀网格进一步细分，即在特征区域划分更多的网格，而非特征区域则相反.这使得特征区域能保留相对多的点，而非特征区域则保留较少的点，因此，与均匀网格法相比，该算法能较好地保留细节特征.2008年，N Dyn 等[13]通过构造非负函数来衡量每一个点云数据的重要性，并用迭代的方法对点云进行精简.该方法取得了不错的精简效果，准确度高，但计算量较大.2013年，H Benhabiles等[14]将聚类分析法和由粗到细策略相结合，提出了一种可以保留锐利边缘点的快速点云精简算法.该算法与其他简化算法相比，很好地处理了锐利边缘点的问题.

国内研究学者也对精简算法进行了大量研究.1999年，Chen Y H等[15]采用基于三角网格的点云精简算法，对采集到的点云数据进行三角化处理，利用向量加权算法对三角网络进行冗余判定，并删除冗余的网格以达到精简的目的.2004年，万军等[16]根据平均点距对点云进行精简.该方法对特征点的识别度较差，容易丢失复杂区域的几何特征.2007年，王宏涛等[17]采用八叉树法对点云空间进行划分，只保留叶节点中最靠近重心的点.该方法处理速度较快，但不能充分保留点云的特征点.2008年，周波等[18]研究了基于八叉树的非均匀网格法，但该算法不能完整保留边界点和细节特征.2011年，Shi B Q等[19]提出了基于K均值聚类的自适应点云精简算法.该算法能够保证原始模型边界的完整性且点云分布较为合理，但是对噪声比较敏感.2015年，袁小翠等[20]根据点云的微分信息对点云数据进行K均值聚类，然后对点云空间进行全局聚类，进而以聚类中心点代替该类数据点来达到精简的目的.

然而，上述方法对点云进行精简时未考虑点云特征问题，对点云的细节特征保留得不够完整，无法很好地逼近点云原型，不适合具有复杂特征和多样曲率的高密度散乱点云的数据精简.[21]因此，近年来保持特征的精简算法较为流行.目前，对特征信息的判别主要依据曲率变化的趋势，通过点云微分信息将点云数据划分为特征区域和非特征区域[22-23]，根据不同区域的特点采用不同策略进行精简，确保在精简的同时保留更多的模型细节特征.2006年，孙肖霞等[24]通过拟合最小二乘球来估算曲率，但该算法较为复杂,而且精简后的点云在曲率较小处易出现空白.2009年，刘涛等[25]在包围盒法的基础上提出一种曲率精简算法，该方法能很好地保留特征点，但在平坦区域容易产生空洞，不利于模型的三维重建.2010年，周煜等[21]结合八叉树空间划分法和平均曲率法，将点云模型包含在空间包围盒内并设定阈值，当小包围盒平均曲率大于阈值时细分包围盒，反之保留曲率值最接近平均曲率值的点并删除其余点.该算法能很好地保留数据的细节特征，但计算量大，效率有待提高.2011年，P F Lee等[26]利用离散形态算子对点云模型进行特征提取，可有效保留特征点，但易受噪声干扰.2012年，朱煜等[27]根据点的空间主曲率对点云数据进行精简，取得了较好的精简效果，但主曲率的获得需要对各点进行二次曲面拟合，运算过程耗时长，且难以实现海量点云的精简.葛源坤等[28]提出一种曲率精简算法，对空间进行划分并搜索各点的K邻域，然后计算各点的曲率值，合理设置曲率阈值.该算法虽然能获得较好的精简率，但是二次曲面拟合过程并不理想，不适用于包含丰富细节信息的点云模型.李凤霞等[29]利用法向量夹角精简点云数据，得到了较好的精简效果，但该方法需要对点云中每个点进行最小二乘拟合，计算效率低.2013年，陈璋雯等[30]采用模糊熵迭代法精简点云数据，有效地保留点云的细节特征，但涉及大量的曲率计算，耗时较大.2015年，Li H等[31]提出以点到局部平面的投影残差来判定点云数据的保留与否，但该算法受噪声的影响大，容易丢失点云模型中平滑区域的细节信息.2016年，杨秋翔等[32]以数据点主曲率的Hausdorff距离为依据提取点云数据特征点，该方法提高了简化效率，但数据点主曲率的Hausdorff距离不一定都相等，导致精简结果不均匀.此外，激光点云数据的精简算法还有很多种且各具优缺点.不同的精简算法适用于不同的场景，在工程实际中，应根据需求来选择合适的精简算法，以期得到符合工程要求的结果.

总结上述精简算法，将点云精简算法归纳为3类：一类是基于概率的精简法，如随机采样法等；二类是基于网格的精简法，如包围盒法、三角网格法和均匀网格法等；三类是基于特征信息的精简法，如最小距离法、曲率精简法等.点云精简算法众多，控制量不统一，缺乏定性和定量的比较.笔者在众多方法中筛选出3种常用的方法，即包围盒法、随机采样法和曲率精简法进行性能比较.首先选取斯坦福大学提供的Bunny模型和三维重构中常用的椅子模型为实验对象，然后在MATLAB中编程并控制其中的变量因素，最后对原始点云进行精简处理，直观比较输出的精简结果，分析各种算法的优劣性和适用性.

2 几种典型的点云数据精简算法

2.1 包围盒法

包围盒法是一种传统的点云数据精简算法，它的工作原理为：构建一个包含所有点云数据的包围盒，并将其分解成若干均匀大小的小包围盒，选取最靠近中心的点来代替小包围盒所有的点以达到精简点云数据的目的，并通过控制小包围盒的大小来控制精简结果.该方法简单高效且容易实现，是一种简单的基于空间准则的精简算法，对表面不复杂和曲率变化不大的物体的点云数据的精简很有效.精简后的点云比较均匀，能够反映简单模型的轮廓特征，但是当物体表面有大曲率曲面时，精简曲面将不能很好地保持原有的模型特征，也无法确保精简的精度，主要适用于模型表面的形状相对简单且对精度要求不高的场合.

2.2 随机采样法

随机采样法的基本思路是：针对散乱的点云数据设计一个随机函数，使其产生的随机数能够覆盖点云分布的所有范围，然后依据随机数将点云数据中与之对应的数据点以相等的概率予以删除，直到点云数据中剩余的点数达到精简要求.该方法对于海量点云数据有较高的精简效率，实现过程简单高效，运行速度快，但是没有考虑到点云空间的具体特征和细节，容易丢失原始模型的空间几何特征，而且随机函数的随机性导致每次运行后的精简效果都不一致，从而点云数据的精简结果无法控制.因此，该方法在点云模型要求较高的实际应用中有很大局限性，主要作为其他精简算法的补充方法，对点云数据进行后续的精简操作.

2.3 曲率精简法

曲率精简法以数据点的曲率为依据，在曲率大的区域精简少量点，以保留足够多的点来表达模型的几何特征，而在曲率相对较小的区域精简较多点以减少数据点的冗余.这是因为点云模型的曲率大小对应模型的几何特征分布，表示点云模型的内部属性：对于曲率大的区域，模型表面的变化相对剧烈，特征比较明显；而在曲率较小的区域，模型表面的变化相对平缓，特征相对不明显.因此，该方法在删除冗余数据的同时，能尽量保留点云模型的细节特征，实际应用中可以采用反映曲率变化的曲面特征参数作为点云精简的判别准则.相比其他点云精简算法，曲率精简法的优点在于既能够准确地保留原始模型的细节特征信息，又能有效地减少冗余的数据点，但是该方法存在曲率计算过程较为复杂、算法运行耗时长和对计算机的性能要求高等缺点.此外，在曲率较小的区域，该方法会删除较多的数据点；在待删除的数据点的选择上，该方法并没有遵循均匀精简的规则，会造成局部空洞现象.

3 实例分析

笔者对同一目标点云分别使用包围盒法、随机采样法和曲率精简法进行精简，在MATLAB平台上实现编程.椅子模型和Bunny模型的原始点云及其经不同精简算法处理后的图像如图1所示，各种算法的结果比较列于表1.

图1 2个模型的原始点云及其精简后的图像Fig. 1 Original Point Cloud and Reduction Results of Two Models

模型组别点云个数精简率/%精简速度精简效果椅子原始点云 49 960包围盒法 16 94466.08一般可作初步精简随机采样法16 98666.00快 需要解决特征点丢失问题曲率精简法16 36967.24慢 需要控制时间模型组别点云个数精简率/%精简速度精简效果Bunny原始点云 35 947包围盒法 11 32568.50一般可作初步精简随机采样法11 50368.00快 需要解决特征点丢失问题曲率精简法12 09566.35慢 需要控制时间

从表1可以看出，在以上算法中，随机采样法速度最快而基于曲率的精简算法速度最慢，包围盒法从时间效率来说介于两者之间.在精简率相近的情况下，各算法都可以保持模型的整体样貌，但有的丧失了一些重要的细节点.从图1可以看出：经包围盒法精简后，点云分布比较均匀，但在平坦区域还是存在很多的冗余信息，在曲率变化较大的区域表面特征丢失比较严重；经随机采样法精简后，点云分布比较均匀，但不能很好地突出模型的几何特征，细节丢失严重，精简效果的随机性较大，不能很好地保留细节特征；经曲率精简法精简后，在曲率大的地方点云比较密集，说明较好地去除了点云的冗余数据并有效地保留了点云细节特征，但因分布不均匀，点云在曲率较小处出现了空洞现象.

4 结语

笔者重点综述了激光点云数据模型的精简算法，分析了点云精简算法的国内外研究现状，并对最常用的3种算法进行了简单介绍及实验验证，分析了它们的优缺点.点云精简结果质量的好坏决定着后续配准及三维重建的效果，对点云精简算法质量的衡量要综合考虑精度、简度、速度和适用性4个方面.理想的点云精简算法是用最少的数据点表达出最重要的特征信息，并在这个过程中有较快的运行速度.在实际应用中，要求一个精简算法同时满足所有要求是十分困难的，而且单纯使用一种方法一般无法取得满足实际要求的精简效果，因此对现有方法的改进和融合是将来的研究方向.