基于有结构信息参与的点对一致性投票的点云法向估计算法

Point Cloud Normal Estimation Algorithm Based on Point Pair Consistent Voting with Structural Information Participation

摘要: 基于平面拟合的算法被广泛地应用于估计点云的法向，近几年来，我们采用最小二乘拟合和加权的方法相结合的思想去估计点云的法向，但是对于尖锐特征附近的点，由于缺少点与平面的结构信息：点与平面法向之间的差异，就会使得法向异常的点对我们的影响比较大。为了减少这类点的影响，我们把邻域分割与平面拟合的思想相结合，提出了有结构信息参与的点对一致性投票的点云法向估计算法，它能更好地估计尖锐特征处点的法向。我们首先，对于当前点所使用的邻域构造协方差矩阵，刻画出点与尖锐特征的距离远近程度，然后再加入了点与平面的结构信息，最后使得拟合出来的正确平面评分较高。实验结果表明，我们的方法与PCV相比，在运行速度上基本一致。但是，我们对于点云法向的估计更为准确，对细节刻画地更好。

Abstract: The algorithm based on plane fitting is widely used to estimate the normal direction of point cloud. In recent years, we have adopted the idea of combining the least square fitting and the weighted method to estimate the normal direction of point cloud. However, for the points near sharp features, due to the lack of structural information of the point and plane: the difference between the point and the plane normal direction, the point with abnormal normal direction will have a greater impact on us. In order to reduce the influence of these points, we combine the idea of neighborhood segmentation and plane fitting, and propose a point cloud normal estimation algorithm with the participation of structure information, which can better estimate the normal direction of points with sharp features. First, we construct a covariance matrix for the neighborhood used by the current point, describe the distance between the point and the sharp feature, and then add the structure information of the point and the plane, and finally make the correct plane fit out have a large score. The experimental results show that our method is consistent with PCV in speed. However, our estimate of the normal direction of the point cloud is more accurate and better characterizes the details.

1. 简介

在三维点云数据中，法向是其重要的几何特征。在点云的重建、渲染、各向异性的光滑、分割、特征检测和提取等方面，我们都希望能够使用准确的法向量，来生成高质量的表面。近年来，对于得到高质量法向的算法有很多，但是由于噪声和采样不均匀的影响，如何能够可靠地估计扫描点云的法向量已经成为点云数据处理中的一个具有挑战性的工作。

对于估计点云法向的算法可分为：基于Voronoi/Delaunay算法[1]-[3]、基于法向修正的算法[4]-[6]、基于深度学习的算法[7]-[9]和基于平面拟合的算法[10]-[18]。

基于Voronoi/Delaunay算法[1]-[3]是指对于给定的点云集合，利用三角网格构建邻域之间的关系，然后通过这个关系来重新建立法向。该算法能够有效地处理不规则分布的点云，并且可以根据点云的几何特征生成高质量的网格结构。但是这个算法在处理大规模点云时，无法准确地处理噪声比较大的点云，算法的计算效率可能会降低，对噪声也比较敏感。

基于法向修正的算法[4]-[6]是指对于给定点的初始法向，利用邻域点之间的关系进行修正，使得修正之后的法向就是该点的最终法向。该算法利用了一种基于平滑策略的滤波方法，可以使三维模型的表面看起来更加光滑和自然。但是对于复杂的三维模型，可能会导致法向量出现过度平滑或者错误的方向，不能准确地恢复模型的尖锐特征。

基于深度学习的算法[7]-[9]是指借助神经网络所具备的自适应与自学习特性，从海量数据库里针对点云特征展开自动学习，并自动调节自身参数的过程，这能够让我们学习到点云的复杂几何结构与法向量之间的关系。该方法对含噪声和不规则的点云数据，展现出了不错的鲁棒性，能够处理复杂的点云模型，并且可以同时学习多个层次的特征，如局部的几何特征和全局的语义特征等。但是该方法在进行实验时，过程比较复杂，对设备的性能要求高，需要对大量的数据进行训练，时间成本较大。

