随着3D扫描技术的发展, 点云数据模型应运而生, 目前已被应用于结构行为监测、信息模型构建、农业应用、自动驾驶视觉导航以及文物虚拟复原等众多领域^[1-5]. 由于扫描采集的点云模型的点数据量大, 点与点之间没有明确关联, 从而导致点云处理的工作量较大, 因此有必要对云模型进行简化预处理.

目前, 国内外学者提出了很多点云简化方法. 如, 李大军等^[6]提出一种基于结构信息约束的网格简化方法, 该方法可以鲁棒地保持最佳三角面的形状和拓扑结构, 改善三维模型的重建效果; Li等^[7]提出一种过滤和简化三维建筑网格模型的方法, 通过边折叠操作实现网格简化, 能够保留分段平面结构和尖锐特征; Liang等^[8]提出一种结合边分裂和边折叠操作的网格简化方法, 该方法具有较小的逼近误差, 在几何特征保持、三角形质量等方面具有较为明显的优势; Leal等^[9]提出一种基于显著性值的点云简化方法, 通过估计点云中点的检测点的显著性来计算动态聚类半径, 从而实现基于聚类的点云简化, 可以在一定程度上提高点云简化的精度, 有效保持点云的边缘特征; Wang等^[10]提出一种基于邻域多特征信息的点云简化方法, 解决了特征保留不完整以及平坦区域出现孔洞的问题; 张军军等^[11]提出一种基于边缘系数的建筑物LiDAR点云数据模型简化方法, 该方法在对点云进行高效简化的同时有效保持边缘特征, 有效提高建筑物的重建效率.

以上点云简化方法可以使点云的结构得以保持, 但时间和空间开销较大, 精确性、多特征融合、特征区域与非特征区域的差异性考量等方面仍需要改进. 鉴于此, 提出一种点重要性判断点云简化方法. 该方法基于点的重要性判断, 采用八叉树结构简化点云非特征点, 可以有效保留点云的重要细节特征, 达到点云简化的目的.

1 点重要性计算

在点云简化中, 为了准确地保留整个点云的细节特征点, 这里通过计算4个特征算子评估点的重要性, 即曲率差、法向量差、投影距离、空间距离.

1.1 特征算子计算

(1)曲率差

曲率是最直观地反映点的尖锐程度的一个参数^[12]. 对于点云 $ {\boldsymbol{P}} $ , 当点 ${{\boldsymbol{p}}_i} \in {\boldsymbol{P}}$ 的曲率与其相邻点 ${{\boldsymbol{p}}_j}$ 的曲率之差很大时, 该点很可能处于尖锐位置, 是一个细节特征点. 因此, 计算点 ${{\boldsymbol{p}}_i}$ 和每个邻近点的曲率之差, 再累积曲率差, 便可反映点 ${{\boldsymbol{p}}_i}$ 的锐度.

(2)法向量差

点云中任意一点 ${{\boldsymbol{p}}_i}$ 的法向量可以反映该点所在的切线平面^[13]. 如果两个点有相同的切平面, 那么它们的法向量是相同的, 并且这两个点之间的法向量差为零. 当点 ${{\boldsymbol{p}}_i}$ 的法向量与其各个相邻点 ${{\boldsymbol{p}}_i}$ 的法向量之差的和较大时, 由点 ${{\boldsymbol{p}}_i}$ 及其相邻点 ${{\boldsymbol{p}}_i}$ 拟合的曲面在点 ${{\boldsymbol{p}}_i}$ 处则较凸或较凹.

(3)投影距离

点与其邻域点形成的平面的投影距离也可以反映点的凹凸性, 投影距离越大, 样本曲率变化也就越大. 为了反映点 ${{\boldsymbol{p}}_i}$ 的曲率的变化, 可以通过计算点 ${{\boldsymbol{p}}_i}$ 的邻域点 ${{\boldsymbol{p}}_j}$ 到其投影平面的投影距离并把这些投影距离相加来体现.

(4)空间距离

空间距离也能反映点云中两点间的关系. 在点云中, 当某一点与其邻域点的空间距离较大时, 可能该点处于尖锐位置, 或是点云采样不均匀导致该点附近区域稀疏. 为了防止出现稀疏区域出现孔洞, 可以通过计算点 ${{\boldsymbol{p}}_i}$ 与其每个邻域点 ${{\boldsymbol{p}}_j}$ 之间的空间距离, 并累加空间距离来反映点 ${{\boldsymbol{p}}_i}$ 的重要性.

1.2 特征算子融合

为了减少误差积累, 将上述4个特征算子加权融合, 即可用于描述点 ${{\boldsymbol{p}}_i}$ 的重要性, 定义为:

$ \begin{split}{I}_{{{\boldsymbol{p}}}_{i}}=&{\displaystyle \sum _{j=1}^{k}\bigg[\alpha \left({{\boldsymbol{c}}}_{i}-{{\boldsymbol{c}}}_{j}\right)+\beta \left(1-{{\boldsymbol{n}}}_{i}^{{\rm{T}}}{{\boldsymbol{n}}}_{j}\right)}\\ 　 &+\gamma |{{\boldsymbol{n}}}_{i}^{{\rm{T}}}\left({{\boldsymbol{p}}}_{i}-{{\boldsymbol{p}}}_{j}\right)|+\delta \left|\right|{{\boldsymbol{p}}}_{i}-{{\boldsymbol{p}}}_{j}\left|\right|\bigg]\end{split} $

