基于自适应邻域的点云法向估计算法

Point Cloud Normal Estimation Algorithm Based on Adaptive Neighborhoods

摘要: 法向量是点云的重要几何属性，能够刻画点云的局部结构。因此快速且准确地估计法向量是非常重要的。在估计点云中某一点的法向时，必然要考虑到其局部邻域。在许多估计点云法向的方法中，使用固定邻域无法满足点云中所有点对于邻域的最佳选择。因此本文提出一种基于自适应邻域的点云法向估计算法，以提高点云法向估计的准确性和可靠性。实验结果表明，将自适应邻域算法应用到多种法向估计方法中，法向估计的质量都有所提升。

Abstract: The normal vector is a crucial geometric attribute of point clouds, capable of characterizing the local geometry of the data. Therefore, rapidly and accurately estimating normals is of great importance. When estimating the normal for a point in a cloud, its local neighborhood must be considered. In many existing normal estimation methods, using a fixed neighborhood fails to meet the optimal selection criteria for all points within the cloud. To address this, this paper proposes a point cloud normal estimation algorithm based on adaptive neighborhoods, aiming to improve the accuracy and reliability of the estimations. Experimental results demonstrate that applying the adaptive neighborhood strategy to various existing normal estimation methods leads to a consistent improvement in the quality of the estimated normals.

1. 引言

点云作为三维空间中离散点的集合，能高效且较为准确地描述出现实世界中物体的三维信息，在多个邻域都发挥了重要作用。而法向量是点云的重要几何属性，在点云数据的分析处理过程中，快速且准确地估计法向量是非常重要的工作。点云的重建、渲染、各向异性的光滑、分割、特征检测和提取等诸多应用，都依赖于高质量的法向信息[1] [2]。

近年来大量学者提出多种点云法向估计的方法。点云法向估计算法可分为基于Voronoi/Delaunay的算法[3] [4]、基于法向修正的算法[5]-[7]、基于局部邻域拟合的算法[1] [2] [8]-[17]。

基于Voronoi/Delaunay的算法[3] [4]是比较早期的点云法向估计算法，其核心思想是利用Voronoi图及其对偶图Delaunay三角剖分揭示点云空间分布结构，并基于该结构进行法向估计。然而，正如原作者Amenta等人[3]指出，该方法的有效性严格依赖于“无噪声”和“均匀采样”的理想前提。由于该方法对点的空间位置极度敏感，导致其在面对真实场景中不可避免的噪声和非均匀采样时，法向估计的准确性会显著下降。

基于法向修正的算法[5]-[7]是一类对于初始法向进行修正的算法。Alexa等人[5]提出了一种移动最小二乘法(Moving Least Squares, MLS)来定义光滑的解析曲面，实现对点云法向的修正。Jones等人[6]将法向修正问题定义为一个能量最小化问题，并构建了一个二次能量函数，实现法向量的全局优化修正。Calderon等人[7]提出了一种迭代的邻域重组算法。该方法基于当前法向，反复地筛选和优化每个点的局部邻域，从而计算出更准确的法向。但是这类方法对于初始法向的要求较高，同时无法很好地保留尖锐特征处的细节。

基于局部邻域拟合的算法[1] [2] [8]-[17]是研究最广泛的方法。最早Hoppe等人[2]提出利用最小二乘拟合方法估计法向，该方法也被称作主成分分析法(Principal Component Analysis, PCA)。PCA方法[2]的基本思想为对于点云中的一个点，其局部表面近似为一个平面，拟合平面的法向量视为该点的法向。随后，许多学者在此基础上进行改进。Pauly等人[8]利用高斯权重对邻域点进行距离加权，对距离当前点较近的邻域点赋予更大的权重，使该邻域点在平面拟合的过程中发挥更大的作用。Cazals等人[9]和Guennebaud等人[10]提出替换平面的方法，分别使用球面和二次曲面代替平面进行局部邻域的拟合。然而，以上方法均难以适应点云局部结构的变化，尖锐特征处法向估计光滑的现象只会得到缓解，而不会被消除，所以在尖锐特征附近法向估计结果的质量依旧不理想[18]。

