Iteratively weighted principal component analysis and orientation consistency for normal estimation in point cloud

问题背景

点云只是一组三维坐标。去噪、分割、曲面重建和可视化等后续处理都需要每个点的表面法向，因此法向估计是点云处理中的一项基础操作。经典方法由 Hoppe 等人提出：用主成分分析（PCA）对每个点的近邻拟合平面，并以该平面的法向作为点的法向。这一方法假设邻域近似为平面，在点稀疏或表面存在尖锐边的地方表现欠佳：例如，在直角处法向可能绕着拐角逐渐过渡，而不是反映真实的边缘（图 2）。

当各点密度不同且存在局部尖锐特征时，相邻点的法向方向也可能不一致，有的指向内侧，有的指向外侧。滚球法（ball-pivoting）和泊松（Poisson）等重建方法都要求法向朝向一致。尖锐特征处的法向不准确，会使重建后的尖锐特征变得模糊；法向朝向不一致，则可能导致重建曲面出现破损。

方法原理

该方法以 PCA 平面拟合为核心，并在其基础上加入两项改进。为提高法向的鲁棒性和可靠性，它按距离和法向相似度为每个邻点加权，并将加权拟合重复数次，作者称之为迭代加权主成分分析（IWPCA）。为使法向朝向一致，它先利用点云中心翻转法向，再沿最小生成树（MST）传播朝向。

1. 局部平面拟合。 用 Kd 树查找每个点的 k 近邻，并对其进行最小二乘平面拟合。邻域协方差矩阵最小特征值对应的特征向量即为法向。
2. 双边权重。 IWPCA 以该点本身为中心构造协方差矩阵，并为每个邻点赋予两种权重。空间权重随邻点与该点距离的增大而减小，由 σ_d 控制，通常取 kNN 搜索半径的一半；法向权重随邻点法向与该点法向偏差的增大而减小，由 σ_n 控制，通常取 15° 到 30°。首次计算时，每个点的法向均设为 (1, 0, 0)，因此法向权重起初是均匀的。
3. 迭代。 每一轮都把上一轮得到的法向代入法向权重。迭代次数越多，估计越好，但耗时也越长；作者建议迭代 2 到 3 次，并以最后一轮的结果作为输出。
4. 向外预翻转。 计算整个点云的中心，将所有指向该中心的法向翻转。
5. 沿最小生成树传播。 用 Prim 算法在相邻点之间构建最小生成树，边权为 1 − |n_i · n_j|。从根节点开始，若子节点法向与父节点法向的点积为负，则翻转子节点的法向。

对于尖锐部位，还可以用同样的空间权重和法向权重对法向进行平滑（双边加权平滑）。在作者的实验中，这使尖锐部位的法向更加鲁棒，但可靠性有所下降；由于 IWPCA 本身已能提高边缘处法向的鲁棒性，作者建议仅在需要时使用。

实验结果

论文中的对比均为可视化比较。在立方体上，IWPCA 提高了尖锐边处法向的鲁棒性；经 MST 重新定向后，全部法向的可靠性、鲁棒性和朝向一致性都得到改善，立方体的形状也更加清晰（图 7）。用泊松方法重建立方体时，基于 IWPCA 法向重建出的棱和顶点比基于经典 PCA 法向的更加锐利、清晰（图 8）。在尖锥上，经典 PCA 在锥顶处的法向结果不理想，部分点的法向未能算出，底部也有许多法向指向内侧；IWPCA 提高了顶部和底部法向的鲁棒性（图 9）。在扫描曲面上，预翻转与 MST 传播（步骤 4–5）修正了朝向不一致的法向，绝大多数法向指向曲面的凸起一侧（图 11）。

IWPCA 的计算量大于经典 PCA，其运行时间包含了法向重定向过程。迭代 1 次时，它比 PCA 慢；迭代 3 次时，它比连续运行 3 次经典 PCA 略快。实验运行环境为 Windows 7（64 位）、Intel Core i7-5650U CPU（2.20 GHz）和 8 GB 内存。邻域大小 k 以及权重参数 σ_d 和 σ_n 不易确定，目前依经验选取；作者提出，今后可根据局部曲率、噪声分布和点密度来确定这些参数。