逐点计算法向量,需要对每一个点拟合出它的切平面,一般使用邻域点信息来查找切平面。
选取要计算的点和它周围一定范围内的点可以拟合出一个平面,最基本的方法是通过最小二乘法取对这些点到平面的距离进行优化(计算量很大)。可以通过计算协方差矩阵来实现切平面的查找。
上面说的C的主分量,直观理解就是这些点在三个正交方向上的分量系数。比如下图:
对于上述所有点,计算协方差矩阵的特征值后,三个特征向量分别代表图中红绿蓝三个轴向上的分量大小。上图中,绿色方向拉伸程度最大,红色次之,蓝色最小。对于一个切平面来说,所有点的分散程度在法向量方向上一定最小。因此只要通过SVD分解得到C矩阵的特征向量,并且找到特征值最小的特征向量,在几何上这个特征向量与表面估计法向量共线(但需要注意该向量方向上可能与法向量相同或相反)。
对于局部最优投影采样,可以简单理解为将X均匀投影到P上,对X投影主要有两个要求:1. X要能投影到表面上(吸引力,吸引X的点到P上);2.X要能均匀地分散到表面上(排斥力,让X内部分散开)。
下图是LOP算法示意图:
左上图中,绿色点是原始点云P,红点是要投影点的集合X。最初投影结果如右上所示,红色点投影到了比较集中的一个小范围中,然后通过迭代优化,红点之间相互排斥,但排斥的距离不会超过绿点约束的范围,因为绿点对红点有吸引力。左下图是经过几轮迭代后,红点逐渐散开到整个表面,右下图是经过多次迭代后得到的较为理想的均匀分布的情况。最后使用点云Q来计算法向量,此时计算的法向量精度更高。
WLOP改进了LOP,主要是加入了一项基于点云密度的局部权重项,并且初始的X可以理解为是原有点云的一个下采样的点云。WLOP和LOP的效果对比如下:
2012年,Huang又提出了对于边界敏感的点云重采样算法。2019年Wang Yifan提出基于patch的3D点云上采样算法。