(1)

其中, $\alpha ,\; \beta , \;\gamma ,\; \delta$ 均为比例因子, 点 ${{\boldsymbol{p}}_j}$ 表示点 ${{\boldsymbol{p}}_i}$ 的一个 $ k $ 邻域点, ${{\boldsymbol{c}}_i}$ 和 ${{\boldsymbol{c}}_j}$ 分别表示点 ${{\boldsymbol{p}}_i}$ 和点 ${{\boldsymbol{p}}_j}$ 的曲率, ${{\boldsymbol{n}}_i}$ 和 ${{\boldsymbol{n}}_j}$ 分别表示点 ${{\boldsymbol{p}}_i}$ 和点 ${{\boldsymbol{p}}_j}$ 的法向量.

对于不同类型的点云, 可以给出不同的比例因子组合. 对于均匀采样的点云, 可以将空间距离算子的比例因子 $ \delta $ 设置为较小值; 对于非均匀采样的点云, 将空间距离算子的比例因子 $ \delta $ 设置为较大值; 对于具有清晰细节特征的点云, 曲率差算子的比例因子 $ \alpha $ 可设置为较大的值; 对于具有一般细节特征的点云, 法向量差算子的比例因子 $ \;\beta $ 、投影距离算子的比例因子 $ \gamma $ 都设置为较大值.

通过计算点 ${{\boldsymbol{p}}_i}$ 的重要性 ${I_{{{\boldsymbol{p}}_i}}}$ , 即可将重要性大于阈值的点保留为细节特征点, 剩余的点为非细节点. 对于特征较少的点云数据, 可以设置较大的阈值, 以保证较高的简化率; 对于具有大量特征和复杂特征的点云数据, 可以置了一个较小阈值来保证算法可以保留较多的细节特征点.

2 基于八叉树的非特征点简化

点重要性 ${I_{{{\boldsymbol{p}}_i}}}$ 的值较大的点即为点云中的特征点, 它们描述了整个点云模型的细节特征、对比特征和结构特征. 但是, 如果仅使用特征点拟合曲面, 曲面中将有许多孔洞, 因此还需要保留一些非特征点, 这里采用八叉树来简化非特征点. 八叉树可以在每个叶节点中保留一个点, 通过把整个点云进行空间分割来实现点云简化.

构建八叉树的基本思想为^[14]: 首先, 设置八叉树的最大递归深度或最大层数, 并找到整体点云的最大和最小空间坐标值, 构建包围点云的最小外立方体, 这个外立方体就是空间包围盒; 然后, 基于空间包围盒, 生成根节点, 判断如果没有达到最大递归深度, 则将当前立方体平均细分为8个; 再判断子立方体中的点数与父立方体中的点数, 如果相同并且数量不为零, 则子立方体被停止切割; 最后, 重复上述递归过程, 直到达到最大递归深度.

基于构建的八叉树, 即可实现非特征点的简化, 具体步骤描述如下.

(1)为点云中的所有非特征点构建一棵八叉树.

(2)对于八叉树的每一个叶节点, 计算它及其邻域点的平均法向量 $\bar {\boldsymbol{n}}$ 和平均曲率 $\bar {\boldsymbol{c}}$ .

(3)计算每个叶节点的法向量与平均法向量之差.

(4)计算每个叶节点的曲率与平均曲率之差.

(5)将向量差和曲率差相加, 并选择该和值最小的点来代替叶节点中的其他点, 计算式为:

$ {\boldsymbol{nc}} = \left(1 - {{\boldsymbol{n}}_i}\bar {\boldsymbol{n}}\right) + \left({{\boldsymbol{c}}_i} - \bar {\boldsymbol{c}}\right) $

(2)

采用上述非特征点简化算法即可在保持点云重要细节特征的基础上, 实现有效的点云简化, 并可防止孔洞的产生.

3 点云简化的评价指标

点云简化算法的效果主要从简化率和简化误差等方面进行度量, 简化率就是简化后的点数与简化前的点数的比值. 简化误差用于度量简化后点云的几何特征的保持效果.

3.1 简化率

在点云简化前后, 其点的三维坐标没有发生任何改变, 所以简化后点云中所包含的点数就可以用于表示点云的简化效果. 该简化效果可以用简化率 $ R $ 表示, 其计算式为:

$ R = \frac{{{N_P} - {N_{P'}}}}{{{N_P}}} $

(3)

其中, $ {N_P} $ 表示简化前点云所包含的点数, $ {N_{P'}} $ 表示简化后点云所包含的点数. $ R $ 值越大, 说明点云的简化程度越高. 但是 $ R $ 值过大会造成孔洞, 影响后期点云处理效果.

3.2 简化误差

简化误差用于评价点云简化的精度, 通常采用最大误差和平均误差来衡量. 最大误差可以衡量点云简化的局部误差, 有效反映点云简化后对细节几何特征的保持效果, 与最大误差 $ {\varepsilon _{\max }} $ 呈正比关系.

定义最大误差 ${\varepsilon _{\max }}\left({\boldsymbol{P}}, {\boldsymbol{P}}'\right)$ 为:

$ {\varepsilon _{\max }}\left({\boldsymbol{P}}, {\boldsymbol{P}}'\right) = \mathop {\max }\limits_{{{{\boldsymbol{p}}}} \in {{{\boldsymbol{P}}}}} d\left({\boldsymbol{p}}, {\boldsymbol{P}}'\right) $

(4)

其中, ${\boldsymbol{P}}$ 表示简化前的点云模型, ${\boldsymbol{P}}'$ 表示简化后的点云模型.

平均误差 ${\varepsilon _{{\rm{ave}}}}$ 可以用于衡量点云简化的全局误差, 定义为:

$ {\varepsilon _{{\rm{ave}}}}\left({\boldsymbol{P}}, {\boldsymbol{P}}'\right) = \frac{1}{N}\mathop {\max }\limits_{{\boldsymbol{p}} \in {\boldsymbol{P}}} d\left({\boldsymbol{p}}, {\boldsymbol{P}}'\right) $

(5)

其中, ${\boldsymbol{P}}$ 表示简化前的点云模型, ${\boldsymbol{P}}'$ 表示简化后的点云模型, $ N $ 表示点云 ${\boldsymbol{P}}$ 所包含的点数; $d\left({\boldsymbol{p}}, {\boldsymbol{P}}'\right)$ 表示对点云 ${\boldsymbol{P}}'$ 做网格剖分后, 点云 ${\boldsymbol{P}}$ 上的一点 ${\boldsymbol{p}}$ 到 ${\boldsymbol{P}}'$ 上最近的三角面片的欧氏距离.

4 实验结果与分析 4.1 公共点云简化

在公共点云简化实验中, 采用Bunny和Horse点云模型来验证点云简化方法, 如图1所示.

对图1所示的公共点云, 分别采用多特征保持简化法^[2]、结构信息约束简化法^[6]、支持向量回归简化^[15]以及提出的点重要性判断简化法等4种方法对其进行简化, 简化结果如图2、图3和表1所示.

从图2、图3和表1的简化结果可见, 所提点云简化方法对公共点云具有较优的简化效果, 可以在有效保持点云重要细节几何特征的同时, 较大化地简化非特征数据信息, 并避免孔洞的产生.

4.2 文物点云简化

文物点云简化实验采用的是兵马俑文物碎片的点云数据模型, 如图4所示. 对该碎片模型分别采用多特征保持简化法、结构信息约束简化法、支持向量回归简化以及提出的点重要性判断简化法等4种方法进行简化, 简化结果如图5、图6和表2所示.

从图5、图6和表2的简化结果可见, 提出的该点重要性判断简化法对文物点云具有最优的简化效果, 可以在有效保持点云重要细节几何特征的同时, 有效删除非特征数据信息, 并避免孔洞产生, 是一种有效的点云简化方法.

综上, 提出的该点重要性判断点云简化方法可以对公共点云和文物点云数据模型进行有效的简化, 不仅可以保留点云的重要几何特征, 而且可以避免产生孔洞. 这是由于该简化方法采用层次式的散乱点云简化方式, 首先采用阈值自适应点删除算法和基于曲率的点删除算法进行去噪, 实现点云初始简化, 然后通过融合曲率差、法向量差、投影距离和空间距离等4个特征算子来评估点的重要性, 进而在保持重要特征点的基础上对非特征点进行简化, 从而实现了点云精确简化, 是一种有效的点云简化方法. 而多特征保持简化法是一种对特征敏感的散乱点云简化方法, 通过提取边界点、计算法向量、提取谷脊点和非特征点来实现点云简化, 可以有效避免简化过度产生的孔洞现象, 但是抗噪性还有待提高; 结构信息约束简化法可以鲁棒地保持最佳三角面的形状和拓扑结构, 改善三维模型的重建效果, 但是对噪声文物点云数据模型的简化精度不够高; 支持向量回归简化法是一种基于ε-不敏感支持向量回归的三维点云特征敏感简化方法, 该方法通过识别高曲率区域实现尖锐边缘点的检测, 可以实现公共点云数据模型的有效简化, 但是对文物点云的简化容易造成孔洞.

5 结论

点云简化是点云数据模型预处理的重要环节之一, 可以在保留点云细节几何特征的基础上实现数据的最大化精简. 为了有效保持散乱点云的显著几何特征, 提出一种点重要性判断点云简化方法, 通过计算曲率差、法向量差、投影距离、空间距离等4个特征算子来评估点的重要性. 从对公共点云和文物点云数据模型的简化结果来看, 该方法可以有效保持点云细节几何特征, 避免孔洞的产生, 实现点云的有效简化, 对各种类型的点云模型的简化具有一定的普适性.