基于平面拟合的算法[10]-[18]对于点云中的每个点，选取其部分邻域点，然后利用最小二乘法拟合的方法，来估计点的法向。该方法是由Hoppe等人[10]首次提出地，对于点云中的每个点，使用主成分分析法(Principal Component Analysis, PCA)，利用邻域内的所有点去拟合平面，得到的平面法向就是该点的法向。当点位于光滑曲面时，其邻域点都位于同一曲面，利用PCA就可以准确地估计该点的法向。但是当点位于尖锐特征处，其邻域点来自不同的曲面，在拟合时会受到位于其它曲面上点的影响，就会使得估计的法向过于平滑。为了提高法向估计结果的准确性，Pauly等人[11]利用当前点与邻域点的距离，构造高斯权函数，进行加权的操作，使得距离远的邻域点有较小的权重系数，减少了不同平面的点对拟合平面的影响。但在拟合过程中，该方法呈现各向同性，使得处于不同光滑曲面上的邻域点，也会被纳入计算，这将会使得拟合结果具有较大的误差。理想情况下，与当前点属于不同平面的点在拟合过程中应该被丢弃，Zhang等人[12]-[14]首先利用邻域分割的思想，对邻域内的所有点按照所处光滑曲面分为几个子邻域，然后从这些子邻域中选择一个最优的子邻域进行平面拟合。该方法减少了来自不同曲面上点的影响。但是对于高曲率的部分不太友好，且计算速度比较慢。Wang等人[15]利用鲁棒统计技术，引入了权重函数，对于与此点距离较远及法向差异较大的点赋予较小的权重，在拟合平面时减少异常点对候选平面的影响。然而这个算法对于非均匀采样的模型，估计的法向会偏向点密度较大的一侧，对尖锐特征点的估计也是不准确的。Boulch等人[16] [17]在采样时，对密度进行加权处理，使得密度较小时，赋予较大的权；能很好地克服采样密度不同对拟合平面所带来的影响。Zhang等人[18]将邻域分割与局部邻域拟合的思想结合在一起，提出了基于点对一致性投票的法向估计算法(pair consistency voting, PCV)。该算法利用两个点之间初始法向的差异来刻画点对位于同一平面可靠程度；在此基础上，利用点和平面之间的距离来刻画点与平面的位置关系。该方法在性能和运行效率上都有所提高，即使是在存在噪声和非均匀采样的情况下，也能够准确保留点云的结构信息。但是该算法只用残量刻画了点对和平面之间的距离信息，没有考虑点对和平面之间的结构信息，在尖锐特征处的法向估计地不太准确。

为了解决这个问题，本文加入了点对与候选平面之间的结构信息，提出了一种有结构信息参与的点对一致性投票的法向估计算法。该算法能有效的丢弃点之间法向差异不大，但点与候选平面法向差异较大的点对，能够获得更为准确的法向，对于尖锐特征处的点能刻画地更准确。

其中我们把与给定平面法向差异较大的点标为蓝色点，与给定平面法向差异较小的点标为红色点，蓝色和红色的点都是邻域内的点，红色点之间构成的是强电对，红色点与蓝色点以及蓝色点之间构成的是弱点对。灰色点是邻域外的点，绿色点是平面上的点，两条虚线是带宽，绿色实线代表给定的平面。可以看出本文算法能够更好地区分正确平面与倾斜平面之间的差异。

2. 本文算法

对于噪声点云$P={\left\{p_i\right\}}_{i=1}^n$ (其中$n$ 为采样点总数，$p_i=\left(x_i,y_i,z_i\right)$ )，在考虑了点对和平面的位置关系上，本文算法加入了点对和平面的结构信息。该算法在点对法向与候选平面法向差异较大时，可以更好地处理异常点对我们的影响，能得到更准确的法向估计。本文算法主要分为以下几个步骤：