为了筛选与当前点在同一平面的邻域点，学者们提出多种方法进行法向估计。Li等人[1]提出一种基于鲁棒统计的法向估计算法(Robust Normal Estimation, RNE)。文献[11] [12]引入鲁棒统计思想来改进传统算法，旨在拟合局部表面时，既能平滑噪声又能有效保持尖锐特征处的细节。但它们的算法对参数设置较为敏感[13]。Zhang等人[14]首次将低秩子空间聚类(Low Rank Representation, LRR)算法引入法向估计，将特征点的邻域分割成多个光滑的子邻域，在其中选择一最优子邻域进行拟合，提升了尖锐特征处法向估计的质量。但是该方法的时间成本较高[18]。在此基础上，Liu等人[15]给出了LRR的加速版本(Fast Low Rank Representation, LRRfast)。为应对复杂的几何结构，Zhang等人[16]构建了一个点对一致性投票(Pair Consistency Voting, PCV)框架，将局部曲面拟合与子空间分割相结合。Boulch等人[17]将霍夫变换与均匀采样策略相融合，提出一种保特征的法向估计算法(Hough Transform, HF)。但是该算法在运算过程中需要多次对法向空间离散和投票，并且不确定的参数较多，导致运算的成本比较大[19]。

虽然上述算法在点云法向估计方向的研究都取得了一定的进展，但大部分都使用全局固定邻域尺度，使用大邻域会使得平坦处法向估计结果的鲁棒性更强，但会使尖锐特征处丢失细节，而使用小邻域会有相反的结果。

Table 1. Normal estimation results of the PCA method using two different neighborhood sizes on various point clouds. The root mean square (RMS) error of the normal angles is given below each model, and point color represents the per-point normal angle error. The results demonstrate that point cloud models with different noise scales require different global fixed neighborhood sizes

表1. PCA方法使用两种不同邻域大小在不同点云上的法向估计结果。每个点云下方给出了法向角度的均方根误差值(RMS)。点云的颜色代表各点的法向角度误差。结果显示，不同噪声尺度的点云模型需要使用不同大小的全局固定邻域

(a) 干净无噪声				(b) 有噪声
$\begin{array}{c}N=16\\ RMS=0.094\end{array}$		$\begin{array}{c}N=64\\ RMS=0.136\end{array}$		$\begin{array}{c}N=16\\ RMS=0.153\end{array}$		$\begin{array}{c}N=64\\ RMS=0.142\end{array}$
	$<$				$>$

由表1可知，在PCA方法中使用全局固定邻域尺度无法满足不同点对于邻域尺度的要求。在各处均平坦的点云模型上使用大邻域或小邻域都可以，无需考虑自适应邻域。然而，在实际应用过程中，处处平坦的模型几乎不存在，所用点云模型都会存在尖锐特征。由表1中的(a)可知，在干净无噪声的点云模型中，平坦区域使用大邻域或小邻域都可以。但对于尖锐特征附近的点，使用小邻域的法向估计结果更好。同时，现在所用的点云数据多是由扫描仪等设备得到，得到的点云数据不可避免会有噪声。由表1中的(b)可知，在存在噪声的点云模型中，平坦区域使用大邻域更好，可以减少噪声的影响，在尖锐特征附近使用小邻域得到的法向估计结果质量更高。

不过，也有许多学者在点云法向估计方法中引入自适应策略。Mitra等人[20]提出自适应选择邻域大小的方法，但该方法在实际应用中的易用性和鲁棒性不强。当参数选择不当或噪声水平比较高时，这个方法的性能不尽如人意[21]。Li等人[1]提出自适应噪声尺度估计的方法，利用自适应估计的局部噪声尺度来定义和控制算法中其他关键参数。但该方法需要尖锐特征附近的点密度较高，这不适用于实际扫描的、稀疏或不均匀的点云[13]。Wang等人[13]提出迭代重加权平面拟合的法向估计算法，并针对带宽这一参数提出自适应带宽策略。然而，这个算法在使用中存在一定的局限性，由于其使用了距离权重、残差权重和法向差异权重这三种权重，导致其无法广泛地应用于其它算法中。

基于以上研究，本文提出一种基于自适应邻域的点云法向估计算法，针对点的几何特征自适应地确定邻域大小，在保留几何特征的同时减小噪声对法向估计的影响。自适应邻域方法能够使得处于平坦处的点得到较大的邻域，越接近尖锐特征处的点的邻域越小，尽可能使邻域只包含与当前点在同一表面的点。这样每个点都能够得到更好的邻域去计算法向，使得点云的法向估计结果更加准确。自适应邻域算法首先给定一个初始邻域，接下来在初始邻域的基础上逐步增长邻域大小，每次增长的邻域点个数为设定的固定数值。在增长邻域的过程中，对当前邻域内的点的初始法向进行实时监测。当邻域点的法向差异达到阈值时，停止增长邻域，将上一次增长后的邻域作为当前点的邻域。实验表明，本文算法能够根据点的几何特征自适应地确定最佳邻域，提升点云法向估计的准确性和可靠性，能够对使用全局固定邻域尺度的法向估计方法进行优化，得到更高质量的点云法向估计结果。

