ABSTRACT

In this paper, a point cloud simplification considering geometric morphology and density distribution is proposed, in view of difficulty of ensure precision of simplified point cloud that generated by traditional method which mainly taking normal vector or curvature as the measurement of geometric information. First, we use the three-dimensional Gauss kernel function to smooth the original point cloud; the importance of current point is evaluated based on flatness variation component and density variation component. The simplification proceeds and finishes by removing the least important point and updating the importance values progressively. At last, the performance of the proposed method is illustrated with two sets of experiment where three classical simplification methods are employed for contrast. The results show that the proposed method can reserve feature points with a uniform distribution.

Keywords:Point Cloud Simplification, Gauss Kernel Function, Smooth Distance, Importance of Point

顾及几何形态与密度分布的点云 压缩方法

张少彬^*，杨必胜，梁福逊

武汉大学测绘遥感信息工程国家重点实验室，湖北 武汉

收稿日期：2018年6月22日；录用日期：2018年7月13日；发布日期：2018年7月20日

摘 要

针对传统点云压缩算法中主要应用法向量、曲率等测度来描述目标区域几何信息，易受噪点影响，无法保证压缩精度的问题，提出一种顾及几何形态与密度分布的点云迭代压缩算法。本文首先利用三维高斯核函数对原始点云进行平滑处理，依据点平滑前后平坦度变化分量与密度变化分量来衡量当前点在点云中的重要度，然后迭代去除重要度最低的点，并计算该点影响范围点集，更新其重要度，最终实现点云压缩。采用两份数据对本文算法进行验证，并与三种经典压缩方法进行对比，实验表明，相较于其他三种方法，本算法压缩结果在点分布均匀的同时，能够较好的保留特征点集。

关键词 :点云压缩，高斯核函数，平滑距离，点重要度

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

三维激光扫描能够快速获取目标表面的高精度三维坐标，被广泛应用于道路测量、变形监测、城市建模、逆向工程等方面 [1]。但高精度的三维点云数据中往往存在大量的冗余，给存储空间提出严峻要求的同时也会给后续处理带来极大的额外负担 [2]。因此，在保留点云特征的前提下，对点云数据进行压缩就显得很有必要，而衡量一个压缩算法的优劣不仅仅在于其压缩效率，更在于压缩后点云数据的特征保留程度 [3]。

近年来，众多学者对点云数据压缩算法进行了研究，并取得了众多的成果。从压缩处理对象来分，可分为点云数据编码压缩 [4] 与点云几何信息压缩两类。数据编码压缩算法重点在于解决三维坐标浮点数值造成的精度浪费，并没有实际减少点云个数，无法获取较高的压缩率，因此，本文研究方向为基于点云几何信息压缩，根据压缩准则的不同，基于几何信息的压缩算法可分为两类：基于格网的压缩与基于无序点的压缩 [5]。

基于网格的压缩算法基本原理为，对点云数据构建多边形格网，如狄洛尼三角网，去除冗余的三角面片来实现点云压缩 [6]，其缺点在于对大量的点云数据构建格网计算复杂且耗时。

基于无序点云的压缩算法则直接作用于点，复杂度低，其重点在曲面变化度量的计算。激光扫描线上的特征点坐标增量大于非特征点坐标增量，蔺小虎 [7] 以此为度量将一维的坐标增量压缩算法发展至二维，对二维方向上坐标增量小于阈值的点进行合并，该算法对点云扫描方式要求苛刻；杨景路 [8] 以法向量夹角与曲率为度量，将点云数据划分为高曲率与低曲率区域，分别进行不同阈值的法向量夹角压缩，该方法保留了更多的特征区域，但没有考虑压缩过程中的信息变化；特征区域法向量夹角变化不确定性高，其局部信息熵较非特征区域点高 [9]，Xuan W [10] 与陈璋雯 [11] 以此作为衡量点重要度准则，迭代去除重要度最低的点，并更新各点的重要度，但法向量、曲率估计易受噪声影响 [12] [13] [14] ；Shi baoquan [15] 利用局部法向量夹角度量对点云数据进行K-Means聚类，并细分边缘类，最后以类中心来代替该类实现点云的压缩；王艺楠 [16] 则利用点的FPFH特征代替传统的法向量、曲率度量对点云进行模糊聚类，此类基于聚类思想的压缩算法受初始聚类中心影响大，鲁棒性低。对压缩后的点云质量评价研究中，Mark Pauly [17] 在实现坐标增量、聚类、粒子模拟三种压缩方法的基础上利用二次误差测量对压缩效果进行了定量评价。