首先，针对点云中的各个点，我们采用PCA算法进行初步的法向估计。具体做法是，通过邻域点构建协方差矩阵，该矩阵得到的特征值能够反映出点与尖锐特征之间的距离。因此，我们将点云中的点划分为两类：若点远离尖锐特征，其邻域点一般来自同一曲面，这类点被定义为光滑点；若点靠近尖锐特征，其邻域点则来自不同曲面，这类点被定义为候选点。

然后，我们在PCV的基础上，加入了点对与候选平面之间的结构信息，提出了有结构信息参与的点对一致性投票的点云法向估计算法。

最后，光滑点的初步法向是可靠的，我们就把光滑点的最终法向定义为PCA得到的初始法向。对于候选点的法向，它的结构比较复杂，PCA得到初始法向不能准确刻画候选点的结构信息，所以利用我们提出的算法来估计候选点$p_i$ 的法向。

针对步骤中的第一、二步，我们分别在2.1和2.2中进行详细的介绍。

2.1. 候选点选择

为了估计$p_i$ 的最初法向，利用协方差矩阵

$T_i=\frac{1}{S}\left[\begin{array}{c}{p}_i^1-{\widehat{p}}_i\\ ⋮\\ p_i^S-{\widehat{p}}_i\end{array}\right]\cdot {\left[\begin{array}{c}{p}_i^1-{\widehat{p}}_i\\ ⋮\\ p_i^S-{\widehat{p}}_i\end{array}\right]}^{\text{T}},p_i^j\in N_i,$ (1)

其中$N_i$ 为$p_i$ 的邻域，$S$ 为$N_i$ 的大小，$p_i^j$ 为邻域点，${\widehat{p}}_i$ 为邻域点的均值，$T_i$ 的最小特征值${\lambda }_0$ 所对应的特征向量就为$p_i$ 的初始法线。对于点$p_i$ ，我们利用$T_i$ 得到的特征值定义特征系数${\omega }_i$

${\omega }_i=\frac{{\lambda }_0}{{\lambda }_0+{\lambda }_1+{\lambda }_2},$ (2)

其中${\lambda }_i\left(i=0,1,2\right)$ 为协方差矩阵$T_i$ 的特征值，且$0\le {\lambda }_0\le {\lambda }_1\le {\lambda }_2$ 。

特征系数${\omega }_i$ 的大小决定了点$p_i$ 与尖锐特征的距离信息。当${\omega }_i$ 越接近0，则点$p_i$ 就离尖锐特征处越远，这时点$p_i$ 的邻域点都在同一平面上；${\omega }_i$ 值越大，则点$p_i$ 靠近尖锐特征，邻域点来自不同平面的可能性就越大。因此，当我们给出一个${\omega }_t$ 的值，如果${\omega }_i>{\omega }_t$ ，我们就认为点$p_i$ 为靠近尖锐特征处的点。$f_{\omega }$ 表示了${\left\{{\omega }_i\right\}}_{i=1}^n$ 的分布情况，最小化特征系数${\omega }_i$ 进行平滑

${\widehat{f}}_{\omega }=\arg \min {\Vert {\widehat{f}}_{\omega }-f_{\omega }\Vert }_F+\lambda {\Vert D{\widehat{f}}_{\omega }\Vert }_1,$ (3)

其中$\lambda$ 为权衡参数，$D$ 为一阶差分矩阵，${\Vert \cdot \Vert }_F$ 和${\Vert \cdot \Vert }_1$ 分别表示$F$ 范数和$L_1$ 范数，阈值${\omega }_t$ 定义为$f_{\omega }$ 达到第一个峰值后的平缓点，在我们的实验中，$\lambda$ 的值固定为1。

2.2. 有结构信息参与的点对一致性投票的点云法向估计算法

PCV的算法使用点对来进行法向估计，它为了减少尖锐特征附近来自不同平面邻域点的影响，其优化函数如下