2. 本文算法

对于给定的噪声点云$P={\left\{p_i\right\}}_{i=1}^n$ ($n$ 为采样点的个数)，本文通过分析点与其邻域内其他点的法向差异，构造了一种自适应邻域方法(见2.1节)，用于提升点云法向估计质量。该算法能够对点云中每一个点自适应地给出合适的邻域，所得邻域可以在PCA、距离加权最小二乘拟合等法向估计方法中使用(见2.2节)，提高点云法向估计结果的准确性。

2.1. 自适应邻域

2.1.1. 算法过程

自适应邻域的算法过程如图1所示。

Figure 1. Algorithm process

图1. 算法过程

由于本文算法中自适应邻域的确定需要使用点云中所有点的初始法向$N_0={\left\{n_i^o\right\}}_{i=1}^n$ ，下面对于如何得到所有点的初始法向$N_0$ 进行简要说明。对当前点$p_i$ 计算其大小为$k_0$ 的邻域，$k_0$ 是初始邻域大小。对于该邻域可使用多种方法计算初始法向，本文采用PCA方法[2]计算当前点$p_i$ 的初始法向$n_i^0$ 。对点云中其他点采用同样的方法计算初始法向，进而可得到所有点的初始法向$N_0={\left\{n_i^o\right\}}_{i=1}^n$ 。

自适应邻域的算法以当前点$p_i$ 、初始邻域$N_i^0=\left\{p_i^j|j=1,2,\cdots ,k_0\right\}$ 、所有点的初始法向$N_0={\left\{n_i^o\right\}}_{i=1}^n$ 、法向的角度差异阈值${\theta }_{\max }$ 、邻域的最大增长次数$m_{\max }$ 和每次增长的邻域点个数$s$ 作为输入。输出自适应邻域大小$\tilde{k}$ ，进而得到当前点$p_i$ 的自适应邻域${\tilde{N}}_i=\left\{p_i^j|j=1,2,\cdots ,\tilde{k}\right\}$ 。

当前点$p_i$ 可能是尖锐特征附近的点，也有可能是平坦处的点，为了有效保留尖锐特征处的几何细节，将初始邻域大小$k_0$ 设置为一个较小的值。自适应邻域算法的核心步骤是逐步增长邻域大小，所以增长邻域的过程何时终止是一个关键问题。本文给出一种评价方式，首先计算当前邻域内法向的角度差异${\theta }_i$ ，再将${\theta }_i$ 与法向的角度差异阈值${\theta }_{\max }$ 进行比较，进而判断增长过程是否终止，增长过程终止后即可确定最终的自适应邻域。

2.1.2. 自适应邻域的确定

下面先介绍如何计算法向的角度差异${\theta }_i$ 。

设在某次增长邻域后$p_i$ 邻域大小为$k$ (若是第0次增长，则$k=k_0$ )，采用$k$ 近邻(KNN)方法[2]得到当前邻域$N_i=\left\{p_i^j|j=1,2,\cdots ,k\right\}$ ，利用初始法向$N_0$ 得到当前邻域点的法向集$N_i=\left\{n_i^j|j=1,2,\cdots ,k\right\}$ 。下面计算法向的角度差异${\theta }_i$ ，考察法向集$N_i$ 中法向的一致性。

定义法向量的平均法向为：

${\overline{n}}_i=\frac{\frac{1}{k}{\displaystyle \sum _{j=1}^k{\widehat{n}}_i^j}}{{\Vert \frac{1}{k}{\displaystyle \sum _{j=1}^k{\widehat{n}}_i^j}\Vert }_2}$ , (1)

其中，${\widehat{n}}_i^j=\frac{n_i^j}{{\Vert n_i^j\Vert }_2}$ ，$n_i^j\in N_i$ 。平均法向近似代表了局部邻域的主方向。下面定义${\theta }_i^j$ 表示当前邻域内邻域

点的初始法向与平均法向${\overline{n}}_i$ 之间的角度，该夹角的大小反映了单个邻域点的法向量相对于整体平均方向的偏离程度。${\theta }_i^j$ 可通过将${\widehat{n}}_i^j$ 与平均法向${\overline{n}}_i$ 点积计算得到，即${\theta }_i^j=\arccos \left({\widehat{n}}_i^j\cdot {\overline{n}}_i\right)$ 。再将${\theta }_i^j$ 进行平方和累加，取均值，即可得到法向的角度差异${\theta }_i$ ，即