针对上述点云压缩算法的问题，本文提出了一种顾及几何形态与密度分布的点云迭代压缩算法。首先，利用高斯核函数获取当前点在平滑前后的位移量，将其分解为平坦度变化分量与密度变化分量，分别赋予不同的权重系数来衡量当前点在点云中的重要度。之后，迭代去除重要度最小的点，并更新影响范围点重要度，直至达到指定的压缩率。最后，选取三种经典压缩方法进行对比实验，并利用Geomagic软件建立压缩前后模型，计算模型偏差对算法结果进行定量评价。结果表明，本文方法相较于其他常用方法能够在保证效率的同时有效的保留点云特征，简化结果点云分布均匀，无需聚类因而稳定性高，并避免了传统曲面变化度量，如曲率，易受噪声影响的问题。

2. 顾及几何形态与密度分布的点云压缩

点云压缩算法一般原理是通过对点局部曲面变化进行定量描述，如法向量，按照一定的规则，如法向量夹角，将局部变化平缓或分布均匀的点适当滤除，尽可能多的保留局部变化明显的点，其实际效果相当于对点云数据进行平滑处理。当点位于分布均匀的平面时，其与经平滑函数生成的预测点之间位移几乎为零；而曲面变化丰富或分布不均的区域点，其平滑前后会产生较大位移。因而，可以利用点平滑前后所产生的位移差异特征来对点的重要度进行排序，滤除重要度低的点，进而达到点云压缩的目的。高斯平滑函数具有旋转对称性，可以保证在各个方向上的平滑程度相同 [18]，因而本文采用高斯平滑函数来计算平滑后点相对应的预测点位置，在分析两者位移在平坦度变化分量与密度变化分量的基础上，对点云数据进行重要度排序，并考虑滤除点后对其局部区域影响，采用迭代思想重新衡量各点重要度，在保证分布均匀的前提下，滤除重要度低的点，保留曲面变化显著点或边界点。本文方法流程如图1所示。

2.1. 高斯平滑预测点坐标计算

高斯平滑是一种线性平滑，可用于消除高斯噪声，且具有旋转对称性，其对各个方向的平滑程度相同，因而被广泛的应用于图像处理、点云去噪等领域。三维中高斯平滑核函数可定义为：

图1. 本文压缩方法流程图

$G\left(p,q,\delta \right)=\frac{1}{2\text{π}{\delta }^2}\exp \left[-\frac{1}{2{\delta }^2}d{\left(p,q\right)}^2\right]$ (1)

其中，δ为高斯函数标准差，代表了平滑窗口的大小，本文设置为4；d(p, q)为当前点p与其邻域点q的欧式距离。高斯平滑利用邻域点的加权平均来代替中心当前点，减小了中心当前点与其邻域点的差异 [12]，在中心模板点的邻域内距离中心模板点越近，其权值越高，通过归一化后可获得其预测点坐标。对于点云M，p为M中任一点，当前点p所对应的预测点p'坐标计算公式为：

$p^{\prime }=\frac{{{\displaystyle \sum }}^{\text{}}{q}_{i}G\left(p,q_i,\delta \right)}{{{\displaystyle \sum }}^{\text{}}G\left(p,q_i,\delta \right)}$ (2)

其中 $q_i$ 为p的某一邻域点， $G\left(p,q_i,\delta \right)$ 各邻域点权值。预测点计算具体过程如下：

1) 读取点云数据，建立KDtree。

2) 采用K近邻获取当前点p邻域点集 $$ 。其中 $K=20$ 。

3) 利用公式(2)计算当前点p的预测点p'坐标。

2.2. 基于平滑前后位移分量分析的点重要度计算

在获取当前点p的高斯平滑预测点p'后，可按公式(3)计算当前点在平滑前后的位移大小 $\left|L_p\right|$ ：

$\left|L_p\right|=\Vert p-p^{\prime }\Vert$ (3)

其中 $L_p$ 为当前点p到其预测点p'的向量。位移大小 $\left|L_p\right|$ 经分析由两方面距离因素构成：当前点p邻域内几何形态变化，即由高低起伏变化引起的相较于局部基准面的平坦度变化分量 $\Delta h$，以及由其邻域内点分布不均引起的密度变化分量 $\Delta s$，位移大小 $\left|L_p\right|$，平坦度变化分量 $\Delta h$，密度变化分量 $\Delta s$，三者符合空间直角三角形关系，如图2所示，S为局部基准面，p'点为预测点。

为更好的贴合目标物体表面以及抑制噪声，局部基准面为当前点p邻域点集最小二乘拟合平面，平面方程为：

$a_{p}x+b_{p}y+c_{p}z+d_p=0$ (4)

其中， $a_p,b_p,c_p,d_p$ 为平面参数，设 $n_p=\left(a_p,b_p,c_p\right)$ 为局部基准面法向量。