${\theta }_i^{*}=\underset{\theta }{\arg \max }{\displaystyle \sum _{p_i^j,p_i^k\in N_i}\rho \left(p_i^j,\theta \right)\rho \left(p_i^k,\theta \right)}\cdot {\omega }_a\left(p_i^j,p_i^k\right){\gamma }_j^2{\gamma }_k^2,$ (4)

其中$\theta$ 代表一个平面，$\rho \left(p_i^j,\theta \right)=\exp \left(-r_{j,\theta }^2/{\sigma }_{r,i}^2\right)$ 是一个递减函数，$r_{j,\theta }$ 是点$p_i^j$ 到平面$\theta$ 的距离，${\omega }_a\left(p_i^j,p_i^k\right)=\exp \left({\cos }^{\alpha }\left(n_i^j,n_i^k\right)/{\sigma }_{a,i}^{\alpha }\right)$ 是高斯权函数，$n_i^k$ 是点$p_i^k$ 的初始法向，$\left(n_i^j,n_i^k\right)$ 是$n_i^j$ 和$n_i^k$ 之间的夹角，${\sigma }_{r,i}$ 和${\sigma }_{a,i}$ 都是高斯权函数的带宽参数，${\gamma }_j,{\gamma }_k$ 是密度权值。

PCV使用${\omega }_a\left(p_i^j,p_i^k\right)$ 来描述点对之间的结构信息，如果两个点的法向相近，则两个点位于同一平面的概率就大，即${\omega }_a\left(p_i^j,p_i^k\right)$ 就大；反之，${\omega }_a\left(p_i^j,p_i^k\right)$ 就小。使用$\rho \left(p_i^j,\theta \right)$ 来刻画点与平面的位置信息，如果点与平面的距离较近，则点对于平面的贡献就大；反之，贡献就小。

但是，对于尖锐特征处的点，如图1(a)所示，PCV所选择的邻域点中有与正确平面法向差异较大点，这会使正确平面的评分比较低，进而导致得到的平面出现倾斜。如图1(c)所示，对于倾斜平面而言，邻域点中有来自不同平面的点，也会导致倾斜平面的评分比较高，会使得尖锐特征处点的法向估计地不够准确。

Figure 1. Schematic diagrams of the PCV and ours algorithms

图1. PCV和我们的算法示意图

为了解决上述问题，本文在刻画点的平面的相似性上，加入了点对与候选平面的法向差异来刻画点对与候选平面的结构信息。我们的方法将目标函数改进为

${\theta }_i^{*}=\underset{\theta }{\arg \max }{\displaystyle \sum _{p_i^j,p_i^k\in N_i}\rho \left(p_i^j,\theta \right)\rho \left(n_i^j,\theta \right)\rho \left(n_i^k,\theta \right)}\cdot {\omega }_a\left(p_i^j,p_i^k\right){\gamma }_j^2{\gamma }_k^2$ (5)

我们定义

$\rho \left(n_i^j,\theta \right)={\left(n_i^j\cdot n_{\theta }\right)}^2,$ (6)

其中$n_{\theta }$ 为候选平面$\theta$ 的法向。

从${\theta }_i^{*}$ 的优化过程中，我们的方法加入了点对与候选平面的结构信息，$\rho \left(n_i^j,\theta \right)$ 和$\rho \left(n_i^k,\theta \right)$ 都大；即点对$p_i^j$ ，$p_i^k$ 对候选平面的贡献较大；反之，则贡献较小；若有一个较大，则点对对候选平面的贡献也较小。凭借这一性质，与$\theta$ 法向差异较大的候选点对在投票过程中起的作用较小，${\theta }_i^{*}$ 对所采用的带宽不敏感。

