移动最小二乘算法理解

2023-03-12 21:14 作者:生医小王子 0人读过 | 我要投稿

一、概述

当点云噪声较小且分布均匀时，我们更容易重建出光顺表面。Marc等人[1]在2003年提出使用移动最小二乘（Moving Least Square, MLS）算法来平滑三维点云。该算法思想比较简单，如图1，使用局部点云 $p_i$ 进行多项式拟合，得到一个拟合曲面 $S_P$ ，然后使用拟合曲面上的投影替代原数据点。PCL实现了该算法，并增加了3种点云增采样方法，下面根据PCL的具体实现，简要介绍算法的实现流程。

二、算法流程

如图2，已知点 $r$ 和它的邻域点集 $p_i$ ，想求取点 $r$ 在拟合曲面 $S_P$ 上的投影，分2步。首先计算出一个二维参考平面H，让点 $p_i$ 能投影至平面点 $(x_i%2Cy_i)$ ，且距离为 $f_i$ 。然后计算二维拟合曲面 $t$ ，因变量为 $f_i$ 。从而点 $r$ 在拟合曲面 $S_P$ 上的投影计算过程为：计算3D点 $r$ 在平面H上的2D投影点 $q$ ，计算拟合曲面 $g$ 在点 $q$ 处的函数值 $t$ ，最终点 $r$ 在曲面 $S_P$ 上的投影值为 $q%2Btn$ ，其中 $n$ 为平面H的法线。

1. 计算参考平面H

参考平面H定义为： $H%3D%5C%7Bx%7C%5Clangle%7Bn%2Cx%7D%5Crangle-D%3D0%2Cx%20%5Cin%20R%5E3%5C%7D$ ，其中 $%5Clangle%7Bn%2Cx%7D%5Crangle$ 为点x到平面的距离，D为常数。通过最小化下式（1）来计算参考平面H。其中 $%5Clangle%20n%2Cp_i%5Crangle%20-D$ 为点 $p_i$ 到平面H的距离； $%5CVert%20p_i-q%5CVert$ 为 $p_i$ 到点 $r$ 在H上的投影点q的距离； $%5Ctheta$ 为平滑的单调递减函数，一般用高斯函数定义。

$%5Csum%20_%7Bi%3D1%7D%5EN%20(%5Clangle%20n%2Cp_i%5Crangle%20-D)%5E2%5Ctheta(%5CVert%20p_i-q%5CVert)$ (1)

2. 计算二维拟合曲面 $g$

通过最小化下式（2）来计算多项式拟合曲面 $g$ 的参数。

$%5Csum_%7Bi%3D1%7D%5EN(g(x_i%2Cy_i)-f_i)%5E2%5Ctheta(%5CVert%20p_i-q%5CVert)$ (2)

其中，当使用高斯函数定义 $%5Ctheta$ 时，如式（3）所示。常量参数h决定了邻域点集 $p_i$ 的选取范围；尺寸小于h的特征都会被平滑掉；h越大，点云越平滑。

$%5Ctheta%20(d)%3De%5E%7B-%5Cfrac%7Bd%5E2%7D%7Bh%5E2%7D%7D$ (3)

3. 点云上采样

从MLS算法原理上看，空间上任意点都可以计算出在拟合曲面上的投影，为此PCL提供了3种点云上采样方法，下面简单介绍一下。

SAMPLE_LOCAL_PLANE：以q点为圆心，在平面H上选取一个圆形区域，在该区域内均匀采点，并计算这些点在拟合曲面 $S_P$ 上的投影
RANDOM_UNIFORM_DENSITY：以q点为中心，在平面H上随机取点，并计算这些点在拟合曲面 $S_P$ 上的投影
VOXEL_GRID_DILATION：使用3D网格覆盖点云空间，选取靠近点云的3D网格点，计算这些网格点在拟合曲面 $S_P$ 上的投影

三、参考文献

[1] M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin, C. T. Silva. Computing and Rendering Point Set Surfaces. IEEE Transactions on Visualization and Computer Graphics. 2003. 9(1): 3-15

标签：MLS PCL

移动最小二乘算法理解

一、概述

二、算法流程

三、参考文献