平坦度变化分量 $\Delta h$ 描述了当前点p在其邻域内的几何形态变化，密度变化分量 $\Delta s$ 描述了当前点邻域内点密度分布信息：当点p位于分布均匀的平面或平缓曲面内部时， $\Delta h=0,\Delta s=0$ ；当点p位于平面

图2. 空间关系图

边缘时， $\Delta h=0,\Delta s\ne 0$ ；当点p位于变化剧烈曲面或曲面边缘时 $\Delta h\ne 0,\Delta s\ne 0$ 。但在实际车载或地面站点云数据中，扫描距离以及目标地物朝向等因素往往会引起目标表面点分布不均，可导致 $\left|L_p\right|$ 中 $\Delta s$ 分量过高，错误的提高了其重要度，如图3红框所示，车顶位置点云其重要度应低于边界或变化明显区域，且与车辆侧面点重要度相近，而在实际中由于其朝向，造成表面点分布不均且点数较少， $\Delta s$ 分量过高，其重要度估计值过高。

综上，当前点的重要度应由平坦度变化分量与密度变化分量两部分来共同确定。为降低由扫描方法与目标朝向引起的密度变化分量值过高所带来的影响，需赋予平坦度变化分量 $\Delta h$ 较高的权重，而赋予密度变化分量 $\Delta s$ 较低的权重，权重皆为正值，且归一化为(0, 1)之间的小数。当前点p重要度计算采用线性加权方法，公式如下：

$H\left(p\right)=k\Delta h+\left(1-k\right)\Delta s$ (5)

$\Delta h=\left|\frac{n_p{L}_p}{\Vert n_p\Vert }\right|$ (6)

$\Delta s=\sqrt{{\left|L_p\right|}^2-\Delta h^2}$ (7)

其中，k为 $\Delta h$ 的权重系数，且 $1>k>1-k>0$，即k取值范围为(0.5, 1)，经验权值 $k=0.8$ 。

点重要度计算具体过程如下：

1) 获取当前点p邻域点集 $N_p$ 。

2) 最小二乘法拟合平面S，获取平面法向量 $n_p$ 。

3) 依照公式(5)计算点p重要度

重复步骤1~3，获取全部点重要度初始值序列。

2.3. 确定去除点影响范围，更新局部点重要度

以公式(5)计算各点的重要度后，通过迭代去除重要度最小的点，获取压缩后点云数据。在去除重要度最低点p过程中，其邻域以及领域点的邻域内各点的平坦度变化信息、点局部分布信息会发生变化，邻域点的重要度也应随之发生变化，而总体点云中其他点则不受该点影响。因此，为提高算法效率，只需更新其影响范围内点集 ${N^{\prime }}_p$ 的重要度。同时，为避免平缓区域过压缩而产生空洞，在搜索 ${N^{\prime }}_p$ 各点的K邻域时，若搜索结果分布范围过大，说明该点周围点密度过小，则给该点赋予较高的重要度。

具体过程如下：

1) 去除当前循环中重要度最低点。

2) 获取影响范围点集 ${N^{\prime }}_p$ 。

图3. 车辆点云分布图

3) 搜索 ${N^{\prime }}_p$ 各点邻域。若其中一点m邻域范围过大，则其重要度 $H\left(m\right)=MAX$ 。

4) 按照公式(5)更新 ${N^{\prime }}_p$ 内各点重要度。

重复步骤1~3，直至达到所需压缩率。

3. 实验及分析

本文以Visual studio 2013为开发平台，结合OpenCV、PCL库，实现本文提出的顾及几何形态与密度分布的点云压缩方法并验证其效果。实验数据为车载车辆点云数据、斯坦福bunny点云数据，如图4，图5，其中车载车辆原始点云点个数为73,285，点云分布不均匀，其中以车顶区域最为严重；bunny原始点云个数为35,947，点云分布均匀。

3.1. 特征检测结果

为检测本文中提出的点重要度度量实际有效，分别从只用 $\Delta h$ 、只用 $\Delta s$ 、采用公式(5)三个方面进行验证，并将其初始重要度序列中前15%作为特征点集输出。图6为车辆点云数据只用平坦度变化分量 $\Delta h$ 检测出的特征点集，图7为车辆点云数据只用密度变化分量 $\Delta s$ 检测出的特征点集，图8为采用公式(5)检测出的车辆总体特征点集，图9为检测出的bunny总体特征点集。