我们的方法加入了点对与候选平面的结构信息，利用候选平面的法向与点的法向之间的差异来量化点对与候选平面之间的结构信息。对于尖锐特征处的点，如图1(b)及图1(d)所示，我们的方法使得来自同一平面上的强点对我们的贡献较大，来自不同平面上的弱点对对我们的贡献较小，这样就能有效地减少来自不同平面上点的影响，使得法向估计地更为准确。如图1(b)所示，对于正确平面，我们的方法把来自不同平面的点对变成了弱点对，对平面的影响减小，使得正确平面得到的评分高，得到的法向估计更为准确。如图1(d)所示，对于倾斜平面，我们的方法使得强点对的数量减少，弱点对的数量增多。这就导致倾斜平面得到的评分较低，得到的法向估计就不准确。我们的方法使得拟合得到的平面与正确平面的相似性就高，得到的法向估计得就更准确。

我们使用的${\sigma }_{a,i}$ 与高斯分布中的方差有类似的作用。如果${\sigma }_{a,i}$ 的值大，则所有点对在拟合平面时的贡献相同。如果${\sigma }_{a,i}$ 的值小，则是两对具有相似角度的点对则共享相当不同的权值。对于每一个相邻的$p_i^j$ ，我们利用高斯函数计算出它与平面的距离残差，中位残差定义为这些残差的平均值。

3. 实验结果及分析

为了评估本文算法的性能，将本文算法与PCA和PCV的算法进行定量和定性的比较。

本文对含有多个光滑曲面和尖锐特征组成的模型：cylinder (100 k)，boxunion2 (100 k)，pipe (100 k)，pipe_curve (100 k)。cylinder模型是一个圆柱体，特征包括平面与曲面相交的尖锐边和直角；boxunion2模型是由多个四面体相交而成，特征包括平面相交的过渡边和基面相交的直角；pipe模型是由圆柱形的管道组成，特征包括2个曲面相交的直角以及两个紧挨着的曲面；pipe_curve模型是由圆柱面及曲面折叠而成，特征包括基面相交的直角、锐角等。这些模型均添加了高斯噪声，其中标准差定义形状对角线的边框长度的0，0.0025，0.012。

3.1. 参数选择

$S$ ：计算光滑点法向所用的邻域点的个数。

$S^{*}$ ：计算候选点法向所用的邻域点的个数。

$k$ ：距离邻域的大小。

其中，噪声水平决定$S$ 和$S^{*}$ 大小，对于邻域内点的个数$S$ 和$S^{*}$ ，噪声水平越高，它们就越大。在实验中，所有算法的邻域点个数$S=256$ ，$S^{*}=2\ast S$ ，其余相关参数都采用默认值。

3.2. 评价函数

为了对计算结果进行量化评估，我们使用均方根误差$\left(RMS\_\tau \right)$ 如下

$RMS{M}_{\tau }=\sqrt{\frac{1}{P}{\displaystyle \sum _{p\in P}{\left(f\left(\langle n_{p,ref},n_{p,est}\rangle \right)\right)}^2}},$ (7)

其中

