基于分层投影的特征点点云数据压缩算法研究

田丰瑞　胡　荣

(1.中铁工程设计咨询集团有限公司，北京　100055；2.华中科技大学文华学院，湖北武汉　430074)

三维激光扫描技术在数字三维建模方面已得到越来越多的应用。一般三维激光扫描得到的数据都会有数十万到上百万个点，为海量数据。如果直接将原始的点云数据用于数字建模，不仅要求处理速度和计算能力较高的计算机，而且会影响后续数据处理的工作效率。同时，构造的三维模型常包含很多冗余信息。为了提高数据后处理的工作效率并得到合适分辨率的数字模型，需要在保证数据几何信息不大量丢失的前提下对原始点云数据进行重采样，即点云数据压缩。

为了避免因存储信息点之间的连通性而带来的存储消耗和信息冗余，以散乱点云数据为处理对象，N Dyn，M S Floater，A Iske[1]等人在2000年提出了一种双变量适应性压缩方法，该算法可以获得与原始点云所表达的物体表面相接近的效果；郑德华[2][3]在2005年提出了直接缩减法；吴杭彬，刘春[4]在2006年提出格网数据压缩法；黄承亮，吴侃，向娟[5]在2009年提出了区域重心数据压缩法等。这些传统的散乱点云压缩算法都是基于数理统计的思想对数据进行均匀采样，压缩过程很少顾及信息点之间的几何关联，并且随着压缩程度的增大，会造成数据压缩结果的边界及曲面特征信息严重丢失，进而影响模型构建的后续操作。在对常用的点云数据压缩算法进行研究的基础上，提出并实现了一种基于分层投影的特征点压缩算法，该算法可有效地解决这些问题并提高数据压缩率。

1　常用的点云数据压缩方法

本文将对常用的点云压缩算法进行概述，并采用MATLAB平台实现，结合现有的三维激光扫描数据进行实例分析。实验数据属于散乱点云数据，共包含242 526个信息点。

1.1　直接缩减法

(1)基于均匀采样的压缩算法

根据用户设定的压缩率(λ)对点云数据进行压缩，即每λ个信息点仅保留1个点。压缩效果见图1(b)和图1(c)，与原始数据相比(见图1(a))，压缩率越低，边缘特征数据丢失更为严重。

(2)基于k邻域的压缩算法

针对点云数据，计算每个点与其他点的空间距离并比较大小，将与其距离最近的k个点建立联系，称为k邻域。k邻域建立以后，以此为基础进行数据压缩。压缩时既可以按距离进行简化，即在每个点的k邻域内去除所有距离小于给定阈值的点；也可以按点数进行简化，即遍历所有点的邻域信息，然后删除点云中距离最近的两个点中的一个，直到达到要求为止。实例分析中k=20按距离50 mm和100 mm的压缩效果见图2(a)和图2(b)。

图1　均匀采样的压缩

图2　k邻域的压缩

直接缩减法数据统计见表1，其中，“-”表示数据无法获取。均匀压缩算法的理论压缩率为λ′=1/λ。

图3　格网压缩效果

表1　直接缩减法数据统计

与基于均匀采样的压缩法相比较，基于k邻域的压缩算法更能体现空间实体的表面特征。

1.2　格网数据压缩法

该算法采用中值滤波的方式对点云数据进行压缩[6]。处理原理是：将点云数据投影到已进行均匀格网划分的平面上，然后计算每个信息点到该平面的几何距离，最后以格网为单位，按中值滤波的要求筛选出几何距离位于中间值的信息点，将其余点删除，实现数据压缩。

投影面内格网均按照300×300进行划分，数据压缩效果见图3(a)、图3(b)和图3(c)。

实验数据是按垂直于Y轴方向进行的，从压缩效果图分析与比较，可以看出，在Y方向投影压缩效果最好，因为信息点在该方向的重叠较少。格网压缩数据统计见表2。

表2　格网压缩数据统计

其中，格网压缩的理论压缩率为网格数与原始点云信息点数的比值。

1.3　区域重心数据压缩法

区域重心压缩法又称为均匀栅格压缩法[7][8]，其实质也是均匀采样压缩算法的一种。基本原理是：首先根据点云数据的6个最值(Xmax,Xmin,Ymax,Ymin,Zmax,Zmin)建立最大外包立方体，然后根据用户指定对立方体细分栅格，最后对落入栅格内的信息点进行重心距离采样，将与栅格重心几何距离最近的信息点保留下来，删除其余点。

图4　区域重心压缩效果

本次实例分析取了三种方式细分栅格，压缩效果见图4，数据统计见表3。

表3　区域重心数据压缩统计

与直接缩减法和格网数据压缩法相比，区域重心数据压缩法的压缩效果最能保留原点云数据的整体特征。但由于三维激光扫描数据为面采样数据，在进行栅格细分时，会产生很多空白栅格(即不包含信息点的栅格)，因此其实际压缩率也最难控制。