如图6所示，平坦度变化分量 $\Delta h$ 将车辆车门把手及侧门下方等曲率变化显著的区域点提取完整，如图中红框所示，但路面区域边缘及车辆表面边缘信息丢失；图7中，边缘信息提取清晰完整，但由于点密度分布不均，路面及车辆表面等曲面变化平缓区域也被检测为特征点；从图8、图9中可看出本文所提出的重要度度量能够有效的将几何形态变化丰富区域及边界点提取出来，并解决了由点分布不均所带来的重要度过高问题，如图中红框所示。

图4. 车载车辆原始点云数据

图5. Bunny原始点云数据

图6. ∆h特征点

图7. ∆s特征点

图8. 车辆总体特征点集

图9. Bunny总体特征点集

3.2. 与常用压缩方法对比实验

为验证最终压缩效果，将采用本文算法压缩结果与随机采样法、格网抽稀方法、基于曲率抽稀方法结果做对比试验，压缩率为30%，车辆点云数据压缩后点个数为21,985。bunny点云数据压缩后点个数为10,212。利用Geomagic软件对压缩后点云数据进行建模，计算原始点云到模型面片距离，红色代表正偏差，蓝色代表负偏差。

3.2.1. 车辆数据压缩结果及模型偏差

图10为本文方法压缩结果，从对比试验中可看出，本文算法压缩结果车辆轮廓清晰，特征区域如车灯，得到较好的保留，密度变化较大区域如车顶，经压缩后点分布均匀，模型无空洞，且偏差最小；结合图11、图12可得，随机采样法、格网抽稀法中车门把手、车灯等变化丰富区域信息缺失，因而上述区域普遍存在偏差；如图13所示，基于曲率抽稀方法中特征区域得到了保留，但受原始点云数据密度分布影响，车顶及前盖部分点密度远远少于侧面及路面，模型出现大面积空洞。表1为30%压缩率下本文方法与三种常用方法的最大正偏差、最大负偏差、标准偏差数值表，单位mm，其中，本文算法最大正、负偏差最小，格网抽稀方法由于其结果分布均匀，标准偏差最小。综上，本文算法能够很好的保留目标几何形态变化显著区域点，同时，密度变化分量使得简化结果无空洞，其较小的权值也保证了不同密度

图10. 本文算法压缩结果及偏差图

图11. 随机采样压缩结果及偏差图

图12. 格网抽稀压缩结果及偏差图

的目标平缓表面在最终简化结果中点分布均匀，如图10中车顶表面与车辆侧面。

3.2.2. Bunny数据压缩结果及模型偏差

从对比试验可看出，在平缓区域，格网抽稀方法与本文算法均取得较好结果；而在尾部、颈部、腿部等曲面变化丰富区域，本文算法偏差最小，其余三种算法则出现较大偏差，具体偏差值如表2所示，Bunny点云数据为封闭模型，且分布均匀，因而四种方法整体偏差不大。结合图14、图17，采用基于曲率的抽稀方法时，耳部区域曲率估计出现错误，造成耳部轮廓点确实，而本文方法则能够完整保留耳部轮廓点，证明本文所提出的重要度度量能够准确描述目标表面变化显著区域点特征。结合图14、图16，格网抽稀方法简化结果点分布均匀，因而平缓区域能够取得良好的模型重建效果，在变化显著区域则会产生较大的信息缺失，本文方法同时估计了几何形态与密度分布，简化结果特征点信息完整，且分布均匀。图15所示，随机采样法由于其随机性，造成特征区域点大量缺失，效果最差。

4. 结论

1) 本文提出了一种顾及几何形态与密度分布的点云压缩算法，采用车载车辆点云数据、bunny点云数据进行了实验验证，结果验证了算法的可行性与实用性。

图13. 曲率抽稀压缩结果及偏差图

表 1. 车辆数据偏差表

表 2. Bunny 数据偏差表

图14. 本文算法压缩结果及偏差图

图15. 随机采样压缩结果及偏差图

图16. 格网抽稀压缩结果及偏差图

图17. 曲率抽稀压缩结果及偏差图

2) 本文提出的从平坦度变化分量与密度变化分量两个方面衡量点重要度，能够在保留曲率变化丰富区域及边界区域的同时，能够获取分布均匀的压缩点云。

3) 高斯平滑核函数δ的取值为实验验证获取，其取值关系到不同粒度下的特征检测能力，下一步需更多的实验来获取其最佳取值方法。

基金项目

国家自然科学基金重点项目(41531177)；国家杰出青年科学基金(41725005)。

文章引用

张少彬,杨必胜,梁福逊. 顾及几何形态与密度分布的点云压缩方法
Point Cloud Simplification Considering Geometric Morphology and Density Distribution[J]. 测绘科学技术, 2018, 06(03): 212-222. https://doi.org/10.12677/GST.2018.63024

参考文献