散文網 » 生活 »日常 » 移動最小二乘算法理解

移動最小二乘算法理解

2023-03-12 21:14 作者:生醫(yī)小王子 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上選取一個圓形區(qū)域，在該區(qū)域內均勻采點，并計算這些點在擬合曲面 $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