${\theta }_i=\frac{1}{k}{\displaystyle \sum _{j=1}^k{\left({\theta }_i^j\right)}^2}$ . (2)

${\theta }_i$ 的大小与当前点$p_i$ 所在位置的局部几何结构有关。$p_i$ 在平坦区域上，${\theta }_i$ 较小，$p_i$ 在尖锐特征附近，${\theta }_i$ 较大。

为了判断增长过程何时终止，需要将法向的角度差异${\theta }_i$ 与法向的角度差异阈值${\theta }_{\max }$ 进行比较。若${\theta }_i>{\theta }_{\max }$ ，则停止增长邻域。若${\theta }_i\le {\theta }_{\max }$ ，则继续增长邻域，下一次的邻域点个数为$k+s$ ，按照上面同样的方法计算法向的角度差异${\theta }_i$ ，再与${\theta }_{\max }$ 比较。

所以，停止增长邻域的情况有两种：

情况1：当增长次数达到邻域的最大增长次数$m_{\max }$ 时，停止增长。

此时，当前点$p_i$ 的最大邻域内的法向差异是较小的，说明$p_i$ 是处于平坦区域的点，则将增长过程中的最大邻域作为自适应邻域。这样即可实现，对于平坦处的点使用较大邻域，减小噪声的干扰。此时邻域增长次数为$m_{\max }$ ，自适应邻域大小$\tilde{k}=k_0+s\times m_{\max }$ 。

情况2：当$\theta >{\theta }_{\max }$ 时，停止增长。

此时，当前点$p_i$ 的当前邻域内的法向差异过大已无法满足要求，说明$p_i$ 是尖锐特征处的点或者是靠近尖锐特征的点。

(1) 若$p_i$ 是尖锐特征处的点，则将初始邻域作为自适应邻域。此时增长次数为0，自适应邻域大小$\tilde{k}=k_0$ 。

(2) 若$p_i$ 是靠近尖锐特征的点，则将上一次增长后的邻域作为最终的自适应邻域，上一次增长后的邻域大小$k-s$ 即为自适应邻域的大小$\tilde{k}$ 。这样即可实现，靠近尖锐特征处的点的邻域选取尽量大，在不将其他表面的点作为邻域点的同时，最大程度上降低噪声对法向估计结果的影响。此时增长次数大于等于1且小于$m_{\max }$ ，自适应邻域大小$\tilde{k}$ 满足$k_0\le \tilde{k}<k_0+s\times m_{\max }$ 。

最后，采用$k$ 近邻(KNN)方法[2]得到当前点$p_i$ 的自适应邻域${\tilde{N}}_i=\left\{p_i^j|j=1,2,\cdots ,\tilde{k}\right\}$ 。这样即可实现为点云中每一点确定一个合适的邻域大小，用于后续的法向估计过程中。

2.2. 法向估计

2.2.1. 基于自适应邻域的PCA方法(PCA_ad)

PCA方法[2]是点云法向估计的一种常用方法，本部分将介绍应用自适应邻域的PCA方法，简记为PCA_ad。

对于点云数据$P={\left\{p_i\right\}}_{i=1}^n$ ，对于当前点$p_i$ ，给定初始邻域$N_i^0=\left\{p_i^j|j=1,2,\cdots ,k_0\right\}$ 、所有点的初始法向$N_0={\left\{n_i^o\right\}}_{i=1}^n$ 、法向的角度差异阈值${\theta }_{\max }$ 、邻域的最大增长次数$m_{\max }$ 和每次增长的邻域点个数$s$ ，可根据2.1节中的自适应邻域算法确定$p_i$ 的自适应邻域为${\tilde{N}}_i=\left\{p_i^j|j=1,2,\cdots ,\tilde{k}\right\}$ 。

下面采用文献[2]中的PCA方法估计法向。首先对于点$p_i$ 计算其自适应邻域${\tilde{N}}_i=\left\{p_i^j|j=1,2,\cdots ,\tilde{k}\right\}$ 的协方差矩阵，协方差矩阵的定义为

$C_i=\frac{1}{\tilde{k}}\left[\begin{array}{c}{p}_i^1-{\overline{p}}_i\\ ⋮\\ p_i^{\tilde{k}}-{\overline{p}}_i\end{array}\right]\times {\left[\begin{array}{c}{p}_i^1-{\overline{p}}_i\\ ⋮\\ p_i^{\tilde{k}}-{\overline{p}}_i\end{array}\right]}^{\text{T}},p_i^j\in {\tilde{N}}_i$, (3)