$f\left(\langle n_{p,ref},n_{p,est}\rangle \right)=\{\begin{array}{l}\langle n_{p,ref},n_{p,est}\rangle ,若\langle n_{p,ref},n_{p,est}\rangle <\tau \\ \pi /2,否则\end{array}$

$\langle ,\rangle$ 为法向间夹角，$n_{p,ref}$ 是$p_i$ 处的参考法向，$n_{p,est}$ 是估计法向。本文中取$\tau ={10}^0$ ，即$n_{p,ref}$ 与$n_{p,est}$ 的值大于$\tau$ 时，认为此点估计不准确。

3.3. 结果分析

图2给出了3种算法在多个模型上$RMS\_\tau$ 的变化情况，表1展示了3种算法在多个模型上的$RMS\_\tau$ 均值，表2给出我们的方法对不同模型的可视化结果。

PCA算法能够准确估计光滑曲面上的光滑点的法向，即使是在采样不均匀的情况。但是对于尖锐特征处的点，该算法估计的法向误差比较大。其原因是PCA算法在进行平面拟合时，选择了邻域内所有点，导致其$RMS\_\tau$ 值比其它算法要高。对于尖锐特征处点的邻域是来自不同光滑曲面上的点组合而成，在选择邻域点时，容易把其他光滑曲面上点考虑在内，这会导致位于尖锐特征附近的点，其法向估计存在偏差，不够准确。

(a) cylinder (100 k) (b) boxunion2 (100 k)

(c) pipe (100 k) (d) pipe_curve (100 k)

Figure 2. The variation of the $RMS\_\tau$ values on different models with the noise

图2. 不同模型上的$RMS\_\tau$ 值随噪声的变化情况

Table 1. The average value $RMS\_\tau$ of various models

表1. 不同模型上的$RMS\_\tau$ 均值

模型	cylinder	boxunion2	pipe	pipe_curve	Average
PCA	0.505	0.996	0.501	0.605	0.652
PCV	0.132	0.358	0.232	0.292	0.254
Ours	0.130	0.348	0.222	0.284	0.246

PCV算法与PCA相比，它的法向估计的比较准确，能很好地恢复模型的特征，其所得到的$RMS\_\tau$ 远远低于PCA。但是由于PCV算法只考虑了点对之间的法向差异以及点对与候选平面之间的距离信息，没有考虑点对与候选平面之间的结构信息，使得对候选点的法向估计地不够准确，在拟合平面时会有一定的影响。如表1所示，我们的方法加入了点对与候选平面之间的结构信息，所得到的$RMS\_\tau$ 均值要比PCV低一些。

Table 2. Visual comparison of normal estimation results under different noise conditions

表2. 不同噪声法向估计结果的可视化比较

模型	No noise	Low noise	High noise
pipe_curve
boxunion2
column_head
star_smooth
cylinder

本文算法对于不同模型的无噪声、低噪声、高噪声都能得到较好的结果。从表1来看，我们的方法能得到最低的$RMS\_\tau$ 均值。从图2来看，对于模型在无噪声与低噪声的情况下，我们方法的$RMS\_\tau$ 值远远低于PCA且与PCV基本持平；在高噪声的情况下，我们方法的$RMS\_\tau$ 值低于PCA与PCV。从表2的结果来看，本文算法对尖锐特征点处理的很好，且尖锐特征处的法向估计的比较准确，对于模型在尖锐特征处的结构信息，能够有效留存，获得高品质的法向。

为了评估我们方法的性能，我们设置邻域大小$S=256$ ，其余参数均采用默认值，给出了一些模型视觉效果及细节图。如表2所示，我们的方法在处理尖锐特征模型时，明显减少了来自不同曲面的影响(如表2的pipe_curve模型和cylinder)。处理更为复杂的模型时，我们的方法也能够很好处理尖锐特征附近点的法向(如表2的boxunion2模型和column_head模型)。对于有着各向异性的候选点的法向，我们的方法在估计法向时也不会严重的法向偏差(如表2的star_smooth模型)。

3.4. 时间比较

我们的方法运行时间比PCA要长，但效果是远远高于PCA；与PCV相比，运行时间基本持平，但实验结果比PCV要好。

4. 结论

我们在PCV的基础上，加入了点对与候选平面之间的结构信息：点对与候选平面之间的法向差异，提出了一种有结构信息参与的点对一致性投票的点云法向估计算法。该算法对于点之间法向差异较小，但和候选平面法向差异较大的点对，有很好的筛选作用，能够有效地减少这类点在法向估计时对我们的影响，使得估计点的法向更加准确，更接近于真实的法向。但是我们的所有实验均是在固定参数下进行的，会不可避免地平滑掉点云的一些小细节，对于越精细复杂的模型，它的影响就越大。如何根据细节来自动调节参数是我们未来仍要进一步讨论的问题。

基金项目

国家自然科学基金(62076115)；辽宁省教育厅基金面上项目(LJKMZ20221434)。

NOTES

^*通讯作者。