2　基于分层投影的特征点压缩法

经过上文的实例分析与比较，直接缩减法易丢失特征点，格网数据压缩法实际压缩率低，区域重心数据压缩法能获得较好的压缩效果，但是实际压缩率难以控制。对此，本文提出一种基于分层投影的特征点压缩算法，该算法首先通过分层投影的方法将散乱点云数据分别沿X、Y、Z三个方向拟合成扫描线点云，然后以曲率为筛选标准对信息点进行特征提取。采用单一方向投影压缩会导致信息点在投影方向发生位置重叠而出现数据空洞，为了克服这一缺陷，利用数据融合的方法将三个坐标轴方向上的阶段性结果统一为压缩成果。

2.1　算法流程与实现

本文提出的基于分层投影的特征点压缩算法主要可分为四个阶段，其具体实现流程如下。

(1)点云分层投影

将点云数据读入一个n×3矩阵并查找信息点中的坐标最值，(Xmax,Xmin,Ymax,Ymin,Zmax,Zmin)以坐标最值为基础进行分层投影，投影流程见图5。

图5　点云分层投影流程

(2)扫描线拟合

搜索位于同一投影面上信息点的平面坐标最值，以Z方向投影为例，比较Lx=Xmax-Xmin与Ly=Ymax-Ymin的大小，确定较大值的坐标轴方向为扫描前进方向，选用Sortrows函数对信息点进行排序。

(3)特征点提取

点云数据信息点处的曲率大小表征了该扫描对象对应部位的曲面构造情况，可以通过信息点的曲率关系进行点云数据的特征点提取，包括大曲率点及轮廓点。为避免曲率求解过程中的矩阵求逆操作，本文采用圆拟合的方式进行信息点的曲率计算。

(4)数据融合

将分别沿X、Y、Z方向提取出的特征点进行融合。数据融合时，首先将三个坐标轴方向上的阶段性结果合并起来，然后选用unique函数将数据中重复的信息点剔除，生成最终输出结果。算法的理论压缩率为

式中T为分割投影面层数，N为原始点云数据量，a为曲率压缩比，即每a个点选取一个曲率最大点。

2.2　实例结果分析与比较

对点云数据沿坐标轴进行分层投影分割，分割效果见图6。

以1 000层投影面分割为例，扫描目标的轮廓特征，扫描效果见图7。

图6　分层投影分割效果

图7　提取目标轮廓特征的效果

以拟合扫描线为单位，计算信息点的曲率，并结合用户指定的曲率压缩比a(取a=10)，筛选曲面特征点。

将得到的轮廓特征数据与曲面特征数据再次进行融合，构成点云数据的压缩结果，效果见图8。

压缩过程的数据统计如表4所示。

表4　压缩结果数据统计

从数据压缩效果图及数据压缩统计表可以看出，基于分层投影的特征点压缩法能较好地解决直接缩减法边缘数据丢失的问题，同时，与能较好保留边缘特征的区域重心数据压缩法(数据压缩率为17.57%)相比，数据压缩效果更好，为后续的数据配准工作节约时间。

3　结论

三维激光扫描技术以其快速获取大量数据等优势给三维建模工作带来极大的便利，如何对点云数据进行适当的压缩，则是国内外研究的重点之一。本文针对混乱点云数据，分析对比了各类方法的压缩效率和效果，并在此基础上提出及实现了一种基于分层投影的特征点压缩算法。试验证明，该算法充分考虑到空间实体的几何特征，使得压缩结果具有较强的针对性，可有效地保留点云数据的轮廓及曲面信息，在后续的点云数据配准工作中，以这些特征点为基础搜索邻近点对，可大大提高数字建模的时间效率。

图8　点云数据压缩效果

[1]N Dyn， M S Floater， A Iske. Adaptive Thinning for Bivariate Scattered Data[J]. Journal of Computational and Applied Mathematics， 2000，33：43-58

[2]郑德华. 三维激光扫描数据处理的理论与方法[D].上海:同济大学，2005

[3]郑德华. 点云数据直接缩减方法及缩减效果研究[J].测绘工程，2006，15(4):27-30

[4]吴杭彬，刘春.三维激光扫描点云数据的空间压缩[J].遥感信息，2006，2：22-24

[5]黄承亮，吴侃，向娟.三维激光扫描点云数据压缩方法[J].测绘科学，2009，34(2):142-144

[6]R R Martin， I A Stroud， A D Marshall. Data reduction for reverse engineering[R]. Deliverable Document Copernicus project， Computer and Automation Institute of Hungarian Academy of Science， January 1996．

[7]朱冒冒，冯祖军，郭建华，等.三维栅格法在数据点云精简中的应用[J]. 上海大学学报，2005，11(3):242-246

[8]张丽艳，周儒荣，蔡炜斌，等.海量测量数据简化技术研究[J].计算机辅助设计与图形学学报，2001，13(11):1019-1023