其中，${\overline{p}}_i$ 是邻域点的均值，$\times$ 代表矩阵的乘法。对协方差矩阵$C_i$ 进行特征分解

$C_i{v}_m={\lambda }_m{v}_m,m=1,2,3$ , (4)

其中，${\lambda }_1\le {\lambda }_2\le {\lambda }_3$ 为特征值，$v_1$ ，$v_2$ ，$v_3$ 是对应的单位特征向量。最小特征值${\lambda }_1$ 对应的特征向量$v_1$ 即为局部表面的法向，故PCA_ad方法的最终输出法向$n_i=v_1$ 。

2.2.2. 基于自适应邻域的距离加权最小二乘拟合方法(disW_ad)

距离加权最小二乘拟合方法(disW) [8]也是点云法向估计的经典方法之一，本部分将介绍应用自适应邻域的距离加权最小二乘拟合方法，简记为disW_ad。

对于点云数据$P={\left\{p_i\right\}}_{i=1}^n$ ，对于当前点$p_i$ ，给定初始邻域$N_i^0=\left\{p_i^j|j=1,2,\cdots ,k_0\right\}$ 、所有点的初始法向$N_0={\left\{n_i^o\right\}}_{i=1}^n$ 、法向的角度差异阈值${\theta }_{\max }$ 、邻域的最大增长次数$m_{\max }$ 、每次增长的邻域点个数$s$ 和随机生成的候选平面数量$t$ ，可根据2.1节中的自适应邻域算法计算出$p_i$ 的自适应邻域为

${\tilde{N}}_i=\left\{p_i^j|j=1,2,\cdots ,\tilde{k}\right\}$ . (5)

下面采用文献[8]中的距离加权最小二乘拟合方法估计法向。该方法的核心思想是最小化一目标函数，得到能量值最小的拟合平面。目标函数如下

${\theta }_i^{\ast }=\underset{\theta }{\arg \min }{\displaystyle \sum _{p_i^j\in {\tilde{N}}_i}{r}_{j,\theta }^2\cdot w_d\left(p_i,p_i^j\right)}$ , (6)

其中，$\theta$ 是候选平面，${\tilde{N}}_i$ 是当前点$p_i$ 的自适应邻域，$r_{j,\theta }$ 是邻域点$p_i^j$ 到候选平面$\theta$ 的距离(拟合残差)。$w_d\left(p_i,p_i^j\right)$ 是一高斯权重函数，其值大小与邻域点$p_i^j$ 和当前点$p_i$ 的距离有关，距离越小，权重值越大。$w_d\left(p_i,p_i^j\right)$ 定义如下

$w_d\left(p_i,p_i^j\right)=\exp \left(-\frac{{\Vert p_i^j-p_i\Vert }_2^2}{{\sigma }_d^2}\right)$ , (7)

其中距离带宽${\sigma }_d=\alpha \cdot \frac{1}{\tilde{k}}\cdot {\displaystyle \sum _{j=1}^{\tilde{k}}{\Vert p_i^j-p_i\Vert }_2}$ ，$\alpha$ 为距离带宽的调整系数，用于控制权重函数对距离的敏感程度。

距离加权最小二乘拟合方法最小化目标函数的过程如下。首先利用自适应邻域${\tilde{N}}_i$ 中的邻域点随机生成多个候选平面，再根据目标函数计算出每个候选平面的能量值，最后筛选出能量值最小的候选平面，将该平面的法向$n_i$ 作为当前点$p_i$ 的法向。故$n_i$ 即为disW_ad方法的输出法向。

3. 实验结果及分析

为了评估自适应邻域算法的性能，本文将PCA与PCA_ad，disW与disW_ad分别进行比较。本文测试包含多种光滑曲面和尖锐特征的合成模型，对所有模型添加中心高斯噪声，标准差定义为点间平均距离的百分比，分别为30%，40%，50%，60%。

3.1. 参数的选择

自适应邻域算法中主要有四个参数，分别是

$k_0$ ：初始邻域大小。

${\theta }_{\max }$ ：法向的角度差异阈值。

$m_{\max }$ ：邻域的最大增长次数。

$s$ ：邻域增长过程中每次增长的邻域点个数。

disW_ad中还包括另外两个参数，分别是

$t$ ：随机生成的候选平面数量。

$\alpha$ ：距离带宽的调整系数。

在实验的过程中，采用了5个不同的初始邻域大小$k_0$ ，分别为10、20、30、40、50。为进一步验证初始邻域大小$k_0$ 对算法性能的影响，进行了下面的实验。选择模型Fandisk (77 K)，其噪声水平设定为40%，固定法向的角度差异阈值${\theta }_{\max }=0.05$ ，最大增长次数$m_{\max }=50$ ，每次增长的邻域点个数$s=5$ ，分别取$k_0=10,20,30,40,50$ 进行实验，记录不同$k_0$ 下的$RMS$ 值和$RM{S}_{\tau }$ 值。实验结果见表2，当$k_0$ 从10增加到50时，误差变化幅度较小，说明算法对$k_0$ 在10~50范围内具有较好的鲁棒性。这也说明初始邻域大小$k_0$ 在一定范围内波动不会显著影响法向估计的质量，验证了本文所选$k_0$ 范围的合理性。

Table 2. Influence of parameter $k_0$ on normal estimation accuracy

表2. 参数$k_0$ 对法向估计精确度的影响

	PCA_ad		disW_ad
$k_0$	$RMS$	$RM{S}_{\tau }$	$RMS$	$RM{S}_{\tau }$
10	0.1916	0.6487	0.2112	0.6946
20	0.1657	0.5357	0.1579	0.5212
30	0.1752	0.5711	0.1629	0.5441
40	0.1843	0.6069	0.1701	0.5686
50	0.1943	0.6364	0.1769	0.5952

${\theta }_{\max }$ 选取为0.05，该参数的确定需经过实验调试。这是因为若${\theta }_{\max }$ 选取过大，则邻域增长停止的条件过于宽松，可能会导致跨越尖锐特征，使得法向估计结果在特征处过于光滑。若${\theta }_{\max }$ 选取过小，则可能由于初始法向估计的误差导致增长过程提前终止，邻域增长的次数不足。${\theta }_{\max }$ 的选取实验如下。在Fandisk (77 K)模型(噪声40%)上进行实验，固定初始邻域大小$k_0=20$ ，最大增长次数$m_{\max }=50$ ，每次增长的邻域点个数$s=5$ 。变化参数${\theta }_{\max }=0.01,0.03,0.05,0.07,0.09$ ，实验结果见表3。

Table 3. Influence of parameter ${\theta }_{\max }$ on normal estimation accuracy

表3. 参数${\theta }_{\max }$ 对法向估计精确度的影响

	PCA_ad		disW_ad
${\theta }_{\max }$	$RMS$	$RM{S}_{\tau }$	$RMS$	$RM{S}_{\tau }$
0.01	0.1718	0.5698	0.1702	0.6107
0.03	0.1655	0.5359	0.1583	0.5262
0.05	0.1657	0.5357	0.1579	0.5212
0.07	0.1665	0.5410	0.1579	0.5208
0.09	0.1674	0.5472	0.1577	0.5201

综合考虑表3中的$RMS$ 值和$RM{S}_{\tau }$ 值，当${\theta }_{\max }=0.05$ 时，PCA_ad方法的$RM{S}_{\tau }$ 值最低，$RMS$ 值相较于最优值相差很小。disW_ad方法的$RMS$ 值和$RM{S}_{\tau }$ 值在${\theta }_{\max }=0.05$ 时的大小与最优值也相差很近。因此，最终选定${\theta }_{\max }$ 值为0.05。

对于其它参数，$m_{\max }$ 设置为50，确保自适应邻域的选取范围足够大。$s$ 设置为5，提高自适应邻域的精确度。disW_ad中的$t$ 和$\alpha$ 分别取200和1.0已在实验中表现良好，无需频繁调整。

PCA和disW中固定邻域尺度分别选定为10，20，30，40，50，100，150，200，250，300，400，500，分别选择固定邻域下的最优结果与应用自适应邻域算法后的最优结果(固定${\theta }_{\max }=0.05$ ，从$k_0=10,20,30,40,50$ 的结果中确定最优结果)进行比较。

3.2. 评价函数

本文采用均方根误差($RMS$ ) [19]和具有阈值的均方根误差($RM{S}_{\tau }$ ) [19]对法向估计的结果进行定量评估。

均方根误差($RMS$ )对算法结果进行全局性评估，计算所有点的法向估计误差，公式为

$RMS\text{=}\sqrt{\frac{1}{\left|P\right|}{\displaystyle \sum _{p\in P}{\langle n_{p,\text{ref}},n_{p,\text{est}}\rangle }^2}}$ , (8)

其中，$P$ 是点云数据集，$n_{p,\text{ref}}$ 是真实法向，$n_{p,\text{est}}$ 是估计法向，$\langle n_{p,\text{ref}},n_{p,\text{est}}\rangle$ 代表真实法向和估计法向之间的夹角。

具有阈值的均方根误差($RM{S}_{\tau }$ )对算法结果进行针对性评估，只计算真实法向与估计法向之间的夹角超过阈值$\tau$ 的点的误差，侧重于算法处理不好的区域(如边缘、噪声点)，公式为

$RM{S}_{\tau }=\sqrt{\frac{1}{\left|P\right|}{\displaystyle \sum _{p\in P}{v}_p^2}}$ , (9)

其中，$v_p=\{\begin{array}{l}\langle n_{p,\text{ref}},n_{p,\text{est}}\rangle 若\langle n_{p,\text{ref}},n_{p,\text{est}}\rangle <\tau \\ \pi /2否则\end{array}$ ，$\langle n_{p,\text{ref}},n_{p,\text{est}}\rangle$ 代表真实法向和估计法向之间的夹角。本文中$\tau ={10}^{\circ }$ 。当真实法向与估计法向之间的夹角大于$\tau$ 时，启用惩罚机制，赋夹角值为$\frac{\pi }{2}$ ，并将此点的法向估计结果视为不准确。

3.3. 结果分析

本文使用PCA、PCA_ad、disW和disW_ad方法在四个模型上进行点云法向估计，表4~7展示了这四种方法对不同噪声水平的模型的$RMS$ 值和$RM{S}_{\tau }$ 值的对比结果，表格中数值取最优尺度时的$RMS$ 值和$RM{S}_{\tau }$ 值，最优尺度分别由12个固定邻域尺度和5个不同的初始邻域大小$k_0$ 确定。图2是表4~7的整合，展示了四个模型的$RMS$ 均值和$RM{S}_{\tau }$ 均值。图3展示不同模型的自适应邻域热力图。表8是不同算法法向估计结果误差的可视化比较。

Table 4. Comparison of different methods under varying noise levels for the Fandisk (77 K) model

表4. Fandisk (77 K)模型在不同噪声水平下不同方法的对比

Fandisk (77 K)
	$RMS$				$RM{S}_{\tau }$
噪声	30%	40%	50%	60%	30%	40%	50%	60%
PCA	0.1678	0.1806	0.1879	0.1955	0.5260	0.5709	0.5956	0.6246
PCA_ad	0.1498	0.1657	0.1712	0.1814	0.4944	0.5357	0.5584	0.5926
disW	0.1622	0.1761	0.1852	0.1941	0.5294	0.5732	0.6052	0.6386
disW_ad	0.1458	0.1579	0.1688	0.1759	0.4937	0.5212	0.5630	0.5862

Table 5. Comparison of different methods under varying noise levels for the Anchor (40 K) model

表5. Anchor (40 K)模型在不同噪声水平下不同方法的对比

Anchor (40 K)
	$RMS$								$RM{S}_{\tau }$
噪声	30%		40%		50%		60%		30%		40%		50%		60%
PCA	0.1650		0.1711		0.1823		0.1893		0.5784		0.6012		0.6472		0.6698
PCA_ad	0.1521		0.1635		0.1712		0.1781		0.5354		0.5904		0.6149		0.6557
disW		0.1585		0.1694		0.1780		0.1880		0.5504		0.5990		0.6445		0.6797
disW_ad		0.1496		0.1559		0.1673		0.1775		0.5402		0.5745		0.6225		0.6592

Table 6. Comparison of different methods under varying noise levels for the Cylinder (60 K) model

表6. Cylinder (60 K)模型在不同噪声水平下不同方法的对比

Cylinder (60 K)
	$RMS$				$RM{S}_{\tau }$
噪声	30%	40%	50%	60%	30%	40%	50%	60%
PCA	0.1153	0.1232	0.1293	0.1334	0.3272	0.3496	0.3747	0.3865
PCA_ad	0.1007	0.1062	0.1101	0.1132	0.2945	0.3283	0.3375	0.3495
disW	0.1083	0.1155	0.1248	0.1300	0.3194	0.3361	0.3714	0.3894
disW_ad	0.0882	0.0957	0.1008	0.1079	0.2799	0.2993	0.3197	0.3451

Table 7. Comparison of different methods under varying noise levels for the Mechpart (92 K) model

表7. Mechpart (92 K)模型在不同噪声水平下不同方法的对比

Mechpart (92 K)
	$RMS$				$RM{S}_{\tau }$
噪声	30%	40%	50%	60%	30%	40%	50%	60%
PCA	0.2422	0.2490	0.2531	0.2593	0.5707	0.6092	0.6461	0.6666
PCA_ad	0.2383	0.2453	0.2483	0.2542	0.5563	0.5748	0.6093	0.6339
disW	0.2418	0.2493	0.2535	0.2610	0.5699	0.6106	0.6521	0.6902
disW_ad	0.2367	0.2446	0.2465	0.2553	0.5372	0.5781	0.6123	0.6448

Figure 2. Line chart comparing the mean $RMS$ and mean $RM{S}_{\tau }$ values at the optimal scale for PCA and disW, using both fixed neighborhoods and adaptive neighborhoods across four models

图2. PCA和disW中使用固定邻域和自适应邻域的四个模型最优尺度下$RMS$ 均值和最优尺度下$RM{S}_{\tau }$ 均值的对比折线图

如表4~7和图2所示，四个模型在不同噪声水平下PCA_ad和disW_ad的$RMS$ 值和$RM{S}_{\tau }$ 值均低于PCA和disW的$RMS$ 值和$RM{S}_{\tau }$ 值，四个模型的$RMS$ 均值和$RM{S}_{\tau }$ 均值也有降低。这表明使用自适应邻域估计法向优于使用固定邻域，在两种经典的点云法向估计算法上应用自适应邻域算法后，法向估计的质量有明显提升。另外，从折线图可以明显看出，$RM{S}_{\tau }$ 值比$RMS$ 值的下降幅度更大。由于$RM{S}_{\tau }$ 值体现点云中的尖锐特征区域的法向误差，而$RMS$ 值体现点云的整体(包括平坦区域和尖锐特征区域)的法向误差，所以下降幅度更大表明了自适应邻域算法对特征处的改进更明显，相较于使用固定邻域，更能够保留几何细节。最后，从表和折线图都可看出，随着噪声水平的提高，四种方法下的$RMS$ 值和$RM{S}_{\tau }$ 值均有所提高。

本文绘制了两种噪声水平下四个模型的自适应邻域热力图，如图3所示。Fandisk (77 K)和Anchor (40 K)的噪声水平为30%，Cylinder (60 K)和Mechpart (92 K)的噪声水平为50%。热力图的绘制采用按比例抽样的方式。若点云数量超过2万，按比例20%抽样(如10万点抽20%即2万点)，确保抽样均匀覆盖整个点云，并且抽样绘制能够保证可视化的效果。由图3可以明显看出，自适应邻域算法能够根据点的几何特性自适应地调整邻域大小。不同颜色代表自适应邻域的大小不同，点在尖锐特征处或尖锐特征附近，自适应邻域较小，呈现深蓝色；点在平坦区域，自适应邻域较大，呈现红色。

Figure 3. Heatmap of the adaptive neighborhoods

图3. 自适应邻域热力图

Table 8. Visual comparison of normal estimation errors from different algorithms

表8. 不同算法法向估计结果误差的可视化比较

RMS	0.1879	0.1712	0.1852	0.1688
RMS	0.1823	0.1712	0.1780	0.1673
RMS	0.1293	0.1101	0.1248	0.1008
RMS	0.2531	0.2483	0.2535	0.2465
	(a) PCA	(b) PCA_ad	(c) disW	(d) disW_ad

表8展示了PCA、PCA_ad、disW和disW_ad对四个点云模型进行法向估计的结果误差，点云的颜色代表各点的法向角度的均方根误差值(RMS)。四个模型选取的噪声水平均为50%。通过可视化比较可以看出，应用自适应邻域算法后，图像上深蓝色区域增多。表中RMS值为四个模型在50%噪声水平下的RMS值，能够明显看出RMS值有所降低。综上，图形和数据均表明使用自适应邻域能够降低法向估计的均方根误差值(RMS)，本文的自适应邻域算法能够提高法向估计的质量。

4. 结论

本文提出一种自适应邻域算法，通过逐步增长邻域大小的方式，给出点的合适邻域，用于后续的法向估计。本文的自适应邻域算法可应用于多种使用固定邻域的点云法向估计方法，在保留几何细节的基础上尽量抑制噪声对法向估计的影响，提高点云法向估计的准确性和可靠性。虽然该自适应邻域算法可应用于多种使用固定邻域的点云法向估计方法中，但本文仅在PCA和距离加权最小二乘拟合方法中应用，该算法在其它方法中的应用仍需继续进行实验，同时对于高噪声水平下算法的有效性也是未来的研究方向。

NOTES

^*通讯作者。